首页 > 代码库 > 学习笔记：单链表实现多项式相乘（一）

学习笔记：单链表实现多项式相乘（一）

2024-08-12 19:07:08   222人阅读

单链表实现多项式相乘，有这样的一个思路可以参考：

实现多项式相乘，最关键的是系数和指数的两个数据，这里命名为coef和HighPower。

最简便的办法是使用两个嵌套循环例如(3x^2+4x^1)(x^2+2x^4)用3x^2遍历另外一个括号内的数据，同时实现本身括号内的遍历。

这个想法的核心程序可归纳为以下：

while(pList!=NULL){        while(pList2!=NULL){            pNew=(PNODE)malloc(sizeof(NODE));            pNew->pNext=NULL;            pNew->coef=(pList->coef)*(pList2->coef);            pNew->HighPower=(pList->HighPower)+(pList2->HighPower);            pReslut=addNewItem(pReslut,pNew);            pList2=pList2->pNext;        }        pList2=pHead2;        pList=pList->pNext;    }

这样即可实现将所有数据，输出到一个新的链表里面。

但同时这也带来了不少问题，怎样才能合并新的链表里面相同系数的参数呢？

这里可以使用这样的方法：

创捷一个新表New,新表New2，将原有的表拆分循环复制在NEW2，然后将NEW2复制给NEW,如果在NEW中有相同项，则直接相加或者相乘，如果没有，则在链表最后添加新的节点。这样即可实现合并单链表中相同系数的参数。

源码如下：

#include<stdio.h>#include<stdlib.h>typedef struct node{    int coef;    int HighPower;    struct node *pNext;}NODE,*PNODE;PNODE crateList();void traverseLinkList(PNODE);PNODE caculate(PNODE,PNODE);PNODE addNewItem(PNODE ,PNODE );PNODE total(PNODE);PNODE ListFind(PNODE,PNODE);int main(){    PNODE pList,pList2,pNew;    pList=crateList();    getchar();     pList2=crateList();    pNew=caculate(pList,pList2);    pNew=total(pNew);    traverseLinkList(pNew);    return(0);}PNODE crateList(){    int a,b,c;    PNODE pCurrent,pPre,pHead=NULL;    pCurrent=NULL;pPre=NULL;     b=0,c=0;    while(1){        if(scanf("%d %d",&b,&c)!=2)            break;        pCurrent=(PNODE)malloc(sizeof(NODE));        if(pHead==NULL)            pHead=pCurrent;        else            pPre->pNext=pCurrent;        pCurrent->pNext=NULL;        pCurrent->coef=b;        pCurrent->HighPower=c;        pPre=pCurrent;    }    puts("input end,now next step");    return(pHead);}void traverseLinkList(PNODE pList){    PNODE pCurrent;    pCurrent=pList;    if(pCurrent==NULL)        puts("No Data Record");    else        while(pCurrent!=NULL){            printf("the Coef is %d,and HighPower is %d\n",pCurrent->coef,pCurrent->HighPower);            pCurrent=pCurrent->pNext;        }} PNODE caculate(PNODE pList,PNODE pList2){    PNODE pNew,pCurrent,pPre,pHead2=pList2,pReslut=NULL;    if(!pList||!pList2){        puts("wrong!");        return(0);    }    while(pList!=NULL){        while(pList2!=NULL){            pNew=(PNODE)malloc(sizeof(NODE));            pNew->pNext=NULL;            pNew->coef=(pList->coef)*(pList2->coef);            pNew->HighPower=(pList->HighPower)+(pList2->HighPower);            pReslut=addNewItem(pReslut,pNew);            pList2=pList2->pNext;        }        pList2=pHead2;        pList=pList->pNext;    }    return(pReslut);}PNODE addNewItem(PNODE pReslut,PNODE pAdd){    PNODE pHead=NULL,pCurrent;    if(pReslut==NULL){        return(pAdd);    }    pHead=pReslut;    pCurrent=pReslut;    while(pCurrent->pNext!=NULL)        pCurrent= pCurrent->pNext;    pCurrent->pNext=pAdd;    pAdd->pNext=NULL;    return(pHead);}PNODE  total(PNODE pNew){    PNODE pNew3,pCurrent,pPre,pHead,pNew2=NULL;    pCurrent=pNew;    if(!pNew)        return(0);    pNew3=(PNODE)malloc(sizeof(NODE));    pNew2=(PNODE)malloc(sizeof(NODE));    pNew3->pNext=NULL;    while(pCurrent!=NULL){        pNew3->coef=pCurrent->coef;            pNew3->HighPower=pCurrent->HighPower;        pNew2=ListFind(pNew2,pNew3);        if(!pHead)            pHead=pNew;        pCurrent=pCurrent->pNext;    }    return(pHead);}PNODE ListFind(PNODE pNew,PNODE pList){    PNODE pCurrent,pPre,pHead,pCurrent2;    while(pCurrent!=NULL){        if(pCurrent->HighPower==pList->HighPower){            pCurrent->coef=(pCurrent->coef)*(pList->coef);            pCurrent->HighPower=pCurrent->HighPower+pList->HighPower;            return(pHead);        }        pCurrent=pCurrent->pNext;    }    pCurrent=(PNODE)malloc(sizeof(NODE));    if(!pHead)        pHead=pCurrent;    else        pPre->pNext=pCurrent;    puts("ok");    pCurrent->pNext=NULL;    pCurrent->coef=pList->coef;    pCurrent->HighPower=pList->HighPower;    pPre=pCurrent;    return(pHead);}

 

学习笔记：单链表实现多项式相乘（一）


联系
我们