一元稀疏多项式计算器(数据结构)

1、摘要：本文是关于任一元稀疏多项式的求解问题的描述，文中使用链式存储结构(带表头结点的单链表)存储一稀疏元多项式，实现了多项式的建立，多项式的输出，多项式a和b相加，多项式a和b相减和求导等功能。鉴于C语言的优点，经过分析，将用C语言解决一元稀疏多项式的求解问题算法的描述。关键词：链表；函数；多项式；数据结构目录1 需求分析32 设计概要43 详细设计和实现53.1主函数53.2求导函数和求和函数53.3其他函数104 调试和操作说明125 总结156 致谢167 参考文献171需求分析课程题目：一元稀疏多项式计算器问题描述：设计一个一元多项式加法器基本要求：(1) 输入并建立多项式；(2)两个

2、多项式相加；(3)输出多项式：n, c1, e1, c2, e2, cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。(4)计算多项式在x处的值；(5)求多项式的导函数。软件环境：Windows，UNIX，Linux等不同平台下的Visual C+ 6.0硬件环境: 512MB内存,80Gb硬盘,Pentium4 CPU,CRT显示器。2概要分析本程序有五个函数：PolyNode *Input()(输入函数)；PolyNode *Deri(PolyNode *head)（求导函数）；PolyNode * Plus(PolyNode *A,Pol

3、yNode *B)（求和函数）；void Output(PolyNode*head)（输出函数）；int main()（主函数）本程序可使用带有附加头结点的单链表来实现多项式的链表表示，每个链表结点表示多项式的一项，命名为node，它包括两个数据成员：系数coef和指数exp，他们都是公共数据成员，*next为指针域，用链表来表示多项式。适用于不定的多项式，特别是对于项数再运算过程中动态增长的多项式，不存在存储溢出的问题。其次，对于某些零系数项，在执行加法运算后不再是零系数项，这就需要在结果多项式中增添新的项；对于某些非零系数项，在执行加法运算后可能是零系数项，这就需要在结果多项式中删去这些项

4、，利用链表操作，可以简单的修改结点的指针以完成这种插入和删除运算（不像在顺序方式中那样，可能移动大量数据项）运行效率高。3详细设计和实现（1）首先介绍主函数：int main()PolyNode *head_a,*head_b;int choice;head_a=new PolyNode;head_a->next=NULL;do system("cls");/清屏函数 Output(head_a); cout<<" _n" cout<<"|-1.输入公式-|n" cout<<"|-2

5、.求 导-|n" cout<<"|-3.两式求和-|n" cout<<"|-4.退出程序-|n" cout<<" n" cin>>choice; if (choice=1) head_a=Input(); else if (choice=2) head_a=Deri(head_a); /求导 else if (choice=3) head_b=Input();head_a=Plus(head_a,head_b);/求和 else if (choice=4) break; els

6、e cout<<"输入错误，重新输入：n"while(choice!=5);return 0;（2）由于此程序是二人合作完成，我在此程序中主要是完成求和和求导函数的设计。所以下面着重介绍下求和函数和求导函数。PolyNode *Deri(PolyNode *head)（求导函数）：流程图如下：NNYstart建立以head1为头指针的空链表，A指向后一接点建立以head2为头指针的空链表，p=head2q=B的第一个接点返回指针head1调用求和函数head1=head1+head2A指向后一接点q指向的接点与A指向的接点相乘，结果保存到head2后面，q指向后

7、一接点A!=NULLq!=NULLYENDPolyNode* Mul(PolyNode*A,PolyNode *B) 图3.1求导函数流程图求导函数部分代码：PolyNode *Deri(PolyNode *head) /求导PolyNode *p=head;while (p->next!=NULL)if(p->next->exp=0) p->next=NULL; /指数为零返回else p->next->coef*=p->next->exp; /系数乘以指数p->next->exp-; /指数减一p=p->next;retur

8、n head;用于对输入的多项式进行求导，求导在链表内进行计算，即运算完成链表的值改变，返回头指针。PolyNode * Plus(PolyNode *A,PolyNode *B)（求和函数）：流程图如下：startNYNYNYYNNYNYNY建立链表head，p=head，两头指针A、B均指向各自的nextA、 B为空A的指数大于B的指数A、B的系数互为倒数AB指数相等B为空A为空p->next=NULL将A的当前接点接到新链表后面，A后指A、B均后指将B接到p后面合并相同系数相同项，连接到新链表后面将A接到p后面将B的当前接点接到新链表后面，B后指如果AB都为空返回头指针ENDPol

