线性表顺序存储实现--归并算法详解

/*------------------------------------------------------- 【程序设计】

题目: 线性表的顺序存储实现--归并: 要求：
La：顺序存储结构的线性表，由小到大排序 Lb：顺序存储结构的线性表，由小到大排序 Lc：顺序存储结构的线性表，La与Lb归并，仍然是由小到大排序

函数列表: 线性表初始化：Status InitList_Sq(SqList *L); 求线性表长度：Status ListLength(SqList *L); 插入元素：Status ListInsert_Sq(SqList *L, int i, ElemType e); 两个线性表归并：void Merge(SqList *La,SqList *Lb,SqList *Lc); 获取某个位置的元素：Status GetItem(SqList *L,int i,ElemType *e); 销毁线性表：Status DestroyList(SqList L); 主函数：void main(); -------------------------------------------------------/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 20 #define LISTINCREAMENT 10 #include <stdio.h> #include <stdlib.h>

//线性表存储空间的分配增量 typedef int ElemType; //Status是函数的类型，其值是函数结果状态代码 typedef int Status;

typedef struct{ ElemType elem; / 线性表占用的数组空间。*/ int length; /线性表的长度/ int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位) }SqList;

//线性表初始化 Status InitList(SqList *L){
L->elem=(ElemType )malloc(LIST_INIT_SIZEsizeof(ElemType)); if (!L->elem) exit(OVERFLOW); //存储分配失败 L->length=0; //空表长度为0 L->listsize= LIST_INIT_SIZE; //初始存储容量 return OK; }

//求线性表长度 Status ListLength(SqList *L){ return L->length; }

//插入元素，C语言数组从第0个元素开始，此处下标从1开始 Status ListInsert(SqList *L, int i, ElemType e) { // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1 ElemType *p,*q,newbase; if (i<1 || i>L->length+1) return ERROR; // 插入位置不合法 if (L->length+1 >= L-> listsize){ newbase=(ElemType)realloc(L->elem++,(LIST_INIT_SIZE+LISTINCREAMENT)*sizeof(ElemType)); if(!newbase) return OVERFLOW;// 当前存储空间已满 L-> elem=newbase; L-> listsize+=LISTINCREAMENT; } q = &(L->elem[i]); // q 指示插入位置 for (p = &(L->elem[L->length]); p >= q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e; // 插入e ++L->length; // 表长增1 return OK; }

//获取某个位置的元素值 Status GetItem(SqList *L,int i,ElemType *e){ if ((i < 1) || (i > L->length)) return ERROR; *e = L->elem[i]; }

void Merge(SqList *La,SqList *Lb,SqList *Lc){

/**********Program**********/ 



int i=1,j=1,k=1; 
while(i<=La->length && j<=Lb->length){ 
    if(La->elem[i] <= Lb->elem[j]){ 
        Lc->elem[k++] = La->elem[i++]; 
    } 
    else{ 
        Lc->elem[k++] = Lb->elem[j++]; 
    } 
} 
while(i<=La->length){ 
    Lc->elem[k++] = La->elem[i++]; 
} 
while(j<=Lb->length){ 
    Lc->elem[k++] = Lb->elem[j++]; 
} 

Lc->length = La->length + Lb->length; 

}

Status DestroyList(SqList *L){ free(L); }

//主函数 int main(){ SqList *La,*Lb,*Lc; ElemType x,*e; int i,n,choice,position,flag;

La=(SqList *)malloc(sizeof(SqList)); 
Lb=(SqList *)malloc(sizeof(SqList)); 
Lc=(SqList *)malloc(sizeof(SqList)); 
    
InitList(La); 
InitList(Lb); 
InitList(Lc); 

printf("请输入La中的元素个数："); 
scanf("%d",&n); 
printf("请输入数据(数字):"); 
for(i=1;i<=n;i++){ 
    scanf("%d",&x); 
    ListInsert(La, i,x); 
} 


printf("请输入Lb中的元素个数："); 
scanf("%d",&n); 
printf("请输入数据(数字):"); 
for(i=1;i<=n;i++){ 
    scanf("%d",&x); 
    ListInsert(Lb, i,x); 
} 
    
// 归并La和Lb 
Merge(La,Lb,Lc); 
      
       
// 归并后的结果为 
printf("归并后的Lc的元素为：") ; 
for(i=1;i<ListLength(Lc);i++) 
    printf("%d ",Lc->elem[i]); 

DestroyList(La); 
DestroyList(Lb); 
DestroyList(Lc); 
return 0; 

}