資料結構第四章評量第12題

/* 程式範例: 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;   /* 多項式串列1、2的相加結果指標 */
   PList d = NULL;   /* 多項式串列1、2的相乘結果指標 */
   /* 建立多項式物件所需的陣列 */
   float list1[6] = { 4, 1,0,3};
   float list2[6] = { 9, 7};
   a = createPoly(6, list1);  /* 建立多項式串列1 */
   b = createPoly(6, list2);  /* 建立多項式串列2 */
   c= pPoly(a,b);   /*串列1與串列2相加*/
   d= mPoly(a,b);  /*串列1與串列2相乘*/
   printPoly(a);     /* 顯示多項式1 */
   printPoly(b);     /* 顯示多項式2 */
   printPoly(c);    /* 顯示多項式1、2相加結果 */
   printPoly(d);    /* 顯示多項式1、2相乘結果 */
   system("PAUSE");
   return 0;
}