多項式的規(guī)范化，采用單鏈表，使用C語言實(shí)現(xiàn)，gcc調(diào)試通過。
1 //該程序是為了將無序的、不規(guī)范的多項式進(jìn)行規(guī)范化而寫的。
2 #include<stdio.h>
3 #include<stdlib.h>
4 #define N 8 //指明多項式數(shù)據(jù)項的數(shù)目
5
6 int GetLength(); //獲得單鏈表的長度
7 void Print(); //打印出單鏈表的節(jié)點(diǎn)數(shù)據(jù)
8
9 typedef struct multinomialnode //定義存儲多項式數(shù)據(jù)項的節(jié)點(diǎn)的結(jié)構(gòu)體
10 {
11 int coefficient,power; //定義系數(shù)和冪
12 struct multinomialnode *next;
13 }node;
14
15 node *Create(int num) //創(chuàng)建存儲多項式的鏈表
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("請依次輸入要處理的多項式元素的系數(shù)和冪：\n");
24 for(i=0;i<num;i++)
25 {
26 printf("請輸入第 %d 個元素的系數(shù)和冪：\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) //對多項式進(jìn)行規(guī)范化的過程
40 {
41 int i;
42 node *pointer,*pre,*cur,*tmp,*q;
43
44 pointer=head->next; //代表用于比較及合并相同冪的節(jié)點(diǎn)，也用于條件判斷，控制循環(huán)
45 pre=pointer; //代表被比較的節(jié)點(diǎn)的上一個節(jié)點(diǎn)的指針，用于鏈接節(jié)點(diǎn)的操作，從而構(gòu)造新的鏈表
46 cur=pointer->next; //代表被比較的節(jié)點(diǎn)，也用于條件判斷，控制循環(huán)
47
48 while(pointer->next!=NULL) //合并無序多項式中具有相同冪的節(jié)點(diǎn)，并將被合并后的節(jié)點(diǎn)刪除
49 {
50 while(cur!=NULL)
51 {
52 if(pointer->power==cur->power) //相等則合并，同時刪除被合并過的節(jié)點(diǎn)
53 {
54 pointer->coefficient+=cur->coefficient; //合并具有相同冪的項的系數(shù)
55 q=cur;
56 cur=cur->next;
57 pre->next=cur;
58 free(q); //釋放內(nèi)存
59 }
60 else //不等則指向被比較的節(jié)點(diǎn)及其上一節(jié)點(diǎn)的指針均后移
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以后構(gòu)造成的多項式
72
73 for(i=0;i<GetLength(head);i++) //將上一步while完成以后得到多項式進(jìn)一步規(guī)范化，使之按數(shù)據(jù)項的冪由大到小依次排列
74 {
75 pre=head; //代表指向當(dāng)前節(jié)點(diǎn)的指針的上一指針，用于交換節(jié)點(diǎn)的操作
76 cur=head->next; //代表指向當(dāng)前節(jié)點(diǎn)的指針，用于比較
77 tmp=cur->next; //代表指向當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)的指針，用于比較和條件判斷
78
79 while(tmp!=NULL)
80 {
81 if(cur->power<tmp->power) //如果當(dāng)前數(shù)據(jù)項的冪小于其后緊鄰的數(shù)據(jù)項的冪，則交換兩個節(jié)點(diǎn)在鏈表中的位置，然后改變指針使重新指向
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) //打印出單鏈表的節(jié)點(diǎn)數(shù)據(jù)
117 {
118 int i=0;
119 node *pointer;
120 pointer=head->next;
121
122 printf("\n新的多項式系數(shù)和冪表示如下：\n");
123 while(pointer!=NULL)
124 {
125 i++;
126 printf("第 %d 個數(shù)據(jù)元素的系數(shù)為：%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
調(diào)試環(huán)境：Ubuntu Desktop 8.04.4 VI 7.1.138 GCC 4.2.4
QQ：81064483
E-mail：AllenNewOK@126.com
復(fù)習(xí)之用，不足之處，煩請高手們指教。< ^_^ >