pex9_9.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "link.h"

struct IntEntry
{
	int value;
	int count;
};

// two IntEntry records are equal if the values fields agree
int operator== (const IntEntry &a, const IntEntry &b)
{
	return a.value == b.value;
}
	
// stream output of an IntEntry record
ostream& operator<< (ostream& ostr, const IntEntry& factor)
{
	// just output the value if the count is 1
	if (factor.count == 1)
		cout << factor.value;
	else
	// if count > 1, output in format value * value * ... * value
	{
		for(int i=0;i < factor.count-1;i++)
			cout << factor.value << " * ";
		cout << factor.value;
	}
	return ostr;
}

void LoadPrimes(LinkedList<IntEntry> &L, int n)
{
	// initially test for prime factor 2
	int i = 2;
	// count of the repeats of the current prime
	int count =0;
	IntEntry  X;

	// loop until all the prime factors are found
	do
		// if i divides n, it is a prime factor
		if (n % i == 0)
		{
			// increment count for this factor and
			// divide it out of n. keep trying i
			count++;
			n = n/i;
		}
		else
		{
			// if count > 0, then i is a prime factor. insert
			// it and its count into the linked list
			if (count > 0)
			{
				X.value = i;
				X.count = count;
				L.InsertRear(X);
			}
			// reset count to 0 and increment i
			count = 0;
			i++;
		}
	// continue if n > 1 or count != 0. the latter condition
	// is tested to handle cases such as n = 4, where n=1 and
	// count = 2 after two iterations. we still need to append
	// a node to the linked list
	while (n > 1 || count != 0);
}

// print a linked list of prime factors
void PrintList(LinkedList<IntEntry>& L)
{	
	int i;
	
	for(i = 0, L.Reset();!L.EndOfList();L.Next(),i++)
	{
		// all but the first factor is preceeded by "*"
		if (i != 0)
			cout << " * ";
		cout << L.Data();
	}
}

// multiply the factors and return the value of the number
int Product(LinkedList<IntEntry>& L)
{
	int prod = 1, i;
	
	for(L.Reset();!L.EndOfList();L.Next())
		for(i=0;i < L.Data().count;i++)
			prod *= L.Data().value;
			
	return prod;
}
		
LinkedList<IntEntry>& CommonPrimes(LinkedList<IntEntry> &L,
								LinkedList<IntEntry> &M)
{
	// build the common primes in *commonList and return
	// a reference to this list
	LinkedList<IntEntry> *commonList = new LinkedList<IntEntry>;
	IntEntry X;
	
	// while traversing L, search M and build *commonList
	L.Reset();
	while (!L.EndOfList())
	{
		// go to the start of M and search for L.Data() in M
		M.Reset();
		while (!M.EndOfList())
			if (L.Data() == M.Data())
			{
				// a prime occurs in both lists. insert it in the
				// rear of *commonList with count field the minimum of
				// the count fields from L and M
				X.value = (L.Data()).value;
				X.count = ((L.Data()).count <= (M.Data()).count) ? 
							(L.Data()).count : (M.Data()).count;
				commonList->InsertRear(X);
				break;
			}
			else
				M.Next();
		L.Next();
	}
	
	// if there are no common primes, return a linked list having
	// a value of 1 and count 1. in this case the numbers represented
	// by the two linked lists are "relatively prime"
	if (commonList->ListEmpty())
	{
		X.value = 1;
		X.count = 1;
		commonList->InsertFront(X);
	}
	
	// return a reference to commonList
	return *commonList;
}
		
void main(void)
{
	LinkedList<IntEntry> L, M, N;
	int  a, b;
	
	cout << "Enter integers a and b: ";
	cin >> a >> b;
	LoadPrimes(L,a);
	LoadPrimes(M,b);
	
	// print the list of factors for a and b
	cout << a << " = ";
	PrintList(L);
	cout << endl << b << " = ";
	PrintList(M);
	cout << endl;
	
	// N contains all the common primes in the prime factorization
	// of a and b
	N = CommonPrimes(L,M);
	// print N
	cout << "GCD(" << a << ", " << b << ") = ";
	PrintList(N);
	// if the GCD is the product of two or more primes,
	// print the product
	if (N.ListSize() > 1)
		cout << " = " << Product(N);
	cout << endl;
}

/*
<Run #1>

Enter integers a and b: 18 60
18 = 2 * 3 * 3
60 = 2 * 2 * 3 * 5
GCD(18, 60) = 2 * 3 = 6

<Run #2>

Enter integers a and b: 18 35
18 = 2 * 3 * 3
35 = 5 * 7
GCD(18, 35) = 1
*/