[ 資料結構 小學堂 ] 鏈結串列 : 單向鏈結串列 - 多項式的串列表示法

前言 : 
在 [ 資料結構 小學堂 ] 陣列結構 : 矩陣與多項式 介紹過矩陣的多項式表示法, 不過使用矩陣表示多項式會有以下困擾 : 

- 多項式內容變動時, 對陣列影響大, 演算法處理不易.
- 由於陣列式靜態資料結構, 所以事先必須尋找一塊連續且夠大的記憶體, 容易造成空間浪費.

因為使用單向鏈結串列來表示多項式, 可以克服以上問題, 多項式的鏈結表示法主要是儲存非零項目, 並且每一項均符合以下資料結構 : 
 

例如假設多項式有 n 個非零項目, 則可以表示成 : 
 

另外關於多項式的加法在單向鏈結結構也相當簡單, 請參考下面代碼範例. 

範例代碼 : 
多項式相加的演算法範例 : 
* List.h 代碼 : 

view plaincopy to clipboardprint?

1. #include   
2. using namespace std;  
3.   
4. class List{  
5. public:  
6.     int coef, exp;  
7.     class List *next;  
8. };  
9.   
10. typedef class List ListNode;  
11. typedef ListNode *ListLink;  
12.   
13. ListLink createLink(int data[4]);  
14. void printLink(ListLink head);  
15. ListLink sumLink(ListLink a, ListLink b);  

* List.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "List.h"  
2.   
3. ListLink createLink(int data[4]){  
4.     ListLink head, newnode, ptr;  
5.     for(int i=0; i<4 ; i++) {  
6.         newnode = new ListNode;  
7.         if(!newnode){  
8.             cout << "Error!! 記憶體配置失敗!!" << endl;  
9.             exit(1);  
10.         }  
11.         if(i==0) {  
12.             newnode->coef = data[i];  
13.             newnode->exp = 3-i;  
14.             newnode->next=NULL;  
15.             head = newnode;  
16.             ptr = head;  
17.         } else {  
18.             newnode->coef = data[i];  
19.             newnode->exp = 3-i;  
20.             newnode->next = NULL;  
21.             ptr->next = newnode;  
22.             ptr = newnode;  
23.         }  
24.     }  
25.     return head;  
26. }  
27.   
28. void printLink(ListLink head) {  
29.     while(head!=NULL) {  
30.         if(head->exp==1 && head->coef!=0)  
31.             cout << head->coef << "X + ";  
32.         else if(head->exp!=0 && head->coef!=0)  
33.             cout << head->coef << "X^" << head->exp << " + ";  
34.         else if(head->exp==0 && head->coef!=0)  
35.             cout << head->coef;  
36.         head = head->next;  
37.     }  
38.     cout << endl;  
39. }  
40.   
41. ListLink sumLink(ListLink a, ListLink b){  
42.     int i=0;  
43.     int sum[4] = {0};  
44.     ListLink ptr;  
45.     while(a!=NULL || b!=NULL){        
46.         if(a!=NULL && b != NULL && (a->exp == b->exp)) {  
47.             sum[i] = a->coef + b->coef;  
48.             i++;  
49.             a = a->next;  
50.             b = b->next;  
51.         } else if((a!=NULL && b==NULL) || (a->exp > b->exp)) {  
52.             sum[i] = a->coef;  
53.             i++;  
54.             a = a->next;  
55.         } else if((a==NULL && b!=NULL) || (a->exp < b->exp)) {  
56.             sum[i] = b->coef;  
57.             i++;  
58.             b = b->next;  
59.         }  
60.     }  
61.     return createLink(sum);  
62. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void ch03_08() {  
2.     ListLink a,b,c;  
3.     int data1[] = {3,0,4,2}; // 多項式A的係數  
4.     int data2[] = {6,8,6,9}; // 多項式B的係數  
5.     cout << "原始多項式: " << endl << "A=" ;  
6.     a = createLink(data1);  
7.     b = createLink(data2);  
8.     printLink(a);  
9.     cout << "B=";  
10.     printLink(b);  
11.     cout << "多項式相加結果: \nC= ";  
12.     c = sumLink(a, b);  
13.     printLink(c);  
14. }  

執行結果 : 

原始多項式:
A=3X^3 + 4X + 2
B=6X^3 + 8X^2 + 6X + 9
多項式相加結果:
C= 9X^3 + 8X^2 + 10X + 11

補充說明 : 
* [ 資料結構 小學堂 ] 鏈結串列 : 單向鏈結串列