EX14. 鏈結串列的應用- 多項式表示法

修改程式範例: Ch4-6.c 為 Ch4-6e.c
請使用含開頭節點的環狀串列結構儲存下列多項式，如下所示：
(1) f(x) = X4+5X3+4X+3
(2) g(x) = 5X2+2X+5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

/* Ch4-6e.c */ #include <stdio.h> #include <stdlib.h> #include "Ch4-6.h" #include "createPoly.c" /* 主程式 */ int main() { PList a = NULL; /* 多項式串列1的開頭指標 */ PList b = NULL; /* 多項式串列2的開頭指標 */ /* 建立多項式物件所需的陣列 */ float list1[5] = { 3, 4, 0, 5, 1 }; float list2[5] = { 5, 2, 5, 0, 0 }; a = createPoly(5, list1); /* 建立多項式串列1 */ b = createPoly(5, list2); /* 建立多項式串列2 */ printf("f(x) = "); /* 顯示多項式1 */ printPoly(a); printf("g(x) = "); /* 顯示多項式2 */ printPoly(b); system("PAUSE"); return 0; }

1 2 3 4 5 6 7 8 9 10 11

/* Ch4-6.h */ struct Node /* Node節點結構 */ { float coef; int exp; /* 結構變數宣告 */ struct Node *next; /* 指向下一個節點 */ }; typedef struct Node PNode; /* 多項式串列節點的新型態 */ typedef PNode *PList; /* 多項式串列的新型態 */ /* 抽象資料型態的操作函數宣告 */ extern PList createPoly(int len, float *array); extern void printPoly(PList first);

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/* createPoly.c */ /* 函數: 建立多項式的串列 */ PList createPoly(int len, float *array) { int i; PList first, ptr, newnode; /* 建立開頭節點 */ first = (PList) malloc(sizeof(PNode)); first->coef = 0.0; /* 建立開頭節點的內容 */ first->exp = -1; ptr = first; /* 前一個節點指標 */ for ( i = len-1; i >= 0; i-- ) { if ( array[i] != 0.0 ) /* 配置節點記憶體 */ { newnode = (PList) malloc(sizeof(PNode)); newnode->coef = array[i]; /* 建立節點的內容 */ newnode->exp = i; ptr->next = newnode; /* 連結新節點 */ ptr = newnode; /* 成為前一個節點 */ } } ptr->next = first; /* 連結第1個節點, 建立環狀串列 */ return first; } /* 函數: 顯示多項式 */ void printPoly(PList first) { PList ptr = first->next; /* 串列真正的開頭 */ float c; int e; while ( ptr != first ) /* 顯示主迴圈 */ { c = ptr->coef; e = ptr->exp; printf("%3.1fX^%d", c, e); ptr = ptr->next; /* 下一個節點 */ if ( ptr != first ) printf(" + "); } printf("\n"); }

/* OUTPUT */

f(x) = 1.0X^4 + 5.0X^3 + 4.0X^1 + 3.0X^0
g(x) = 5.0X^2 + 2.0X^1 + 5.0X^0
請按任意鍵繼續 . . .