数据结构(c语言)一元稀疏多项式计算器.doc

实验报告一题目:编制一个一元稀疏多项式计算器班级:1302018姓名:王雪学号:**********完成日期:、需求分析1、一元稀疏多项式简单计算器的功能是:;,输出形式为整数序列:n,c1,e1,c2,e2,………cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;,建立多项式a+b;,建立多项式a-b。2、设计思路:;,定义指针*。每次输入一项的系数和指数,,即在计算机终站上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运行命令;最后根据相应的输入数据(滤去输入中的非法字符)建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为:c1x^e1+c2x^e2+…+cnx^en3、设计思路分析要解决多项式相加,必须要有多项式,所以必须首先建立两个多项式,在这里采用链表的方式存储链表,所以我将结点结构体定义为序数coef指数expn指针域next运用尾插法建立两条单链表,以单链表polynp和polynh分别表示两个一元多项式a和b,a+b的求和运算等同于单链表的插入问题(将单链表polynp中的结点插入到单链表polynh中),因此“和多项式”中的结点无须另生成。为了实现处理,设p、q分别指向单链表polya和polyb的当前项,比较p、q结点的指数项,由此得到下列运算规则:①若p->expn<q->expn,则结点p所指的结点应是“和多项式”中的一项,令指针p后移。②若p->expn=q->expn,则将两个结点中的系数相加,当和不为0时修改结点p的系数。③若p->expn>q->expn,则结点q所指的结点应是“和多项式”中的一项,将结点q插入在结点p之前,且令指针q在原来的链表上后移。二、概要设计为实现上述程序的功能,应以带头结点的单链表表示多项式。为此,需要一个抽象数据类型:单链表。{数据对象:D={ai|ai∈TermSet,i=1,2,…,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系:R1={<ai-1,ai>ai-1,ai∈D且ai-1中的指数值<ai中的指数值,i=2,…,n}基本操作:CreatLinkList(&p,m)操作结果:输入m项的系数和指数,建立一元多项式p。DestoryLinkList(&p)初始条件:一元多项式p已存在。操作结果:(p)初始条件:一元多项式p已存在。操作结果:(&pa,&pb)初始条件:一元多项式pa和pb已存在。操作结果:完成多项式的相加运算,即:pa=pa+pb,(&pa,&pb)初始条件:一元多项式pa和pb已存在。操作结果:完成多项式的想减运算,即:pa=pa-pb,并销毁一元多项式pb.}:1)主程序模块:Voidmain(){初始化;输出菜单;While(1){接受命令;处理命令;}(循环一直为真直至接受退出命令);2)单链表单元模块——实现单链表的抽象数据类型;3)结点结构单元模块——定义单链表的结点结构。三、、结点类型和指针类型typedefintStatus;typedefintElemType;typedefstructLNode{  float   coef;                    //系数  ElemType expn;                 //指数  struct  LNode*next;           }LNode,*LinkList;StatusMakeNode(LinkList&p,LinkListhead){//分配由p指向下一个多项式的头结点head、后继为空的结点,并返回TRUE,//若分配失败,则返回FALSEp=(LinkList)malloc(sizeof(structLNode));if(!p)returnfalse;p=head;p->next=null;returnture;voidFreeNode(LinkList&p){//释放p所指结点free(q1);      q1=q2;      q2=q2->next;}:voidInsert(Li