数据结构c语言课程设计报告1

数据结构c语言课程设计报告 迷宫求解实验报告

C语言与数据结构课程设计报告

学 号 姓 名

课程设计题目 迷 宫 求 解

2011 年 12 月

数据结构c语言课程设计报告 迷宫求解实验报告

目 录

1 需求分析 1.1 功能与数据需求 1.1.1 题目要求的功能 1.1.2 扩展功能 1.2 界面需求 1.3 开发环境与运行需求 2 概要设计 2.1主要数据结构 2.2程序总体结构 2.3各模块函数说明 3 详细设计

3.1算法分析与设计 3.2主要程序段设计 4 测试 5 使用说明

5.1应用程序功能的详细说明 5.2应用程序运行环境要求

5.5输入数据类型、格式和内容限制 6 总结提高

6.1课程设计总结

6.2开发中遇到的问题和解决方法 6.3 对自己完成课设完成情况的评价

6.4《C语言与数据结构课程设计》课程的意见与建议 附录：程序源代码

数据结构c语言课程设计报告 迷宫求解实验报告

1 需求分析 1.1 功能与数据需求 迷宫求解

问题描述：以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

1.1.1 题目要求的功能

基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）, （1,2,2）, （2,2,2） （3,2,3）, （3,1,2）,…。

测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。

1.1.2 扩展功能

（1）编写递归形式的算法，求得迷宫中所有可能的通路；

（2）以方阵形式输出迷宫及其通路

1.2 界面需求

请求输入进入程序 请求输入起始位置

数据结构c语言课程设计报告 迷宫求解实验报告

请求输入终点位置 输出方阵迷宫 输出路径 输出方阵路径

1.3 开发环境与运行需求 Visual C++6.0 2 概要设计

2.1主要数据结构

数据结构c语言课程设计报告 迷宫求解实验报告

输入起始位置，终点位置

判断首节点 是否为通路

Y判断路径能 否走通

N

Y对坐标标记

N路径

处

是 否 到 达 迷 宫 出 口左 边 是 否 存 在 通 下 边 是 否 存 在 通 路 右 边 是 否 存 在 通 路 上 边 是 否 存 在 通 路

Y

路

输

路径，

路径入栈

2.3 各模块函数说明typedef struct{ int pos_x[length];//进栈坐标 int pos_y[length];

数据结构c语言课程设计报告 迷宫求解实验报告

int top; int base;

}Stack; //新建结构体

void initStack(Stack *p) //初始化栈

Push(Stack *p,int x,int y,int d) //入栈具体操作 Pop(Stack *p,int read[2],int d) //出栈并读出前一步的坐标 initMaze(int Maze[10][9])//建立迷宫

Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具体路径的求解 menu();//调用菜单函数 main();//实现迷宫求解的主函数

3 详细设计

迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按左、右、上、下4个方向顺序试探下一

个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。

每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条合适的通路；若退回到了入口处，则说明不存在合法的通路到达出口。

用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。

二维数组的第0行、第

m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。

4 测试

数据结构c语言课程设计报告 迷宫求解实验报告

数据结构c语言课程设计报告 迷宫求解实验报告

5 使用说明

5.1应用程序功能的详细说明

按提示输入数字1进入迷宫，输入迷宫入口，迷宫出口 5.2应用程序运行环境要求 Microsoft Visual C++6.0

5.5输入数据类型、格式和内容限制

输入的数据都是整型（int），输入迷宫的数据间要用空格或回车隔开

6 总结提高

6.1课程设计总结

要能很好的掌握编程,仅仅通过简单的程序的编写是无法达成的,需要大量积累和深入研究才有可能 …… 此处隐藏：4771字，全部文档内容请下载后查看。喜欢就下载吧 ……