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

山东理工大学计算机学院 课 程 设 计 （数据结构） 班 级 计科1102 姓 名 张汝全 学 号 1111051010 指导教师 肖爱梅 2013年 1 月 7 日 课程设计任务书及成绩评定 课题名称 动态链表结构下的一元多项式的加法、减法和乘法的实现。 Ⅰ、题目的目的和要求： 1.巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。 （1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。 （2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。 2.设计题目要求： 首先判定一元多项式是否稀疏 分别采用顺序和链式结构实现； 结果在M(x)中无重复阶项和无零系数项； 二 年 月 日目 录 第一章 概述……………………………………………………………1 第二章 系统分析………………………………………………………2 第三章 概要设计………………………………………………………3 第四章 详细设计………………………………………………………4 第五章 运行与测试……………………………………………………18 第六章 总结与心得……………………………………………………20参考文献………………………………………………………………21第一章 概述 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是动态链表结构下的一元多项式的加法、减法和乘法的实现。一元多项式计算是用C语言设计一个一元多项式简单计算器。它能够实现按指数升序排列建立并输出多项式，并且能够完成两个多项式的相加、相减与相乘的运算和将其结果输入的功能。通过设计一元多项式，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能提高，综合运用所学的理论知识和方法独立分析和解决问题的能力；加深对常用数据结构的理解，强化逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。 第二章 系统分析 ? 动态链表结构下的一元多项式的加法、减法、乘法的实现。可以分为几个模块：输入模块、输出模块（升幂）、数据处理模块（多项式的加减乘）、主程序模块。 在程序执行过程中加入汉字提示符，让使用者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了。 程序执行时的命令：①创建两个一元多项式②输入第一个一元多项式的项数③依次输入一元多项式的系数和指数④以相同方式输入第二个一元多项式⑤数据处理⑥输出结果。 测试数据。输入的一元多项式系数指数分别为7 0,3 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) 乘法结果为：56x+24x^(2)+154x^(7)+3x^(8)+45x^(9)+198x^(15)-81x^(16)+40x^(18)+110x^(24)-45x^(25) 第三章 概要设计 数据结构的设计 为了节省存储空间，只存储多项式中系数非零的项，本程序使用链式存储结构。 算法的设计本设计从总体上划分为3个模块。 主函数模块。程序的入口，主要实现各个函数的调用。 头文件模块。定义类和结构体。 函数模块。数据处理和实现每个功能。 抽象数据类型 ADT list{ 数据对象：D={ai | ai ∈ ElenSet, i=1,2,…,n,n≥0} 数据关系：R1={ai-1,ai | ai-1,ai∈D,i=2,…,n} 基本操作： InitLink(head, len) 初始条件：链表为空。 操作结果：创建链表。 Sparsity(head, len) 初始条件：链表已存在。 操作结果：判断是否稀疏。 Display(head) 初始条件：链表已存在。 操作