數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題課程設(shè)計(jì)

《熬據(jù)信構(gòu)C》

課程設(shè)計(jì)報(bào)告

一.課程設(shè)計(jì)概述

本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)共完成5個(gè)題目：成

績(jī)分析問(wèn)題，哈夫曼編碼器，迷宮問(wèn)題，八

皇后問(wèn)題，農(nóng)夫過(guò)河問(wèn)題的求解。

使用環(huán)境：C語(yǔ)言。

編譯環(huán)境：VisualStudio2022o

實(shí)驗(yàn)內(nèi)容：

迷宮問(wèn)題。

問(wèn)題描述：

以一^個(gè)m*n(l<=m,n<=100)的長(zhǎng)方陣表示

迷宮,0和1分別表示迷宮中的通路和障礙。

設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一

條從入口到出口的通路，或得出沒(méi)有通路的

結(jié)論。

需求分析：

(1)找出迷宮中的一條通路。求得的通路

以三元組(i,j,d)的形式輸出，其中：(i,

j)指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一

坐標(biāo)的方向。若迷宮中沒(méi)有通路，則輸出“無(wú)

解”。

(2)找出迷宮中所有可能的通路。

(3)如果有通路，找出最短通路。

(4)以方陣形式輸出迷宮及其通路。

概要設(shè)計(jì)：

----ADT—

(

voidstackinit(ST*p);

voidstackpush(ST*p,datatypex);

datatypestacktop(ST*p);

voidstackpop(ST*p);

intstacksize(ST*p);

boolstackempty(ST*p);

voidstackdestroy(ST*p);

存儲(chǔ)結(jié)構(gòu)：

typedefPTdatatype;//將數(shù)據(jù)類型改為結(jié)構(gòu)體

typedefstructstack

datatype*a;

inttop;

intcapacity;

}ST;

設(shè)計(jì)思路：

下面是迷宮問(wèn)題的設(shè)計(jì)思路和關(guān)鍵算法：

通過(guò)遞歸方式，不斷地選擇可通過(guò)的下一個(gè)位置，并將選擇的路

徑保存在棧中，直到找到迷宮出口或者所有路徑都嘗試完畢。最

終，根據(jù)棧中存儲(chǔ)的路徑信息，打印出正確的路徑

1.定義結(jié)構(gòu)體和類型別名：

-TT：表示迷宮中位置的結(jié)構(gòu)體，包含行和列兩個(gè)成員變量。

-'datatype'：將數(shù)據(jù)類型改為結(jié)構(gòu)體，即為'PT'類型。

-'ST'：表示棧的結(jié)構(gòu)體，包含一個(gè)存儲(chǔ)元素的數(shù)組、棧頂指

針和棧的容量。

2.實(shí)現(xiàn)棧的相關(guān)操作：

-'stackinit'：初始化棧。

-'stackpush'：入棧操作。

-'stackpop'：移除棧頂元素。

-'stacktop'：獲取棧頂元素。

-'stackempty'：判斷棧是否為空。

-'stacksize'：獲取棧中元素個(gè)數(shù)。

-'stackdestroy'：銷毀棧。

3.實(shí)現(xiàn)判斷迷宮中指定位置是否可以通過(guò)的函數(shù)：

-'ispass'：根據(jù)給定的迷宮二維數(shù)組、迷宮的行數(shù)和列數(shù)以及

當(dāng)前位置，判斷該位置是否可以通過(guò)。即判斷當(dāng)前位置是否在迷

宮范圍內(nèi)，并且迷宮中當(dāng)前位置是否為可通過(guò)的路徑（值為0）。

4.實(shí)現(xiàn)遞歸函數(shù)求解迷宮路徑：

-'getmazepath'：根據(jù)給定的迷宮二維數(shù)組、迷宮的行數(shù)和列

數(shù)以及當(dāng)前位置，通過(guò)遞歸方式求解迷宮路徑。首先將當(dāng)前位置

入棧，然后判斷當(dāng)前位置是否為迷宮出口，如果是則返回真；否

則，將當(dāng)前位置標(biāo)記為已訪問(wèn)，并依次判斷上、下、左、右四個(gè)

方向的位置是否滿足繼續(xù)遞歸的條件，如果滿足則遞歸調(diào)用該函

數(shù)。如果四個(gè)方向都不滿足條件，則將當(dāng)前位置出棧，并返回假。

5.實(shí)現(xiàn)打印路徑的函數(shù)：

-'printpath'：根據(jù)給定的棧對(duì)象，將棧中的元素按正確順序

打印出來(lái)。由于棧先進(jìn)后出的特性，需要使用一個(gè)新的棧將原始

棧中的元素倒序存儲(chǔ)，然后再?gòu)男聴Ｖ幸来稳〕鰲ｍ斣卮蛴　?/p>

6.主函數(shù)：

-在主函數(shù)中，首先讀取迷宮的行數(shù)和列數(shù)。

-動(dòng)態(tài)分配二維數(shù)組存儲(chǔ)迷宮的數(shù)據(jù)。

-讀取迷宮數(shù)據(jù)。

-初始化路徑棧，并調(diào)用遞歸函數(shù)求解迷宮路徑。

-如果找到了路徑，調(diào)用打印路徑的函數(shù)輸出路徑；否則,

輸出"沒(méi)有通路"。

-銷毀路徑棧。

