线性表的归并题目（2015年03月23日）

线性表的归并题目（2015年03月23日）

线性表的归并

题目描述：已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列。

顺序存储实现

采用顺序存储形式，该程序还添加了归并以外的几个功能十二生肖排列顺序表2021图表十二生肖排列顺序表2021图表线性表的归并题目（2015年03月23日）线性表的归并题目（2015年03月23日），可供使用参考。

#include
#include
#define OK			1
#define ERROR		0
#define OVERFLOW	-1
#define LIST_SIZE   50
#define INCREACE    50
typedef struct {
	int* elem;
	int length;
	int Listsize;
}SqList;
typedef int Status;
Status InitList(SqList* L) {
	L->elem = (int*)malloc(LIST_SIZE * sizeof(int));
	if (!L->elem)exit(OVERFLOW);
	L->Listsize = LIST_SIZE;
	L->length = 0;
	return OK;
}
Status CreateList(SqList* L) {
	int n = 0;
	printf("构建线性表，输入元素个数:");
	scanf_s("%d", &n);
	printf("输入%d个元素!请输入:",n);
	for (int i = 0;i < n;i++) {
		scanf_s("%d", &L->elem[i]);
		L->length++;
	}
	printf("构建完成!");
	return OK;
}
Status Show(SqList L) {
	printf("线性表为:");
	if (L.length < 1) { printf("空表!");return ERROR; }
	for (int i = 0;i < L.length;i++) {
		printf("%d ", L.elem[i]);
	}
	printf("-----数组长度为:%d\n\n", L.length);
	return OK;
}
Status ListInsert(SqList* L, int p, int v) {
	if (p<1 || p>L->length + 1)exit(ERROR);
	if (L->length==L->Listsize) {
		printf("\n内存不足,增加内存!");
		int* new = NULL;
		new = (int*)realloc(L->elem, (L->Listsize + INCREACE) * sizeof(int));
		if (!new)exit(OVERFLOW);
		L->elem = new;
		L->Listsize += INCREACE;
	}
	for (int j = L->length;j >= p;j--) {
		L->elem[j] = L->elem[j - 1];
	}
	L->elem[p - 1] = v;
	L->length++;
	return OK;
}
Status ListDelete(SqList* L, int p, int* v) {
	if (p<1 || p>L->length)exit(ERROR);
	if (p > L->Listsize)exit(ERROR);
	*v = L->elem[p - 1];
	for (int j = p - 1;j < L->length - 1;j++) {
		L->elem[j] = L->elem[j + 1];
	}
	L->length--;
	return OK;
}
Status ListSearch_position(SqList L, int p) {
	if (p<1 || p>L.length)exit(ERROR);
	if (p > L.Listsize)exit(ERROR);
	printf("\n位置为%d的元素的值为:%d", p, L.elem[p - 1]);
	return OK;
}
Status ListSearch_value(SqList L, int v) {
	int i = 0;
	for (i = 0;i < L.length;i++) {
		if (L.elem[i] == v)
			return i + 1;
	}
	printf("\n未找到值为%d的元素", v);
	exit(ERROR);
}
Status ListClean(SqList* L) {
	int l = L->length;
	for (int i = 0;i < l;i++) {
		L->elem[i] = 0;
		L->length--;
	}
	printf("\n线性表清空!");
	return OK;
}
void MergeList(SqList La, SqList Lb, SqList* Lc) {
	//已知顺序线性表La和Lb的元素按值非递减排列
	//归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
	int* pa = La.elem;
	int* pb = Lb.elem;
	Lc->length = La.length + Lb.length;
	Lc->Listsize = Lc->length;
	Lc->elem = (int*)malloc(Lc->Listsize * sizeof(int));
	if (!Lc->elem)exit(OVERFLOW);//储存分配失败
	int* pc = Lc->elem;
	int* pa_last = La.elem + La.length - 1;
	int* pb_last = Lb.elem + Lb.length - 1;
	while (pa <= pa_last && pb <= pb_last) {	//归并
		if (*pa <= *pb)*pc++ = *pa++;
		else *pc++ = *pb++;
	}
	while (pa <= pa_last)*pc++ = *pa++;//插入La的剩余元素
	while (pb <= pb_last)*pc++ = *pb++;//插入Lb的剩余元素
}// MergeList_Sq
void main() {
	SqList La;
	SqList Lb;
	SqList Lc;
	InitList(&La);
	InitList(&Lb);
	InitList(&Lc);
	printf("表a,");
	CreateList(&La);
	Show(La);
	printf("表b,");
	CreateList(&Lb);
	Show(Lb);
	MergeList(La, Lb, &Lc);
	printf("归并后的");
	Show(Lc);
}

运行结果截图

链式存储实现

该程序中也包含了归并所用函数以外的其他链表操作十二生肖排列顺序表2021图表，可以供使用参考。

