数据结构课程设计报告-公园导游图.docx

课程设计报告
课程名称 数据结构
课题名称 公园导游图
专 业 计算机科学与技术
班 级 计算机0702
学 号
姓 名
指导教师—
2009年 10月 26日
工程学院
课程设计任务书
课程名称 数据结构
课 题 公园导游图
专业班级 计算机0702
学生姓名
学 号—
指导老师—审 批
任务书下达日期 2009 年 10月 8日
任务完成日期 2009 年 11月 8日
1设计容与设计要求


由系统随机生成4扑克牌，用户利用扑克牌的数字及运算符号 + ”、 “一'
妙、r‘及括号“（”和从键盘上输入一个计算表达式，系统运行后得出计算 结果，如果结果等丁 24,则显示Congratulation!”，否则显示Ihcorrect! ”
设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式， 利用后缀表达式求值。

随机生成一个迷宫图，迷宫大小为N*N , N预定义为常数，修改N的值可 以改变迷宫的大小。用白色表小可走的路，蓝色表小墙壁不可以通过。系统设 计两种运行方式：一种是系统自动探索（用递归方法实现） ；另一种是由人工
操作探索通路。
设计思路：程序首先要考虑迷宫的表示，这是一个二维关系图，所以可选 择二维数组来存储。数组元素只有两种值 0和1 ,分别代表通路和墙壁。图形 的显示可以根据数组元素的值来确定。如果是人工探索，则依据按键来确定探 索物的位置坐标，利用循环语句实现。如果是系统自动探索，可采用递归算法 实现。

演示遍历二义树的过程，所以首先建立二义树，并用图形显示出树的形状。 建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系 统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二义树不超 过5层，最多26个字符，输入字符小数点“'代表NULL。初始树为某种颜色的 结点，三种情况的遍历采用填充另外一种醒目的颜色， 来表示当前遍历的结点，
同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍 历序歹0。

按照行优先顺序将用户随机输入的数据建成 2维数组并以图形方式逐步显 示出来，然后再按照列优先顺序以图形方式逐步输出相应数组。

演示拓扑排序的过程。按照有向图给出的次序关系，将图中顶点排成一个 线性序列，对丁有向图中没有限定次序关系的顶点，则可以人为加上任意的次 序关系。要求每输出一个顶点后就演示从图中删去此顶点以及所有以它为尾的 弧。

演示图的深度优先，广度优先遍历过程，并输出原图结构及遍历结果。要 求图的结点数不能少丁 6个。可以由系统随机生成图，也可以由用户手动输入 图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进 图的效果。

在8*8的棋盘上摆放8个皇后，使他们不在同一条对角线上和不在一行和 列上。 解决8皇后时，在安放第i行皇后时，需要在列的方向从1到n试探（j =1,…,n）:首先在第j列安放一个皇后，如果在列、主对角线、次对角线方向 有其它皇后，则出现攻击，撤消在第 j列安放的皇后。如果没有出现攻击，在 第j列安放的皇后不动，递归安放第i+1行皇后。该课题要求求解可能的方案 及方案数并逐步演示摆放皇后的过程。

建立一个递增有序的双链表。功能是随机生成8个结点数据，每生成一个 结点则申请空间得到一个指针，将数据存放到指针所指的数据域中，然后将结 点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入位置， 第二不演示插入过程中指针的变化，第三步显示插入后的链表结果。

给出一某公园的导游图，游客通过终端询问可知：从某一景点到另一景点 的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游 览各景点，最后回到出口（出口就在入口旁边）。要求用图示展示最佳路径。
：
所选题目根据学号确定，学号模 9加1,即（学号％9+1）。如你的学号为
12,则所选题目号为：12%9+1=(题目4)。注意，所有的课题都要求用图形 方式演示步骤和结果。有兴趣的同学可以自己针对数据结构课程中所讲算法来 设计一个演示过程的算法，但要预先告知老师，经过审批，方可确定课题。
：

需求分析
程序的功能。
输入输出的要求。
概要设计
程序由哪些模块组成以及模块之间的层次结构、 各模块的调用关系；每个
模块的功能。
课题涉及的数据结构和数