线性表实现一元多项式操作

水深无声 2022-05-08 05:44 228阅读 0赞

数组存放：

不需要记录幂，下标就是。

比如1，2，3，5表示1+2x+3x^2+5x^3

有了思路，我们很容易定义结构

typedef struct node{
        float * coef;//系数数组
        int maxSize;//最大容量
        int order;//最高阶数
    }Polynomial;

先实现求和：我们想求两个式子a+b，结果存在c中。

逻辑很简单，就是相加啊。

void Add(Polynomial & A,Polynomial & B,Polynomial & C)
    {
        int i;
        int m=A.order;
        int n=B.order;
        for(i=0;i<=m && i<=n;i++)//共有部分加一起
            C.coef[i]=A.coef[i]+B.coef[i];
        while(i<=m)//只会执行一个，作用是把剩下的放入c
            C.coef[i]=A.coef[i];
        while(i<=n)
            C.coef[i]=B.coef[i];
        C.order=(m>n)?m:n;//等于较大项
    }

实现乘法：

我们思考一下，两个多项式怎么相乘？

把a中每一项都和b中每一项乘一遍就好了。

高中知识

void Mul(Polynomial & A,Polynomial & B,Polynomial & C)
    {
        int i;
        int m=A.order;
        int n=B.order;
        if(m+n>C.maxSize)
        {
            printf("超限");
            return;
        }
        for(i=0;i<=m+n;i++)//注意范围，是最高项的幂加起来
            C.coef[i]=0.0;
        for(i=0;i<=m;i++)
        {
            for(j=0;j<=n;j++)
            {
                C.coef[i+j]+=A.coef[i]*B.coef[j];
            }
        }
        C.order=m+n;//注意范围，是最高项的幂加起来
    }

利用数组存放虽然简单，但是当幂相差很大时，会造成空间上的严重浪费（包括时间也是），所以我们考虑采用链表存储。

我们思考一下如何存储和做运算。

我们肯定要再用一个变量记录幂了。每个节点记录系数和指数。

考虑如何相加：

对于c，其实刚开始是空的，我们首先要实现一个插入功能，然后，遍历a和b，进一步利用插入函数来不断尾插。

因为a和b都是升幂排列，所以相加的时候，绝对不会发生结果幂小而后遇到的情况，所以放心的一直插入就好了。

具体实现也比较好想：a和b幂相等就加起来，不等就小的单独插入，然后指针向后移。

加法就放老师写的代码吧，很漂亮的代码：（没和老师商量，希望不会被打）

老师原地插的，都一样都一样

老师原文：[http://www.edu2act.net/article/shu-ju-jie-gou-xian-xing-biao-de-jing-dian-ying-yong/][http_www.edu2act.net_article_shu-ju-jie-gou-xian-xing-biao-de-jing-dian-ying-yong]

void AddPolyn(polynomial &Pa, polynomial &Pb)
    	//多项式的加法：Pa = Pa + Pb,利用两个多项式的结点构成“和多项式”。 
    {
    	LinkList ha = Pa;		//ha和hb分别指向Pa和Pb的头指针
    	LinkList hb = Pb;
    	LinkList qa = Pa->next;
    	LinkList qb = Pb->next;	//ha和hb分别指向pa和pb的前驱
    	while (qa && qb)		//如果qa和qb均非空
    	{
    		float sum = 0.0;
    		term a = qa->data;
    		term b = qb->data;
    		switch (cmp(a,b))
    		{
    		case -1:	//多项式PA中当前结点的指数值小
    			ha = qa;
    			qa = qa->next;
    			break;
    		case 0:		//两者指数值相等
    			sum = a.coef + b.coef;
    			if(sum != 0.0)
    			{	//修改多项式PA中当前结点的系数值
    				qa->data.coef = sum;
    				ha = qa;
    			}else
    			{	//删除多项式PA中当前结点
    				DelFirst(ha, qa);
    				free(qa);
    			}
    			DelFirst(hb, qb);
    			free(qb);
    			qb = hb->next;
    			qa = ha->next;
    			break;
    		case 1:
    			DelFirst(hb, qb);
    			InsFirst(ha, qb);
    			qb = hb->next;
    			ha = ha->next;
    			break;
    		}//switch
    	}//while
    	if(!ListEmpty(Pb))
    		Append(Pa,qb);
    	DestroyList(hb);
    
    }//AddPolyn

对于乘法，我们就不能一直往后插了，因为遍历两个式子，可能出现幂变小的情况。所以我们要实现一个插入函数，如果c中有这一项，就加起来，没这一项就插入。

我们先实现插入函数：（哦，对了，我没有像老师那样把系数和指数再定义一个结构体，都放一起了。还有next我写的link，还有点别的不一样，都无伤大雅，绝对能看懂）

void Insert(Polynomial &L,float c,int e)//系数c，指数e
    {
        Term * pre=L;
        Term * p=L->link;
        while(p && p->exp<e)//查找
        {
            pre=p;
            p=p->link;
        }
        if(p->exp==e)//如果有这一项
        {
            if(p->coef+c)//如果相加是0了，就删除节点
            {
                pre->link=p->link;
                free(p);
            }
            else//相加不是0，就合并
            {
                p->coef+=c;
            }
        }
        else//如果没这一项，插入就好了，链表插入写了很多遍了
        {
                Term * pc=new Term;//创建
                pc->exp=e;
                pc->coef=c;
                pre->link=pc;
                pc->link=p;        
        }
    }

插入写完了，乘法就好实现了，还是两个循环，遍历a和b，只是最后调用Insert方法实现就ok

insert（c，乘系数，加幂）

拓展：一维数组可以模拟一元多项式。类似的，二维数组可以模拟二元多项式。实现以后有时间写了再放链接。

[http_www.edu2act.net_article_shu-ju-jie-gou-xian-xing-biao-de-jing-dian-ying-yong]: http://www.edu2act.net/article/shu-ju-jie-gou-xian-xing-biao-de-jing-dian-ying-yong/