C语言实现合并两个非递减的有序表、以及求两个线性表的并集

数据结构

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define NULL 0
int i,n,j,e;
typedef struct LNode {//定义链表的结构体
	int data;
	struct LNode* next;//定义LNode类型的指针next,并且next指针存放的是下一个结点的地址。
	//这个是根据结点的定义，每一个结点由数据域和指针域组成，而指针域存放的是下一个结点的地址。
}Lnode,*linklist;//Lnode是结构体的别名，*linklist是LNode类型的指针，存放的是结构体LNode的地址。

//1.单链表的初始化，建一个带头结点的空表
int InitList_L(linklist& L) {
	//先建立一个带头结点的单链表
	L = (linklist)malloc(sizeof(Lnode));//知道头指针就相当于知道整个单链表
	L->next = NULL;//让头结点的指针域为空，就表示一个空链表
	return OK;
}
//2.单链表的建立函数（头插法）
int CreateList_H(linklist& L, int n) {
	//请输入单链表的结点
	printf("\n请输入单链表的长度：");
	scanf("%d", &n);
	printf("\n请输入单链表的结点(从尾到头)：");
	//
	Lnode* p;
	for (i = n; i > 0; i--) {//插入n个结点就循环n次
		p = (Lnode*)malloc(sizeof(Lnode));//创建的新结点
		scanf("%d", &p->data);//输入元素值data
		p->next = L->next;//先让新结点的指针域指向新结点后面的结点的地址，这样新结点就跟后面的结点连起来了
		L->next = p;//再让新结点前面的结点的指针域指向新结点的地址p，这样新结点就跟前面的结点连起来了。
	}
	//遍历一下链表，让其展示出来
	printf("\n创建的单链表为：");
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	return 0;
}
//3.实现两个非递减有序表的合并函数(链表实现)
void MergeList_L(linklist& La, linklist& Lb,linklist& Lc) {
	Lnode* pa, *pb, *pc;
	pa = La -> next;//pa指向La链表的首元结点
	pb = Lb -> next;//pb指向Lb链表的首元结点
	Lc = pc = La;//用链表La的头结点来做Lc的头结点
	while (pa && pb) {//LaLb两个链表都不为空，就一直循环
		if (pa->data <= pb->data) {
			pc->next = pa;//就让pc->next指向pa,意思就是把这个pa放进Lc
			pc = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;//表示如果pa为非空，pc->next=pa;否则pc->next=pb;
	/*if (pa) {
		pc->next = pa;
	}else {
		pc->next = pb;
	}*/
	free(Lb);//释放Lb链表的头结点
	printf("\n合并后的链表为：");
	//pc在两个链表合并完成之后会到表尾，需要加一句pc = Lc->next 来让pc指向链表的首元结点，再进行遍历
	pc = Lc->next;//这一步是让pc指向首元结点，好进行遍历。
	while (pc) {
		printf("%d ", pc->data);
		pc = pc->next;
	}
}
//4.链表的取值函数
//取出L表中第i个元素的值，用e返回
int GetElem_L(linklist& L, int i, int &e) {
	/*printf("\n请输入要取出的元素序号：");
	scanf("%d", &i);*/
	Lnode* p;//定义一个Lnode类型的指针p，让它指向表L的首元结点
	p = L->next;
	j = 1;//再来一个计数器j
	while (p && j < i) {
		p = p->next;
		j++;
	}
	if (!p || j > i) {//第i个元素不存在，j > i是当输入的i是0 或者<0的数，输入的i非法
		return ERROR;
	}
	e = p->data;//第i个元素的data域用e返回
	return e;
}
//5.链表的查找函数
int LocateElem_L(linklist& L, int e) {
	//查找链表中值为e的数据元素，找的到就返回真，找不到就返回假
	//printf("\n请输入要查找的元素值：");
	//scanf("%d", &e);//scanf的&不要老是忘记
	Lnode* p;
	p = L->next;//让p指向首元结点
	while (p && p->data != e) {
		p = p->next;
	}
	if (!p) { 
		return ERROR;
	}
	else { return OK; }
}
//6.获取表长的函数
int GetListLength_L(linklist& L) {
	Lnode* p;
	j = 0;
	p = L->next;
	while (p) {
		p = p->next;
		j++;
	}
	return j;
	
}
//7.链表的插入函数
void InsertElem_L(linklist& L, int e) {
	//将元素e插入链表的最后一位
	/*printf("\n请输入要插入的值：");
	scanf("%d", &e);*/
	Lnode* s, *p;//s代表新结点
	p = L->next;//p指向首元结点

	s = (Lnode*)malloc(sizeof(Lnode));//生成新结点s
	s->data = e;
	
	for (i = 0; i < GetListLength_L(L)-1; i++) {//4改成表长（表中元素个数）-1
		p = p->next;
	}
	p->next = s;//此时p= s表示把新结点s接在p的后面。
	s->next = NULL;

	/*printf("\n插入后的表为：");

	p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}*/
	
};
//8.实现两个线性表的并集函数
void Union_L(linklist& La, linklist& Lb) {
	int La_length = GetListLength_L(La);
	int Lb_length = GetListLength_L(Lb);
	for (i = 1; i <=La_length; i++) {
		GetElem_L(La,i,e);
		if(!LocateElem_L(Lb,e)){
			InsertElem_L(Lb, e);
		}
	}
	Lnode* p;
	p = Lb->next;
	printf("\n合并后的链表为：");
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
}

int main() {
	linklist La, Lb,Lc;
	InitList_L(La);
	InitList_L(Lb);
	InitList_L(Lc);//初始化3个链表

	CreateList_H(La, n);
	//LocateElem_L(La, e);
	//GetListLength_L(La);
	//InsertElem_L(La, e);
	
	//GetElem_L(La, i, e);
	//printf("第%d个的元素为：%d", i, e);//这两行是测试取值函数GetElem_l();
	CreateList_H(Lb, n);//创建两个链表La和Lb.
	//Union_L(La, Lb);
	MergeList_L(La, Lb, Lc);
	return 0;
}