數(shù)據(jù)結(jié)構(gòu)實驗報告 棧和隊列

1/11數(shù)據(jù)結(jié)構(gòu)實驗報告計科090909

數(shù)據(jù)及實驗二棧和隊列：迷宮問題求解實驗?zāi)康恼莆諚：完犃械捻樞虼鎯Y(jié)構(gòu)；掌握棧和隊列的操作特性；掌握基于順序棧和鏈隊列的基本操作的實現(xiàn)方法。實驗內(nèi)容設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲迷宮；設(shè)計存儲結(jié)構(gòu)保存從入口到出口的通路；設(shè)計算法完成迷宮問題的求解；分析算法的時間復(fù)雜度。實驗實現(xiàn)1、用棧實現(xiàn)求迷宮從出口到入口的一條路徑（不一定是最短路徑）（1）順序棧結(jié)構(gòu)SeqStack.hconstintStackSize=64;//10只是示例性的數(shù)據(jù)，可以根據(jù)實際問題具體定義template<classT>//定義模板類SeqStackclassSeqStack{public:SeqStack();//構(gòu)造函數(shù)，棧的初始化 ~SeqStack(){}//析構(gòu)函數(shù)voidPush(Tx);//將元素x入棧 TGetTop();TPop();//將棧頂元素彈出 intEmpty();//判斷棧是否為空 voidPrint();//輸出棧中元素private:Tdata[StackSize];//存放棧元素的數(shù)組inttop;//棧頂指針，指示棧頂元素在數(shù)組中的下標(biāo)};template<classT>SeqStack<T>::SeqStack(){ top=-1;}template<classT>voidSeqStack<T>::Push(Tx){if(top==StackSize-1)throw"上溢";top++;data[top]=x;}template<classT>TSeqStack<T>::Pop(){Tx;if(top==-1)throw"下溢";x=data[top--];returnx;}template<classT>TSeqStack<T>::GetTop(){ if(top!=-1)returndata[top];}template<classT>intSeqStack<T>::Empty(){ if(top==-1)return1; elsereturn0;}template<classT>voidSeqStack<T>::Print(){ while(top!=-1) { Ttemp; temp=Pop(); cout<<temp.x<<'\t'<<temp.y<<'\t'<<temp.d<<'\n'; }}主函數(shù)實現(xiàn)四方向查找#include<iostream.h>#include"SeqStack.h"constintN=10;typedefstruct{ intx,y,d;}DataType;structDirectInc{ intdx,dy;};constDirectIncmove[4]={{0,1},{1,0},{0,-1},{-1,0}};voidmazepath(intmaze[N][N]){ DataTypetemp; intg,h,v,i,j; SeqStack<DataType>S;//棧（*S）已建立 temp.x=1;temp.y=1;temp.d=-1;//入口位置及方向 maze[1][1]=-1; S.Push(temp); while(!S.Empty()) { temp=S.GetTop();i=temp.x;j=temp.y;v=temp.d+1; if(v==4)S.Pop(); while(v<4) { g=i+move[v].dx;h=j+move[v].dy; if(maze[g][h]==0) { temp.x=g;temp.y=h;temp.d=v; S.Push(temp); maze[i][j]=-1;i=g;j=h; if(i==N-2&&j==N-2) { S.Print(); return; } elsev=0; } else { v++; if(v==4)S.Pop(); } }//endwhile(v<4) }//endwhile(!S.Empty())}voidmain(){ intmaze[N][N]={{1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; cout<<"從出口到入口的路徑為\n(xy代表坐標(biāo)d代表方向(東0，南1，西2，北3))\nx\ty\td"<<endl; mazepath(maze);}運行結(jié)果：b、八方向查找#include<iostream.h>#include"SeqStack.h"constintN=10;typedefstruct{ intx,y,d;}DataType;structDirectInc{ intdx,dy;};constDirectIncmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};voidmazepath(intmaze[N][N]){ DataTypetemp; intg,h,v,i,j; SeqStack<DataType>S;//棧（*S）已建立 temp.x=1;temp.y=1;temp.d=-1;//入口位置及方向 maze[1][1]=-1; S.Push(temp); while(!S.Empty()) { temp=S.GetTop();i=temp.x;j=temp.y;v=temp.d+1; if(v==8)S.Pop(); while(v<8) { g=i+move[v].dx;h=j+move[v].dy; if(maze[g][h]==0) { temp.x=g;temp.y=h;temp.d=v; S.Push(temp); maze[i][j]=-1;i=g;j=h; if(i==N-2&&j==N-2) { S.Print(); return; } elsev=0; } else { v++; if(v==8)S.Pop(); } }//endwhile(v<8) }//endwhile(!S.Empty())}voidmain(){ intmaze[N][N]={{1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; cout<<"從出口到入口的路徑為\n(xy代表坐標(biāo)d代表方向(東0,東南1,南2,西南3,西4,西北5,北6,東北7))\nx\ty\td"<<endl; mazepath(maze);}運行結(jié)果：2、用隊列實現(xiàn)求迷宮問題從入口到出口的最短路徑鏈隊列結(jié)構(gòu)CirQueue.hconstintQueueSize=100;//定義存儲隊列元素的數(shù)組的最大長度template<classT>//定義模板類CirQueueclassCirQueue{public:CirQueue();//構(gòu)造函數(shù)，置空隊~CirQueue();//析構(gòu)函數(shù)voidEnQueue(Tx);//將元素x入隊TDeQueue();//將隊頭元素出隊TGetQueue();//取隊頭元素（并不刪除）intEmpty();//判斷隊列是否為空 TGet(inti); intGetFront(){returnfront;} intGetRear(){returnrear;}private:Tdata[QueueSize];//存放隊列元素的數(shù)組intfront,rear;//隊頭和隊尾指針，分別指向隊頭元素的前一個位置和隊尾元素的位置};template<classT>CirQueue<T>::CirQueue(){ front=rear=0;}template<classT>CirQueue<T>::~CirQueue(){}template<classT>voidCirQueue<T>::EnQueue(Tx){if((rear+1)%QueueSize==front)throw"上溢";rear=(rear+1)%QueueSize;//隊尾指針在循環(huán)意義下加1data[rear]=x;//在隊尾處插入元素}template<classT>TCirQueue<T>::DeQueue(){if(rear==front)throw"下溢";front=(front+1)%QueueSize;//隊頭指針在循環(huán)意義下加1returndata[front];//讀取并返回出隊前的隊頭元素，注意隊頭指針}template<classT>//指向隊頭元素的前一個位置TCirQueue<T>::GetQueue(){inti;if(rear==front)throw"下溢";i=(front+1)%QueueSize;//注意不要給隊頭指針賦值returndata[i];}template<classT>intCirQueue<T>::Empty(){if(front==rear) return1; else return0;}template<classT>TCirQueue<T>::Get(inti){ if(i>=0&&i<=rear)returndata[i];}主函數(shù)實現(xiàn)（八方向查找）#include<iostream.h>#include"CirQueue.h"constintM=6,N=8;typedefstruct{intx,y,pre;}DataType;structDirectInc{ intdx,dy;};DirectIncmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};voidPrintShortPath(CirQueue<DataType>Q){ inti=Q.GetRear(); do{ DataTypee=Q.Get(i); cout<<'('<<e.x<<','<<e.y<<')'<<"pre:"<<e.pre<<endl; i=e.pre; }while(i!=-1); cout<<endl<<"WholeQueue:"<<endl; for(intu=1;u<=Q.GetRear();u++) { DataTypee=Q.Get(u); cout<<'('<<e.x<<','<<e.y<<')'<<"pre:"<<e.pre<<endl; }}voidRestore(intmaze[M+2][N+2]){ inti,j; for(i=1;i<=M;i++) for(j=1;j<=N;j++) if(maze[i][j]==-1)maze[i][j]=0; for(i=1;i<=M;i++) { for(j=1;j<=N;j++) cout<<maze[i][j]<<""; cout<<endl; }}voidShortPathQue(CirQueue<DataType>*Q,intmaze[M+2][N+2]){ inti,j,g,h,v,find=0; DataTypee={1,1,-1}; Q->EnQueue(e); maze[1][1]=-1; while(!Q->Empty()&&!find) { e=Q->DeQueue(); i=e.x; j=e.y; for(v=0;v<8;v++) { g=i+move[v].dx; h=j+move[v].dy; if(maze[g][h]==0) { e.