数据结构作业二，用链表实现队列，用深搜宽搜解决迷宫问题，另是模版类的用法； 模版类用法举例： 栗子一：
template<class bbb> class Node{ public: bbb data; Node *next; Node(){next=NULL;} };//只在前面加template关键字就可以；栗子二：
template<class ttt> class Linkquuue{ public: Linkquuue(); ~Linkquuue(); void Enqueue(ttt x); int Dequeue(); ttt Getqueue(); int Empty(){if(Front==Rear)return 1;return 0 ;} private: Node<ttt>*Front,*Rear; }; template<class ttt> Linkquuue<ttt>::Linkquuue(){ Node<ttt> *s=new Node<ttt>; s->next=NULL; Front=Rear=s; } template<class ttt> Linkquuue<ttt>::~Linkquuue(){ while(Rear!=Front){ Node<ttt> *p; ttt x; p=Front->next; Front->next=p->next; if(p->next==NULL)Rear=Front; delete p; } } template<class ttt> void Linkquuue<ttt>::Enqueue(ttt x){ Node<ttt> *s=new Node<ttt>; s->data=x; s->next=NULL; Rear->next=s; Rear=s; } template<class ttt> int Linkquuue<ttt>::Dequeue() { if(Rear==Front)return 0; Node<ttt> *p; ttt x; p=Front->next; x=p->data; Front->next=p->next; if(p->next==NULL)Rear=Front ; delete p; return 1; } template<class ttt> ttt Linkquuue<ttt>::Getqueue(){ return Front->next->data; }///类里只在类外加一个模版类声明即可，类外，在哪里加就在哪里加参数表； ///所以模版类声明的有效范围只在当前区域内有效；链表实现队列： 代码：
template<class bbb> class Node{ public: bbb data; Node *next; Node(){next=NULL;} }; template<class ttt> class Linkquuue{ public: Linkquuue(); ~Linkquuue(); void Enqueue(ttt x); int Dequeue(); ttt Getqueue(); int Empty(){if(Front==Rear)return 1;return 0 ;} private: Node<ttt>*Front,*Rear; }; template<class ttt> Linkquuue<ttt>::Linkquuue(){ Node<ttt> *s=new Node<ttt>; s->next=NULL; Front=Rear=s; } template<class ttt> Linkquuue<ttt>::~Linkquuue(){ while(Rear!=Front){ Node<ttt> *p; ttt x; p=Front->next; Front->next=p->next; if(p->next==NULL)Rear=Front; delete p; } } template<class ttt> void Linkquuue<ttt>::Enqueue(ttt x){ Node<ttt> *s=new Node<ttt>; s->data=x; s->next=NULL; Rear->next=s; Rear=s; } template<class ttt> int Linkquuue<ttt>::Dequeue() { if(Rear==Front)return 0; Node<ttt> *p; ttt x; p=Front->next; x=p->data; Front->next=p->next; if(p->next==NULL)Rear=Front ; delete p; return 1; } template<class ttt> ttt Linkquuue<ttt>::Getqueue(){ return Front->next->data; }深搜加宽搜实现迷宫问题（举例说明）， ///实验问题及具体举例说明； /* 迷宫问题。以一维数组Maze[m+2][n+2]数组描述一个迷宫，元素。值为0表示通道，值为1表示墙壁，以 Maze[1][1]表示迷宫的入口，maze[m][n]表示迷宫的出口，外层数据全为1表示外围墙壁，Maze数组内层数据表达一个迷宫（数据来源于输入或随机赋值），打印一条如何从Maze[1][1]到达出口Maze[m][n]的路径，若无解，则打印“无解”信息 迷宫问题举例： 设： 1）：图大小给出，n行m列1<=n,m<=20，图中1为墙壁，0为可走的路； 2）：从当前点可移动到上下左右四点（如果没有障碍及可走的情况下） 3）：求（1,1）到（m，n）所走的最短路，如有多条输出任意一条，没有输出”no a way!”； 4）：描述：多组数据读到文档尾，输入n，m，表示图的大小为n行m列，接下来n行每行有m个数； 输出：输出最短路径，每行一个坐标表示走过的点，多组解输出任意一组，无解情况输出”no a way!”，然后换行； 样例： 样例输入
2 5 0 1 0 0 0 0 0 0 1 0 4 6 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 2 2 0 1 1 0样例输出1
1 1 2 1 2 2 2 3 1 3 1 4 1 5 2 5 no a way! no a way!*/ 具体代码： 简版：
#include <bits/stdc++.h> using namespace std; template<class bbb> class Node{ public: bbb data; Node *next; Node(){next=NULL;} }; template<class ttt> class Linkquuue{ public: Linkquuue(); ~Linkquuue(); void Enqueue(ttt x); int Dequeue(); ttt Getqueue(); int Empty(){if(Front==Rear)return 1;return 0 ;} private: Node<ttt>*Front,*Rear; }; template<class ttt> Linkquuue<ttt>::Linkquuue(){ Node<ttt> *s=new Node<ttt>; s->next=NULL; Front=Rear=s; } template<class ttt> Linkquuue<ttt>::~Linkquuue(){ while(Rear!=Front){ Node<ttt> *p; ttt x; p=Front->next; Front->next=p->next; if(p->next==NULL)Rear=Front; delete p; } } template<class ttt> void Linkquuue<ttt>::Enqueue(ttt x){ Node<ttt> *s=new Node<ttt>; s->data=x; s->next=NULL; Rear->next=s; Rear=s; } template<class ttt> int Linkquuue<ttt>::Dequeue() { if(Rear==Front)return 0; Node<ttt> *p; ttt x; p=Front->next; x=p->data; Front->next=p->next; if(p->next==NULL)Rear=Front ; delete p; return 1; } template<class ttt> ttt Linkquuue<ttt>::Getqueue(){ return Front->next->data; } struct zuobiao { int x,y; zuobiao(int a,int b){x=a;y=b;} zuobiao(){}; }; const int maxn=22; int tu[maxn][maxn]; int lu[maxn][maxn]; int n,m; int showlu(int x,int y) { if(x==0&&y==0){ cout<<x+1<<" "<<y+1<<endl; return 0; } for(int i=-1;i<2;i++){ for(int j=-1;j<2;j++){ if((i==0||j==0)&&i^j!=0) { int si=x+i,wai=y+j; if(si>=0&&si<n&&wai>=0&&j<m){ if(lu[si][wai]==(lu[x][y]-1)){ showlu(si,wai); cout<<x+1<<" "<<y+1<<endl; return 0; } } } } } return 0; } int main() { while(cin>>n>>m){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>tu[i][j]; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(tu[i][j]==1) lu[i][j]=-1; if(tu[i][j]==0) lu[i][j]=0; } } lu[0][0]=1; Linkquuue<zuobiao>qu; qu.Enqueue(zuobiao(0,0)); while(!qu.Empty()){ zuobiao now=qu.Getqueue(); qu.Dequeue(); for(int i=-1;i<2;i++){ for(int j=-1;j<2;j++){ if((i==0||j==0)&&i^j!=0){ int si=now.x+i,wai=now.y+j; if(si>=0&&si<n&&wai>=0&&wai<m){ if(lu[si][wai]==0){lu[si][wai]=lu[now.x][now.y]+1; qu.Enqueue(zuobiao(si,wai)); } } } } } } if(lu[n-1][m-1]==0||lu[n-1][m-1]==-1) cout<<"no a way!"<<endl; else{ showlu(n-1,m-1); cout<<endl; } } return 0; }加注释版：
#include <bits/stdc++.h> using namespace std; template<class bbb> class Node{ ///链表里的节点； public: bbb data; Node *next; Node(){next=NULL;} ///可直接生成节点； }; template<class ttt> class Linkquuue{ ///队列类，用链表结构存储； public: ///构造函数，生成了一个标志节点，没注意这个，debug到天亮； Linkquuue(); ///析构函数，因为是通过new申请的内存，必须要自己动手释放， ///否则析构函数一般不用写东西； ~Linkquuue(); ///入队； void Enqueue(ttt x); ///出队，先入者先出； int Dequeue(); ///得到队头的元素，注意对头有标志节点； ttt Getqueue(); ///判断是否为空；为空输出1，不为空输出0； int Empty(){if(Front==Rear)return 1;return 0 ;} private: ///队列元素，只记录队首和队尾即可； Node<ttt>*Front,*Rear; }; template<class ttt> ///构造函数，申请一个新节点，其实不用，但是改动麻烦，注意即可； Linkquuue<ttt>::Linkquuue(){ Node<ttt> *s=new Node<ttt>; s->next=NULL; Front=Rear=s; } template<class ttt> ///析构函数，析构掉申请的内存，主要构造时候申请的空节点； Linkquuue<ttt>::~Linkquuue(){ while(Rear!=Front){ Node<ttt> *p; ttt x; p=Front->next; Front->next=p->next; if(p->next==NULL)Rear=Front; delete p; } delete Front; } template<class ttt> ///入队操作，在队首添加即可，注意空节点； void Linkquuue<ttt>::Enqueue(ttt x){ Node<ttt> *s=new Node<ttt>; s->data=x; s->next=NULL; Rear->next=s; Rear=s; } ///出队操作，去掉队尾申请的内存即可； template<class ttt> int Linkquuue<ttt>::Dequeue() { if(Rear==Front)return 0; Node<ttt> *p; ttt x; p=Front->next; x=p->data; Front->next=p->next; if(p->next==NULL)Rear=Front ; delete p; return 1; } ///根据先入先出的原则，拿出队首元素， ///主要第一个为空节点，返回第二个节点 template<class ttt> ttt Linkquuue<ttt>::Getqueue(){ return Front->next->data; } ///上面的操作均在模版类中实现，这里具体到类； ///为下面的程序开个坐标类，记录处理到的坐标； struct zuobiao { int x,y; ///支持类型强转； zuobiao(int a,int b){x=a;y=b;} ///支持直接建立坐标类，不必赋值； zuobiao(){}; }; ///本程序的参数，及地图的最大是多少，后期可调； const int maxn=22; ///存图，即原始的数据； int tu[maxn][maxn]; ///存路，之后的操作在这里进行，可保护原始数据； int lu[maxn][maxn]; ///参数允许范围内具体地图的大小，这里开全局是为深搜的调用； int n,m; ///输出路径，宽搜跑地图得到路径，深搜可反向进行搜索，输出路径； int showlu(int x,int y) { ///深搜结束条件，即搜索到起始位置； if(x==0&&y==0){ cout<<x+1<<" "<<y+1<<endl; return 0; } ///从高位向低位进行搜索,因为高位是低位宽搜来的，所以一定有路， ///关系如同，根可以找到n多叶子，叶子只能找到一个根； for(int i=-1;i<2;i++){ for(int j=-1;j<2;j++){ if((i==0||j==0)&&i^j!=0) { int si=x+i,wai=y+j; if(si>=0&&si<n&&wai>=0&&j<m){ if(lu[si][wai]==(lu[x][y]-1)){ ///找到下个点时进行递归操作； showlu(si,wai); ///因为要正着输出路径，所以， ///放在递归的后面，可以从低位输出； cout<<x+1<<" "<<y+1<<endl; ///这里符合条件就返回，保证了只输出一条路径； return 0; } } } } } return 0; } int main() { ///保证有数据就可以读入操作； while(cin>>n>>m){ ///读入数据结构；其实可以写成函数，不过意义不大； for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>tu[i][j]; } } ///路径的初始化操作； for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(tu[i][j]==1) lu[i][j]=-1; if(tu[i][j]==0) lu[i][j]=0; } } ///因为下面的入队条件是等零，所以这里初始化下； lu[0][0]=1; ///首先声明队列，入队起点； Linkquuue<zuobiao>qu; qu.Enqueue(zuobiao(0,0)); while(!qu.Empty()){ ///得到队首元素； zuobiao now=qu.Getqueue(); ///队首处理完成，出队； qu.Dequeue(); for(int i=-1;i<2;i++){ for(int j=-1;j<2;j++){ if((i==0||j==0)&&i^j!=0){ int si=now.x+i,wai=now.y+j; if(si>=0&&si<n&&wai>=0&&wai<m){ if(lu[si][wai]==0){lu[si][wai]=lu[now.x][now.y]+1; qu.Enqueue(zuobiao(si,wai)); ///搜索到下个符合条件的位置入队； } } } } } } ///lu数组没有改变，说明到达不到，输出no a way！； if(lu[n-1][m-1]==0||lu[n-1][m-1]==-1) cout<<"no a way!"<<endl<<endl; ///有路及输出路径； else{ showlu(n-1,m-1); cout<<endl; } } return 0; }