级数据结构课程设计方案.docVIP

《 数据结构》课程设计指导书 课程代号：适用专业： 本课程设计是《数据结构》课程的组成之一，也是它的继续和延伸。采用集中学习方法，分组完成一个小型应用系统。开设本课程的目的是使学生通过参加小型软件的开发过程，进一步了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力；创新能力和创新意识1. 了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况。和详细设计调试与测试结果分析 2.排序算法性能分析 功能要求： 能进行各种排序算法运算，排序包括直接插入、希尔排序、冒泡排序、快速排序、堆排序、二路归并。 能对各种算法进行比较， 人机界面自定义，要友好。将排序的结果包括排序后的序列、算法关键字比较和移动的次数等。并列表比较。 测试数据要求：测试数据至少3组，每组数据个数10000。 汉化人机界面 较高要求：实现图形化操作界面，在不同界面间可相互切换。 3．求城市之间的光纤网连接的最短电缆长度 功能要求： 从文件city.txt中读入一个图，文件city.txt结构如下： 第一行为整数m，n，其中m表示城市个数（顶点数），n表示边数； 接着的m行每行都是一个字符串，表示城市名； 接下来的n行每行代表一条边，其格式为“城市名 城市名 距离”。 要求在所有城市之间建立光纤网，使所用光纤总长度最短。 输出城市建成的光纤网所用光缆的总长及每个连接的长度。 4. 哈希表的设计与实现 问题描述： 设计哈希表实现电话号码查询系统。 功能要求： 设每个记录有下列数据项：电话号码、用户名、地址； 从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 采用再哈希法解决冲突； 查找并显示给定电话号码的记录； 查找并显示给定用户名的记录。 在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。? 5.文本格式化 问题描述： 文本文件非空且以文本文件形式存放（为空没有格式化意义）。输入输出文件名均由用户从键盘输入。 字的定义：由非（‘@’，‘ ’(空格)）的任意ASCII码字符组成。 文本文件的定义：由字母字符，数字字符，空格和可以用ASCII代码显示的字符组成。‘@’只表示换行的意义。‘ ’(空格)只表示一个字的结束的意义。 任何完整的字都没有被分割在两行:，行尾不齐没关系，但要实现左对齐。每行字符数不超过60 输出文件中字与字之间只留一个空格符，即实现多余空格符的压缩。 符号‘@’指示它后面的正文在格式化时应另起一段排放，段首缩入8个字符的位置。 功能要求： 输出文件中字与字之间只留一个空格符，即实现多与空格符的压缩； 在输出文件中，任何完整的字仍不能分割在两行，行尾不齐没关系，但行首要对齐（即左对齐）； 如果所要求的每页页底所空行数不少于3，即将页号印在页底空行中第2行中的中间位置上，否则不印； 版面要求的参数要包含： ①页长（Page Length）—每页内文字（不计页号）的行数； ②页宽（Page Wedth）—每行内文字所占最大字符数； ③左空白（Left Margin）—每行文字前的固定空格数； ④头长（Heading Length）—每页页顶所空行数； ⑤脚长（Footing Length）—每页页底所空行数； ⑥起始页号（Starting Page Number）—首页的页号。见《数据结构题集》P117 6.哈夫曼编译码器 问题描述：利用哈夫曼编码进行信息通信，要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。 功能要求： 一个完整的系统应具有以下功能： I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入