第一篇：2數(shù)據(jù)結(jié)構(gòu)-實(shí)驗(yàn)報(bào)告二(棧和隊(duì)列及其應(yīng)用)

實(shí)驗(yàn)二 棧和隊(duì)列及其應(yīng)用

一、實(shí)驗(yàn)?zāi)康?/p>

1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類(lèi)型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。

2.熟練掌握棧類(lèi)型的兩種實(shí)現(xiàn)方法。

3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。

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

用隊(duì)列求解迷宮問(wèn)題 [問(wèn)題描述] 以一個(gè)M*N的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和墻壁。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。[基本要求] 實(shí)現(xiàn)一個(gè)以順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i，j，pre）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，pre表示本路徑中上一個(gè)方塊在隊(duì)列中的下標(biāo)。

[測(cè)試數(shù)據(jù)] 由學(xué)生任意指定。

三、源代碼

# include #define M 5 #define N 5

//行數(shù) //列數(shù)

//隊(duì)最多元素個(gè)數(shù)

//一個(gè)迷宮,其四周要加上均為1的外框{1,1, #define MaxSize 100 int mg[M+2][N+2]={ {1,1,1,1,1,1,1}, {1,0,0,0,0,0,1}, {1,0,1,0,0,1,1}, {1,0,1,0,0,1,1}, {1,0,1,0,1,0,1}, {1,0,0,0,0,0,1}, {1,1,1,1,1,1,1} };

typedef struct {int i,j;int pre;} Box;typedef struct { Box data[MaxSize];int front, rear;}QuType;void mgpath1(int xi,int yi,int xe,int ye)//搜索路徑為：（xi，yi）{ void print(QuType qu, int front);->(xe,ye)

int i,j,find=0,di;QuType qu;//定義順序隊(duì) qu.front=qu.rear=-1;qu.rear++;qu.data[qu.rear].i=xi;//(xi,yi)進(jìn)隊(duì) qu.data[qu.rear].j=yi;qu.data[qu.rear].pre=-1;mg[xi][yi]=-1;while(qu.front!=qu.rear&&!find){qu.front++;i=qu.data[qu.front].i;j=qu.data[qu.front].j;if(i==xe&&j==ye){find=1;print(qu,qu.front);

}

for

(di=0;di<4;di++)

{

switch(di)

{

case 0 :i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;case 1 :i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;case 2 :i=qu.data[qu.front].i+1;j=qu.data[qu.front].j+1;break;case 3 :i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break;

}

if(mg[i][j]==0)

{find=1;

qu.rear++;

qu.data[qu.rear].i=i;qu.data[qu.rear].j=j;

qu.data[qu.rear].pre=qu.front;

mg[i][j]=-1;

}

} } }

void print(QuType qu, int front){

int k=front,j,ns=0;

printf(“n”);do

{j=k;

k=qu.data[k].pre;

qu.data[j].pre=-1;

} while(k!=0);printf(“迷宮路徑如下：n”);k=0;while(k

ns++;

printf(“t(%d,%d)”,qu.data[k].i,qu.data[k].j);

if(ns%5==0)printf(“n”);} k++;} printf(“n”);} void main()

{ mgpath1(1,1,M,N);printf(“迷宮所有路徑如下:n”);

}

四、測(cè)試結(jié)果：

五、心得體會(huì)

做實(shí)驗(yàn)首先要掌握大量的理論知識(shí)，然后認(rèn)真去完成實(shí)驗(yàn)。做實(shí)驗(yàn)過(guò)程會(huì)碰見(jiàn)較大的困難，這就要需要我們的毅力。小小的迷宮隱藏大大的奧秘。

第二篇：實(shí)驗(yàn)報(bào)告——棧和隊(duì)列的應(yīng)用

實(shí)驗(yàn)5 棧和隊(duì)列的應(yīng)用

目的和要求：

（1）熟練棧和隊(duì)列的基本操作；（2）能夠利用棧與隊(duì)列進(jìn)行簡(jiǎn)單的應(yīng)用。

一、題目

題目1.利用順序棧和隊(duì)列，實(shí)現(xiàn)一個(gè)棧和一個(gè)隊(duì)列，并利用其判斷一個(gè)字符串是否是回文。所謂回文，是指從前向后順讀和從后向前倒讀都一樣的字符串。例如，a+b&b+a等等。

題目2.假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成一隊(duì)。跳舞開(kāi)始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴。若兩隊(duì)初始人數(shù)不相同，則較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪舞曲?，F(xiàn)要求寫(xiě)一算法模擬上述舞伴配對(duì)問(wèn)題，并實(shí)現(xiàn)。

題目3.打印機(jī)提供的網(wǎng)絡(luò)共享打印功能采用了緩沖池技術(shù)，隊(duì)列就是實(shí)現(xiàn)這個(gè)緩沖技術(shù)的數(shù)據(jù)結(jié)構(gòu)支持。每臺(tái)打印機(jī)具有一個(gè)隊(duì)列（緩沖池），用戶(hù)提交打印請(qǐng)求被寫(xiě)入到隊(duì)列尾，當(dāng)打印機(jī)空閑時(shí)，系統(tǒng)讀取隊(duì)列中第一個(gè)請(qǐng)求，打印并刪除之。請(qǐng)利用隊(duì)列的先進(jìn)先出特性，完成打印機(jī)網(wǎng)絡(luò)共享的先來(lái)先服務(wù)功能。

題目4.假設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中的元素, 同時(shí)設(shè)置一個(gè)標(biāo)志tag，以tag == 0和tag == 1來(lái)區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為“空”還是“滿(mǎn)”。試編寫(xiě)與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法。

題目5.利用循環(huán)鏈隊(duì)列求解約瑟夫環(huán)問(wèn)題。

請(qǐng)大家從本組未討論過(guò)的五道題中選擇一道，參照清華鄧俊輝老師MOOC視頻及課本相關(guān)知識(shí)，編寫(xiě)相應(yīng)程序。

選擇題目3：

打印機(jī)提供的網(wǎng)絡(luò)共享打印功能采用了緩沖池技術(shù)，隊(duì)列就是實(shí)現(xiàn)這個(gè)緩沖技術(shù)的數(shù)據(jù)結(jié)構(gòu)支持。

二、程序清單

//Ch3.cpp #include #include #include“ch3.h” template void LinkedQueue::makeEmpty()//makeEmpty//函數(shù)的實(shí)現(xiàn) { LinkNode*p;while(front!=NULL)//逐個(gè)刪除隊(duì)列中的結(jié)點(diǎn)

{

p=front;

front=front->link;

delete p;} };template bool LinkedQueue::put_in(T&x）{//提交命令函數(shù)

if(front==NULL){//判斷是否為空

front=rear=new LinkNode;//如果為空，新結(jié)點(diǎn)為對(duì)頭也為對(duì)尾

front->data=rear->data=x;

if(front==NULL)//分配結(jié)點(diǎn)失敗

return false;} else{

rear->link=new LinkNode;//如不為空，在鏈尾加新的結(jié)點(diǎn)

rear->link->data=x;

if(rear->link==NULL)

return false;

rear=rear->link;} return true;};template bool LinkedQueue::carry_out()//執(zhí)行命令函數(shù) { if(IsEmpty()==true)//判斷是否為空

{

return false;} cout<data<<“ ”;//輸出鏈尾的數(shù)據(jù)，代表執(zhí)行打印命令

LinkNode*p=front;front=front->link;//刪除以執(zhí)行的命令，即對(duì)頭修改

delete p;//釋放原結(jié)點(diǎn)

return true;};void main()

//主函數(shù) { LinkedQueue q;//定義類(lèi)對(duì)象

char flag='Y';

//標(biāo)志是否輸入了命令

const int max=30;//一次獲取輸入命令的最大個(gè)數(shù) while(flag=='Y')//循環(huán) { int i=0;char str[max];//定義存儲(chǔ)屏幕輸入的命令的數(shù)組

gets(str);//獲取屏幕輸入的命令

while(str[i]!='