数据结构实验报告一元多项式

数据结构课程设计报告课 题: 一元多项式 _XX学 号：8 专业_ XXXX指导 XXXX设计时间： 2015年12月30日星期三 评阅意见：评定成绩： 指导老师签名： 年 月 日15 / 15目录一、 任务目标 3二、 概要设计 4三、 详细设计 6四、 调试分析8五、 源程序代码8六、 程序运行效果图与说明15七、 本次实验小结16八、 参考文献 16一丶任务目标分析 a.能够按照指数降序排列建立并输出多项式b.能够完成两个多项式的相加,相减,并将结果输入要求：程序所能达到的功能： a.实现一元多项式的输入；b.实现一元多项式的输出； c.计算两个一元多项式的和并输出结果； d.计算两个一元多项式的差并输出结果；除任务要求外新增乘法：计算两个一元多项式的乘积并输出结果2输入的形式和输入值的围：输入要求：分行输入,每行输入一项,先输入多项式的指数,再输入多项式的系数,以0 0为结束标志,结束一个多项式的输入。输入形式：2 3-1 23 01 20 0输入值的围：系数为int型,指数为float型3输出的形式：第一行输出多项式1；第二行输出多项式2；第三行输出多项式1与多项式2相加的结果多项式；第四行输出多项式1与多项式2相减的结果多项式；第五行输出多项式1与多项式2相乘的结果多项式二、概要设计程序实现a. 功能：将要进行运算的二项式输入输出；b. 数据流入：要输入的二项式的系数与指数；c. 数据流出：合并同类项后的二项式；d. 程序流程图：二项式输入流程图；e. 测试要点：输入的二项式是否正确,若输入错误则重新输入。流程图：开始申请结点空间输入二项式各项的系数 x, 指数 y输入二项式的项数输出已输入的二项式是否输入正确合并同类项结束是否三、详细设计1：存储结构 一元多项式的表示在计算机可以用链表来表示,为了节省存储空间,只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项,它包含三个域,分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表,对一元多项式的运算中会出现的各种可能情况进行分析,实现一元多项式的相加、相减操作。2：数据链表由于采用链表的方法,我们可以建立3条链；一条用于存放多项式HA,一条用于存放多项式HB,还有一条用于存放新形成的HC。此外,我们的程序应具备以下几个功能：建立链表,撤销链表,打印链表,按要求插入一个新的结点,复制链表；为了使上面程序结构分析进一步细化,为了使程序结构更加清晰,我们可以把上面的容都编写成函数形式。1、建立链表该程序建立链表的函数与大多数建立链表的操作基本一致,但是由于实体是一元多项式的关系。我们更希望,在处理客户输入的数据的同时,能对数据进行适当的处理。也就是数学上所说的,对一元多项式进行化简,并按照降幂排序。由于在前面的练习中,我们得知,在链表中插入一个结点的函数,具有对链表的成员进行排序与合并的功能。如此一来,我们可以巧妙地处理,在建立链表的同时,调用在链表中插入一个结点的函数,对新建立的链表进行化简。 该函数的算法描述如下；声明指针变量,并作为头指针的指针变量赋初值NULL；创建一个新的结点,并输入链表的信息；若输入的系数值与函数值同不为0时,调用在链表中插入一个结点的insert函数,将结点插入链表中；若还要继续插入结点,转到步骤2继续进行；否则,程序结束,把头指针返回主程序。2、撤销链表撤销链表是为了把链表所占用的地址回收起来,防止造成浪费。我们该程序可以采用从链表的始端逐步销去结点。在这个过程中,我们需要链表的头地址作为形式参数,还需要建立一个指针用来指向新头地址。该函数的算法描述如下：指针变量；并把头地址指针赋给新指针变量；把头地址指针指向下一个结点；删除新指针变量；若还要继续删除结点,转到步骤1继续执行；否则,结束程序。3、按要求插入一个新的结点由于前面的建立链表的creat函数,调用了该函数,所以我们这个函数的设计思想也明朗多了,由于建立的链表是有序的,并且需要合并指数相同的结点,所以要新结点需要按指数值降幂的顺序插入链表中。判断链表是否为空,如果为空则直接插入即可；否则按照要插入结点指数值的大小在链表中寻找他要插入的位置,对于插入位置有第一个节点、最后一个结点和链表中间这三种情况分别进行处理。函数的形式参数：链表的头地址,指向要插入结点的指针；返回结果：插入结点后新链表的头地址。该函数的算法描述如下：声明指针变量并令它指向连头结点；判断指向要插入结点的指针是否为空；如果是,则不需要插入新结点,直接返回头地址,程序结束；否则再判断链表是否为空；如果是,则直接插入结点,然后返回链表的头地址,程序结束；否则,在链表中寻找待插入结点的插入位置：1,若链表中存在着与插入的结点的指数相同的情况,我们依然插入链中,只是把该结点的系数修改为0,把链中的结点系数修改为两系数之和。 2,若链表中不存在着与插入的结点的指数相同的情况,我们正常地插入链中。返回插入结点后链表的头地址,程序结束。4、主函数主函数主要负责输出界面的指引语句,并合理地调用各个函数,还要有适当的循环操作以及停止循环的语句,以致可以方便地达到合并两个一元多项式的功能。四、调试分析1调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:在输入诸如0,3,2,0时,程序无常运行或总是出错.解决：对指数或系数为0的情况应单独讨论。为此,建立了delZeroCoef函数来解决问题。2算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为Om+n,减法运算的时间复杂度为O,其中m,n分别表示二个一元多项式的项数。问题和改进思想：在设计该算法时,出现了一些问题,例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值,不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果,而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列,可在数据的输入后先做一个节点的排序函数,通过对链表排序后再进行之后加减运算。五、 源程序代码#include #include #include typedef struct LNode float coef; int expn; struct LNode *next; LNode; LNode* InitPolyn ifn return NULL; LNode *h = La = mallocsizeof, *Lb; La-coef = 0.0; int i; printf; for i = 1; i scanfcoef,&La-expn; ifcoef Lb = La; La = La-next = mallocsizeof; Lb-next = NULL;free; return h; LNode* selsort LNode *g, *La, *Lb; if return NULL; float f; int i, fini = 1; fornext&fini;g = g-next fini = 0; fornext;Lb;La = La-next,Lb = Lb-next if expn expn f = La-coef;i = La-expn; La-coef = Lb-coef;La-expn = Lb-expn; Lb-coef = f;Lb-expn = i; fini = 1; fornext;La; ifexpn=La-expn g-coef += La-coef; g-next = La-next; Lb = La; La = La-next; free; else ifnext g = g-next; La = La-next; return h; void PrintfPoly LNode *Lb = La; if putchar; return; ifcoef!=1 printfcoef; ifexpn=1 putchar; else ifexpn printfexpn; else ifexpn putchar; else ifexpn=1 putchar; else printfexpn; Lb = Lb-next; while ifcoef 0 putchar; ifcoef!=1 printfcoef; ifexpn=1 putchar; else ifexpn printfexpn; else ifexpn putchar; else ifexpn=1 putchar; else printfexpn; Lb = Lb-next; Compare if expn expn return -1; if expn b-expn return 1; return 0; LNode* AddPolyn LNode *h, *qa = Pa, *qb = Pb, *La, *Lb; float sum; h = La = mallocsizeof; La-next = NULL; while switch Compare case -1: La-next = qb; La = qb; qb = qb-next; break; case 0: sum = qa-coef + qb-coef; if La-next = qa; qa-coef = sum; La = qa; qa = qa-next; else Lb = qa; qa = qa-next; free; Lb = qb; qb = qb-next; free; break; case 1: La-next = qa; La = qa; qa = qa-next; break; if La-next = qa; if La-next = qb; Lb = h; h = h-next; free; return h; LNode* Add int n; puts; scanf; Pb = InitPolyn; Pb = selsort; PrintfPoly; ifcoef0 printf; PrintfPoly; Pa = AddPolyn; printf; Pa = selsort; PrintfPoly; return Pa; LNode* SubtractPolyn LNode *La = Pb; while La-coef *= -1; La = La-next; return AddPolyn; LNode* Subtract int n; puts; scanf; Pb = InitPolyn; Pb = selsort; PrintfPoly; printf; putchar;PrintfPoly;putchar; Pa = SubtractPolyn; printf; Pa = selsort; PrintfPoly; return Pa; LNode* MultiplyPolyn if return NULL; LNode *pa = Pa, *p, *q, *r, *s, *t; r = p = mallocsizeof; while p-coef = pa-coef; p-expn = pa-expn; q = p; p = p-next = mallocsizeof; pa = pa-next; q-next = NULL; free; pa = Pa; t = s = mallocsizeof; while q = s; s = s-next = mallocsizeof; pa = pa-next; q-next = NULL; free; pa = Pa; while pa-coef *= Pb-coef; pa-expn += Pb-expn; pa = pa-next; Pb = Pb-next; while p = r; s = t; while s-coef = p-coef * Pb-coef; s-expn = p-expn + Pb-expn; p = p-next; s = s-next; Pa = AddPolyn; Pb = Pb-next; return Pa; LNode* Multiply int n; puts; scanf; Pb = InitPolyn; Pb = selsort; putchar;PrintfPoly;putchar; printf; putchar;PrintfPoly;putchar; printf; Pa = MultiplyPolyn; Pa = selsort; PrintfPoly; return Pa; void main LNode *A,*B; char s2; int i,n; printf; printf; printf; printf;puts; scanf; A = InitPolyn; A = selsort; PrintfPoly; p: puts; getchar; q: gets; ifs1!=0 | !isdigit puts;goto q; i = *s-48; switch case 1:A = Add;goto p; case 2:A = Subtract;goto p; case 3:A = Multiply;goto p; case 4:break;default:puts;goto q;六、程序运行效果图与说明例：x2+3x4 按照需要操作的多项式输入第1个多项式的项数例中多项式项数为2,输入2,回车； 依次输入两个非零项,两个项之间用空格间开即可,每项输入,前一个为系数,后一个为指数,例中多项式第一项系数为1,输入1,空格,指数为2,输入2,空格,第二项系数为3,输入3,空格,指数为4,输入4,回车；即显示x2+3x4例：计算 与 的乘积（1） 选择需要操作的运算,例如要计算多项式乘多项式x2+3x4,选择3,回车；（2） 再按照步骤2输入多项式,回车；（3） 输出X= 21x12+22x10+5x8七、本次实验小结通过本次学习制作一元多项式的实验报告,我发现了自己存在的不足,同时也知道了学无止境,亲自动手,使我的实际操作有了很大提升,通过跟室友同学之间的交流,弄清楚了许多知识点,这也是值得高兴的,但还有一些无法得到解决,我希望自己在以后的程序设计中更进一步,如果我们好好利用,专业课程对我们以后是有莫大帮助的在这里再一次感帮助过我的同学,互相学习才能取长补短。八、参考文献数据结构C语言版 严蔚敏编数据结构与算法分析Weiss著大话数据结构 程杰编 以及网络上有关数据结构的学习