算法2.2已知线性表LA和LB中的数据元素按值⾮递减有序排列，现要求将LA和
LB归并为⼀个。。。
数据结构（C语⾔版）严蔚敏吴伟民
算法2.2 已知线性表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,8,9,11,11,15,20)
说明：为了展⽰结果，代码加⼊线性表的抽象数据类型的全部构造，实际是UnionList函数达成该练习结果，因为该函数内需要调⽤抽象数据类型构造的其他函数，所以全部列出。
代码块：
#include<stdio.h>
#include<stdlib.h>
//Function result status code
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASALBE -1
#define OVERFLOW -2
//Status is the type of function whose value is the function result status code
typedef int Status;
typedef struct{
int*data;
int length;
}List;
void output(List *L);
Status InitList(List *L);
Status DestroyList(List *L);
Status ClearList(List *L);
Status ListEmpty(List *L);
Status ListLength(List *L);
Status GetElem(List *L,int i,int*e);
Status compare(List *a,int b);
Status LocateElem(List *L,int e, Status (*pfun)(List *ce,int num));
Status PriorElem(List *L,int cur_e,int*pre_e);
Status NextElem(List *L,int cur_e,int*next_e);
Status ListInsert(List *L,int i,int e);
Status ListDelete(List *L,int i,int*e);
Status visit(List *L);
Status ListTraverse(List *L, Status (*pfun)(List *ce));
void UnionList(List *La, List *Lb);
void MergeList(List *La, List *Lb, List *Lc);
void output(List *L){
int i;
printf("Result: ");
for(i=0; i<ListLength(L); i++)
printf("%d ", L->data[i]);
printf("\n");
printf("\n");
}
Status InitList(List *L){
L->data=(int*)malloc(30*sizeof(int));
if(!L)exit(OVERFLOW);
L->length=0;
return OK;
}//InitList
Status DestroyList(List *L){
free(L);
return OK;
}//DestroyList
Status ClearList(List *L){
int i;
for(i=0; i<=ListLength(L); i++){
if(L->data[i]!=0)
L->data[i]=0;
L->length--;
}
L->length--;
return OK;
}//ClearList
Status ListEmpty(List *L){
if(L->length!=0)
return FALSE;
else
return TRUE;
}//ListEmpty
Status ListLength(List *L){
return L->length;
}//ListLength
Status GetElem(List *L,int i,int*e){
int j;
for(j=0; j<ListLength(L); j++)
if(j==i-1){
e=&L->data[j];
break;
}
return*e;
}//GetElem
Status compare(List *a,int b){
int i, judge;
for(i=0, judge=0; i<ListLength(a); i++){
if(a->data[i]==b){
judge=1;
return TRUE;
break;
}
}
if(judge==0)
return FALSE;
}//compare
Status LocateElem(List *L,int e, Status (*pfun)(List *ce,int num)){ int i;
for(i=0; i<ListLength(L); i++){
if(L->data[i]==e){
return i+1;
break;
}
}
if(!pfun(L, e))
return0;
}//LocateElem
Status PriorElem(List *L,int cur_e,int*pre_e){
int i, judge;
for(i=0, judge=0; i<ListLength(L); i++){
for(i=0, judge=0; i<ListLength(L); i++){
if(i!=0&&cur_e==L->data[i]){
judge=1;
pre_e=&L->data[i-1];
break;
}
}
if(i==0||judge==0)
return ERROR;
else
return*pre_e;
}//PriorElem
Status NextElem(List *L,int cur_e,int*next_e){
int i, judge;
for(i=0, judge=0; i<ListLength(L); i++)
if(i!=ListLength(L)-1&&cur_e==L->data[i]){
judge=1;
next_e=&L->data[i+1];
break;
}
if(i==ListLength(L)-1||judge==0)
return ERROR;
else
return*next_e;
}//NextElem
Status ListInsert(List *L,int i,int e){
int j;
if(i<1||(i-1)>ListLength(L))return ERROR;
else{
for(j=ListLength(L); j>=i; j--)
L->data[j]=L->data[j-1];
L->length++;
L->data[j]=e;
return OK;
}
}
Status ListDelete(List *L,int i,int*e){
int j, temp;
if(i<0||i>ListLength(L))return ERROR;
temp=L->data[i];
for(j=i; j<ListLength(L)-1; j++)
L->data[j]=L->data[j+1];
L->length--;
e=&temp;
return*e;
}//ListDelete
Status visit(List *L){
int i, judge;
for(i=0, judge=0; i<ListLength(L); i++){
if(L->data[i]!=NULL)
judge=1;
else{
judge=0;
break;
}
}
if(judge==0)
return ERROR;
else
return OK;
}//visit
Status ListTraverse(List *L, Status (*pfun)(List *ce)){ if(pfun(L))
return TRUE;
else
return FALSE;
return FALSE;
}//ListTraverse
void UnionList(List *La, List *Lb){
La->length=ListLength(La);
Lb->length=ListLength(Lb);
int i, re,*el=NULL;
Status (*pfun)(List *ce,int num);
for(i=0; i<Lb->length; i++){
re=GetElem(Lb, i+1, el);
if(!LocateElem(La, re, compare))
printf("ListInsert Status: %d\n",ListInsert(La, La->length+1, re)); }
}//UnionList
void MergeList(List *La, List *Lb, List *Lc){
//La and LB are arranged in non decreasing order
printf("InitList Lc Status: %d\n",InitList(Lc));
int i=0, j=0, k=0;
La->length=ListLength(La);
Lb->length=ListLength(Lb);
int*ai=NULL,*bj=NULL, a, b;
while((i<La->length)&&(j<Lb->length)){
printf("GetElem ai: %d\n",GetElem(La, i+1, ai));
a=GetElem(La, i+1, ai);
printf("GetElem bj: %d\n",GetElem(Lb, j+1, bj));
b=GetElem(Lb, j+1, bj);
printf("Lc Length: %d\n", Lc->length);
if(a<=b){
k++;
printf("ListInsert ai Status: %d\n",ListInsert(Lc, k, a));
i++;
}
else{
k++;
printf("ListInsert bj Status: %d\n",ListInsert(Lc, k, b));
j++;
}
}
while(i<La->length){
printf("GetElem ai: %d\n",GetElem(La, i+1, ai));
a=GetElem(La, i+1, ai);
i++;
k++;
printf("ListInsert ai: %d\n",ListInsert(Lc, k, a));
}
while(j<Lb->length){
printf("GetElem bj: %d\n",GetElem(Lb, j+1, bj));
c语言listinsert函数b=GetElem(Lb, j+1, bj);
j++;
k++;
printf("ListInsert bj: %d\n",ListInsert(Lc, k, b));
}
output(Lc);
}//MergeList
int main()
{
List *Li=(List*)malloc(sizeof(List));
printf("InitList Li Status: %d\n",InitList(Li));
int i, n,*r=NULL;
printf("Enter List Li Length: ");
scanf("%d",&n);
printf("Enter %d numbers: ", n);
for(i=0; i<n; i++){
scanf("%d",&Li->data[i]);
Li->length++;
}
}
printf("ListLength: %d\n",ListLength(Li));
printf("ListEmpty Status: %d\n",ListEmpty(Li));
printf("GetElem: %d\n",GetElem(Li,3, r));
printf("LocateElem: %d\n",LocateElem(Li,13, compare)); printf("PriorElem %d\n",PriorElem(Li,16, r));
printf("NextElem: %d\n",NextElem(Li,2, r));
printf("ListInsert Status: %d\n",ListInsert(Li,1,1)); output(Li);
printf("ListDelete Status: %d\n",ListDelete(Li,2, r)); output(Li);
printf("ListTraverse Status: %d\n",ListTraverse(Li, visit));
List *Lb=(List*)malloc(sizeof(List));
printf("InitList Lb Status: %d\n",InitList(Lb));
int m;
printf("Enter List Lb length: ");
scanf("%d",&m);
printf("Enter %d numbers: ", m);
for(i=0; i<m; i++){
scanf("%d",&Lb->data[i]);
Lb->length++;
}
List *Lc=(List*)malloc(sizeof(List));
MergeList(Li, Lb, Lc);
printf("ClearList Status: %d\n",ClearList(Li));
printf("ListEmpty Status: %d\n",ListEmpty(Li));
printf("DestroyList Status: %d\n",DestroyList(Li)); system("pause");
return0;
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论