whiteblue/자료구조다항식구하기

No older revisions available

~cpp 
#include <iostream>
#include <vector>

using namespace std;

#define MAX 10000;

typedef struct poly_node * poly_pointer;

struct poly_node {
	int coef;
	int expon;
	poly_pointer link;	
};

poly_pointer pread();
poly_pointer pmult (poly_pointer a, poly_pointer b);
void pwrite (poly_pointer a);
int countNode(poly_pointer a);

int count_ = 0;

int main()
{
	poly_pointer a,b,c,d;

	a = pread();
	b = pread();
	pwrite(a);
	pwrite(b);
	c = pmult(a,b);
	pwrite(c);
	d=pmult(a,c);
	pwrite(d);

	return 0;
}

poly_pointer pread()
{
	int preExpon = MAX;
	int tempCoef;
	int tempExpon;

	poly_pointer result = new poly_node;
	poly_pointer temp;
	poly_pointer rear;
	temp = result;

	while (true)
	{
		cout << "coef, expon 을 입력하시오. 종료하려면 (0 0)을 입력 (예 : coef expon ): ";

		cin >> tempCoef;
		cin >> tempExpon;

		if ( tempCoef == 0 && tempExpon == 0 )
		{
			cout << "End" << endl;
			delete result;

			rear->link = NULL;

			break;
		}

		if (tempExpon >= 0 && tempExpon < preExpon)
		{
			result->coef = tempCoef;
			result->expon = tempExpon;

			preExpon = tempExpon;

			rear = result;

			result->link = new poly_node;

			result = result->link;

		}
		else
		{
			cerr << "다시 입력하시오." << endl;
		}

	}

	return temp;
}

poly_pointer pmult (poly_pointer a, poly_pointer b)
{
	int countnodeA = 0;
	int countnodeB = 0;

	poly_pointer ptemp = b;

	poly_node temp;

	count_ = 0;
	countnodeA = countNode(a);

	count_ = 0;
	countnodeB = countNode(b);

	vector <poly_node> v;

	for (int i = 0 ; i < countnodeA ; i++)
	{
		for (int j = 0 ; j < countnodeB ; j++)
		{
			temp.coef = a->coef * b->coef;
			temp.expon = a->expon + b->expon;

			v.push_back(temp);
			
			b = b->link;
		}
		a = a->link;
		b = ptemp;
	}		// 각 노드를 나누기

	for (i = 0 ; i < v.size()-1 ; i++)
	{
		for (int j = i ; j < v.size()-1 ; j++)
		{
			if ( v[j].expon < v[j+1].expon )
			{
				temp = v[j+1];
				v[j+1]  = v[j];
				v[j] = temp;
			}
		}
	}

	for (i = 0 ; i < v.size()-1 ; i++)
	{
		if ( v[i].expon == v[i+1].expon )
		{
			v[i].coef += v[i+1].coef;
			v.erase(v.begin() + i+1);
			i--;
		}
	}

	poly_pointer result = new poly_node;
	poly_pointer tempResult;
	poly_pointer rear;

	tempResult = result;

	for (i = 0 ; i < v.size() ; i++)
	{
		result->coef = v[i].coef;
		result->expon = v[i].expon;
		rear = result;

		result->link = new poly_node;
		result = result->link;
	}

	rear->link = NULL;

	return tempResult;
}

void pwrite(poly_pointer a)
{
	if ( a->link == NULL ) {

		cout << a->coef << "X^" << a->expon << endl;
		return;
	}

	cout << a->coef << "X^" << a->expon << " + ";

	pwrite(a->link);
}

int countNode(poly_pointer a)
{

	if ( a != NULL )
	{
		count_++;
		countNode(a->link);
	}
	else
	{
		return count_;
	}
}