首页 > 代码库 > 数据结构之 线性表---有序链表的归并
数据结构之 线性表---有序链表的归并
数据结构实验之链表四：有序链表的归并
Time Limit: 1000MS Memory limit: 65536K
题目描述
分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。
输入
第一行输入M与N的值；
第二行依次输入M个有序的整数；
第三行依次输入N个有序的整数。
第二行依次输入M个有序的整数；
第三行依次输入N个有序的整数。
输出
输出合并后的单链表所包含的M+N个有序的整数。
示例输入
6 51 23 26 45 66 9914 21 28 50 100
示例输出
1 14 21 23 26 28 45 50 66 99 100
提示
不得使用数组！
#include <iostream>#include <string>#include <stdio.h>#include <string.h>#include <queue>#define INF 99999999using namespace std;struct node{ int data; struct node *next;};struct node *creat(int n){ int i; node *head, *p, *tail; head = new node; head->next = NULL; tail=head; for(i=0; i<n; i++) { p=new node; cin>>p->data; p->next=NULL; tail->next=p; tail=p; } return head;}struct node *merge(node *h1, node *h2){ struct node *p1, *p2, *tail; p1=h1->next; p2=h2->next; delete h2; //释放h2 tail=h1; while(p1 && p2) { if(p1->data < p2->data)//链上data值小的 { tail->next=p1; tail=p1; p1=p1->next; } else { tail->next=p2; tail=p2; p2=p2->next; } } if(p1) { tail->next=p1; } else { tail->next=p2; } return h1;}int main(){ int n, m; cin>>n>>m; int i; node *h1, *h2, *h3, *w; h1=creat(n); h2=creat(m); h3=merge(h1, h2); w=h3->next; for(i=0; i<n+m; i++) { if(i==0) { cout<<w->data; } else { cout<<" "<<w->data; } w=w->next; } cout<<endl; return 0;}
数组实现：
#include <iostream>#include <stdio.h>#include <string.h>using namespace std;int a[100];int b[100];int c[200], e=0;int main(){ int i, j; int n, m; scanf("%d %d", &n, &m ); for(i=0; i<n; i++) { scanf("%d", &a[i] ); } for(j=0; j<m; j++) { scanf("%d", &b[j] ); } i = 0; j = 0; while(i<n && j<m ) { if(a[i] <= b[j] ) { c[e++] = a[i] ; i++; } else { c[e++] = b[j]; j++; } } if(i==n && j<m) { while(j<m) { c[e++] = b[j]; j++; } } else if(j==m && i<n) { while(i<n) { c[e++] = a[i] ; i++; } } for(i=0; i<e; i++) { if(i==0) printf("%d", c[0] ); else printf(" %d", c[i] ); } printf("\n"); return 0;}
数据结构之 线性表---有序链表的归并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。