HNCU1324: 算法2-2：有序线性表的有序合并

数据结构2.2线性表的顺序表示和实现 严蔚敏版 已知线性表 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 中顺序后移。上述归并算法如下图：

  图：有序列表有序插入算法 #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define INIT_List 100 #define INITCREMENT 10 #define OVERFLOW 0 #define N 100 typedef int ElemType; typedef int Status; typedef struct { ElemType *elem; int length; int listsize; }list; Status InitList(list *l) {//初始化线性表 l->elem = (ElemType*)malloc(INIT_List*sizeof(ElemType)); if(!l->elem)//存储分配失败 return ERROR; l->length = 0;//空表长度为0 l->listsize = INIT_List;//初始化存储容量 return OK; } Status InsertList(list *l,int e,int i) {//把e插入到线性表l中 //i 的合法值为1<= i<= l.lenghth+1 int *newbase,*p,*q; int j; if( i < 1|| i > l->length+1)//i值不合法 return ERROR; if(l->length >= l->listsize )//当存储空间已满，增加分配 { newbase = (ElemType*)realloc(l->elem,(l->listsize+INITCREMENT)*sizeof(ElemType)); if(!newbase)//存储分配失败 exit(OVERFLOW); l->elem = newbase;//新基址 l->listsize += INITCREMENT;//增加存储容量 } p = &(l->elem[i-1]);//p为插入位置 j = l->length ; for(q = &(l->elem[j-1]); q>= p; q--)//插入位置及元素后移 *(q+1) = *q; *p = e;//插入e l->length ++;//表长加1 return OK; } Status LengthList(list *l) {//返回线性表长度 return l->length ; } Status GetElem(list *l,int n,int *a) {//找到在线性表l中第n个位置的数 *a = l->elem[n-1]; return OK; } void Print(list *l) {//输出线性表中的元素 int i = 0; while(i < l->length) { printf("%d ",l->elem[i]); i ++; } printf("\n"); } Status MergeList(list *la,list *lb,list *lc) {//合并线性表 InitList(lc); int i,j,k; int la_len,lb_len; int a,b; i = j = k = 1; la_len = LengthList(la); lb_len = LengthList(lb); while(i <= la_len&&j <=lb_len )//la,lb均非空 { GetElem(la,i,&a); GetElem(lb,j,&b); if( a <= b) { InsertList(lc,a,k++); i++; } else { InsertList(lc,b,k++); j++; } } while(i <= la_len) { GetElem(la,i,&a); InsertList(lc,a,k++); i++; } while(j <= lb_len) { GetElem(lb,j,&b); InsertList(lc,b,k++); j++; } return OK; } int main() { int m,n; int i,j; list la,lb,lc; int a[N+10],b[N+10]; while(scanf("%d",&m)!=EOF) { j = 1; InitList(&la);//初始化线性表 la for( i = 1; i <= m; i++) { scanf("%d",&a[i]); InsertList(&la,a[i],j++);//建立线性表la } scanf("%d",&n); j = 1; InitList(&lb);//初始化线性表lb for( i = 1; i <= n; i ++) { scanf("%d",&b[i]); InsertList(&lb,b[i],j++);//建立线性表lb } MergeList(&la,&lb,&lc);//合并线性表 Print(&lc);//输出合并后的线性表 } return 0; }