C语言线性表顺序存储实现 - 归并排序算法

#include <stdio.h> #include <stdlib.h>

#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

typedef int ElemType; typedef int Status;

typedef struct{ ElemType *elem; int length; int listsize; }SqList;

Status InitList(SqList *L){ L->elem=(ElemType )malloc(LIST_INIT_SIZEsizeof(ElemType)); if (!L->elem) exit(OVERFLOW); L->length=0; L->listsize= LIST_INIT_SIZE; return OK; }

Status ListLength(SqList *L){ return L->length; }

Status ListInsert(SqList *L, int i, ElemType e) { 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]); for (p = &(L->elem[L->length]); p >= q; --p) *(p+1) = *p; *q = e; ++L->length; return OK; }

Status GetItem(SqList *L,int i,ElemType *e){ if ((i < 1) || (i > L->length)) return ERROR; *e = L->elem[i]; return OK; }

void Merge(SqList *La,SqList *Lb,SqList *Lc){ 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]; i++; } else{ Lc->elem[k] = Lb->elem[j]; j++; } k++; } while (i <= La->length){ Lc->elem[k] = La->elem[i]; i++; k++; } while (j <= Lb->length){ Lc->elem[k] = Lb->elem[j]; j++; k++; } Lc->length = k - 1; }

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

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); } 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;