数据结构课程设计说明书

1、安徽理工大学数据结构课程设计说明书题目: 一元多项式计算 院 系： 计算机科学与工程学院专业班级： 数字媒体13-1班 学 号： 2013303102 学生姓名： 钱福琛 指导教师： 梁兴柱 2015年 1月 9 日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 学 号2013303102学生姓名钱福琛专业（班级）数字媒体13-1设计题目一元多项式计算设计技术参数系统平台：Windows 7/Windows XP开发工具：VC+6.0设计要求【基本要求】（1）建立多项式并输出；（2）多项式a和b相加，建立多项式a+b；输出相加的多项式（3）多项式a和b相减，建立多项式a-b。输出相

2、减的多项式（4）多项式a和b相乘，建立多项式a*b。输出相乘的多项式（5）用带表头结点的单链表存储多项式。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划2015年1月5日 对课程设计问题及要求做了深入分析,并建立程序大致框架2015年1月6日 对于main函数进行完善2015年1月7日 对于多项式存储进行完善2015年1月8日 进行多项式加减乘除的程序部分设计2015年1月9日 完善各程序并调试运行参考资料刘国钧,陈绍业,王凤翥. 图书馆目录M. 北京：高等教育出版社，1957指导教师签字教研室主任签字 2014年 11 月 10 日 学生姓名： 钱福琛 学号： 20

3、13303102 专业班级： 数字媒体13-1 课程设计题目： 一元多项式计算 指导教师评语： 成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩评定表目 录1 问题描述2 功能描述2.1 课题要求2.2 软件格式规定3 设计- 2 -3.1 相关函数介绍说明3.2 主程序的流程基函数调用说明4 程序设计- 5 -4.1 多项式存储的实现4.2 加减乘除算法4.2.1加法运算的实现4.2.2减法运算的实现4.2.3乘法运算的实现4.2.4除法运算的实现4.3 函数调用关系图5 运行测试1 问题描述1.1首先是确定结构化程序设计的流程图，利用已学过的数据结构来构造二个存储多项式的结构

4、，接着把输入，加，减，乘，除运算分成四个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块.2 功能描述2.1 课题要求 A. 支持一元多项式的运算器B. 能够正确输入并显示输入多项式的每一项C. 要求将输入的多项式F（X），G(X)可进行加，减，乘，除运算，并显示结果2.2 软件格式规定A输入的形式 :按程序菜单的数字选择输入，并按提示输入多项式。按照（系数 指数）的格式进行输入并以输入（0 0）作为结束输入的控制。 B. 程序所能达到的功能 :能够进行多项式的输入，显示，加，减，乘，除运算。C.输出的形式:按照多项式的数学表达式的形式输出，形如：

5、F(x)=X2+2X3-2X4-3X3-X1+103 设计3.1 相关函数介绍说明 （1）程序定义的数据结构类型为线性表的链式存储结构类型变量： typedef struct linknode（2）程序定义的其它函数：linnode *Sort(linnode *S);/多项式按指数从大到小排序linnode *CreateList(); /创建多项式Void ShowList(linnode *head) ; /显示多项式linnode *Copy(linnode *copy); /拷贝多项式（因为做减法运算时会破坏原来输入的多项式）linnode *SearchList(linnode *

6、head,int x);/查找函数Linnode *Mulr(linnode *s,linnode *p)/用一个节点去乘与一个多项式（辅助除法运算）Linnode *AddSame(linnode *head);/和并多项式的同类项linnode *Add(linnode *head1,linnode *head2); / 加法linnode *Mul(linnode *head1,linnode *head2); / 乘法linnode *Sub(linnode *head1,linnode *head2); / 减法Void Div(linnode *head1,linnode *hea

7、d2)/除法int main( )/主函数3.2 主程序的流程基函数调用说明（1）主程序的简要流程图选择界面菜单对应操作的数字结束执行完选择的功能后返回结果并回到程序主界面调用功能对应的函数main()图1 主程序流程图（2）各程序模块之间的层次（调用）关系 输入模块“CreateList（）”，首先按提示逐项输入多项式的每一项，当接收到“0 0”时终止输入，此时调用“Sort（）”进行按指数降序排列后直接返回多项式的链表头指针。 加法运算模块“Add（）”，首先将两个多项式连接成一个多项式，再调用“AddSame（）”函数进行合并连接后的多项式的同类项并返回头指针。减法运算程序模块“Sub(

8、 )”，首先判断多项式1是否为空，不为空时调用“SearchList（）”进行查找操作，查找到的结果与多项式1作减法后删除多项式2中查找到的对应项。多项式2中剩余的项取反后连接到多项式1的尾部，再调用“AddSame（）”进行合并同类项操作并返回头指针。 乘法运算程序模块“Mul( )”， 首先判断输入的多项式两个不为空时进行多项式相乘运算，并将结构存储在新创建的多项式中。再调用“AddSame（）”进行合并同类项后返回头指针。除法运算模块“Div”，首先判断第一个多项式的最高次数大于或等于第二多项式的最高次数，然后再用第一个多项式的第一项去除于第二个多项式的第一项，所得的商的第一项，然后调用

