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

实验报告一题目：编制一个一元稀疏多项式计算器班级：1302018姓名：王雪学号：13020188030完成日期：2014.4.5一、需求分析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.1定义线性表的动态分配顺序存储结构；2.2建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思路分析要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为序数coef指数expn指针域next运用尾插法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polynp中的结点插入到单链表polynh中），因此“和多项式”中的结点无须另生成。为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：①若p-expnq-expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。②若p-expn=q-expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。③若p-expnq-expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。二、概要设计为实现上述程序的功能，应以带头结点的单链表表示多项式。为此，需要一个抽象数据类型：单链表。2.1单链表的抽象数据类型定义ADTLinkList{数据对象：D={ai|ai∈TermSet,i=1,2,…,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1={ai-1,aiai-1,ai∈D且ai-1中的指数值ai中的指数值,i=2,…,n}基本操作：CreatLinkList(&p,m)操作结果：输入m项的系数和指数，建立一元多项式p。DestoryLinkList(&p)初始条件：一元多项式p已存在。操作结果：销毁一元多项式p.PrintLinkList(p)初始条件：一元多项式p已存在。操作结果：打印输出一元多项式p.AddLinkList（&pa,&pb）初始条件：一元多项式pa和pb已存在。操作结果：完成多项式的相加运算，即：pa=pa+pb,并销毁一元多项式pb.SubtractLinkList(&pa,&pb)初始条件：一元多项式pa和pb已存在。操作结果：完成多项式的想减运算，即：pa=pa-pb,并销毁一元多项式pb.}ADTLinkList2.2本程序包括个模块：1）主程序模块：Voidmain（）{初始化；输出菜单；While（1）{接受命令；处理命令；}（循环一直为真直至接受退出命令）；2）单链表单元模块——实现单链表的抽象数据类型；3）结点结构单元模块——定义单链表的结点结构。三、详细设计3.1元素类型、结点类型和指针类型typedefintStatus;typedefintElemType;typedefstructLNode{floatcoef;//系数ElemTypeexpn;//指数structLNode*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;}3.2单链表的基本操作设置如下：voidInsert(LinkListp,LinkListh)；//将节点p插入到多项式链表hLinkListCreateLinkList(LinkListhead,intm);//建立一个头指针为head、项数为m的一元多项式,并返回该多项式的头结点；//若分配空间失败，则返回FALSEvoidDestroyLinkList(LinkListp);//销毁多项式pvoidPrintLinkList(LinkListP);//输出构造的一元多项式PStatuscompare(LinkLista,LinkListb)//节点进行比较:a的指数b的指数return1;a的指数==b的指数return0;a的指数b的指数return-1.LinkListAddLinkList(LinkListpa,LinkListpb)//求解并建立多项式a+b，返回其头指针LinkListSubtractLinkList(LinkListpa,LinkListpb)//求解并建立多项式a-b，返回其头指针其中部分操作的伪码如下：LinkListCreateLinkList(LinkListhead,intm){p=head=(LinkList)malloc(sizeof(structLNode));head-next=NULL;for(i=0;im;i++){p=(LinkList)malloc(sizeof(structLNode));//建立新结点以接收数据printf(请输入第%d项的系数与指数:,i+1);scanf(%f%d,&p-coef,&p-expn);Insert(p,head);//调用Insert函数插入结点}returnhead;}//CreateLinkListStatuscompare(LinkLista,LinkListb){if(a&&b){if(!b||a-expnb-expn)return1;elseif(!a||a-expnb-expn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}//comparefloatValueLinkList(LinkListhead,intx){//输入x值，计算并返回多项式的值for(p=head-next;p;p=p-next){t=1;for(i=p-expn;i!=0;)//i为指数的系数pow(x,i){if(i0){t/=x;i++;}//指数小于0，进行除法else{t*=x;i--;}}//指数大于0，进行乘法sum+=p-coef*t;}returnsum;}//ValueLinkListLinkListMultiplyLinkList(LinkListpa,LinkListpb){//求解并建立多项式a*b，返回其头指针LinkListqa=pa-next;LinkListqb=pb-next;hf=(LinkList)malloc(sizeof(structLNode));//建立头结点hf-next=NULL;for(;qa;qa=qa-next){for(qb=pb-next;qb;qb=qb-next){pf=(LinkList)malloc(sizeof(structLNode));pf-coef=qa-coef*qb-coef;pf-expn=qa-expn+qb-expn;Insert(pf,hf);}//调用Insert函数以合并指数相同的项}returnhf;}//MultiplyLinkList3.3主函数和其他函数的伪码算法voidmain(){//主函数Initiation();//多项式初始化PrintCommand();//输出菜单while(1){//循环一直为真知道选择j||J即退出命令时，程序退出printf(\n请选择操作：);scanf(%c,&flag);Interpter(flag);//具体的操作命令}}//mainvoidInitiation(){printf(请输入a的项数:);scanf(%d,&m);pa=CreateLinkList(pa,m);//建立多项式aprintf(请输入b的项数:);scanf(%d,&n);pb=CreateLinkList(pb,n);//建立多项式bprintf(多项式已创建\n);}//InitiationvoidPrintCommand(){//输出菜单显示键入命令的提示信息；Printf（’A’,’B’,’C’,’D’,’E’）;}//PrintCommandvoidInterpter(charflag){//具体的操作命令switch(flag){case'A':case'a':{PrintLinkList(pa);break;}case'B':case'b':{PrintLinkList(pb);break;}case'C':case'c':{AddLinkList(pa,pb);PrintLinkList(pc);break;}case'D':case'd':{SubtractLinkList(pa,pb));PrintLinkList(pc);break;}case'E':case'e':{DestroyLinkList(pa);DestroyLinkList(pb);exit(0);}default:printf(\n您的选择错误，请重新选择!\n);}}//Interpter函数说明：Initiation();//多项式初始化PrintCommand();//输出菜单Interpter();//具体的操作命令PrintLinkList();//打印多项式(降序输出)AddLinkList();//两个多项式相加SubtractLinkList();//两个多项式相减DestroyLinkList();//销毁多项式compare();//两个节点比较CreateLinkList();//创建多项式Insert();//将节点插入已知多项式中四、源程序#includestdio.h#includemalloc.h#includestdlib.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;typedefstructLNode{floatcoef;//系数ElemTypeexpn;//指数structLNode*next;}LNode,*LinkList;/*全局节点初始化多项式节点为空*/staticLinkListpa=NULL;staticLinkListpb=NULL;staticLinkListpc=NULL;/*将节点p插入到多项式链表h*/voidInsert(LinkListp,LinkListh){if(p-coef==0)free(p);//系数为0的话释放结点else{LinkListq1,q2;q1=h;q2=h-next;while(q2&&p-expnq2-ex