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

1、.C语言与数据结构课程设计报告       学 号 2011013759  姓 名 俞杰 课程设计题目 迷宫求解 小组成员 俞杰 安飞 洪飞  2012 年 12 月 目 录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应用程序运行环境

2、要求5.5输入数据类型、格式和内容限制6 总结提高6.1课程设计总结6.2开发中遇到的问题和解决方法6.3 对自己完成课设完成情况的评价6.4C语言与数据结构课程设计课程的意见与建议附录：程序源代码1 需求分析 1.1 功能与数据需求 1.1.1 题目要求的功能 以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。 0010001000100010000011010111001000010000010001010

3、11110011100010111000000 1 2 3 4 5 6 7 8 1.1.2 扩展功能 （1）编写递归形式的算法，求得迷宫中所有可能的通路； （2）以方阵形式输出迷宫及其通路。1.2 界面需求 输入行数和列数 输入每一行中的通路（0，0）和障碍（1,1）. 输入入口坐标（1,1）和出口坐标（m,n）.1.3 开发环境与运行需求 开发环境 Microsoft Visual C+ 6.0 最低运行需求 windows xp ;32位系统2 概要设计 2.1主要数据结构： typedef struct /*用于存放迷宫的位置和该点信息*/ int x,y,d;Datatype;type

4、def struct /*该栈用于存储走过的结点*/ Datatype dataMAXSIZE; int top;Sqstack,*PSqstack;typedef struct /*用于存放当前结点可走的四个方向*/ int x,y;item;2.2程序总体结构 输入起始位置，终点位置 判断首节点是否为通路判断路径能否走通对坐标标记 是否到达迷宫出口处南边是否存在通路东边是否存在通路北边是否存在通路存储路径，将路径入栈 有解迷宫 无解迷宫 YNYNY输出迷宫 选择路径 西边是否存在通路 打印所走的路径2.3各模块函数说明 PSqstack Init_Sqstack() /*初始化空栈*/in

5、t Push_Sqstack(PSqstack s,Datatype x) /*入栈*/int Pop_Sqstack(PSqstack s,Datatype *x) /*出栈*/void Destroy_Sqstack(PSqstack *s) /*销毁栈*/int Mazepath(int mazen+2,int x0,int y0) /*求迷宫路径函数，入口参数： 指向迷宫数组的指针，开始点（x0,y0）*/Pop_ Sqstack(s,&temp);Push_Sqstack(t,temp); /*栈t是栈s的逆，因为s保存 的途径是反的，加t 使输出的途径变为正*/3 详细设计

6、3.1算法分析与设计 思路：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。实现：假设“当前位置”指的是“在收索过程中某一时刻所在图中某个方 块位置”，则求迷宫中的一条路径的算法的基本思想是：若当前位置“可通”， 则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”则应该顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探

7、索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东·南·西·北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“从当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“入栈” 。3.2主要程序段设计void main() int i,j; int mazem+2n+2; printf("请输入迷宫矩阵:9*8n"); for(i=0,j=0;i<m+2;i+) /*将迷宫四周赋值为1，即不可

8、走*/ mazeij=1; for(i=0,j=0;j<n+2;j+) mazeij=1; for(i=0,j=n+1;i<m+2;i+) mazeij=1; for(i=m+1,j=0;j<n+2;j+) mazeij=1; for(i=1;i<m+1;i+) /*给迷宫赋值*/ for(j=1;j<n+1;j+) scanf("%d",&mazeij); for(i=0;i<m+2;i+) /*打印迷宫*/ for(j=0;j<n+2;j+) if(mazeij=0) printf(" "); els

