数据结构课程设计整理版.docx

数据结构课程设计

第一篇：数据结构课程设计一、课程题目：一元稀疏多项式计算器二、需求分析1、一元稀疏多项式简单计算器的功能是：1.1输入并建立多项式；1.2输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,„„„cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；1.3多项式a和b相加，建立多项式a+b；1.4多项式a和b相减，建立多项式a-b。2、设计思路:2、设计思路：2.1定义线性表的动态分配顺序存储结构；2.2建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；根据相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。3、程序执行的命令包括：1）输入多项式a；2）输入多项式b;3）求a+b;4)求a-b；5）求a*b；6）求a的导数；7）求b的导数；8）退出程序。4、测试数据：1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^-3-x);3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);4、(x+x^3)+(-x-x^3)=0;5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);6、(x+x^2+x^3)+0=x+x^2+x^3.7、互换上述测试数据中的前后两个多项式三、概要设计为了实现上述功能需用带表头结点的单链表存储多项式。为此需要两个抽象的数据类型：线性表和多项式。1.有序表的抽象数据类型定义为：ADTList{数据对象：D={ai|ai∈Elemset,i=1,2,„，n,n≥0}数据关系：R1={|ai-1,ai∈D,i=2,„,n}基本操作：PolyNode*p,*q,*r,*head;操作结果:构造一个空的线性表。Listinsert(&L,i,e)初始条件:线性表L存在，0≤i≤L的元素个数。操作结果:在L中第i个位置之后插入新的结点e。}ADTList2、多数据类型定义为：ADTPolynomial{数据对象:D={ai,bi|ai为不为0的实数，bi为整数，i=2,„,n}数据关系:R1={ai，bi}基本操作：PrintPolyn(Polynp)操作结果:输出多项式p。DestroyPolyn(Polynp)操作结果:销毁多项式p。PolynCreatePolyn(Polynhead,intm)操作结果:创建一个m项的多项式。PolynAddPolyn(Polynpa,Polynpb)初始条件:多项式链表pa,pb存在。操作结果:创建一新多项式链表p，其结点为pa，pb相加。PolynSubtractPolyn(Polynpa,Polynpb)初始条件:多项式链表pa，pb存在。操作结果:创建一新多项式链表p，其结点为怕pa，pb相减。ValuePolyn(Polynhead,intx)操作结果:输入x值，计算并返回多项式的值}ADTPolynomial四、详细设计1、元素类型、结点类型和指针类型typedefintStatus;typedefstruct{intcoef;intexpn;}Term;typedefTermElemType;typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;2、主函数和其他函数voidmain(){intm,n,a,x;intflag;Polynomialpa,pb,pc;printf(“欢迎使用多项式操作程序n”);//输出菜单printf(“n1:创建多项式an”);printf(“n2:创建多项式bn”);printf(“n3:输出多项式an”);printf(“n4:输出多项式bn”);printf(“n5:输出a+bn”);printf(“n6:输出a-bn”);printf(“n7:输出a的导数n”);printf(“n8:输出b的导数n”);printf(“n9:代入x的值计算an”);printf(“n10:代入x的值计算bn”);printf(“n11:输出a*bn”);printf(“n12:退出程序n”);while(a){printf(“n请选择操作：”);scanf(“%d”,&flag);s