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

实习报告：1.5题 一元稀疏多项式计算器实习报告题目：设计一个一元稀疏多项式简单计算器班级：计科一班 姓名：康宇 学号： 完成日期：2013.4.15一、需求分析1、一元稀疏多项式简单计算器的功能是：1） 输入并建立多项式；2） 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 3） 多项式a和b相加，建立多项式a+b；4） 多项式a和b相减，建立多项式a-b。5） 计算多项式在x处的值；6） 求多项式a、b的导函数； 2、测试数据：1、(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7);2、(6x-3-x+4.4x2-1.2x9+1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x);3、(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5);4、(x+x3)+(-x-x3)=0;5、(x+x100)+(x100+x200)=(x+2x100+x200);6、(x+x2+x3)+0=x+x2+x3.二、概要设计 为实现上述程序功能，应以有序链表来表示多项式的系数和指数。定义线性表的动态分配顺序存储结构；建立多项式存储结构，定义指针*next利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。 1、元素类型、结点类型和指针类型：typedef struct LNode float xishu; /系数 int zhishu; /指数 struct LNode *next; LNode,*Linklist; 2、建立两个全局链表指针，Linklist List1=NULL;Linklist List2=NULL;用来存放两个多项式，然后在main（）函数里调用输入函数。 3、本程序包括7个模块 1）主程序： Void main()While(1)输出菜单；接受命令；处理命令；If（命令=退出）则程序退出；释放链表； 2）输入函数： Void Input() 调用插值函数In（List1）处理链表一； 调用插值函数In（List2）处理链表二；3)输出函数：Void Output()调用输值函数Out（List1）处理链表一；调用输值函数Out（List2）处理链表一； 4）相加函数： Void Add()if(List1节点指数 List2节点指数)输出List1节点;指针后移；else if(List1节点指数 List2节点指数)输出List1节点;指针后移；else if(List1节点指数 List2节点指数)输出List2节点;(系数要取负再输出)指针后移；Else两链表指针都后移； if(链表1到头) 输出链表2剩余的节点； else(即链表二到头) 输出链表1剩余的节点； 6）求值函数： void Calc() 输入x的值； 依次调用链表一的节点，求出单项式的值相加后输出； 7）求导函数： void Daohanshu() 输出多项式一的导函数； 三、详细设计#include #include #include typedef struct LNode /元素类型float xishu;int zhishu;struct LNode *next;LNode, *Linklist;Linklist List1=NULL;Linklist List2=NULL;Linklist In(Linklist L)/依次往链尾插Linklist p;float a;int b;Linklist head=(Linklist)malloc(sizeof(LNode);L=head;head-zhishu=0;/head-zhishu头结点放的是多项式的项数p=head;p-next=NULL;printf(请输入一个多项式：n);while(scanf(%f %d,&a,&b)&(a|b)/默认多项式是按指数由小到大输入/printf(%f %dn,a,b);(head-zhishu)+;/printf(%3dn,L-zhishu);Linklist q=(Linklist)malloc(sizeof(LNode);q-xishu=a;q-zhishu=b;if(p-next=NULL)p-next=q;q-next=NULL;p=head;elseif(p-next-zhishuzhishu)q-next=p-next;p-next=q;p=head;elsep=p-next;printf(您已成功输入一个多项式！n);return L;void Input()List1=In(List1);List2=In(List2);void Out(Linklist L)Linklist p;p=L-next;printf(此多项式有%3d项 ,L-zhishu);while(p!=NULL)/按指数由大到小输出printf(%0.1f %3d ,p-xishu,p-zhishu);p=p-next;printf(n);void Output()printf(第一个多项式为：n);Out(List1);printf(第二个多项式为：n);Out(List2);void Add()Linklist p1,p2;p1=List1-next;p2=List2-next;printf(相加后的多项式为：n);while(p1&p2)if(p1-zhishup2-zhishu)printf(%0.1f %3d ,p1-xishu,p1-zhishu);p1=p1-next;else if(p1-zhishuzhishu)printf(%0.1f %3d ,p2-xishu,p2-zhishu);p2=p2-next;elseprintf(%0.1f %3d ,p1-xishu+p2-xishu,p1-zhishu);p1=p1-next;p2=p2-next;if(p1=NULL)while(p2)printf(%0.1f %3d ,p2-xishu,p2-zhishu);p2=p2-next;elsewhile(p1)printf(%0.1f %3d ,p1-xishu,p1-zhishu);p1=p1-next;printf(n);void Sub()Linklist p1,p2;p1=List1-next;p2=List2-next;printf(相减后的多项式为：n);while(p1&p2)if(p1-zhishup2-zhishu)printf(%0.1f %3d ,p1-xishu,p1-zhishu);p1=p1-next;else if(p1-zhishuzhishu)printf(%0.1f %3d ,-p2-xishu,p2-zhishu);p2=p2-next;elseif(p1-xishu-p2-xishu!=0)printf(%0.1f %3d ,p1-xishu-p2-xishu,p1-zhishu);p1=p1-next;p2=p2-next;if(p1=NULL)while(p2)printf(%0.1f %3d ,-p2-xishu,p2-zhishu);p2=p2-next;elsewhile(p1)printf(%0.1f %3d ,p1-xishu,p1-zhishu);p1=p1-next;printf(n);void Calc()int x;double sum=0;Linklist p;printf(请输入x的值：);scanf(%d,&x);p=List1-next;while(p)sum+=p-xishu*pow(x,p-zhishu);p=p-next;printf(多项式1在x处的值为：%0.1lf,sum);printf(n);void Daohanshu()Linklist p;p=List1-next;printf(多项式1的导函数为：n);while(p)printf(%0.1f %3d ,p-xishu*p-zhishu,p-zhishu-1);p=p-next;printf(n);int main()int num;while(1)printf(-n);printf(1-输入并建立多项式;n);printf(2-输出其指系数排列;n);printf(3-多项式相加;n);printf(4-多项式相减;n);printf(5-计算多项式在x处的值;n);printf(6-求多项式a的导函数a;n);printf(0-退出n);printf(-n);printf(请输入您要选择的功能：);scanf(%d,&num);switch(num)case 1:Input();break;/输入函数case 2:Output();break;/输出函数case 3:Add();break;/函数相加case 4:Sub();break;/函数相减case 5:Calc();break;/计算函数在x处的值case 6:Daohanshu();break;/求函数的导函数case 0:exit(1);default :printf(输入错误，请重新输入！);free(List1);free(List2);return 0;四、调试分析1.由于链表是设置成为全局变量，所以任意函数都可以修改它，存在一定风险性。但这也为后来的函数方便了，所有的函数统一没有参数。2.刚开始时曾忽略了一些变量的类型以及没有考虑到指针的返回问题，使调试程序浪费了一定的时间。今后应重视确定参数的变量和赋值属性的区分和标识