9、e printf("#"); printf("n"); Mazepath(maze,1,1);主函数设计main定义迷宫数组；将迷宫四周赋值为1，即不可走；按所给格式 输入迷宫矩阵（m，n），1为路障，0为该位置为通路；打印迷宫矩阵；调用Mazepath函数；int Mazepath(int mazen+2,int x0,int y0) /*求迷宫路径函数， 入口参数：指向迷宫数组的指针，开始点（x0,y0）*/PSeqstack s,t;Datatype temp;int x,y,d,i,j;item move4;if(maze11=1|mazemn=

10、1)printf("输入迷宫数据错误，起点和终点应为:0n");elsemove0.x=0;move0.y=1;move1.x=1;move1.y=0;move2.x=0;move2.y=-1;move3.x=-1;move3.y=0; /*对move定义为向四个方向探索的数组*/s=Init_Seqstack(); /*初始化栈s*/t=Init_Seqstack(); /*初始化栈t*/if(!s)printf("栈初始化失败n");return (0);temp.x=x0;temp.y=y0;temp.d=0;Push_Seqstack(s,tem

11、p); /*迷宫入口点入栈*/while(s->top!=-1)Pop_Seqstack(s,&temp);x=temp.x;y=temp.y;d=0; /*将方向重新定位为右方，即move0*/while(d<4) /*在该点向四个方向尝试走*/i=x+moved.x;j=y+moved.y;if(mazeij=0) /*该路可走*/temp.x=x;temp.y=y;temp.d=d;Push_Seqstack(s,temp); /*将可走的路入栈*/x=i;y=j;mazexy=-1; /*将走过的点标记为-1*/if(x=m&&y=n) /*判断走到

12、终点*/printf("该迷宫的走法为:n");while(s->top!=-1)Pop_Seqstack(s,&temp);Push_Seqstack(t,temp); /*栈t是栈s的逆，因为s保存的途径是反的，加t使输出的途径变为正*/Destroy_Seqstack(&s); /*销毁栈*/while(t->top!=-1) /*打印走过的途径*/Pop_Seqstack(t,&temp); printf("<%d,%d,%d>",temp.x,temp.y,temp.d);printf("

13、;<%d,%d>",m,n);Destroy_Seqstack(&t); /*销毁栈*/return OK;elsed=0; /*将方向定位为右方*/elsed+; /*尝试其 他方向是否可走*/printf("该迷宫无法走出n");Destroy_Seqstack(&s);return ERROR;Mazepath函数if（迷宫入口或迷宫是否有通路）Printf（“输入迷宫数据错误“）；else对move定义为向四个方向探索的数组初始化栈s，t；迷宫入口点入栈While（判断s是否为空） 入口参数：指向迷宫数组的指针，开始点（x0,y

14、0）while（d<4）初始位置If（该路口走）将可走的路入栈将走过的点标记为-1If（ 判断走到终点）栈t是栈s的逆，因为s保存的途径是反的加t使输出的途径变为正；销毁栈s；打印走过的途径；销毁栈t；Else将方向定位为右方*/Else尝试其他方向是否可走*/4 测试 迷宫路径测试迷宫方向测试无法走出迷宫的测试完整的迷宫测试5 使用说明5.1应用程序功能的详细说明 使用者自己设计一个（9，8）迷宫，迷宫为9行8列的矩阵，1表示该 位置为路障，0表示该位置为通路， 每一行中两位置之间用空格隔开。进 入下一行设计按enter键。设计特别要求，矩阵位置（1,1）,（9,8）为0， 否则程序不

15、能运行。 按enter键运行程.5.2应用程序运行环境要求 Microsoft Visual C+6.05.5输入数据类型、格式和内容限制 输入的数据都是整型（int），输入迷宫的数据间要用空格或回车隔开6 总结提高6.1课程设计总结这次的实验，我们发现书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题不但要深入地理解，而且要不断地更正以前的错误思维，才能完成实验设计。通过这次的课程设计我们也更加理解和掌握了栈和数组的正确使用方法，更为重要的是了解了通过数组和结构体结合来生成的数据结构的特点及应用，这是在这之前未接触过的。总之，通过这次的课程设计，让我对计算机编程在实际问题中的

16、应用有了极大的了解，同时也让我知道了栈的强大，很多问题都可以用栈来解决。6.2开发中遇到的问题和解决方法1.（安飞）问题：对循环结构与数组结合对迷宫外墙的的设计不知道该怎么应用。 解决方法：上网查找几个迷宫的设计，以后结合自己的理解，小组讨论后，建了一个二维数组，定义2个变量，控制变量法，让迷宫四周为1。2. (洪飞) 问题：对于点向四个方向的走向不清楚，不知道如何判断该路是否可走，最后如何判断到达终点以及出栈。解决方法：首先将迷宫口的点入栈，然后将点的坐标赋值给x,y，将方向重新定位为右方。用while循环来判断四个方向是否可走，用if语句来来判断该路是否可走，最后将走过的路径入栈，将走过的

17、点标记为-1，同样用if语句来判断到达终点，最后出栈。3.（俞杰）问题：刚开始的时候我们只定义了一个栈s=Init_Sqstack()；但是在输出结果时发现无法把所有走过的坐标输出来！最后通过讨论，知道原来栈是后进先出，所以只能输出最后一个坐标。 解决方法：引入另一个栈t=Init_Sqstack();它的作用是：栈t是栈s的逆，因为s保存的途径是反的，加t 使输出的途径变为正，这样就可以把所有的坐标输出来。6.3 对自己完成课设完成情况的评价 在这次的课程设计中，我们小组通过对栈和数组的运用，终于完成了迷宫求解的编程,在我们刚拿到题目的时候，我们就知道这一次的任务必须要栈来实现，所以我们把栈

18、的内容复习了一下才开始编的，不过当我们把栈的部分编好的时候，才知道后面的似乎更难。在方向的可走上我提出使用类似于二维坐标的方式来实现，也就是数组move .x或move .y来实现的。我觉得这种思想好在把数学的知识融合在程序里，使的整个程序更容易理解。最后，在我们三个人共同讨论、上网查找相关知识和向其他同学请教最终解决了遇到的问题，完成了整个设计。6.4C语言与数据结构课程设计课程的意见与建议 C语言是数据结构这门课的核心，没有良好的c语言基础，学习这门课程是很难的。首先，我们在阅读数据结构的时候，都是用c语言编写的，这就需要我们把程序看懂；其次，当你完成某部分的数据结构的知识时，必须要把它完

19、整了，才能在VC+ 6.0上运行，我发现我们在完成编程后，main函数部分是我们最容易错的部分，这和我们c语言的基础有关吧。所以我的建议是：1. 希望老师在上课的时候能够简单帮我们复习回顾一下c语言知识。2. 希望老师能够在举例的时候能够多用几个完整的程序，这样可以运行给我们看看，更能够加深我们对知识的理解。附录：程序源代码#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100#define ERROR 0#define OK 1#define m 9#define n 8typedef struct /*用于存放迷

20、宫的位置和该点信息*/int x,y,d;Datatype;typedef struct /*该栈用于存储走过的结点*/Datatype dataMAXSIZE;int top;Sqstack,*PSqstack;typedef struct /*用于存放当前结点可走的四个方向*/int x,y;item;PSqstack Init_Sqstack() /*初始化空栈*/PSqstack s;s=(PSqstack)malloc(sizeof(Sqstack);if(s)s->top=-1;return s;int Push_Sqstack(PSqstack s,Datatype x)

21、/*入栈*/if(s->top=MAXSIZE-1)return ERROR; /*栈满不能入栈*/elses->top+;s->datas->top=x;return OK;int Pop_Sqstack(PSqstack s,Datatype *x) /*出栈*/if(!s)return ERROR; /*栈控不能出栈*/else*x=s->datas->top;s->top-;return OK;void Destroy_Sqstack(PSqstack *s) /*销毁栈*/if(*s)free(*s);*s=NULL;return;int M

22、azepath(int mazen+2,int x0,int y0) /*求迷宫路径函数，入口参数：指向迷宫数组的指针，开始点（x0,y0）*/PSqstack s,t;Datatype temp;int x,y,d,i,j;item move4;if(maze11=1|mazemn=1)printf("输入迷宫数据错误，起点和终点应为:0n");elsemove0.x=0;move0.y=1;move1.x=1;move1.y=0;move2.x=0;move2.y=-1;move3.x=-1;move3.y=0; /*对move定义为向四个方向探索的数组*/s=Init

23、_Sqstack(); /*初始化栈s*/t=Init_Sqstack(); /*初始化栈t*/if(!s)printf("栈初始化失败n");return (0);temp.x=x0;temp.y=y0;temp.d=0;Push_Sqstack(s,temp); /*迷宫入口点入栈*/while(s->top!=-1)Pop_Sqstack(s,&temp);x=temp.x;y=temp.y;d=0; /*将方向重新定位为右方，即move0*/while(d<4) /*在该点向四个方向尝试走*/i=x+moved.x;j=y+moved.y;if(mazeij=0) /*该路可走*/temp.x=x;temp.y=y;temp.d=d;Push_Sqstack(s,temp); /*将可走的路入栈*/x=i;y=j;mazexy=-1; /*将走过的点标记为-1*/if(x=m&&y=n) /*判断走到终点*/printf("该迷宫的走法为:n");while(s->top!=-1)Pop_Sqstack(s,&temp);Push_Sqstack(t,temp); /*栈t是栈s的逆，因为s保存的途径是反的，加t使输出的途径变