数据结构迷宫课题

《数据结构迷宫课题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、例7.1求迷宫的最短路径迷宫可用二维数鏡示，下图所示为数組aze[6][8]表示的迷宫，maze[i]j]的値0或为1,前者表示走通，后者表示受阻，设迷宫入口坐标（0,0）,出口坐标（m-1,n-1）,且设maze[0][0]=0和maze[m-1][n-1]=0。01234567010100011001101001100111100110011000110101100000迷宫最短路径的搜索过程迷宫可看成是一个有向图，迷宫中偽0的坐标方位可视做图中一个顶点，两个僞0的相邻顶点之间存在一条弧。而广度优先搜索访问

2、顶点的次序是鶴径长度”渐增的次序来进行的，因此，求迷宫的最短路径可以基于广度优先搜索遍历进行，只要路径存在，从始点出发的搜索过程中必能访问到终点，一旦到达终点，则得到的必为最短路径。1）如何得到迷宫对应的有向图？从迷宫中的任意一个方位（i,j）出发，到达下一个方位（g,h）侧g=i+di[v]h=j+dj[v]v=0,1,2,・・・，7di01I1■1■11dj11)■1■1■112）如何得到路径？从入口到出口的最短路径上的方位必是广度优先搜索遍历过程中搜索到的顶点，因此在遍历过程中应保存所经过的方位，但需要修

3、改链队列的结点结构及其入队列和出队列的算法。将链队列的结点改为’双链”结点。即结点中包next和pre两个指针；修改入队列的操作。插入新的队尾结点时，＞pre域的指针指向刚刚出队列的结点，即当前的队头指针所指结点；修改出队列的操作。出队列时，仅移动队头指针，而移队头结点从链表中謝算法思想：从入口出发，向四周搜索，记下所有下一步能达的坐标点，然后依次再从这点出发，再记下所有下一步能到达的坐标点，依次类推，直到出口为止，然后从出口点沿搜索路径回溯到入口。的一条最短路径。链队列的状态如下所示：312475typede

4、fstruct{intxpos;intypos;}PosType;typedefstructDQNode{PosTypeseat;structDQNode*next;structDQNode*pre;〃指向弧尾的指针}DQNode,*DQueuePtr;typedefstruct{DQueuePtrfront;DQueuePtrreear;}DLinkQueue;voidlnitQueue(DLinkQueue&Q){Q.front=Q.rear=NULL；}voidEnQueue(DLinkQueue&QPo

5、sTypee){p=newDQNode;p->seat.xpos=e.xpos;p->seat.ypos=e.ypos;p->next=NULL;if(!Q.rear){p->pre=NULL;Q.rear=p;Q.front=p;}//ifelse{p->pre=Q.front;Q.rear->next=p;Q,rear=p;}//else}//EnQueuevoidDeQueue(DLinkQueue&Q){Q.front=Q.front->next;}boolQueueEmpty(DLinkQueueQ)

6、{return(Q.front==NULL;}voidGetHead(DLinkQueueQ,PosType&e){e.xpos=Q.front->seat.xpos;e.ypos=Q.front->seat.ypos;}boolShortestPath(intmaze叩，intm,intn,Stack&S){〃求m行n列的迷宫maze中从入口[0][0]到出口[m-1][n-1]的〃最短路径，若存在，则返回TRUE,此时栈S中从栈顶到〃栈底为最短路径所经过的各个方位；若该迷宫不通，则返〃回FALSE,此时栈S

7、为空栈。〃算法7.6DLinkQueueQ;boolvisited[m][n];InitQueue(Q);//队列初始化for(i=0;i

8、头顶点curposfor(v=0;v<8,!found;v++){//搜索8个方向的邻接点npos=NextPos(curpos,v);//类型为RosType的npos是搜索到的下一点if(Pass(npos)){//如果下一点可走通则入队列EnQueue(Q,npos);visited[npos.xpos][npos.ypos]=TRUE;//置到访标志}//ifif(npos.x