数据结构八皇后问题实习报告资料.docx

  1. 1、本文档共14页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构 实习报告 专业:数字媒体技术 姓名:李义 年级:2013级 学号:201301052015 完成日期:2015.12.31 题目:八皇后问题 一、项目简介 八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8?8格的国际象棋棋盘上,安放八个皇后,要求没有一个皇后能够“吃掉”任何其他一个皇后,即任意两个皇后都不能处于同一行、同一列或同一条对角线上,求解有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法得出结论,有92种摆法。 二、概要设计 2.1 主要模块: 这个程序主要由4个模块组成,分别是画棋盘模块,画皇后模块,输出皇后摆法模块,和解决如何摆置皇后模块。这4个模块隶属于主函数模块。既主函数通过对这4个模块的合理调用解决“8皇后问题”,同时这4个模块之间也互有调用。 2.2 程序设计的数据结构及其关系: 数据结构的实现:数组a[i]:a [i]表示第i个皇后放置的列;i的范围:1-8;对角线数组:b[j](主对角线),c[j](从对角线),根据程序的运行,去决定主从对角线是否放入皇后;然后进行数据的初始化。从n列开始摆放第n个皇后(因为这样便可以符合每一竖列一个皇后的要求),先测试当前位置(n,m)是否等于0(未被占领):如果是,摆放第n个皇后,并宣布占领(切记要横列竖列斜列一起来),接着进行递归;如果不是,测试下一个位置(n,m+1),但是如果当时,却发现此时已经无法摆放时,便要进行回溯。 三 、详细设计 3.1 定义相关的数据类型: 3.1.1 定义的相关数据类型: int A[21],B[21],C[21],Y[8]; void *buff1,*buff2 3.1.2 设计思想: 本程序通过对子函数void qu(int i)的调用,将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂,繁琐,但在实际中,只要当一只皇后放入棋盘后,在横与列、斜线上没有另外一只皇后与其冲突,再对皇后的定位进行相关的判断。即可完成。如果在这个程序中,我们运用的是非递归的思想,那么将大量使用if等语句,并通过不断的判断,去推出答案,而且这种非递归的思想,大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后,那么程序的时间复杂度,以及相关的代码简化都能取得不错的改进。这个程序,我运用到了数据结构中的栈、数组,以及树和回溯的方法。特别是在对于树以及二叉树的学习,更是为八皇后的问题提供了科学的解决方案,通过对树的分析,把八皇后的问题看成了树,而在衍生第一个变化后,上面的第一层八个变化就变成了八个结点,而这八个结点再继续的衍生??,这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计,回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中,它先进行判断,棋盘上是否已经得到一个完整的布局(即棋盘是否已经摆上8个棋子),如果是,则输出布局;如果不是则依次先根遍历满足约束条件的各棵子树,流程即是: 判断该子树根的布局是否合法:如果合法的话,则先根遍历该子树;如果不合法的话,则剪去该子树的分支。 3.2 相关代码及算法 3.2.1 主模块C码算法: void main(void) { Queen Q; int gdriver=DETECT,gmode; initgraph(gdriver,gmode,D://Win-TC); SetQueen(Q); setcolor(YELLOW); QueenPic(); cleardevice(); setcolor(LIGHTGREEN); settextstyle(0,0,3); outtextxy(180,10,Eight Queens); setcolor(WHITE); settextstyle(0,0,1); outtextxy(250,400,2009.11.8 3:30pm); QueenRe(Q,0); getch(); closegraph(); } 3.2.2 棋盘模块C码算法 void Checker(void) /* 画棋盘函数 */ { int i,k; for(k=0;k8;k++) for(i=0;i8;i++) if(k%2==0i%2==0||k%2!=0i%2!=0) { setfillstyle(SOLID_FILL,LIGHTBLUE); setcolor(LIGHTBLUE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,L

文档评论(0)

希望之星 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档