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

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › C++合并有序链表
返回列表 发新帖
查看: 1555|回复: 5

[已解决]C++合并有序链表

[复制链接]
旋转小代码
发表于 2020-9-23 16:25:58 | 显示全部楼层 |阅读模式
1鱼币
问题描述：将两个非递减有序单链表合并成一个非递减有序单链表；


输入样例：
5
1 3 5 7 9
6
2 3 4 6 8 10


输出样例：
1 2 3 3 4 5 6 7 8 9 10
以下是我的代码，只有部分是自己写的，剩下是原题目，错误大致在于 Merge(LinkList &A, LinkList &B) 里。
  1. #include <iostream>
  2. using namespace std;
  3. struct Node
  4. {
  5.         int data;
  6.    
  7.         Node *next;
  8. };
  9. class LinkList
  10. {
  11. public:
  12.    
  13.         LinkList(int a[],int n);//尾插法在单链表中插入n个数据
  14.         
  15.         ~LinkList();
  16.         
  17.         void PrintList();
  18.            
  19.         Node * GetFirst(){return first;}

  21. private:
  22.    
  23.         Node *first;
  24. };

  26. LinkList::LinkList(int a[],int n)
  27. {
  28.         first = new Node; //附设头结点

  30.         Node *rear = first;
  31.         
  32.         int i;
  33.         for(i=0;i<n;i++)
  34.         {
  35.                 Node *s = new Node;
  36.                 s->data = a[i];
  37.                 rear->next = s;
  38.                 rear = s;
  39.         }        
  40.         rear->next = NULL;
  41. }

  43. void LinkList::PrintList()
  44. {
  45.         
  46.         Node *p=first->next;
  47.         
  48.         while(p)
  49.                
  50.         {
  51.                
  52.                 cout<<p->data<<" ";
  53.         
  54.                 p=p->next;
  55.                
  56.         }
  57. }


  60. LinkList::~LinkList()
  61. {
  62.    
  63.         Node *p=first,*s;
  64.    
  65.         while(!p)
  66.                
  67.         {
  68.         
  69.                 s=p;
  70.         
  71.                 p=p->next;
  72.         
  73.                 delete s;
  74.                
  75.         }
  76. }

  78. void Merge(LinkList &A, LinkList &B)
  79. {
  80.         //Todo:将A和B两个非递减有序单链表合并，结果放到A链表中
  81.         
  82.         Node *p = A.GetFirst() ->next;
  83.         Node *q = B.GetFirst() ->next;
  84.         Node *s, *t;
  85.         s = q;
  86.         t = p;
  87.         
  88. //while里的m 和n 是主函数的变量，不知道怎么访问，或者有别的方法？求指教=_=      
  89.         while(q->next!= nullptr)
  90.         {
  91.                 for(int count = 0; count<m; count++)
  92.                 {
  93.                         if(s->data >= p->data && s->next < p->next)
  94.                         {
  95.                                 q = q->next ;
  96.                                 s->next =p->next ;
  97.                                 p->next =s;
  98.                                 s = q;
  99.                         }
  100.                         else
  101.                         {
  102.                                 p = p->next;
  103.                         }
  104.                 }
  105.                
  106.         }

  108. }
  109. int main()
  110. {
  111.         int m,i,x;
  112.    
  113.         cin >> m;
  114.         int a[m];
  115.         for(i=0;i<m;i++)
  116.         {
  117.                 cin >> a[i];
  118.           }
  119.         LinkList la(a,m);

  121.         //Todo:用与la相同方式创建单链表lb
  122.         cin >> n;
  123.         int b[n];
  124.         for(i=0;i<n;i++)
  125.         {
  126.                 cin >> b[i];
  127.           }
  128.         LinkList lb(b,n);

  130.         
  131.             
  132.         Merge(la,lb);

  134.         la.PrintList();

  136.         return 0;
  137. }
复制代码

