多項式的規范化，采用單鏈表，使用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
復習之用，不足之處，煩請高手們指教。< ^_^ >