多项式的规范化_数据结构_单链表_C语言实现

多项式的规范化，采用单链表，使用C语言实现，gcc调试通过。

 

//该程序是为了将无序的、不规范的多项式进行规范化而写的。
#include<stdio.h>
#include<stdlib.h>
#define N 8  //指明多项式数据项的数目

int GetLength();  //获得单链表的长度
void Print();  //打印出单链表的节点数据

typedef struct multinomialnode  //定义存储多项式数据项的节点的结构体
{
	int coefficient,power;  //定义系数和幂
	struct multinomialnode *next;
}node;

node *Create(int num)  //创建存储多项式的链表
{
	int i;
	node *head,*pointer,*tmp;
	
	head=(node*)malloc(sizeof(node));
	if(head!=NULL)	pointer=head;
	
	printf("请依次输入要处理的多项式元素的系数和幂：\n");
	for(i=0;i<num;i++)
	{
		printf("请输入第 %d 个元素的系数和幂：\n",i+1);
		tmp=(node*)malloc(sizeof(node));
		if(tmp!=NULL)
		{
			scanf("%d%d",&tmp->coefficient,&tmp->power);
			tmp->next=NULL;
			pointer->next=tmp;
			pointer=tmp;			
		}
	}
	return(head);
}

node *Standard(node *head)  //对多项式进行规范化的过程
{
	int i;
	node *pointer,*pre,*cur,*tmp,*q;
	
	pointer=head->next;  //代表用于比较及合并相同幂的节点，也用于条件判断，控制循环
	pre=pointer;  //代表被比较的节点的上一个节点的指针，用于链接节点的操作，从而构造新的链表
	cur=pointer->next;  //代表被比较的节点，也用于条件判断，控制循环

	while(pointer->next!=NULL)  //合并无序多项式中具有相同幂的节点，并将被合并后的节点删除
	{
		while(cur!=NULL)
		{
			if(pointer->power==cur->power)  //相等则合并，同时删除被合并过的节点
			{
				pointer->coefficient+=cur->coefficient;  //合并具有相同幂的项的系数
				q=cur;
				cur=cur->next;
				pre->next=cur;
				free(q);  //释放内存
			}
			else  //不等则指向被比较的节点及其上一节点的指针均后移
			{
				cur=cur->next;
				pre=pre->next;
			}
		}
		pointer=pointer->next;  //后移
		pre=pointer;  //重新初始化
		cur=pointer->next;  //重新初始化
	}
	
	Print(head);  //打印出上面while以后构造成的多项式

	for(i=0;i<GetLength(head);i++)  //将上一步while完成以后得到多项式进一步规范化，使之按数据项的幂由大到小依次排列
	{
		pre=head;  //代表指向当前节点的指针的上一指针，用于交换节点的操作
		cur=head->next;  //代表指向当前节点的指针，用于比较
		tmp=cur->next;  //代表指向当前节点的下一节点的指针，用于比较和条件判断
	
		while(tmp!=NULL)
		{
			if(cur->power<tmp->power)  //如果当前数据项的幂小于其后紧邻的数据项的幂，则交换两个节点在链表中的位置，然后改变指针使重新指向
			{
				pre->next=tmp;
				cur->next=tmp->next;
				tmp->next=cur;
				
				pre=tmp;
				tmp=cur->next;
			}
			else  //如果条件相反的话，直接后移这三个指针
			{
				pre=pre->next;
				cur=cur->next;
				tmp=tmp->next;
			}
		}
	}

	return(head);
}

int GetLength(node *head)  //获得单链表的长度
{
	int i=0;
	node *pointer;
	pointer=head->next;

	while(pointer!=NULL)
	{
		i++;
		pointer=pointer->next;
	}
	return i;
}

void Print(node *head)  //打印出单链表的节点数据
{
	int i=0;
	node *pointer;
	pointer=head->next;
	
	printf("\n新的多项式系数和幂表示如下：\n");
	while(pointer!=NULL)
	{
		i++;
		printf("第 %d 个数据元素的系数为：%d,幂为：%d\n",i,pointer->coefficient,pointer->power);
		pointer=pointer->next;
	}
}

int main()
{
	node *multinomial;
	multinomial=Create(N);
	Print(multinomial);

	multinomial=Standard(multinomial);
	Print(multinomial);

	return 0;
}

 

 

调试环境：Ubuntu Desktop 8.04.4    VI 7.1.138    GCC 4.2.4
QQ：81064483
E-mail：[e-mail]

复习之用，不足之处，烦请高手们指点。< ^_^ >