pex9_14.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <stdlib.h>
#pragma hdrstop

#include "link.h"

// insert item into an ordered linked list
template <class T>
void InsertOrder(LinkedList<T>& x, const T& item)
{
   // use the linked list traversal mechanism to locate the
   // insertion point
   for(x.Reset();!x.EndOfList();x.Next())
      if (item < x.Data())
         break;
         
   // insert item at the current list location
   x.InsertAt(item);
}

// search for elem in a linked list x. if found
// return True(1); otherwise, return False(0)
template <class T>
int Find(LinkedList<T>& x, const T& elem)
{
	for(x.Reset();!x.EndOfList();x.Next())
		if (x.Data() == elem)
			return 1;
	return 0;
}

// return the union of sets x and y represented by
// (ordered) linked lists
template <class T>
LinkedList<T> Union(LinkedList<T>& x, LinkedList<T>& y)
{
	// initialize u to be list x
	LinkedList<T> u = x;

	// add to u all the elements of y that are not in u
	for(y.Reset();!y.EndOfList();y.Next())
		if (!Find(u,y.Data()))
			InsertOrder(u,y.Data());

	// return the union
	return u;
}

// return the intersection of sets x and y represented by
// (ordered) linked lists
template <class T>
LinkedList<T> Intersection(LinkedList<T>& x, LinkedList<T>& y)
{
	// initialize i to be list x
	LinkedList<T> i = x;

	// delete all elements from i that are not in y
	// the resulting list i is the intersection
	// reset list i, since the traversal state of list y
	// will be assigned to i
	i.Reset();
	while(!i.EndOfList())
		if (!Find(y,i.Data()))
			i.DeleteAt();
		else
			i.Next();

	// return the union
	return i;
}

// write LinkedList object L to a stream
template <class T>
ostream& operator<< (ostream& ostr, LinkedList<T>& L)
{
	for(L.Reset();!L.EndOfList();L.Next())
		ostr << L.Data() << "  ";
	return ostr;
}		

void main(void)
{
	// linked lists representing sets A, B and their union
	// and intersection
	LinkedList<int> A, B, unionAB, interAB;
	// values in sets A and B 
	int alist[] = {1,2,5,8,12,33,55},
		blist[] = {2,8,10,12,33,88,99};

	// build sets A and B
	for(int i=0;i < 7;i++)
	{
		InsertOrder(A,alist[i]);
		InsertOrder(B,blist[i]);
	}

	// print sets A and B
	cout << "Set A: { " << A << '}' << endl;
	cout << "Set B: { " << B << '}' << endl;
		
	// compute the union and intersection of A and B
	unionAB = Union(A,B);
	interAB = Intersection(A,B);

	// print the results
	cout << "Union of A and B: { " << unionAB << '}' << endl;
	cout << "Intersection of A and B: { " << interAB << '}' << endl;
}

/*
<Run>

Set A: { 1  2  5  8  12  33  55  }
Set B: { 2  8  10  12  33  88  99  }
Union of A and B: { 1  2  5  8  10  12  33  55  88  99  }
Intersection of A and B: { 2  8  12  33  }
*/