课设——一元多项式加减法

1、课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目：一元多项式加（减）法计算一元多项式加（减）法计算 院（系）： 计算机学院专 业： 计算机科学与技术班 级： 学 号： 姓 名： 指导教师： 说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实求；数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。不予通过。报告和电子数据必须作为实验现象重复的关键依据。沈阳航空航天大学课程设计报告 学术诚信声明 本人声明本人声明

2、：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。 本人签名: 日期： 年 月 日沈阳航空航天大学课程设计报告 I 沈阳航空航天大学沈阳航空航天大学课课程程设设计计任任务务书书课程设计名称数数据据结结构构 课课程程设设计计专业计计算算

3、机机科科学学与与技技术术学生姓名班级学号题目名称一元多项式加（减）法计算一元多项式加（减）法计算起止日期2015年12月21日起至2016年1月6日止课设内容和要求：设计一个一元多项式简单的加（减）法计算器，系统主要功能如下：1.从键盘输入多项式，并以文件形式存储；2.实现两个多项式相加，并建立输出多项式；3.实现两个多项式相减，并建立输出多项式。注：可选择带头结点的单循环链表或单向链表存储多项式。要求：1.利用所学知识，设计相应的数据结构；2.熟练运用开发环境；3.完成软件的设计与编码；4.熟练掌握基本的调试方法；5.提交符合课程设计规范的报告。参考资料：1 严蔚敏，吴伟民 . 数据结构（C

4、 语言版）M. 北京：清华大学出版社，20062 吴国英. 算法设计与分析M.北京：清华大学出版社，20063 徐宝文，李志.C 程序设计语言M.北京：机械工业出版社，2004教教研研室室审审核核意意见见： 同同意意 不不同同意意 教教研研室室主主任任签签字字：指导教师（签名）指导教师（签名）年月日学学 生（签名）生（签名）年月日沈阳航空航天大学课程设计报告 II 目目 录录1 概要设计概要设计.- 1 -1.1 题目的内容与要求 .- 1 -1.2 总体结构 .- 1 -2 详细设计详细设计.- 2 -2.1 主模块 .- 2 -2.2 输入模块 .- 2 -2.3 显示多项式模块 .- 3

5、 -2.4 多项式加法模块 .- 4 -2.5 多项式减法模块 .- 5 -3 调试分析调试分析.- 7 -4 测试及运行结果测试及运行结果.- 8 -参考文献参考文献.- 10 -附附 录（关键部分程序清单）录（关键部分程序清单）.- 11 -沈阳航空航天大学课程设计报告 - 0 - 1 概要设计1.1 题目的内容与要求题目的内容与要求内容：设计一个一元多项式简单的加（减）法计算器。系统主要功能如下：1.从键盘输入多项式，并以文件形式存储；2.显示已输入的多项式； 3.实现两个多项式相加，并建立输出多项式；4.实现两个多项式相减，并建立输出多项式。详细描述：用 C 语言编写一段程序，该程序的

6、功能相当于一个一元多项式的计算器，能够实现按照指数降幂建立并输出多项式，并且能够完成多个多项式的相加、相减运算及结果输出的功能。此程序的数据结构可选择带头结点的单链表存储多项式。链表的结构体可以用来存储多项式的系数、指数、下一个指针 3 个元素，这样便于实现任意多项式的加法、减法运算。1.2 总体结构总体结构本程序主要分为五个模块（功能模块图见图功能模块图见图 1.1）：主模块，输入模块，显示多项式模块，多项式加法模块、多项式减法模块。主模块：控制整个程序的运行，控制菜单操作。输入模块：从键盘输入多项式，并以文件形式存储。显示多项式模块：显示存入链表中的多项式。多项式加法模块：实现两个多项式相

7、加，并建立输出多项式。多项式减法模块：实现两个多项式相减，并建立输出多项式。图 1.1 功能模块图一元多项式计算器主模块输入模块显示多项式模块多项式相加模块多项式相减模块沈阳航空航天大学课程设计报告 - 1 - 2 详细设计2.1 主模块主模块控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块，实现各项功能，流程如图 2.1 所示。 否 是 图 2.1 主模块流程图注释：显示主菜单，选择不同序号执行不同功能。2.2 输入模块输入模块一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，

8、分别存放该项的系数、指数以及指向下一个多项式结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。输入多项式采用头插法的方式，输入多项式中的一个项的系数和指数，就产开始申请节点空间输入多项式的项数输入多项式的系数 m，指数n是否输入正确进行多项式的输出、加法、减法运算结束沈阳航空航天大学课程设计报告 - 2 - 生一个新的结点，建立起它的右指针，并用头结点指向它。为了判断一个多项式是否输入结束，定义一个结束标志，当输入非 0 时就继续；输入为 0 时，就结束一个多项式的输入。流程图如图 2.2 所示。 否 是 否 是 图 2.2 输入

