数据结构课程设计报告

《数据结构》

课程设计报告。

安徽工业大学计算机学院。

2024年6月。

目录。一：马的遍历问题。

二：大数相乘问题。

一：马的遍历问题。

程序设计名称]:

马的遍历。程序设计要求]：

在中国象棋棋盘上，对任意位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。主要要求：依次输出所走过的各位置的坐标；最好能画出棋盘的图形形式，并在其上动态地标注行走过程。

程序问题分析]：

先了解中国象棋的相关信息与规则。中国象棋是9*10的棋盘，马的走法只有一种就是“马走日”，忽略“蹩脚马”的情况。接着通过程序要求分析，这个题目采用的是深度优先算法和回溯法：

在“走到”一个位置后要寻找下一个位置，如果发生“阻塞”的情况，就是后面走不通的情况，则向后回溯，重新寻找。在寻找下一步的时候，对周围的这几个点进行比较，从而分出优劣程度从而看它们周围可以走的点谁最少，然后就走那条可走路线最少的那条。经过这样的筛选后，就会为后面的路径寻找提供方便，从而减少回溯次数。

最后，本程序的棋盘和数组类似，因而采用数组进行存储，同时因为有回溯，所以采用栈的方法。同时还有八个方向的数组和为栈设计的每个点周围的八个方向那些可以走的数组。

数据结构设计]：

棋盘有10行9列，利用chess来表示一个棋盘，chess[i][j]=0或1；其中：0表示通路，1表示不通，当从某点向下试探时，中间点的8个方向可以试探；棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了保证边缘点也有八个方向可以走，使问题能够简单化，不用再判断当前点的试探方向有几个。栈（stack）是限定仅在表尾进行插入或删除操作的线性表。

因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。假设栈s=（a1,a2,，an），则称a1为栈底元素，an为栈顶元素。

栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（listinfirstout）的线性表。在棋盘问题中，假设以栈s记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。

由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。

1.同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了判断的方便，这里在棋盘周围各加了两层“墙”。具体数据结构定义如下：

int chess[14][13采用最大的中国象棋10*9制的。

int canpath[14][13][8每个棋子的八个方向哪些可以走。

typedef struct

棋盘的八个方向。

int y;

int x;

direction;

direction dir[8]=,八个方向。

typedef struct

栈的节点结构。

int x,y走过位置。

int di走向下一个方向。

pathnode;

typedef struct

if(d<9)

return d;

elsereturn -1;

void init_path(path *p)//初始化栈。

p->top=-1;

int push_path(path *p,pathnode t,int v)

if(p->top>=63+26*v)

return -1;

elseint empty(path p)

判断栈是否为空。

if(<0) return 1;

return 0;

int pop_path(path *p,pathnode *t)出栈。

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了