设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › 线性表合并头尾结点指向同一地址陷入死循环
返回列表 发新帖
查看: 1775|回复: 2

[已解决]线性表合并头尾结点指向同一地址陷入死循环

[复制链接]
homeskating
发表于 2023-3-13 22:59:09 | 显示全部楼层 |阅读模式
10鱼币
  1. /*
  2. 结构体
  3. */
  4. using namespace std;
  5. #define ElemType int
  6. #define Status int
  7. constexpr auto SUCCESS = 1;
  8. constexpr auto ERROR = -1;
  9. typedef struct LNode {
  10.         ElemType data;
  11.         struct LNode* next;
  12. }*Link, * Position;
  13. typedef struct {
  14.         Link head, tail;
  15.         int len;
  16. }LinkList;
  17. /*
  18. 初始化一个已经声明链表L
  19. */
  20. Status InitList(LinkList& L) {
  21.         L.head = new LNode;
  22.         L.head->next = nullptr;
  23.         L.tail = L.head;
  24.         L.len = 0;
  25.         if (L.head)
  26.         {
  27.                 cout << "初始化成功" << endl;
  28.                 return SUCCESS;
  29.         }
  30.         return ERROR;
  31. }
  32. /*
  33. 返回链表当中头结点的位置
  34. */
  35. Position GetHead(LinkList L) {
  36.         if (!L.head)
  37.         {
  38.                 cout << "线性链表不存在" << endl;
  39.                 return nullptr;
  40.         }
  41.         return L.head;
  42. }
  43. /*
  44. 由当前p指向的位置，查找p的下一个邻接元素的位置
  45. */
  46. Position NextPos(LinkList L, Link p) {
  47.         if (!L.head)
  48.         {
  49.                 cout << "线性链表不存在" << endl;
  50.                 return nullptr;
  51.         }
  52.         if (p == L.tail)
  53.         {
  54.                 return nullptr;
  55.         }
  56.         return p->next;
  57. }
  58. /*
  59. 获取当前指针p指向的元素的数据域的值，以e返回
  60. */
  61. ElemType GetCurElem(Link p) {
  62.         return p->data;
  63. }
  64. /*
  65. 将头结点删除
  66. */
  67. Status DelFirst(Link h, Link& q) {
  68.         q = h->next;
  69.         if (q)
  70.         {
  71.                 h->next = q->next;
  72.                 return SUCCESS;
  73.         }
  74.         else
  75.         {
  76.                 return ERROR;
  77.         }
  78. }
  79. /*
  80. 向链表内插入数据，s以后得一个或若干个结点
  81. 插入链表的尾部
  82. */
  83. Status Append(LinkList& L, Link s) {
  84.         //修改链表的tail指针
  85.         L.tail->next = s;
  86.         while (L.tail->next != nullptr)
  87.         {
  88.                 L.len++;
  89.                 L.tail = L.tail->next;
  90.         }
  91.         return SUCCESS;
  92. }
  93. /*
  94. 由当前p指向的位置，查找p的下一个邻接元素的位置
  95. */
  96. Position NextPos(LinkList L, Link p) {
  97.         if (!L.head)
  98.         {
  99.                 cout << "线性链表不存在" << endl;
  100.                 return nullptr;
  101.         }
  102.         if (p == L.tail)
  103.         {
  104.                 return nullptr;
  105.         }
  106.         return p->next;
  107. }
  108. /*
  109. 释放p指向的结点
  110. */
  111. void FreeNode(Link& p) {
  112.         delete p;
  113.         p = nullptr;
  114. }
  115. /*
  116. 归并La和Lb得到新的单链线性表Lc，
  117. Lc的元素也按值非递减排列
  118. */
  119. Status MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc,
  120.         int (*compare)(ElemType, ElemType)) {
  121.         if (!InitList(Lc))
  122.         {
  123.                 return ERROR;
  124.         }
  125.         Link ha = nullptr, hb = nullptr, pa = nullptr,
  126.                 pb = nullptr, q = nullptr;
  127.         ha = GetHead(La);
  128.         hb = GetHead(Lb);
  129.         pa = NextPos(La, ha);
  130.         pb = NextPos(Lb, hb);
  131.         ElemType a = 0, b = 0;
  132.         while (pa && pb)
  133.         {
  134.                 a = GetCurElem(pa);
  135.                 b = GetCurElem(pb);
  136.                 if ((*compare)(a, b) <= 0)
  137.                 {
  138.                         DelFirst(ha, q);
  139.                         Append(Lc, q);
  140.                         pa = NextPos(La, ha);
  141.                 }
  142.                 else
  143.                 {
  144.                         DelFirst(hb, q);
  145.                         Append(Lc, q);
  146.                         pb = NextPos(Lb, hb);
  147.                 }
  148.         }
  149.         if (pa)
  150.         {
  151.                 Append(Lc, pa);
  152.         }
  153.         else {
  154.                 Append(Lc, pb);
  155.         }
  156.         FreeNode(ha);
  157.         FreeNode(hb);
  158.         return SUCCESS;
  159. }
  160. /*
  161. 主函数
  162. */
  163. int main(void) {
  164.         LinkList list = {}, list2 = {}, list3;
  165.         Link link = nullptr, p = nullptr;
  166.         InitList(list);
  167.         InitList(list2);
  168.         cout << "插入成功状态为" << (ListInsert_L(list, 1, 100)) << endl;
  169.         cout << "插入成功状态为" << (ListInsert_L(list, 2, 200)) << endl;
  170.         cout << "插入成功状态为" << (ListInsert_L(list, 3, 300)) << endl;
  171.         cout << "插入成功状态为" << (ListInsert_L(list2, 1, 400)) << endl;
  172.         cout << "插入成功状态为" << (ListInsert_L(list2, 2, 500)) << endl;
  173.         cout << "插入成功状态为" << (ListInsert_L(list2, 3, 600)) << endl;
  174.         cout << "头结点位置为：" << (GetHead(list)) << endl;
  175.         cout << "头结点2位置为：" << (GetHead(list2)) << endl;
  176.         cout << "线性表长度为:" << (ListLength(list)) << endl;
  177.         ListTraverse(list, visit);
  178.         cout << endl;
  179.         ListTraverse(list2, visit);
  180.         cout << endl;
  181.         cout << "索引为：" << (LocateElem(list, 200, compare)) << endl;
  182.         LocatePos(list, 1, p);
  183.         cout << "p=" << p << endl;
  184.         MergeList_L(list, list2, list3, compare2);
  185.         ListTraverse(list3, visit);
  186. }