最佳答案
月排行榜 / 总排行榜
xieglt
2020-9-23 16:25:59
本帖最后由 xieglt 于 2020-9-23 17:29 编辑
  1. #include <iostream>
  2. using namespace std;

  4. struct Node
  5. {
  6.         int data;
  7.         struct Node *next;
  8.                
  9.                 bool operator > (const struct Node  & e)
  10.                 {
  11.                         return (data > e.data) ? true : false;
  12.                 }

  14.                 bool operator < (const struct Node  & e)
  15.                 {
  16.                         return (data < e.data) ? true : false;
  17.                 }
  18. };

  20. class LinkList
  21. {
  22. public:
  23.    
  24.         LinkList(int a[],int n);//尾插法在单链表中插入n个数据
  25.         
  26.         ~LinkList();
  27.         
  28.         void PrintList();
  29.            
  30.         Node * GetFirst(){return first->next;}
  31.                
  32.                 void Clean()
  33.                 {
  34.                         first->next = NULL;
  35.                 }

  37.                 void SetList(Node * p)
  38.                 {
  39.                         first->next = p;
  40.                 }

  42. private:
  43.    
  44.         Node *first;
  45. };

  47. LinkList::LinkList(int a[],int n)
  48. {
  49.         first = new Node; //附设头结点

  51.         Node *rear = first;
  52.         
  53.         int i;
  54.         for(i=0;i<n;i++)
  55.         {
  56.                 Node *s = new Node;
  57.                 s->data = a[i];
  58.                 rear->next = s;
  59.                 rear = s;
  60.         }        
  61.         rear->next = NULL;
  62. }

  64. void LinkList::PrintList()
  65. {
  66.         
  67.         Node *p=first->next;
  68.         
  69.         while(p)
  70.                
  71.         {
  72.                
  73.                 cout<<p->data<<" ";
  74.         
  75.                 p=p->next;
  76.                
  77.         }
  78. }


  81. LinkList::~LinkList()
  82. {
  83.    
  84.         Node *p=first,*s;
  85.                
  86.                 //!p 循环条件逻辑错误,
  87.         while(p != NULL)
  88.                
  89.         {
  90.         
  91.                 s=p;
  92.         
  93.                 p=p->next;
  94.         
  95.                 delete s;
  96.                
  97.         }
  98. }

  100. Node * MergeList(Node* l1,Node * l2)
  101. {
  102.         if(l1 == NULL)
  103.         {
  104.                 return l2;
  105.         }
  106.        
  107.         if(l2 == NULL)
  108.         {
  109.                 return l1;
  110.         }
  111.        
  112.         Node * lpHead = (* l1 < * l2) ? l1 : l2;
  113.         Node * lpBig = (* l1 < * l2) ? l2 : l1;
  114.        
  115.         Node * lpSmall = lpHead;
  116.        
  117.         while(lpSmall != NULL)
  118.         {
  119.                 if(lpSmall->next == NULL)
  120.                 {
  121.                         lpSmall->next = lpBig;
  122.                         break;
  123.                 }
  124.                
  125.                 if(*(lpSmall->next) < * lpBig)
  126.                 {
  127.                         lpSmall = lpSmall->next;
  128.                 }
  129.                 else
  130.                 {
  131.                         Node * lpNode = lpSmall->next;
  132.                         lpSmall->next = lpBig;
  133.                        
  134.                         lpSmall = lpBig;
  135.                         lpBig = lpNode;
  136.                 }
  137.         }       
  138.         return lpHead;
  139. }

  141. void Merge(LinkList &A, LinkList &B)
  142. {
  143.        
  144.         Node *p = A.GetFirst();
  145.         Node *q = B.GetFirst();
  146.         Node *s, *t;
  147.         s = q;
  148.         t = p;

  150.         A.SetList(MergeList(p,q));
  151.         //将两个链表合并后，要把后一个链表清空，否则释放内存释放两次
  152.         B.Clean();
  153.        
  154.         //while里的m 和n 是主函数的变量，不知道怎么访问，或者有别的方法？求指教=_=      
  155. /*        while(q->next!= nullptr)
  156.         {
  157.                 for(int count = 0; count<m; count++)
  158.                 {
  159.                         if(s->data >= p->data && s->next < p->next)
  160.                         {
  161.                                 q = q->next ;
  162.                                 s->next =p->next ;
  163.                                 p->next =s;
  164.                                 s = q;
  165.                         }
  166.                         else
  167.                         {
  168.                                 p = p->next;
  169.                         }
  170.                 }
  171.                
  172.     }
  173. */
  174. }

  176. int main()
  177. {
  178.         int m,n,i,x;
  179.    
  180.         cin >> m;
  181.                 //动态数组不能这么定义，得用new生成
  182.                 //int a[m]
  183.         int * a = new int[m];
  184.         for(i=0;i<m;i++)
  185.         {
  186.                 cin >> a[i];
  187.         }
  188.         LinkList la(a,m);
  189.                 delete[] a;

  191.         //Todo:用与la相同方式创建单链表lb
  192.         cin >> n;
  193.         int * b = new int[n];
  194.         for(i=0;i<n;i++)
  195.         {
  196.                 cin >> b[i];
  197.           }
  198.         LinkList lb(b,n);
  199.                 delete [] b;

  201.         
  202.             
  203.         Merge(la,lb);

  205.         la.PrintList();

  207.         return 0;
  208. }
