数据结构课程设计实验报告模板.docx

《数据结构课程设计实验报告模板.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计实验报告模板.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计实验报告模板 数据结构课程设计（2022/2022学年第二学期） -迷宫问题求解 系别：软件学院 指导教师： 班级： 学号： 姓名： 目录 一、课程设计实验报告 (1) 二、需求分析描述 (1) 三、基本要求 (1) 四、系统分析与设计 (1) 五、迷宫求解代码 (6) 六、调试分析 (13) 七、实验心得与体会 (14) 八、参考文献 (14) 一、需求分析描述 1.一个迷宫可用上图所示方阵m,n表示，0表示能通过，1 表示不能 通过。现假设耗子从左上角1,1进入迷宫，编写算法，寻求一 条从右下角m,n 出去的路径 2.迷宫数据由程序提供，迷宫随机生成。 3.程序执行命令为：

2、（1）、创建迷宫；（2）、求解迷宫；（3）、输 出迷宫。 二、基本要求 1.首先实现长宽的输入功能 2.实现自动生成迷宫的方法,我们以1为阻碍,0为通路来设计. 3.实现栈 的输入,输出,判断路径,不对的返回,对的进栈.4,最后输出迷宫的正确路径. 创新要求： 首先输入迷宫的长宽的,然后实现栈的输入,输出,判断路径,不对的返回,对的进栈,最后输出迷宫的正确路径.可以看到每个迷宫都存在“围墙”，用1作为迷宫的围墙，如果没有通路。则输出无通路。 三、系统分析与设计 1 、系统分析（功能要求）： 1void initstack(sqstack *s);/*初始化栈*/ 将栈顶和栈底分别申请一段动态存

3、储空间，将栈分配长度为100的空间，将栈的原始长度定义为2 2void stackpush(sqstack *s,int);/*增加栈顶*/ 将栈的动态存储空间增加50，将栈顶指针上移相应高度，特殊情况单独考虑见程序。 3void stackpop(sqstack *s);/*撤销栈顶*/ 栈空提示无法删除，其他情况删除栈顶。 4void stackinput(sqstack *s);/*输出栈*/ 输出寻找到的一条迷宫路径 5int mgway(sqstack *s);/*迷宫路径*/ 寻找到可执行的一条迷宫路径 6void destorystack(sqstack *s);/*撤销栈S*/

4、 将栈内元素清空 7void makemg(sqstack *s);/*制造迷宫*/ 输入迷宫的长宽（2-15），并产生迷宫图 2、设计方案 求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的

5、下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。 为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。 3、 4、概要设计 1.方阵栈： #define STACK_INI_SIZE 100 typedef struct int *top; /指向栈的顶端域 int *base; /指向栈的低端域 int length; /栈的长度 int stacksize; /栈的最大长度 sqstack; 2.产生迷宫的矩阵二维数组 为了使每一个迷宫存在迷宫的边界和两个端口：入口

6、、出口，设置了一个二维数组，在迷宫的周边定义为1，使得迷宫存在边界，并在（1,1），（x-2,y-2）初定义为0，即定义迷宫的出口，大大减小了无解的情况。 for(i=0;itop=s-base=(int *)malloc(STACK_INI_SIZE*sizeof(int); if(!s-base) exit(1); s-stacksize=STACK_INI_SIZE; *(s-base)=0; s-top+; *(s-top)=101; s-top+; s-length=2; void stackinput(sqstack *s)/*迷宫栈的输出*/ int w,y,z,i=0,*p;

7、p=s-base; p+; printf(n迷宫正确路径n); while(p!=s-top) printf(%d,%d),y=*p/100%10,w=*p%10); p+; i+; if(i=7) printf(n); i=0; void stackpush(sqstack *s,int i)/*增加栈顶*/ if(s-length=s-stacksize) printf(路过); s-base=(int *)realloc(s-base,(STACK_INI_SIZE+STACKINCREMENT)*sizeof(int); if(!s-base) exit(1); s-top=s-bas

8、e+s-length; s-stacksize+=STACKINCREMENT; stackinput(s); if(s-length=0) *(s-base)=i; s-top+; s-length+; else *(s-top)=i; s-top+; s-length+; void stackpop(sqstack *s)/*删除栈顶*/ if(s-length=0) printf(栈空无法删除); if(s-length=1) s-top-; *(s-top)=*(s-base)=NULL; s-length=0; else s-top-; *(s-top)=NULL; s-length

9、-; int mgway(sqstack *s)/*迷宫路径*/ int gudge(sqstack *s,int);/*判断是否能通行*/ int homing(sqstack *s);/*退栈后I所对应的方向*/ int i=1,j,k; while(s-top!=s-base) if(itop; q=s-base; q+; p-; while(p!=q&*p!=i) p-; if(*p=i) return(0); else return(1); int homing(sqstack *s)/*i退位后所对应的方向*/ int a,b,c,d,*q; q=s-top; q-; a=(*q)

10、/100; b=(*q)%100; q-; c=(*q)/100; d=(*q)%100; m=(*q)/100; n=(*q)%100; if(a=c) if(d-b=1) return(3); else if(d-b=-1) return(1); else if(b=d) if(c-a=1) return(4); else if(c-a=-1) return(2); return(0); void destorystack(sqstack *s) if(*(s-base)!=NULL) free(s-base); s-length=0; void makemg(sqstack *s) /*创建迷宫及输出迷宫图的函数*/ int mgway(sqstack *s); void clearstack(sqstack *s); int flag=1,flag2=1,i,j,k; char ch; while(flag) printf(nnttt迷宫tttnnn); printf(请输入迷宫的长宽(4-15):n); printf(输入长:); fflush(stdin);