/************************************************************************/ /* @author lynnbest 目標:多項式的乘法 exp: A(X)=2X^3+4 B(x)=4X^4+2X^3 C(X)=A(x)*B(x)=8X^7+4X^6+16X^4+8X^3 思路: 1.創建兩個鏈表,用於存儲兩個多項式 用鏈式存儲 系數域+指數域+指針域 2.完成兩個多項式的乘法 3.打印出新結果 */ /************************************************************************/ #include <stdio.h> #include <stdlib.h> typedef struct node { float coef;//系數 int exp; //指數 struct node *next; //指針域 }listnode; listnode *CreateList(int n); int printflist(listnode *head); int InverseList(listnode *head); listnode *MultiplisePoly(listnode *head_a,listnode *head_b); int main() { printf(" 鏈表實現多項式的乘法 \n"); printf("----by lynnbest ----\n\n"); int n; printf("請輸入A(X)的項數(降冪排列)\n"); scanf("%d",&n); listnode *head_a=CreateList(n); printf("A(X)="); printflist(head_a); printf("請輸入B(X)的項數(降冪排列)\n"); scanf("%d",&n); listnode *head_b=CreateList(n); // InverseList(head_b); printf("B(X)="); printflist(head_b); listnode *head_c=MultiplisePoly(head_a,head_b); printf("C(X)=A(X)*B(X)="); printflist(head_c); return 0; } listnode *CreateList(int n) { listnode *head=(listnode *)malloc(sizeof(listnode)),*p,*pre=head;//head指向頭結點,p指向新開辟的節點 float coef; //系數 int exp; //指數 if(NULL==head) { printf("開辟頭結點失敗\n"); exit(-1); } head->next=NULL; for(int i=0;i<n;i++) { if(NULL==(p=(listnode *)malloc(sizeof(listnode)))) { printf("新結點malloc失敗\n"); exit(-1); } printf("請輸入第%d個系數和指數\n",i+1); scanf("%f,%d",&coef,&exp); p->coef=coef; p->exp=exp; //更新節點數據 p->next=NULL; //插入節點 pre->next=p; pre=p; } return head; //這裡是返回堆的內存區 不是局部變量 } int printflist(listnode *head) { listnode *p=head->next; while(p->next!=NULL) { printf("%1.1f*X^%d+",p->coef,p->exp);// %1.1f格式輸出小數點後只保留一位 p=p->next; } printf("%1.1f*X^%d\n",p->coef,p->exp); return 0; } /************************************************************************/ /* 鏈式相乘: 思路: 1.因為兩個鏈表都是指數遞減,所以A(X)遞減,B(x)逆置下,遞增,why do this? 2.先獲取兩個最大的指數和 exp_max. 這樣的話余下的指數就是都在0~7之間了。 關鍵來了,遍歷相乘本質並不難,但是如何可以找到所有的指數呢?而且還要開辟新的節點來存儲沒有的指數 解決:用一個新的鏈來存儲結果,從exp_max開始向下查找,每一個可能指數都要遍歷到。 這裡指數升序+降序的排列就很精妙了。 for(k=exp_max;k>=0;k--) { 相乘; 判斷是否還有同類的系數,有就相加; } 如何判斷呢?就是在步進查找。 若是當前k值,表明該指數找到了,此時就是a,b都後繼一位,因為只有這種組合才可能有同樣系數 若是當前指數<k,表明則表明要增加系數和,只有a增加 若是當前指數>k,表明要減少系數和,只有b增加 這也就看出了,a,b兩個鏈表指數一個升序一個降序的好處了。這種思路很好 3.歸納總結下: 3.1 求k=exp_max; 3.2 逆置b 3.3 遍歷查找 怎麼做循環又是個問題 一旦查找到了 =k的情況,然後就繼續搜索其他可能性 直到都到NULL節點 */ /************************************************************************/ listnode *MultiplisePoly(listnode *head_a,listnode *head_b)//鏈式相乘 { listnode *head_c,*pa=head_a,*pb=head_b,*pc,*newnode; int exp_max; //指數之和最大值 if(pa->next!=NULL && pb->next!=NULL) exp_max=pa->next->exp+pb->next->exp; //獲取最大指數和 else return NULL; //初始化鏈表C頭結點 head_c=(listnode *)malloc(sizeof(listnode)); if(NULL==head_c) { printf("開辟鏈表C失敗\n"); exit(-1); } head_c->coef=0.0; head_c->exp=0; head_c->next=NULL; pc=head_c; InverseList(head_b); //逆置b鏈表 float ceof=0.0; for(int k=exp_max;k>=0;k--) { pa=head_a->next; //恢復pa的指向 while(pa!=NULL && pa->exp>k) //首先查找pa的位置 找不大於k的 pa=pa->next; pb=head_b->next;//恢復Pb的指向 while(pa!=NULL && pb!=NULL && pa->exp+pb->exp<k)//然後在查找pb的位置 pa+pb的指數和不大於k pb=pb->next; //經過上面兩輪後 pa+pb 的exp<=k while(pa!=NULL && pb!=NULL)//此循環進入後,找到所有的同指數的和相加 { if(k==pa->exp+pb->exp) //目的就是找等於K { ceof+=pa->coef*pb->coef; pa=pa->next; pb=pb->next; } else { if(pa->exp+pb->exp<k) //小於k 增加pb pb=pb->next; else pa=pa->next; //大於k 減小pa } } if(ceof!=0.0) //有系數了 就將此節點插入到c鏈表中 { if(NULL==(newnode=(listnode *)malloc(sizeof(listnode)))) { printf("鏈表C節點開辟失敗"); exit(-1); } newnode->coef=ceof; newnode->exp=k; newnode->next=NULL; //插入節點數據 pc->next=newnode; pc=newnode; //插入節點 ceof=0.0; } } InverseList(head_b); return head_c; } int InverseList(listnode *head) //逆置鏈表 { listnode *p=head->next,*q; //p指向正要逆置的節點,q指向下一個待逆置的節點 head->next=NULL; while(p) //當前節點不為空 { q=p->next;//保存下一個節點 p->next=head->next; //先更新逆置點的 next head->next=p; //在更新head->next p=q; //下一輪 } return 0; }