数据结构课程设计

《数据结构》

课程设计。一、迷宫问题。

1. 表示迷宫的数据结构：

设迷宫为m 行n 列，利用maze[m][n]来表示一个迷宫，maze[m][n]=0或1；其中0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，而四个角点有2个方向，其它边缘点有3个方向，为了使所有点都有4方向可探，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。

2. 试探方向：

每个点有四个方向去试探，如当前坐标（x,y），与其相邻的四个点的坐标都可根据与该点的相邻方向而得到，从当前位置向前试探的方向为从正东沿顺时针进行的四个方向为：(x,y+1),(x+1,y),(x,y-1),(x-1,y)。将这4个方向的坐标增量放在一个结构数组move[4]中，在move数组中，每个元素有两个域组成，x:

横坐标增量，y:纵坐标增量。

move数组如下：

typedef struct

int pop_seqstack(pseqstack s , datatype *x)

/*入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。*/

if (empty_seqstack ( s )

return 0; /栈空不能出栈 */

else int mazepath(int maze[m+2][n+2],item *move,int x0,int y0)//入口参数：指向迷宫的数组，指向移动方向的指针，开始点(x0,y0),出口点(m，n)，返回值1表示有路径，0表示无路径。

pseqstack s

datatype temp;

int x,y,d,i,j;

s=init_seqstack();初始化栈。

if(!s)

push_seqstack(s,temp);/迷宫入口点入栈。

printf("所走路径为：");

while(!empty_seqstack(s))

//while(!empty_seqstack(s))

destroy_seqstack(&s);/销毁栈。

return 0;

void main()

int i,j;

int s;

int maze[6+2][8+2]=,迷宫初始化。

printf("输入迷宫为：");

for(i=1;i<7;i++)

item mv[4];

mv[0].x=0;mv[0].y=1;mv[1].x=1;mv[1].y=0;

mv[2].x=0;mv[2].y=-1;mv[3].x=-1;mv[3].y=0;//四个方向初始化。

s=mazepath(maze,mv,1,1);

printf("");

for(i=1;i<7;i++)

6. 运行结果：

二、八皇后问题。

1.八皇后介绍：

在国际象棋中，皇后的势力范围包括上、下、左、右、左上、左下、右上、右下共八个方向，但每行、每列、对角线不允许出现两个皇后。

2.程序构想：

运用递归来求解八皇后问题，必须先判断传入的坐标位置是否可放置皇后。（判断该坐标上、下、左、右、左上、左下、右上、右下八个方向是否有其他的皇后，有返回0，无返回1）。

假设传入的坐标为（x,y），则：

坐标上方：（x,y-1）到（x,0）是否有其它皇后。

坐标下方：（x,y+1）到（x,8-1）是否有其它皇后。

坐标左方：（x-1,y）到（0,y）是否有其它皇后。

坐标右方：（x+1,y）到（8-1,y）是否有其它皇后。

坐标左上方：（x-1,y）到（x,0）或（0,y）是否有其它皇后。

坐标右上方：（x+1,y-1）到（x,0）或（8-1,y）是否有其它皇后。

坐标左下方：（x-1,y+1）到（x,8-1）或（0,y）是否有其它皇后。

坐标右下方：（x+1,y+1）到（x,8-1）或（8-1,y）是否有其它皇后。

递归结束条件：

当八皇后都放置成功。

递归执行部分：

判断传入的坐标是否可放置皇后，可以放置则依序递归放置下一个皇后。

3.源程序为：

#include""

char chessboard[8][8声明8×8的空白棋盘。

int queenplace(int x,int y) /判断传入坐标是否可放置皇后。

int i,j;

if(chessboard[x][y]!=x') 判断是否有皇后。

return 0;

for(j=y-1;j>=0;j判断上方是否有皇后。

if(chessboard[x][j]!=x')

return 0;

for(j=y+1;j<8;j判断下方是否有皇后。

if(chessboard[x][j]!=x')

return 0;

for(i=x-1;i>=0;i判断左方是否有皇后。

if(chessboard[i][y]!=x')

return 0;

for(i=x+1;i<8;i++)判断右方是否有皇后。

if(chessboard[i][y]!=x')

return 0;

i=x-1;

j=y-1;

while(i>=0&&j>=0) /判断左上方是否有皇后。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了