9、yNode*Plus(PolyNode*A,PolyNode *B) 图3.2求和函数流程图本函数用于对多项式进行加法计算，需要运用存有两个多项式的头指针，前一头指针可是前一计算的计算结果，也可是调用输入函数，后一头指针是调用输入函数输入的多项式的头接点。经过计算得到一个新的链表，函数返回链表的头指针。求和函数部分代码PolyNode * Plus(PolyNode *A,PolyNode *B)/相加PolyNode *head,*p;head=new PolyNode;p=head;A=A->next;B=B->next; while(A!=NULL|B!=NULL)if(A=

10、NULL) p->next=B; break; /如果A空，把B后面的所有接点接到p之后if(B=NULL) p->next=A; break; /如果B空，把A后面的所有接点接到p之后 if(A->exp=B->exp) /如果两指数数相等，相加if(A->coef+B->coef!=0) p->next=new PolyNode; p=p->next; p->exp=A->exp; p->coef=A->coef+B->coef;A=A->next;B=B->next; continue; /如果两系

11、数互为倒数，不保存，后指，继续循环if(A->exp > B->exp) /A的指数大于B的指数p->next=new PolyNode;p=p->next;p->exp=A->exp;p->coef=A->coef;A=A->next; continue; /将A的当前接点接到新链表后面，A后指p->next=new PolyNode;p=p->next;p->exp=B->exp;p->coef=B->coef;B=B->next; /将B的当前接点接到新链表后面，B后指if (A=NUL

12、L&&B=NULL) /如果A B 都为空p->next=NULL;return head; /返回头指针（3）其他函数（同组的成员设计）#include <iostream>#include <process.h>using namespace std;typedef struct node float coef; /系数 int exp; /指数 struct node *next; /指针域 指向下一个系数不为0的子项 PolyNode;PolyNode *Input() /输入函数float c; /系数域int e; /指数域PolyNo

13、de *p,*q,*r,*head;cout<<"请输入多项式:n"cout<<"形式：系数1 指数1 系数2 指数2 系数3 指数3.0 0：n"head=new PolyNode; /建立头接点p=head;p->next=NULL;for (;)cin>>c>>e;if(c=0&&e=0) break; /结束输入if(c=0) continue; /从新输入，不保存if(head->next=NULL) /输入第一个接点p->next=new PolyNode;p=

14、p->next;p->coef=c,p->exp=e;p->next=NULL;continue;p=head;while(p->next!=NULL && e<=p->next->exp) p=p->next;/如果输入的指数小于p的下一个接点，p向后指if (e=p->exp) p->coef+=c;continue;/如果相等，直接加上去，继续循环q=new PolyNode;q->coef=c,q->exp=e;if (p->next!=NULL&&e>p->

15、next->exp)/如果p的后继接点的指数小于输入的指数，插入到p的当前接点之后r=p->next;p->next=q;q->next=r;continue;p->next=q;/如果输入的值小于所有接点，接在最后一个接点之后p=p->next; p->next=NULL;return head;输出函数void Output(PolyNode*head) /输出PolyNode*p;p=head->next;if(p=NULL) cout<<"当前没有公式或计算结果为0，请选1输入！n" return;if(p

16、!=NULL)cout<<"计算结果：n"cout<<p->coef<<"X"<<p->exp;p=p->next;while(p!=NULL)cout<<"+"<<p->coef<<"X"<<p->exp;p=p->next; cout<<endl;cout<<"如果想重新输入公式，请选1输入！nn"4调试与操作说明（1）当程序运行时，进入

17、主界面。如图： 图4.1主界面此时输入1-4选择操作（2）输入1后按回车出现： 图4.2输入主界面输入1 2 3 4 5 6 0 0后按回车之后 会出现界面： 图4.3输入后的界面（3）求导：输入2求导后按回车会出现结果： 图4.4 求导结果结果正确。（4）求和：如果进入图4.3后输入3后按回车会出现界面： 图4.5求和界面输入2 2 4 4 6 6 0 0 后结果会出来： 图4.6 求和结果结果正确。此系统在得到计算结果后可以直接用计算的结果进行下一步计算，如果不想用当前的结果，也可按“1”重新输入公式进行下一步计算 总结经过一个学期对数据结构的学习，使我对其有了很大的了解，也对C+进行了温

18、习和了解；在课程设计期间，我们每个人都做了一个课程设计，在这个过程中，遇到了不少困难，但最终还是在自己的努力和同学的帮助下完成了设计，也使我学到了不少。这个程序比较简单，在书上面有一道习题，而且有一些提示。我照着书上的结构体写下来，然后思考那三种计算因该用什么样的算法实现。前面的问题都很简单，但要操作的时候就困难了，因为有很多特殊的情况需要考虑，课程设计前后没多少时间，但是浪费了我几天的时间来想那些函数，不过还是在同学的帮助下解决了它。在求和函数中遇到了一些困难，但又在自己的努力和同学的帮助下迎刃而解。后来的程序流程图又花费了不少时间，不过总算完成了。现在才发现思维对于学习计算机的人来说是多么重要。程序设计是做完了，在做设计的过程我学到了不少，使我对