C语言顺序表合并算法实现及优化

#include <stdio.h> #include <stdlib.h> #define MAX_LIST_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量

#define OK 1 #define OVERFLOW 0 typedef int Status;

typedef struct { int *elem; int length; int listsize;

} SqList;

Status InitList(SqList& L, int length, int listsize) { L.elem = (int *)malloc(sizeof(int) * listsize); L.length = length; L.listsize = listsize; if (!L.elem) { exit(OVERFLOW); } return OK; }

Status MergeList_Sq(SqList La, SqList Lb, SqList& Lc) // 已知顺序线性表La和Lb的元素按非递减排列 // 归并La，Lb得到新的顺序性表Lc，Lc的元素也按非递减排列 { int length1, length2; length1 = La.length; length2 = Lb.length; int i, j, k; int ai, bj; i = j = 0; k = 0;

while (i < length1 && j < length2) // 归并 
{
	ai = La.elem[i];
	bj = Lb.elem[j];
	if (ai <= bj)
	{
		Lc.elem[k] = ai;
		i++;
	}
	else
	{
		Lc.elem[k] = bj;
		j++;
	}
	k++;
}

while (i < length1)
{
	Lc.elem[k] = La.elem[i];
	i++;
	k++;
} // 插入La的剩余元素 
while (j < length2)
{
	Lc.elem[k] = Lb.elem[j];
	j++;
	k++;
} // 插入Lb的剩余元素 
Lc.length = k;
return OK;

} // MergeList_Sq

int main() { SqList La, Lb, Lc; int length1, length2; // 输入第一个顺序表 int i; printf("请输入第一个顺序表的长度：\n"); scanf("%d", &length1); if (!InitList(La, length1, MAX_LIST_SIZE)) { printf("La初始化出错！！！"); return 0; } printf("请输入第一个顺序表的序列值：\n"); for (i = 0; i < length1; i++) { scanf("%d", &La.elem[i]); } // 输入第二个顺序表 int j; printf("请输入第二个顺序表的长度：\n"); scanf("%d", &length2); if (!InitList(Lb, length2, MAX_LIST_SIZE)) { printf("Lb初始化出错！！！"); return 0; } printf("请输入第二个顺序表的序列值：\n"); for (j = 0; j < length2; j++) { scanf("%d", &Lb.elem[j]); } /// if (!InitList(Lc, length1 + length2, MAX_LIST_SIZE)) { printf("Lc初始化出错！！！"); return 0; } if (!MergeList_Sq(La, Lb, Lc)) { printf("顺序表合并出错！！！"); return 0; } int k; printf("合并后的顺序表Lc为："); for (k = 0; k < Lc.length; k++) { printf("%d ", Lc.elem[k]); } /// 释放内存 free(La.elem); free(Lb.elem); free(Lc.elem); return 0; }