前言
在上一期中我们学习了顺序表，顺序表可以通过索引（下标）快速地存、取表中元素，但文章末尾提及它有缺点，例如头插或从中间插入效率低等，而链表可以有效的解决这些问题。那么就让我们走进链表的学习~~
一、什么是链表
1.1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构：
注意：
1.链式结构在逻辑上是连续的，但在物理上不一定连续。
2.节点都是从堆上申请的。
3.从堆上申请空间，是按一定策略分配的，申请的空间可能连续，也可能不连续。
1.2 链表的分类
- 单向或者双向（单链表或者双链表）
- 带头或者不带头（带哨兵位和不带哨兵位）
- 循环或者非循环
1.3 单链表的结构
typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode;
这种链表被称为无头+单向+非循环链表
二、链表的实现
📖2.1 创建节点
我们想使用链表来实现各种功能得先有链表，所以首先使用malloc创建节点。
SListNode* BuySListNode(SLTDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
📖2.2 头插
要想让链表连起来，就要让newnode->next存放下一个节点的地址，也就是旧链表plist的值，然后将newnode的地址存放在plist中，形成新的链表。无论一开始有没有节点，头插都是相同的。
// 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pplist; //*pplist=plist *pplist = newnode; }
📖2.3 头删
头删时如果先释放空间，就会找不到下一个节点的地址；如果先把下一个节点的地址赋给*pplist就会导致无法释放空间，所以我们要创建一个临时变量来存放下一个节点的地址。
// 单链表头删 void SListPopFront(SListNode** pplist) { assert(*pplist); SListNode* newnode = (*pplist)->next; free(*pplist); *pplist = newnode; }
📖2.4 尾插
我们在尾插时，会有两种情况，链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误，接下来就让我们学习学习这两种尾插的情况。
💭链表不为空
当我们传递的是plist的值，屏幕上并没有打印出我们想要的结果。这是为什么呢？
形参是实参的一份临时拷贝，形参的改变不会影响实参，pplist的改变不会影响plist。 临时变量出作用域销毁，phead和newnode销毁，找不带开辟的节点，会造成内存泄漏。
确做法是要将plist的地址传递过去，我们通过解引用就可以改变plist。plist中存放的是指针，我们传递指针的地址要用二级指针接收。
💭链表不为空
链表不为空时，我们要找到尾节点。这里我们要注意不能使用 tail!=NULL 判断。这样我们无法把链表连接起来。
// 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x) { assert(pplist); SListNode* newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* tail = *pplist; while (tail->next) { tail = tail->next; } tail->next = newnode; } }
📖2.5 尾删
在尾删时也有两种情况，一种是有很多节点，另一种是只剩一个节点，当删最后一个节点时，要改变plist的值，所以我们要传递plist的指针。我们要使用两个指针，当后面的指针释放后，可以利用前面的指针将最后一个节点的next置为空。
// 单链表的尾删 void SListPopBack(SListNode** pplist) { assert(*pplist); //一个 if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } //多个 else { SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
📖2.6 查找
循环判断时不要使用cur->next，这样写最后一个数据要单独处理不方便，找到时就返回此时的地址。
// 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return 0; }
📖2.7 在pos位置之前插入
在pos位置之前插入有一种特殊的情况就是头插，要改变plist的值，我们要传二级指针进去。同时我们要创建一个指针变量，找到pos之前的位置，才能使链表连接起来。
void SListInsertAfter(SListNode** pplist,SListNode* pos, SLTDateType x) { assert(pos); if (pos == *pplist) { SListPushFront(pplist, x); } else { SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } SListNode* newnode = BuySListNode(x); newnode->next = pos; prev->next = newnode; } }
📖2.8 在pos位置之后插入
这里我们要注意地址赋值的顺序，顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域，就会丢失下一个节点的地址。
void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }
📖2.9 删除pos位置
有可能删除的是头节点，所以要传递二级指针。
// 删除pos位置 void SLTErase(SListNode** pplist, SListNode* pos) { assert(pos); if (pos == *pplist) { SListPopFront(pplist); } else { SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; pos = NULL; free(pos); } }
📖2.10 删除pos后面位置
void SListEraseAfter(SListNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { SListNode* next = pos->next; pos->next = next->next; free(next); next = NULL; } }
📖2.11 销毁
void SListDestory(SListNode** pplist) { assert(pplist); SListNode* cur = *pplist; SListNode* next = NULL; while (cur->next != NULL) { next = cur->next; free(cur); cur = NULL; } *pplist = NULL; }
三、总代码
SList.h
#pragma once // slist.h #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; // 动态申请一个节点 SListNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 单链表在pos位置之前插入x void SListInsert(SListNode** pplist,SListNode* pos, SLTDateType x); // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos,SLTDateType x); // 删除pos位置 void SLTErase(SListNode** pphead, SListNode* pos); // 删除pos后面位置 void SListEraseAfter(SListNode* pos); // 销毁 void SListDestory(SListNode** pplist);
SList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"SList.h" // 动态申请一个节点 SListNode* BuySListNode(SLTDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } // 单链表打印 void SListPrint(SListNode* plist) { SListNode* tail = plist; while (tail) { printf("%d->", tail->data); tail = tail->next; } printf("NULL\n"); } // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* tail = *pplist; while (tail->next) { tail = tail->next; } tail->next = newnode; } } // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; } // 单链表的尾删 void SListPopBack(SListNode** pplist) { assert(*pplist); if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } } // 单链表头删 void SListPopFront(SListNode** pplist) { assert(*pplist); SListNode* newnode = (*pplist)->next; free(*pplist); *pplist = newnode; } // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return 0; } void SListInsert(SListNode** pplist,SListNode* pos, SLTDateType x) { assert(pos); if (pos == *pplist) { SListPushFront(pplist, x); } else { SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } SListNode* newnode = BuySListNode(x); newnode->next = pos; prev->next = newnode; } } // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } // 删除pos位置 void SLTErase(SListNode** pplist, SListNode* pos) { assert(pos); if (pos == *pplist) { SListPopFront(pplist); } else { SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; pos = NULL; free(pos); } } void SListEraseAfter(SListNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { SListNode* next = pos->next; pos->next = next->next; free(next); next = NULL; } } void SListDestory(SListNode** pplist) { assert(pplist); SListNode* cur = *pplist; SListNode* next = NULL; while (cur->next != NULL) { next = cur->next; free(cur); cur = NULL; } *pplist = NULL; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~
