Question
【问题描述】
编制一个能演示将两个有序表合并为一个有序表的程序。
【基本要求】
已知递增有序线性表LA和LB,现将LA和LB合并到LC,LC也是递增有序的。
【测试数据】
LA=(3,5,8,11) LB=(2,6,8,9,11,15,20)
合并后的LC=(2,3,5,6,8,9,11,15,20)
#include<stdio.h>
#include<stdlib.h>
//构建线性表结构
typedef struct LNode *List;
struct LNode{
int data[1000];
int last;
};
//生成线性表
List createList(int arr[],int arrLen){
List L= (List)malloc(sizeof(struct LNode));
L->last=0;
for(int i=0;i<=arrLen;i++){
L->data[L->last]=arr[i];
L->last++;
}
return L;
}
//合并两个线性表
List mergeList(List L1,List L2){
List L = (List)malloc(sizeof(struct LNode));
L->last=0;
int j=0,k=0;
while(j<L1->last && k<L2->last){
if(L1->data[j]==L2->data[k]){
L->data[L->last]=L1->data[j];
j++;
k++;
}else if(L1->data[j]<L2->data[k]){
L->data[L->last]=L1->data[j];
j++;
}else{
L->data[L->last]=L2->data[k];
k++;
}
L->last++;
}
while(j<L1->last){
L->data[L->last]=L1->data[j];
j++;
L->last++;
}
while(k<L2->last){
L->data[L->last]=L2->data[k];
k++;
L->last++;
}
return L;
}
int main(void){
int a[100],b[100];
char temp;
int countA=0,countB=0;
printf("请输入第一个递增有序线性表: ");
while(scanf("%d%c",&a[countA],&temp),temp!='\n'){
countA++;
}
printf("请输入第二个递增有序线性表: ");
while(scanf("%d%c",&b[countB],&temp),temp!='\n'){
countB++;
}
List L1=createList(a,countA);
List L2=createList(b,countB);
List L = mergeList(L1,L2);
printf("合并后的线性表为: %d",L->data[0]);
for(int i=1;i<L->last;i++){
printf(" %d",L->data[i]);
}
}