华中科技大学数据结构课件2.rar

//==================================迷宫问题（又称电路板问题)=============================== #include<iomanip.h> #include<fstream.h> //=========================================类声明============================== template <class T> class queue; template <class T> class node { friend class queue<T> ; private: T data; node<T> * next; }; //---------- template <class T> class queue { public: queue(){front=rear=NULL;} ~queue(); void enqueue(T a); bool dequeue(T& savedeq); bool empty(); private: node<T> * front; node<T> * rear; }; //---------- class position { public: int row; int col; }; //==============================================类函数声明================================= template<class T> queue<T>::~queue() { node<T>* p; for(int i=0;front;i++) { p=front; front=front->next; delete p; } } //---------- template<class T> bool queue<T>::empty() { return front==NULL; } //---------- template<class T> void queue<T>::enqueue(T a) { node<T> * p=new node<T>; p->data=a; p->next=NULL; if(front==NULL&&rear==NULL) { rear=front=p; } else { rear->next=p; rear=p; } } //---------- template<class T> bool queue<T>::dequeue(T& savedeq) { if(front==NULL&&rear==NULL) return 0; node<T> * p=front; front=front->next; savedeq=p->data; if(front==NULL) rear=NULL; delete p; return 1; } //============================================主程序==================================== void main() { //-------------------------------------初始化迷宫-------------------------------- cout<<"请在文本中输入迷宫方阵.（障碍物用x表示，可通行路径用0表示满意）每行结尾用'.'标识"<<endl; cout<<"结束后按任意键继续："<<endl; char wait; cin>>wait; lb: ifstream fin1,fin2; //对象声明 cout<<"输入文件路径:"; //文件路径指定 char * road=new char [30]; cin>>road; fin1.open(road,ios::in|ios::out|ios::nocreate); //打开文件 if(!fin1) //文件不存在处理 { cout<<"无此文件"<<endl; fin1.close(); goto lb; } char g; int han=0,lie=0; while(fin1>>g) { if(g=='.') ++han; if(han==0) lie++; } fin1.close(); fin2.open(road); int ** p=new int* [han+2]; for(int i=0;i<=han+1;i++) p[i]=new int[lie+2]; for(i=0;i<=han+1;i++) { p[i][0]=-1; p[i][lie+1]=-1; } for(int j=0;j<=lie+1;j++) { p[0][j]=-1; p[han+1][j]=-1; } for(i=1;i<=han;i++) for(j=1;j<=lie+1;j++) if(fin2>>g&&g!='.') { if(g=='0') p[i][j]=0; if(g=='x') p[i][j]=-1; } fin2.close(); cout<<endl; cout<<"你输入的迷宫是："<<endl; cout<<endl; for(i=1;i<=han;i++) { for(j=1;j<=lie;j++) cout<<setw(3)<<p[i][j]; cout<<endl; cout<<endl; } //---------- int h1,l1,h2,l2; // 入口出口设置 cout<<"入口的行:"; cin>>h1; cout<<"入口的列:"; cin>>l1; cout<<"出口的行:"; cin>>h2; cout<<"出口的列:"; cin>>l2; position start,finish; start.row=h1; start.col=l1; finish.row=h2; finish.col=l2; //---------- position offset[4]; //辅助移动对象 offset[0].row=0; offset[0].col=1; offset[1].row=1; offset[1].col=0; offset[2].row=0; offset[2].col=-1; offset[3].row=-1; offset[3].col=0; //---------- int length; //变量声明 position here,nb; //---------- here.row=start.row; //寻找出口程序 here.col=start.col; queue<position> assist; while(true) { for(i=0;i<4;i++) { nb.row=here.row+offset[i].row; nb.col=here.col+offset[i].col; if(p[nb.row][nb.col]==0) { p[nb.row][nb.col]=p[here.row][here.col]+1; if(nb.row==finish.row&&nb.col==finish.col) break; assist.enqueue(nb); } } if(nb.row==finish.row&&nb.col==finish.col) break; if(assist.empty()) { cout<<"不存在通往出口的路"<<endl; char x; cin>>x; return; } assist.dequeue(here); } //---------- length=p[finish.row][finish.col]; //回溯入口 cout<<endl; cout<<"出口到入口的长度是"<<length<<endl; here.row=finish.row; here.col=finish.col; for(i=length;i>=2;i--) { for(j=0;j<4;j++) { nb.row=here.row+offset[j].row; nb.col=here.col+offset[j].col; if(p[nb.row][nb.col]==i-1) break; } p[nb.row][nb.col]=-2; here.row=nb.row; here.col=nb.col; } //----------- char ** result=new char* [han+2]; //二维数组转字符型 for(i=0;i<=han+1;i++) result[i]=new char[lie+2]; for(i=1;i<=han;i++) { for(j=1;j<=lie;j++) { if(p[i][j]==-2) result[i][j]='*'; else if(i==h1&&j==l1) result[i][j]='a'; else if(i==h2&&j==l2) result[i][j]='z'; else if(p[i][j]==-1) result[i][j]='#'; else result[i][j]='_'; } } //----------- ofstream fout; //迷宫输出到文本中 fout.open(road,ios::app); fout<<endl; fout<<"以下是迷宫路线："<<endl; fout<<endl; for(i=1;i<=han;i++) { for(j=1;j<=lie;j++) fout<<setw(3)<<result[i][j]; fout<<endl; fout<<endl; } fout<<"(入口 a 出口 z 路径 * 可通行路径 _ 障碍物 #)"<<endl; fout.close(); cout<<endl; cout<<"结果已保存到"<<road<<endl; char z; cin>>z; }