搜索
1数据结构课程设计报告设计题目:迷宫问题院系：数学科学学院专业班级：信息与计算科学学生姓名：夏豪学生学号：09213034指导教师：李晓翠2012年5月25日2目录前言...............................................................................................................................31什么是数据结构·······················································································32学习数据结构有什么用··············································································3一问题定义.................................................................................................................4二可行性研究.............................................................................................................42.1迷宫问题处理系统的基本系统模型·····························································42.2迷宫问题处理系统的功能级数据流图··························································4三需求分析.................................................................................................................5四总体设计.................................................................................................................54.1数据结构设计考虑··················································································54.2逻辑结构存储结构··················································································54.2程序流程图···························································································6五详细设计.................................................................................................................7六编码.........................................................................................................................9七运行结果...............................................................................................................157.1无路径情况··························································································157.2有路径情况··························································································15总结.................................................................................................................16参考文献...............................................................................................................163前言1什么是数据结构？数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构在计算机科学界至今没有标准的定义。各个大家根据自己的理解，都有不同的表述方式（如：LobertL.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。）。数据结构具体指同一类数据元素中，个元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。2学习数据结构有什么用？有很多同学都认为学习数据结构没有多大用处，下面是作者在网上的一些疑问。同学甲：我学数据结构觉得它类似与高中时的数学，很难！但是没用……好像就专门来考验一个人逻辑思维用的，为了要在同学间获得很聪明的虚荣，拼命的研究，从来也没有思考过到底它有什么用处。同学乙：老师总是对我们说想要在IT行业中有所成就就必须学好数据结构，但是我们现在学的这些什么栈、数组、图、树之类的东西，好像和我们编程没有什么联系。现在我们先来说说学习数据结构的意义数据结构是计算机科学与技术专业、计算机信息管理与应用专业，电子商务等专业的基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付当前众多复杂的课题。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好数据结构这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程、编译原理、人工智能、图视学等都是十分有益的。对于数据结构有什么用，人们就用了几点总结出来：1程序＝结构数据＋算法；2数据结构，总的来说，就是你的编程的基本功；3语言更新太快，数据结构不可能过时；4算法是对数据的处理；5数据结构是以后编程的重中之重的基础！没有数据结构就没有编程这一说！你的技术越高，数据结构越显重要！4一问题定义迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。二可行性研究科学技术快速发展的今天，我们也是有各种各样的娱乐生活，小朋友是祖国的未来，在哪个时代都是应该被重视的，小朋友的生活中娱乐智力开发显得格外重要，迷宫游戏就是小朋友们非常熟悉的一种智力开发游戏，现在我们就为这种游戏开发一种能寻找路径的程序，为小朋友提供答案参考。程序使用者迷宫问题处理系统迷宫路径输入输出迷宫问题处理系统的基本系统模型5迷宫问题处理系统的功能级数据流图三需求分析所求路径必须是简单路径（即在求得的路径上不能重复出现同一个通道块）。假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块的位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一个位置”探索，即切换到“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道快的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。四总体设计4.1数据结构设计考虑1）建立一个二维数组白哦是迷宫的路径（0表示通道，1表示墙壁）；2）创建一个栈，用来存储“当前路径”，即“在搜素过程中某一时刻所在图中某个地方的位置”。4.2逻辑结构存储结构1）创建一个Int类型的二维数组intmaze[n1][n2],用来存放0和1（0表示通道，1表示墙壁）；2）创建一个结构体用来存储数组信息（数组的横坐标X，数组的纵坐标Y，方向C）结构体：Typedefstructnode{intx；inty；intc；}linkstack；3）创造一个栈包括（top表示栈顶元素）Linkstacktop[n1*n2]；4.3程序流程图6程序流程图输入一个迷宫（迷宫的大小为10*10，且起点为（1,1））判断当前结点的北面是否走得通判断当前结点是否为通路判断当前结点的东面是否走得通判断当前结点的南面是否走得通判断当前结点的西面是否走得通添加坐标结点路径该迷宫无通路判断路径是否走得通该迷宫无通路是否到达迷宫出口输出由起点到终点的路径YNYNNY7五详细设计1创建数组的大小，数组的大小要求用户自己定义。具体的算法：printf（“请输入迷宫的大小；”）；//输入的大小就规定了数组大小的界限scanf（“%d”，&g）；//再次用scanf来输入使用者要创建的迷宫大小，并且把值赋给g这个参量，用于对于迷宫数组的创建printf（“大小创建完毕，请输入迷宫：\n”）；//此步用来提示用户输入迷宫2用户自己定义迷宫的内容（其中自定义迷宫入口（1,0），迷宫的出口为（g-2，h-1））迷宫的生成的算法：voidsz（intg，inth）{//创建数组函数，设定参量并从主函数中获得要使用的参量inta，b；for（a=0；ag；a++）for（b=0；bh；b++）scanf（“%d”，&maze[a][b]）；}//使用循环来给数组赋值，也就是用来创建迷宫的格式，这是一个自定义的迷宫创建，其中的0和1分别是表示通路和障碍，定义的数组其实就是迷宫的设计图3产生迷宫（其中自定义迷宫入口（1,0），迷宫的出口为（g-2，h-1））算法：voidscsu（intg，inth）{//创建迷宫输出函数，设置参量并从主函数中获得要使用的参量inta，b；printf（“生成的迷宫：\n”）；//提示要实现的内容是什么for（a=0；ag;a++）{for（b=0；bh；b++）printf（maze[a][b]？“#”：“”）；printf（“\n”）；//使用循环语句来实现迷宫的变化，输出迷宫}}4最后，迷宫寻路，在寻路的时候，我们应从入口（1,0）进入迷宫，当迷宫的入口处有障碍或者出口被堵塞，再或者没有通路时整个程序结束，并输出迷宫无解的提示。如果迷宫求解过程中没有出现无解情况，那么在求解的过程中，会输出迷宫的通路路径，并且输出坐标值，让使用者更清楚路径的走法。在寻路的过程中，每走过