9、模块流程图注释：1.分别输入两个多项式 f、g；2.以文件形式保存输入的多项式。2.3 显示多项式模块显示多项式模块显示多项式分以下几种情况：1.如果系数是大于 0 的项，就输出“+系数 X指数”的形式；2.如果系数是小于 0 的项，输出“-系数 X指数”的形式；3.如果指数为 0 的项，直接输出“系数”；4.如果指数是 1 的项，直接输出“+X”。流程图如图 2.3 所示。开始输入一个多项式的项数输入多项式某一项的系数和指数输入是否为 0结束是否已输入两个多项式沈阳航空航天大学课程设计报告 - 3 - 否 是 否 是 是 否 否 是 是 否 图 2.3 显示多项式模块流程图注释：选择显示多项

10、式功能，显示出已输入的两个多项式 f 和 g。2.4 多项式加法模块多项式加法模块从两个多项式的头部开始判断，当两个多项式的某一项度不为空时，假设P、Q 分别指向多项式 F 和多项式 G 中当前进行比较的结点，然后比较两个结点中的指数项，有三种情况： 1.当 P 所指结点的指数小于 Q 的话，就应该复制 P 的结点到多项式链中。 2.P 所指结点的指数如果大于 Q 的指数，则复制 Q 的结点到多项式链中。 3.当 P 所指结点的指数等于 Q 所指结点的指数，则将两个结点中的系数相加，若和不为 0，则修改 P 所指结点的系数值，同时释放 Q 所指的结点；若和为 0，从多项式 F 的链表中删除相应

11、结点，并释放 P、Q 所指结点。流程图如图 2.4 所示。开始m0n=0输出-mn=1输出-mX输出+mn=0n=1输出+mX输出“-mXn”输出“+mXn”结束沈阳航空航天大学课程设计报告 - 4 - 是 否 是 否图 2.4 多项式加法模块流程图注释：选择输出 f+g 功能，输出 f+g。2.5 多项式减法模块多项式减法模块从两个多项式的头部开始判断，当两个多项式的某一项度不为空时，假设P、Q 分别指向多项式 F 和多项式 G 中当前进行比较的结点，然后比较两个结点中的指数项，有三种情况： 1.当 P 所指结点的指数小于 Q 的话，就应该复制 P 的结点到多项式链中。 2.P 所指结点的指

12、数如果大于 Q 的指数，则复制 Q 的结点到多项式链中，并开始定义存储结果的空链 r存储多项式 1 的空链 P 是否为空存储多项式 2 的空链 Q 是否为空同指数项系数相加后存入 r合并同类项输出存储多项式的和的链 r直接把 Q 中各项存入 r把 P 中各项系数改变符号后存入 r结束沈阳航空航天大学课程设计报告 - 5 - 将建立的结点系数变为相反数。 3.当 P 所指结点的指数等于 Q 所指结点的指数时，并将 Q 的结点系数变为相反数，并将两结点中的系数相加，若和不为 0，则修改 P 所指结点的系数值，同时释放 Q 所指的结点；若和为 0，从多项式 F 的链表中删除相应结点，并释放P、Q 所

13、指结点。流程图如图 2.5 所示。 是 否 是 否 图 2.5 多项式减法模块流程图注释：选择输出 f-g 功能，输出 f-g。开始定义存储结果的空链 r存储多项式 1 的空链 P 是否为空存储多项式 2 的空链 Q 是否为空同指数项系数相加后存入 r合并同类项输出存储多项式的和的链 r结束直接把 Q 中各项存入 r把 P 中各项系数改变符号后存入 r沈阳航空航天大学课程设计报告 - 6 - 3 调试分析在本次课程设计中，经过反复调试，程序已经可以正常运行。在设计一些算法时，出现了一些问题：问题 1：在建立链表时，头指针的设立导致了之后运用到相关的指针时没能很好的移动指针，出现了数据重复输出或

14、是输出系统缺省值，不能实现算法。解决方法：改掉设立头指针的方法，另定义指针，使其指向结点，并移动指针，避免了数据重复输出等问题。问题 2：实现加减法时，建立第三个链表，在引用之前数据时，出现混乱。解决方法：实现加法和减法算法时，分别建立一个新的多项式，再度利用之前的链表之一来进行结点的比较、插入和删除等操作。问题 3：输入的多项式不能按一定的次序排列输出。解决方法： 为了使输入数据按指数降序排列，可在数据的输入后先做一个结点的排序函数，通过对链表排序后再进行之后的加减运算。沈阳航空航天大学课程设计报告 - 0 - 4 测试及运行结果运行截图如下：1、分别输入两个多项式2、输出显示两个已输入的多

