下载网址_如何推广网站最有效_百度站长工具数据提交_模板建站和开发网站区别

前言

我们之前学过了顺序表，认识到本身就是一段连续的储存地址构成的空间，可以不断通过动态分配内存构成空间，而链表在空间上与它不同。

一、链表的概念和结构

1.1概念

链表是一种物理存储结构上非连续的、非顺序的存储结构，数据元素的逻辑结构是通过链表中的指针链接次序实现的。

1.2结构

链表由一组节点组成，每个节点包含数据和指向下一个节点的指针。链表可以是单向的，即每个节点只有一个指向下一个节点的指针；也可以是双向的，每个节点有指向前一个节点和后一个节点的指针。链表可以动态地分配内存空间，灵活地插入、删除元素，但查找元素的效率相对较低。这一篇只讲一下单向的链表，也就是单链表。

就类似上面一样，前一个节点里的指针变量指向下一个节点的地址，最后成为一条链，这样就是一个单链表。

1.从图中我们可以看到，链式结构在逻辑上是连续的，但是在屋里上不一定连续。

2.现实中的节点一般都是从堆上申请出来的。

3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

二、链表的实现

1、节点本身结构

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;//不能这么写//SListNode* next;//c++可以这么写，但是C语言不能这么写，这里struct SListNode才是一个类型//SLTNode* next;//typedef在十五行以后才起作用
}SLTNode;

我们知道一个节点就是一个结构体，这里把SLTDataType定为是int的别名，以后凡是设计到整形数据的就可以用它来定义，方便理解。接着结构体SListNode里面定义两个变量，一个是节点本身的数据，另一个是用来存放下一个节点地址的指针，结构体SListNode别名SLTNode，方便后续的使用。

2.链表打印

我们首先想一个问题，链表的打印是否涉及到链表本身的修改？链表如果为空的话，链表打印可以不可以？

//打印
void SLTPrint(SLTNode* phead)
{//这里不需要断言，因为空的表也可以打印SLTNode* cur = phead;//while (cur != NULL)while(cur){printf("%d-->", cur->data);cur = cur->next;}printf("NULL\n");
}

链表打印不涉及到修改链表，所以这里传入一个链表的首地址就可以，通过另一个结构体指针变量来接收这个地址，通过循环就可以实现链表的打印，当然链表的最后是NULL，这里用一行打印显示出来。如果链表里面是空的话，就可以直接打印NULL，所以这里不需要对链表是否为空进行一个判断。

void Test1()
{SLTNode* plist = NULL;SLTPrint(plist);
}

通过测试发现没有毛病：

3.定义一个首节点

为什么要写一个这样的函数，因为我们后续的实现，包括插入，删除，查找什么的都可能会需要这一段代码，为了防止复用，所以就直接自己封装一个函数代码，以后调用就方便多了。

//定义一个首节点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("Malloc::");return;}//对首节点初始化newnode->data = x;newnode->next = NULL;return newnode;
}

我们如果传入一个首节点，那么就需要有一个节点的数据，所以这里的参数就传入一个数据的值，之后通过申请一个节点的空间，对节点进行初始化，这个节点的值是参数的数据，节点的下一个地址就是NULL，因为这里是首节点，后续没有其它节点了。返回这个节点。

4.尾插

当然顺序表有尾差，那么链表也有尾插。对于链表的尾插，我们需要考虑链表是否为空，为空的话那尾插就相当于链表中加入一个节点并且有且只有一个节点，如果有多个节点，就需要寻找到最后一个节点，在后面加上新节点。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)//二级指针把实参修改连接，*pphead其实就是plist
{assert(pphead);//先定义一个节点SLTNode* newnode=BuySLTNode(x);if (*pphead == NULL){*pphead=newnode;}else{//找尾SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
//单链表这里改变实参就用二级传地址，不改变就用一级

这里因为要对实参进行修改，而实参是一个指针，如果要对它进行修改，那么这里的参数应该是一个二级指针，对二级指针进行解引用就是要改变的链表。这里要对链表进行一下断言，因为要判断链表是否存在，如果不存在运行的时候错误提示，一目了然。

逻辑上就是如果链表里节点为空，尾插就相当于在链表里创建一个新节点，通过BuySLTNode（x）函数就可以实现。如果不为空，那么就通过循环找到最后的节点，如果一个节点的下一个节点地址为空，那么这个节点就是最后一个节点，这里我们通常不对链表本身进行操作，而是通过别的变量来进行操作，找到最后的节点后把新创建的节点赋给最后节点的后一个节点就可以了。

我们可以通过代码演示一下：

void Test2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPrint(plist);
}

