信息-数据结构-课程设计指导书(赵明信息09)

数据结构课程设计PAGEPAGE2数据结构课程设计指导书（信息管理与信息系统专业）信息与控制工程学院2009年3月数据结构课程设计指导书一、课程设计的性质、目的与作用《数据结构》是计算机科学中一门综合性的专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。课程设计是一项综合性设计活动，要求在教师的指导下，利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不太复杂但却是综合性的问题。从规模来说，课程设计是在平时作业的基础上进一步扩大的大作业。在设计中，要求学生要全面考虑相互联系的各个方面及问题。通过课程设计，使学生了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风，从而使学生对整个课程的知识体系有较深入的理解，在运用本课程的知识解决实际问题方面得到锻炼，对锻炼学生的实践能力以及运用本课程的知识、方法解决更为复杂的实际问题有较好的启发和指导作用，从而为后续课程的学习、毕业设计环节以及将来的实际工作打好坚实的基础。通过对给定问题的求解，使学生在运用《数据结构》、程序设计以及迄今为止所学课程中的各种基本技术和理论，在建立问题模型、构造求解算法、设计数据结构、编程及上机调试等方面得到全面的锻炼，从而能更深刻地理解《数据结构》的精髓，为后续软件课程的学习及软件设计能力的提高奠定良好的基础。二、课程设计的步骤课程设计就是要运用本课程以及到目前为止的有关课程中的知识和技术来解决实际的问题。在运用计算机解决实际问题时，主要进行以下几个方面的工作：1．建立模型许多问题的最初描述既不精确又不简练，还有一些问题不可能简单而精确地用计算机可求解的形式来描述，即使有些可用计算机求解的问题，也需要在很大范围内确定问题的参数，而那些合理的参数值只有通过实验才能确定。因此，要用计算机解决问题，必须首先要以简明、严格的方式将问题描述清楚，可以说，成功的关键在于明确要解决的问题。如果能用一个形式模型来刻画问题，则将有益于问题的形式化描述，我们就可以依据这个严格的模型对问题进行求解。对应形式化了的问题，我们容易知道是否已有现成的程序或方法可以利用。即使没有现成的程序或方法可用，至少可以利用这个形式模型所具有的种种性质来构造好的解法。数学或其它科学中的几乎所有分支都可作为某一类具体问题的抽象模型。例如，在涉及到若干对象及其相互间关系的问题时所用的数学模型为图论；数值计算问题中常用的数学模型为线性方程组（用于求解电路的电流强度或结构中的应力）或微分方程（用于预报人口增长情况或化学反应速度等）；在符号与文本处理问题时常用字符串及形式语法作为模型（如编译系统）。《数据结构》课程中所介绍的各种结构均可作为一种模型。2．构造算法对问题建立了适当的数学模型后，就可以依据这一模型求解。最初的目标是给出一个算法形式的解法，这是设计的核心部分。所给出的算法并非一定要用某种计算机语言来描述，但应能较方便地转换为某种计算机语言程序。在建立了适当的数学模型后，某些问题就可以转换为一些经典问题或基于某些经典问题的综合或变异形式的求解。例如，如果所转换出的模型为图，则可能借助于图的深度遍历、广度遍历、求最小生成树、求最短路径、拓扑排序、关键路径、二分图的匹配、图的着色等问题的求解算法来实现。在问题的求解没有可借助的方法时，需要自己构思求解方法。在构造求解方法时，需要注意对时间、空间、程序实现以及其它有关性能的要求。另外，在构造算法时，最好是在数学模型上构造。3．选择数据结构在确定了求解算法后，就可以开始编程方面的构思了。从算法到程序还是有一定的距离的，为此，需要做两方面的工作，其一是选择合适的数据结构以存储所涉及到的数据，其二是用指定的计算机语言来描述算法。下面先讨论第一个方面，即选择数据结构的问题。在选择数据结构时，除了要能将所需的数据存储起来外，还需要考虑所选择的结构是否便于问题的求解，时间和空间复杂度是否符合要求。《数据结构》课程中已经对此作了许多讨论。在实际应用时，需根据问题的要求进行合理的选择以及综合。在选择数据结构的同时，还需要做的一项工作就是要为所选择的数据结构提供必要的基本运算，即提供可供应用程序调用的基本运算，程序中的其它运算可通过调用这些基本运算来实现对该结构的操作，这样既便于独立地调试程序，又可避免在程序中对该结构直接进行操作，从而可提高程序的可维护性。4．编程编程的另一个方面是用指定的计算机语言来描述算法和数据结构，并将其转换为完整的上机程序。这包括提供必要的辅助程序段，如建立和输入一个结构，显示结构，跟踪程序的运行等。另外，在编程过程中可能还需要设置数据结构，也要为这些结构提供基本运算。在设计时，如果所用的结构是《数据结构实验工具》能支持的，则其中的一些辅助工作可以省略，但如果工具不支持时，就需要读者自己设计有关的操作了。5.总结对设计进行总结和讨论，包括本设计的优、缺点，时间、空间性能，与其它可能存在的求解方法之间的比较等。通过总结，可以对问题求解有更全面、深入的认识，从而达到由典型到全面、由具体到一般的飞跃，实现设计的目标。因此，这是设计所不可缺少的重要内容。这部分内容应作为设计报告中的一个组成部分。三、课程设计的内容1.哈夫曼编／译码器【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个哈夫曼码的编／译码系统。【基本要求】一个完整的系统应具有以下功能：(l)I：初始化（Initialization）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。(2)E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3)D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。(4)P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写人文件codePrin中。(5)T：打印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】(1)利用教科书例6.2中的数据调试程序。(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码："THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLMN频度641322321032115475715322057字符OPQRSTUVWXYZ频度63151485180238181161【实现提示】(l)编码结果以文本方式存储在文件CodeFile中。(2)用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q"，表示退出运行quit.请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“q”为止。(3)在程序的一次执行过程中，第一次执行I,D,C命令之后，哈夫曼树已经在内存了，不必再读入，每次执行中不一定执行I命令，因为文件htmtree可能早已建好。2.哈希表设计【问题描述】针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。【基本要求】假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。【测试数据】取读者周围较熟悉的30个人名。【选作内容】（1）从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。（2）研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。（3）在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。3.内部排序算法比较【问题描述】各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。【基本要求】（1）对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。（2）待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。【测试数据】由随机产生器决定。【实现提示】主要工作是设法在程序中适当的地方插入计数操作。程序还可以包括计算几组数据得出结果波动大小的解释。注意分块调试的方法。【选作内容】对不同的输入表长做试验，观察检查两个指标相关于表长的变化关系。还可以对稳定性做验证。4.迷宫问题【问题描述】以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】首先以一个链表表示存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以一个三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一个坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1)，(1,2,2)，(2,2,2)，(3,2,3)，(3,1,2)，……。【测试数据】迷宫的测试数据如下：左上角(1,1)为入口，右下角(8,9)为出口。12345678001000100010001000001101011100100001000001000101011110011100010111000000【实现提示】计算机解迷宫问题通常采用的是“穷举求解”方法，即从入口出发，顺着一个方向进行探索，若能走通，则继续前进；否则沿原路返回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以以二维数组存储迷宫数据，通常设定入口点的下标为(1,1)，出口的下标为(m,n)。为方便起见，可在迷宫的四周加一周障碍。对于迷宫中的任意位置，均可决定有东、南、西、北四个方向可通。【选作内容】编写递归形式的算法，求得迷宫中所有可能的通路。以方阵的形式输出迷宫及其通路。5.校园导游咨询【问题描述】设计一个校园导游程序，为来访的客人提供各种信息咨询服务。【基本要求】设计你所在的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内的各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等信息。为来访的客人提供图中任意景点相关信息的查询为来访的客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径。【测试数据】由读者根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图为一个无向网。顶点和边均含有相关信息。【选作内容】提供任意景点问路查询，即求任意两个景点之间的所有路径。提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。校园导游的景点和道路扩充功能。扩充道路信息，如道路类别（车道、人行道等），沿途景色等级，以至可按客人所需分别查询人行路径或车行路径等。扩充每个景点的邻接景点的方向等信息，使得路径查询结果能够提供详尽的导向信息。实现校园导游图的仿真界面。四、课程设计的要求1．关于课题及选题在后面的课题表中列出了多个设计课题，每个课题都有相应的要求或说明。各课题的难易度是有差异的，因此，参加课程设计的学生首先要了解设计的任务，仔细阅读各题的设计要求，然后根据自己的基础和能力情况从中选择一题，或者由指导教师指定。一般来说，选择课题应以在规定的时间内能完成，并能得到应有的锻炼为基本原则。若学生对规定课题以外的相关课题较感兴趣，希望选作课程设计的课题时，应征得指导教师的认可，并写出明确的设计要求和说明。2.关于设计的总要求在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。3．验收在设计完成后，应由指导教师当场运行、验收，只有在验收合格后才能认定为设计部分的结束。4．课程设计说明书设计结束后要写出课程设计说明书，以作为整个课程设计评分的书面依据和存档材料。设计报告必须用A4书写或打印并装订，封面按照学校的