《[2017年整理]数据结构单链表的合并》由会员分享，可在线阅读，更多相关《[2017年整理]数据结构单链表的合并（4页珍藏版）》请在金锄头文库上搜索。
1、问题描述 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。基本要求用链式存储结构实现存储#include stdafx.h#include iostreamusing namespace std;struct Node int num ;Node *next ; ;Node* Create() /创建单链表 int n=0;Node *p1,*p2,*head; p1=p2=new Node;head=NULL;while (p1-num!=0) if (n=
2、1) head=p1; else p2-next=p1; p2=p1;p1=new Node;cinp1-num; if(p1-numnum&p1-num!=0)coutp1-num;n+; p2-next=NULL; return head; void Print(Node *head) /输出链表Node* p=head;while (p) coutnumnext; coutnext;while (q) r=q-next; q-next=p; p=q;q=r;head-next=NULL;head=p;return head;Node *MergeList(Node *head1,Node
3、 *head2) /合并单链表，降序if(head1=NULL)return head2;if(head2=NULL)return head1;Node *head;if(head1-num=head2-num)head=head1;head1=head1-next;elsehead=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-
4、next;elsetemp-next = head2;head2 = head2-next ;temp =temp-next; if (head1 = NULL) temp-next = head2;if (head2 = NULL)temp-next = head1;return head;int Count(Node *head)/求表长 Node* p=head;int i=0;while (p) i+;p=p-next; return i;int main(int argc, char* argv)Node *p1,*p2;p1,p2=new Node;cout创建单链表 1,递增排序,0 作为结束符！n;p1=Create();cout单链表 1 为n;Print(p1);cout*n;cout创建单链表 2，递增排序，0 作为结束符！n;p2=Create();cout单链表 2 为：n;Print(p2);cout*n;cout合并单链表为（降序排列）：n;Node *p3;p3=MergeList(ReverseList(p1),ReverseList(p2);Print(p3);cout合并单链表表长为:Count(p3)endl;system(pause);return 0;
