数据结构|【自此文之后，学习链表一片坦途】数据结构|链表

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

文章目录

前言

一、什么是链表

1. 链表的概念

2. 链表的分类

2.1 单链表

2.2 双向链表

二、链表接口的实现

1. 创建新结点

2. 打印数据

3. 链表的头插法

4. 链表的尾插法

5. 链表的头删法

6. 链表的尾删法

7. 链表中数据的查找

8. 在任意位置前插入

9. 在任意位置后插入

10. 在任意位置后插入

11. 在任意位置后删除

总结

前言链表在实际当中的物理存储当中并不是连续的，我们平常所描述的链表两两相连接是为了方便理解所描述出的逻辑结构，在实际当中并不存在，就如同我们在高中物理当中所学的电场线一样，在实际当中并不存在。
那么链表到底是如何实现联系的呢？其实就是通过地址，链表分为数据域和指针域，这里的箭头就代表着地址，第一个链表的结点存放着第二个链表的地址，第二个链表存放着第三个链表结点的地址，以此类推，最后一个链表结点存放着NULL。
在C语言当中，由我们所学过的指针相关知识可有知道，指针<=>地址，准确的说指针就是地址，我们平常所说的指针其实代表指针变量，而 ” * “ 代表解引用的意思，就是根据地址把在这个地址存放的内容取出来。

文章图片

提示：以下是本篇文章正文内容，下面案例可供参考
一、链表 1.链表的概念及结构：

文章图片

2.拓展：

1）如图所示，链表在逻辑上是连续的，但是在实际当中的物理地址却并不一定是连续的
2）现实当中的结点都是从堆中申请出来的
3）从堆上申请出的空间，两次申请到的空间可能连续也可能不连续
4）要知道，在链表当中想要访问第二个结点就必须先知道第一个结点的地址也就是首地址，然后根据第一个结点当中的指针域中的第二个结点的地址来访问第二个结点，以此类推想要知道后一个结点就必须先知道该结点的前一个结点（该原理类似于俄罗斯套娃）

3.链表的分类：
1）单向或者双向：

文章图片

2）带头或者不带头：

文章图片

3）循环或者不循环：

文章图片

4.不同结构的特点：

1）无头单向非循环：结构简单，一般不会单独用来存储数据，实际中更多是用来作为其他数据结构的子结构
2）带头双向循环：结构复杂，一般用于单独存储数据，虽然结构复杂但是在使用的时候却非常方便、简单

二、单链表 1.单链表常用接口

// 无头、单向、非循环链表typedef int DataType; typedef struct SListNode { DateType data; struct SList* next; }SList; // 动态申请一个结点 SListNode* BuySListNode(DateType x); // 单链表打印 void SListPrint(SList* head); // 单链表尾插 void SListPushBack(SList** head, DateType x); // 单链表的头插 void SListPushFront(SList** head, DateType x); // 单链表的尾删 void SListPopBack(SListNode** head); // 单链表头删 void SListPopFront(SListNode** head); // 单链表查找 SListNode* SListFind(SList* head, DateType x); // 单链表在pos位置之后插入x void SListInsertAfter(SList* pos, DateType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SList* pos);

2.接口的代码实现
1）创建结点：

说明：这里接口对于链表的第一个结点的传参需要使用二级指针，至于为什么使用二级指针在文章的最后面会向大家说明，我们这里着重介绍知识点以及用法。

