张扣(基于链表的多项式的计算)

《张扣(基于链表的多项式的计算)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学号13080101462014-2015学年第一学期《数据结构》课程设计报告基于单链表的多项式的加减法题目：的设计专业：计算机科学与技术班级：13计科（1）班姓名：张扣学号：1308010146指导教师：陈茅成绩：计真机与信息工超系工零—四年十—用工十五9H录1•设计要求12.愀娶坟计12.1.存储结构12.2.基本算法23.详细设计53.1.根据题H要求采用单连表存储结构53.2.函数的调用关系层次结构64.设计结果与分析64.1.测试的数据及结果64.2.算法的时间复杂度及改进75.心得体会76.88参考文献8附录源代码91设计要求建立一元多项式并按照

2、指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果。2概要设计2.1存储结构一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式屮系数非零的项。链表屮的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。单连表的抽象数据类型定义：ADTList{数据对象:D={ai

3、aiEElemSet,i=l,2,…，n,n>0}数据关系:Rl={<

4、ai~l,ai>

5、ai-1,aiED,i:2,…，n}基木操作：InitList(&L)//操作结果：构造一个空的线性表CreatPolyn(&L)//操作结果：构造-个以单连表存储的多项试DispPolyn(L)//操作结果：显示多项试Polyn(&pa,&pb)//操作结果：显示两个多项试相加，相减的结果}ADTList木程序含模块：typedefstructLNode//定义单链表{}LNode,*LinkList;voidInitList(LinkList&L)//定义一个空表{}voidCreatPolyn(LinkList&L)//用单链表定义一

6、个多项式；{}voidDispPolyn(LinkListL)//显示输入的多项式{}voidPolyn(LinkList&pa,LinkList&pb){}voidmain(){//定义一个車连表；cout<

7、：要输入的多项式的系数与指数。(3)数据流出：合并同类项后的多项式。(1)程序流程图：多项式输入流程图如图1所示。(1)测试要点：输入的多项式是否正确，若输入错误则重新输入。结束图2输入与输出2、多项式的加法(1)功能：将两多项式相加。(2)数据流入：输入函数。(3)数据流出：多项式相加后的结果。(4)程序流程图：多项式的加法流程图如图2所示。(5)测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。开始合并同类项结束图3多项式的加法3、多项式的减法(1)功能：将两多项式相减。(2)数据流入：调用输入函数。(3)数据流出：多项式相减后的结果。(4

8、)程序流程图：多项式的减法流程图如图3所示。(5)测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。合并同类项图4多项式的减法3详细设计3.1.根据题0要求采用单连表存储结构typedefstructLNode//定义单链表{}LNode,*LinkList;voidInitList(LinkList&L)//定义一个空表{}voidCreatPolyn(LinkList&L)//用单链表定义一个多项式；{}voidDispPolyn(LinkListL)//显示输入的多项式{}voidPolyn(LinkList&pa,LinkList&pb

9、){}3.2.主函数mainvoidmain(){LNode钆1，*L2;Polyn(LI,L2);}函数的调用关系层次结构多项式Polyn用革链表定义多项式CreatPolyn定义一个空表InitList显示输入的多项式DispPolyn}4设计结果与分析采用单连表形式按照指数降序排列建立并输出多项式；在相加，相减的过程中如果指数相同就执行系数相加，相减，否则就把大的项直接写入。完成两个多项式的相加、相减;将从新得到的单连表结果输出；该算法的时间复杂度为两个多项式的项式之和。测试的数据及结果2212313212^=辦^=^=^:irnyinrirn匕m

10、o日44J1?IJ1?与与与与与BB魏级数:3系系系