devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

单链表增序排列节点(单链表算法库拓展v2.0)

作者：知新_RL | 2024-03-30 16:59:19

赞

踩

单链表增序排列节点(单链表算法库拓展v2.0)

对单链表中元素进行排序(至少有2个数据节点)

  1. /**************************************************
  2. (13)函数名:LinkList_sorting
  3. 功  能:对单链表中元素进行排序(至少有2个数据节点)
  4. 参  数:LinkList *&L:要进行排序的单链表
  5. 注意: ① 空表,或者只有一个数据节点,则不需要排序,返回false
  6.       ② 开始节点必须是头结点,因为我们会用到start_compare->next,
  7.       ③ 把数据节点(第二个数据节点及以后)和原始链表(头结点+一个数据节点)
  8.       ④ 在有序表中,一直找到比前一个节点大,比后一个节点小的空挡,
  9.          所以时刻对比start_compare->next->data, 并且start_compare->next不能为空
  10.          (为空代表到达末尾,交替空指针)
  11.         ⑤ 顺序不能变, 避免丢失有序表后续信息(指针覆盖的一句话)
  12. 详细链接:https://blog.csdn.net/qq_57484399/article/details/127141307
  13. 返回值:bool: 是否符合排序标准,并排序成功  ? true: false
  14. **************************************************/
  15. bool LinkList_sorting(LinkList *&L)
  16. {
  17.     LinkList *compare,*start_compare,*Remaining_node;
  18.     if(L->next == NULL || L->next->next == NULL)//①保证至少有2个数据节点
  19.     {
  20.         return false;
  21.     }
  22.     compare = L->next->next;
  23.     start_compare = L;  //②开始节点必须是头结点
  24.     Remaining_node = compare->next;
  25.     L->next->next = NULL; //③把数据节点(第二个数据节点及以后)和原始链表(头结点+一个数据节点)
  26.  
  27.     while(compare != NULL)
  28.     {
  29.         Remaining_node = compare->next;
  30.         start_compare = L;
  31.         while((start_compare->next != NULL) && (compare->data > start_compare->next->data))
  32.         {
  33.             start_compare = start_compare->next;
  34.         } //④
  35.  
  36.         compare->next = start_compare->next;
  37.         start_compare->next = compare;     //⑤
  38.         compare = Remaining_node;
  39.     }
  40.     return true;
  41.  
  42. }

单链表完整函数库:

