多項(xiàng)式的規(guī)范化，采用單鏈表，使用C語(yǔ)言實(shí)現(xiàn)，gcc調(diào)試通過(guò)。
1 //該程序是為了將無(wú)序的、不規(guī)范的多項(xiàng)式進(jìn)行規(guī)范化而寫(xiě)的。
2 #include<stdio.h>
3 #include<stdlib.h>
4 #define N 8 //指明多項(xiàng)式數(shù)據(jù)項(xiàng)的數(shù)目
5
6 int GetLength(); //獲得單鏈表的長(zhǎng)度
7 void Print(); //打印出單鏈表的節(jié)點(diǎn)數(shù)據(jù)
8
9 typedef struct multinomialnode //定義存儲(chǔ)多項(xiàng)式數(shù)據(jù)項(xiàng)的節(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)建存儲(chǔ)多項(xià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("請(qǐng)依次輸入要處理的多項(xiàng)式元素的系數(shù)和冪：\n");
24 for(i=0;i<num;i++)
25 {
26 printf("請(qǐng)輸入第 %d 個(gè)元素的系數(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) //對(duì)多項(xiàng)式進(jìn)行規(guī)范化的過(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)的上一個(gè)節(jié)點(diǎn)的指針，用于鏈接節(jié)點(diǎn)的操作，從而構(gòu)造新的鏈表
46 cur=pointer->next; //代表被比較的節(jié)點(diǎn)，也用于條件判斷，控制循環(huán)
47
48 while(pointer->next!=NULL) //合并無(wú)序多項(xiàng)式中具有相同冪的節(jié)點(diǎn)，并將被合并后的節(jié)點(diǎn)刪除
49 {
50 while(cur!=NULL)
51 {
52 if(pointer->power==cur->power) //相等則合并，同時(shí)刪除被合并過(guò)的節(jié)點(diǎn)
53 {
54 pointer->coefficient+=cur->coefficient; //合并具有相同冪的項(xiàng)的系數(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)造成的多項(xiàng)式
72
73 for(i=0;i<GetLength(head);i++) //將上一步while完成以后得到多項(xiàng)式進(jìn)一步規(guī)范化，使之按數(shù)據(jù)項(xiàng)的冪由大到小依次排列
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ù)項(xiàng)的冪小于其后緊鄰的數(shù)據(jù)項(xiàng)的冪，則交換兩個(gè)節(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 //如果條件相反的話，直接后移這三個(gè)指針
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) //獲得單鏈表的長(zhǎng)度
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新的多項(xiàng)式系數(shù)和冪表示如下：\n");
123 while(pointer!=NULL)
124 {
125 i++;
126 printf("第 %d 個(gè)數(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í)之用，不足之處，煩請(qǐng)高手們指教。< ^_^ >