数据结构课程设计1.ppt

**数据结构课程设计一、目的通过实际例题设计算法,了解数据结构课程的实际应用。二、设计步骤1.问题分析与系统结构设计充分地分析和理解问题的本身，弄清要求做什么（而不是怎样做）限制条件是什么？按照以数据结构为中心的原则划分模块，即定义数据结构及其上的操作，使得对数据结构的存取仅通过这些操作实现。数据结构课程设计所以，在此过程操作中要综合考虑系统功能，考虑怎样的系统结构清晰、合理、简单和易于调试，最后写出每个过程和函数的算法和规格说明、列出过程或函数之间的调用关系。这个过程称之为系统结构设计，它是一个不断调试的过程。并需要将过程（或函数）的规格说明尽可能地明确具体。数据结构课程设计2.详细设计和编码详细设计和编码是对过程（或函数）规格说明的进一步求精。即：用IF、WHILE等语句写出算法框架。而编码就是程序设计。它是对详细设计的结果进一步求精，并用某种高级语言表达出来；如何编写程序才能较快地完成调式是特别要注意的问题。数据结构课程设计3.上机准备和静态检查上机准备包括以下几方面：高级语言文本几用户测试手册、熟悉机器用户手测、准备调试工具及调试方案及测试数据及用手工执行程序；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。4.上机调试程序数据结构课程设计5.整理实习报告（1）实习报告的内容a.需求与规格说明：描述问题、简述题目要解决的问题是什么？规定如件做什么？b.设计(ⅰ）设计思想：存储结构（题目中心限定的要重复）；数据结构课程设计(ⅱ)设计表示：每个函数或过程的头和规格说明；列出每个过程或函数所调用的过程或函数，可用调用关系图表达。c.用户手册：即使用说明。d.调式报告：调式过程中遇到的主要问题是如何解决的、对设计和编码的回顾讨论和分析；对空分析；改进设想；经验和体会。e.附录：原程序清单（或磁盘）和结果。数据结构课程设计（2）实验报告的要求各种文档资料要用公文纸书写工整，而不能写在程序清单上。各种文档资料要求在程序开发过程中逐渐形成三、实习报告范例1.问题：迷宫问题数据结构课程设计问题描述：用矩阵Mnxn表示一个迷宫，0和1分别表示路和墙壁，迷宫的入口为（1，1）、出口为（n，n)，试求从入口到出口的一条通路。基本要求：写出程序，能够求出一条这样的通路。选择要求：用非递归算法实现求全部可能的通路。2.实习报告（1）要求和规格说明表示迷宫的矩阵在图论的意义下可以视为一个图，数据结构课程设计其中任何一个元素若为0则表示图中一个结点，若它的上、下、左、右邻接元素是0则这两点之间有无向边。因为每个结点最多可能有四个结点0/1作为迷宫的输入形式则输出形式为#—墙壁，路径为“*”、剩余的用“ㄩ”若找不到，报告适当信息。问题要求：写一个程序，求出从过点（1，1）到（n，n）的一条简单路径。数据结构课程设计（a)存储结构：用字符数组存储迷宫与输出一致。因为在迷宫的周围加一圈墙壁“#”(可简化对于是否越出迷宫边界的检测）所以数组定义为：intmaze[0…n+1,0…n+1];（2）设计：（Ⅰ）设计思想另外：因为是递归算法，所以要设栈:intstack[1…stakmax];数据结构课程设计(b)主要算法思想递归算法：其特点是把问题局部化，只考虑在一般状态下如何处理各种情况。设当前元素下为（r，c），若不是墙，可以继续分析处理。若为出口点（r=n，c=n），则记录下最后一个足迹，完成了寻路任务，打印迷宫并标记“成功”。否则，记下足迹，标志它在当前探查路径上，再用同样的策略考虑四个方向上的每个元素。数据结构课程设计非递归算法：把递归算法视为“完成某任务”，如果把任务存放在栈中，非递归算法就是每次只处理栈顶的一项任务。处理效果：可以为直接完成这项任务后退栈，也可能引出几个子任务进栈直至空栈为止。（Ⅱ）设计表示法*