数据结构B课程设计指导书

数据结构B课程设计指导书目录TOC\o"1-5"\h\z\o"CurrentDocument"1课程简介3\o"CurrentDocument"2教学目的与意义3\o"CurrentDocument"3设计内容、任务描述34课程设计主要步骤与时间分配34.1课程设计的主要步骤3\o"CurrentDocument"4.2课程设计进度安排45课程设计过程中的各环节内容45.1建立模型45.2选择合适的存储结构4\o"CurrentDocument"5.3构造求解算法55.4编写程序5\o"CurrentDocument"5.5测试6\o"CurrentDocument"5.6撰写课程设计报告6\o"CurrentDocument"6课程设计成绩的评定7附录1：参考选题81课程简介《数据结构B》是信息管理与信息系统专业的重要基础课程，是一门理论与实践并重的课程，课程设计环节是这门课程的集中性实践教学环节。在先修课程《数据结构B》的基础上，在教师的指导下，利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不太复杂但却是综合性的问题。从规模来说，课程设计是在平时作业的基础上进一步扩大的大作业。在设计中，要求学生要全面考虑相互联系的各个方面及问题。本课程的基本任务，是使学生通过学习，掌握基本算法和数据结构，数据结构与算法的关系。培养计算机信管专业的学生结合实际应用，设计有效的算法和数据结构的能力。2教学目的与意义《数据结构B》是信息管理与信息系统专业的重要基础课程,本课程设计是配合该课程教学而开设的一门实践课程。通过课程设计，使学生对整个《数据结构B》课程的知识体系有较深入的理解，在运用本课程的知识解决实际问题方面得到锻炼，对锻炼学生的实践能力以及运用本课程的知识、方法解决更为复杂的实际问题有较好的启发和指导作用，从而为后续课程的学习、毕业设计环节以及将来的实际工作打好坚实的基础。3设计内容、任务描述在认真研读教材，理解讲课内容的基础上，在附录1参考选题中任选1-2个设计课题（也可自拟与课程相关题目），针对具体问题，运用《数据结构》、程序设计以及迄今为止所学课程中的各种基本技术和理论在规定的时间内完成数据模型的选择、数据结构的定义、求解算法设计及程序编制及调试。4课程设计主要步骤与时间分配4.1课程设计的主要步骤本课程在1周时间内需完成选题、数据模型建立、存储方案选择、求解算法构造、程序编写及测试、设计报告撰写等环节内容。4.2课程设计进度安排集中讲授：2学时（第一天，重点是介绍指导书，指导学生选题，并就学生所选课题进行具体指导）；数据模型建立、存储方案选择：1天时间（第一天）；求解算法构造、程序编写及测试：3天时间（第二天一一第四天）撰写设计报告：第五天5课程设计过程中的各环节内容5.1建立模型建立模型通常包括所描述问题中的数据对象及其关系的描述、问题求解的要求及方法等方面。将一个具体的问题转换为我们所熟悉的模型，就可以很容易进行求解。要描述群体中个体之间的关系时，可以采用《离散数学》中所介绍的图结构。例如要求解一个工程的最小代价或者关键路径时，可以采用图结构中的AOV网或AOE网等模型。数值计算问题中常用的数学模型为线性方程组（用于求解电路的电流强度或结构中的应力）或微分方程（用于预报人口增长情况或化学反应速度等）。《离散数学》及许多数学课程中就介绍了许多模型。《数据结构》课程中所介绍的各种结构也是数学模型。数学模型的建立是求解实际问题的基础。一般情况下，实际应用问题可能会各式各样，但有共性的问题都是同一类数学模型，例如我们所熟悉的工资表的处理问题、学生成绩管理问题、电话号码查询问题、图书管理系统等都属于‘线性表’这种模型。只要掌握‘线性表’的存储结构、操作算法我们就能解决如工资表的处理、学生成绩管理等一系列问题，学习《数据结构》这门课程的根本目的就在于此。再如：在有n个选手P1，P2,P3,…，Pn参加的单循环赛中，每对选手之间非胜即负。现要求求出一个选手序列P1'，P2'，P3'，…，Pn'，使其满足Pi'胜Pi+1'（i=1,…,N-1）。这个问题看似复杂，由于仅涉及到n个选手，并且这些选手之间的关系仅是胜负关系，因此可用图这种数学模型来表示：用顶点表示选手，用弧表示选手之间的胜负关系：当且仅当Pi'胜Pj'，有从i到j的一条弧，在这种表示下，本题问题变成了在有向图中求解出一条包含所有顶点的简单路径的问题。由此可见，正确选择数学模型是解决问题的关键，这就要求我们具有扎实的数学基础，同时熟练地掌握数据结构所介绍的线性表、队列与栈、广义表、树和图等各种结构（模型）的存储方法和操作算法。5.2选择合适的存储结构在构造出求解算法之后，就需要考虑如何在计算机上实现。从算法到程序还是有一定距离的。为此，需要做两方面的工作，其一是选择合适的存储结构，其二是用指定的计算机语言来描述算法。下面先讨论第一个方面，即选择存储结构的问题。选择合适的存储结构首先是为了将问题所涉及到的数据（包括数据中的基本对象及对象之间的关系）存储到计算机中。此外，还需要考虑所选择的结构是否便于问题的求解，时间和空间复杂度是否符合要求。《数据结构》课程中已经对此作了许多讨论。在实际应用时，需根据问题的要求进行合理的选择及综合。不同的存储形式对问题的求解实现有较大的影响，所占用的存储空间也可能有较大的差异。例如，顺序存储结构一般来说便于直接存取，从而节省存取时间，但是在插入和删除元素时需要移动元素，从而浪费时间，而链式存储结构在插入和删除元素时无需移动元素，但需花费时间来搜索元素。线性表较多采用顺序存储结构，而非线性结构则不宜采用这种形式。5.3构造求解算法在建立好模型之后，一个具体的问题就变成了一个用模型所描述的抽象的问题。借助于这一模型以及已有的知识（例如数据结构中有关图结构的基本知识），我们可以相对容易地描述出原问题的求解方法即算法。从某种意义上说，该算法不仅能实现原问题的求解，而且还能实现许多类似的具体问题的求解，尽管这些具体问题的背景及其描述形式可能存在较大的差异。算法设计的核心是给出问题求解的基本算法。所给出的算法并非一定要用某种计算机语言来描述，但应能较方便地转换为某种计算机语言程序。在建立了适当的数学模型后，某些问题就可以转换为一些经典问题或基于某些经典问题的综合或变异形式的求解。例如，如果所转换出的模型为图，则可能借助于图的深度遍历、广度遍历、求最小生成树、求最短路径、拓扑排序、关键路径、二分图的匹配、图的着色等问题的求解算法来实现。在问题的求解没有可借助的方法时，需要自己构思求解方法。在构造求解方法时，需要注意对时间、空间以及其它有关性能的要求。5.4编写程序编程是用指定的计算机语言来描述算法和数据结构，并将其转换为完整的上机程序。这包括提供必要的辅助函数，如建立和输入一个结构，显示结构等。编写出的代码一定要注重程序设计风格，提高程序的可读性。5.5测试对设计者来说，很难保证所编写的程序没有错误，因此需要对原代码进行测试，以发现其中的错误和缺陷。按照软件工程的观点，测试是为了发现错误，而不是证明其正确，也就是说，即使没有发现错误，也不能证明是正确的。5.6撰写课程设计报告在一个课题设计完成之后，需要写出设计报告，以对设计进行总结和讨论，包括课题的要求、模型建立和算法设计，系统组成及说明，使用说明，程序清单，总结和体会，本设计的优、缺点，时、空间性能分析，与其它可能存在的求解方法之间的比较等。通过总结，可以对问题及其求解有更全面、深入的认识，从而达到由典型到全面、由具体到一般的飞跃。设计报告一般要以固定规格的纸张(如A4)书写或打印并装订，字迹及图表要清楚、工整、规范。内容主要包括下面几个方面：问题描述设计思路(数学模型的选择)数据结构定义系统功能模块介绍程序清单运行与调试分析等6课程设计成绩的评定课程设计最终成绩=系统功能实现（50%）+程序质量（20%）+设计报告质量（30%），核定成绩后，最终按照优、良、中、及格、不及格五个等级评定出课程成绩。附录1:参考选题选题0学生运动会成绩数据库功能：学生运动会成绩数据库系统记录某校运动会上全部运动项目，各系获得的分数及排名的情况，包括50、100、200，400，1500米，跳高，跳远，标枪，铅球铁饼等。进入系统后可以输入和修改某个项目的结果情况，可以按各系院编号输出总分；按总分排序；按男团体总分排序；按系院编号查询；按项目编号查询;按女团体总分排序。分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：建立一个文件，包括某个系，5个项目的得分情况，能对文件中的信息进行扩充（追加），修改和删除；3）进一步要求：完成对多个系，多个项目的得分排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。键盘输入：系院数目，男子项目数女子项目数，（每项目取前三名，分别为10，5，2分）要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。选题1哈夫曼树应用功能：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）最低要求：完成功能1；3）进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。选题2n维矩阵乘法：AB-1功能：设计一个矩阵相乘的程序，首先从键盘输入两个矩阵a，b的内容，并输出两个矩阵，输出ab-i结果。分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：建立一个文件，可完成2维矩阵的情况；3）一步要求：通过键盘输入维数n。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。选题38个皇后问题功能：在8X8的国际象样棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：依次输出各种成功的放置方法；3）进一步要求：能画出棋盘的图形形式，并在其上动态地演示试探过程。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。选题4设计一个模拟计算器的程序功能：对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：求出2维数组的功能；3）进一步要求：完成3维以上数组的功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。选题5n元多项式乘法功能：完成两个n元多项式作乘法，给出明确的等式形式。分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。3）进一步要求：实现三元二次多项式的乘法。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。选题6集合运算功能：使用链表来表示集合，完成集合的合并，求交集等操作。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。选题7公园的导游图功能：给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。选题8商店存货管理系统功能：建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进行扩充（追加），修改和删除以及简单的排序；3）进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序