复制代码

最佳答案

xieglt

查看完整内容

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

xieglt
发表于 2020-9-23 16:25:59 | 显示全部楼层    本楼为最佳答案   
本帖最后由 xieglt 于 2020-9-23 17:29 编辑
  1. #include <iostream>
  2. using namespace std;

  4. struct Node
  5. {
  6.         int data;
  7.         struct Node *next;
  8.                
  9.                 bool operator > (const struct Node  & e)
  10.                 {
  11.                         return (data > e.data) ? true : false;
  12.                 }

  14.                 bool operator < (const struct Node  & e)
  15.                 {
  16.                         return (data < e.data) ? true : false;
  17.                 }
  18. };

  20. class LinkList
  21. {
  22. public:
  23.    
  24.         LinkList(int a[],int n);//尾插法在单链表中插入n个数据
  25.         
  26.         ~LinkList();
  27.         
  28.         void PrintList();
  29.            
  30.         Node * GetFirst(){return first->next;}
  31.                
  32.                 void Clean()
  33.                 {
  34.                         first->next = NULL;
  35.                 }

  37.                 void SetList(Node * p)
  38.                 {
  39.                         first->next = p;
  40.                 }

  42. private:
  43.    
  44.         Node *first;
  45. };

  47. LinkList::LinkList(int a[],int n)
  48. {
  49.         first = new Node; //附设头结点

  51.         Node *rear = first;
  52.         
  53.         int i;
  54.         for(i=0;i<n;i++)
  55.         {
  56.                 Node *s = new Node;
  57.                 s->data = a[i];
  58.                 rear->next = s;
  59.                 rear = s;
  60.         }        
  61.         rear->next = NULL;
  62. }

  64. void LinkList::PrintList()
  65. {
  66.         
  67.         Node *p=first->next;
  68.         
  69.         while(p)
  70.                
  71.         {
  72.                
  73.                 cout<<p->data<<" ";
  74.         
  75.                 p=p->next;
  76.                
  77.         }
  78. }


  81. LinkList::~LinkList()
  82. {
  83.    
  84.         Node *p=first,*s;
  85.                
  86.                 //!p 循环条件逻辑错误,
  87.         while(p != NULL)
  88.                
  89.         {
  90.         
  91.                 s=p;
  92.         
  93.                 p=p->next;
  94.         
  95.                 delete s;
  96.                
  97.         }
  98. }

  100. Node * MergeList(Node* l1,Node * l2)
  101. {
  102.         if(l1 == NULL)
  103.         {
  104.                 return l2;
  105.         }
  106.        
  107.         if(l2 == NULL)
  108.         {
  109.                 return l1;
  110.         }
  111.        
  112.         Node * lpHead = (* l1 < * l2) ? l1 : l2;
  113.         Node * lpBig = (* l1 < * l2) ? l2 : l1;
  114.        
  115.         Node * lpSmall = lpHead;
  116.        
  117.         while(lpSmall != NULL)
  118.         {
  119.                 if(lpSmall->next == NULL)
  120.                 {
  121.                         lpSmall->next = lpBig;
  122.                         break;
  123.                 }
  124.                
  125.                 if(*(lpSmall->next) < * lpBig)
  126.                 {
  127.                         lpSmall = lpSmall->next;
  128.                 }
  129.                 else
  130.                 {
  131.                         Node * lpNode = lpSmall->next;
  132.                         lpSmall->next = lpBig;
  133.                        
  134.                         lpSmall = lpBig;
  135.                         lpBig = lpNode;
  136.                 }
  137.         }       
  138.         return lpHead;
  139. }

  141. void Merge(LinkList &A, LinkList &B)
  142. {
  143.        
  144.         Node *p = A.GetFirst();
  145.         Node *q = B.GetFirst();
  146.         Node *s, *t;
  147.         s = q;
  148.         t = p;

  150.         A.SetList(MergeList(p,q));
  151.         //将两个链表合并后，要把后一个链表清空，否则释放内存释放两次
  152.         B.Clean();
  153.        
  154.         //while里的m 和n 是主函数的变量，不知道怎么访问，或者有别的方法？求指教=_=      
  155. /*        while(q->next!= nullptr)
  156.         {
  157.                 for(int count = 0; count<m; count++)
  158.                 {
  159.                         if(s->data >= p->data && s->next < p->next)
  160.                         {
  161.                                 q = q->next ;
  162.                                 s->next =p->next ;
  163.                                 p->next =s;
  164.                                 s = q;
  165.                         }
  166.                         else
  167.                         {
  168.                                 p = p->next;
  169.                         }
  170.                 }
  171.                
  172.     }
  173. */
  174. }

  176. int main()
  177. {
  178.         int m,n,i,x;
  179.    
  180.         cin >> m;
  181.                 //动态数组不能这么定义，得用new生成
  182.                 //int a[m]
  183.         int * a = new int[m];
  184.         for(i=0;i<m;i++)
  185.         {
  186.                 cin >> a[i];
  187.         }
  188.         LinkList la(a,m);
  189.                 delete[] a;

  191.         //Todo:用与la相同方式创建单链表lb
  192.         cin >> n;
  193.         int * b = new int[n];
  194.         for(i=0;i<n;i++)
  195.         {
  196.                 cin >> b[i];
  197.           }
  198.         LinkList lb(b,n);
  199.                 delete [] b;

  201.         
  202.             
  203.         Merge(la,lb);

  205.         la.PrintList();

  207.         return 0;
  208. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

旋转小代码
 楼主| 发表于 2020-9-23 18:28:27 | 显示全部楼层
xieglt 发表于 2020-9-23 17:28

能不能只改while里的代码，别的代码题目给的尽量不动
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

fury可
发表于 2020-9-23 21:30:36 | 显示全部楼层
你这s 和 t 有什么定义的必要么  而且还把s 和 p混用
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

fury可
发表于 2020-9-24 14:22:01 | 显示全部楼层
  1. #include <iostream>
  2. using namespace std;
  3. struct Node
  4. {
  5.         int data;
  6.    
  7.         Node *next;
  8. };
  9. class LinkList
  10. {
  11. public:
  12.    
  13.         LinkList(int a[],int n);//尾插法在单链表中插入n个数据
  14.         
  15.         ~LinkList();
  16.         
  17.         void PrintList();
  18.            
  19.         Node * GetFirst(){return first;}

  21. private:
  22.    
  23.         Node *first;
  24. };

  26. LinkList::LinkList(int a[],int n)
  27. {
  28.         first = new Node; //附设头结点

  30.         Node *rear = first;
  31.         
  32.         int i;
  33.         for(i=0;i<n;i++)
  34.         {
  35.                 Node *s = new Node;
  36.                 s->data = a[i];
  37.                 rear->next = s;
  38.                 rear = s;
  39.         }        
  40.         rear->next = nullptr;
  41. }

  43. void LinkList::PrintList()
  44. {
  45.         
  46.         Node *p=first->next;
  47.         
  48.         while(p)
  49.                
  50.         {
  51.                
  52.                 cout<<p->data<<" ";
  53.         
  54.                 p=p->next;
  55.                
  56.         }
  57. }


  60. LinkList::~LinkList()
  61. {
  62.    
  63.         Node *p=first,*s;
  64.    
  65.         while(p)
  66.                
  67.         {
  68.         
  69.                 s=p;
  70.         
  71.                 p=p->next;
  72.         
  73.                 delete s;
  74.                
  75.         }
  76. }

  78. void Merge(LinkList &A, LinkList &B, int m,int n)
  79. {
  80.         //Todo:将A和B两个非递减有序单链表合并，结果放到A链表中
  81.         
  82.         Node *p = A.GetFirst() ->next;
  83.         Node *q = B.GetFirst() ->next;
  84.         Node *s, *t, *j;
  85.         t = A.GetFirst()->next;
  86.         s = B.GetFirst()->next;
  87.         
  88. //while里的m 和n 是主函数的变量，不知道怎么访问，或者有别的方法？求指教=_=      
  89.         while(p)
  90.         {
  91.                 if(p->data<q->data&&p)
  92.                 {
  93.                     t = p;
  94.                     p = p->next;
  95.                 }
  96.                 else
  97.                 {
  98.                     t->next = s;
  99.                     while((q->data<=p->data)&&q)
  100.                     {
  101.                         s = q;
  102.                         q = q->next;
  103.                     }
  104.                     s->next = p;
  105.                     s = q;
  106.                 }
  107.         }
  108.         if(q)
  109.         {
  110.             t->next = q;
  111.         }

  113. }
  114. int main()
  115. {
  116.         int m,n,i,x;
  117.    
  118.         cin >> m;
  119.         int a[m];
  120.         for(i=0;i<m;i++)
  121.         {
  122.             cin >> a[i];
  123.         }
  124.         LinkList la(a,m);

  126.         //Todo:用与la相同方式创建单链表lb
  127.         cin >> n;
  128.         int b[n];
  129.         for(i=0;i<n;i++)
  130.         {
  131.             cin >> b[i];
  132.         }
  133.         LinkList lb(b,n);

  135.         cout<< "Merge"<<endl;
  136.             
  137.         Merge(la,lb,m,n);

  139.         la.PrintList();

  141.         return 0;
  142. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

孟婆汤
发表于 2020-9-25 11:06:25 | 显示全部楼层
  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>

  6. typedef struct Node
  7. {
  8.         Node* pNext;
  9.         int data;
  10. }Node, *pNode;

  12. typedef struct Link
  13. {
  14.         int cur_len;
  15.         pNode pHeader;
  16. }Link, *PLink;


  19. PLink InitLink()
  20. {
  21.         pNode pHeader = (pNode)malloc(sizeof(Node));
  22.         memset(pHeader, 0, sizeof(Node));
  23.         pHeader->data = 0;
  24.         pHeader->pNext = NULL;

  26.         PLink plinkNode = (PLink)malloc(sizeof(Link));
  27.         memset(plinkNode, 0, sizeof(Link));
  28.         plinkNode->cur_len = 0;
  29.         plinkNode->pHeader = pHeader;

  31.         return plinkNode;
  32. }

  34. bool AddNode(PLink plinkNode, int data)
  35. {
  36.         pNode pHeader = plinkNode->pHeader;
  37.         if (pHeader == NULL)
  38.         {
  39.                 printf("无效链表\n");
  40.                 return false;
  41.         }
  42.         pNode pTempNode = (pNode)malloc(sizeof(Node));
  43.         memset(pTempNode, 0, sizeof(Node));
  44.         pTempNode->data = data;
  45.         pTempNode->pNext = NULL;

  47.         pNode pCurNode = pHeader;
  48.         while (pCurNode->pNext != NULL)
  49.         {
  50.                 pCurNode = pCurNode->pNext;
  51.         }
  52.         pCurNode->pNext = pTempNode;
  53.         plinkNode->cur_len++;
  54.         return true;
  55. }

  57. bool InsertSortData(PLink plinkNode, int data)
  58. {
  59.         pNode pHeader = plinkNode->pHeader;
  60.         if (pHeader == NULL)
  61.         {
  62.                 printf("无效链表\n");
  63.                 return -1;
  64.         }

  66.         pNode pCurNode = pHeader;
  67.         int flag = 0;
  68.         while (pCurNode->pNext != NULL)
  69.         {
  70.                 if (pCurNode->pNext->data >= data)
  71.                 {
  72.                         pNode pTempNode = (pNode)malloc(sizeof(Node));
  73.                         pTempNode->data = data;
  74.                         pTempNode->pNext = pCurNode->pNext;
  75.                         pCurNode->pNext = pTempNode;
  76.                         flag = 1;
  77.                         plinkNode->cur_len++;
  78.                         break;
  79.                 }
  80.                 else
  81.                 {
  82.                         pCurNode = pCurNode->pNext;
  83.                 }
  84.         }
  85.         // 最后一个
  86.         if (flag == 0)
  87.         {
  88.                 pNode pTempNode = (pNode)malloc(sizeof(Node));
  89.                 pTempNode->data = data;
  90.                 pTempNode->pNext = pCurNode->pNext;
  91.                 pCurNode->pNext = pTempNode;
  92.                 plinkNode->cur_len++;
  93.         }
  94. }

  96. void MergeLink(PLink plinkNode1, PLink plinkNode2)
  97. {
  98.         // 将 Plink2 中的元素，插入 Plink1中

  100.         pNode pHeader1 = plinkNode1->pHeader;
  101.         pNode pHeader2 = plinkNode2->pHeader;


  104.         pNode pCurNode1 = pHeader1->pNext;
  105.         pNode pCurNode2 = pHeader2->pNext;


  108.         /*
  109.         5
  110.         1 3 5 7 9
  111.         6
  112.         2 3 4 6 8 10
  113.         */
  114.         for (int i = 0; i < plinkNode2->cur_len; i++)
  115.         {
  116.                 InsertSortData(plinkNode1, pCurNode2->data);
  117.                 pHeader2->pNext = pCurNode2->pNext;
  118.                 free(pCurNode2);
  119.                 pCurNode2 = pHeader2->pNext;
  120.         }
  121.         free(pHeader2);
  122.         free(plinkNode2);

  124. }

  126. int main()
  127. {
  128.         PLink plinkNode1 = InitLink();
  129.         PLink plinkNode2 = InitLink();
  130.         for (int i = 1; i < 10; i+=2)
  131.         {
  132.                 AddNode(plinkNode1, i);
  133.         }
  134.         for (int i = 2; i < 11; i+=2)
  135.         {
  136.                 AddNode(plinkNode2, i);
  137.         }

  139.         MergeLink(plinkNode1, plinkNode2);


  142.         system("pause");
  143.         return 0;       
  144. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2025-7-6 09:51

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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