数据结构课程设计-迷宫、遍历二叉树、文章编辑

1、景德镇陶瓷学院数据结构课程设计报告院系：信息工程学院专业：计算机科学与技术班级：计科2班学号：201310510112姓名：张旸一、 课程设计概述本次数据结构课程设计共完成了3个问题：迷宫问题；建立二叉树，层序、先序遍历；文章编辑使用语言：C语言、C+编译环境：Windows7、Microsoft Visual Studio 2013、VC+ 6.0二、 课程设计内容2.1题目一：迷宫问题1.问题描述 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。2.需求分析（1）实现一个以链表作存储结构的栈类

2、型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中，(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。（2）编写递归形式算法，求得迷宫中所有可能的通路；（3）以方阵形式输出迷宫及其通路（选做）。3.概要设计3.1设计原理程序的三大模块：主程序模块、栈模块和迷宫模块。主程序模块：初始化迷宫模块栈模块：实现迷宫数据的抽象化和对迷宫数据的处理迷宫模块：实现迷宫数据抽象类型int main() 初始化； 接受命令； 处理命令； 返回；各模块之间的调用关系如下：主程序模块迷宫模块栈模块3.2储存结构设计3.2.1设定栈的抽象数据类型定义ADT Stack数据对

3、象：D= ai|ai CharSet,i=1,2,n,n0 数据关系：R1=<ai-1, ai>| ai-1 , ai D,i=2,n 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE,否则返回FALSE。 GetTop(S,&e) 初始条件：栈S已存在。 操作结果：若栈S不空，则以e返

4、回栈顶元素。 Push(&S,e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入信的栈顶元素e。 Pop(&S,&e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。ADT Stack3.2.2设定迷宫的抽象数据类型ADT maze 数据对象：D=ai,j | ai,j 0,1,0im+1,0jn+1,m,n10数据关系：R=ROW,COL ROW= <ai-1,j, ai,j >| ai-1,j , ai-1D,i=1,m+1,j=0,n+1 COL= <ai,j-1, ai,j >| ai,j-1 , ai-1D,

5、i=1,m+1,j=0,n+1 InitMaze (&M ,a ,row , col )初始条件：二维数组arow+2col+2已经存在，其中自第一行至第row+1行、每行中自第1列至第col+1列的元素已经有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，并在迷宫四周加上一圈障碍。 MazePath (&M)初始条件：迷宫M已被赋值。操作结果：若迷宫M中存在一条通路，则按照所走的步骤，从小到大依次排列。 PrintMaze (M)初始条件：迷宫M已存在。操作结果：已字符形式输出迷宫。ADT maze;3.2.3寻找公共路径的实验过程设定当前为出始值的入

6、口：Do   若当前位置可通，   则将当前位置插入栈顶；      若该位置是出口位置，则结束；      否则切换当前位置的东邻方块为新的当前位置；        否则     若栈不空且栈顶位置尚有其他方向未被探索，  则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置 的下一邻块；     

7、 若栈不为空且栈顶位置的四周均不可通，      则删除栈顶位置；      若栈不为空，则重新测试新的栈顶位置，      直至找到一个可通的相邻块或出栈至栈空；              4.详细设计4.1迷宫模块以二维动态数组*mazemn表示迷宫，数组中元素值为0表示通路，1表示障碍。(1)坐标位置类型:str

8、uct Maze /定义描述迷宫中当前位置的结构类型int x; /当前位置的行坐标int y; /当前位置的列坐标int dir; /0:无路径或已到达出口,1:下,2:右,3:上,4:左; (2)创建迷宫CreatMaze:int* CreatMaze(int &m, int &n); (3)输出命宫路径PrintPath:void PrintPath(Stack p); (4)恢复迷宫Restore:void Restore(int *maze, int m, int n); (5)寻找迷宫maze中从（0，0）到（m,n）的路径Mazepath:bool Mazepat

9、h(int *maze, int m, int n);4.2栈模块(1)栈类型Stack:class Stackprivate:LinkNode *top; /指向第一个结点的栈顶指针public:Stack(); /构造函数，置空栈Stack(); /析构函数void Push(Maze e); /把元素e压入栈中Maze Pop(); /使栈顶元素出栈Maze GetTop(); /取出栈顶元素void Clear(); /把栈清空bool empty(); /判断栈是否为空; (2)构造一个空栈Stack:Stack:Stack()top=NULL;(3)删除栈Stack:Stack:S

10、tack() (4)进栈操作Push:void Stack:Push(Maze e) LinkNode *P;P=new LinkNode;P->data=e;P->next=top;top=P;(5)出栈操作Pop:Maze Stack:Pop() Maze Temp;LinkNode *P;P=top;top=top->next;Temp=P->data;delete P;return Temp;(6)取栈顶元素GetTop:Maze Stack:GetTop()return top->data;(7)清空栈Clear:void Stack:Clear() t

11、op=NULL;(8)判断是否为空栈empty:bool Stack:empty() if(top=NULL) return 1;else return 0;4.3主程序模块程序如下:int main()int m = 0, n = 0;int *maze;maze = CreatMaze(m, n);if (Mazepath(maze, m, n)cout << "迷宫路径探索成功!n"else cout << "路径不存在!n"system("pause");return 0;4.4函数调用关系的层次结构框

12、图主程序PushStackCreatMazeInitializationReadCommandInterpretMazePathPopemptyGetTopPrintPathRestore4.5测试用例设计 1 2 3 4 5 6 7 80010001000100010000011010111001000010000010001010111100111000101110000005.运行结果及分析 5.1运行结果 5.2问题的模型化描述以及求解算法的简要描述（1）计算机解迷宫问题通常使用的是“穷举求解”的方法，即从设定的迷宫入口出发，然后顺着某一个方向进行探索，如若能走通，则继续往前行进；否则

13、沿着原路退回，换一个方向继续探索路径，直至找到出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路，路径探索失败。（2）可以以二维数组形式存储迷宫数据，通常设定入口的下标为（1，1），出口的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可设定有东、南、西、北四个方向可通；以行坐标、列坐标、数字化方向和方向四个字符的组合输出迷宫路径。5.3对于设计和编码的讨论与分析（1）刚着手解决这个迷宫问题的时候，首先要解决的就是如何实现迷宫问题求解。我们可以用“穷举求解”的方法来寻找迷宫的解。于是，又有问题了，该如何穷举？该怎么穷举才不

14、会出错？根据指导书上的需求，可以分为四个方向挨个探索。至于，如何储存并实现这个迷宫，就得依赖于栈和二维数组的相关知识了。（2）在具体编码时，也会遇到很多问题，譬如网络上的一些代码的运行会出现错误，需要自己动手动脑亲自调试。这样有助于对数据结构相关知识的理解，同时也达到了这门课程设计的实验目的，那就是通过自己动手动脑体会算法与数据结构的相关思想，并将所学知识运用到实际的编程过程中，达到学以致用的目的。2.2题目二：建立二叉树，层序、先序遍历；1.问题描述建立二叉树，层序、先序遍历要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列

15、的函数、输出先序遍历序列的函数。2.需求分析2.1主功能模块根据提示信息,用户可以方便地通过本程序来完成建立、遍历二叉树等操作。界面设计合理、美观、人性化, 程序智能, 安全性高。2.2创建树模块当进入程序运行界面后,根据提示输入需要建立的二叉树,按照先序次序输入各个结点的值, 完成二叉树的建立。2.3遍历树模块实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作,并输出各遍历序列。3.概要设计3.1主界面设计思想流程图3.2创建二叉树3.2.1二叉树创建的思想(1)定义二叉树结点值的类型为字符型。(2)设定结

16、点个数不超过10个。(3)按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。相关函数如下: void CreateBiTree(BiTree &T)3.2.2二叉树创建的算法流程图开始创建二叉树结束3.3先序递归遍历3.3.1先序递归遍历思想若二叉树为空，则空操作，否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树. 相关函数如下: void PreOrderTraverse(BiTree T)3.3.2先序递归遍历的算法流程图开始判结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历右子树YN3.4中序递归遍历3.4.1中序递归遍历思想若二叉树为空

17、，则空操作，否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树. 相关函数如下: void InOrderTraverse(BiTree T)3.4.2中序递归遍历的算法流程图开始判结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN3.5后序递归遍历3.5.1后序递归遍历思想若二叉树为空，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点. 相关函数如下: void PostOrderTraverse(BiTree T)3.5.2后序递归遍历的算法流程图开始判结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点

18、YN3.6先序非递归遍历3.6.1先序非递归遍历思想(1)访问结点的数据域；(2)指针指向p的左孩子结点；(3)从栈中弹出栈顶元素；(4)指针指向p的右孩子结点. 相关函数如下: void NRPreOrder(BiTree bt)3.6.2先序非递归遍历的算法流程图开始申请一个STL栈stack<*> s判结点是否空输出结点值p->datas.push(p)结点的值变为它的左孩子判断结点是否空p=s.pop()p=p->rchild结束判断栈或结点是否空NYNYN3.7中序非递归遍历3.7.1中序非递归遍历思想(1)指针指向p的左孩子结点；(2)从栈中弹出栈顶元素；(

19、3)访问结点的数据域；(4)指针指向p的右孩子结点. 相关函数如下: void NRInOrder(BiTree bt)3.7.2中序非递归遍历的算法流程图开始申请一个STL栈stack<*> s判结点是否空s.push(p)结点的值变为它的左孩子判断结点是否空输出结点值p->datap=s.pop()p=p->rchild结束判断栈或结点是否空NYYNN3.8后序非递归遍历3.8.1后序非递归遍历思想若二叉树为空，则空操作；否则引入栈和标记模拟递归工作栈, 初始时栈为空，相关函数如下: void NRPostOrder(BiTree bt);3.8.2后序非递归遍历的

20、算法流程图开始申请一个STL栈stack<*> s;用一个bool变量flag标记是否访问flag=0 s.push(p)p=p->lchild top+判断标志flag是否为1输出结点的数据p->datap = s.pop()p= p->rchild结束NYYNNYYN判断结点是否空判栈或结点是否空判断结点是否空3.9层序非递归遍历3.9.1层序非递归遍历思想(1)访问该元素所指结点。(2)若该元素所指结点的左右孩子结点非空, 则该元素所指结点的左孩子指针和右孩子指针顺序入队。相关函数如下: void LevelOrderTraverse(BiTree T)3.

21、9.2层序非递归遍历的算法流程图开始申请一个STL队列queue<*> q结束N判结点是否空Y判左结点是否空q.push(p->rchild)q.push(p->lchild)判右结点是否空q.push(root);判队列是否为空p=q.front()；输出结点值p->data; q.pop()YYNNYN4.详细设计 4.1主模块本模块定义了系统运行主界面的相关内容和相关操作函数, 源代码如下: void main()BiTree T;T = NULL;int select;/cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时

22、可连续输入):"<<endl;/ CreateBiTree(T);while (1)cout << "*遍历二叉树*n"cout << "*n"cout << "1.创建二叉树 n"cout << "2.二叉树的递归遍历算法（前、中、后） n"cout << "3.二叉树的层次遍历算法 n"cout << "4.二叉树的非递归遍历算法（前、中、后） n"cout << &

23、quot;0.退出 n"cout << "*n"cin >> select;switch (select)case 0:return;case 1:cout << "请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):" << endl;CreateBiTree(T);break;case 2:if (!T) cout << "未建立树，请先建树！"elsecout << "n先序遍历:n"PreOrderTraverse

24、(T);cout << "n中序遍历:n"InOrderTraverse(T);cout << "n后序遍历:n"PostOrderTraverse(T);break;case 3:cout << "n层序遍历:n"LevelOrderTraverse(T);break;case 4:if (!T) cout << "未建立树，请先建树！"elsecout << "n先序遍历:n"NRPreOrder(T);cout <<

25、"n中序遍历:n"NRInOrder(T);cout << "n后序遍历:n"NRPostOrder(T);break;default:cout << "请确认选择项:n"/end switch/end while 4.2创建树模块源代码如下: void CreateBiTree(BiTree &T)/按先序次序输入, 构造二叉链表表示的二叉树T, 空格表示空树/ if(T) return;char ch;ch = getchar(); /不能用cin来输入, 在cin中不能识别空格. if (ch =

26、 ' ') T = NULL;elseif (!(T = (BTNode *)malloc(sizeof(BTNode) cout << "malloc fail!"T->data = ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); 4.3遍历树模块本模块包括了各种遍历二叉树的函数，源代码如下: void PreOrderTraverse(BiTree T) /二叉树的先序遍历(递归)成员函数声明void InOrderTraverse(BiTree T) /二叉树的中序遍

27、历(递归)成员函数声明void PostOrderTraverse(BiTree T) /二叉树的后序遍历(递归)成员函数声明void LevelOrderTraverse(BiTree T) / 二叉树的层序遍历(非递归)成员函数声明void NRPreOrder(BiTree bt) / 二叉树的先序遍历(非递归)成员函数声明void NRInOrder(BiTree bt) /二叉树的中序遍历(非递归)成员函数声明void NRPostOrder(BiTree bt) /二叉树的后序遍历(非递归)成员函数声明5.运行结果及分析5.1运行结果ABCDEFHG随机建立一棵树。由数据结构的知识

28、，按照先序次序输入各个节点的值为: ABD#CEG#F#H#(此处#代表空格)。在程序中输入这些节点，创建树，如下图: 输入1：创建二叉树，输出结果如下：输入2：输出该二叉树的递归遍历算法的遍历结果, 输出结果如下:输入3：输出该二叉树的层序遍历算法的遍历结果, 输出结果如下: 输入4：输出该二叉树的非递归遍历算法的遍历结果, 输出结果如下: 5.2算法分析5.2.1时间复杂度其实无论是先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历还是层序遍历，其基本操作都是访问二叉树结点。因此对于拥有n个结点的二叉树，其时间复杂度均为O(n)。5.2.2空间复杂度对

29、于采用递归的方法遍历二叉树, 即先序递归遍历、中序递归遍历以及后序递归遍历，并不需要对其辅助空间就能实现对二叉树的遍历, 则空间复杂度为O(1)。对于采用非递归的方法遍历二叉树, 即先序非递归遍历、中序非递归遍历以及后序非递归遍历, 所需辅助空间为遍历过程中栈的最大容量, 即树的深度, 一般情况下为 ，则空间复杂度为0（ ），最坏情况下为n, 则空间复杂度也为O(n)。2.3题目三：文章编辑1.问题描述输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行。2.需求分析（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在

30、文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"；（3）输出删除某一字符串后的文章。3.概要设计3.1定义结构体 struct line，文本行采用顺序存储，行与行之间采用链式存储。3.2主要函数int FindString(LINE * &he

31、ad,char *str) /*统计str在文章中出现的次数*/求在一行中Str出现的次数的流程图：开始count=0;h=0;len1=0; len2=strlen(str);p->datai=str0i+k=0;j=0;p->datai+j=strjk+;j+;k=len2count+;i=i+k-1;结束YNYNNY .查找第一个字符，如果有第一个字符即p->datai=str0，设计数器k=0； 查找这个字符后面的字符与要查找的字符串是否匹配即 p->datai+j=strj，如果匹配则k+； 重复第二步，如果k=len2，则查找到count+；如果没查找到，重

32、新进行第一步void delstringword(char *s,char *str) /*删除字符串*s中的字符串*str*/ strpi jsfor(m=0;m<i;m+)tmpcount+=sm;for(n=j;n<len;n+)tmpcount+=sn;tmp实现思想： 从字符串s中寻找str第一次出现的位置 *p=strstr(s,str);len=strlen(s);i=len-strlen(p)即前i项恰好不含要删除的 字符串，将前i项复制到tmp中； .j=i+strlen(str) 即要删除的字符串在i+1和j之间，将j之后的字符串复制到tmp中；将tmp赋给串s

33、，返回s4.详细设计 设计思想 （1）定义结构体：typedef struct line char *data; struct line *next;LINE;（2）输出函数void OutPut(LINE * &head) 将头指针赋值为p；通过do-while语句遍历链表；（3）字符串的创建函数： void Create(LINE * &head) 用printf语句输出一句提醒语句，请用户输入要编辑的文章 为链表建立一个附加表头结点，将p付给表头指针； 输入字符串，同时判断输入的字符串是否满足条件； 用if语句判断文章是否输入完成。 （4）统计文章中英文字母数：void

34、countLetter(LINE * &head) 将p付给表头指针； 初始化count为0； 用do-while语句遍历链表，同时统计字符串中英文字母数 用printf语句输出文章中英文字母数，调用子函数menu()。（5）统计文章中数字个数：void countNumber(LINE* &head) 将p付给表头指针； 初始化count为0； 用do-while语句遍历链表，同时统计字符串中数字个数； 用printf语句输出文章中数字个数，调用子函数menu()。（6）统计文章中的空格数：void countSpace(LINE * &head) 将p付给表头指针；

35、 初始化count为0； 用do-while语句遍历链表，同时统计字符串中空格数； 用printf语句输出文章中空格数，调用子函数menu()。（7）统计文章总字数：void countAll(LINE * &head)将p付给表头指针； 初始化count为0； 用do-while语句遍历链表，同时统计字符串中总字数； 用printf语句输出文章中总字数，调用子函数menu()。（8）查找字符串的函数：void FindString(LINE * &head)将p付给表头指针；初始化count为0；初始化len1,用来保存当前行的总字符数；定义整型变量len2表示待统计字符串的

36、长度；用printf语句提醒用户输入要统计的字符串；用do-while语句遍历链表，同时用for循环和if语句找出指定字符串在文章中出现的次数；用printf语句输出指定字符串在文章中出现的总次数，调用子函数menu()。（9）删除字符串的函数：void DelString(LINE * &head) 先创建一个delstringword，其中包含两个字符串char *s和char *str，用*s表示输入的字符串，*str表示要删除的字符。这个函数的功能是找到字符串s在字符串中出现的位置并删除该字符串。 定义字符串的删除函数DelString(),用do-while语句遍历链表，语句

37、中再套用if语句，并调用delstringword()进行删除。（10）主函数:void main() 用switch语句实现功能的调用。一个数字对应一个操作。5.运行结果及分析5.1运行结果输入一段文章后以Ctrl+E作为结尾表示文章输入结束然后分别输入1、2、3、4、5、6、7进行测试，结果如下：5.2输入问题解决优化Q：在输入文章时，往往要输入多行文字，那么计算机怎样识别文章是否结束输入？输出文章时，又怎样处理表示结束的字符？A：输入文章时，以Ctrl+E(E)表示结尾，当tmp0=5时，发现输入E，则结束输入。输出时文章时，tmpstrlen(tmp)-1=5即发现表示结束的字符E，用

38、代码p->datastrlen(tmp)-1='0'除去最后一个控制符 “E”即可解决问题。三、 课程设计总结数据结构课程设计的主要目的是学习并实践运用一些常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构的知识，讨论对他们实行的各种运算的实现算法。连续两周的数据结构课程设计使我对数据结构与算法方面的知识有了更加深入的了解，也使我认识到自己在算法学习以及编程习惯上面还有很多的不足之处。今后我应当多读一些数据结构算法与编程思想方面的书籍，注重理论与实践的结合，多进行上机练习编写程序，提高自己的实际动手能力和独立思考的能力，不断充实自

39、己，更好地掌握编程思想，培养自己运用数据结构和算法的相关思想解决问题的能力。同时，此次课程设计也使我对编程产生了兴趣，特别是在通过查书籍资料以及网上资源的情况下能够使程序运行成功，让人十分地有成就感，参考网上的代码并结合理论课知识读懂程序代码的设计思想及其设计理念，也让我获益颇多。最后，通过这次实践，我们也应该认识到自己所学到的东西实在太浅太简单太基础，我们以后应当认真地学习专业知识，打好基础，为自己的未来铺路，因为成功是百分之九十九的汗水加上百分之一的灵感。景德镇陶瓷学院数据结构课程设计源程序院系：信息工程学院专业：计算机科学与技术班级：计科2班学号：201310510112姓名：张旸使用语

40、言：C语言、C+编译环境：Windows7、Microsoft Visual Studio 2013、VC+ 6.0源代码一：迷宫问题#include<iostream>using namespace std;struct Maze /定义描述迷宫中当前位置的结构类型int x; /当前位置的行坐标int y; /当前位置的列坐标int dir; /0:无路径或已到达出口,1:下,2:右,3:上,4:左;class LinkNode /链表结点friend class Stack;public:Maze data;LinkNode *next;class Stackprivate:

41、LinkNode *top; /指向第一个结点的栈顶指针public:Stack(); /构造函数，置空栈Stack(); /析构函数void Push(Maze e); /把元素e压入栈中Maze Pop(); /使栈顶元素出栈Maze GetTop(); /取出栈顶元素void Clear(); /把栈清空bool empty(); /判断栈是否为空;Stack:Stack()top = NULL;Stack:Stack()void Stack:Push(Maze e)LinkNode *P;P = new LinkNode;P->data = e;P->next = top;

42、top = P;Maze Stack:Pop()Maze Temp;LinkNode *P;P = top;top = top->next;Temp = P->data;delete P;return Temp;Maze Stack:GetTop()return top->data;void Stack:Clear()top = NULL;bool Stack:empty()if (top = NULL) return 1;else return 0;bool Mazepath(int *maze, int m, int n); /寻找迷宫maze中从（0，0）到（m,n）的

43、路径void PrintPath(Stack p); /输出迷宫的路径void Restore(int *maze, int m, int n); /恢复迷宫int* CreatMaze(int &m, int &n); /获取迷宫int* CreatMaze(int &m, int &n)/返回存取迷宫的二维指针int *maze; /定义二维指针存取迷宫int i = 0, j = 0;int a, b;cout << "请输入迷宫的规模（行 列）:"cin >> a >> b;cout <<

44、; "请输入迷宫内容（以0表示通路，1表示障碍）:n"m = a;n = b; /m,n分别代表迷宫的行数和列数maze = new int *m + 2;for (i = 0; i<m + 2; i+)mazei = new intn + 2;for (i = 1; i <= m; i+) /输入迷宫的内容，0代表可通，1代表不通for (j = 1; j <= n; j+)cin >> mazeij;for (i = 0; i<m + 2; i+)mazei0 = mazein + 1 = 1;for (i = 0; i<n +

45、 2; i+)maze0i = mazem + 1i = 1;return maze;bool Mazepath(int *maze, int m, int n)/寻找迷宫maze中从（0，0）到（m,n）的路径Stack q, p; /栈p、q分别存探索迷宫的过程和存储路径Maze Temp1, Temp2;int x, y, loop;int move42 = 0, 1 , 1, 0 , 0, -1 , -1, 0 ; /当前位置移动的4个方向Temp1.x = 1;Temp1.y = 1;q.Push(Temp1); /入口位置进栈p.Push(Temp1);maze11 = -1; /

46、标志入口位置已到达过while (!q.empty() /栈q非空，则反复探索Temp2 = q.GetTop();if (!(p.GetTop().x = q.GetTop().x&&p.GetTop().y = q.GetTop().y)p.Push(Temp2);/如果有新位置入栈，则把上一个探索的位置存入栈pfor (loop = 0; loop<4; loop+) /探索当前位置的4个相邻位置x = Temp2.x + moveloop0; /计算出新位置x位置值y = Temp2.y + moveloop1; /计算出新位置y位置值if (mazexy = 0

47、) /判断新位置是否可达Temp1.x = x;Temp1.y = y;mazexy = -1; /标志新位置已到达过q.Push(Temp1); /新位置入栈if (x = (m) && (y = (n) /成功到达出口Temp1.x = m;Temp1.y = n;Temp1.dir = 0;p.Push(Temp1); /把最后一个位置入栈PrintPath(p); /输出路径Restore(maze, m, n); /恢复路径return 1;if (p.GetTop().x = q.GetTop().x&&p.GetTop().y = q.GetTop

48、().y)/如果没有新位置入栈，则返回到上一个位置p.Pop();q.Pop();return 0; /查找失败，迷宫无路经void PrintPath(Stack p) /输出路径cout << "迷宫的路径为n"cout << "括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)n"Stack t; /用于按从入口到出口存取路径int a, b;Maze data;LinkNode *temp;temp = new LinkNode;temp->data = p.Pop(); /取栈p的顶点元素，即第一个位置t.

49、Push(temp->data); /第一个位置入栈tdelete temp;while (!p.empty() /栈p非空，则反复转移temp = new LinkNode;temp->data = p.Pop(); /获取下一个位置/得到行走方向a = t.GetTop().x - temp->data.x;b = t.GetTop().y - temp->data.y;if (a = 1) temp->data.dir = 1; /方向向下else if (b = 1) temp->data.dir = 2; /方向向右else if (a = -1)

50、 temp->data.dir = 3; /方向向上else if (b = -1) temp->data.dir = 4; /方向向左t.Push(temp->data); /新位置入栈delete temp;/输出路径，包括行坐标，列坐标，下一个位置方向while (!t.empty() /栈非空，继续输出data = t.Pop();cout << '(' << data.x << ',' << data.y << ',' << data.dir &l

51、t;< ","switch (data.dir)case 1:cout << ")n" break;case 2:cout << ")n" break;case 3:cout << ")n" break;case 4:cout << ")n" break;case 0:cout << "出口)n" break;void Restore(int *maze, int m, int n) /恢复探索过的迷宫int

52、i, j;for (i = 0; i<m + 2; i+) /遍历指针for (j = 0; j<n + 2; j+)if (mazeij = -1) /恢复探索过位置mazeij = 0;int main()int m = 0, n = 0;int *maze;maze = CreatMaze(m, n);if (Mazepath(maze, m, n)cout << "迷宫路径探索成功!n"else cout << "路径不存在!n"system("pause");return 0;源代码二：建立二叉树，层序、先序遍历#include