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

举报
兔老大 发表于 2021/04/25 01:31:43 2021/04/25
【摘要】   数组存放: 不需要记录幂,下标就是。 比如1,2,3,5表示1+2x+3x^2+5x^3 有了思路,我们很容易定义结构 typedef struct node{ float * coef;//系数数组 int maxSize;//最大容量 int order;//最高阶数}Polynomial; 先实现求和:我们想求两个式子a+b,结果存在c中。 ...

 

数组存放:

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

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

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


  
  1. typedef struct node{
  2. float * coef;//系数数组
  3. int maxSize;//最大容量
  4. int order;//最高阶数
  5. }Polynomial;

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

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


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

实现乘法:

我们思考一下,两个多项式怎么相乘?

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

高中知识

 


  
  1. void Mul(Polynomial & A,Polynomial & B,Polynomial & C)
  2. {
  3. int i;
  4. int m=A.order;
  5. int n=B.order;
  6. if(m+n>C.maxSize)
  7. {
  8. printf("超限");
  9. return;
  10. }
  11. for(i=0;i<=m+n;i++)//注意范围,是最高项的幂加起来
  12. C.coef[i]=0.0;
  13. for(i=0;i<=m;i++)
  14. {
  15. for(j=0;j<=n;j++)
  16. {
  17. C.coef[i+j]+=A.coef[i]*B.coef[j];
  18. }
  19. }
  20. C.order=m+n;//注意范围,是最高项的幂加起来
  21. }

 

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

 

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

 

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

考虑如何相加:

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

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

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

加法就放老师写的代码吧,很漂亮的代码:(没和老师商量,希望不会被打)

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

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


  
  1. void AddPolyn(polynomial &Pa, polynomial &Pb)
  2. //多项式的加法:Pa = Pa + Pb,利用两个多项式的结点构成“和多项式”。
  3. {
  4. LinkList ha = Pa; //ha和hb分别指向Pa和Pb的头指针
  5. LinkList hb = Pb;
  6. LinkList qa = Pa->next;
  7. LinkList qb = Pb->next; //ha和hb分别指向pa和pb的前驱
  8. while (qa && qb) //如果qa和qb均非空
  9. {
  10. float sum = 0.0;
  11. term a = qa->data;
  12. term b = qb->data;
  13. switch (cmp(a,b))
  14. {
  15. case -1: //多项式PA中当前结点的指数值小
  16. ha = qa;
  17. qa = qa->next;
  18. break;
  19. case 0: //两者指数值相等
  20. sum = a.coef + b.coef;
  21. if(sum != 0.0)
  22. { //修改多项式PA中当前结点的系数值
  23. qa->data.coef = sum;
  24. ha = qa;
  25. }else
  26. { //删除多项式PA中当前结点
  27. DelFirst(ha, qa);
  28. free(qa);
  29. }
  30. DelFirst(hb, qb);
  31. free(qb);
  32. qb = hb->next;
  33. qa = ha->next;
  34. break;
  35. case 1:
  36. DelFirst(hb, qb);
  37. InsFirst(ha, qb);
  38. qb = hb->next;
  39. ha = ha->next;
  40. break;
  41. }//switch
  42. }//while
  43. if(!ListEmpty(Pb))
  44. Append(Pa,qb);
  45. DestroyList(hb);
  46. }//AddPolyn

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

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


  
  1. void Insert(Polynomial &L,float c,int e)//系数c,指数e
  2. {
  3. Term * pre=L;
  4. Term * p=L->link;
  5. while(p && p->exp<e)//查找
  6. {
  7. pre=p;
  8. p=p->link;
  9. }
  10. if(p->exp==e)//如果有这一项
  11. {
  12. if(p->coef+c)//如果相加是0了,就删除节点
  13. {
  14. pre->link=p->link;
  15. free(p);
  16. }
  17. else//相加不是0,就合并
  18. {
  19. p->coef+=c;
  20. }
  21. }
  22. else//如果没这一项,插入就好了,链表插入写了很多遍了
  23. {
  24. Term * pc=new Term;//创建
  25. pc->exp=e;
  26. pc->coef=c;
  27. pre->link=pc;
  28. pc->link=p;
  29. }
  30. }

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

insert(c,乘系数,加幂)

 

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

 

 

 

 

 

 

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/82982642

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。