singlelist.cpp

  1. #include "singlelist.h"
  2.  
  3. /**************************************************
  4. ①函数名: CreatList_Head
  5. 功  能: 头插法建立单链表
  6. 参  数: (1)LinkList *&L: 传入的单链表指针地址
  7.         (2)ElemType Array_used[]:要用来建表的数组
  8.         (3)int Array_number: 数组的长度
  9. 返回值:    无
  10. **************************************************/
  11. void CreatList_Head(LinkList *&L, ElemType Array_used[], int Array_number)
  12. {
  13.     int counter;
  14.     LinkList *newnode;
  15.     L = (LinkList *)malloc(sizeof(LinkList)); //创建头结点
  16.     L->next = NULL;
  17.     for(counter = 0; counter < Array_number; counter++)
  18.     {
  19.         newnode = (LinkList *)malloc(sizeof(LinkList));  //创建新节点
  20.         newnode->data = Array_used[counter];
  21.         newnode->next = L->next;         //将newnode插在原开始结点之前,头结点之后
  22.         L->next = newnode;
  23.     }
  24. }
  25. /**************************************************
  26. ②函数名: CreatList_Tail
  27. 功  能: 尾插法建立单链表
  28. 参  数: (1)LinkList *&L: 传入的单链表指针地址
  29.         (2)ElemType Array_used[]:要用来建表的数组
  30.         (3)int Array_number:数组的长度
  31. 返回值:   无
  32. **************************************************/
  33. void CreatList_Tail(LinkList *&L, ElemType Array_used[], int Array_number)
  34. {
  35.     int counter;
  36.     LinkList *newnode,*tailnode;
  37.     L = (LinkList *)malloc(sizeof(LinkList));//创建头结点
  38.     L->next = NULL;
  39.     tailnode = L;       //尾结点tailnode始终指向终端结点,开始指向头结点
  40.     for(counter = 0; counter < Array_number; counter++)
  41.     {
  42.         newnode = (LinkList *)malloc(sizeof(LinkList)); //创建新节点
  43.         newnode->data = Array_used[counter];
  44.         tailnode->next = newnode;   //将新节点插入到尾结点之后
  45.         tailnode = newnode;         //更新尾结点
  46.     }
  47.     tailnode->next = NULL;          //终端结点next域置空
  48. }
  49.  
  50. /**************************************************
  51. ③函数名: DisplayLinkList
  52. 功  能: 输出单链表
  53. 参  数: (1)LinkList *L:将要输出的单链表
  54. 返回值: 无
  55. **************************************************/
  56.  
  57. void DisplayLinkList(LinkList *L)
  58. {
  59.     LinkList *shownode;
  60.     shownode = L->next;
  61.     while(shownode != NULL)
  62.     {
  63.         printf("%d",shownode->data);
  64.         shownode = shownode->next;        //一直遍历,直到指向尾->newt = NULL
  65.     }
  66.     printf("\n");
  67. }
  68. /**************************************************
  69. ④函数名: DestroyLinkList
  70. 功  能: 销毁单链表
  71. 参  数: (1)LinkList *&L:要销毁的单链表
  72. 注意:① 等到指引下一个节点的指针为Null时就跳出,避免出现野指针,此时再销毁destroyNode
  73.     ② 避免断开联系,记录 销毁节点的下一个节点
  74. 返回值: 无
  75. **************************************************/
  76. void DestroyLinkList(LinkList *&L)
  77. {
  78.     LinkList *destoryNode,*nextNode;
  79.     destoryNode = L;
  80.     nextNode = destoryNode->next;
  81.     while(nextNode != NULL)        //①
  82.     {
  83.         free(destoryNode);
  84.         destoryNode = nextNode;
  85.         nextNode = destoryNode->next;   //②
  86.     }
  87.     free(destoryNode);
  88.  
  89. }
  90. /**************************************************
  91. ⑤函数名: InitLinkList
  92. 功  能: 初始化单链表
  93. 参  数: LinkList *&L:要被初始化的链表指针地址
  94. 返回值: 无
  95. **************************************************/
  96. void InitLinkList(LinkList *&L)
  97. {
  98.     L = (LinkList *)malloc(sizeof(LinkList));//创建头结点
  99.     L->next = NULL;
  100. }
  101. /**************************************************
  102. ⑥函数名: LinkListEmpty
  103. 功  能: 判断单链表是否为空
  104. 参  数: (1)LinkList *L:要判断的单链表
  105. 返回值: bool: 是否为空? treu:false
  106. **************************************************/
  107. bool LinkListEmpty(LinkList *L)
  108. {
  109.     return (L->next == NULL);
  110. }
  111.  
  112. /**************************************************
  113. ⑦函数名: LinkListLength
  114. 功  能: 返回单链表L中数据节点的个数
  115. 参  数: LinkList *L:要计算的数据节点
  116. 返回值: int: 线性表数据节点个数值
  117. **************************************************/
  118. int LinkListLength(LinkList *L)
  119. {
  120.     int counter = 0;
  121.     LinkList *nowNode = L;
  122.     while(nowNode->next != NULL)
  123.     {
  124.         counter++;
  125.         nowNode = nowNode->next;
  126.     }
  127.     return counter;
  128. }
  129.  
  130. /**************************************************
  131. ⑧函数名: GetLocateValue
  132. 功  能: 求特定位置的数据元素值
  133. 参  数: (1)LinkList *L:要找的单链表
  134.         (2)int location:所要找的位置
  135.         (3)ElemType &value: 传递回所要找的值
  136. 注意: ① 判断跳出的时候, 是查找成功, 还是抵达末尾
  137.      ② counter == 要找到序号,则跳出,所以counter < location  ,
  138.     nowNode指向的节点为空,则到末尾,则跳出
  139.     ③④ 这两条语句, 所指向的序号和节点, 是同步的, 位置到或者此节点为空,则跳出
  140. 返回值: bool: 是否查找成功? true:false
  141. **************************************************/
  142. bool SpecificLocate_Value(LinkList *L,int location, ElemType &value)
  143. {
  144.     int counter = 0;
  145.     LinkList *nowNode = L;
  146.     while(counter < location && nowNode != NULL)//②
  147.     {
  148.         counter++;          //③  当前计数的节点
  149.         nowNode = nowNode->next;//④当前遍历到的节点
  150.     }
  151.     if(nowNode == NULL)                //①
  152.     {
  153.         return false;
  154.     }
  155.     else
  156.     {
  157.         value = nowNode->data;
  158.         return true;
  159.     }
  160.  
  161. }
  162.  
  163. /**************************************************
  164. ⑨函数名:SpecificValue_Location
  165. 功  能: 查找特定数据值的节点,并返回其位置
  166. 参  数: (1)LinkList *L: 被查找的单链表(2)ElemType e:
  167. 注  意:  ①从头结点后的第一个节点开始找
  168.          ②while循环内的两条语句是同步指向的
  169.          ③当nowNode为空时(到达末尾仍未找到), counter作废
  170.          ④当nowNode不为空时,跳出时, counter表示所指向节点存在,并符合所需
  171. 返回值:
  172. **************************************************/
  173. int SpecificValue_Location(LinkList *L, ElemType value)
  174. {
  175.     int counter = 1;
  176.     LinkList *nowNode = L->next;    //①
  177.     while(nowNode != NULL && nowNode->data != value)
  178.     {
  179.         nowNode = nowNode->next;
  180.         counter++;                     //②
  181.     }
  182.     if(nowNode == NULL)           //③
  183.     {
  184.         return 0;
  185.     }
  186.     else                    //④
  187.     {
  188.         return counter;
  189.     }
  190.  
  191. }
  192. /**************************************************
  193. ⑩函数名: LinkList_InsertElement
  194. 功  能: 在单链表特定位置插入节点
  195. 参  数: (1)LinkList *&L:要插入的单链表
  196.         (2)int location:要插入的位置
  197.         (3) ElemType &value:插入的数据
  198. 思路:    先在单链表L中,找到第 i-1个节点(不算头结点),若存在这样的节点,
  199.         将值为value的节点 插入到其后面
  200. 注意:    ① 计数器和 nowNode是同步往后移动(从L->next开始算第一个节点),
  201.          直到 找到counter = location-1,
  202.          ②此时 nowNode不为空,则此时nowNode指向
  203.          要插入位置的 前一个节点
  204.          ③ 覆盖指针前, 牢记 nowNode->next里面存放的是后继节点信息,所以要先处理
  205.           newNode->next = nowNode->next;
  206.           然后我们才能再把 nowNode->next指向新节点 newNode
  207. 返回值: bool: 是否存在第i-1个节点,并插入成功? true : false
  208. **************************************************/
  209. bool LinkList_InsertElement(LinkList *&L, int location, ElemType &value)
  210. {
  211.         int counter = 0;
  212.         LinkList *nowNode = L;
  213.         LinkList *newNode;
  214.         while((counter < (location-1)) && (nowNode != NULL)) //①
  215.         {
  216.             counter++;
  217.             nowNode = nowNode->next;
  218.         }
  219.         if(nowNode == NULL)//②
  220.         {
  221.             return false;
  222.         }
  223.         else
  224.         {
  225.             newNode = (LinkList *)malloc(sizeof(LinkList));
  226.             newNode->data = value;
  227.             newNode->next = nowNode->next;//③
  228.             nowNode->next = newNode;
  229.             return true;
  230.         }
  231. }
  232. /**************************************************
  233. (11)函数名: LinkList_Delete_Location
  234. 功  能: 删除特定位置的节点元素
  235. 参  数: (1)LinkList *&L:被删除的单链表 (2)int location:特定位置
  236.         (3) ElemType &value:被删除的元素值
  237. 思路:    找到第location-1个元素, 存储第locataion个元素值(判断null),然后free
  238.         链接 location-1 和 location+1
  239. 注意:    ① counter和指针节点是同步的,要么找到location-1个节点,要么到末尾
  240.         ② 虽然可能找到location-1个元素,其可能是最后一个元素,从而导致删除失败
  241.         需要判断一下,deleteNode是否为空,才能得出是否任务成功
  242.         ③ 指针覆盖还是老生常谈,先存储一下deleteNode(方便free),
  243.            然后指针交替,然后free
  244. 返回值:  bool: 是否删除成功? true:false
  245. **************************************************/
  246. bool LinkList_Delete_Location(LinkList *&L,int location, ElemType &value)
  247. {
  248.     int counter = 0;
  249.     LinkList *nowNode = L;
  250.     LinkList *deleteNode;
  251.     while(counter < (location-1) && nowNode != NULL)   //①
  252.     {
  253.         counter++;
  254.         nowNode = nowNode->next;
  255.     }
  256.     if(nowNode == NULL)
  257.     {
  258.         return false;
  259.     }
  260.     else
  261.     {
  262.         deleteNode = nowNode->next;
  263.         if(deleteNode == NULL)    //②
  264.         {
  265.             return false;
  266.         }
  267.         value = deleteNode->data;
  268.         nowNode->next = deleteNode->next;  //③
  269.         free(deleteNode);
  270.         return true;
  271.     }
  272. }
  273.  
  274. /**************************************************
  275. (12)函数名: DeleteMaxNode
  276. 功  能: 删除单链表中最大的一个节点
  277. 参  数: (1)LinkList *&L:要删除节点的单链表
  278. 思路: 四个指针, 最大指针,最大指针前一个节点
  279.     目前遍历的指针,遍历指针的前一个节点, 边比较,边替换,边遍历
  280. 注意:①避免只有一个头结点,造成空指针替换异常
  281.     ②③ 顺序不能变,因为③跳出的时候, 会利用到while的非空条件,
  282.    避免对比的时候, 出现野指针,直到为空时,即可直接跳出,非空则比较替换
  283. 返回值:是否删除成功 ? true:false
  284. **************************************************/
  285. bool   DeleteMaxNode(LinkList *&L)
  286. {
  287.     LinkList *nowNode,*preNode;
  288.     LinkList *maxNode,*preMaxNode;
  289.     nowNode = L->next;
  290.     preNode = L;
  291.     maxNode = nowNode;
  292.     preMaxNode = preNode;
  293.     if(nowNode == NULL) //①
  294.     {
  295.         return false;
  296.     }
  297.     while(nowNode != NULL) //直到末尾
  298.     {
  299.         if(nowNode->data > maxNode->data)   //②
  300.         {
  301.             maxNode = nowNode;
  302.             preMaxNode = preNode;
  303.         }
  304.         preNode = nowNode;       //接着走下一个节点
  305.         nowNode = nowNode->next;   //③
  306.     }
  307.     preMaxNode->next = maxNode->next;
  308.     free(maxNode);
  309.     return true;
  310. }
  311.  
  312. /**************************************************
  313. (13)函数名:LinkList_sorting
  314. 功  能:对单链表中元素进行排序(至少有2个数据节点)
  315. 参  数:LinkList *&L:要进行排序的单链表
  316. 注意: ① 空表,或者只有一个数据节点,则不需要排序,返回false
  317.       ② 开始节点必须是头结点,因为我们会用到start_compare->next,
  318.       ③ 把数据节点(第二个数据节点及以后)和原始链表(头结点+一个数据节点)
  319.       ④ 在有序表中,一直找到比前一个节点大,比后一个节点小的空挡,
  320.          所以时刻对比start_compare->next->data, 并且start_compare->next不能为空
  321.          (为空代表到达末尾,交替空指针)
  322.         ⑤ 顺序不能变, 避免丢失有序表后续信息(指针覆盖的一句话)
  323. 详细链接:https://blog.csdn.net/qq_57484399/article/details/127141307
  324. 返回值:bool: 是否符合排序标准,并排序成功  ? true: false
  325. **************************************************/
  326. bool LinkList_sorting(LinkList *&L)
  327. {
  328.     LinkList *compare,*start_compare,*Remaining_node;
  329.     if(L->next == NULL || L->next->next == NULL)//①保证至少有2个数据节点
  330.     {
  331.         return false;
  332.     }
  333.     compare = L->next->next;
  334.     start_compare = L;  //②开始节点必须是头结点
  335.     Remaining_node = compare->next;
  336.     L->next->next = NULL; //③把数据节点(第二个数据节点及以后)和原始链表(头结点+一个数据节点)
  337.  
  338.     while(compare != NULL)
  339.     {
  340.         Remaining_node = compare->next;
  341.         start_compare = L;
  342.         while((start_compare->next != NULL) && (compare->data > start_compare->next->data))
  343.         {
  344.             start_compare = start_compare->next;
  345.         } //④
  346.  
  347.         compare->next = start_compare->next;
  348.         start_compare->next = compare;     //⑤
  349.         compare = Remaining_node;
  350.     }
  351.     return true;
  352.  
  353. }

