• 售前

  • 售后

热门帖子
入门百科

一篇解单链表(0基础看)(C语言)《数据结构与算法》

[复制链接]
如心所愿1 显示全部楼层 发表于 2022-1-12 12:32:47 |阅读模式 打印 上一主题 下一主题
目录
链表
1. 链表的概念及结构
2. 链表的分类
2.1. 单向或者双向
​2.2. 带头或者不带头
​2.3. 循环或者非循环 
2.4. 虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构
3. 效果展示图
4. 接口实现
4.01. 本文章要实现的接口
4.02. 链表的实现
​4.03. 初始化
​4.04. 销毁链表
4.05. 打印链表
4.06. 动态申请一个节点​
4.07. 头插
​4.08. 尾插
4.09. 头删
4.10. 尾删
4.11. 查找某个值并返回地址
​4.12. 在pos位置之前插入某个值
​4.13. 删除pos位置的值
5. 源代码
5.1. test.c
5.2. SList.h
5.3. SList.c

  谁都不能阻挡你成为更优秀的人。     
  链表

   1. 链表的概念及结构

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

2. 链表的分类

2.1. 单向或者双向

2.2. 带头或者不带头

2.3. 循环或者非循环 


2.4. 虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构



     1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。      2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。     3. 效果展示图


4. 接口实现

   本篇幅是无头+单向+非循环链表增删查改实现,下一篇就是带头+双向+循环链表的实现哈。
    对于接口的实现我们首先是要知道要实现什么,本文是对于链表的基本使用,让大家初步了解链表,所以就只实现顺序表的增删查改,还有特定位置前插入删除特定位置值等当然代码也不一定要作者这么写,这里只是提供一种思路,废话不多说,看代码。  
  有什么不懂的欢迎到评论区交流哈,当然也可以私信作者。
  
4.01. 本文章要实现的接口



4.02. 链表的实现

4.03. 初始化

4.04. 销毁链表


4.05. 打印链表


4.06. 动态申请一个节点

4.07. 头插

4.08. 尾插


4.09. 头删


4.10. 尾删


4.11. 查找某个值并返回地址

4.12. 在pos位置之前插入某个值

4.13. 删除pos位置的值


5. 源代码

5.1. test.c

  1. #include"SList.h"
  2. int main()
  3. {
  4.         //直接初始化next为NULL就可以了
  5.         SListNode* plist = NULL;
  6.         //头插 1 2
  7.         SListPushFront(&plist, 1);
  8.         SListPushFront(&plist, 2);
  9.         SListPushFront(&plist, 6);
  10.         SListPrint(&plist);
  11.         //尾插 3 4 5
  12.         SListPushBack(&plist, 3);
  13.         SListPushBack(&plist, 4);
  14.         SListPushBack(&plist, 5);
  15.         SListPrint(&plist);
  16.         //头删一个数
  17.         SListPopFront(&plist);
  18.         SListPrint(&plist);
  19.         //尾删两个个数
  20.         SListPopBack(&plist);
  21.         SListPopBack(&plist);
  22.         SListPrint(&plist);
  23.         //找 3 4 1
  24.         SListFind(&plist, 3);
  25.         SListFind(&plist, 4);
  26.         SListFind(&plist, 1);
  27.         //在 1 前面插入 8
  28.         SListNode* pos=SListFind(&plist, 1);
  29.         SListInsert(&plist, pos, 8);
  30.         SListPrint(&plist);
  31.         //删除 2  3
  32.         pos = SListFind(&plist, 2);
  33.         SListErase(&plist, pos);
  34.         SListPrint(&plist);
  35.         pos = SListFind(&plist, 3);
  36.         SListErase(&plist, pos);
  37.         SListPrint(&plist);
  38.         //销毁链表
  39.         SListDestory(&plist);
  40.         return 0;
  41. }
复制代码
5.2. SList.h

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3. #include<assert.h>
  4. #include<malloc.h>
  5. typedef int SLTDateType;
  6. typedef struct SListNode
  7. {
  8.         SLTDateType date;
  9.         struct SListNode* next;
  10. }SListNode;
  11. //销毁
  12. void SListDestory(SListNode** pphead);
  13. //打印
  14. void SListPrint(SListNode** pphead);
  15. //动态申请一个节点
  16. SListNode* BuySListNode(SLTDateType x);
  17. //查找某个值
  18. SListNode* SListFind(SListNode** pphead, SLTDateType x);
  19. //头插
  20. void SListPushBack(SListNode** pphead,SLTDateType x);
  21. //尾插
  22. void SListPushFront(SListNode** pphead, SLTDateType x);
  23. //头删
  24. void SListPopFront(SListNode** pphead);
  25. //尾删
  26. void SListPopBack(SListNode** pphead);
  27. //在pos位置之前插入某个值
  28. void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
  29. //删除pos位置的值
  30. void SListErase(SListNode** pphead,SListNode* pos);
  31. //找到某个值并改变为某个值
