数据结构中八皇后问题的堆栈非递归方法的实现研究.doc

上传人:PIYPING 文档编号:10807577 上传时间:2021-06-05 格式:DOC 页数:2 大小:110.41KB
返回 下载 相关 举报
数据结构中八皇后问题的堆栈非递归方法的实现研究.doc_第1页
第1页 / 共2页
数据结构中八皇后问题的堆栈非递归方法的实现研究.doc_第2页
第2页 / 共2页
亲,该文档总共2页,全部预览完了,如果喜欢就下载吧!
资源描述

《数据结构中八皇后问题的堆栈非递归方法的实现研究.doc》由会员分享,可在线阅读,更多相关《数据结构中八皇后问题的堆栈非递归方法的实现研究.doc(2页珍藏版)》请在三一文库上搜索。

1、李志伟1,河南 郑州曹阳2,张凯2( 1、郑州科技学院信息工程学院4500642、郑州科技学院实验中心 河南 郑州 450064 )【摘 要】: 八皇后问题是一个古老而著名的问题,是回溯法的典型算法。 对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,还可以辅助教师进行教学演示,可以产生良 好的教学效果。【关键词】: 数据结构;八皇后;回溯法;堆栈;非递归1、八皇后问题概述:八皇后问题是一个古老而著名的问题,2.2 图形存取在 Turbo C 环境中,图形的存取可用如下标准函数 实现:size=imagesize (x1,y1,x2,y2) ; 返回存储区域所需字

2、 节数。arrow=malloc(size);建立指定大小的动态区域位图,并设定一指针 arrow。getimage(x1,y1,x2,y2,arrow);将指定区域位图存于一 缓冲区。putimage(x,y,arrow,copy)将位图置于屏幕上以(x,y)左上角的区域。虽然,用递归或 while 循环实现八皇后乃至 n 皇后 问题效率较高,而且思路清楚,但是为了更好的体现八 皇后问题在数据结构与算法中的应用, 为数据结构的 初学者达到融会贯通的目的; 我们不妨尝试一下加入是回溯法的典型算法 。 该问题是十九世纪著名的数学家高斯1850 年提出的, 主要目的是在一个 88 国际象棋盘 上,

3、有 8 个皇后,每个皇后占一格;要求皇后间不会出 现相互“攻击”的现象,即不能有两个皇后处在同一行、 同一列或同一对角线上。2、八皇后问题的方法实现关于八皇后问题的解法有很多种,高斯认为有 76种方案。 1854 年在柏林的象棋杂志上不同的作者发表 了 40 种不同的解, 后来有人用图论的方法解出 92 种结果。 对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,还可以辅助 教师进行教学演示,可以产生良好的教学效果。 同时也 是比较高效的方法之一,它主要解决两个问题:即回溯 算法的实现和图形存取。2.1 回溯法实现回溯法实现的主要思路首先是把棋盘的横坐标定一个栈和

4、非递归方法实现一下。可以让读者体验一下递归和非递归方法的区别,能够让初学者学会递归和非递归方法之间的转换。 本文将主要介绍采用堆栈非递归实现数据结构中的经典算法八皇后问题。3、堆栈的使用堆栈是一种执行“后进先出”算法的数据结构。 它 是在内存中开辟一个存储区域, 数据一个一个顺序地为 i,纵坐标定为 j,i 和 j 的取值范围是从 1 到 8。当某个皇后占了位置(i,j)时,在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。 在语句实现 中可定义如下三个整型数 组 :a8,b15,c24。 其 中 :aj-1=1 表示第 j 列上无皇后;aj-1=0 表示第 j 列上有皇后;bi+

5、j-2=1 表示(i,j)的对角线(左上至右下)无 皇后;bi+j-2=0 表示(i,j)的对角线(左上至右下)有皇 后;ci-j+7=1 表示(i,j)的对角线(右上至左下)无皇后;存入(也就是“压栈push”)这个区域之中。有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元,存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫做“栈底”。 在压栈的过程中,每ci-j+7=0 (i,j)的对角线(右上至左下)有皇后。为第 i 个皇后选择位置,其算法实现如下:for(j=1;j=8;j+) /* 第 j 个皇后在第 j 行 */然后是有一个数据压入堆栈,就放在和前一个单元相连的

