3.3尾删
如果是空链表，我们可以直接使用断言。
一个节点直接释放掉plist.两个节点以上就首先需要找尾，先看下面这个代码。（**pphead就是plist）
上面这个代码找到尾后，直接把taill置空，肯定不行
free（taill）的本质是把tail指向的节点给free了，再把taill置空。出了作用域，taill销毁，那他前一个还是空。所以还需要找到taill的前一个。
以下两种解决办法都可以。
最终完整代码如下：
测试结果如下：
删除6个。
3.4头删
同理，头删与尾删大同小异，头删实现更简单。
测试结果如下：
3.5查找
查找实质还是遍历链表：
3.6在pos位置之前插入x
pos是任意一个节点，防止为空呢，我们先检查一下：
那他还有什么特殊情况呢，头插，尾插就是其中两种，其次处理pos在中间位置。
完整代码如下：
测试结果如下：在给定数字前面插它的十倍
3.7在pos位置以后插入x
要是后插就会便捷很多。因为他不可能实现头插，所以就会很简单。
如果是第一个代码：测试结果如下：
进入了死循环。
修改后完整代码如下：
测试结果如下：
3.8删除pos位置
删除部分就简单了。分情况，头删首先需要单独处理，其次尾删是不需要单独处理的，因为正常删就已经包含尾删情况了。
完整代码如下：
测试结果如下：
3.9删除pos的后一个位置
删后一个考虑的就是要找到前一个，处理好这个就简单了。其次有个坑，它删不了头。
完整代码：
4.单链表结构与顺序存储结构的优缺点
简单地对单链表结构和顺序存储结构做对比：
通过上面的对比，我们可以得出一些经验性的结论：
1.若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如说游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不太合适了，单链表结构就可以大展拳脚。当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。
2.当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表给构。这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天，这种用顺序存储结构效率会高很多。
总之，线性表的顺序存储结构和单链表结构各有其优缺点，不能简单地说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能。
5.链表完整代码：
5.1 SList.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode* phead); SLTNode* BuySListNode(SLTDataType x); //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x); //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x); //尾删 void SLTPopBack(SLTNode** pphead); //头删 void SLTPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //在pos位置之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos位置以后插入x void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos);
5.2 SList.c
#define _CRT_SECURE_NO_WARNINGS #include"SList.h" //打印函数 void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; //while (cur != NULL) while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //开辟新节点 SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { //改变的结构体的指针 *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } //改变的结构体 tail->next = newnode; } } //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } //尾删 void SLTPopBack(SLTNode** pphead) { //空 assert(*pphead); //一个节点 //一个以上节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; /*SLTNode* tailprev = NULL; SLTNode* tail = *pphead; while (tail->next) { tailprev = tail; tail = tail->next; } free(tail); tail = NULL; tailprev->next = NULL;*/ } } //头删 void SLTPopFront(SLTNode** pphead) { //空 assert(*pphead); //非空 SLTNode* newnode = (*pphead)->next; free(*pphead); *pphead = newnode; } //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(pos); if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } } //在pos位置以后插入x void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySListNode(x); /*pos->next = newnode;*/ newnode->next = pos->next; pos->next = newnode; } //删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); //pos = NULL; } } //删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos) { assert(pos); //检查Pos是否为尾节点 assert(pos->next); SLTNode* posNext = pos->next; pos->next = posNext = posNext->next; free(posNext); posNext = NULL; }
5.3 Test.c
#define _CRT_SECURE_NO_WARNINGS #include"SList.h" //交互链表测试 void TestSList1() { int n; printf("请输入链表的长度：\n"); scanf("%d", &n); printf("请依次输入每个节点的值：\n"); SLTNode* plist = NULL; for (size_t i = 0; i < n; i++) { int val; scanf("%d", &val); SLTNode* newnode = BuySListNode(val); //头插 newnode->next = plist; plist = newnode; } SLTPrint(plist); } //测试尾插头插 void TestSList2() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTPushFront(&plist, 10); SLTPushFront(&plist, 20); SLTPushFront(&plist, 30); SLTPushFront(&plist, 40); SLTPrint(plist); } //测试尾删 void TestSList3() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); /*SLTPopBack(&plist); SLTPrint(plist);*/ } //测试头删 void TestSList4() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); /*SLTPopFromt(&plist); SLTPrint(plist);*/ } void TestSList5() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTNode* pos = SLTFind(plist, 40); if (pos) { pos->data *= 10; } SLTPrint(plist); int x; scanf("%d", &x); pos = SLTFind(plist, x); if (pos) { SLTInsert(&plist, pos, x * 10); } SLTPrint(plist); } void TestSList6() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); int x; scanf("%d", &x); SLTNode* pos = SLTFind(plist, x); if (pos) { SLTErase(&plist, pos); } SLTPrint(plist); } void TestSList7() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); int x; scanf("%d", &x); SLTNode* pos = SLTFind(plist, x); if (pos) { SLTEraseAfter(pos); pos = NULL; } SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); } int main() { TestSList7(); }
