编辑代码

/*------------------------------------------------------------
---------将两个顺序表合并为一个顺序表----------------
------------------------------------------------------------*/

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

/*---------顺序表类型定义（第71页） -------*/
#define maxsize 1024
typedef int datatype;

typedef struct {
	datatype data[maxsize]; //采用向量存储线性表，data[0]不用，从索引为1的data[1]开始使用
	int last;  //last是顺序表当前的长度
} sequenlist;

//声明函数原型
sequenlist *InitList();
int Insert(sequenlist *, datatype, int);
int Length(sequenlist *);
void merge(sequenlist *La, sequenlist *Lb, sequenlist *Lc);
void PrintList(sequenlist *);

int main() {
	int len_a = 6;
	int a[6] = {2, 4, 5, 6, 6, 9};
	int len_b = 4;
	int b[4] = {1, 3, 7, 8};
	sequenlist *La, *Lb, *Lc;
	La = InitList();
	Lb = InitList();
	Lc = InitList();
	int i, j;
	for (i = 0; i < len_a; i++) {
		La->data[i + 1] = a[i];
	}
	La->last = len_a;
	for (j = 0; j < len_b; j++) {
		Lb->data[j + 1] = b[j];
	}
	Lb->last = len_b;
	printf("顺序表La为：\n");
	PrintList(La);
	printf("顺序表Lb为：\n");
	PrintList(Lb);
	printf("合并后的顺序表Lc为：\n");
	merge(La, Lb, Lc);
	PrintList(Lc);
	Length(Lc);
	return 0;
}

/*------------------------------------------------------------
---------算法3.2 建立一个空顺序表（第72页）----------------
通过函数返回值将结果带回到主调函数
------------------------------------------------------------*/
sequenlist *InitList() {
//分配顺序表的动态存储空间，将表的长度置为0
	sequenlist *L = (sequenlist *)malloc(sizeof(sequenlist));
	L->last = 0;
	return L;
}

/*------------------------------------------------------------
---------算法3.3 顺序表中插入结点（第72页）----------------
在顺序表的第i个位置上插入一个新结点x
------------------------------------------------------------*/
int Insert(sequenlist *L, datatype x, int i) {
//将新结点插入顺序表的第i个位置。插入成功返回1；不成功返回0.
	int k;
	if (L->last >= maxsize - 1) {
		printf("表已满.\n");    //插入不成功返回0
		return 0;
	}

	if (i < 1 || i > L->last + 1) {
		printf("非法插入位置.\n");
		return 0;
	}

	for (k = L->last; k >= i; k--) {
		L->data[k + 1] = L->data[k]; //结点后移
	}
	L->data[i] = x; //插入到L->data[i]中。从data[1]开始存放，data[0]不用
	L->last++;   //表长度加1
	return 1;   //插入成功返回1
}

void merge(sequenlist *La, sequenlist *Lb, sequenlist *Lc) {
	int i, j, k, a, b;
	i = j = k = 1;
	while (i <= La->last && j <= Lb->last) {
		a = La->data[i];
		b = Lb->data[j];
		if ( a < b) {
			Insert(Lc, a, k++);
			i++;
		} else {
			Insert(Lc, b, k++ );
			j++;
		}
	}
	while (i <= La->last) {
		a = La->data[i];
		Insert(Lc, a, k++ );
		i++;
	}
	while (j <= Lb->last) {
		b = Lb->data[j];
		Insert(Lc, b, k++  );
		j++;
	}
}


void PrintList(sequenlist *L) { //输出顺序表
	int i;
	for (i = 1; i <= L->last; i++)
		printf("%5d", L->data[i]);
	printf("\n");
}

int Length(sequenlist *L) {  //求表长度
	printf("表长度为%d.\n", L->last);
	return L->last;
}