数据结构 八皇后问题 报告
更新时间:2023-07-20 21:36:01 阅读量: 实用文档 文档下载
- 数据结构推荐度:
- 相关推荐
数据结构实验报告
实验名称:实验2 利用栈结构实现八皇后问题
学生姓名: 廖宁
班 级: 2009211114
班内序号: 18
学 号: 09210411
日 期: 2010年11月18日
1.实验要求
八皇后问题是19世纪著名的数学家高斯于1850年提出的。他的问题是:在8*8的棋盘上放置8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。
提示:
(1)可以使用递归或非递归两种方法实现。
(2)实现一个关键算法,判断任意两个皇后是否在同一行、同一列和同一斜线上。
2. 程序分析
程序工程包含一个模板类函数实现定义的源文件forthelove.cpp和测试源文件sbsuowang.cpp。
2.1 存储结构
存储结构为栈。
2.2 关键算法分析
(1)
判断在第row行第column列摆放皇后是否非法,采取定行不定列的方法,列相等的算法为position[i]=colume,对角线相等有两种情况:一是position在上则
row-i=colume-position[i];
二是position在下,row-i=position[i]-colume.加入能放皇后,列和对角线上值都不能相等。 具体代码如下:
int IsIllegal(int row, int column, const int* position)
{/
int i;
for (i=1; i < row; ++i)
{
if ((position[i] == column)
|| (row - i == column - position[i])
|| (row - i == position[i] - column))
{
return TRUE;
}
}
return FALSE;
}
(2)
我采用定行尝试列的方法来遍历,记录皇后位置的数组可以和栈数组合二为一,而栈顶指针也可以和行坐标合二为一,这样一来栈帧只要一个列坐标就可以了。
1.伪代码:
while(栈不空)
{
if ( 行(即栈顶) <= n && 列 <= n )
{
if ( 当前位置不能放皇后 )
{
列++;
}
else
{
列入栈(隐含着"行++");
列 = 1;
}
}
else
{
if ( 行(即栈顶) > n )
{
输出位置数组(即栈数组);
}
列退栈(隐含着"行--");
列++;
}
}//end while
具体实现代码:
void Queens(int n, void (* Visit)(const int* position))
{
//position[n]数组:position[0]为棋盘大小,即n
//position[1]~position[n]:下标为行坐标,值为列坐标
int* stack = NULL; //栈
int top; //栈顶
int column; //列
stack = (int*)malloc((n + 1) * sizeof(int));
stack[0] = n;
top = column = 1;
while(top > 0)
{
if ((top <= n) && (column <= n))
{
if (IsIllegal(top, column, stack))
{
++column;
}
else
{
stack[top++] = column;
column = 1;
}
}
else
{
if (top > n)
{
(* Visit)(stack);
}
column = stack[--top];
++column;
}
}//end while
free(stack);
return;
}
3. 程序运行结果
程序实现八皇后问题:
经过测试,程序运行良好,无明显错误。
4. 总结
(1)这次上机实验,用栈结构实现了八皇后问题,总体上程序没有很大毛病,基本上运行良好。
(2)这个程序不仅解决了八皇后的问题,求出了八皇后的摆放方法数,并有效的输出,同时推广到n皇后问题上,只要n的数值不是很大,都能正确的得出结果,这是不错的提升。
(3)对栈结构有了深刻的认识,数据结构的东西,必须是经过上机去体会的,不能拘泥于课本,课本的东西还是比较基础的,有时候需要实用的知识的时候,多参考查询网上的知识是非常有益的。
(4)最后衷心感谢老师和同学在我做这个程序过程中的关心和帮助。
正在阅读:
数据结构 八皇后问题 报告07-20
评审简表12-13
新时期电力企业工会做好财务经审的几点思考06-26
六年级语文下册第三单元珍惜《可爱的中国》教案北师大版03-16
高速公路临建施工方案 - 图文03-27
宗教知识竞赛03-18
陌生奶奶作文900字07-02
幼儿园教学工作报告02-25
润滑油常规分析项目05-31
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 数据结构
- 皇后
- 报告
- 问题
- 2017全国青少年禁毒知识竞赛选择题及答案
- 第三章第四节 小学生记忆的发展
- 高速移动环境下WiMAX系统多普勒频移估计技术研究
- 嵌入式系统在过电流保护装置中的应用研究
- 人教版六年级上册数学第一次月考试卷2
- 广州市白云区某污水处理系统一期工程尾水排放管工程施工组织设计
- 胰岛素泵的使用方法和临床注意事项
- 多媒体教学方法研究
- NRE-FL101M10V10X12.5F中文资料
- 2.5.1平面几何中的向量方法2.5.2向量在物理中的应用举例(教、学案)
- 邮政营业员职业技能鉴定考试模拟试题1
- 常按四穴位 保肾养健康
- 2010年广东省高等职业院校招收中等职业学校毕业生考试(英语)试题
- 中央财政造林补贴试检查验收管理办法
- 电路第十三章 拉普拉斯变换
- 2012最新中考化学总复习之化学式和化合价
- 国旗下讲话稿期中考试总结
- RBI在石化工业中应用
- Logistic映射分岔图局部放大的计算机模拟
- 高三文科练习一三角函数的图像与性质