【数据结构】单链表的实现
温馨提示：这篇文章已超过397天没有更新，请注意相关的内容是否还可用！
🌇个人主页：平凡的小苏
📚学习格言：别人可以拷贝我的模式，但不能拷贝我不断往前的激情
🛸C语言专栏：https://blog.csdn.net/vhhhbb/category_12174730.html
🚀数据结构专栏：https://blog.csdn.net/vhhhbb/category_12211053.html
家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路过的友友麻烦多多点赞关注，欢迎你们的私信提问，感谢你们的转发！
关注我，关注我，关注我，你们将会看到更多的优质内容！！
目录
1、单链表存储结构定义
2、单链表的优缺点
3、单链表的实现
3.1、线性单链表的存储结构
3.2、单链表的插入
3.3、单链表的删除
3.4、单链表打印
3.5、单链表查找
3.6、单链表的销毁
4、源码
4.1、SList.h
4.2、SList.c
4.3、Test.c
1、单链表存储结构定义
- 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。
- 以前在顺序结构中，每个数据元素只需要存储数据元素信息就可以了。现在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。
- 因此，为了表示每个数据元素ai与其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点。
- n个结点（ai的存储映像）链结成一个链表，即为线性表（a1,a2,......,an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
2、单链表的优缺点
简单的对单链表结构和顺序存储结构做对比：
存储分配方式：
1.顺序存储结构用一段连续存储单元依次为存储线性表的数据元素
2.单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能：
1.查找：顺序存储结构O(1)
单链表O(n)
2.插入和删除：
顺序存储结构需要平均移动表长一半的元素，时间复杂度为O(n)
单链表在找出位置的指针后，插入和删除时间复杂度仅为O(1)]
空间性能：
1.顺序存储结构需要预分配存储空间，分小了，易发生上溢，分大了，浪费
2.单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
结论：
1.若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
2.当线性表中的元素个数变化较大或者根本不知道有多大时，最好使用单链表。
3、单链表的实现
3.1、线性单链表的存储结构
#include #include #include typedef int SLTDateType; typedef struct SListNode { SLTDateType data;//数据域 struct SListNode* next;//指针域 }SListNode;3.2、单链表的插入
SListNode* BuySListNode(SLTDateType x)//申请结点函数 { SListNode* new = (SListNode*)malloc(sizeof(SListNode)); if (new == NULL) { perror("malloc fail:"); exit(-1); } new->data = x; new->next = NULL; return new; } void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x) { assert(pplist); assert(pos); SListNode* new = BuySListNode(x); SListNode* prev = *pplist; if (*pplist == pos)//pos处于单链表的头就是头插 { new->next = *pplist; *pplist = new; } else { while (prev->next != pos)//处于pos的前面插入一个数 { prev = prev->next; } new->next = pos; prev->next = new; } }算法思路：
(1)声明——指针pplist指向链表头；
(2)当prev->next不等于pos时，让p的指针向后移动，不断指向下一结点；
(3)pos不等于空就代表这个结点存在，若不存在就断言；
(4)单链表插入的标准语句new-> = pos; prev->next = new;
注：
在这段算法代码中，我们用到了c语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放数据。
3.3、单链表的删除
现在我们来看看单链表的删除，设存储元素data的结点为pos，要实现将结点pos删除单链表的操作，其实就是将他的前继结点的指针绕过，指向它的后继结点即可。
实现代码如下：
void SListErase(SListNode** pplist, SListNode* pos) { assert(pplist); assert(*pplist); assert(pos); SListNode* prev = *pplist; SListNode* cur = *pplist; while (cur) { if (cur == pos) { if (*pplist == pos)//如果pos处于链表头那就代表是头删 { *pplist = cur->next; free(cur); cur = *pplist; } else//将它的前继结点指向的指针绕过，指向它的后继结点 { prev->next = cur->next; free(cur); cur = prev->next; } } else { prev = cur; cur = cur->next; } } }算法思路：
(1)声明——指针pplist指向链表头；
(2)当cur不等于pos时，就往后遍历链表，让cur的指针向后移动，不断指向下一个结点
(3)若pos等于空，就代表这个链表不存在；
(4)单链表删除的标准语句 prev->next = cur->next; free(cur); cur = prev->next;
注;
这一段算法代码里，我们又用到了另一个C语言的标准函数free。它的作用就是让系统回收一个Node结点，释放内存。
3.4、单链表打印
void SListPrint(SListNode* plist) { SListNode* cur = plist; while (cur)//遍历到空就停止 { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }3.5、单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }3.6、单链表的销毁
void SListDestroy(SListNode** pplist) { free(*pplist); *pplist = NULL; }4、源码
注：由于头插、头删、尾插、尾删和任意位置的插入和删除是差不多，这里直接放源码
4.1、SList.h
#include #include #include 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 // 分析思考为什么不在pos位置之前插入？ void SListInsert(SListNode ** pplist,SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 // 分析思考为什么不删除pos位置？ void SListErase(SListNode ** pplist,SListNode* pos); // 单链表的销毁 void SListDestroy(SListNode**pplist);4.2、SList.c
#include"SList.h" SListNode* BuySListNode(SLTDateType x) { SListNode* new = (SListNode*)malloc(sizeof(SListNode)); if (new == NULL) { perror("malloc fail:"); exit(-1); } new->data = x; new->next = NULL; return new; } void SListPushBack(SListNode** pplist, SLTDateType x) { assert(pplist); SListNode* new = BuySListNode(x); SListNode* tail = *pplist; if (*pplist == NULL) { *pplist = new; } else { while (tail->next != NULL) { tail = tail->next; } tail->next = new; } } void SListPrint(SListNode* plist) { SListNode* cur = plist; while (cur) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } void SListPushFront(SListNode** pplist, SLTDateType x) { assert(pplist); SListNode* new = BuySListNode(x); new->next = *pplist; *pplist = new; } void SListPopBack(SListNode** pplist) { assert(pplist); assert(*pplist); SListNode* prev = NULL; SListNode* tail = *pplist; if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { while (tail->next) { prev = tail; tail = tail->next; } prev->next = NULL; free(tail); tail = NULL; } } void SListPopFront(SListNode** pplist) { assert(pplist); assert(*pplist); SListNode* cur = (*pplist)->next; free(*pplist); *pplist = cur; } SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x) { assert(pplist); assert(pos); SListNode* new = BuySListNode(x); SListNode* prev = *pplist; if (*pplist == pos) { new->next = *pplist; *pplist = new; } else { while (prev->next != pos) { prev = prev->next; } new->next = pos; prev->next = new; } } void SListErase(SListNode** pplist, SListNode* pos) { assert(pplist); assert(*pplist); assert(pos); SListNode* prev = *pplist; SListNode* cur = *pplist; while (cur) { if (cur == pos) { if (*pplist == pos)//如果pos处于链表头那就代表是头删 { *pplist = cur->next; free(cur); cur = *pplist; } else//将它的前继结点指向的指针绕过，指向它的后继结点 { prev->next = cur->next; free(cur); cur = prev->next; } } else { prev = cur; cur = cur->next; } } } void SListDestroy(SListNode** pplist) { free(*pplist); *pplist = NULL; }4.3、Test.c
#include"SList.h" void TestSListNode() { SListNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListNode* pos = SListFind(plist, 3); SListErase(&plist,pos); SListPrint(plist); } int main() { TestSListNode(); return 0; }好了！我的分享到这里就结束了，有什么不足的地方请各位大佬多多指教！！！
