双链表课程设计.doc

课 程 设 计 报 告 课程名称 数据结构 课题名称 专 业 班 级 学 号 姓 名 指导教师 陈淑红 李杰君 2014年 月 日  湖南工程学院 课 程 设 计 任 务 书 课程名称 数据结构 课 题 专业班级 学生姓名 学 号 指导老师 陈淑红 审 批 任务书下达日期 201 年 6 月 日 任务完成日期 201年 月 日 1设计内容与设计要求 1.1设计内容 1.1.1 算术24游戏演示 由系统随机生成4张扑克牌，用户利用扑克牌的数字及运算符号“+”、“—”、“*”、“/”及括号“（”和“）”从键盘上输入一个计算表达式，系统运行后得出计算结果，如果结果等于24，则显示“Congratulation!”，否则显示“Incorrect!” 设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。 1.1.2 迷宫探索 随机生成一个迷宫图，迷宫大小为N*N，N预定义为常数，修改N的值可以改变迷宫的大小。用白色表示可走的路，蓝色表示墙壁不可以通过。系统设计两种运行方式：一种是系统自动探索（用递归方法实现）；另一种是由人工操作探索通路。 设计思路：程序首先要考虑迷宫的表示，这是一个二维关系图，所以可选择二维数组来存储。数组元素只有两种值0和1，分别代表通路和墙壁。图形的显示可以根据数组元素的值来确定。如果是人工探索，则依据按键来确定探索物的位置坐标，利用循环语句实现。如果是系统自动探索，可采用递归算法实现。 1.1.3 二叉树遍历演示 演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表NULL。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。 1.1.4 拓扑排序演示 演示拓扑排序的过程。按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。要求每输出一个顶点后就演示从图中删去此顶点以及所有以它为尾的弧。 1.1.5 图的遍历 演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。要求图的结点数不能少于6个。可以由系统随机生成图，也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。 1.1. 双链表创建演示 建立一个递增有序的双链表。功能是随机生成8个结点数据，每生成一个结点则申请空间得到一个指针，将数据存放到指针所指的数据域中，然后将结点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入位置，第二演示插入过程中指针的变化，第三步显示插入后的链表结果。 1.1.公园导游图 给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。要求用图示展示最佳路径。Prim算法或Kruskal算法求该图的最小生成树，并用图形展示相应的过程步骤。 1.2 选题方案所选题目根据学号确定，学号模加1，即（学号%+1）。如你的学号为1，则所选题目号为：1%8+1＝（题目）。注意，所有的课题都要求用图形方式演示步骤和结果。 1.3设计要求1.3.1 课程设计报告规范 （1）需求分析 程序的功能。 输入输出的要求。 （2）概要设计 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。 （3）详细设计 采用C语言定义相关的数据类型。 写出各模块的类C码算法。 画出各函数的调用关系图、主要函数的流程图。 （4）调试分析以及设计体会 测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。 程序调试中遇到的问题以及解决问题的方法。 课程设计过程经验教训、心得体会。 （5）使用说