程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 單鏈表實現多項式的相乘

單鏈表實現多項式的相乘

編輯:C++入門知識

/************************************************************************/  
/* @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;  
}  

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved