順序棧的實現(xiàn)

PAGEPAGE1數(shù)據(jù)結(jié)構(gòu)課程實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)班級計算123實驗日期2014.05.15-2014.05.28姓名學(xué)號實驗成績實驗名稱實驗二順序棧的實現(xiàn)實驗?zāi)康募耙蟆緦嶒災(zāi)康摹考由罾斫忭樞驐５囊饬x，理解用它的插入與刪除操作的算法。【實驗要求】首先實現(xiàn)一個以順序存儲結(jié)構(gòu)(也可以是鏈?zhǔn)酱鎯Y(jié)構(gòu))的棧類型，然后編寫一求解迷宮的非遞歸程序。求得的通路以三元組(i,j,d)的形式輸出，其中：(i,j)指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。（理解InitStack、StackEmpty、Push、Pop和conversion等算法。）實驗題目：迷宮求解實驗環(huán)境硬件平臺：普通的PC機軟件平臺：Windows7操作系統(tǒng)編程環(huán)境：VisualC++6.0實驗內(nèi)容【實驗內(nèi)容】用數(shù)制的轉(zhuǎn)換算法調(diào)試順序棧的基本操作算法。編寫主程序調(diào)用數(shù)制的轉(zhuǎn)換conversion算法，再由conversion調(diào)用InitStack、StackEmpty、Push、Pop算法。用不同的數(shù)轉(zhuǎn)換成不同的進制調(diào)試程序并對相應(yīng)的輸出作出分析；修改輸入數(shù)據(jù)，預(yù)期輸出并驗證輸出的結(jié)果，加深對Push和Pop算法的理解?！締栴}描述】以一個m*n的二維矩陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條(或所有)從入口到出口的通道，或得出沒有通路的結(jié)論。算法描述及實驗步驟實驗設(shè)計：抽象數(shù)據(jù)類型：typedefstruct{ intx;//當(dāng)前位置的橫坐標(biāo) inty;//當(dāng)前位置的縱坐標(biāo) chartype;//當(dāng)前位置的屬性：墻壁或通道(0/1) boolisfoot;//判斷當(dāng)位置是否已走過,true代表已走過}Position;//當(dāng)前位置信息typedefstruct{ intorder;//腳步在地圖上的序號 Positionseat;//行走的當(dāng)前位置 intaspect;//下一步的方向}Block;//腳步typedefstruct{ intwidth;//地圖的長度 intheight;//地圖的寬度 Position*site;//地圖內(nèi)的各個位置}Maze;//地圖typedefstruct{Block*base; Block*top; intlength; intstacksize;}Stack;主程序模塊：intmain(intargc,_TCHAR*argv[]){ Positionstart,end; Blockblk; StackS; intwidth,height; printf("輸入迷宮比例X*Y\n"); printf("輸入X:"); scanf("%d",&width);intPositionComparison(Positionmaze,Positionpos)//判斷當(dāng)前位置是否合法intPass(Maze*maze,Positioncurpos)//判斷當(dāng)前位置是否可以前進或者是否走過voidFootSet(Maze*maze,Positionsite)//留下足跡PositionNextPos(Position&cur,intaspect)//判斷方向IntMazePath(Maze*maze,Positionstart,Positionend,Stack&S)//搜索從入口到出口的路徑迷宮求解流程圖：路徑搜索算法：Do{

若當(dāng)前位置可通，

則{將當(dāng)前位置插入棧頂；

//納入通路

若該位置是出口位置，則結(jié)束；

//求得路徑存放在棧中

否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

}

否則，

若棧不空切棧頂位置尚有其他方向未經(jīng)探索，

則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；

若棧不空但棧頂位置的四周均不可通；

則{刪去棧頂位置；

//從路徑中刪除該通道塊

若棧不空，則重新測試新的棧頂位置，

直至找到一個可通的相鄰塊或出棧至?？照{(diào)試過程及實驗結(jié)果總結(jié)在這次實驗中遇到了很多實際性的問題，在實驗設(shè)計中才發(fā)現(xiàn)，書本上理論性的東西與在實際運用中的還是有一定的出入的，所以有些問題不但要深入地理解，而且要不斷地更正以前的錯誤思維，才能完成實驗設(shè)計。通過這次實驗設(shè)計我也發(fā)現(xiàn)了自身存在的不足之處，雖然感覺理論上已經(jīng)掌握，但在運用到實踐的過程中仍有意想不到的困惑，經(jīng)過一番努力才得以解決。實驗中，通過自己不斷的學(xué)習(xí)，以及和同學(xué)們之間的討論，讓我進一步的了解了棧與數(shù)組的應(yīng)用，這次實驗使我受益匪淺。附錄#include"stdlib.h"#include"stdio.h"#include"time.h"#include<tchar.h>#defineSTACK_INIT_SIZE10typedefstruct{ intx;//當(dāng)前位置的橫坐標(biāo) inty;//當(dāng)前位置的縱坐標(biāo) chartype;//當(dāng)前位置的屬性：墻壁或通道(0/1) intisfoot;//判斷當(dāng)位置是否已走過,true代表已走過}Position;//當(dāng)前位置信息typedefstruct{ intorder;//腳步在地圖上的序號 Positionseat;//行走的當(dāng)前位置 intaspect;//下一步的方向}Block;//腳步typedefstruct{ intwidth;//地圖的長度 intheight;//地圖的寬度 Position*site;//地圖內(nèi)的各個位置}Maze;//地圖typedefstruct{Block*base; Block*top; intlength; intstacksize;}Stack;intInitStack(Stack&S){ S.base=(Block*)malloc(STACK_INIT_SIZE*sizeof(Block)); if(!S.base)return0; S.top=S.base; S.stacksize=STACK_INIT_SIZE; S.length=0; return1;}intPush(Stack&S,Blockdata){ if(S.length>=S.stacksize) { S.base=(Block*)realloc(S.base,(STACK_INIT_SIZE+S.stacksize)*sizeof(Block)); if(!S.base)return0; S.top=S.base+S.stacksize; S.stacksize+=STACK_INIT_SIZE; } *S.top=data; S.top++; S.length++; return1;}intPop(Stack&S,Block&data){ if(S.top==S.base)return0; S.top--; data=*S.top; S.length--; return1;}voidDestroyStack(Stack&S){ free(S.base);}voidClearStack(Stack&S){ DestroyStack(S); InitStack(S);}Maze*GreatMaze(intwidth,intheight)//創(chuàng)建地圖{ Maze*maze=(Maze*)malloc(sizeof(Maze));//為地圖分配存放空間 maze->width=width; maze->height=height; maze->site=(Position*)malloc(width*height*sizeof(Position));//為地圖坐標(biāo)分配空間srand((unsigned)time(NULL));//產(chǎn)生隨機數(shù) inti,k,j=0; if(width>0&&height>0) { for(i=0;i<maze->width;i++) for(k=0;j<maze->height*(i+1);j++,k++) { maze->site[j].x=k; maze->site[j].y=i; intn=rand()%9+1; if(n>5) maze->site[j].type='0';//設(shè)置墻壁 else maze->site[j].type='1';//設(shè)置通道 } } returnmaze;//返回定義好的地圖}voidPrintMaze(Maze*maze)//打印地圖{ inti,j=0; printf("\t"); for(i=0;i<maze->width;i++) printf("%d",i);//打印橫坐標(biāo) printf("\n"); printf("\n"); for(i=0;i<maze->height;i++) { printf("%d\t",i);//打印縱坐標(biāo) for(j;j<maze->width*(i+1);j++) if(maze->site[j].type=='0') printf("■");//打印墻壁 else printf("□");//打印通道 printf("\n"); }}intPositionComparison(Positionmaze,Positionpos)//判斷當(dāng)前位置是否合法{ if(maze.x==pos.x&&maze.y==pos.y) return1; else return0;}intPass(Maze*maze,Positioncurpos){ Position*pos; pos=maze->site; for(inti=0;i<maze->height*maze->width;i++) { if(PositionComparison(*pos,curpos))//判斷當(dāng)前位置是否合法 if(pos->type=='0'||maze->site[i].isfoot==true)//判斷當(dāng)前位置是否可以前進或者是否走過 return0; else return1; pos++; } return0;}voidFootSet(Maze*maze,Positionsite)//留下足跡{ for(inti=0;i<maze->height*maze->width;i++) { if(PositionComparison(maze->site[i],site)) { maze->site[i].isfoot=true;//留下已走過的足跡 } }}PositionNextPos(Position&cur,intaspect){ switch(aspect) { case1:cur.y+=1;break;//向下 case2:cur.x+=1;break;//向右 case3:cur.y-=1;break;//向上 case4:cur.x-=1;break;//向左 }returncur;}intMazePath(Maze*maze,Positionstart,Positionend,Stack&S){ intcurstep; Positioncurpos;//探索的位置 Blockpath;//腳步 InitStack(S); curpos.x=start.x; curpos.y=start.y;//入口 curstep=1;//探索第一步 do { if(Pass(maze,curpos))//當(dāng)前位置是否可以通過 { FootSet(maze,curpos);//留下足跡 path.order=curstep;//當(dāng)前走過的總步數(shù) path.seat=curpos;//踏下腳步 path.aspect=1; Push(S,path);//保存腳步 if(PositionComparison(curpos,end))//判斷是否是重點 return1; curpos=NextPos(curpos,1);//繼續(xù)向下一個方向探索 curstep++;//探索的步數(shù)增加一 } else { if(S.length!=0) { Pop(S,path);//退到上一步 while(path.aspect==4&&S.length!=0)//如果當(dāng)前位置無法再前行,再退回一步 Pop(S,path); if(path.aspect<4)//如果當(dāng)前位置可再繼續(xù)探索 { path.aspect++;//轉(zhuǎn)變探索方向 Push(S,path);//保存當(dāng)前位置(只更新了探索方向) curpos=NextPos(path.seat,path.aspect);//繼續(xù)探索下一個方向 } } } }while(S.length!=0); return0;}intmain(intargc,_TCHAR*argv[]){ Positionstart,end; Blockblk