5.头插

头插还是比较很好想的，当我们插入一个节点：

只要把新的节点的next指针指向原来的第一个节点，之后把新节点定义为首节点就可以了。

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

我们可以通过运行来看一下：

void Test3()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPrint(plist);
}

这里尾插的效率没有头插的效率高，可以通过代码就可以看出来。

6.尾删

尾删分为三个步骤，检查，分情况单个节点，或者多个节点进行操作。凡是删除，应该检查链表是否存在，链表里是否有节点，如果只有一个节点，那么把这个节点释放掉就可以，如果有多个的节点，那么就要找到最后的节点，进行删除。（这里有一个细节）

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead); //暴力检查assert(*pphead);温柔检查//if (*pphead = NULL)//	return;//1.只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//2.多个节点SLTNode* tail = *pphead;SLTNode* prev=NULL;/*while (tail->next->next != NULL){tail = tail->next;}*/while (tail->next != NULL){prev = tail;tail = tail->next;}/*free(tail->next);*/free(tail);tail = NULL;prev->next = NULL;//这两种方法没有什么大差别
}

一个节点很简单，找到了释放掉置成空指针就可以，但是多个节点的时候，我们通过循环找到了最后的节点，该怎么操作？

我们实现的是找到了最后的节点，但我们想要它被删除，这个节点被释放后，它的上一个节点的next指向就得为null。

所以这里通过双指针prev和tail，一前一后，当tail找到后被释放后，prev的next指针指向Null。即可实现尾删。

void Test4()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPopBack(&plist);SLTPrint(plist);
}

7.头删

头删就是把原本的头节点的地址换为第二个节点的地址，让第二个节点变成了头节点，之前的头节点释放掉。

//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);温柔检查//if (*pphead = NULL)//	return;SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}

同样的先对其进行检查，然后，定义一个头结点地址变量用来存之前的头结点，然后头结点被赋予第二个节点的地址，之前的头结点被释放掉。就实现了头删。

void Test5()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPopFront(&plist);SLTPrint(plist);
}

8.查找

这里是查找一个数的指针并返回。

//查找,这里查找一下这个值为x的指针并返回
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

通过一个循环就可以实现。

void Test6()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);if (SListFind(plist, 2))printf("找到了");elseprintf("没有找到");
}

我们可以找一下2

9.pos之前插入，不能实现尾插

这里要检测pos是否为空，我们这里的pos也是一个节点，目的是在pos这个节点之前插入新节点，当然我们找到的pos是通过查找SLTPushBack函数而实现的。

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//pphead永远不会为空，因为它是地址//检测pos是否为空assert(pos);//头部的插入if (pos == *pphead){SLTPushFront(pphead, x);}//找到pos的前一个位置//这里默认认为pos是存在在链表里的节点//如果pos不是节点，那么就会出现空指针的问题else{SLTNode* prev = *pphead;while(prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}

如果就是一个节点，那么就是直接头插一个新节点就可以，如果有多个节点，那么就可以找到pos。

在pos之前进行加入一个节点，把next的指向更新就可以了。

void Test7()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTNode* pos = SListFind(plist, 2);SListInsert(&plist, pos, 9);SLTPrint(plist);
}

10.pos后面插入

这个就很简单了，对比pos前面插入就非常的简单

//pos后面插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}

逻辑就是创建一个新节点，通过更新next指向地址就可以实现。

void Test8()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTNode* pos = SListFind(plist, 2);SLTInsertAfter(pos, 9);SLTPrint(plist);
}

11.pos位置删除

依旧是分情况，如果链表里面只有一个节点，那么就可以通过头删或者尾删来删除这一个节点，但是推荐用头删，因为头删比尾删效率高一些。

//pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);//assert(*pphead);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;//这里没有什么用，形参的改变不影响实参}
}

如果是多个节点的话需要找到pos的节点，pos前的节点指向pos后面的节点，然后把pos释放，就实现了pos位置的节点删除。

void Test9()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTNode* pos = SListFind(plist, 2);SLTErase(&plist, pos);SLTPrint(plist);
}

12.pos后面删除

//pos位置后面删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* newnode = pos->next;pos->next = newnode->next;free(newnode);newnode = NULL;
}

找到了pos，然后把pos的next指向pos->next->next，这里pos->next就是newnode，所以释放newnode后就实现了pos后面的节点的删除。

void Test10()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTNode* pos = SListFind(plist, 2);SLTEraseAfter(pos);SLTPrint(plist);
}

总结

单链表不适合在前面插入和删除位置，单链表适合在后面插入和删除位置。