含义
1.顺序表的回顾
之前的文章已经谈到了顺序表，关于顺序表，有一下的几种特点
1.中间，头部的删除，复杂度为O(N);
2.增容会有申请新的空间，拷贝数据，释放旧的空间，会有不小的消耗；
3：整容一般是呈2的倍数增长，但是也会造成一定的空间浪费，比如，当前的容量是100，满了以后·增加到200，我们继续插入5个数据，后面没有数据插入，就浪费了95个空间
2.链表的含义
那么，是否存在一种数据结构，能够解决上面的问题：
1.中间，头部数据的删除，不需要挪动数据
2.不需要扩容
3.不会造成空间的浪费
没错，就是今天的链表
链表的组成：
链表是由当前节点要存储的数据+下一个节点的地址组成的，就比如下面的这个
你可以把链表看成一节一节的火车车厢，想要加车厢的时候随时加，前面一个车厢掌管后面一个车厢的钥匙
放下一个节点的地址是为了方便找到下一个节点（这里有一点废话了哈），话不多说，上代码
typedef int SLdatetype;//链表的创建
struct Slist
{SLdatetype a;struct Slist* arr;
};
有的时候你觉得结构体的类型太长了，懒得写，以后在使用的时候也不太发表，可以换成下面的
typedef int SLdatetype;
typdef struct Slist
{SLdatetype a;struct Slist* arr;
}SL;
//下面的写法是不行的
typedef int SLdatetype;
typdef struct Slist
{SLdatetype a;SL* arr;//这种写法是不行的，因为编译器在执行程序的时候，是自上而下来扫描的，SL这种类型还没有//创建完毕
}SL;链表的打印
#include"Slist.h"
void SLprint(SL* phead)
{SL* ptemp = phead;//建立临时的变量，防止下次要找头节点的时候找不到了while (ptemp!= NULL){printf("%d->", ptemp->date);ptemp = ptemp->next;}printf("NULL");
}测试代码
#include"Slist.h"void test01()
{//在写的时候不建议这样写，这里只是为了测试//申请空间SL* node1 = (SL*)malloc(sizeof(SL));node1->date =1;SL* node2 = (SL*)malloc(sizeof(SL));node2->date =2;SL* node3 = (SL*)malloc(sizeof(SL));node3->date =3;//连接node1->next = node2;node2->next = node3;node3->next = NULL;SLprint(node1);
}int main()
{test01();return 0;
}输出结果
链表的尾插
SL* SLbuynode(SLdatetype x)
{SL* newnode = (SL*)malloc(sizeof(SL));newnode->date = x;newnode->next = NULL;return newnode;
}
void SLpushback(SL** pphead, SLdatetype x)
{assert(pphead);//判断有效SL* pnew = SLbuynode(x);if (*pphead == NULL){*pphead = pnew;return;}SL* Ptail = *pphead;while (Ptail->next){Ptail = Ptail->next;}Ptail->next = pnew;
}测试代码
void test01()
{SL* pptest = NULL;SLpushback(&pptest,1);SLprint(pptest);
}int main()
{test01();return 0;
}代码说明
对上面的代码进行的几点说明
SLpushback(&pptest,1);1.因为是对pphead进行的复制，所以上面函数进行的是传址调用，如果是传值调用的话，由于形参是实参的一份临时拷贝，所以在进行复制的时候，等到函数结束的时候形参销毁，该函数又没有返回值，所以对形参的改变并不会引起实参的改变
assert(pphead);//判断有效2.断言部分，当你传入的地址是空指针的时候，编译其会报错，所以加上断言，但是我觉得具体原因是：当你传入空指针的时候，对该地址进行解引用的时候是找不到你要插入的位置的，就像别人给了你一张空头支票，你去银行去取钱，结果柜员一看，根本就找不到支票里面的钱在哪个地方一样，这是你的表情一定会和下面的一样
3.对于*pphead是否需要断言，答案是否定的，那里就是需要插入数据，因此是不需要断言的
链表的头插
void SLpushfront(SL** pphead, SLdatetype x)
{assert(pphead);SL*pnew= SLbuynode(x);pnew->next = *pphead;*pphead=pnew;
}链表的尾删
void SLpopback(SL** pphead)
{assert(pphead);assert(*pphead);//链表只有一个节点的情况if ((*pphead)->next == NULL){*pphead = NULL;free(*pphead);return;}SL* tail = *pphead;SL* pre = NULL;//尾节点的前一个节点，在尾节点删除的时候，要将前面的节点的下一个节点置为空while (tail->next){pre = tail;//找到前驱节点tail = tail->next;}pre->next = NULL;free(tail);tail = NULL;}链表的头删
关于链表的头删，只需要把第一个节点释放掉，然后然第二个节点变成第一个节点就行了
void SLpopfront(SL** pphead)
{SL* pcur = *pphead;*pphead= pcur->next;free(pcur);pcur = NULL;
}记住，在删除链表的头节点的时候，要先把头节点赋值给第二个节点，在对头节点进行释放，比如，写成下面的代码就不行
void SLpopfront(SL**pphead)
{freep(*pphead);*pphead=(*pphead)->next;
}
//因为已经释放了头节点，头节点已经变成了空指针
//空指针的下一个节点是不知道的链表的查找
链表的查找和数组元素的查找是一样的，都是通过遍历的方式查找，找到了就返回当前的地址，没有找到就返回空指针
SL* SLfind(SL** pphead, SLdatetype x)
{assert(pphead);SL* pfind = *pphead;while (pfind){if (pfind->date == x){return pfind;//找到了，返回当前的指针}pfind = pfind->next;}return NULL;//没有找到，返回空指针
}在指定位置之前插入数据
思路：情况一
该链表只有一个节点，直接调用头插函数
情况2：
该链表有多个链表，通过遍历的方式找到前驱节点，改变前驱节点的指向
void SLpushposfront(SL** pphead, SL* pos, SLdatetype x)
{assert(pphead);assert(*pphead);SL* prev = *pphead;//定义前驱节点if ((*pphead)->next == NULL)//该链表只有一个节点{SLpushfront(pphead, x);return;}SL* pnew = SLbuynode( x);while (prev->next != pos){prev = prev->next;}//该节点为前驱节点prev->next = pnew;pnew->next = pos;
}在指定位置之后插入节点
void SLpushposback(SL* pos, SLdatetype x)
{assert(pos);SL* posback = pos->next;//记录pos后面位置的节点SL* newnode = SLbuynode(x);pos->next = newnode;newnode->next = posback;
}对上面代码的说明
为啥要在插入节点之前的步骤中先记录pos后面的节点嘞？
原因上面的最后一句代码
newnode->next = posback;如果不记录的话，posback就变成了要插入的代码了，比如你写成这样
pos->next = newnode;
newnode->next = pos->next;//pos->next是newnode删除pos节点
思路：情况一：多个节点找到先驱节点，改变先驱的指向，让它指向pos节点的下一个节点
情况二：只有一个节点，执行头删或尾部删除
void SLerasepos(SL**pphead, SL* pos)
{assert(pphead);assert(*pphead);SL* prev = *pphead;//定义前驱节点if ((*pphead)->next == NULL)//只有一个节点，删除尾节点{SLpopfront(pphead);return;}while (prev->next != NULL){prev = prev->next;}//退出循环，前驱节点被找到prev->next = pos->next;free(pos); pos = NULL;
}注意：上面最后三行代码的顺序不能交换，不能写成下面的代码
free(pos);
pos = NULL;
prev->next = pos->next;原因是pos节点已经被释放，后面哪来的pos->next
删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos->next不能为空assert(pos->next);//pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}摧毁链表
void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
