一，链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
而在数据结构中：
注意：
1，从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2，现实中的结点一般都是从堆上申请出来的
3，从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续；
实际中链表的结构非常多样，今天我们来写一下单链表，此表一会其他的自然水到渠成！
二，接口实现
1，单链表的创建
//无头 + 单向 + 非循环链表增删查改实现 typedef int LKLDataType; typedef struct LinKedListNode { LKLDataType data; struct LinKedListNode* next; }LKLNode;
首先创建一个结构体表示单链表，data是存储的值，LKLDataType是储存的值的数据类型，next是结点----指向下一个；
这里的LKLDataType是int的重命名，也可以说是数据类型的重命名，这样统一化方便后续更改；
2，接口函数
// 动态创立新结点 LKLNode* BuyLKLNode(LKLDataType x); // 打印 void LKLPrint(LKLNode* phead); // 头插 void LKLNodePushFront(LKLNode** phead, LKLDataType x); // 头删 void LKLNodeBackFront(LKLNode** phead); // 尾插 void LKLNodePushBack(LKLNode** phead, LKLDataType x); // 尾删 void LKLNodePopBack(LKLNode** phead); // 查找 LKLNode* LKLFind(LKLNode* phead, LKLDataType x); // 单链表在pos位置之后插入x void LKLInsertAfter(LKLNode* pos, LKLDataType x); // 单链表删除pos位置之后的值 void LKLEraseAfter(LKLNode* pos); // 销毁 void LKLDestroy(LKLNode** plist);
这是以上要实现的接口函数；
3，动态创立新结点
//动态创立新结点 LKLNode* BuyLKLNode(LKLDataType x) { LKLNode* newnode = (LKLNode*)malloc(sizeof(LKLNode)); newnode->data = x; newnode->next = NULL; return newnode; }
后面创立新节点时直接调用此函数，一定要向堆区申请空间，这样函数结束空间会保留不会被回收；
4，打印
//打印 void LKLPrint(LKLNode* phead) { assert(phead); LKLNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL"); }
打印也就是打印data的值，用cur=phead然后每次打印完都让cur走向下一个直到为空结束；
5，头插
//头插 void LKLNodePushFront(LKLNode** phead, LKLDataType x) { assert(phead); LKLNode* newnode = BuyLKLNode(x); newnode->next = *phead; *phead = newnode; }
先断言一下，既然插入数据那就要申请一个新节点，然后令新节点的next指向phead然后再令phead指向新节点；
6，头删
//头删 void LKLNodeBackFront(LKLNode** phead) { assert(phead); //为空 assert(*phead); //非空 LKLNode* newnode = (*phead)->next; free(*phead); *phead = newnode; }
还是先断言，有人会问为什么要断言两次？其实很好判断，哪个需要解引用那个就需要断言；
令一个变量newnode等于头结点的下一个，在释放头结点，在令头结点指向newnode即可；
7，尾插
//尾插 void LKLNodePushBack(LKLNode** phead, LKLDataType x) { assert(phead); assert(*phead); LKLNode* newnode= BuyLKLNode(x); LKLNode* cur = *phead; //为空 if (*phead == NULL) { *phead = newnode; } //非空 else { while (cur->next) { cur = cur->next; } cur->next = newnode; } }
还是先断言判断，然后要插入一个新的数据先申请一个新结点，如果头结点为空则直接让头结点指向新结点即可，如果头结点不为空，则需要找到next为空的结点，这里用一个循环搞定，然后再直接让next为空的结点指向新节点即可；
8，尾删
//尾删 void LKLNodePopBack(LKLNode** phead) { assert(phead); //为空 assert(*phead); //一个 if ((*phead)->next==NULL) { free(*phead); *phead = NULL; } //两个及以上 else { LKLNode* tail = *phead; /*LKLNode* prev = NULL; while (tail->next) { prev = tail; tail = tail->next; } free(prev->next); prev->next = NULL;*/ while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
还是先断言一下，然后这里有两种情况，链表只有一个结点，两个以上结点的时候；
当链表只有一个结点也就是头结点，直接头删即可；
两个以上结点的时候，我这里有两种解决方案；
方案一常规法：先用循环找到next为空的结点，并且在循环里保留上一个结点prev，然后释放next为空的结点再让prev的next指向空即可；
方案二：不需要标记上一个结点，直接原地判断，判断结点的next的next是否为空，否则继续向后推进，是则释放结点的next然后再令自己的next指向空也就相当于变成了尾结点；
9，查找
// 单链表查找 LKLNode* LKLFind(LKLNode* phead, LKLDataType x) { assert(phead); LKLNode* pos = phead; while (pos) { if (pos->data == x) { return pos; } pos = pos->next; } return NULL; }
老样子先断言一下，然后直接用循环遍历链表找到data是x的值然后返回此结点即可；
10，单链表在pos位置之后插入x
// 单链表在pos位置之后插入x void LKLInsertAfter(LKLNode* pos, LKLDataType x) { assert(pos); LKLNode* newnode= BuyLKLNode(x); LKLNode* cur = pos; newnode->next = cur->next; cur->next = newnode; }
先断言，要插入数据先申请一个新结点，然后令新结点的next指向pos的next，再返回来让pos的next指向新结点；
11，单链表删除pos位置之后的值
// 单链表删除pos位置之后的值 void LKLEraseAfter(LKLNode* pos) { assert(pos); assert(pos->next); LKLNode* cur = pos; LKLNode* newnode = cur->next->next; free(cur->next); cur->next = newnode; }
要删除值首先要确保得有值，所以开始断言；
先定义一个变量newnode指向pos的next的next，然后再释放pos的next，再令pos指向newnode以达到删除之后的效果；
12，销毁
// 单链表的销毁 void LKLDestroy(LKLNode** phead) { assert(phead); assert(*phead); LKLNode* cur = *phead; LKLNode* next = NULL; while (cur) { next = cur->next; free(cur); cur = next; } }
老样子那个需要解引用那个就先断言一下，然后用循环遍历，先标记下一个结点，然后释放自己，再让自己指向标记的结点直到为空结束；
三，源代码
LKList.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //无头 + 单向 + 非循环链表增删查改实现 typedef int LKLDataType; typedef struct LinKedListNode { LKLDataType data; struct LinKedListNode* next; }LKLNode; // 动态创立新结点 LKLNode* BuyLKLNode(LKLDataType x); // 打印 void LKLPrint(LKLNode* phead); // 头插 void LKLNodePushFront(LKLNode** phead, LKLDataType x); // 头删 void LKLNodeBackFront(LKLNode** phead); // 尾插 void LKLNodePushBack(LKLNode** phead, LKLDataType x); // 尾删 void LKLNodePopBack(LKLNode** phead); // 查找 LKLNode* LKLFind(LKLNode* phead, LKLDataType x); // 单链表在pos位置之后插入x void LKLInsertAfter(LKLNode* pos, LKLDataType x); // 单链表删除pos位置之后的值 void LKLEraseAfter(LKLNode* pos); // 销毁 void LKLDestroy(LKLNode** plist);
LKList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"LKList.h" //动态创立新结点 LKLNode* BuyLKLNode(LKLDataType x) { LKLNode* newnode = (LKLNode*)malloc(sizeof(LKLNode)); newnode->data = x; newnode->next = NULL; return newnode; } //头插 void LKLNodePushFront(LKLNode** phead, LKLDataType x) { assert(phead); LKLNode* newnode = BuyLKLNode(x); newnode->next = *phead; *phead = newnode; } //头删 void LKLNodeBackFront(LKLNode** phead) { assert(phead); //为空 assert(*phead); //非空 LKLNode* newnode = (*phead)->next; free(*phead); *phead = newnode; } //尾插 void LKLNodePushBack(LKLNode** phead, LKLDataType x) { assert(phead); assert(*phead); LKLNode* newnode= BuyLKLNode(x); LKLNode* cur = *phead; //为空 if (*phead == NULL) { *phead = newnode; } //非空 else { while (cur->next) { cur = cur->next; } cur->next = newnode; } } //尾删 void LKLNodePopBack(LKLNode** phead) { assert(phead); //为空 assert(*phead); //一个 if ((*phead)->next==NULL) { free(*phead); *phead = NULL; } //两个及以上 else { LKLNode* tail = *phead; /*LKLNode* prev = NULL; while (tail->next) { prev = tail; tail = tail->next; } free(prev->next); prev->next = NULL;*/ while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } } // 单链表查找 LKLNode* LKLFind(LKLNode* phead, LKLDataType x) { assert(phead); LKLNode* pos = phead; while (pos) { if (pos->data == x) { return pos; } pos = pos->next; } return NULL; } // 单链表在pos位置之后插入x void LKLInsertAfter(LKLNode* pos, LKLDataType x) { assert(pos); LKLNode* newnode= BuyLKLNode(x); LKLNode* cur = pos; newnode->next = cur->next; cur->next = newnode; } // 单链表删除pos位置之后的值 void LKLEraseAfter(LKLNode* pos) { assert(pos); assert(pos->next); LKLNode* cur = pos; LKLNode* newnode = cur->next->next; free(cur->next); cur->next = newnode; } // 单链表的销毁 void LKLDestroy(LKLNode** phead) { assert(phead); assert(*phead); LKLNode* cur = *phead; LKLNode* next = NULL; while (cur) { next = cur->next; free(cur); cur = next; } } //打印 void LKLPrint(LKLNode* phead) { assert(phead); LKLNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL"); }
四，总结
做数据结构的题目画图很重要，小伙伴们刚开始喜欢用脑子去构图想象，但遇到复杂的情况会紊乱的，画图最为可观方便，可以培养一个良好的画图习惯；
如有不足之处欢迎来补充交流！
完结。。。
