数据结构课程设计报告-一元多项式加减运算.doc

《数据结构课程设计报告-一元多项式加减运算.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-一元多项式加减运算.doc（25页珍藏版）》请在装配图网上搜索。

1、山东理工大学计算机学院课 程 设 计（数据结构）班 级计科1102姓 名张汝全学 号1111051010 指导教师肖爱梅2013年 1 月 7 日课程设计任务书及成绩评定课题名称动态链表结构下的一元多项式的加法、减法和乘法的实现。 、题目的目的和要求： 1.巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2.设计题目要求：1) 首先判定一元多项式是否稀疏2) 分别采

2、用顺序和链式结构实现；3) 结果在M(x)中无重复阶项和无零系数项；4) 要求结果以升幂排列输出、设计进度及完成情况日 期内 容1.7-1.9选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.10-1.12创建相关数据结构,录入源程序。1.13-1.15调试程序并记录调试中的问题，初步完成课程设计报告。1.16上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。1.17考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏 数据结构（C语言版）清华大学出版社 19992 严蔚敏 数据结构题集（C语言版）

3、清华大学出版社 19993 谭浩强 C语言程序设计 清华大学出版社4 与所用编程环境相配套的C语言或C+相关的资料、成绩评定：设计成绩： （教师填写）指导老师： （签字）二 年 月 日目 录第一章 概述1第二章 系统分析2第三章 概要设计3第四章 详细设计4第五章 运行与测试18第六章 总结与心得20参考文献21第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程

4、设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是动态链表结构下的一元多项式的加法、减法和乘法的实现。一元多项式计算是用C语言设计一个一元多项式简单计算器。它能够实现按指数升序排列建立并输出多项式，并且能够完成两个多项式的相加、相减与相乘的运算和将其结果输入的功能。通过设计一元多项式，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能提高，综合运用所学的理论知识和方法独立分析和解决问题的能力

5、；加深对常用数据结构的理解，强化逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。第二章 系统分析1 动态链表结构下的一元多项式的加法、减法、乘法的实现。可以分为几个模块：输入模块、输出模块（升幂）、数据处理模块（多项式的加减乘）、主程序模块。2 在程序执行过程中加入汉字提示符，让使用者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了。3 程序执行时的命令：创建两个一元多项式输入第一个一元多项式的项数依次输入一元多项式的系数和指数以相同方式输入第二个一元多项式数据处理输出结果。4 测试数据。输入的一元多项式系数指数分别为7 0,3

6、 1,9 8,5 17和8 1,22 7,-9 8。加法结果为：7+11x+22x(7)+5x(17)减法结果为：7-5x-22x(7)+18x(8)+5x(17)5 乘法结果为：56x+24x(2)+154x(7)+3x(8)+45x(9)+198x(15)-81x(16)+40 x(18)+110 x(24)-45x(25)第三章 概要设计1. 数据结构的设计为了节省存储空间，只存储多项式中系数非零的项，本程序使用链式存储结构。2. 算法的设计本设计从总体上划分为3个模块。a) 主函数模块。程序的入口，主要实现各个函数的调用。b) 头文件模块。定义类和结构体。c) 函数模块。数据处理和实现

7、每个功能。3. 抽象数据类型ADT list数据对象：D=ai | ai ElenSet, i=1,2,n,n0数据关系：R1= | ai-1,aiD,i=2,n基本操作：InitLink(&head, len)初始条件：链表为空。操作结果：创建链表。Sparsity(&head, len)初始条件：链表已存在。操作结果：判断是否稀疏。Display(head)初始条件：链表已存在。操作结果：输出多项式。 Merge(&head)初始条件：链表已存在。操作结果：合并指数相同的项。 SelectSort(&head)初始条件：链表已存在。操作结果：选择排序。 Negative(&head)初始条

