多项式的规范化,采用单链表,使用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:AllenNewOK@126.com
复习之用,不足之处,烦请高手们指点。< ^_^ >
?
?