3.2 链表的分类
实际中链表的分类的有很多，这里只介绍两类：单向不带头，双向带头
单向不带头：结构简单，一般不会单独用来存储数据。更多的是作为其他数据结构的子结构，例如哈希桶
双向带头：结构最复杂，一般用来单独存储数据。
3.3 链表的实现
单向不带头
定义类型和结构体
typedef int LSdatatype; typedef struct Slist { LSdatatype data; struct Slist* next; }SL;
打印单链表
//打印单链表 void SLprint(SL* phead); void SLprint(SL* phead) { SL* tmp = phead; while (tmp != NULL) { printf("%d->", tmp->data); tmp = tmp->next; } printf("NULL\n"); }
销毁单链表
//销毁单链表 void SLdestory(SL* phead); void SLdestory(SL** pphead) { assert(pphead); SL* cur = *pphead; while (cur != NULL) { SL* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
由于每个节点中都保存下一个节点的地址，不能直接释放*pphead，需要创建临时变量进行替换。
插入数据，便需要创建一个新的节点，由于新节点的创建不止出现一次，为了方便，将其独立为函数
SL* CreateSLnode(LSdatatype x) { SL* newnode = (SL*)malloc(sizeof(SL)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; return newnode; }
头插
//头插 void SLpushfront(SL** pphead, LSdatatype x); void SLpushfront(SL** pphead, LSdatatype x) { SL* newnode = CreateSLnode(x); newnode->next = *pphead; *pphead = newnode; }
插入数据 1，2，3，4 监视如下
注意
改变数据，需要通过指针；改变指针，需要通过指针的指针。
由于上面是需要改变的指针，所有需要通过二级指针进行修改
在之后的学习中可以通过两种方式代替二级指针
- 返回新的链表头
- 设计为带哨兵位的链表
尾插
//尾插 void SLpushback(SL** pphead, LSdatatype x); void SLpushback(SL** pphead, LSdatatype x) { assert(pphead); SL* newnode = CreateSLnode(x); //1.plist 为空 改变结构体指针 if (*pphead == NULL) { *pphead = newnode; } //2.plist 不为空 改变结构体内容 else { //找尾 SL* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
尾插数据 5 ，监视如下
链表为空，插入第一个节点，改变SL*，通过结构体指针的指针pphead
链表不为空，插入节点，改变SL，通过结构体指针SL*tail
头删
//头删 void SLpopfront(SL** pphead); void SLpopfront(SL** pphead) { assert(pphead); SL* del = *pphead; //检查，避免数据删除完之后，继续删除数据，导致内存崩溃 //1 温柔的检查 while (*pphead == NULL) { return; } //暴力检查 /*assert(*pphead != NULL);*/ *pphead = (*pphead)->next; free(del); del = NULL; }
头删数据 4，监视如下
如果直接将第一个节点删去，就不能找到第二个节点，所以创建临时变量del保存第一个节点，之后再将其删去
尾删
//尾删 void SLpopback(SL** pphead); void SLpopback(SL** pphead) { assert(pphead); //1 温柔的检查 while (*pphead == NULL) { return; } //暴力检查 /*assert(*pphead != NULL);*/ //1 一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } //2 多个节点 else { 方法1 //SL* tail = *pphead; //while (tail->next->next != NULL) //{ // tail = tail->next; //} //free(tail->next); //tail->next = NULL; //方法2 //找尾 SL* tail = *pphead; SL* pre = NULL; while (tail->next != NULL) { pre = tail; tail = tail->next; } free(tail); tail = NULL; pre->next = NULL; } }
尾删数据5，监视如下
查找节点
//查找节点 SL* SLfind(SL* phead, LSdatatype x); SL* SLfind(SL* phead, LSdatatype x) { assert(phead); SL* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
在pos之前插入新节点
//在pos之前插入新节点 void SLinsert(SL** pphead, SL* pos, LSdatatype x); void SListInsert(SL** pphead, SL* pos, LSdatatype x) { assert(pphead); assert(pos); //pos在第一个节点 if (pos == *pphead) { SListPushFront(pphead, x); } else { SL* prev = *pphead; while (prev->next != pos) { prev = prev->next; // 暴力检查，pos不在链表中，或者pos的值是错误的 assert(prev); } SL* newnode = CreateSLnode(x); prev->next = newnode; newnode->next = pos; } }
在数据 3，插入数据4，监视如下
在pos后面插入新节点
//在pos后面插入新节点 void SLinsertafter(SL* pos, LSdatatype x); void SLinsertafter(SL* pos, LSdatatype x) { assert(pos); SL* newnode = CreateSLnode(x); newnode->next = pos->next; pos->next = newnode; }
在数据1 后面插入数据 0，监视如下
删除pos位置
//删除pos位置 void SLerase(SL* pphead, SL* pos); void SLerase(SL** pphead, SL* pos) { assert(pphead); assert(pos); //pos是第一个节点 if (*pphead == pos) { SLpopfront(pphead); } else { SL* tmp = *pphead; while (tmp->next != pos) { tmp = tmp->next; } tmp->next = pos->next; free(pos); //不需要将pos置空，改变pos不会改变链表 //pos=NULL } }
将数据2所在位置进行删除，监视如下
删除pos后面的位置
//删除pos后面的位置 void SLeraseafter(SL* pos); void SLeraseafter(SL* pos) { assert(pos); if (pos->next == NULL) { return; } else { SL* next = pos->next; pos->next = next->next; free(next); } }
将数据1所在位置后面的位置进行删除，监视如下