SList* BuyListNode(DataType x) { SList* newnode = (SList*)malloc(sizeof(SList)); if (newnode == NULL) { printf("malloc is fail\n"); exit(-1); } newnode->data = https://www.it610.com/article/x; newnode->next = NULL; return newnode; }

2）数据打印：

说明：
这里的”assert“代表断言，就是认为条件肯定正确，否则代码无法继续向下执行，
例如”assert（a）“，那么就意味着 a 必须存在，如果 a 不存在，系统会自动报错。

void SListPrint(SList* head) { assert(head); SList* cur = head; while (cur) { printf("%d", cur->data); cur = cur->next; } printf("\n"); }

3）单链表尾插：

说明：
首先：链表无法向顺序表一样支持随机访问，想要访问任何一个结点都必须从第一个结点开始访问，一个一个地向后移动直到找到要访问的结点为止（注意第一个结点并不等于头结点，我们常说的头结点是指哨兵卫结点，这个之后会给大家介绍）。

void SListPushBack(SList** head, DataType x) { assert(head); SList* newnode = BuyListNode(x); if ((*head) == NULL) { *head = newnode; } else { SList* tail = *head; while (tail->next) { tail = tail->next; } tail->next = newnode; newnode->next = NULL; } }

4）单链表头插：

说明：
这里的”*head==newnode“两个结点相等代表着把等号后面的结点的位置给与等号前面的结点，或者说让前面的结点到后一个结点的位置上去，这个与顺序表当中数组元素的赋值的理解恰好相反。

void SListPushFront(SList** head, DataType x) { assert(head); SList* newnode = BuyListNode(x); newnode->next = *head; *head = newnode; }

5）单链表尾删法：

说明：
1.当链表当中只有一个结点的时候，它的处理方式与有多个结点时不相同的。
2.进行尾删就是删除链表当中的最后一个结点，要想顺利删除链表的最后一个结点就必须找到链表的前一个结点，也就是倒数第二个结点，因为倒数第二个结点的指针域当中还存放着最后一个结点的地址，所以想要彻底删除最后一个结点就必须把倒数第二个结点的指针域置为空，然后将最后一个结点释放（free）掉。
3.这里使用双指针，tail 和 prev， prev跟着tail往前走，tail先走一步，prev后走一步到达tail 之前的位置，这样使得 prev 永远都在 tail 后面行走，等 tail 走到最后一个结点的时候，prev 正好处于倒数第二个结点。

void SListPopBack(SList** head) { assert(head); if ((*head)->next == NULL) { free(*head); *head = NULL; } else { SList* tail = *head; SList* prev = NULL; while (tail->next) { prev = tail; tail = tail->next; } prev->next = NULL; free(tail); tail = NULL; } }

6）单链表头删法：

说明：
直接释放掉单链表的第一个结点，然后把链表的下一个结点的位置给与第一个结点，或者说让链表的第一个结点（链表的首地址）到达原来的第二个结点处。
在释放第一个结点以前，必须先找到第二个结点的位置，因为如果不这样做，当释放掉第一个结点以后，就无法根据第一个结点找到第二个结点，那么这个时候就必须先找到第二个结点，并且用 ”next“ 标识出来，以便后续使用。

void SListPopFront(SList** head) { assert(head); SList* next = (*head)->next; free(*head); *head = next; }

7）元素数据查找：

SList* SListFind(SList* head,DataType x) { assert(head); SList* cur = head; while (cur) { if (cur->data =https://www.it610.com/article/= x) { return cur; } cur = cur->next; } return NULL; }

8）任意位置之前插入元素：
说明：
1.这里在传参的时候给出一个pos指针指向任意结点/
2.与之前相同，在pos的前一个位置插入结点就必须先找到pos结点的前一个结点，利用pos前、pos、和pos后三个位置进行”-->“的连接，是链表连贯起来。

void SListInsert(SList** head, SList* pos, DataType x) { assert(head); assert(pos); if ((*head)->next == NULL) { SListPushFront(head, x); } else { SList* newnode = BuyListNode(x); SList* cur = *head; while (cur->next != pos) { cur = cur->next; } cur->next = newnode; newnode->next = pos; } }

9）任意位置之前删除元素：

说明：
这个与上一个接口类似，先找到前一个结点的位置，但是注意这里必须先将pos前与pos后的结点连接起来，才能将pos释放掉，这个顺序绝对不能错误，因为想要访问pos后面的结点就必须通过pos访问，如果先将pos释放掉的话，那么将无法访问pos之后的结点，那么pos前和pos后的结点就无法串联起来了，那么一个链表将会从中断开。

void SListErase(SList** head, SList* pos) { assert(head); assert(pos); if ((*head)->next == NULL) { SListPopBack(head); } else { SList* cur = *head; while (cur->next != pos) { cur = cur->next; } cur->next = pos->next; free(pos); pos = NULL; } }

10）任意位置之后插入元素：

说明：
先找到pos的后一个位置并且标识出来，然后将新结点插入到pos的后面，新结点再与前后两个结点串联起来。

void SListInsertAfter(SList* pos, DataType x) { assert(pos); SList* newnode = BuyListNode(x); SList* next = pos->next; pos->next = newnode; newnode->next = next; }

11)任意位置之后删除元素：

说明：
原理与之前类似

void SListEraseAfter(SList* pos) { assert(pos); SList* del = pos->next; pos->next = del->next; free(del); del = NULL; }

三、双链表未完待续，我们下期再见！！！
总结——为什么一定要使用二级指针传参？

首先定义一个SList* 类型的指针指向单链表的第一个结点，通过这个指针的移动来对链表进行增删改查的操作，但是形参只是实参的临时拷贝，对形参进行操作引起的改变并不能影响实参，所以这里必须将指向第一个元素的指针的地址传递过去，通过指针的地址来操作指针，达到操作链表的目的。
那么有没有什么办法可以不使用双指针呢？当然有了，有两种方案，其一是函数使用return返回，其二就是我们刚才提到的哨兵卫结点，也就是带头结点。
可能有人回文为什么在上文当中的接口中，为什么有些接口的传参就没有使用双指针呢，比如”SListFind“接口，那是因为当链表的第一个结点需要或者可能改变的时候才需要传递地址，而元素的查找并不需要或者没有可能改变链表的第一个结点（链表的首地址）所以直接将指针本身传递过去就可以了，没有必要将指针的地址传递过去（这里涉及到值传递和址传递）。
所以哨兵卫的优势就体现在这，只要拥有一个哨兵卫结点，操作链表可以直接通过哨兵卫，也就是说链表的首地址无论如何不会发生变化，那么这个时候就不需要将指针的地址传过去，只需要将指向头结点的指针本身传过去即可。
如果想要理解址传递和值传递可以利用函数写一个两数交换的接口，比较两者之间的不同。

#includevoid Swap(int a,int b) { int tmp=a; a=b; b=tmp; }int main() { int a=3,b=10; Swap(a,b); printf("%d %d",a,b); }

请问上述的代码能否实现两数叫唤呢？
答案是否定的，因为我们刚才就一直在提，形参只是实参的临时拷贝，Swap函数中只是将两个形参交换，实参并没有发生改变，所以这个时候必须进行址传递，如下图所示。

#includevoid Swap(int* a,int *b) { int tmp=*a; *a=*b; *b=tmp; }int main() { int a=3; int b=10; Swap(&a,&b); printf("%d %d",a,b); }

【数据结构|【自此文之后，学习链表一片坦途】】此时只有通过两数的地址才能将两数真正的实现交换。

请问你学会了吗？