polynomial.cpp

多项式运算

#include <stdio.h>
#include <stdlib.h>

#include "slist.h"

void insert_data(list_t poly , node_t p_node)
{
	node_t p_temp;
	int n = 0 ;

	for (p_temp = poly->head ; p_temp != NULL ;)
	{
		if (p_temp->data->exp > p_node->data->exp)
			n++;
		else break;

		p_temp = p_temp->next;
	}

	insert_node(poly , n , p_node);
}

void kick_zero(list_t poly)
{
	node_t node_p;
	int i ;

	node_p = poly->head;

	for (i = 1 ;node_p != NULL ;i++)
	{
		if (node_p->data->coe == 0)
		{
			node_p = node_p->next;
			delete_node(poly , i);
			i--;
		}
		node_p = node_p->next;
	}
}

void format_list(list_t poly)
{
	node_t p_prev;
	node_t p_next;
	int count;

	p_prev = poly->head;
	p_next = p_prev->next;

	for (count = 2;p_next != NULL;)
	{
		if (p_prev->data->exp == p_next->data->exp)
		{
			p_prev->data->coe+= p_next->data->coe;
			delete_node(poly , count);
			p_next = p_prev->next;
			continue;
		}
		p_prev = p_next;
		p_next = p_prev->next;
		count++;
	}

	kick_zero(poly);
}

void fill_list(FILE *finput , list_t poly)
{
	int n , i ;
	data_t p_data;
	node_t p_node;

	fscanf(finput, "%d", &n);

	for (i = 0 ; i < n ; i++ )
	{
		p_data = (data_t) malloc(sizeof(data));
		
		if (p_data == NULL)
		{
			printf("Insert data  failed.");
			exit(1);
		}

		fscanf(finput, "%f %d", &(p_data->coe), &(p_data->exp));
		p_node = make_node(p_data);

		insert_data(poly , p_node);
	}

	format_list(poly);
}

node_t copy_node(node_t node1)
{
	node_t node2;
	data_t data_p;

	data_p = (data_t) malloc(sizeof(data));
	node2 = (node_t) malloc(sizeof(node));
	
	node2->data = data_p;
	node2->data->coe = node1->data->coe;
	node2->data->exp = node1->data->exp;
	node2->next = NULL;

	return node2;
}

list_t poly_add(list_t poly_1, list_t poly_2)
{
	list_t poly_sum;
	node_t p1_node ,p2_node ;
	node_t p_temp;

	poly_sum = init_list();

	p1_node = poly_1->head;
	p2_node = poly_2->head;

	for (; (p1_node != NULL) && (p2_node != NULL) ;)
	{
		if (p1_node->data->exp > p2_node->data->exp)
		{
			p_temp = copy_node(p1_node);
			insert_data(poly_sum ,p_temp);
			p1_node = p1_node->next;
		}
		else
		{
			p_temp = copy_node(p2_node);
			insert_data(poly_sum ,p_temp);
			p2_node = p2_node->next;
		}
	}

	if (p1_node == NULL)
	{
		while(p2_node != NULL)
		{
			p_temp = copy_node(p2_node);
			insert_data(poly_sum ,p_temp);
			p2_node = p2_node->next;
		}
	}
	else{
		while(p1_node != NULL)
		{
			p_temp = copy_node(p1_node);
			insert_data(poly_sum ,p_temp);
			p1_node = p1_node->next;
		}
	}
	format_list(poly_sum);

	return poly_sum;
}

void get_oppo(list_t poly)
{
	node_t node_p;

	for (node_p = poly->head; node_p != NULL;)
	{
		node_p->data->coe = -1 * (node_p->data->coe);
		node_p = node_p->next;
	}
}

list_t poly_mul(list_t poly_1, list_t poly_2)
{
	list_t poly_dif;

	get_oppo(poly_2);
	poly_dif = poly_add(poly_1 , poly_2);
	get_oppo(poly_2);

	return poly_dif;
}

void out_data(FILE *foutput , list_t poly)
{
	int i;
	node_t node_p;

	node_p = poly->head;

	fprintf(foutput, "%d\n",poly->len);
	for (i = 0 ; i < poly->len ;i++)
	{
		fprintf(foutput, "(%g*x^%d)", node_p->data->coe , node_p->data->exp);
		if (i != (poly->len - 1))
			fprintf(foutput, "+");
		node_p = node_p->next;
	}

	fprintf(foutput, "\n");
}