题目1-一元多项式的加法、减法、乘法的实现-报告(共56页).docx

《题目1-一元多项式的加法、减法、乘法的实现-报告(共56页).docx》由会员分享，可在线阅读，更多相关《题目1-一元多项式的加法、减法、乘法的实现-报告(共56页).docx（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上理学院课程设计说明书课 程 名 称: 数据结构与算法A设计实践 课 程 代 码: 题 目 一:一元多项式加法、减法、乘法 年级/专业/班: 2013/信科/2班 学 生 姓 名: 冯金慧 学 号: 09 开 始 时 间: 2015 年 12 月 28 日完 成 时 间: 2016 年 01 月 10 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日专心-专注-专业数据结构与算法A设计实践任务书学院名称： 理学院 课程代码：_专业： 信科 年级： 2012 一、 设计题目 一元

2、多项式的加法、减法、乘法的实现（限最多1人完成）二、 主要内容 完成一无多项式的基本运算功能。三、具体要求及提交的材料设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn 请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)Bn(x)。 要求： 1) 首先判定多项式是否稀疏2) 分别采用顺序和动态存储结构实现；3) 结果M(x)中无重复阶项和无零系数项；要求输出结果的升幂和降幂两种排列情况测试数据及测试结果请在上交的资料中写明；必须上机

3、调试通过l按数据结构课程设计大纲中的要求完成课程设计报告格式。设计结束后，每个学生必须上交的材料有：1 课程设计报告打印稿一份 2课程设计的源代码电子文档一份四、主要技术路线提示稀疏的多项式最好采用链式存储结构；两式相减与相加的算法是一致的，只是减式的数据项反号；两式相乘是两式相加的变形。五、进度安排共计两周时间，建议进度安排如下：1 选题，应该在上机实验之前完成 2. 需求分析、概要设计可分配4学时完成2 详细设计可分配4学时 4. 调试和分析可分配10学时。2学时的机动，可提前安排部分提前结束任务的学生答辩六、 推荐参考资料1. 冯博琴 等编著，软件技术基础（修改版），西安交通大学出版社，

4、19972. 严蔚敏 等著，数据结构，清华大学出版社，20033. 李芸芳 等著，软件技术基础（第二版），清华大学出版社，20004. 徐孝凯 等著，数据结构（C语言描述），清华大学出版社，2004指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日目 录摘 要一元多项式计算是用C语言设计一个一元多项式简单计算机，它能够实现按指数降幂排列或者按指数升幂排列建立并输出多项式，并且能够完一元多项式的四则运算，并将其运算结果输出的功能。一元多项式的存储方式分为静态数组存储和动态链表存储两种方式，两种方式的特点各不相同，顺序存储简单明了，但是缺乏灵活性，当多项式为稀疏多项式时，顺序存储则会浪

5、费许多存储空间，链式存储动态分配内存，但操作起来比顺序存储稍微复杂一些，所以具体内容具体分析，该选择哪一种方式进行存储还需进一步分析；通过一元多项式链式存储和顺序存储的比较与体会，可以体会到对一元多项式链式存储和顺序存储各自的的优缺点和适用性。一元多项式的运算，包含四个方面，多项式的加、减、乘、除，然而那，在具体计算中，我们需要考虑很多因素。首先，我们需要判断多项式是否稀疏，其次，考虑对多项式的存储方式（顺序存储或者链式存储），并且，我们还需要保证在计算结果中，不能有重复阶的出现和零项系数的出现，在输出结果时，我们可以让其升序或者降序输出。 本程序用VS2010编写，可以实现对多项式的加减乘的

6、运算，采用顺序存储和链式存储两种方式分别可以进行多项式的加、减、乘的运算以及判断该多项式是否稀疏，最后再将运算结果以升序或者降序排列情况输出。关键词：多项式，顺序存储，链式存储，升序降序引 言1问题的背景分析 为了更好的学习数据结构这一门理论和实践性均较强的基础课程，熟练掌握理论知识的同时更需要加强上机的实践。本课程就是要达到理论和实践相互结合，培养学生的动手能力，在实践中理解各种算法，在创作中提升，使我们能够在数据结构课程中，学会数据结构和算法设计解决问题的思想。1.1问题的提出 本课程设计主要是探究一元多项式的四则运算，而与此同时，首先，需要我掌握和理解的是对一元多项式的不同的存储方式（链