singlelist.h

  1. #ifndef SINGLELIST_H_INCLUDE
  2. #define SINGLELIST_H_INCLUDE
  3.  
  4. #include <stdio.h>
  5. #include <malloc.h>
  6.  
  7. typedef int ElemType;   //定义单链表节点类型
  8.  
  9. typedef struct LNode
  10. {
  11.     ElemType data;
  12.     struct LNode *next; //指向后继节点
  13.  
  14. }LinkList;
  15. //①头插法建立单链表
  16. void CreatList_Head(LinkList *&L, ElemType Array_used[], int Array_number);
  17. //②尾插法建立单链表
  18. void CreatList_Tail(LinkList *&L, ElemType Array_used[], int Array_number);
  19. //③输出单链表
  20. void DisplayLinkList(LinkList *L);
  21. //④销毁单链表
  22. void DestroyLinkList(LinkList *&L);
  23. //⑤ 初始化线性表
  24. void InitLinkList(LinkList *&L);
  25. //⑥ 判断线性表是否为空表
  26. bool LinkListEmpty(LinkList *L);
  27. //⑦ 返回单链表L中数据节点的个数
  28. int LinkListLength(LinkList *L);
  29. //⑧ 求线性表L中指定位置的某个数据元素
  30. bool SpecificLocate_Value(LinkList *L,int location, ElemType &value);
  31. //⑨ 按元素值查找特定元素的位置
  32. int SpecificValue_Location(LinkList *L, ElemType value);
  33. //⑩ 把元素插入到特定位置
  34. bool LinkList_InsertElement(LinkList *&L, int location, ElemType &value);
  35. //(11) 删除特定位置的节点元素
  36. bool LinkList_Delete_Location(LinkList *&L,int location, ElemType &value);
  37. //(12)单链表删除其中其最大节点元素
  38. bool  DeleteMaxNode(LinkList *&L);
  39. //(13)对单链表中元素进行排序(至少有2个数据节点)
  40. bool LinkList_sorting(LinkList *&L);
  41. #endif // SINGLELIST_H_INCLUDE

main.cpp演示函数:

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include "singlelist.h"
  4.  
  5. int main()
  6. {
  7.     LinkList *L1;
  8.     ElemType shuzu[8] = {3,2,4,5,1,7,8,6};
  9.     CreatList_Tail(L1,shuzu,6);
  10.     DisplayLinkList(L1);
  11.     if(LinkList_sorting(L1))
  12.     {
  13.         printf("排序成功:\n");
  14.         DisplayLinkList(L1);
  15.     }
  16.     else
  17.     {
  18.         printf("排序失败!\n");
  19.     }
  20.  
  21.  
  22. }

演示结果:

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/341258
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号