数据结构：迷宫课程设计

1、数据结构课程实验报告学院：物光学院班级：姓名：学号：实验设备：计算机1台实验日期：2008年12月27日实验项目名称综合试验一迷宫问题实验目的仅仅认识到栈是一种特殊的线性表是远远不够的，本次实习的目的 在于深入了解栈的特征，以便在实际问题背景下灵活运用它，同时 还将巩固这种数据结构的构造方法。实验要求：要求设计程序输出如下：(1)建立一个大小为mXn的任意迷宫(迷宫数据可由用户输入或由程序自动生成)，并在屏幕上显示出来；找出一条通路的二元组(1门)数据序列，(i,j)表示通路上某一点的坐标。用一种标志(如数字8)在迷宫中标出该条通路；在屏幕上输出迷宫和通路；上述功能可用菜单选择。实验内容(包括

2、步骤)：问题描述迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的 门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在 出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行 上述实验， 直到老鼠从入口走到出口，而不走错 步。老鼠经过多次试验最终学会走 通迷宫的路线。设计 个计算机程序对任意设定的矩形迷宫如下图A所示，求出 条从 入口到出口的通路，或得出没有通路的结论。调试与结果测试：#include #include #define MAX 15#define NULL 0typedef struct listnode

3、(int adjno;struct listnode *next;listnode;typedef struct(int data;listnode *first;headnode;typedef struct(headnode vexsMAX*MAX;int vexnum;int rownum;int colnum;adjlist;adjlist G;/*输入迷宫，0为可通行，1为不可通行，用二维矩阵表示*/adjlist input (int mazeMAX,adjlist G)(int i,j;int rownum,colnum;printf(Please input the lengt

4、h of the maze:n)；printf(rownum=)；scanf(d，&G.rownum);printf(colnum=)；scanf(d,&G.colnum);for(i=0;iG.rownum;i+)printf(Input the %d row： %d ，i+1,i+1);for(j=0;jG.colnum;j+)scanf(d,&mazeij);return(G);/*二维数组向无向图的转化*/adjlist change (int mazeMAX,adjlist G)(int i,j;listnode *p;G.vexnum二G.rownum*G.colnum;for(i

5、=0;iG.vexnum;i+)/* 图中结点的初始化 */(G.vexsi.data=mazei/G.colnumi%G.colnum;G.vexsi.first二NULL;for(i=0;iG.rownum;i+)/*将无向边用指针表示出来*/for(j=0;j=0&mazei-1j=0)(p=(listnode *)malloc(sizeof(listnode);p-adjno=(i-1)*G.colnum+j;p-next=G.vexsi*G.colnum+j.first;G.vexsi*G.colnum+j.first二p;if(i+1adjno=(i+1)*G.colnum+j;p

6、-next=G.vexsi*G.colnum+j.first;G.vexsi*G.colnum+j.first二p;if(j-1=0&mazeij-1=0)(p=(listnode *)malloc(sizeof(listnode);p-adjno=i*G.colnum+j-1;p-next=G.vexsi*G.colnum+j.first;G.vexsi*G.colnum+j.first二p;if(j+1adjno=i*G.colnum+j+1;p-next=G.vexsi*G.colnum+j.first;G.vexsi*G.colnum+j.first=p;if(i-1=0&j-1=0&

7、mazei-1j-1=0)(p=(listnode *)malloc(sizeof(listnode);p-adjno=(i-1)*G.colnum+j-1;p-next=G.vexsi*G.colnum+j.first;G.vexsi*G.colnum+j.first=p;if(i-1=0&j+1adjno=(i-1)*G.colnum+j+1;物光学院计算机类实验报告 p-next=G.vexsi*G.colnum+j.first;G.vexsi*G.colnum+j.first二p;if(i+1=0&mazei+1j-1=0)p=(listnode *)malloc(sizeof(lis

8、tnode);p-adjno=(i+1)*G.colnum+j-1;p-next=G.vexsi*G.colnum+j.first;G.vexsi*G.colnum+j.first二p;if(i+1G.colnum&j+1adjno=(i+1)*G.colnum+j+1;p-next=G.vexsi*G.colnum+j.first;G.vexsi*G.colnum+j.first二p;return(G);/*用int travgraph ()函数广度优先遍历无向图*/int travgraph(adjlist G,int record,int entry,int exit) (listnod

9、e *p;int queueMAX*MAX,visitedMAX*MAX; /*用 visited数组标记图的结点是否遍 历过*/int i;int front=0,rear=1;for(i=0;iadjno=0)visitedp-adjno=1;recordp-adjno=queuefront+1;queue+rear=p-adjno;if(p-adjno=exit)goto end;p=p-next;front=front+1;end:;/*用回溯法找到从出口到入口的路径，并输出*/void output (int record口，int entry,int exit)(int i=0,t

10、;if(entry=exit&G.vexsexit.data=0)printf(Its already at exportn)；elseif(recordexit!=-1)(t=exit;printf(The most short path is as follows： n)；while(t!二entry)printf(%d,%d-，t/G.colnum+1,t%G.colnum+1);t=recordt;if(+i%5=0)printf(n)；printf(%d,%d，t/G.colnum+1,t%G.colnum+1);elseprintf(Have no path from the en

11、trance to the exitn)； void main()(int entry_row,entry_col,exit_row,exit_col,entry,exit;int mazeMAXMAX;int recordMAX*MAX;G=input(maze,G);G=change(maze,G);printf(Inputting the maze entrance sits the mark (*, *)：);scanf(d,%d，&entry_row,&entry_col);printf(Inputting the maze exports to sit the mark (*, *

12、)：);scanf(d,%d，&exit_row,&exit_col);entry=entry_row*G.colnum+-entry_col;exit=exit_row*G.colnum+exit_col;travgraph(G,record,entry,exit);output(record,entry,exit);getch();1.所示输入迷宫大小：行数（=15）： 6/列数（=15）： 10/0表示可通行，1表示不能通过。输入第1行：10111111111输入第2行：20100100011输入第3行：30001101001输入第4行：40110001101输入第5行：50000100001输入第6行：6111111