8、件：链表已存在。操作结果：取负。 DelZero(&head)初始条件：链表已存在。操作结果：删除系数为0的项。 operator + (&head，&b);初始条件：链表已存在。操作结果：重载+。 operator * (&head，&b);初始条件：链表已存在。操作结果：重载*。第四章 详细设计1. 类定义。polynomial.h#ifndef POLYNOMIAL_H_INCLUDED#define POLYNOMIAL_H_INCLUDEDtemplate struct Node T coef; /定义系数 T expn; /定义指数 Node *next; /定义结构体templa

9、te /模板类class LinkList private: Node *head; /定义头结点 public: LinkList(); /初始化链表 void InitLink(int len); /建立链表 void Sparsity(int len); /是否稀疏 void Display(); /显示 void Merge(); /合并指数相同的项 void SelectSort(); /选择排序 void Negative(); /取负 void DelZero(); /删除系数为0的项 LinkList operator + (LinkList &b); /重载+ LinkLis

10、t operator * (LinkList &b); /重载*;#endif / POLYNOMIAL_H_INCLUDED2. 成员函数。polynomial.cpp#include#includepolynomial.husing namespace std;template LinkList:LinkList() head=new Node; head-next=NULL;/初始化template void LinkList:InitLink(int len) Node *p, *q; q=head; cout 系数 指数： endl; while(len-) p=new Node;

11、cin p-coef p-expn; p-next=NULL; q-next=p; q=p; /建立多项式template void LinkList:Display() DelZero(); Node *q; q=head-next; if (!q) /空链表输出0 cout 0 coef) if (q-coef = 1) if (q-expn = 0) cout coef; else if(q-expn = 1) cout x; else cout x ( expn coef = -1) if (q-expn = 0) cout coef; else if(q-expn = 1) cout

