&>&&>&&>&&>&实现两个链表的合并
实现两个链表的合并
上传大小：4KB
基本功能要求：
（1）建立两个链表A和B 链表元素个数分别为m和n个
（2）假设元素分别为 x1 x2 …xm
把它们合并成一个线性表C 使得：
当m& n时 C x1 y1 x2 y2 …xn yn … xm
当n&m时 C y1 x1 y2 x2 …ym xm … yn
输出线性表C：
（1） 用直接插入排序法对C进行升序排序 生成链表D 并输出链表D &&基本功能要求：
（1）建立两个链表A和B 链表元素个数分别为m和n个
（2）假设元素分别为 x1 x2 …xm
把它们合并成一个线性表C 使得：
当m& n时 C x1 y1 x2 y2 …xn yn … xm
当n&m时 C y1 x1 y2 x2 …ym xm … yn
[更多]...展开收缩
综合评分：0（0位用户评分）
所需积分：2
下载次数：2
审核通过送C币
创建者：fireblue1990
创建者：ljheee
课程推荐相关知识库
上传者其他资源上传者专辑
课程资源热门标签
VIP会员动态
android服务器底层网络模块的设计方法
所需积分：0
剩余积分：720
您当前C币：0
可兑换下载积分：0
兑换下载分：
兑换失败，您当前C币不够，请先充值C币
消耗C币：0
你当前的下载分为234。
实现两个链表的合并
会员到期时间：
剩余下载次数：
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：合并两个排序的链表 - 三颗心 - 博客园
随笔 - 78, 文章 - 0, 评论 - 2, 引用 - 0
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
方法一:递归 : 要注意递归结束的条件及代码的鲁棒性
方法二:非递归。需要较多的指针
1 #include&iostream&
2 #include&stdio.h&
3 #include&tchar.h&
5 struct ListNode
ListNode* m_pN
11 ListNode* CreateListNode(int value)
ListNode* pNode = new ListNode();
pNode-&m_nValue =
pNode-&m_pNext = NULL;
20 void PrintList(ListNode* pHead)
ListNode* pNode = pH
while(pNode != NULL)
printf("%d\t",pNode-&m_nValue);
pNode = pNode-&m_pN
printf("\n");
31 void DestroyList(ListNode* pHead)
ListNode* pNode = pH
while(pNode != NULL)
pHead = pHead-&m_pN
pNode = pH
42 void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
if(pCurrent == NULL)
printf("Error to connect two nodes.\n");
pCurrent-&m_pNext = pN
53 //方法1 递归
要注意代码的鲁棒性
54 ListNode* Merge1(ListNode* pHead1, ListNode* pHead2)
if(pHead1 == NULL)
return pHead2;
else if(pHead2 == NULL)
return pHead1;
ListNode* pMergedHead = NULL;
if(pHead1-&m_nValue & pHead2-&m_nValue)
pMergedHead = pHead1;
pMergedHead-&m_pNext = Merge1(pHead1-&m_pNext, pHead2);
pMergedHead = pHead2;
pMergedHead-&m_pNext = Merge1(pHead1, pHead2-&m_pNext);
return pMergedH
77 //方法2: 非递归
比递归麻烦太多，定义的指针也多了一些。不过容易理解
78 ListNode* Merge2(ListNode* pHead1, ListNode* pHead2)
if(pHead1 == NULL)
return pHead2;
if(pHead2 == NULL)
return pHead1;
ListNode* pNode1 = pHead1;
ListNode* pNode2 = pHead2;
ListNode* pMergedHead = NULL; //合并后的链表的头结点
ListNode* pCurLastNode = NULL;
if(pNode1-&m_nValue & pNode2-&m_nValue)
pMergedHead = pHead1;
pNode1 = pNode1-&m_pN
pCurLastNode = pMergedH
pMergedHead = pHead2;
pNode2 = pNode2-&m_pN
pCurLastNode = pMergedH
while(pNode1 !=NULL && pNode2 != NULL)
if(pNode1-&m_nValue & pNode2-&m_nValue)
pCurLastNode-&m_pNext = pNode1;
pCurLastNode = pNode1;
pNode1 = pNode1-&m_pN
pCurLastNode-&m_pNext = pNode2;
pCurLastNode = pNode2;
pNode2 = pNode2-&m_pN
if(pNode1 == NULL)
pCurLastNode-&m_pNext = pNode2;
if(pNode2 == NULL)
pCurLastNode-&m_pNext = pNode1;
return pMergedH
126 //list1: 1-&3-&5
127 //list2: 2-&4-&6
129 int main()
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode3);
ConnectListNodes(pNode3, pNode5);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode6 = CreateListNode(6);
ConnectListNodes(pNode2, pNode4);
ConnectListNodes(pNode4, pNode6);
printf("The first list is:\n");
PrintList(pNode1);
printf("The second list is:\n");
PrintList(pNode2);
printf("The merged list is:\n");
//由于函数是会改变链表，不能同时运行。将true改变为false即可测试方法二
printf("Solution1\n");
ListNode* pMergedHead = Merge1(pNode1, pNode2);
PrintList(pMergedHead);
DestroyList(pMergedHead);
printf("Solution2\n");
ListNode* pMergedHead = Merge2(pNode1, pNode2);
PrintList(pMergedHead);
DestroyList(pMergedHead);#include &stdio.h&
#include &malloc.h&
#include &stdlib.h&
#define MC (Count *)malloc(sizeof(struct Count));
struct Count
int V//系数
int L//指数
struct Count * pN
//造链表并赋值
struct Count * Make (void)
//链表长度
struct Count * pHead = MC//头指针
if (pHead == NULL)
printf(&分配内存失败!\n&);
struct Count * pList = MC//结点
pList = pH
pList-&pNext = NULL;
printf(&的项数为：&);
scanf(&%d&,&len);
for (i=0;i&++i)
printf(&第%d项为(系数,指数):&,i+1);
scanf(&%d,%d&,&val,&last);
struct Count * pNew = MC
if (pHead == NULL)
printf(&分配内存失败!\n&);
pNew-&Val =
pNew-&Last =
pList-&pNext = pN
pNew-&pNext = NULL;
pList = pN
//列出多项式
void List(Count * pHead)
struct Count * p = pHead-&pN
while (p!=NULL)
printf(&(%dX^%d)&,p-&Val,p-&Last);
if (p!=NULL)
putchar('+');
putchar('\n');
//多项式相加处理
struct Count * Add (Count * pHead_1,Count * pHead_2)
pHead_1 = pHead_1-&pN
while (pHead_1 != NULL)
pHead_1 =pHead_1-&pN
if (pHead_1-&pNext == NULL)
pHead_1-&pNext = pHead_2;
return pHead_1;
int main (void)
struct Count * phead_1 = NULL;
struct Count * phead_2 = NULL;
struct Count * phead_add = NULL;
printf(&\n多项式&1&&);
phead_1 = Make();
printf(&\n你输入的多项式为:\n&);
List(phead_1);
printf(&\n多项式&2&&);
phead_2 = Make();
printf(&\n你输入的多项式为:\n&);
List(phead_2);
phead_add = Add (phead_1,phead_2);
printf(&\n多项式的和为:\n&);
List(phead_add);
在VC++6.0运行结果是：
多项式&1&的项数为：2
第1项为(系数,指数):3,3
第2项为(系数,指数):4,2
你输入的多项式为:
(3X^3)+(4X^2)
多项式&2&的项数为：2
第1项为(系数,指数):2,4
第2项为(系数,指数):5,4
你输入的多项式为:
(2X^4)+(5X^4)
多项式的和为:
(-X^-)+(2X^4)+(5X^4)
Press any key to continue
------解决方案--------------------
3个问题1、Add 函数返回的指针不是表1的头节点，而是表1的尾节点（实际上不需要返回，Add函数声明为 void 都行）2、main函数中，List调用传入的参数应该是phead_13、Add 函数中，连接两个链的时候，pHead_1-&pNext = pHead_2，实际上是把表2的头节点也链进去了，应该跳过表2的头节点链表2的第一个数据节点：pHead_1-&pNext = pHead_2-&pNext
------解决方案--------------------如果是链表连接，就无需释放，都仍是在使用的。
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有}