6、后面一个单元中,堆栈指示器中的地址自动加 1。 读取这些数据时,按照堆栈指示器中的地址读取数据,堆栈指 示器中的地址数自动减 1。 这个过程叫做“弹出 pop”。if (i,j)位置为空)) /* 即相应的三个数组的对应元素值为 1*/如此就实现了后进先出的原则。堆栈是计算机中最常占用位置值为 0*/if i8(i,j) /* 置相应的三个数组对应的元素用的一种数据结构,比如函数的调用在计算机中是用堆栈实现的。 堆栈可以用数组存储, 也可以用链表存储。 堆栈的结构体定义如下:#define MAX_SIZE 100 typedef int DATA_TYPE;为 i+1 个皇后选择合适的位置;

7、else 输出一个解在非递归中, 程序如何知道到底要转移DATA_TYPE dataMAX_SIZE;int top;这里面包括一个栈顶指针,一个数据项数组。 栈顶 指针最开始指向-1,然后存入数据时,栈顶指针加 1,取出数据后,栈顶指针减 1。在实现八皇后问题中,也可以用数组来存储堆栈,它用一个数组 arr 来表示皇后在行间或位置;depth 表 示下一步探索的深度;Stack 作为上层跳转下来时上层分继续执行? 例如数据结构中树的三种遍历出来只有三种操作:访问当前结点,访问左右子树。 这三种操作的顺序不同,遍历方式也果我们再抽象一点,对这三种操作再进行一以得到:访问当前结点:对目前的数据进

8、行 访问左子树:变换当前的数据以进行下一次 右子树:再次变换当前的数据以进行下一次问左子树所不同的方式)。 也就是说一般来说归方法一般采用堆栈。位置的中间纪录.*;Size 表示问题的规模。的算法如下:NQueensProblem Stack Version压首行首列元素 0 进栈. depth 置 1doIf depth 达到 size则跳出并输出结果ElseIf(当前层depth-1达到了底部)其堆栈实现在八皇后问题中,可以加入一个栈,采用归方法来实现,其非递归实现的主要代码如printf(ndepth%dn,depth);if(flag=1)printf(resolve successf

9、ullyn);elseprintf(no resolven);/*aid fun*/int checkXiePos(int r1,int r2,int c1,int c2)return ! (fabs(r1-r2)=fabs(c1-c2);int checkVPos(int* arr,int len)int flag=1;int i,j;assertF(arr! =NULL,in checkVPos,arr is nulln);for(i=0;ilen-1;i+)for(j=i+1;jlen;j+)if(arri=arrj)flag=0;break;return flag;int partFi

10、nished(int* arr,int len)int flag=1;int i,j;assertF(arr! =NULL,in partFinished,arr is nulln);flag=flag&checkVPos(arr,len); for(i=0;ilen-1;i+) for(j=i+1;jlen;j+) flag=flag&checkXiePos(i,j,arri,arrj);if(! flag)goto out;out:return flag;5、结论将搜索层上跳一层并压栈 *Else搜索层(depth)试探同层的下一个位置 iif 这个位置有冲突并且 i 没有超出问题规模 将

11、 i 置于同层的下一个位置.else if 这个位置有冲突并且 i 已超出问题规模 返回到上层的跳下来的位置,借助堆栈( 先弹出, 然 后 压 新 位置)*探索层仍为 depthElse 当前位置没有冲突当前位置压栈Depth 下跳一层(depth+)4、非递归方法4.1 递归方法原理用栈保存未完成的工作,在适当的时候从栈中取出并执行。 系统保存了工作的数据和状态,数据就是函数的局部变量,状态就是程序指针。4.2 非递归方法原理和递归的原理相同, 只不过是把由系统负责保存工作信息变为程序自己保存,这样能减少保存数据的本文中主要讨论了采用堆栈非递归方法冗余(主要是节省了局部变量的空间),提高存储

12、效率;把程序要完成的工作分成两类: 手头工作和保存在栈 中的待完成的工作。 手头工作指程序正在做的工作。 由 于某些工作不能一步完成,必须暂缓完成,于是可把它 保存在栈中,这就是待完成的工作。 手头工作必须有 其结束条件,不能永远做下去;保存的待完成工作必须结构中经典的问题八皇后问题,采用堆的方法解决了递归方法中效率的问题, 而且者了解了堆栈的含义,进一步的了解。对数据结构的综合应参考文献:1严蔚敏.数据结构(C 语言版)M 清华大学出版社,2003 2 黄 建 民 、 罗 杰. 八皇后问题的非递归算法设计 J 计算 2004(5)含有完成该项工作的所有必要信息。程序必须有秩序地完成各项工作。 如,可把手头工作恰当处理(直接处理或暂时保存)后,才能继续接手下一步的工作。 待完

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 科普知识


经营许可证编号:宁ICP备18001539号-1