7、式存储和顺序存储）中，如何有效的对其进行加、减、乘的运算。其次，需要解决的问题就是给定一个一元多项式，要怎么去判断多项式的稀疏和稠密性。再者，打印多项式时可如何进行升幂和降幂的打印出多项式。这些问题都需要我逐一解决。C语言C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。C语言发展过程1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。19

8、77年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本可移植的C语言编译程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming Language，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。1.2任务与分析任务是实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)Bn(x)。 4) 首先判定多项式是否稀疏5) 分别采用顺序和动态存储结构实现；6) 结果M(x)中无重复阶项和无零系数项；要求输出结果的升幂和降幂两种排列情况分析：（1）

9、用一维数组cp1n1和cp2n2存储一元多项式Am(x)和Bn(x)的系数，用for循环来计算顺序结构中的加法、减法、乘法的结果。而顺序存储的加减乘运算则分为三个模块函数来解决这三种运算。（2）用指针*d,*q来存储一元多项式的内容，再利用指针计算动态链表下一元多项式的加法、减法、乘法的结果。（3）在用降幂升幂两种排列输出结果时，用expn和coef表示一元多项式的系数和指数，输出两种排列结果。而链式存储的加减乘运算也是分为三个模块函数来解决这三种运算2 系统分析2.1功能需求 此课题是主要任务是创建一元多项式，并可以选择不同的存储方式对一元多项式进行存储并且可以进行多项式的加、减、乘基本运算

10、，最后将结果可以按照升序或者降序排列。首先需要创建两个一元多项式，才能继续下一步的进行基本的多项式运算（加、减、乘）。然后将两种不同的存储方式各自分成一个子快，编写出相应的2个函数（顺序存储、链式存储），然后在主程序里面提示各个选项对相应的功能，用户输入相应的操作数，分别调用不同的函数，打印出相应的排列结果（升幂排列或者降幂排列）。因此，实际需要设计的任务就是创建一元多项式，以及不同存储方法的函数编写，还有不同存储模式下各自的加减乘的函数编写，为了直观和方便，画出流程图如下图：一元多项式的计算主流程图1.1：为动态链表结构为顺序结构开始输入两个多项式各项的系数选择实现结构顺序结构？YN选择打印

11、输出结果的方式升幂？YN升幂输出结果降幂输出结果打印输出处理后的结果结束图1.1一元多项式的计算主流程图（2）顺序存储结构流程图如图1.2所示减法？开始采用顺序存储结构调用加法函数YN加法？调用降幂输出函数调用升幂输出函数YN调用减法函数调用乘法函数选择打印输出结果的顺序升幂？YN打印输出处理后的结果结束图1.2顺序存储结构流程图（3）动态链表结构流程图如图1.3所示减法？开始采用动态链表存储结构调用加法函数YN加法？调用降幂输出函数调用升幂输出函数YN调用减法函数调用乘法函数选择打印输出结果的顺序升幂？YN打印输出处理后的结果结束图1.3动态链表结构流程图流程图很直观的描述了整个程序服务过程

12、。 2.2总体要求首先主函数中必须成功创建两个一元多项式，然后查阅资料知道多项式的存储方法，结合数据结构课程，我选择了比较熟悉的顺序存储和链式存储，用户想要对两个多项式进行不同的运算，首先就必须按照先序成功创建一元多项式。用户要对多项式进行运算，那就需要知道他想怎么运算（加减乘）。这需要用户手动输入选择序号。通过用户输入的信息，计算机就可以进行相关的操作，根据用户输入的信息调用对应的函数进行加减乘的运算，最后再按照用户输入的选择升序或者降序输出结果供用户浏览了；我就要用相应的程序去实现这个过程,这才是我最后的目的。2.3数据需求 输入一元多项式的项数，系数和对应的次数3、详细设计与实现 3.1

13、设计思路 要完成一元多项式顺序存储和链式存储的加、减、乘这几个基本的运算，有很多种方法可以实现。但结合数据结构课程，我选择了比较适合自己的算法，其他的算法还有很多，只是都不是很熟悉，我的思想大多都来源于书上，对一元多项式的顺序存储和链式存储的算法做了分析，下一步自然就是完成它的程序了，不能用程序描述出来那在好也没有用的。详细设计如下：/定义顺序存储结构类型int n1,n2;int cp1n1; intcp2n2/定义动态链表结构类型#define INFEX 10000#define INFCO 10000double coef;int expn;p_pol *next;/顺序存储结构的抽象

