课程设计

第1章 八皇后问题

经济管理学院本科课程设计论文

数据结构课程设计

学 号： 1005170116

姓 名： 李 登

班 级： 管理101

专 业： 信息管理与信息系统

系 别: 管理系

指导教师： 孙鸿飞

2011 年 12 月 30日 吉 林

课程设计

课程设计

目录

第1章 八皇后问题............................................................................................................- 1 -

1. 1课题综述八皇后问题的来源及意义 ......................................................................- 1 -

1. 2 面对的问题 ........................................................................................................- 1 -

1.2．1解决冲突问题 ...........................................................................................- 1 -

1.2．2所用的知识 ..............................................................................................- 2 -

1.3需求分析 ..............................................................................................................- 2 -

1.3.1 涉及到的知识点 ........................................................................................- 2 -

1.3.2 功能要求 ...................................................................................................- 2 -

1.4概要设计 ..............................................................................................................- 2 -

1.4.1解决冲突问题.............................................................................................- 3 -

1.4.2数据结构的实现 .........................................................................................- 3 -

1.4.3流程图 .......................................................................................................- 4 -

1.5详细设计 ..............................................................................................................- 4 -

1.6调试分析及测试....................................................................................................- 6 -

1.6.1 遇到的问题及解决方法 ..............................................................................- 6 -

1.6.2 算法的时空分析 ........................................................................................- 7 -

1.6.3 程序模块构架 ............................................................................................- 7 -

1.6.4 程序使用说明 ............................................................................................- 7 -

1.6.5测试结果....................................................................................................- 7 -

第2章 停车场管理问 ...................................................................................................... - 10 -

2.1要解决的问题 ..................................................................................................... - 10 -

2.2基本要求 ............................................................................................................ - 10 -

2.2.1解决问题的思路及要求............................................................................. - 10 -

2.2．2对栈的要求 ............................................................................................ - 11 -

2.2.3算法流程图 .............................................................................................. - 11 -

2.5.1栈的抽象数据类型.................................................................................... - 13 -

2.5.2链式队列的抽象数据类型 ......................................................................... - 14 -

2.6模块划分 ............................................................................................................ - 16 -

2.6.1主程序模块 .............................................................................................. - 16 -

2.6.2 两个栈模块 ............................................................................................. - 16 -

2.6.3队列模块.................................................................................................. - 17 - 实现队列抽象数据类型 ...................................................................................... - 17 - 数据对象：D={aiai∈ElemSet,i=1,2, ,n,n=0}................................................... - 17 -

2.6.4模块调用关系........................................................................................... - 17 -

2.7详细设计与源程序 .............................................................................................. - 17 -

课程设计

2.7.1详细设计.................................................................................................. - 17 -

2.7.2部分源程序 .............................................................................................. - 18 -

2.8调试过程中的问题及系统测试情况...................................................................... - 20 -

2.8.1出现的问题 .............................................................................................. - 20 -

2.8.2运行过程..................................................................................................- 20 - 课程设计心得体会 .................................................................................................... - 26 - 参考文献 .................................................................................................................. - 26 - 附录 ......................................................................................................................... - 26 -

课程设计

第1章 八皇后问题

1.1课题综述八皇后问题的来源及意义

八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。

1. 2 面对的问题

1.2．1解决冲突问题

这个问题包括了行，列，两条对角线；

列：规定每一列放一个皇后，不会造成列上的冲突；

行：当第I行被某个皇后占领后，则同一行上的所有空格都不

再放皇后，要把以I为下标的标记置为被占领状态；

课程设计

1.2．2所用的知识

使用数据结构的知识，用递归法解决问题

1.3需求分析

1.3.1 涉及到的知识点

本次课程设计中，用到的主要知识有：

递归法的运用，for语句的灵活运用。

数据结构中树知识的灵活运用、栈及数组的掌握。

1.3.2 功能要求

当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观的界面显示。

进入界面后，就会提示输入字符串的输入形式，在八皇后求解程序中，只要你选择输出解的格式，选择1则显示为每一列皇后的放置的行数，，选择2则显示的是以矩阵形式形象的显示皇后的放置位置，选择0则退出程序的调试。在调试结果中，1的位置也就表示了该皇后应该所在的位置，0代表了空位置。

1.4概要设计

本课件学生是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。在这个程序中，我的主要思路以及思想是这样的：

课程设计

1.4.1解决冲突问题

这个问题包括了行，列，两条对角线；

列：规定每一列放一个皇后，不会造成列上的冲突；

行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要 把以I为下标的标记置为被占领状态；

对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。

1.4.2数据结构的实现

而对于数据结构的实现，学生则是着重于:

数组a[I]：a [I]表示第I个皇后放置的列；I的范围：1..8; 对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后

课程设计

1.4.3流程图

图1-1 算法流程图

1.5详细设计

解析：递归实现n皇后问题。

算法分析：

数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列。如果某列上已经有皇后，则为1，否则为0。

数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]。如果某条主对角线上已经有皇后，则为1，否则为0。

数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]。如果某条从对角线上已经有皇后，则为1，否则为0。

代码如下：

课程设计

#include <stdio.h>

static char Queen[8][8];

static int a[8];

static int b[15];

static int c[15];

static int iQueenNum=0; //记录总的棋盘状态数

void qu(int i); //参数i代表行

int main()

{

int iLine,iColumn;

//棋盘初始化，空格为*，放置皇后的地方为@

for(iLine=0;iLine<8;iLine++)

{

a[iLine]=0; //列标记初始化，表示无列冲突

for(iColumn=0;iColumn<8;iColumn++)

Queen[iLine][iColumn]='*';

}

//主、从对角线标记初始化，表示没有冲突

for(iLine=0;iLine<15;iLine++)

b[iLine]=c[iLine]=0;

qu(0);

return 0;

}

void qu(int i)

{

int iColumn;

for(iColumn=0;iColumn<8;iColumn++)

{

if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)

//如果无冲突

{

Queen[i][iColumn]='@'; //放皇后

a[iColumn]=1; //标记，下一次该列上不能放皇后

b[i-iColumn+7]=1; //标记，下一次该主对角线上不能放皇后 c[i+iColumn]=1; //标记，下一次该从对角线上不能放皇后

if(i<7) qu(i+1); //如果行还没有遍历完，进入下一行

else //否则输出

课程设计

{

//输出棋盘状态

int iLine,iColumn;

printf("第%d种状态为：\n",++iQueenNum);

for(iLine=0;iLine<8;iLine++)

{

for(iColumn=0;iColumn<8;iColumn++)

printf("%c ",Queen[iLine][iColumn]);

printf("\n");

}

printf("\n\n");

}

//如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置

Queen[i][iColumn]='*';

a[iColumn]=0;

b[i-iColumn+7]=0;

c[i+iColumn]=0;

}

}

}

1.6调试分析及测试

1.6.1 遇到的问题及解决方法

由于对八个皇后放置的位置不能一次确定，而且前一个皇后的放置位置直接影响着后面的放置位置，使程序调试时要花费不少时间。

本程序有些代码重复出现，显得程序的有些代码看起来很杂乱。但其中最主要的问题是逻辑错误导致程序死循环或不循环或循环一小部分,但是编译时却没有错误,就是没有正确的输出答案。

课程设计

1.6.2 算法的时空分析

该算法的运行时间和和皇后的放置方法成正比，在最好情况下的时间和空间复杂度均为O（1），在最差情况下均为O（n*n），平均情况在它们之间。

1.6.3 程序模块构架

本程序模块划分比较合理，且利用指数组存储棋盘，操作方便。至于整体的系统架构，为了简单起见，这样的系统可以分成两个模块，第一个模块是负责模拟问题、提供算法，而另外一个模块则致力于窗口演示，是一个窗体应用程序

1.6.4 程序使用说明

本程序的运行环境为DOS操作系统

进入演示程序后即显示文本方式的用户界面

进入界面后，就会提示输入字符串的输入形式，在八皇后求解程序中，只要你选择输出解的格式，选择1则显示为每一列皇后的放置的行数，，选择2则显示的是以矩阵形式形象的显示皇后的放置位置，选择3则退出程序的调试。在调试结果中，1的位置也就表示了该皇后应该所在的位置，0代表了空位置。

1.6.5测试结果

课程设计

图1-2

初步运行界面

图1-3 位置标明每一行皇后放置的列数

课程设计

图1-4 位置标明每一行皇后放置的列数

图1-5 视图矩阵形式显示皇后位置

课程设计

第2章 停车场管理问

2.1要解决的问题

停车场是一条可以停放n辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端，最先到达的第一辆车停在最北端）若停车场已经停满n辆车，后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场，每两停在车场的车要安时间长短缴费。 要求：以栈模拟停车场，以队列车场外的便道，按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码、以及到达或离去的时刻。对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费）。栈以顺序结构实现，队列以链表结构实现。

2.2基本要求

2.2.1解决问题的思路及要求

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车到达或离去信息，汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。

课程设计

2.2．2对栈的要求

需要另设一个栈，临时停放为离去的汽车让路而从停车场退出来的汽车，也 用顺序存储结构实现。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻

2.2.3算法流程图

课程设计

图2-1 算法流程图