多项式的规范化，采用单链表，使用C语言实现，gcc调试通过。
1 //该程序是为了将无序的、不规范的多项式进行规范化而写的。
2 #include<stdio.h>
3 #include<stdlib.h>
4 #define N 8 //指明多项式数据项的数目
5
6 int GetLength(); //获得单链表的长度
7 void Print(); //打印出单链表的节点数据
8
9 typedef struct multinomialnode //定义存储多项式数据项的节点的结构体
10 {
11 int coefficient,power; //定义系数和幂
12 struct multinomialnode *next;
13 }node;
14
15 node *Create(int num) //创建存储多项式的链表
16 {
17 int i;
18 node *head,*pointer,*tmp;
19
20 head=(node*)malloc(sizeof(node));
21 if(head!=NULL) pointer=head;
22
23 printf("请依次输入要处理的多项式元素的系数和幂：\n");
24 for(i=0;i<num;i++)
25 {
26 printf("请输入第 %d 个元素的系数和幂：\n",i+1);
27 tmp=(node*)malloc(sizeof(node));
28 if(tmp!=NULL)
29 {
30 scanf("%d%d",&tmp->coefficient,&tmp->power);
31 tmp->next=NULL;
32 pointer->next=tmp;
33 pointer=tmp;
34 }
35 }
36 return(head);
37 }
38
39 node *Standard(node *head) //对多项式进行规范化的过程
40 {
41 int i;
42 node *pointer,*pre,*cur,*tmp,*q;
43
44 pointer=head->next; //代表用于比较及合并相同幂的节点，也用于条件判断，控制循环
45 pre=pointer; //代表被比较的节点的上一个节点的指针，用于链接节点的操作，从而构造新的链表
46 cur=pointer->next; //代表被比较的节点，也用于条件判断，控制循环
47
48 while(pointer->next!=NULL) //合并无序多项式中具有相同幂的节点，并将被合并后的节点删除
49 {
50 while(cur!=NULL)
51 {
52 if(pointer->power==cur->power) //相等则合并，同时删除被合并过的节点
53 {
54 pointer->coefficient+=cur->coefficient; //合并具有相同幂的项的系数
55 q=cur;
56 cur=cur->next;
57 pre->next=cur;
58 free(q); //释放内存
59 }
60 else //不等则指向被比较的节点及其上一节点的指针均后移
61 {
62 cur=cur->next;
63 pre=pre->next;
64 }
65 }
66 pointer=pointer->next; //后移
67 pre=pointer; //重新初始化
68 cur=pointer->next; //重新初始化
69 }
70
71 Print(head); //打印出上面while以后构造成的多项式
72
73 for(i=0;i<GetLength(head);i++) //将上一步while完成以后得到多项式进一步规范化，使之按数据项的幂由大到小依次排列
74 {
75 pre=head; //代表指向当前节点的指针的上一指针，用于交换节点的操作
76 cur=head->next; //代表指向当前节点的指针，用于比较
77 tmp=cur->next; //代表指向当前节点的下一节点的指针，用于比较和条件判断
78
79 while(tmp!=NULL)
80 {
81 if(cur->power<tmp->power) //如果当前数据项的幂小于其后紧邻的数据项的幂，则交换两个节点在链表中的位置，然后改变指针使重新指向
82 {
83 pre->next=tmp;
84 cur->next=tmp->next;
85 tmp->next=cur;
86
87 pre=tmp;
88 tmp=cur->next;
89 }
90 else //如果条件相反的话，直接后移这三个指针
91 {
92 pre=pre->next;
93 cur=cur->next;
94 tmp=tmp->next;
95 }
96 }
97 }
98
99 return(head);
100 }
101
102 int GetLength(node *head) //获得单链表的长度
103 {
104 int i=0;
105 node *pointer;
106 pointer=head->next;
107
108 while(pointer!=NULL)
109 {
110 i++;
111 pointer=pointer->next;
112 }
113 return i;
114 }
115
116 void Print(node *head) //打印出单链表的节点数据
117 {
118 int i=0;
119 node *pointer;
120 pointer=head->next;
121
122 printf("\n新的多项式系数和幂表示如下：\n");
123 while(pointer!=NULL)
124 {
125 i++;
126 printf("第 %d 个数据元素的系数为：%d,幂为：%d\n",i,pointer->coefficient,pointer->power);
127 pointer=pointer->next;
128 }
129 }
130
131 int main()
132 {
133 node *multinomial;
134 multinomial=Create(N);
135 Print(multinomial);
136
137 multinomial=Standard(multinomial);
138 Print(multinomial);
139
140 return 0;
141 }
142
调试环境：Ubuntu Desktop 8.04.4 VI 7.1.138 GCC 4.2.4
QQ：81064483
E-mail：AllenNewOK@126.com
复习之用，不足之处，烦请高手们指教。< ^_^ >