14、数据类型定义int n1,n2;利用一维数组cp1n1和cp2n2存储多项式的系数/基本操作：void creatpoly1(double *a,int pt)操作结果：建立顺序结构void addpoly(double *a,double *b,double *c)初始条件：一维数组cp1n1和cp2n2已建立操作结果：顺序结构相加void subpoly(double *a,double *b,double *c)初始条件：一维数组cp1n1和cp2n2已建立操作结果：顺序结构相减 void mulpoly(double *a,double *b,double *c) 初始条件：一维数组c

15、p1n1和cp2n2已建立操作结果：顺序结构相乘void ansprint(double *a,int n) 初始条件: 一维数组cp1n1和cp2n2已建立操作结果：选用升幂或降幂排列打印出结果/动态链表结构的抽象数据类型定义typedef struct p_pol double coef; int expn; p_pol *next；MPP；基本操作：MPP * creatlink(MPP *p,int n,int pt)初始条件：动态链表已定义操作结果：构造动态链表结构void addlink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相加

16、void sublink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相减void mullink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相乘void printlink(MPP * p)初始条件：动态链表已定义操作结果：选用升幂或降幂排列打印结果void deletelink(MPP *p)初始条件：动态链表已定义操作结果：删除结点释放内存3.2详细编码/包含头文件#include stdafx.h#include #include#include #include #include #incl

17、ude #include using namespace std;/自定义函数原型说明void creatpoly1(double *a, int pt) /建立顺序结构void ansprint(double *a, int n) /打印出结果void addpoly(double *a, double *b, double *c,int m,int n) /顺序结构相加void subpoly(double *a, double *b, double *c) /顺序结构相减void mulpoly(double *a, double *b, double *c) /顺序结构相乘MPP *

18、creatlink(MPP *p, int n, int pt) /构造动态链表结构void printlink1(MPP * p) /打印结果Am(x)void printlink2(MPP * p) /打印结果Bn(x)void printlink(MPP * p) /打印结果M(x)void addlink(MPP *p1, MPP *p2, MPP *p3) /动态链表相加void sublink(MPP *p1, MPP *p2, MPP *p3) /动态链表相减void mullink(MPP *p1, MPP *p2, MPP *p3) /动态链表相乘void deletelin

19、k(MPP *p) /删除结点释放内存/建立顺序结构 顺序存储一元多项式则是通过下标作为指数，系数存储在数组对应的位置，若系数为0，则在其指数对应的数组位置存储的数为0。void creatpoly1(double *a, int pt) /建立顺序结构int i;if (pt = 1)/第一个多项式for (i = 0; i = cp1n1 - 1.expn; i+)/把小于等于最大指数的项系数赋值为0ai = 0;for (i = 0; i n1; i+)/把指数大于0的项赋值输入的系数acp1i.expn = cp1i.coef;else/第二个多项式for (i = 0; i = cp

20、2n2 - 1.expn; i+)/把小于等于最大指数的项系数赋值为0ai = 0;for (i = 0; i cp2n2 - 1.expn ? cp2n2 - 1.expn : cp1n1 - 1.expn);/两个多项式的最大指数（较小）int max = (cp1n1 - 1.expn cp2n2 - 1.expn ? cp2n2 - 1.expn : cp1n1 - 1.expn);/两个多项式的最大指数（较大）int i;for (i = 0; i = min; i+)/在小于某个多项式的最大指数（较小）的情况下，直接相加ci = ai + bi;for (; i cp2n2 - 1

21、.expn)/如果较小的最大指数在b多项式ci = ai;else/如果较小的最大指数在a多项式ci = bi;puts(相加结果为：);ansprint(c, max);/输出最后的相加结果/顺序结构相减，对应的数组下标相同的系数相加void subpoly(double *a, double *b, double *c) /顺序结构相减int min = (cp1n1 - 1.expn cp2n2 - 1.expn ? cp2n2 - 1.expn : cp1n1 - 1.expn);/两个多项式的最大指数（较小）int max = (cp1n1 - 1.expncp2n2 - 1.exp

22、n ? cp2n2 - 1.expn : cp1n1 - 1.expn);/两个多项式的最大指数（较大）int i;for (i = 0; i = min; i+)/在小于某个多项式的最大指数（较小）的情况下，直接相减ci = ai - bi;for (; i cp2n2 - 1.expn)/如果被减数a的最大指数较大ci = ai;else/如果减数b的最大指数较大ci = -bi;puts(相减结果为：);ansprint(c, max);/输出最后的相减结果/顺序结构相乘void mulpoly(double *a, double *b, double *c) /顺序结构相乘int ma

