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

標籤

2010年9月16日 星期四

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

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

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

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

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

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

範例代碼 : 
多項式相加的演算法範例 : 
* List.h 代碼 : 
  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 代碼 : 
  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. }  
* 呼叫演算法代碼 : 
  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


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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!