题目描述
已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则
LC=(2,3,6,6,8,8,9,11,11,15,20)
算法描述如下:
从上述问题要求可知,LC中的数据元素或是LA中的数据元素,或是LB中的数据元素,则只要先设LC为空表,然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列,可设两个指针 i 和 j 分别指向LA和LB中某个元素,若设 i 当前所指的元素为 a,j 所指的元素为 b,则当前应插入到 LC 中的元素 c 为 c = a < b ? a : b显然,指针 i 和 j 的初值均为1(实际写代码时往往是从 0 开始的),在所指元素插入 LC 之后,在 LA 或者 LB 中顺序后移。上述归并算法如下图:
图:有序列表有序插入算法
输入格式
有多组测试数据,每组测试数据占两行。第一行是集合A,第一个整数m(0<=m<=100)代表集合A起始有m个元素,后面有m个非递减排序的整数,代表A中的元素。第二行是集合B,第一个整数n(0<=n<=100)代表集合B起始有n个元素,后面有n个非递减排序的整数,代表B中的元素。每行中整数之间用一个空格隔开。
输出
每组测试数据只要求输出一行,这一行含有 m+n 个来自集合 A 和集合B 中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。
样例输入
4 3 5 8 11
7 2 6 8 9 11 15 20
样例输出
2 3 5 6 8 8 9 11 11 15 20
#include<iostream> #include<malloc.h>/* malloc()等 */ #include<stdio.h> /* EOF(=^Z或F6),NULL */ using namespace std; #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */ typedef int ElemType; typedef int Status; typedef struct LIST { ElemType *elem; int length; int listsize; }Sqlist; Status SetList (Sqlist *L) { (*L).elem= (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!(*L).elem) return ERROR ; (*L).length=0; (*L).listsize=LIST_INIT_SIZE; return OK; } int ListLength (Sqlist L) { return L.length; } void PrintList(Sqlist L) { ElemType *q; int i; q=L.elem; for(i=0;i<L.length;i++,q++) if(i!=0) cout<<' '<<*q; else cout<<*q; cout<<endl; } int FindInList(Sqlist L,ElemType e) { int i; for(i=0;i<L.length;i++) if(L.elem[i]>=e) break; return (i+1); } Status InList(Sqlist *L,int i,ElemType e) { if(i<1||i>(*L).length+1) return ERROR; if((*L).length>=(*L).listsize) { ElemType *newbase; newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) return ERROR ; (*L).listsize+=LISTINCREMENT; (*L).elem=newbase; } ElemType *q,*p; q=(*L).elem+i-1; p=(*L).elem+(*L).length-1; for(;p>=q;p--) *(p+1)=*p; *q=e; (*L).length++; return OK; } int main() { int i,m,n,a[110],b[110],j; while(cin>>n) { for(i=0;i<n;i++) cin>>a[i]; cin>>m; for(i=0;i<m;i++) cin>>b[i]; struct LIST La; SetList(&La); for(i=0;i<n;i++) InList(&La,i+1,a[i]); for(i=0;i<m;i++) { j=FindInList(La,b[i]); InList(&La,j,b[i]); } PrintList(La); } }