复制代码
5.3. SList.c

  1. #include"SList.h"
  2. //动态申请一个节点
  3. SListNode* BuySListNode(SLTDateType x)
  4. {
  5.         SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  6.         (newnode)->next = NULL;
  7.         newnode->date = x;
  8.         return newnode;
  9. }
  10. //头插
  11. void SListPushFront(SListNode** pphead, SLTDateType x)
  12. {
  13.         SListNode* newnode=BuySListNode(x);
  14.         if (!(*pphead))
  15.         {
  16.                 *pphead = newnode;
  17.         }
  18.         else
  19.         {
  20.                 newnode->next = *pphead;
  21.                 *pphead = newnode;
  22.         }
  23. }
  24. //打印
  25. void SListPrint(SListNode** pphead)
  26. {
  27.         SListNode* cur = *pphead;
  28.         while (cur)
  29.         {
  30.                 //注意这里打印的 -> 和下面的 NULL 只是为了打印出来更像是链表
  31.                 printf("%d->", cur->date);
  32.                 cur = cur->next;
  33.         }
  34.         printf("NULL\n");
  35. }
  36. //尾插
  37. void SListPushBack(SListNode** pphead, SLTDateType x)
  38. {
  39.         SListNode* tail = *pphead;
  40.         SListNode* newnode=BuySListNode(x);
  41.         if (!tail)
  42.         {
  43.                 tail = newnode;
  44.         }
  45.         else
  46.         {
  47.                 while (tail->next)
  48.                 {
  49.                         tail = tail->next;
  50.                 }
  51.                 tail->next = newnode;
  52.         }
  53. }
  54. //头删
  55. void SListPopFront(SListNode** pphead)
  56. {
  57.         assert(*pphead);
  58.        
  59.         SListNode* next = (*pphead)->next;
  60.         free(*pphead);
  61.         *pphead = next;
  62. }
  63. //尾删
  64. void SListPopBack(SListNode** pphead)
  65. {
  66.         assert(*pphead);
  67.         SListNode* tail = *pphead;
  68.         SListNode* prev = *pphead;
  69.         if (prev->next == NULL)  //一个节点的时候
  70.         {
  71.                 //注意这里free是*pphead
  72.                 free(*pphead);
  73.                 *pphead = NULL;
  74.                 return;
  75.         }
  76.         else
  77.         {
  78.                 //多个节点的时候(此时最少两个节点)
  79.                 tail = tail->next;
  80.                 while (tail->next)
  81.                 {
  82.                         tail = tail->next;
  83.                         prev = prev->next;
  84.                 }
  85.                 //这里只需要free最后面的一个空间
  86.                 free(tail);
  87.                 tail = NULL;
  88.                 prev->next = NULL;
  89.         }
  90. }
  91. //查找某个值
  92. SListNode* SListFind(SListNode** pphead, SLTDateType x)
  93. {
  94.         assert(*pphead);
  95.         SListNode* cur = *pphead;
  96.         while (cur != NULL)
  97.         {
  98.                 if (cur->date == x)
  99.                 {
  100.                         printf("找到啦!\n");
  101.                         return cur;
  102.                 }
  103.                 else
  104.                 {
  105.                         cur = cur->next;
  106.                 }
  107.         }
  108.         printf("没有找到此值\n");
  109.         return NULL;
  110. }
  111. //在pos位置之前插入某个值
  112. void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
  113. {
  114.         if (pos == *pphead)
  115.         {
  116.                 SListPushFront(pphead, x);
  117.         }
  118.         else
  119.         {
  120.                 SListNode* prev = *pphead;
  121.                 SListNode* newnode = BuySListNode(x);
  122.                 while (prev->next != pos)
  123.                 {
  124.                         prev = prev->next;
  125.                 }
  126.                 prev->next = newnode;
  127.                 newnode->next = pos;
  128.         }
  129. }
  130. //删除pos位置的值
  131. void SListErase(SListNode** pphead, SListNode* pos)
  132. {
  133.         assert(*pphead);
  134.         if (pos == *pphead)
  135.         {
  136.                 SListPopFront(pphead);
  137.         }
  138.         else
  139.         {
  140.                 SListNode* prev = *pphead;
  141.                 while (prev->next != pos)
  142.                 {
  143.                         prev = prev->next;
  144.                 }
  145.                 prev->next = pos->next;
  146.                 free(pos);
  147.                 pos = NULL;
  148.         }
  149. }
  150. //销毁
  151. void SListDestory(SListNode** pphead)
  152. {
  153.         assert(*pphead);
  154.         SListNode* pos = *pphead;
  155.         SListNode* cur = *pphead;
  156.         while (pos->next == NULL)
  157.         {
  158.                 if (cur->next != NULL)
  159.                 {
  160.                         cur = cur->next;
  161.                 }
  162.                 else
  163.                 {
  164.                         free(cur);
  165.                         cur = NULL;
  166.                         cur = *pphead;
  167.                 }
  168.         }
  169.         free(pos);
  170.         pos = NULL;
  171. }
复制代码

   今天的内容就到这里了哈!!!
  要是认为作者有一点帮助你的话!
  就来一个点赞加关注吧!!!当然订阅是更是求之不得!
  赠人玫瑰,手有余香=。=!
  最后的最后感谢大家的观看!!!
  你们的支持是作者写作的最大动力!!!
  下期见哈!!!
  





来源:https://blog.caogenba.net/weixin_62700590/article/details/122424778
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作