数据结构单链表合并

《数据结构单链表合并》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、[问题描述]假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。[基本要求]用链式存储结构实现存储#include"stdafx.h"#include"iostream"usingnamespacestd;structNode{intnum;Node*next;};Node*Create()//创建单链表{intn=0;Node*p1,*p2,*head;p1=p2=newNode;head=NULL;while(p1->num!=0)

2、{if(n==1){head=p1;}elsep2->next=p1;p2=p1;p1=newNode;cin>>p1->num;if(p1->num<=p2->num&&p1->num!=0){cout<<"重新输入按递增排序的单链表:";cin>>p1->num;}n++;}p2->next=NULL;returnhead;}voidPrint(Node*head)//输出链表{Node*p=head;while(p){cout<num<<"";p=p->next;}cout<

3、链表的逆转{Node*p,*q,*r;p=head;q=p->next;while(q){r=q->next;q->next=p;p=q;q=r;}head->next=NULL;head=p;returnhead;}Node*MergeList(Node*head1,Node*head2)//合并单链表，降序{if(head1==NULL)returnhead2;if(head2==NULL)returnhead1;Node*head;if(head1->num>=head2->num){head=head1;head1=head1->next;}else{hea

4、d=head2;head2=head2->next;}Node*temp=head;while(head1!=NULL&&head2!=NULL){if(head1->num>=head2->num){temp->next=head1;head1=head1->next;temp=temp->next;}else{temp->next=head2;head2=head2->next;temp=temp->next;}}if(head1==NULL)temp->next=head2;if(head2==NULL)temp->next=head1;returnhead;

5、}intCount(Node*head)//求表长{Node*p=head;inti=0;while(p){i++;p=p->next;}returni;}intmain(intargc,char*argv[]){Node*p1,*p2;p1,p2=newNode;cout<<"创建单链表1,递增排序,0作为结束符！";p1=Create();cout<<"单链表1为";Print(p1);cout<<"*********************************************";cout<<"创建单链表2，递增排序，0作为结束符！"

6、;p2=Create();cout<<"单链表2为：";Print(p2);cout<<"*********************************************";cout<<"合并单链表为（降序排列）：";Node*p3;p3=MergeList(ReverseList(p1),ReverseList(p2));Print(p3);cout<<"合并单链表表长为:"<