9、“Mulr（）”用商的第一项去乘第二个多项式，用第一个多项式减去乘得的多项式，所得的差多项式再与第二个多项式的最高指数项判断。直到第二多项式的最高次数项大于与之判断的多项式时结束运算，并调用“ShowList（）”输出相应的结果。 显示函数“ShowList（）”，首先调用“Sort（）”进行排序，再按格式输出多项式的每一项。4 程序设计4.1 多项式存储的实现 多项式是由若干项构成的一个数学式子，其每一项包含系数与指数。然而我们可以把每一项看成是一个节点，再由这些节点连接成多项式。根据所学数据结构，采用线性表的链式存储来存储多项式的每一个项的系数与指数。其结构为：typedef struct

10、 linknode /链表节点的结构体float coe; /系数int index; /指数struct linknode *next; linnode; 4.2 加减乘除算法 在多项式运算的程序设计中，每一部分都会调用一些其它函数来辅助完成运算（例如：对输入的多项式进行排序，查找，合并等），在这里主要说明加减乘除运算的程序设计，其它函数的程序设计和具体调用关系请查看程序清单。4.2.1加法运算的实现开始 加法计算还是比较容易实现的，将两个传递过来的多项式链表进行复制操作（加法运算会破坏原来两个链表的结构），再将复制出来的两链表进行连接操作，即将第一个多项式链表的尾指针next指向第二个链表

11、的第一个节点，最后进行合并同类项操作。 复制两个多项式连接两个多项式合并连接好的多项式的同类项返回合并同类项后的多项式头指针结束图2 加法运算原理图对于加法运算我们并不用考虑多项式是否为空的情况，为空时连接后合并同类项处理后仍然返回空的多项式。4.2.2减法运算的实现开始被减数是否为空 是被减数每一项查找减数与之对应的项 否 找到未找到加法操作，并将值赋给被减数 被减数与减数取反后连接 合并同类项 结束 图3 减法运算原理图4.2.3乘法运算的实现开始判断两个多项式是否都为空多项式两两相乘 否 合并同类项 结束 是图4 乘法运算原理图4.2.4除法运算的实现开始判断两个多项式是否都为空 判断最

12、高次幂被减数>=减数 否相除得商的第一项 是 乘与被除数被除数减去所得多项式得到的结果作为被除数输出商和余数否 结束 是图5 除法运算原理图在程序设计时应注意: 由于在输入多项式的时候就调用了Sort（）函数进行降序排序，因此在除法运算时并不需要从新排序。4.3 函数调用关系图此函数调用关系图主要描述了四则运算的实现、取反及实现各运算所要调用的函数，详情还请看程序清单。Sort()排序ShowList()显示输出SearchList()搜索SearchList()搜索SearchList()搜索SearchList()搜索节点AddSame()合并Negate()取反AddSame()合并AddSame()合并Mulr()