pex9_10.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "link.h"

struct Term
{
	double coeff;
	int power;
};

// stream input of a Term record
istream& operator>> (istream& istr, Term& z)
{
	// read whitespace separated coefficient and power
	istr >> z.coeff >> z.power;

	return istr;
}

// stream ouptut of a Term record
ostream& operator<< (ostream& ostr, const Term& z)
{
	// output the coefficient
	ostr << z.coeff;

	// if the power is 2 or more, format is "coeff*x^power"
	if (z.power >= 2)
		ostr << "*x^" << z.power;
	else
	// if power is 1, format is "coeff*x"
	if (z.power == 1)
		ostr << "*x";
	// if z.power is 0, output coefficient only

	return ostr;
}

// insert Term item into a list in descending order
// of power
void InsertOrder(LinkedList<Term>& f, const Term& item)
{
   // use the linked list traversal mechanism to locate the
   // insertion point
   for(f.Reset();!f.EndOfList();f.Next())
      if (item.power > f.Data().power)
         break;
         
   // insert item at the current list location
   f.InsertAt(item);
}

// print the polynomial represented by list f
void PrintPoly(LinkedList<Term>& f)
{
	Term t;
	
	// if list f is empty, return
	if (f.ListEmpty())
		return;
		
	// start printing at first term
	f.Reset();
	// output first term
	cout << f.Data();
	
	// output remaining terms in the polynomial
	for(f.Next();!f.EndOfList();f.Next())
		// if current term has negative coefficient, output
		// format is " -  abs(coeff)*x^power"
		if (f.Data().coeff < 0)
		{
			t = f.Data();
			t.coeff = -t.coeff;
			cout << " - " << t;
		}
		else
			// if current term has positive coefficient, output
			// format is " +  coeff*x^power"
			cout << " + " << f.Data();
}

// compute x^n
double Power(double x, int n)
{
	double product = 1.0;
	
	for(int i=0;i < n;i++)
		product *= x;

	return product;
}

// evaluate the polynomial represented by f at the value x
double Poly(LinkedList<Term>& f, double x)
{
	double value = 0.0;
	Term t;

	// cycle through the list and add up the terms
	for(f.Reset();!f.EndOfList();f.Next())
	{
		t = f.Data();
		value += t.coeff * Power(x,t.power);
	}
	return value;
}

void main(void)
{
	// f represents the polynomial
	LinkedList<Term> f;
	Term t;
	// evaluate the polynomial for these values of x
	double xvals[] = {0.5, -1.5, 1.0};

	// read a term of the polynomial
	cin >> t;
	
	// insert t into f and read a new term. terminate
	// when you read a coefficient of 0 
	while(t.coeff != 0.0)
	{
		InsertOrder(f,t);
		cin >> t;
	}

	// print the polynomial
	PrintPoly(f);
	cout << endl;

	// evaluate the polynomial at xvals[0]..xvals[2]
	for(int i=0;i < 3;i++)
		cout << Poly(f,xvals[i]) << "  ";
	cout << endl;
}

/*
<Run>

2 5
-12 4
3 3
-1 2
5 1
3 0
0 0
2*x^5 - 12*x^4 + 3*x^3 - 1*x^2 + 5*x + 3
4.9375  -92.8125  0
*/