15、项式沈阳航空航天大学课程设计报告 - 1 - 3、计算并输出多项式 f+g4、计算并输出多项式 f-g5、退出程序沈阳航空航天大学课程设计报告 - 0 - 参考文献1 严蔚敏，吴伟民 . 数据结构（C 语言版）M. 北京：清华大学出版社，20062 吴国英. 算法设计与分析M.北京：清华大学出版社，20063 徐宝文，李志.C 程序设计语言M.北京：机械工业出版社，20044 王敬华，林萍.C 语言程序设计教程M.北京：清华大学出版社，20055 谭浩强. C 程序设计M.北京：清华大学出版社，1999沈阳航空航天大学课程设计报告 - 1 - 附 录（关键部分程序清单）/定义链表数据结构typ

16、edef struct Duoxiang float xishu; int zhishu; struct Duoxiang *next;*Duo,Duoxiang; /Duo 为结点指针类型/向链表中插入中数据void Insert(Duo p,Duo h) if(p-xishu=0) free(p); /系数为 0 的话释放结点 else Duo q1,q2; q1=h; q2=h-next; while(q2&p-zhishuzhishu) /查找插入位置 q1=q2; q2=q2-next; if(q2&p-zhishu=q2-zhishu) /将指数相同项合并 q2-xishu+=p-

17、xishu; free(p); if(!q2-xishu) /系数为 0，释放结点 q1-next=q2-next; free(q2); else /指数为新时，将结点插入 p-next=q2; q1-next=p; 沈阳航空航天大学课程设计报告 - 2 - /建立一个头指针为 head、项数为 m 的一元多项式Duo CreateDuo(Duo head, int m) int i; Duo p; p=head=(Duo)malloc(sizeof(struct Duoxiang); head-next=NULL; for(i=0;ixishu); printf(请输入指数：); scanf

18、(%d,&p-zhishu); Insert(p,head); /调用 Inser 函数插入结点 return head;/输出显示多项式void PrintDuo(Duo P) Duo q=P-next; int flag=1; /项数计算器 if(!q) /若多项式为空，输出 0 putchar(0); printf(n); return; while(q) if(q-xishu0&flag!=1) /系数大于 0，且不是第一项 putchar(+); if(q-xishu!=1&q-xishu!=-1) /系数 1 或-1 的普通情况 printf(%g,q-xishu); if(q-z

19、hishu=1) putchar(X); else if(q-zhishu) printf(X%d,q-zhishu); else沈阳航空航天大学课程设计报告 - 3 - if(q-xishu=1) if(!q-zhishu) putchar(1); else if(q-zhishu=1) putchar(X); else printf(X%d,q-zhishu); if(q-xishu=-1) if(!q-zhishu) printf(-1); else if(q-zhishu=1) printf(-X); else printf(-X%d,q-zhishu); q=q-next; flag

20、+; printf(n);/比较多项式 f 和 g 的指数，并返回一个值int compare(Duo f,Duo g) if(f&g) if(!g|f-zhishug-zhishu) return 1; else if(!f|f-zhishuzhishu) return -1; else return 0; else if(!f&g) /f 多项式已空，但 g 多项式非空 return -1; else return 1; /g 多项式已空，但 a 多项式非空沈阳航空航天大学课程设计报告 - 4 - /求解并建立多项式 f+g，返回其头指针Duo AddDuo(Duo pf,Duo pg)

21、Duo qf=pf-next; Duo qg=pg-next; Duo headc,hc,qc; hc=(Duo)malloc(sizeof(struct Duoxiang); /建立头结点 hc-next=NULL; headc=hc; while(qf|qg) qc=(Duo)malloc(sizeof(struct Duoxiang); switch(compare(qf,qg) case 1: qc-xishu=qf-xishu; qc-zhishu=qf-zhishu; qf=qf-next; break; case 0: qc-xishu=qf-xishu+qg-xishu; qc

22、-zhishu=qf-zhishu; qf=qf-next; qg=qg-next; break; case -1: qc-xishu=qg-xishu; qc-zhishu=qg-zhishu; qg=qg-next; break; if(qc-xishu!=0) qc-next=hc-next; hc-next=qc; hc=qc; 沈阳航空航天大学课程设计报告 - 5 - else free(qc); /当相加系数为 0 时，释放该结点 return headc;/求解并建立多项式 f-g，返回其头指针Duo SubDuo(Duo pf,Duo pg) Duo h=pg; Duo p=pg-next; Duo pd; while(p) /将 pg 的系数取反 p-xishu*=-1; p=p-next; pd=AddDuo(pf,h); for(p=h-next;p;p=p-next) /恢复 pg 的系数 p-xishu*=-1; return pd;沈阳航空航天大学课程设计报告 - 0 - 课程设计总结：课程设计总结：在这次课程设计中，我遇到了不少困难，但是在我的坚持和虚心请教中都得到顺利解决