23、x = cp1n1 - 1.expn + cp2n2 - 1.expn + 2;/计算乘积的项数int i, j;for (i = 0; i max; i+)/如果小于max直接将新多项式的指数赋值为0ci = 0;for (i = 0; i = cp1n1 - 1.expn; i+)/计算剩余的项for (j = 0; j next = NULL;/初始化指针为NULLq-coef = INFCO;/初始化初始系数q-expn = -INFEX;/初始化初始指数p = q;for (i = 0; i next = NULL;if (pt = 1)/第一个多项式d-coef = cp1i.co

24、ef;/多项式系数d-expn = cp1i.expn;/多项式指数else/第二个多项式d-coef = cp2i.coef;/多项式系数d-expn = cp2i.expn;/多项式指数q-next = d;/继续下一个结点q = d;return p;/打印结果，用户可选择升幂或者降幂打印，如若用户输入的选项不正确，则系统默认升幂打印出结果。void printlink(MPP * p) /打印结果M(x)int num = 0, i = 0, choose, count = 0;puts(请选择输出顺序：1 升幂 2 降幂：);scanf_s(%d, &choose);/输入打印格式选

25、项MPP *tp = p;p = p-next;while (p != NULL)/计算结点个数num+;p = p-next;MPOL *d = new MPOLnum;/建立输出数据结构p = tp-next;while (p != NULL)/对新建的数据结构赋值di.coef = p-coef;di.expn = p-expn;i+;p = p-next;if (choose = 2) /降幂打印多项式count = 0;printf(M(X)=);for (i = num - 1; i = 0; i-)if (di.coef0)putchar(+);printf(%lfX%d, di

26、.coef, di.expn);else /升幂打印多项式if (choose != 1)printf(没有%d选项，系统将默认输出升序：nM(X)=, choose);elseprintf(M(X)=);for (i = 0; i 0)putchar(+);printf(%lfX%d, di.coef, di.expn);putchar(10);/动态链表相加，即比较对应的指数，如若相同，则系数相加void addlink(MPP *p1, MPP *p2, MPP *p3) /动态链表相加MPP * p, *head;p = (MPP *)malloc(sizeof(MPP);/建立动态链

27、表if (p = NULL)exit(0);/初始化链表数据p-coef = INFCO;p-expn = -INFEX;p-next = NULL;head = p3 = p;p1 = p1-next;p2 = p2-next;while (p1 != NULL | p2 != NULL)/两个链表相加，两个链表到表尾时结束循环if (fabs(head-coef) 1e-8)p = (MPP *)malloc(sizeof(MPP);/创建结点if (p = NULL)exit(0);head-next = p;head = p;head-next = NULL;if (p1 = NULL

28、)/将加数的值赋值给和的链表head-coef = p2-coef;head-expn = p2-expn;p2 = p2-next;continue;if (p2 = NULL)/将被加数的值赋值给和的链表head-coef = p1-coef;head-expn = p1-expn;p1 = p1-next;continue;if (p1-expn = p2-expn)/两个多项式指数相等，系数相加head-coef = p1-coef + p2-coef;head-expn = p1-expn;p1 = p1-next;p2 = p2-next;else if (p1-expn expn

29、)/被加数小于加数，将被加数的值赋值给和head-coef = p1-coef;head-expn = p1-expn;p1 = p1-next;else/被加数大于加数，将加数的值赋值给和head-coef = p2-coef;head-expn = p2-expn;p2 = p2-next;puts(相加结果为：);printlink(p3);/输出最后相加的结果/动态链表相减，即比较对应的指数，如若相同，则系数相减void sublink(MPP *p1, MPP *p2, MPP *p3) /动态链表相减MPP * p, *head;p = (MPP *)malloc(sizeof(M

30、PP);/创建结点if (p = NULL)exit(0);/初始化链表p-coef = INFCO;p-expn = -INFEX;p-next = NULL;head = p3 = p;p1 = p1-next;p2 = p2-next;while (p1 != NULL | p2 != NULL) /两个链表相减，两个链表到表尾时结束循环if (fabs(head-coef) 1e-8)p = (MPP *)malloc(sizeof(MPP);/创建结点if (p = NULL)exit(0);head-next = p;head = p;head-next = NULL;if (p1

31、 = NULL)/被减多项式到表尾，将第二个多项式的值赋值给结果多项式/指数不变，系数取相反数head-coef = -p2-coef;head-expn = p2-expn;p2 = p2-next;continue;if (p2 = NULL)/第二个多项式到表尾，将被减多项式的值赋值给结果多项式head-coef = p1-coef;head-expn = p1-expn;p1 = p1-next;continue;if (p1-expn = p2-expn)/两个多项式的某项指数相等，将相减结果赋值给结果多项式head-coef = p1-coef - p2-coef;head-exp

32、n = p1-expn;p1 = p1-next;p2 = p2-next;else if (p1-expn expn)/被减数指数小于减数，将被减数结果赋值给结果多项式head-coef = p1-coef;head-expn = p1-expn;p1 = p1-next;else/被减数大于减数，将减数的值赋值给结果多项式，系数去相反数head-coef = -p2-coef;head-expn = p2-expn;p2 = p2-next;puts(相减结果为：);printlink(p3);/输出多项式相减的结果/动态链表相乘void mullink(MPP *p1, MPP *p2,

33、 MPP *p3) /动态链表相乘MPP *p, *head, *d, *tp;int i, j;p = (MPP *)malloc(sizeof(MPP);/创建结果链表if (p = NULL)exit(0);/初始化结果链表p-coef = INFCO;p-expn = -INFEX;p-next = NULL;tp = head = p3 = p;p = (MPP *)malloc(sizeof(MPP);if (p = NULL)exit(0);p-coef = INFCO;p-expn = INFEX;p-next = NULL;tp-next = p;for (i = 0; i

34、next;d = p2;for (j = 0; j next;p = (MPP *)malloc(sizeof(MPP);/创建结果链表结点if (p = NULL)exit(0);p-next = NULL;p-coef = p1-coef*d-coef;/将两个多项式系数相乘后赋值给结果链表p-expn = p1-expn + d-expn;/将两个多项式指数相加后赋值给结果链表tp = p3;while (tp-next != NULL)if (tp-expn = p-expn)tp-coef += p-coef;free(p);/释放结点break;if (tp-expnexpn&tp

35、-next-expnp-expn)p-next = tp-next;tp-next = p;break;tp = tp-next;tp = p3;while (tp-next != NULL)if (tp-next-expn = INFEX)free(tp-next);tp-next = NULL;break;tp = tp-next;puts(相乘结果为：);printlink(p3);/输出两个多项式相乘结果/删除结点释放内存void deletelink(MPP *p) /删除结点释放内存MPP *d;while (p != NULL)d = p;p = p-next;free(d);/

36、释放结点到此为止，所有功能已经分别实现了，通过执行各个函数，就可以完成相应的功能。现在唯一需要做的就是找个函数来将他们“集中起来”，用来组合在一起，才能让它们互相配合，一起工作。这个任务当然是由main()来完成了：int main()printf(n);printf(t功 能： 二 叉 树 的 遍 历nn);printf(t编 译 环 境：V S 2 0 1 0nn);printf(t发 布 日 期：2 0 1 5 - 1 1 - 2 5nn);printf(n*程序开始！*n);/存储结构选择菜单 d:printf(ttt存储菜单n);printf(t*n);printf(ttt请选择实现结构：nttt1 顺序结构 nttt2 动态链表结构 nttt3 主菜单nttt4 退出n);printf(t*nn);printf(请输入选项：n);/四则运算选择菜单p:printf(ntt四则运算菜单n);printf(t*n);printf(ttt选择操作方式：nttt1 相加 nttt2 相减 nttt3 相乘