登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›单向循环链表的初始化、插入、删除、遍历 ...

单向循环链表的初始化、插入、删除、遍历

度阡舅 2025-6-30 17:37:25
  1. /**
  2. * @file name ： CircularLnList.c
  3. * @brief     :  实现一个单向循环链表的接口，可实现链表的增删改查，另外为了提高可移植性，所以链表中
  4. *               数据元素的类型为DataType_t，用户可以根据实际情况修改链表中元素的类型
  5. * @author    :  MINDSETT@163.com
  6. * @date      :  2025/6/27
  7. * @version   :  1.0
  8. * @note      :  特别说明：此接口实现的单向循环链表中尾结点的指针域指向头结点后面的首结点的地址，并不是头结点的地址
  9. * CopyRight (c)  2025  MINDSETT@163.com  All Right Reserved
  10. */
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14. #include <stdbool.h>
  15. //指定链表中元素的数据类型，用户可根据需要进行修改
  16. typedef int DataType_t;
  18. //构造链表的结点，链表中所有结点的数据类型应该是相同的（数据域+指针域）
  19. typedef struct CircularLinkedList
  20. {
  21.     DataType_t                  data;   //结点的数据域
  22.     struct CircularLinkedList *   next;   //结点的指针域
  23. }CircularLnList_t;
  26. /**
  27. * @name    :  CircularLnList_Create
  28. * @brief   :  创建一个空链表，空链表应该有一个头节点，对链表进行初始化
  29. * @param   :  None
  30. * @retval  :  返回头结点的地址
  31. * @date    :  2025/6/27
  32. * @version :  1.0
  33. * @note    :  None
  34. */
  35. CircularLnList_t *CircularLnList_Create(void)
  36. {
  37.     //创建一个头结点并对头结点申请内存
  38.     CircularLnList_t* Head=(CircularLnList_t*)calloc(1,sizeof(CircularLnList_t));
  39.     if (NULL==Head){
  40.         perror("calloc memory for Head is failed\n");
  41.         exit(-1);
  42.     }
  43.     //对头结点进行初始化,头结点不存储数据域，指针域指向自身，体现“循环”思想
  44.     Head->next=Head;
  45.     //将头结点的地址返回
  46.     return Head;
  47. }
  50. /**
  51. * @name    :  CircularLnList_NewNode
  52. * @brief   :  创建一个新结点，并为新结点申请堆内存以及对新结点的数据域和指针域进行初始化
  53. * @param   :  
  54. *             @data:新结点的数据
  55. * @retval  :  返回新结点的地址
  56. * @date    :  2025/6/27
  57. * @version :  1.0
  58. * @note    :  None
  59. */
  60. CircularLnList_t * CircularLnList_NewNode(DataType_t data)
  61. {
  62.     //创建新结点，并未新结点申请堆内存
  63.     CircularLnList_t * New=(CircularLnList_t*)calloc(1,sizeof(CircularLnList_t));
  64.      if (NULL==New){
  65.         perror("calloc memory for NewNode is failed\n");
  66.         return NULL;
  67.     }
  68.     //对新结点的数据域和指针域进行初始化
  69.     New->data=data;
  70.     New->next=NULL;
  71.     return New;
  72. }
  75. /**
  76. * @name    :  CircularLnList_FirstInsert
  77. * @brief   :  创建一个新结点,并把新结点插入链表的首部初始化
  78. * @param   :  
  79. *             @Head:插入的链表
  80. *             @data:新结点的数据
  81. * @retval  :  功返回true，失败返回false
  82. * @date    :  2025/6/27
  83. * @version :  1.0
  84. * @note    :  None
  85. */
  86. bool CircularLnList_FirstInsert(CircularLnList_t * Head,DataType_t data)
  87. {
  88.     //创建新结点，并对新结点进行初始化
  89.     CircularLnList_t* New=CircularLnList_NewNode(data);
  90.     if (NULL==New){
  91.         perror("Create New node is failed\n");
  92.         return false;
  93.     }
  94.     //判断链表是否为空，如果为空，则将新结点直接插入
  95.     if (Head==Head->next){
  96.         Head->next=New;
  97.         New->next=New;//指针域指向自身，体现“循环”思想
  98.         return true;
  99.     }
  100.     //备份首结点的地址
  101.     CircularLnList_t * tail=Head->next;
  102.     //找到尾结点
  103.     while( tail->next != Head->next ){
  104.         tail=tail->next;
  105.     }
  106.     tail->next=New;          //尾结点的指针域指向新首结点
  107.     //新结点插入首部   
  108.     New->next=Head->next;   //新结点的指针域指向旧首结点
  109.     Head->next=New;         //头结点的指针域指向新首结点
  111.     return true;
  112. }
  114. /**
  115. * @name    :  CircularLnList_TailInsert
  116. * @brief   :  创建一个新结点,并把新结点插入链表的尾部
  117. * @param   :  
  118. *             @Head:插入的链表
  119. *             @data:新结点的数据
  120. * @retval  :  成功返回true，失败返回false
  121. * @date    :  2025/6/27
  122. * @version :  1.0
  123. * @note    :  None
  124. */
  125. bool CircularLnList_TailInsert(CircularLnList_t * Head,DataType_t data)
  126. {
  127.     //创建新结点，并对新结点进行初始化
  128.     CircularLnList_t* New=CircularLnList_NewNode(data);
  129.     if (NULL==New){
  130.         perror("Create New node is failed\n");
  131.         return false;
  132.     }
  133.     //判断链表是否为空，如果为空，则将新结点直接插入
  134.     if (Head==Head->next){
  135.         Head->next=New;
  136.         New->next=New;//指针域指向自身，体现“循环”思想
  137.         return true;
  138.     }
  139.     //备份首结点的地址
  140.     CircularLnList_t * tail=Head->next;
  141.     //找到尾结点
  142.     while( tail->next != Head->next ){
  143.         tail=tail->next;
  144.     }
  145.     //新结点指向首结点，旧尾结点指向新结点
  146.     New->next=tail->next;
  147.     tail->next=New;
  149.     return true;
  150. }
  153. /**
  154. * @name    :  CircularLnList_DestInsert
  155. * @brief   :  创建一个新结点,并把新结点插入链表的指定位置
  156. * @param   :  
  157. *             @Head:插入的链表
  158. *             @Dest:指定需要新结点插入位置的直接前驱的数据
  159. *             @data:新结点的数据
  160. * @retval  :  成功返回true，失败返回false
  161. * @date    :  2025/6/27
  162. * @version :  1.0
  163. * @note    :  None
  164. */
  165. bool CircularLnList_DestInsert(CircularLnList_t * Head,DataType_t Dest,DataType_t data)
  166. {
  167.     //创建新结点，并对新结点进行初始化
  168.     CircularLnList_t* New=CircularLnList_NewNode(data);
  169.     if (NULL==New){
  170.         perror("Create New node is failed\n");
  171.         return false;
  172.     }
  173.     //判断链表是否为空，如果为空，则将新结点直接插入
  174.     if (Head==Head->next){
  175.         Head->next=New;
  176.         New->next=New;//指针域指向自身，体现“循环”思想
  177.         return true;
  178.     }
  179.     //备份首结点的地址
  180.     CircularLnList_t * curr=Head->next;
  181.     //如果链表为非空，遍历链表，目的是找到目标结点
  182.     do{
  183.         if(Dest==curr->data){
  184.             //找到目标结点
  185.             New->next=curr->next;
  186.             curr->next=New;
  187.             return true;
  188.         }
  189.         curr=curr->next;
  190.     }while( curr!=Head->next);
  191.     //未找到目标结点，错误输出
  192.     printf("Dest is not found\n");
  193.     free(New);
  194.         
  195.     return false;
  196. }
  199. /**
  200. * @name    :  CircularLnList_FirstDel
  201. * @brief   :  删除链表的首结点
  202. * @param   :  
  203. *             @Head:链表的头结点
  204. * @retval  :  成功返回true，失败返回false
  205. * @date    :  2025/6/27
  206. * @version :  1.0
  207. * @note    :  None
  208. */
  209. bool CircularLnList_FirstDel(CircularLnList_t* Head)
  210. {
  211.     //备份首结点
  212.     CircularLnList_t * first=Head->next;
  213.     CircularLnList_t * tail=Head->next;
  214.     //判断传参错误或链表为空
  215.     if (NULL==Head || Head==Head->next){
  216.         perror("Linked list is empty\n");
  217.         return false;
  218.     }
  219.     //1.只有一个首结点
  220.     if (Head->next->next==Head->next){
  221.         Head->next=Head;
  222.         first->next=NULL;//首结点的指针域指向NULL,从链表中断开(避免野指针)
  223.         free(first);
  224.         return true;
  225.     }
  226.     //2.链表有多个结点
  227.     //找到尾结点
  228.     while( tail->next!=Head->next ){
  230.         tail=tail->next;
  231.     }
  232.     //尾结点指向首结点的直接后驱
  233.     tail->next=first->next;
  234.     //将头结点指针域指向首结点的直接后驱
  235.     Head->next=first->next;
  236.     //旧的首结点的指针域指向NULL,从链表中断开(避免野指针)
  237.     first->next=NULL;
  238.     //释放首结点占用的内存
  239.     free(first);
  241.     return true;
  242. }
  245. /**
  246. * @name    :  CircularLnList_TailDel
  247. * @brief   :  删除链表的尾结点
  248. * @param   :  
  249. *             @Head:链表的头结点
  250. * @retval  :  成功返回true，失败返回false
  251. * @date    :  2025/6/27
  252. * @version :  1.0
  253. * @note    :  None
  254. */
  255. bool CircularLnList_TailDel(CircularLnList_t* Head)
  256. {
  257.     //备份头结点和首结点
  258.     CircularLnList_t * prev=Head;
  259.     CircularLnList_t * tail=Head->next;
  260.     //判断传参错误或链表为空
  261.     if (NULL==Head || Head==Head->next){
  262.         perror("Linked list is empty\n");
  263.         return false;
  264.     }
  265.     //1.只有一个首结点
  266.     if (Head->next->next==Head->next){
  267.         Head->next=Head;
  268.         tail->next=NULL;//首结点的指针域指向NULL,从链表中断开(避免野指针)
  269.         free(tail);
  270.         return true;
  271.     }
  272.     //2.链表有多个结点
  273.     //找到尾结点和它的直接前驱
  274.     while( tail->next!=Head->next ){
  275.         prev=tail;
  276.         tail=tail->next;
  277.     }
  278.     //尾结点的直接前驱指向首结点
  279.     prev->next=tail->next;
  280.     //旧的尾结点的指针域指向NULL,从链表中断开(避免野指针)
  281.     tail->next=NULL;
  282.     free(tail);
  284.     return true;
  285. }
  288. /**
  289. * @name    :  CircularLnList_DestDel
  290. * @brief   :  删除链表的指定结点
  291. * @param   :  
  292. *             @Head:链表的头结点
  293. *             @Dest:需要删除的指定结点
  294. * @retval  :  功返回true，失败返回false
  295. * @date    :  2025/6/27
  296. * @version :  1.0
  297. * @note    :  None
  298. */
  299. bool CircularLnList_DestDel(CircularLnList_t* Head,DataType_t Dest)
  300. {
  301.     //备份头结点和首结点
  302.     CircularLnList_t * prev=Head;
  303.     CircularLnList_t * curr=Head->next;
  304.     //判断传参错误或链表为空
  305.     if (NULL==Head || Head==Head->next){
  306.         perror("Linked list is empty\n");
  307.         return false;
  308.     }
  309.     //1.只有一个首结点
  310.     if (Head->next->next==Head->next){
  311.         Head->next=Head;
  312.         curr->next=NULL;//首结点的指针域指向NULL,从链表中断开(避免野指针)
  313.         free(curr);
  314.         return true;
  315.     }
  316.     //2.链表有多个结点
  317.     //遍历链表，目的是找到目标结点和它的直接前驱
  318.     do{
  319.         if(Dest==curr->data){
  320.             //找到目标结点
  321.             prev->next=curr->next;
  322.             curr->next=NULL;//尾结点的指针域指向NULL,从链表中断开(避免野指针)
  323.             free(curr);
  324.             return true;
  325.         }
  326.         prev=curr;
  327.         curr=curr->next;
  328.     }while( curr!=Head->next);
  329.     //未找到目标结点，错误输出
  330.     printf("Dest is not found\n");
  332.     return false;
  333. }
  336. /**
  337. * @name    :  CircularLnList_Print
  338. * @brief   :  遍历输出链表中各个结点的数据
  339. * @param   :  
  340. *             @Head:需要遍历的链表
  341. * @retval  :  成功返回true，失败返回false
  342. * @date    :  2025/6/27
  343. * @version :  1.0
  344. * @note    :  None
  345. */
  346. bool CircularLnList_Print(CircularLnList_t* Head)
  347. {
  348.     //判断传参错误或链表为空
  349.     if (NULL==Head || Head==Head->next){
  350.         perror("Current CircularLinkedList is empty\n");
  351.         return false;
  352.     }
  353.     //对链表的头节点的地址进行备份
  354.     CircularLnList_t *curr=Head;
  355.     //循环遍历链表
  356.     while(curr->next){
  357.         curr=curr->next;
  358.         printf("Data=%d ",curr->data);
  359.         if( curr->next == Head->next){
  360.             break;
  361.         }
  362.     }
  364.     return true;
  365. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
度阡舅
2025-6-30 17:37:25

0

粉丝关注

14

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