数据结构课程设计指导书

《数据结构与算法》课程设计 指 导 书

计算机学院 一.设计要求: 本课程设计是为了配合《数据结构》课程的开设,通过设计一个完整的程序,使学生掌握数据结构的应用,算法的编写,类C语言的算法转换成C程序并用Turbo C2.0或Visual C++6.0上机调试的基本方法。要求如下: 1.要充分认识课程设计对自己的重要性,认真做好课程设计前的各项准备工作。 2.既要虚心接受老师的指导,又要充分发挥主观能动性.结合课题,独立思考,努力钻研,勤于实践,勇于创新。 3.独立按时完成规定的工作任务,不得弄虚作假,不准抄袭他人内容,否则成绩以不及格计。 4.课程设计期间,无故缺席按旷课处理;缺席时间达四分之一以上者,其成绩按不及格处理。 5.在设计过程中,要严格要求自己,树立严肃,严密,严谨的科学态度,必须按时,按质,按量完成课程设计。 6.小组成员之间,分工明确,但要保持联系畅通,密切合作,培养良好的互相帮助和团队协作精神。 二.适用专业 适用于2011级计算机科学与技术专业。 三.课程设计的一般步骤 1.选题与搜集资料: 4-5人为一小组进行选题,进行课程设计课题的资料搜集。 2.分析与概要设计:根据搜集的资料,进行程序功能与数据结构分析,并选择合适的数据结构,并在此基础上进行实现程序功能的算法设计。 3.程序设计:运用掌握C语言编写程序,实现所程序的各个模块功能。 4.调试与测试:自行调试程序,成员交叉测试程序,并记录测试情况。 5.实习报告:编写实习报告 6.验收与评分:指导教师对每个小组的开发的系统,及每个成员开发的模块进行综合验收. 7.结合设计报告,根据课程设计成绩的评定方法,评出成绩。 四.本课程设计内容与要求 掌握课程设计的每个步骤,在此基础上设计出所要求的数据结构,功能模块和完整的主程序。 1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2. 逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。 3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；（算法思想） 4.程序实现：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；（算法实现） 5.程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； 6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析； 五.上机任务 1.选择合适的数据结构,并定义数据结构的结构体; 2.根据程序所要完成的基本要求和程序实现提示,设计出完整的算法; 3.设计出主程序(main函数),使其成为完整的程序. 六.课程设计报告内容包括： 1.需求分析 在该部分中叙述，每个模块的功能要求 2.概要设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。 3.详细设计 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 4.调试分析 调试过程中所做的工作,设计的测试用例,时间复杂度等，测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 5.测试结果 输入数据和输出数据示例 6．课程设计总结可以包括 : 课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容； 七.上交相关内容要求 上交的成功内容必须由以下三个部分组成，缺一不可。 1.上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）； 2．上交程序的说明文件：在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明； 3.课程设计报告：保存在word文档镇南关，文件名要求按照“学号-姓名-课程设计题目”命名。 八.考核方式与成绩评定 设计报告与程序源码作为考核的内容,成绩计分按优,良,中,差4级评定. 九.课程设计题目 1.一元多项式的运算 设计要求：计算任意两个一元多项式的加法、减法以及乘法。 基本功能： a．按照指数升序次序，输入并建立多项式A与B。 b．计算多项式A与B的和，即建立多项式A+B。 c．按照指数升序次序，输出多项式A、B、A+B。 实现提示： 一元n次多项式：P(x,n)=P0+P1X1+P2X2+…+PnXn，其每一个子项都是由“系数”和“指数”两部分来组成的，因此可以将它抽象成一个由“系数、指数对”构成的线性表，其中，多项式的每一项都对应于线性表中的一个数据元素。由于对多项式中系数为0的子项可以不记录它的指数值，对于这样的情况就不再付出存储空间来存放它了；基于此，可以采用一个带有头结点的单链表来表示一个一元多项式。 数据类型定义可描述如下： typedef struct pnode {int coef; /*系数域*/ int exp; /*指数域*/ struct pnode *next; /*指针域，指向下一个系数不为0的子项*/ }PolyNode, *PolyLink; PolyLink A, B, C; /*单链表存储的多项式A、B、C*/ 2.算术表达式求值 设计要求：将任意一个算术表达式转化为逆波兰表示，并根据逆波兰表示计算表达式的值。 基本功能： 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。 算法输出：表达式运算结果。 实现提示： 算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 3. 简易家谱系统 设计要求：输入家族成员情况，建立树结构，统计家族成员人数，能查询家族成员辈份情况。 系统功能： a. 输入、修改与删除家谱信息功能 b. 查询功能： 1）某家谱成员的所有子孙的集合 2） 某家谱成员的所有祖先的集合 3） 某家谱成员的所有同辈成员的集合 4）求某家谱成员的所有上一辈成员的集合 5）给出两个家谱成员，确定他们的关系 c. 统计功能 1）统计家谱成员总人数 2） 统计从事某种职业的人数 实现提示： 使用多叉树表示家族成员的关系。 4.哈希表及其应用 建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。 基本功能： 使用哈希查找表存储信息；实现查找、插入、删除、统计、输出等功能； 实现提示： 利用关键字与存储位置之间的对应关系的哈希函数构造哈希表，哈希表既可以用于存储信息，也可以提高查找信息的速度。 5. 二叉排序树与平衡二叉排序树基本操作的实现 设计要求：用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作。 基本功能： 用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均查找长度,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”； 判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果。 实现提示： 建立二插排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。计算二插排序树的平均查找长度时，可采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。 删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。 判断二插排序树是否为平衡二叉树的函数，也是采用递归函数的方式，分别判定以树中每个结点为根结点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二叉树。 6．哈夫曼树的应用 设计要求：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。 实现提示： 在构造哈夫曼树时，可以设置一个大小为2n-1的数组ht保存哈夫曼树中各结点的信息.其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组ht中的序号，叶子结点的这两个指针值为空（即-1）。为了判定一个结点是否已加入到要建立的s哈夫曼树中，可通过parent域的值来确定。初始时parent的值为-1，当结点加入到树中时，该结点parent的值为其双亲结点在数组ht中的序号。 哈夫曼树的存储结构定义述如下：