复制代码
最佳答案
月排行榜 / 总排行榜
jhq999
2023-3-13 22:59:10
本帖最后由 jhq999 于 2023-3-14 07:45 编辑
homeskating 发表于 2023-3-13 23:04
补一下代码

你的注释习惯太好了，bug很容易找出来
  1. Status DelFirst(Link h, Link& q) {
  2.         q = h->next;
  3.         if (q)
  4.         {
  5.                 h->next = q->next;
  6.                 q->next=nullptr;////////////////////////
  7.                 return SUCCESS;
  8.         }
  9.         else
  10.         {
  11.                 return ERROR;
  12.         }

  14. }
复制代码

最佳答案

jhq999

查看完整内容

你的注释习惯太好了，bug很容易找出来
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

jhq999
发表于 2023-3-13 22:59:10 | 显示全部楼层    本楼为最佳答案   
本帖最后由 jhq999 于 2023-3-14 07:45 编辑
homeskating 发表于 2023-3-13 23:04
补一下代码

你的注释习惯太好了，bug很容易找出来
  1. Status DelFirst(Link h, Link& q) {
  2.         q = h->next;
  3.         if (q)
  4.         {
  5.                 h->next = q->next;
  6.                 q->next=nullptr;////////////////////////
  7.                 return SUCCESS;
  8.         }
  9.         else
  10.         {
  11.                 return ERROR;
  12.         }

  14. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

homeskating
 楼主| 发表于 2023-3-13 23:04:31 | 显示全部楼层
补一下代码
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<iostream>
  4. using namespace std;
  5. #define ElemType int
  6. #define Status int
  7. constexpr auto SUCCESS = 1;
  8. constexpr auto ERROR = -1;
  9. typedef struct LNode {
  10.         ElemType data;
  11.         struct LNode* next;
  12. }*Link, * Position;
  13. typedef struct {
  14.         Link head, tail;
  15.         int len;
  16. }LinkList;
  17. /*
  18. 分配一个p指向的值为e的结点，
  19. 并返回SUCCESS，如果分配失败，则
  20. ERROR
  21. */
  22. Status MakeNode(Link& p, ElemType e) {
  23.         p = new LNode;
  24.         p->data = e;
  25.         if (p)
  26.         {
  27.                 return SUCCESS;
  28.         }
  29.         else {
  30.                 return ERROR;
  31.         }
  32. }
  33. /*
  34. 释放p指向的结点
  35. */
  36. void FreeNode(Link& p) {
  37.         delete p;
  38.         p = nullptr;
  39. }
  40. /*
  41. 初始化一个已经声明链表L
  42. */
  43. Status InitList(LinkList& L) {
  44.         L.head = new LNode;
  45.         L.head->next = nullptr;
  46.         L.tail = L.head;
  47.         L.len = 0;
  48.         if (L.head)
  49.         {
  50.                 cout << "初始化成功" << endl;
  51.                 return SUCCESS;
  52.         }
  53.         return ERROR;
  54. }
  55. /*
  56. 将当前链表L清空，变成一个初始状态的链表
  57. */
  58. Status ClearList(LinkList& L) {
  59.         Link p = L.head->next;
  60.         while (p)
  61.         {
  62.                 L.head->next = p->next;
  63.                 delete p;
  64.                 p = nullptr;
  65.                 L.len--;
  66.                 p = L.head->next;
  67.         }
  68.         if (L.head->next == nullptr)
  69.         {
  70.                 return SUCCESS;
  71.         }
  72.         else {
  73.                 return ERROR;
  74.         }
  75. }
  76. /*
  77. 销毁一个链表L
  78. */
  79. Status DestroyList(LinkList& L) {
  80.         ClearList(L);
  81.         delete L.head;
  82.         L.head = nullptr;
  83.         L.tail = nullptr;
  84.         if (!L.head)
  85.         {
  86.                 return ERROR;
  87.         }
  88.         return SUCCESS;
  89. }
  90. /*
  91. 在头结点位置插入一个新的结点，
  92. h指向头，s指向新的结点
  93. */
  94. Status InsFirst(Link h, Link s) {
  95.         s->next = h->next;
  96.         h->next = s;
  97.         return SUCCESS;
  98. }
  99. /*
  100. 将头结点删除
  101. */
  102. Status DelFirst(Link h, Link& q) {
  103.         q = h->next;
  104.         if (q)
  105.         {
  106.                 h->next = q->next;
  107.                 return SUCCESS;
  108.         }
  109.         else
  110.         {
  111.                 return ERROR;
  112.         }
  113. }
  114. /*
  115. 向链表内插入数据，s以后得一个或若干个结点
  116. 插入链表的尾部
  117. */
  118. Status Append(LinkList& L, Link s) {
  119.         //修改链表的tail指针
  120.         L.tail->next = s;
  121.         while (L.tail->next != nullptr)
  122.         {
  123.                 L.len++;
  124.                 L.tail = L.tail->next;
  125.         }
  126.         return SUCCESS;
  127. }
  128. /*
  129. 删除链表尾结点元素，由q返回
  130. */
  131. Status Remove(LinkList& L, Link& q) {
  132.         if (!L.head)
  133.         {
  134.                 cout << "线性链表不存在" << endl;
  135.                 return ERROR;
  136.         }
  137.         q = L.head;
  138.         while (q->next != L.tail)
  139.         {
  140.                 q = q->next;
  141.         }
  142.         L.tail = q;
  143.         q = q->next;
  144.         L.tail->next = nullptr;
  145.         L.len--;
  146.         delete q;
  147.         q = nullptr;
  148.         return SUCCESS;
  149. }
  150. /*
  151. 将元素插入由p指定的位置的前一个位置，
  152. 并修改p指向新的结点
  153. */
  154. Status InsBefore(LinkList& L, Link& p, Link s) {
  155.         Link q = L.head;
  156.         if (!L.head)
  157.         {
  158.                 cout << "线性链表不存在" << endl;
  159.                 return ERROR;
  160.         }
  161.         while (q->next != p)
  162.         {
  163.                 q = q->next;
  164.         }
  165.         q->next = s;
  166.         s->next = p;
  167.         p = s;
  168.         L.len++;
  169.         return SUCCESS;
  170. }
  171. /*
  172. 将元素插入由p指定位置的下一个位置，
  173. 并修改p指向新结点
  174. */
  175. Status InsAfter(LinkList& L, Link& p, Link s) {
  176.         if (!L.head)
  177.         {
  178.                 cout << "线性链表不存在" << endl;
  179.                 return ERROR;
  180.         }
  181.         s->next = p->next;
  182.         p->next = s;
  183.         if (p == L.tail)
  184.         {
  185.                 L.tail = L.tail->next;
  186.         }
  187.         p = s;
  188.         L.len++;
  189.         return SUCCESS;
  190. }
  191. /*
  192. 修改当前指针p指向的元素的数据域的值为e
  193. */
  194. Status SetCurElem(Link& p, ElemType e) {
  195.         p->data = e;
  196.         return SUCCESS;
  197. }
  198. /*
  199. 获取当前指针p指向的元素的数据域的值，以e返回
  200. */
  201. ElemType GetCurElem(Link p) {
  202.         return p->data;
  203. }
  204. /*
  205. 将线性表清空
  206. */
  207. Status ListEmpty(LinkList L) {
  208.         if (!L.head)
  209.         {
  210.                 cout << "线性链表不存在" << endl;
  211.                 return 0;
  212.         }
  213.         if (L.head->next == nullptr)
  214.         {
  215.                 return SUCCESS;
  216.         }
  217.         else
  218.         {
  219.                 return ERROR;
  220.         }
  221. }
  222. /*
  223. 获取线性表长度
  224. */
  225. int ListLength(LinkList L) {
  226.         if (!L.head)
  227.         {
  228.                 cout << "线性链表不存在" << endl;
  229.                 return ERROR;
  230.         }
  231.         return L.len;
  232. }
  233. /*
  234. 返回链表当中头结点的位置
  235. */
  236. Position GetHead(LinkList L) {
  237.         if (!L.head)
  238.         {
  239.                 cout << "线性链表不存在" << endl;
  240.                 return nullptr;
  241.         }
  242.         return L.head;
  243. }
  244. /*
  245. 返回链表当中最后一个结点的位置
  246. */
  247. Position GetLast(LinkList L) {
  248.         if (!L.head)
  249.         {
  250.                 cout << "线性链表不存在" << endl;
  251.                 return nullptr;
  252.         }
  253.         return L.tail;
  254. }
  255. /*
  256. 由当前p指向的位置，查找p的邻接前一个结点位置
  257. */
  258. Position PriorPos(LinkList L, Link p) {
  259.         Link q = L.head;
  260.         if (!L.head)
  261.         {
  262.                 cout << "线性链表不存在" << endl;
  263.                 return nullptr;
  264.         }
  265.         if (p == L.head)
  266.         {
  267.                 return nullptr;
  268.         }
  269.         while (q->next != p)
  270.         {
  271.                 q = q->next;
  272.         }
  273.         return q;
  274. }
  275. /*
  276. 由当前p指向的位置，查找p的下一个邻接元素的位置
  277. */
  278. Position NextPos(LinkList L, Link p) {
  279.         if (!L.head)
  280.         {
  281.                 cout << "线性链表不存在" << endl;
  282.                 return nullptr;
  283.         }
  284.         if (p == L.tail)
  285.         {
  286.                 return nullptr;
  287.         }
  288.         return p->next;
  289. }
  290. /*
  291. 返回p指示线性链表L中第i个结点的位置并返回SUCCESS,
  292. i值不合法则返回ERROR
  293. */
  294. Status LocatePos(LinkList L, int i, Link& p) {
  295.         int j = 0;
  296.         Link pt = L.head;
  297.         while (pt && j < i)
  298.         {
  299.                 pt = pt->next;
  300.                 j++;
  301.         }
  302.         if (!pt || j > i)
  303.         {
  304.                 return ERROR;
  305.         }
  306.         else
  307.         {
  308.                 p = pt;
  309.                 return SUCCESS;
  310.         }
  311. }
  312. Status compare(ElemType x, ElemType y) {
  313.         if (x == y)
  314.         {
  315.                 return SUCCESS;
  316.         }
  317.         else {
  318.                 return ERROR;
  319.         }
  320. }
  321. Status compare2(ElemType x, ElemType y) {
  322.         return x - y;
  323. }
  324. /*
  325. 返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置
  326. */
  327. int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
  328.         Link q = L.head->next;
  329.         int count = 1;
  330.         while (q != nullptr)
  331.         {
  332.                 if (compare(q->data, e) == SUCCESS) {
  333.                         return count;
  334.                 }
  335.                 q = q->next;
  336.                 count++;
  337.         }
  338.         return ERROR;
  339. }
  340. Status visit(ElemType x) {
  341.         cout << x << " ";
  342.         return SUCCESS;
  343. }
  344. /*
  345. 依次对L的每个元素调用函数visit(),
  346. 一但visit()失败，则操作失败
  347. */
  348. Status ListTraverse(LinkList L, Status(*visit)(ElemType)) {
  349.         Link q = L.head->next;
  350.         while (q)
  351.         {
  352.                 if (visit(q->data)) {
  353.                         q = q->next;
  354.                 }
  355.                 else
  356.                 {
  357.                         return ERROR;
  358.                 }
  359.         }
  360.         return SUCCESS;
  361. }
  362. /*
  363. 在带头结点的单链线性表L的第i个元素
  364. 之前插入元素e
  365. */
  366. Status ListInsert_L(LinkList& L, int i, ElemType e) {
  367.         Link h = nullptr, s = nullptr;
  368.         if (!LocatePos(L, i - 1, h))
  369.         {
  370.                 return ERROR;
  371.         }
  372.         if (!MakeNode(s, e))
  373.         {
  374.                 return ERROR;
  375.         }
  376.         int inFirstResult = InsFirst(h, s);
  377.         cout << (inFirstResult == SUCCESS ? "插入新结点成功" : "插入新结点失败") << endl;
  378.         Append(L, s);
  379.         return SUCCESS;
  380. }
  381. /*
  382. 归并La和Lb得到新的单链线性表Lc，
  383. Lc的元素也按值非递减排列
  384. */
  385. Status MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc,
  386.         int (*compare)(ElemType, ElemType)) {
  387.         if (!InitList(Lc))
  388.         {
  389.                 return ERROR;
  390.         }
  391.         Link ha = nullptr, hb = nullptr, pa = nullptr,
  392.                 pb = nullptr, q = nullptr;
  393.         ha = GetHead(La);
  394.         hb = GetHead(Lb);
  395.         pa = NextPos(La, ha);
  396.         pb = NextPos(Lb, hb);
  397.         ElemType a = 0, b = 0;
  398.         while (pa && pb)
  399.         {
  400.                 a = GetCurElem(pa);
  401.                 b = GetCurElem(pb);
  402.                 if ((*compare)(a, b) <= 0)
  403.                 {
  404.                         DelFirst(ha, q);
  405.                         Append(Lc, q);
  406.                         pa = NextPos(La, ha);
  407.                 }
  408.                 else
  409.                 {
  410.                         DelFirst(hb, q);
  411.                         Append(Lc, q);
  412.                         pb = NextPos(Lb, hb);
  413.                 }
  414.         }
  415.         if (pa)
  416.         {
  417.                 Append(Lc, pa);
  418.         }
  419.         else {
  420.                 Append(Lc, pb);
  421.         }
  422.         FreeNode(ha);
  423.         FreeNode(hb);
  424.         return SUCCESS;
  425. }
  426. int main(void) {
  427.         LinkList list = {}, list2 = {}, list3;
  428.         Link link = nullptr, p = nullptr;
  429.         InitList(list);
  430.         InitList(list2);
  431.         int makeNodeResult = MakeNode(link, 100);
  432.         cout << (makeNodeResult == SUCCESS ? "成功分配结点" : "分配结点失败") << endl;
  433.         cout << "插入成功状态为" << (ListInsert_L(list, 1, 100)) << endl;
  434.         cout << "插入成功状态为" << (ListInsert_L(list, 2, 200)) << endl;
  435.         cout << "插入成功状态为" << (ListInsert_L(list, 3, 300)) << endl;
  436.         cout << "插入成功状态为" << (ListInsert_L(list2, 1, 400)) << endl;
  437.         cout << "插入成功状态为" << (ListInsert_L(list2, 2, 500)) << endl;
  438.         cout << "插入成功状态为" << (ListInsert_L(list2, 3, 600)) << endl;
  439.         cout << "头结点位置为：" << (GetHead(list)) << endl;
  440.         cout << "头结点2位置为：" << (GetHead(list2)) << endl;
  441.         cout << "线性表长度为:" << (ListLength(list)) << endl;
  442.         ListTraverse(list, visit);
  443.         cout << endl;
  444.         ListTraverse(list2, visit);
  445.         cout << endl;
  446.         cout << "索引为：" << (LocateElem(list, 200, compare)) << endl;
  447.         LocatePos(list, 1, p);
  448.         cout << "p=" << p << endl;
  449.         MergeList_L(list, list2, list3, compare2);
  450.         ListTraverse(list3, visit);
  451. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-4-22 17:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表