数据结构与算法专业课程设计专题计划数学与计算机系信计本科.doc

《数据结构和算法》课程设计计划
一、设计目标
数据结构和算法课程设计是《数据结构和算法》课程教学必不可缺一个关键步骤，它可加深学生对该课程所学内容深入了解和巩固，是将计算机课程和实际问题相联接关键步骤。经过课程设计，能够提升学生分析问题、处理问题，从而利用所学知识处理实际问题能力，所以必需给足够重视。
二、课程设计任务
7-8人为一个课题组，组长1人，要求每组任选2题，各组不得反复选题且需独立完成课题内容，课题组组员必需清楚课题总体设计，必需分有功效模块并独立完成所分模块程序编写任务。最终课题组长组织连调，全部组员必需参与。
三、课程设计内容:
1．二叉树中序、前序、后序递归、非递归遍历算法，按层次遍历非递归遍历算法实现，应包含建树实现。
===================================================================
2．车厢调度
假设停在铁路调度站入口处车厢序列编号一次为1，2，3，4。设计一个程序，求出全部可能由此输出长度为4车厢序列。
===================================================================
3．平衡二叉树判定
给定一个二叉树先序遍历或后序遍历结果，判定其是否为平衡二叉树。
===========================================================================
4.图基础操作和实现设计要求：
(1)自选存放结构,输入含n个顶点（用字符表示顶点）和e条边图G
(2)求每个顶点度,输出结果；
(3)指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提醒:使用一个栈实现DFS)；
(4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提醒:使用一个队列实现BFS)；
(5)输入顶点x,查找图G:若存在含x顶点,则删除该结点及和之相关连边,并作
DFS遍历(实施操作3)；不然输出信息“无x”；
===========================================================================
5.图算法实现
(1)读入图信息，建立和其对应邻接矩阵和邻接表；
(2)实现Prim、Kruskal、Dijkstra序算法。
===========================================================================
6.内部排序算法性能分析
设计要求：设计一个测试程序比较多个内部排序算法关键字比较次数和移动次数以取得直观感受。
(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；
(2)待排序表表长大于100，表中数据随机产生，最少用5组不一样数据作比较，比较指标有：关键字参与比较次数和关键字移动次数（关键字交换记为3次移动）；
(3)输出比较结果。
===========================================================================
7.AOE网研究
已知一个AOE网，求其关键路径长度及关键活动有哪些。
8.二叉排序树实现
   (1) 用二叉链表作存放结构,以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
(2)对二叉排序树T作中序遍历，输出结果；
(3)输入元素x,查找二叉排序树T,若存在含x结点,则删除该结点,并作中序遍历(实施操作2)；不然输出信息“无x”；
==========================================================================
9.哈夫曼编码/译码器
设计一个利用哈夫曼算法编码和译码系统，反复地显示并处理以下项目，直到选择退出为止。基础要求以下：
(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
(2)编码：利用建好哈夫曼树生成哈夫曼编码；
(3)输出编码；
(4)译码：利用编码实现译码。
=================================================================
10.稀疏矩阵应用
分别实现三元组、十字链表下稀疏矩阵存放、加法、乘法、转置实现。
=================================================================
11. 串应用
本设计要求实现串存放、求串长、判定串相等、取子串、插入子串、删除子串、串匹配等。本设计用一个主控菜单程序控制，最少实现以上7个功效。=================================================================
12.结构能够使n个城市连接最小生成树
给定一个地域n个城市间距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到最小生成树代价。基础要求以下：
(1)城市间距离网采取邻接矩阵表示，若两个城市之间不存在道路，则将对应边权值设为自己定义无穷大值。要求在屏幕上显示得到最小生成树中包含了哪些城市间道路，并显示得到最小生成树代价。
(2)表示城市间距离网邻接矩阵（要求最少6个城市，10条边）
(3)最小生成树中包含边及其权值，并显示得到最小生成树代价。
13. 特殊矩阵压缩存放算法实现
对于特殊矩阵能够经过压缩存放降低存放空间。基础要求：
(1)针对多个特殊矩阵进行压缩存放，并能显示压缩后相关地址和值；
(2)输入在原来特殊矩阵中地址，要求能从压缩后矩阵中读出对应值；
=================================================================
14.算术表示式求解
给定一个算术表示式，经过程序求出最终结果。基础要求：
(1)从键盘输入要求解算术表示式；
(2)采取栈结构进行算术表示式求解过程；
(3)能够判定算术表示式正确是否；
(4)对于错误表示式给出提醒；
(5)对于正确表示式给出最终结果；
===========================================================================
15.广义表应用
因为广义表在结构上较线性表复杂得多，所以，广义表运算也不如线性表简单。本设计要求实现广义表建立、查找、输出、取表头和取表尾和求深度等。
本设计用一个主控菜单程序控制，最少实现以下6个功效：
(1)建立广义表
(2)输出广义表
(3)结点查找
(4)求广义表表头
(5)求广义表表尾
(6)求广义表深度
===========================================================================

四、课程设计基础要求
1．问题分析和任务定义。依据设计题目标要求，充足地分析和了解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？
2．逻辑设计。对问题描述中包含操作对象定义对应数据类型，并根据以数据结构为中心标准划分模块，定义主程序模块和各抽象数据类型。逻辑设计结果应写出每个抽象数据类型定义(包含数据结构描述和每个基础操作功效说明)，各个关键模块算法，并画出模块之间调用关系图。
3．具体设计。定义对应存放结构并写出各函数伪码算法。在这个过程中，要综合考虑系统功效，使得系统结构清楚、合理、简单和易于调试，抽象数据类型实现尽可能做到数据封装，基础操作规格说明尽可能明确具体。具体设计结果是对数据结构和基础操作作出深入求精，写出数据存放结构类型定义，写出函数形式算法框架。
4．程序编码。把具体设计结果深入求精为程序设计语言程序。同时加入部分注解和断言，使程序中逻辑概念清楚。
5．程序调试和测试。采取自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具多种功效，设计测试数据确定疑点，经过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好源程序清单和结果。
6．结果分析。程序运行结果包含正确输入及其输出结果和含有错误输入及其输出结果。算法时间、空间复杂性分析。
7．编写课程设计汇报并提交相关内容
设计最终需提交内容包含：
（1）课程设计汇报（1份，A4纸打印，同时包含一份电子版）命名格式为：组号+班级+（组长姓名等）+数计系课程设计汇报.doc<如1、数计系10信计（石杭等）课程设计汇报.doc>
汇报要求版面清楚，格式规范，不然重新编写。汇报内容要求包含：
①问题概述、分析及研究意义；
②数据结构逻辑设计和物理存放设计；
③关键算法设计、步骤描述或伪代码描述；
④数据结构时空复杂性分析和关键算法复杂性分析；
⑤程序最终实现结果（包含关键结果界面抓取，能够说明问题关键试验结果数据打印或其可视化结果等）。
⑥参考文件（假如需要）。
⑦附录部分附上关键数据结构定义及关键算法源代码。
（2）源程序文档（电子方法提交）
源程序代码要求结构清楚、可读性好。应对源程序中类说明（假如采取面向对象方法设计），函数说明，接口说明，关键变量说明等进行注释；源程序要进行合适缩进编排。命名格式为：组号+班级+（组长姓名等）+数计系课程设计源程序<如1、数计系10信计（石杭等）课程设计源程序>
（3）全部以电子方法提交文件全部存在一个目录中，并对其进行压缩（用Winrar或Winzip均可），压缩后文件按要求格式进行命名，命名格式为：组号+班级+（组长姓名等）+课程设计.rar<如1、数计系10信计（石杭等）课程设计.rar>。
五、评分标准
1、基础功效： 50分
经过功效实现情况进行评分。
2、设计汇报： 20分
根据设计汇报要求进行评分。
3、回复问题： 15分
4、课程设计期间考勤： 15分
5、核分标准： 100分
（90~100为优、80~89为良、70~79为中、60~69为及格、，60以下为不及格）
六、 设计时间
—第2学期：第 周