C++ 大作业 题目四

//题目四：要求利用带头结点的单链表，根据所提供的源代码，实现两个集合的并、交、差运算。
//【具体功能描述】
//1)要求用带头结点的单链表存储两个集合中的元素和最终的结果。
//2)集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即使得链表中没有重复数据。
//3)显示两个集合的内容及其并集、交集和差集的内容。
//4)要求不改变原来的集合，并集、交集和差集分别另外存放。
#include <iostream>
#include <string>
#include <malloc.h>
using namespace std;

struct Lnode {
	int data;
	struct Lnode* next;
};
typedef struct Lnode LinkList;
//struct Lnode LinkList;
void Disp(LinkList *Link) {
	LinkList *p = Link->next;
	//cout <<  "集合中的元素：" << endl;
	while (p!=NULL)
	{   
		cout  << p->data << " ";
		p= p->next;
	}
	cout << endl;
}


void DestroyList(LinkList *&Link) {
	LinkList *p ,*pre=Link;
	while (pre!=NULL)
	{
		p = pre->next;
		pre = NULL;
		delete pre;
		free(pre);

		pre = p;
		
	}
	Link = NULL;
}

LinkList* CreateListF() {   //创建链表
	LinkList* header,* a,* b,* c;
	int n;
	int data;
	cout << "创建一个链表，大小为：" << endl;
	cin >> n;
	header = (LinkList*)malloc(sizeof(LinkList));
	header->next = NULL;//首先先置空
	a = header;
	cout << "请对链表进行输入：" << endl;
	for (int i = 0, k=0; i < n; i++,k++) {
		int flag = 1;
		b = header->next;
		cin >> data;
		for (int j = 0; j < k; j++,b= b->next) {//如果当前输入的data与前面的链表内的数相同的话，舍去；反之创新节点
			if (data == b->data) {
				flag = 0;
				k--; //记录有多少个元素
				break;
			}
		}
		if (flag) {
			c = (LinkList*)malloc(sizeof(LinkList));
			c->data = data;
			a->next = c;
			a = c;
		}
	}
	a->next = NULL;
	return header;
}
LinkList* Combination(LinkList* &p,LinkList* &q) {  //简单合并
	LinkList  *a, *b,*Comb,*c,*d;
	Comb = (LinkList*)malloc(sizeof(LinkList));
	Comb->next = NULL;
	c = Comb;
	a = p;
	b = p->next;
	while (b!=NULL)
	{	
		d= (LinkList*)malloc(sizeof(LinkList));//
		a = b;
		d->data = a->data;//
		c->next = d; //
		c = d;//
		b = a->next;
	}
	
	c->next = q->next;

	//free(q);
	return Comb;
}
LinkList* Union(LinkList *&p) {   //并集
	LinkList *a = p->next, *b  , *c, *head , *d;
	//Disp(p);
	head  = (LinkList*)malloc(sizeof(LinkList));
	head->next = NULL;
	//int Len = getLength(p);
	d = head;
	while(a!=NULL) {
		int flag = 1;
		//cout << "调试：" << endl;
		//Disp(a);
		b = a->next;
		//Disp(b);
		while (b != NULL) {
			
			if (a->data == b->data) {
				flag = 0;
				//cout << b->data << "||";
			}
			if(flag==0) {
				//a = a->next;
				break;
			}
			b = b->next;
		}

			if (flag == 1) {
				c = (LinkList*)malloc(sizeof(LinkList));
				c->data = a->data ;
				d->next = c;
				d = c;
			}

			a = a->next;
	}
	d->next = NULL;
	return head;

}
void Subs(LinkList *L1, LinkList *L2, LinkList *&L3) {
	LinkList *a, *b, *c,*d;
	a = L1->next; 
	L3 = (LinkList *)malloc(sizeof(LinkList));
	L3->next = NULL;
	c = L3;
	while ( a!=NULL ) {
		int flag = 1;
		b = L2->next;
		while (b != NULL) {
			if (a->data == b->data) {
				flag = 0;
				//break;
			}
			if (flag == 0) {
				a = a->next;
				break;
			}
			b = b->next;

		}
		if (flag) {
			d = (LinkList *)malloc(sizeof(LinkList));
			d->data = a->data;
			c->next = d;
			c = d;
			a = a->next;
		}
		//cout << a->data;

	}
	c->next = NULL;

}

void InterSect(LinkList *L1, LinkList *L2, LinkList *&L3) {
	LinkList *a, *b, *c, *d;
	a = L1->next;
	L3 = (LinkList *)malloc(sizeof(LinkList));
	L3->next = NULL;
	c = L3;
	while (a != NULL) {
		b = L2->next;
		while (b != NULL) {
			if (a->data == b->data) {

				d = (LinkList *)malloc(sizeof(LinkList));
				d->data = a->data;
				c->next = d;
				c = d;
				a = a->next;
				break;
			}
			else {
				b = b->next;
			}
		}
		if (b == NULL)
			a = a->next;
		//cout << a->data;

	}
	c->next = NULL;

}

void Sort(LinkList *L1) {
	LinkList *a=L1->next, *b, *c;
	int temp = 0;
	while (a!=NULL)
	{
		b = a->next;
		while (b != NULL){
		if (a->data > b->data) {
			temp = a->data;
			a->data = b->data;
			b->data = temp;
		}
		b = b->next;
		}
		a = a->next;
	}
}


int getLength(LinkList *Link) {
	int Lenth = 0;
	LinkList *L = Link->next;
	while (L != NULL) {
		Lenth++;
		L = L->next;
	}
	return Lenth;
}

int main() {
	LinkList *ha,*ba,*ca,*da,*ea;
	ha = CreateListF();
	cout << "A集合：" << endl;
	Disp(ha);
	ba = CreateListF();
	cout << "B集合：" << endl;
	Disp(ba);
	cout << "A的有序集合：" << endl;
	Sort(ha);
	Disp(ha);
	cout << "B的有序集合：" << endl;
	Sort(ba);
	Disp(ba);
	cout << "A、B集合相加：" << endl;
	ca = Combination(ha, ba);
	Disp(ca);

	cout << "A、B集合的并：" << endl;
	da=Union(ca);
	Disp(da);

	//DestroyList(ca);
	
	cout << "A、B集合的差：" << endl;
	Subs(ha, ba, ca);
	Disp(ca);

	cout << "A、B集合的交集：" << endl;
	InterSect(ha, ba, ca);
	Disp(ca);
	
	//int Len = getLength(ca);
	//cout << "合并后的长度：" << Len << endl;
	DestroyList(ha);
	DestroyList(ba);
	DestroyList(ca);
	DestroyList(da);
	
	system("pause");
	return 0;
}