#include
#include
#define OK			1
#define ERROR		0
#define OVERFLOW	-1
typedef struct LNode{
	int data;
	struct LNode* next;
}LNode,* LinkList;
typedef int Status;
Status InitLinkList(LinkList* L) {
	*L = (LinkList)malloc(sizeof(LNode));
	if (!*L)exit(OVERFLOW);
	(*L)->next = NULL;
	return OK;
}
Status CreateLinkList_Tail(LinkList L) {
	//尾插法建立单链表
	int n = 0;
	LNode* q = L;
	printf("确认输入元素的个数:");
	scanf_s("%d", &n);
	printf("请输入%d个元素的值:", n);
	for (int i = 0;i < n;i++) {
		LNode* p = (LNode*)malloc(sizeof(LNode));
		if (!p)exit(OVERFLOW);
		scanf_s("%d", &p->data);
		p->next = NULL;
		q->next = p;
		q = p;
	}
	return OK;
}
Status CreateLinkList_Head(LinkList L) {
	//头插法建立单链表
	int n = 0;
	LNode* q = L;
	printf("确认输入元素的个数:");
	scanf_s("%d", &n);
	printf("请输入%d个元素的值:", n);
	for (int i = 0;i < n;i++) {
		LNode* p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->data);
		p->next = q->next;
		q->next = p;
	}
	return OK;
}
LNode* GetNode(LinkList L, int p) {
	//得到第p个位置的元素
	LNode* q = L;
	for (int i = 0;i < p;i++) {
		q = q->next;
	}
	return q;
}
Status LocateNode(LinkList L, int v) {
	//定位数值为v的元素在单链表中的位置
	LNode* p = L;
	int locate = 0;
	while (p != NULL && p->data != v) {
		p = p->next;
		locate++;
	}
	return locate;
}
Status LinkListLength(LinkList L) {
	int length = 0;
	LNode* p = L->next;
	while (p != NULL) {
		p = p->next;
		length++;
	}
	return length;
}
Status LinkListInsert(LinkList L, int p, int v) {
	//链表第p个位置插入一个元素
	if (!L)exit(ERROR);
	LNode* pr = GetNode(L, p - 1);//得到p位置前一个元素的位置
	LNode* new = (LNode*)malloc(sizeof(LNode));
	if (!new)exit(OVERFLOW);
	new->data = v;
	new->next = pr->next;
	pr->next = new;
	return OK;
}
Status LinkListDelete(LinkList L, int p, int* v) {
	//删除位置为p的元素，并返回其值
	if (!L)exit(ERROR);
	LNode* q = GetNode(L, p);//得到p位置前一个元素的位置
	LNode* qn = q->next;
	*v = q->data;
	q->data = qn->data;
	q->next = qn->next;
	free(qn);
	return OK;
}
Status Show(LinkList L) {
	if (!L)exit(ERROR);
	if (LinkListLength(L) < 1) { printf("\n链表为空表!");exit(ERROR); }
	LNode* p = L->next;
	printf("链表元素输出:");
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("-----链表长度为%d\n\n", LinkListLength(L));
	return OK;
}
LinkList MergeList(LinkList La, LinkList Lb) {
	LinkList Lc;
	LNode* pa;LNode* pb;LNode* pc;
	Lc = (LNode*)malloc(sizeof(LNode));
	if (Lc == NULL)exit(OVERFLOW);
	pa = La->next;
	pb = Lb->next;
	pc = Lc;
	while (pa && pb) {
		if (pa->data <= pb->data) {
			LNode* s = (LNode*)malloc(sizeof(LNode));
			if (s == NULL)exit(OVERFLOW);
			s->data = pa->data;
			pc->next = s;
			pc = s;
			pa = pa->next;
		}
		else {
			LNode* s = (LNode*)malloc(sizeof(LNode));
			if (s == NULL)exit(OVERFLOW);
			s->data = pb->data;
			pc->next = s;
			pc = s;
			pb = pb->next;
		}
	}
	while (pa != NULL) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		if (s == NULL)exit(OVERFLOW);
		s->data = pa->data;
		pc->next = s;
		pc = s;
		pa = pa->next;
	}
	while (pb != NULL) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		if (s == NULL)exit(OVERFLOW);
		s->data = pb->data;
		pc->next = s;
		pc = s;
		pb = pb->next;
	}
	pc->next = NULL;
	printf("归并函数调用!");
	return Lc;
}
void main() {
	LinkList La = NULL;
	LinkList Lb = NULL;
	LinkList Lc = NULL;
	InitLinkList(&La);
	InitLinkList(&Lb);
	InitLinkList(&Lc);
	printf("表a,");
	CreateLinkList_Tail(La);
	Show(La);
	printf("表b,");
	CreateLinkList_Tail(Lb);
	Show(Lb);
	Lc = MergeList(La, Lb);
	printf("归并后的");
	Show(Lc);
}

运行结果截图