11_2_2.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Node
{
	int data;
	Node *next;
};

void Intersect(Node *a, Node *b)
{
	Node *pre	= a;
	Node *p		= a->next;
	Node *q		= b->next;
	Node *tmp;
	while (p && q)
	{
		if (p->data > q->data)
		{
			tmp			= p;
			pre->next	= p->next;
			p			= pre->next;
			delete tmp;
		}
		else if (p->data < q->data)
			q = q->next;
		else
		{
			p	= p->next;
			pre	= pre->next;
			q	= q->next;
		}
	}
	// 删除a中未比较过的元素
	while (p)
	{
		tmp			= p;
		pre->next	= p->next;
		p			= pre->next;
		delete tmp;
	}
}

void Union(Node *a, Node *b)
{
	Node *pre	= a;
	Node *p1	= a->next;
	Node *p2	= a->next->next;
	Node *q		= b->next;
	Node *tmp;
	while (q && p2)
	{
		if (p1->data == q->data || p2->data == q->data)
		{
			pre	= pre->next;
			p1	= p1->next;
			p2	= p2->next;
			q	= q->next;
		}
		else if (p1->data > q->data && q->data > p2->data)
		{
			tmp			= new Node;
			tmp->data	= q->data;
			tmp->next	= p2;
			p1->next	= tmp;
			pre			= pre->next->next;
			p1			= p1->next->next;
			p2			= p2->next;
			q			= q->next;
		}
		else if (p1->data < q->data)
		{
			tmp			= new Node;
			tmp->data	= q->data;
			tmp->next	= p1;
			pre->next	= tmp;
			q			= q->next;
			pre			= pre->next;
		}
		else // p2->data > q->data
		{
			tmp			= new Node;
			tmp->data	= q->data;
			tmp->next	= p2->next;
			p2->next	= tmp;
			pre			= pre->next;
			p1			= p1->next;
			p2			= p2->next;
		}
	}
	if (q)
		p1->next = q;
}

void Difference(Node *a, Node *b)
{
	Node *pre	= a;
	Node *p		= a->next;
	Node *q		= b->next;
	Node *tmp;
	while (p && q)
	{
		if (q->data > p->data)
		{
			q = q->next;
		}
		else if (q->data < p->data)
		{
			p	= p->next;
			pre	= pre->next;
		}
		else
		{
			tmp		= p;
			pre->next	= p->next;
			p		= p->next;
			delete tmp;
			q		= q->next;
		}
	}
}

void PrintList(Node *a)
{
	Node *p = a->next;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

void main()
{
	cout << "请输入一列降序数，输入#结束：" << endl;

	int data[MAX_SIZE];
	int i = 0;
	char c[8];
	while (c[0] != '#')
	{
		cin >> c;
		if (c[0] != '#')
			data[i] = atoi(c);
		i++;
	}
	int n1			= i - 1;

	cout << "请再输入一列降序数，输入#结束：" << endl;

	int data2[MAX_SIZE];
	i = 0;
	c[0] = '0';
	while (c[0] != '#')
	{
		cin >> c;
		if (c[0] != '#')
			data2[i] = atoi(c);
		i++;
	}
	int n2			= i - 1;

	// Main program.

	Node *a			= new Node;
	Node *b			= new Node;
	Node *aSolid	= a;
	Node *bSolid	= b;
	Node *tmp;
	for (i = 0; i < n1; i++)
	{
		tmp			= new Node;
		tmp->data	= data[i];
		a->next		= tmp;
		a			= a->next;
	}
	a->next = NULL;
	for (i = 0; i < n2; i++)
	{
		tmp			= new Node;
		tmp->data	= data2[i];
		b->next		= tmp;
		b			= b->next;
	}
	b->next = NULL;
	cout << "集合A的元素为：";
	PrintList(aSolid);
	cout << endl << "集合B的元素为：";
	PrintList(bSolid);
	cout << endl;
	
	int find;
	cout << "请输入命令，1为求交集，2为求并集，3为求差集：" << endl;
	cin >> find;
	switch (find)
	{
	case 1:
		Intersect(aSolid, bSolid);
		cout << "A∩B为：";
		PrintList(aSolid);
		break;
	case 2:
		Union(aSolid, bSolid);
		cout << "A∪B为";
		PrintList(aSolid);
		break;
	case 3:
		Difference(aSolid, bSolid);
		cout << "A－B为：";
		PrintList(aSolid);
		break;
	}
}