12、 -x; else cout -x ( expn expn = 0) cout coef; else if(q-expn = 1) cout coef x; else cout coef x ( expn next; while(q) if (q-coef) if (q-coef 0) if (q-coef = 1) if (q-expn = 0) cout expn = 1) cout +x; else cout +x ( expn expn = 0) cout + coef; else if(q-expn = 1) cout + coef x; else cout + coef x ( e

13、xpn coef = -1) if (q-expn = 0) cout coef; else if (q-expn = 1) cout -x; else cout -x ( expn expn = 0) cout coef; else if(q-expn = 1) cout coef x; else cout coef x ( expn next; cout endl;/输出多项式template void LinkList:Sparsity(int len) if (head-next = NULL) cout 0 endl; cout 不稀疏！ endl; return ; Node *p

14、, *q; q=head; p=head-next; while(q-next) q=q-next; double x=1.0*len/(q-expn-p-expn); Display(); if (x = 0.05) cout 稀疏！ endl; else cout 不稀疏！ endl;/判断是否稀疏template void LinkList:Merge() Node *p, *q, *t; for (q=head-next; q; q=q-next) for (p=q-next; p & p-expn = q-expn; ) q-coef+=p-coef; q-next=p-next;

15、t=p; p=p-next; free(t); /合并指数相同的项template void LinkList:SelectSort() Node *p, *q; for (q=head-next; q; q=q-next) for (p=q-next; p; p=p-next) if (q-expn p-expn) swap(q-coef,p-coef); swap(q-expn,p-expn); Merge();/选择排序 升幂template void LinkList:Negative() Node *p; p=head-next; while(p) p-coef=0-p-coef;

16、p=p-next; /取负template void LinkList:DelZero() Node *p, *q, *t; p=head-next; q=head; while(p) if (p-coef = 0) q-next=p-next; t=p; p=p-next; free(t); else q=p; p=p-next; /删除系数为0的项template LinkList LinkList:operator+ (LinkList &b) LinkList m; Node *q, *p; Node *pa, *pb; pa=head-next; pb=b.head-next; q=

17、m.head; while(pa & pb) T x=pa-expn - pb-expn; if (x 0) p=new Node; p-coef=pa-coef; p-expn=pa-expn; p-next=NULL; q-next=p; q=p; pa=pa-next; else if(x 0) p=new Node; p-coef=pb-coef; p-expn=pb-expn; p-next=NULL; q-next=p; q=p; pb=pb-next; else T coef=pa-coef+pb-coef; if (coef) p=new Node; p-coef=coef;

18、p-expn=pa-expn; p-next=NULL; q-next=p; q=p; pa=pa-next; pb=pb-next; else pa=pa-next; pb=pb-next; while(pa) p=new Node; p-coef=pa-coef; p-expn=pa-expn; p-next=NULL; q-next=p; q=p; pa=pa-next; while(pb) p=new Node; p-coef=pb-coef; p-expn=pb-expn; p-next=NULL; q-next=p; q=p; pb=pb-next; return m;/重载+te

19、mplate LinkList LinkList:operator* (LinkList &b) LinkList m; Node *q, *p; Node *pa, *pb; q=m.head; for (pa=head-next; pa; pa=pa-next) for (pb=b.head-next; pb; pb=pb-next) p=new Node; p-coef=pa-coef*pb-coef; p-expn=pa-expn+pb-expn; p-next=NULL; q-next=p; q=p; return m;/重载*void menu() for (int i=0; i8

20、0; i+) cout *; cout endl; cout 1.建立多项式tt2.输出多项式tt3.多项式相加 endl;cout 4.多项式相减tt5.多项式相乘tt0.退出系统 endl; for (i=0; i80; i+) cout *; cout endl; cout 请选择：;3. 主函数。main.c#include #include #include #include #include #include polynomial.cppusing namespace std;int main() /freopen(data1.in, r, stdin); /输入重定向 /freo

21、pen(data1.out, w, stdout); /输出重定向 LinkList a, b, m1, m2, m3; int n, flag; int ALen, BLen; menu(); while(cin n, n) system(cls); switch(n) case 0: cout 欢迎下次使用！ endl; exit(0); case 1: flag=0; cout ALen; a.InitLink(ALen); /建立一元多项式 a.SelectSort(); /升幂排序 cout BLen; b.InitLink(BLen); /建立一元多项式 b.SelectSort(

22、); /升序排序 break; case 2: cout a=; a.Sparsity(ALen); /判断是否稀疏 cout b=; b.Sparsity(BLen); /判断是否稀疏 break; case 3: m1=a+b; m1.SelectSort(); cout a+b=; m1.Display(); /输出a+b break; case 4: if (flag = 0) b.Negative(); /对b取负 flag=1; m2=a+b; m2.SelectSort(); cout a-b=; m2.Display(); /输出a-b break; case 5: if (f

23、lag = 1) b.Negative(); /b取负 flag=0; m3=a*b; m3.SelectSort(); cout a*b=; m3.Display(); /输出a*b break; default:cout 输入错误，请重新输入！ endl; menu(); return 0;第五章 运行与测试程序开始界面。选择 1，分别输入两个一元多项式选择2，输出两个一元多项式分别选择3、4、5输入0结束程序第6章 总结与心得 这次课程设计使本学期所学的数据结构知识得到了巩固和应用，并且对C+也有了更进一步的了解。虽然在设计过程中遇到了一些困难，但感觉收获还是挺多的，自己扩充了很多知识点

24、。通过这周的课程设计，我意识到好的学习方法的重要性，在学习中要学会主动，学会自学，不要什么东西都指望别人，要靠自己去细心观察，多问自己一个为什么，多动手查查、看看，不会的问题，抬头是google，这样自己学到手的东西才会更多！参考文献:1 严蔚敏、吴伟民主编 数据结构（C语言版） 清华大学出版社 20022 殷人昆等著 数据结构（C+版） 清华大学出版社 20013 金远平著 数据结构（C+描述） 清华大学出版社 2005 4 许卓群等著 数据结构与算法 高等教育出版社 20045 Frank M.Carrano 等著 数据结构与+高级教程清华大学出版社 20046 严蔚敏、吴伟民 数据结构习题集（C语言版）清华大学出版社 7 谭浩强C+面向对象程序设计清华大学出版社 200621