下载文档原格式
算法导论答案算法导论概述《算法导论》是一本经典的计算机科学教材，由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein合著。
这本书详细介绍了算法的设计、分析和实现，并涵盖了算法导论领域的许多重要概念和技术。
本文将为你提供一些关于《算法导论》中一些常见问题的答案。
1. 什么是算法？算法是一系列明确定义的步骤，用于解决特定问题或完成特定任务。
它可以是一个计算过程、一个程序或一个有限的操作序列。
算法通常用于计算和数据处理领域，是计算机科学的核心概念。
2. 为什么学习算法很重要？学习算法的重要性体现在以下几个方面：•提高问题解决能力：算法是解决问题的有效工具。
学习算法可以帮助我们思考和理解问题，并设计出相应的解决方案。
•优化计算性能：算法的设计和分析可以帮助我们提高计算的效率和性能。
合适的算法可以在短时间内处理大规模数据集和复杂计算任务。
•促进技术创新：算法是许多技术和应用的基石，包括人工智能、机器学习、数据挖掘等。
学习算法可以为我们打开更多的研究和创新机会。
3. 《算法导论》提供了哪些内容？《算法导论》这本书详细介绍了算法的基本概念和设计技巧，并提供了许多典型算法的实现和分析。
以下是该书的一些主要内容：•算法分析：对算法进行时间复杂度和空间复杂度的理论分析，帮助我们评估算法的效率和性能。
•排序和查找算法：介绍了各种排序算法（如插入排序、归并排序、快速排序）和查找算法（如二分查找、哈希表）。
•图算法：讨论了图的表示方法和图搜索算法（如深度优先搜索、广度优先搜索）以及最短路径算法（如Dijkstra算法）等。
•动态规划和贪心算法：介绍了动态规划和贪心算法的原理和应用，用于解决具有最优子结构性质的问题。
•分治算法和递归思想：讲解了分治算法的基本原理，并提供了许多使用递归思想解决问题的例子。
•NP完全问题：探讨了NP完全问题的性质和求解方法，引导了读者进入计算复杂性理论的领域。
第二次实验报告红黑树1.红黑树1.1 需求分析本实验要求实现红黑树各种操作如SEARCH ，PREDECESOR ，SUCCESSOR ，MINIMUM，MAXIMUM，INSERT，DELETE 等。
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是在1972 年由Rudolf Bayer 发明的，他称之为"对称二叉B 树"，它现代的名字是在Leo J. Guibas 和Robert Sedgewick 于1978 年写的一篇论文中获得的。
它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。
在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:1. 每个结点或红或黑。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL 指针)都是黑色的。
4. 如果一个结点是红色的,那么它的周边3 个节点都是黑色的。
5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
结果是这个树大致上是平衡的。
因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些特性确保了这个结果，注意到属性5 导致了路径不能有两个毗连的红色节点就足够了。
最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。
因为根据属性4 所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。
快速排序实验报告SA14225010一、题目当输入数据已经“几乎”有序时，插入排序速度很快。
在实际应用中，我们可以利用这一特点来提高快速排序的速度。
当对一个长度小于k的子数组调用快速排序时，让它不做任何排序就返回。
当上层的快速排序调用返回后，对整个数组运行插入排序来完成排序过程。
试证明：这一排序算法的期望时间复杂度为O （nk+nlg（n/k））。
分别从理论和实践的角度说明我们应该如何选择k？二、算法思想当输入数据已经“几乎”有序时，插入排序速度很快。
当对一个长度小于k的子数组调用快速排序时，让它不做任何排序就返回。
当上层的快速排序调用返回后，对整个数组运行插入排序来完成排序过程。
累加k的值，计算出当k为不同值时算法运行的时间，来算出当k大约为什么值时运行的时间最短，并与传统的快速排序算法的运行时间进行比较。
三、实验结果输入100个不同的整数值，选取不同的k的值，观察所用时间四、实验分析理论上看，k的值选取为20到25较好；但是，从实际上来看，当k为50左右时间为39毫秒，最少，但不同的时刻运行后的时间都不相同，而且不同的输入时刻的运行时间也不相同，当数据较大时候，对k 的值的选取有会有所不同，同时不同性能的机器对测试结果也不同，所以对于k值的选取没有固定的数值。
#include<iostream>#include<sys/timeb.h>using namespace std;#define M 40void swap(int * a,int * b){int tem;tem=*a;*a=*b;*b=tem;}int partition(int v[],const int low,const int high){int i,pivotpos,pivot;pivotpos=low;pivot=v[low];for(i=low+1;i<=high;++i){if(v[i]<pivot){pivotpos++;if(pivotpos!=i)swap(v[i],v[pivotpos]);}}v[low]=v[pivotpos];v[pivotpos]=pivot;//cout<<"the partition function is called\n";return pivotpos;}/*void QuickSort(int a[], const int low,const int high) {int item;if(low<high){item=partition(a,low,high);QuickSort(a,low,item-1);QuickSort(a,item+1,high);}}*/void QuickSort(int a[], const int low,const int high) {int item;if(high-low<=M)return;if(low<high){item=partition(a,low,high);QuickSort(a,low,item-1);QuickSort(a,item+1,high);}// cout<<"the QuickSort is called"<<endl;}void InsertSort(int a[],const int low,const int high){int i,j;int tem;for(i=1;i<high+1;++i){tem=a[i];j=i-1;while(j>=0&&tem<a[j]){a[j+1]=a[j];j--;}a[j+1]=tem;}//cout<<"the InsertSort is called"<<endl;}void HybridSort(int a[],const int low,const int high){QuickSort(a,low,high);InsertSort(a,low,high);cout<<"the HybidSort is called"<<endl;}int main(){int i,a[100];//int *a=NULL;long int t;struct timeb t1,t2;/*cout<<"please input the number of the element:"<<endl;cin>>n;a = (int*)malloc(n*sizeof(int));cout<<"please input every element:"<<endl;*/for( i=0; i<100; i++){a[i]=i+10;}//QuickSort(a,0,n-1);ftime(&t1);HybridSort(a,0,99);cout<<" after sorted quickly,the result is"<<endl;for(i=0; i<100; i++){cout<<a[i]<<" ";if(i%10==0)cout<<endl;}cout<<endl;ftime(&t2);t=(t2.time-t1.time)*1000+(litm); /* 计算时间差 */ printf("k=%d 用时%ld毫秒\n",M,t);//cout<<"the memory of array a is free"<<endl;//free(a);cout<<"\n"<<endl;return 0;}。
Chapter2 Getting Start2.1 Insertion sort2.1.2 将Insertion-Sort 重写为按非递减顺序排序2.1.3 计算两个n 位的二进制数组之和2.2 Analyzing algorithms2.2.1将函数32/10001001003n n n --+用符号Θ表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n 个元素已经是最大的元素了.最好时间和最坏时间均为2()n Θ2.3 Designing algorithms2.3.3 计算递归方程的解22()2(/2)2,1k if n T n T n n if n for k =⎧=⎨+ = >⎩ （1） 当1k =时，2n =，显然有()lg T n n n =（2） 假设当k i =时公式成立，即()lg 2lg 22i i i T n n n i ===⋅，则当1k i =+，即12i n +=时，111111()(2)2(2)222(1)22lg(2)lg i i i i i i i i T n T T i i n n ++++++==+=⋅+=+== ()lg T n n n ∴ =2.3.4 给出insertion sort 的递归版本的递归式(1)1()(1)()1if n T n T n n if n Θ =⎧=⎨-+Θ >⎩2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描，是否可以将算法的时间提高到(lg )n n Θ？虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2()n Θ2.3-7 给出一个算法，使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间(lg )n n Θ，然后再进行查找：Search(A,n,x)QuickSort(A,n);i←1; j←n ;while A[i]+A[j]≠x and i<jif A[i]+A[j]<xi←i+1elsej←j -1if A[i]+A[j]=xreturn trueelsereturn false时间复杂度为)(n Θ。
算法导论上机实验报告册班级：xxxxxx学号：xxxxxxx 姓名：xxxx 教师：xxxxxx目录实验一排序算法 (1)题目一： (1)1、题目描述： (1)2、所用算法： (1)3、算法分析： (1)4、结果截图： (1)5、总结： (2)题目二： (3)1、题目描述： (3)2、所用算法： (3)3、算法分析： (3)4、结果截图： (3)5、总结： (4)题目三： (4)1、题目描述： (4)2、所用算法： (4)3、算法分析： (5)4、结果截图： (5)5、总结： (5)题目四： (6)1、题目描述： (6)3、算法分析： (6)4、结果截图： (6)5、总结： (7)实验二动态规划 (7)题目一： (7)1、题目描述： (7)2、所用策略： (7)3、算法分析： (7)4、结果截图： (8)5、总结： (8)题目二： (9)1、题目描述： (9)2、所用策略： (9)3、算法分析： (9)4、结果截图： (9)5、总结： (10)题目三： (10)1、题目描述： (10)2、所用策略： (10)3、算法分析： (10)4、结果截图： (11)题目四： (12)1、题目描述： (12)2、所用策略： (12)3、算法分析: (12)4、结果截图： (12)5、总结： (13)题目五： (13)1、题目描述： (13)2、所用策略： (13)3、算法分析： (13)4、结果截图： (14)5、总结： (14)实验三贪心算法 (14)题目一： (14)1、题目描述： (14)2、所用策略： (14)3、算法分析： (14)4、结果截图： (15)5、总结： (16)题目二： (16)1、题目描述： (16)3、算法分析： (16)4、结果截图： (17)5、总结： (17)题目三： (17)1、题目描述: (17)2、所用算法： (18)3、算法分析： (18)4、结果截图： (18)5、总结： (19)题目四： (19)1、题目描述： (19)2、所用算法： (19)3、算法分析： (19)实验四回溯法 (19)题目一： (19)1、题目描述： (20)2、所用策略： (20)3、算法分析： (20)题目二： (21)1、题目描述： (21)2、所用策略： (21)实验一排序算法题目一：1、题目描述：描述一个运行时间为θ(nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。
算法导论参考答案算法导论参考答案算法导论是计算机科学领域中一本经典的教材，被广泛应用于计算机科学和工程的教学和研究中。
它涵盖了算法设计和分析的基本概念，以及各种常见算法的实现和应用。
本文将为读者提供一些算法导论中常见问题的参考答案，以帮助读者更好地理解和掌握这门课程。
1. 什么是算法？算法是一系列解决问题的步骤和规则。
它描述了如何将输入转换为输出，并在有限的时间内完成。
算法应具备正确性、可读性、健壮性和高效性等特点。
2. 如何分析算法的效率？算法的效率可以通过时间复杂度和空间复杂度来衡量。
时间复杂度表示算法执行所需的时间量级，常用的时间复杂度有O(1)、O(n)、O(logn)、O(nlogn)和O(n^2)等。
空间复杂度表示算法执行所需的额外空间量级，通常以字节为单位。
3. 什么是渐进符号？渐进符号用于表示算法的时间复杂度或空间复杂度的增长趋势。
常见的渐进符号有大O符号、Ω符号和Θ符号。
大O符号表示算法的上界，Ω符号表示算法的下界，Θ符号表示算法的平均情况。
4. 什么是分治法？分治法是一种算法设计策略，将问题分解为若干个子问题，并对子问题进行独立求解，最后将子问题的解合并得到原问题的解。
典型的分治算法有归并排序和快速排序。
5. 什么是动态规划？动态规划是一种通过将问题分解为相互重叠的子问题来求解的方法。
它通常用于求解具有重叠子问题和最优子结构性质的问题。
典型的动态规划算法有背包问题和最短路径问题。
6. 什么是贪心算法？贪心算法是一种通过每一步选择局部最优解来求解整体最优解的方法。
贪心算法通常不能保证得到全局最优解，但在某些问题上能够得到近似最优解。
典型的贪心算法有霍夫曼编码和最小生成树算法。
7. 什么是图算法？图算法是一类用于解决图结构相关问题的算法。
图由节点和边组成，节点表示对象，边表示对象之间的关系。
图算法包括图的遍历、最短路径、最小生成树和网络流等问题的求解。
8. 什么是NP完全问题？NP完全问题是一类在多项式时间内无法求解的问题。
第五次实验报告——最长公共子序列的生成算法1.1算法应用背景最长公共子序列是一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。
而最长公共子串(要求连续)和最长公共子序列是不同的。
最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。
对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。
简而言之，百度知道、百度百科都用得上。
1.2算法原理若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
例：∑= {x, y, z} ，A = x y z y x z x zx x x 是长度为3 的子序列x z y z x 是长度为5 的子序列例：A = x y z y x z x z，B = x z y x x y z xx x x是长度为3 的公共子序列x z y z 是长度为4 的公共子序列x z y x x z 是长度为6 的最长公共子序列1.3算法描述记L n,m为序列A n和B m的最长公共子序列长度，则L i,j为序列A i和Bj的最长公共子序列的长度。
根据最长公共子序列的性质，则得到：阶段的划分和最长公共子序列长度的获取第一阶段：计算A1和Bj的最长公共子序列的长度L1,j ,j=1,2,…m第二阶段：计算A2和B j的最长公共子序列的长度L2,j, j=1,2,…m第n 阶段：计算A n和B j的最长公共子序列的长度L n,j, j=1,2,…m第n 阶段的L m,n便是序列A n和B m的最长公共子序列的长度为了得到A n和B m最长公共子序列，设置一个二维的状态字数组s i，j，在上述每一个阶段计算L n,j过程中，根据公共子序列的性质则有按照如下方法把搜索状态登记于状态字s i，j中：s i，j =1 a i=b js i，j =2 a i≠b j L i-1,j>= L i,j-1s i，j =3 a i≠b j L i-1,j< L i,j-1设L n,m=k,S k=c1c2……c k是序列A n和B m的长度为k的最长公共子序列。
算法导论实验一电子信息科学与技术(2)班朱健2011329640228实验题目：使用STL库实现杨辉三角系数求解。
代码://杨辉三角#include <iostream>#include <queue>using namespace std;int main(void){int n;queue<int> q;printf("输入行数(1-10): \n");scanf("%d",&n);if (n>0 && n<11){printf("输入正确!\n");} else {printf("输入有无!\n");return 0;}if (n == 1){printf("1\n");return 0;}q.push(0);q.push(1);for (int i=0; i<n; i++){int v1;q.push(0);int temp = 0;while (temp <= (n-i)){printf("%2c",' ');temp++;}for (int j=0; j<i+2; j++){v1 = q.front();q.pop();int v2 = q.front();//取队头结点元素int sum = v1 + v2;q.push(sum);if (v1 != 0)printf("%3d ",v1);}printf("\n");}return 0;}截图:实验题目：使用STL库实现迷宫求解。
代码:/*使用STL库实现迷宫求解建立一个m*n个格子的迷宫，使用随机函数为迷宫里的每个格子赋值（1或0）可通过设置Max值控制迷宫大小1表示有障碍，无法通过0表示无障碍，可以通过9表示边界8表示路径4表示查询路径过程中曾经经过的位置选手从（0,1）进入从(10,9)出若无通路会显示“无通路”,有通路会显示路径有无通路均会显示走过的迷宫*/#include<iostream>#include<stdlib.h>#include<time.h>#include<stack>using namespace std;#define Max 8typedef struct Node{int x;//横坐标int y;//纵坐标int d;//方向(1表示下，2表示右，3表示左，4表示上)}Node;bool InitStack(stack<Node> *S)//初始化栈{bool b = false;Node temp;Node temp1;temp.x = 0;temp.y = 1;temp.d = 0;S->push(temp);temp1 = S->top();printf("初始化栈成功!\n");b = true;return b;}bool CreateMaze(int (*arr)[Max])//建立迷宫{bool b = false;srand((unsigned)time(NULL));int i, j;for (i=0; i<Max; i++){arr[i][0] = 9;arr[i][Max-1] = 9;}for (j=0; j<Max; j++){arr[0][j] = 9;arr[Max-1][j] = 9;}for (i=1; i<Max-1; i++){for (j=1; j<Max-1; j++){arr[i][j] = rand()%2;//取0或1 }}arr[1][1] = 0;arr[Max-2][Max-2] = 0;for (i=0; i<Max; i++){for (j=0; j<Max; j++){printf("%3d ",arr[i][j]);}printf("\n");}printf("\n\n\n");b = true;return b;}void StackEmpty(stack<Node> S){int size;size = S.size();if (size <= 0){printf("栈为空！\n");exit(0);}}bool Validate_1(int (*arr)[Max], stack<Node> S)//验证当方向为下时的位置{int i, j;int size;bool b = false;Node temp;Node temp1;size = S.size();StackEmpty(S);//判断栈是否为空if (size > 1){temp = S.top();S.pop();temp1 = S.top();S.push(temp);if (temp1.d == 4){return b;}} else {temp = S.top();}i = temp.x;j = temp.y;i = i+1;//原位置向下一个位置if ((i==0) || (i==Max-1) || (j==0) || (j==Max-1)){return b;} else if (arr[i][j] == 0){b = true;}return b;}bool Validate_2(int (*arr)[Max], stack<Node> S)//验证当方向为右时的位置{int i, j;int size;bool b = false;Node temp;Node temp1;size = S.size();StackEmpty(S);//判断栈是否为空if (size > 1){temp = S.top();S.pop();temp1 = S.top();S.push(temp);if (temp1.d == 3){return b;}} else {temp = S.top();}i = temp.x;j = temp.y;j = j+1;//原位置向下一个位置if ((i==0) || (i==Max-1) || (j==0) || (j==Max-1)){return b;} else if (arr[i][j] == 0){b = true;}return b;}bool Validate_3(int (*arr)[Max], stack<Node> S)//验证当方向为左时的位置{int i, j;int size;bool b = false;Node temp;Node temp1;size = S.size();StackEmpty(S);//判断栈是否为空if (size > 1){temp = S.top();S.pop();temp1 = S.top();S.push(temp);if (temp1.d == 2){return b;}} else {temp = S.top();}i = temp.x;j = temp.y;j = j-1;//原位置向下一个位置if ((i==0) || (i==Max-1) || (j==0) || (j==Max-1)){return b;} else if (arr[i][j] == 0){b = true;}return b;}bool Validate_4(int (*arr)[Max], stack<Node> S)//验证当方向为上时的位置{int i, j;int size;bool b = false;Node temp;Node temp1;size = S.size();StackEmpty(S);//判断栈是否为空if (size > 1){temp = S.top();S.pop();temp1 = S.top();S.push(temp);if (temp1.d == 1){return b;}} else {temp = S.top();}i = temp.x;j = temp.y;i = i-1;//原位置向下一个位置if ((i==0) || (i==Max-1) || (j==0) || (j==Max-1)){return b;} else if (arr[i][j] == 0){b = true;}return b;}bool Validate(int dNum, int (*arr)[Max], stack<Node> S)//验证下一个位置是否为空{bool b = false;switch (dNum){case 1:b=Validate_1(arr, S);break;case 2:b=Validate_2(arr, S);break;case 3:b=Validate_3(arr, S);break;case 4:b=Validate_4(arr, S);break;default:exit(0);}return b;}bool PushStack_1(stack<Node> *S, int (*arr)[Max])//将栈顶元素位置下面的一个元素加入{int i, j;int size1, size2;bool b = false;Node pro;Node temp;size1 = S->size();pro = S->top();S->pop();pro.d = 1;S->push(pro);i = pro.x;j = pro.y;i ++;temp.x = i;temp.y = j;temp.d = 0;arr[i][j] = 8;S->push(temp);size2 = S->size();if((size2 - size1) == 1){b = true;}return b;}bool PushStack_2(stack<Node> *S, int (*arr)[Max])//将栈顶元素位置右面的一个元素加入{int i, j;int size1, size2;bool b = false;Node pro;Node temp;size1 = S->size();pro = S->top();S->pop();pro.d = 2;S->push(pro);i = pro.x;j = pro.y;j ++;temp.x = i;temp.y = j;temp.d = 0;arr[i][j] = 8;S->push(temp);size2 = S->size();if((size2 - size1) == 1){b = true;}return b;}bool PushStack_3(stack<Node> *S, int (*arr)[Max])//将栈顶元素位置左面的一个元素加入{int size1, size2;bool b = false;Node pro;Node temp;size1 = S->size();pro = S->top();S->pop();pro.d = 3;S->push(pro);i = pro.x;j = pro.y;j --;temp.x = i;temp.y = j;temp.d = 0;arr[i][j] = 8;S->push(temp);size2 = S->size();if((size2 - size1) == 1){b = true;}return b;}bool PushStack_4(stack<Node> *S, int (*arr)[Max])//将栈顶元素位置上面的一个元素加入{int i, j;int size1, size2;bool b = false;Node pro;Node temp;size1 = S->size();pro = S->top();S->pop();pro.d = 4;//加入下一个位置的方向S->push(pro);j = pro.y;i --;temp.x = i;temp.y = j;temp.d = 0;arr[i][j] = 8;S->push(temp);size2 = S->size();if((size2 - size1) == 1){b = true;}return b;}bool PushStack(int dNum, stack<Node> *S, int (*arr)[Max])//将新的位置加入栈中{bool b = false;switch (dNum){case 1:b=PushStack_1(S, arr);break;case 2:b=PushStack_2(S, arr);break;case 3:b=PushStack_3(S, arr);break;case 4:b=PushStack_4(S, arr);break;default:exit(0);}return b;}bool PopStack(stack<Node> *S, int (*arr)[Max])//回溯{bool b = false;int i, j;int size1, size2;Node temp;size1 = S->size();temp = S->top();i = temp.x;j = temp.y;arr[i][j] = 4;S->pop();size2 = S->size();if((size1 - size2) == 1){b = true;}return b;}void Disp(int (*arr)[Max], stack<Node> S) {int i;int j;int size;int size1;Node temp;stack<Node> s;s = S;size = S.size();size1 = size;while (size > 0){temp = S.top();S.pop();i = temp.x;j = temp.y;arr[i][j] = 8;size = S.size();}for(i=0; i<Max; i++){for(j=0; j<Max; j++){if (i==Max-1 && j==Max-2)printf("%3d ",8);continue;}printf("%3d ",arr[i][j]);}printf("\n");}printf("\n");if (size1 == 1)//判断是否存在通路return ;while (s.size() != 0){temp = s.top();s.pop();printf("[%d, %d]\n",temp.x, temp.y);}}int main(void){int i;int j;int d = 0;int dNum;Node temp;stack<Node> S;//用于存放路径int arr[Max][Max];bool flag = false;InitStack(&S);//初始化栈CreateMaze(arr);//建立迷宫temp = S.top();i = temp.x;j = temp.y;while ((i<Max-1 && j<Max-1) && (i!=Max-2 || j!=Max-2)) {temp = S.top();//取栈顶元素dNum = 0;//方向数字while (dNum < 4)flag = false;dNum ++;if (temp.d == dNum)//栈顶元素之前一个元素不用检查{continue;}flag = Validate(dNum, arr, S);//验证下一个位置是否为空if (flag){PushStack(dNum, &S, arr);//将新的位置加入栈中break;}}if (!flag)//如果栈底元素在地图中下、左和右均不为空，则回溯{flag = false;flag = PopStack(&S, arr);if (!flag){printf("回溯失败!\n");return 0;}}if (S.size() == 1){printf("无通路!\n");break;}temp = S.top();i = temp.x;j = temp.y;}Disp(arr, S);//显示通关迷宫return 0;}截图:。
