数据结构：两个顺序表合并算法

1.问题描述

将a，b两个有序顺序表进行合并，放在c顺序表当中，并且要保证顺序表c仍然有序。

2.解题思路

因为a，b两个顺序表是有序的，所有可以从前往后一起查找a，b当中最小的一个数值，放入到c中。

如果遍历到最后，a遍历完了，b没有遍历完，就把b剩下的放入c中；反之，b遍a没有遍历完，就把a剩下的放入c中。

3.实现代码

#include #include #define MAXSIZE 100typedef int ElemType;typedef struct {//顺序表的结构ElemType *data;int length;int listsize;}List;int InitList(List *L)//初始化顺序表{L->data = (ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!(L->data))exit(0);L->length=0;L->listsize=MAXSIZE;return 1;}void CreatList(List *L)//创建一个顺序表{int i;printf("请输入测试的数据总数：\n");scanf("%d",&L->length);printf("请输入测试的数据：\n");for(i=0;ilength;i++)scanf("%d",&L->data[i]);}void Printf(List *L)//打印顺序表中的值{int i;if(L->length==0){printf("顺序表为空！");return ;}elsefor(i=0;ilength;i++)printf("%d ",L->data[i]);printf("\n"); }void MergeList(List *a,List *b,List *c){//合并两个顺序表放入c中int i=0;int j=0;int k=0;int La_len=a->length;int Lb_len=b->length;c->length=a->length+b->length;while((i<La_len)&&(jdata[i]data[j])//如果a当前的值小于b{c->data[k]=a->data[i];//c放入当前a的值i++;//a,c都往后移一位k++;}else{//如果a当前值大于等于bc->data[k]=b->data[j]; //c放入当前b的值j++;//b,c都往后移一位k++;}}while(idata[k]=a->data[i];k++;i++;}while(jdata[k]=b->data[j];k++;j++;}}int main(){List *L1;List*L2;List*L3;L1 = (List*) malloc(sizeof(List));L2 = (List*) malloc(sizeof(List));L3 = (List*) malloc(sizeof(List));InitList(L1);InitList(L2);CreatList(L1);CreatList(L2);printf("输入顺序表A：");Printf(L1);printf("输入顺序表B：");Printf(L2);L3->data = (ElemType*)malloc(MAXSIZE*sizeof(ElemType));MergeList(L1,L2,L3);getchar();printf("输入顺序表C：");Printf(L3);getchar();return 0;}