-釋放動(dòng)態(tài)分配的內(nèi)存空間。

詳細(xì)設(shè)計(jì)：

ttdefine_CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#include<assert.h>

typedefstructpostion

(

introw;〃行

intcol;〃列

}PT;

typedefPTdatatype;〃將數(shù)據(jù)類型改為結(jié)構(gòu)體

typedefstructstack

(

datatype*a;

inttop;

intcapacity;

}ST;

voidstackinit(ST*p);

voidstackpush(ST*p,datatypex);

datatypestacktop(ST*p);

voidstackpop(ST*p);

intstacksize(ST*p);

boolstackempty(ST*p);

voidstackdestroy(ST*p);

voidstackinit(ST*p)〃棧的初始化

(

assert(p);

p->a=NULL;

p->top=0;

p->capacity=0;

)

voidstackpush(ST*p,datatypex)〃入棧

(

assert(p);

if(p->top==p->capacity)

(

intnewcapacity=p->capacity==0?4:2*p->capacity;

datatype*tmp=(datatype*)realloc(p->a,sizeof(datatype)*newcapacity);

if(tmp!=NULL)

{

p->a=tmp;

p->capacity=newcapacity;

)

)

p->a[p->top]=x;

p->top++;

)

voidstackpop(ST*p)〃移除棧頂元素

(

assert(p);

assert(p->top>0);

p->top-;

)

datatypestacktop(ST*p)〃出棧

(

assert(p);

assert(p->top>0);

returnp->a[p->top-1];

}

boolstackempty(ST*p)〃是否為空

(

returnp->top==0;

)

intstacksize(ST*p)〃棧中元素個(gè)數(shù)

assert(p);

returnp->top;

)

voidstackdestroy(ST*p)〃內(nèi)存銷毀

(

assert(p);

free(p->a);

p->a=NULL;

p->top=0;

p->capacity=0;

)

boolispass(int**maze,intN,intM,PTpos)

(

if(pos.row>=0&&pos.row<N&&pos.col>=0&&pos.col<M&&

maze[pos.row][pos.col]==0)

{〃坐標(biāo)不越界并且該處位置二0

returntrue;

)

returnfalse;

)

STpath;

boolgetmazepath(int**maze,intN,intM,PTcur)

(

stackpush(&path,cur);//入棧

if(cur.row==N-1&&cur.col—M-1)〃找到出口就返回真

(

returntrue;

)

maze[cur.row][cur.col]=2;〃先將目前所處位置賦值為2

PTnext;

next=cur;//Jt

next,row-=1;

if(ispass(maze,N,M,next))〃判斷上的位置是否滿足繼續(xù)的條件

(

if(getmazepath(maze,N,M,next))〃滿足條件就遞歸

(

returntrue;〃為了防止找到繼續(xù)遞歸下去返回真

)

)

next=cur;〃下

next,row+=1;

if(ispass(maze,N,M,next))〃判斷下的位置是否滿足繼續(xù)的條件

(

if(getmazepath(maze,N,M,next))〃滿足條件就遞歸

(

returntrue;〃為了防止找到繼續(xù)遞歸下去返回真

)

)

next=cur;〃左

next.col-=1;

if(ispass(maze,N,M,next))〃判斷左的位置是否滿足繼續(xù)的條件

(

if(getmazepath(maze,N,M,next))〃滿足條件就遞歸

(

returntrue;〃為了防止找到繼續(xù)遞歸下去返回真

)

)

next=cur;〃右

next,col+=1;

if(ispass(maze,N,M,next))〃判斷右的位置是否滿足繼續(xù)的條件

(

if(getmazepath(maze,N,M,next))〃滿足條件就遞歸

(

returntrue;〃為了防止找到繼續(xù)遞歸下去返回真

)

)

stackpop(&path);//如果上下左右都不滿足就移除棧頂元素

returnfalse;〃如果上下左右都不滿足就返回false

)

voidprintpath(ST*ps)〃由于此時(shí)的path棧要打印出來(lái)會(huì)倒著出，

〃所以又重新創(chuàng)建了一個(gè)棧，將數(shù)據(jù)導(dǎo)進(jìn)去

(

STrpath;

stackinit(&rpath);

while(!stackempty(&path))

(

stackpush(ferpath,stacktop(fepath));

stackpop(&path);

)

while(!stackempty(&rpath))

PTtop=stacktop(&rpath);〃此時(shí)數(shù)據(jù)類型被改為PT

printf("(%d,%d)”,top.row,top.col);

printf("\n");

stackpop(&rpath);

)

stackdestroy(&rpath);〃內(nèi)存銷毀

)

intmain()

(

intN=0;

intM=0;

while(scanf("%d%d”,&N,&M)!=EOF)〃多組輸入

(

〃動(dòng)態(tài)開辟二維數(shù)組

//I.開辟N個(gè)指針數(shù)組

int**maze=(int**)malloc(sizeof(int*)*N);

//2.開辟M(fèi)個(gè)空間

inti=0;

for(i=0;i<N;i++)

(

maze[i]=(int*)malloc(sizeof(int)*M);

)

intj=0;

for(i=0;i<N;i++)

(

for(j=0;j<M;j++)

(

scanf("%d”,&maze[i][j]);

)

)

PTentry={0,0};

stackinit(fepath);

if(getmazepath(maze,N,M,entry))

(

printpath(&path);〃輸出通路的路徑