作業十四：儲存多項式

/* 程式範例: Ch4-6.c */
#include <stdio.h>
#include <stdlib.h>
struct Node {               /* Node節點結構 */
   float coef;  int exp;    /* 結構變數宣告 */
   struct Node *next;       /* 指向下一個節點 */
};
typedef struct Node PNode;  /* 多項式串列節點的新型態 */
typedef PNode *PList;       /* 多項式串列的新型態 */
/* 抽象資料型態的操作函數宣告 */
PList createPoly(int len, float *array);
void printPoly(PList first);
PList pPoly(PList a,PList b);
PList mPoly(PList a,PList b);
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");  
}
PList pPoly(PList a,PList b){
   int i,c;
   int max=((a->next->exp)>(b->next->exp))?a->next->exp+1:b->next->exp+1;
   float *ptr=(float *)malloc(sizeof(float)*max);
   PList cur;
   for(i=0;i<max;i++){
      ptr[i]=0;
   }
   cur=a->next;
   while(cur!=a){
       c=cur->exp;
       ptr[c]+=cur->coef;
       cur=cur->next;
   }
   cur=b->next;
   while(cur!=b){
      c=cur->exp;
      ptr[c]+=cur->coef;
      cur=cur->next;
   }
   cur=createPoly(max,ptr);
   return cur;
}
PList mPoly(PList a,PList b){
   int i,max,k;
   float *ptr,v;
   PList cur1,cur2,cur;
   max=a->next->exp+b->next->exp+1;
   ptr=(float *)malloc(sizeof(float)*max);
   for(i=0;i<max;i++){
      ptr[i]=0;
   }
   cur1=a->next;
   while(cur1!=a){
       cur2=b->next;
       while(cur2!=b){
          v=cur1->coef*cur2->coef;
          k=cur1->exp+cur2->exp;
          ptr[k]+=v; 
          cur2=cur2->next;
       }
       cur1=cur1->next;
   }
   cur=createPoly(max,ptr);
   return cur;
}
/* 主程式 */
int main() {
   PList a = NULL;    /* 多項式串列1的開頭指標 */
   PList b = NULL;   /* 多項式串列2的開頭指標 */
   PList c = NULL;
   PList d = NULL;
   /* 建立多項式物件所需的陣列 */
   float list1[5] = { 3, 4,0,5,1};
   float list2[3] = { 5, 2,5};
   a = createPoly(5, list1);  /* 建立多項式串列1 */
   b = createPoly(3, list2);  /* 建立多項式串列2 */
   printf("f(x)=");
   printPoly(a);     /* 顯示多項式1 */
   printf("g(x)=");
   printPoly(b);    /* 顯示多項式2 */
   system("PAUSE");
   return 0;
}