当前位置：文档之家 › 数据结构集中上机实验报告

数据结构集中上机实验报告

  • 格式：doc
  • 大小：305.50 KB
  • 文档页数：16

XX大学

信息与计算科学专业

2008级《数据结构》集中上机

设计题目： 迷宫求解（非递归求解）

设计时间： 2010-2011学年第一学期

姓名 班级 学号 成绩

1 目录

一、实验内容............................................................................................. 2

二、需求分析............................................................................................. 2

三、总体设计............................................................................................. 2

（一）存储结构 .................................................................................. 2

（二）流程图 ...................................................................................... 3

四、详细设计............................................................................................. 3

（一）基本算法解析 .......................................................................... 3

（二）为实现算法，需要的象的数据类型 ...................................... 4

(三)函数的调用关系 ............................................................................ 5

（四）算法时间、空间复杂度 .......................................................... 5

五、代码 ..................................................................................................... 5

六、运行结果分析 .................................................................................. 10

（一）迷宫路径探索成功 ................................................................ 10

（二）迷宫路径未找到的情况 ........................................................ 13

（三）程序的优缺点与改进 ............................................................ 13

七、参考文献........................................................................................... 14

八、心得体会........................................................................................... 14

2 一、实验内容

任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。

二、需求分析

1、可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求使用非递归算法。

2、用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立迷宫。

3、可以自行输入迷宫的入口和出口坐标。

4、程序执行的命令包括：

（1）构造栈函数。其中包括了构造空栈InitStack；压入新数据元素Push；栈顶元素出栈Pop。

（2）构造求迷宫路径函数。其中定义了二维数组maze[M][N]存取迷宫数据；输出找到的通路MazePath。

（3）建立一个迷宫initmaze。其中包括输入迷宫行数列数以及各行各列；加一圈围墙并输出迷宫。

三、总体设计

（一）存储结构：

首先用二维数组存储迷宫数据，迷宫数据由用户输入。

一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东南西北所用代表数字，自行定义）。

1．从入口出发，顺着某一个方向进行探索，若能走通，继续往前走，否则沿原路退回，换 一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到但没能到达出口，则所设置的迷宫没有通路。

迷宫的入口点的下标（a,b），出口点的下标（m,n）。为方便，可在迷宫周围加一周障碍。对于迷宫的任意位置，均可约定有东西南北4个方向可以走通。经过的位置把0变成-1，输出迷宫路径。

2本程序有三个模块;

（1） 主程序模块

（2） 三个模块即其对象，实现栈链表抽象数据类型

（3） 迷宫存储迷宫，寻路径，输出迷宫。 3 （二）流程图

四、详细设计

（一）基本算法解析：

首先用二维数组存储迷宫数据，迷宫数据由用户输入。

一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表存取迷宫maze[M][N]

输入迷宫的行和列的内容

求取一条路径MazePath

迷宫无路径 显示结果

while(S1){Pop(S1,e);Push(S2,e); while(S2) { Pop(S2,e);

printf("-->(%d,%d,%d)",e.x,e.y,e.d)

END 函数Push,Pop

调用 函数MazePath，Push,Pop

调用

if(a==end.x&&b==end.y&&maze[a][b]==0)Push(S1,elem); 4 示走到下一坐标的方向（东南西北所用代表数字，自行定义）。

迷宫的过程可以模拟成一个搜索的过程。每到一处，总让它按东西南北四个方向顺序试探下一个位置，如果某方向可以通过，并且不曾到达，则前进一步，在新的位置上继续进行探索。如果4个方向都走不通或者曾经到达过，则退回一步，在原来的位置上继续试探下一位置。

每前进一步或后退一步，都要进行判断，若前进到了出口处，则说明找到了一条通路，若退回到了入口处，则说明不存在通路。

用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（a,b）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为期寻找一条从入口点到出口点的通路。

二维数组的0行m+1列元素全置成“1”，表示迷宫的外墙，第一行第一列元素和第m行m列元素置成“0”，表示迷宫的入口和出口。

假设当前所在位置是（x,y）。延某个方向前进一步，它可能到达的位置最多有4。

如果用结构体Element elem记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用结构体Element elem确定

while(!StackEmpty(S1)) //栈不为空 有路径可走

{

Pop(S1,elem);

i=elem.x;

j=elem.y;

d=elem.d+1;

从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。定义一个栈，按从入口到出口存取路径，在搜索过程中，每前进一步，如果有新位置入栈，则把上一个探索的位置存入栈中，当前位置“-1”（表示这个位置在通路上），并将该位置的坐标压入栈中。

如果没有新位置入栈，则返回到上一个位置。

一直到达出口。

总之，入口出发，顺着某一个方向进行探索，若能走通，则继续往前进，否则沿着原路返回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。

迷宫的入口点在位置（1,1），出口点在位置（m,n）。为处理方便，可在迷宫的四周加一周障碍。对于迷宫的任一位置，均可定为东南西北四个方向可通。

（二）为实现算法，需要的象的数据类型

InitStack() 构造空栈

StackEmpty() 判断栈是否为空

Push() 压入新数据元素

Pop() 栈顶元素出栈

m 迷宫的行数

n 迷宫的列数

d 0=东 1=南 2=西 3=北 5 typedef struct Lstack

{

Element elem; 链栈

struct LStack *next;

}*PLStack;

(三)函数的调用关系

main

initmaze mazePath

InitStack Push Pop

（四）算法时间、空间复杂度

1）本算法在空间上主要开辟了一个二维数组，规模都是迷宫（m+2）*（n+2）。一个是栈，一个是迷宫路径记录，输入时候调用栈。

2)在时间上为简单的链表栈的存储结构，二维指针initmaze函数算法时间复杂度为O（（m+2）*（n+2）），Mazepath为O（1），（m为行数n为列数）。

五、代码

/*以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

首先实现一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。*/

#include

#include

#define M 15

#define N 15

合集下载

上机实验报告(精选11篇)

上机实验报告(精选11篇)

上机实验报告 篇1

用户名se××××学号姓名学院

①实验名称：

②实验目的：

③算法描述（可用文字描述，也可用流程图）：

④源代码：（.c的文件）

⑤用户屏幕（即程序运行时出现在机器上的画面）：

2．对c文件的要求：

程序应具有以下特点：a可读性：有注释。

b交互性：有输入提示。

c结构化程序设计风格：分层缩进、隔行书写。

3.上交时间：12月26日下午1点-6点，工程设计中心三楼教学组。请注意：过时不候哟！

四、实验报告内容

0．顺序表的插入。

1.顺序表的删除。

2．带头结点的单链表的\'插入。

3.带头结点的单链表的删除。

注意：1.每个人只需在实验报告中完成上述4个项目中的一个，具体安排为：将自己的序号对4求余，得到的数即为应完成的项目的序号。

例如：序号为85的同学，85%4=1，即在实验报告中应完成顺序表的删除。

2.实验报告中的源代码应是通过编译链接即可运行的。

3.提交到个人空间中的内容应是上机实验中的全部内容。

上机实验报告 篇2

一、《软件技术基础》上机实验内容

1．顺序表的建立、插入、删除。 2．带头结点的单链表的建立（用尾插法）、插入、删除。

二、提交到个人10m硬盘空间的内容及截止时间

1．分别建立二个文件夹，取名为顺序表和单链表。

2．在这二个文件夹中，分别存放上述二个实验的相关文件。每个文件夹中应有三个文件(.c文件、.obj文件和.exe文件)。

3. 截止时间：12月28日（18周周日）晚上关机时为止，届时服务器将关闭。

三、实验报告要求及上交时间（用a4纸打印）

1．格式：

《计算机软件技术基础》上机实验报告

用户名se×××× 学号 姓名 学院

① 实验名称：

② 实验目的：

③ 算法描述（可用文字描述，也可用流程图）：

④ 源代码：（.c的文件）

⑤ 用户屏幕（即程序运行时出现在机器上的画面）：

2．对c文件的要求：

程序应具有以下特点：a 可读性：有注释。

数据结构集中上机实验报告

数据结构集中上机实验报告

XX大学

信息与计算科学专业

2008级《数据结构》集中上机

设计题目： 迷宫求解（非递归求解）

设计时间： 2010-2011学年第一学期

姓名 班级 学号 成绩

目录

一、实验内容............................................................................................. 2

二、需求分析............................................................................................. 2

三、总体设计............................................................................................. 2

（一）存储结构 .................................................................................. 2

（二）流程图 ...................................................................................... 3

四、详细设计............................................................................................. 3

（一）基本算法解析 .......................................................................... 3

（二）为实现算法，需要的象的数据类型 ...................................... 4

数据结构上机矩阵排列实验报告

数据结构上机矩阵排列实验报告

数据结构实验报告

1. 实验要求

创建一个m x n的矩阵，要求每行元素按非减的次序排列。

2. 实验代码

#include

#define M 5

#define N 5

void Init(int A[M][N])

{

int i,j;

int value;

for(i=0;i

for(j=0;j

{

scanf("%d",&value);

A[i][j]=value;

}

return;

}

void Display(int A[M][N])

{

int i,j;

for(i=0;i

for(j=0;j

{

printf("%5d",A[i][j]);

if(j==N-1)

printf("\n");

}

return ;

}

void paixu(int A[M][N])

{

int i,t,j,p;

int a[N];

for(p=0;p

{

for(i=0;i

{

for(i=0;i

{

for(j=0;j

if(a[j]>a[j+1])

{

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

}

}

for(i=0;i

A[p][i]=a[i];

}

}

void main()

{

int A[M][N];

printf("输入5*5数组\n");

Init(A);

printf("显示数组\n");

Display(A);

paixu(A);

printf("显示排序后的数组\n");

Display(A);

}

3. 实验截图

流程图：

4. 实验小结

掌握了数组的创建和显示的操作，矩阵每行视作一个一维数组，采用冒泡排序算法。

开始

输入一组数据

数据结构上机操作实验报告

数据结构上机操作实验报告

实验一 单链表的基本操作（必做）

一、实验目的

1.掌握单链表的存储、初始化、插入、删除等操作的程序实现。

2.加深对单链表基本概念,基本理论及相应算法的掌握与理解。

3.了解链表的处理方式，学习体会简单的单链表程序实现相关知识。

二、实验内容

1.建立一个链表、设计链表的基本操作实现算法、输出一个链表表，调试并输出结果。

2.编写一个程序实现如下功能：让计算机产生出50个0~9之间的随机数并依次保存到单链表中;输出遍历单链表；从单链表中删除与给定值相等的所有结点；输出遍历单链表；输出单链表长度，调试并输出结果。

三、实验步骤

1.定义一个链表结构体。。

2.利用插入功能插入一个结点。

3.利用删除功能删除一个结点。

四、程序运行测试

1.利用插入功能插入一个结点。

2.利用删除功能删除一个结点。

五、实验报告要求

1.绘制链表操作实现的流程图。

2.详细给出程序运行测试结果（包括测试数据和测试结果）。

3.选试验步骤2-3中的任意一个，给出程序的详细注释。 4.参考程序中某一部分功能的改进（选做）

5.实验心得与体会

6.附录，实验用源程序

六、参考源代码

#include

#include

typedef struct LNode

{int data;

struct LNode *next;

}Lnode, *LinkList;

//假设下面的单链表均为带头结点。

void CreatLinkList(LinkList &L,int j)

{//建立一个单链表L,数据为整数，数据由键盘随机输入。

LinkList p,q;

L=(LinkList )malloc(sizeof(Lnode));

L->next=NULL;

q=L;

cout<<"在单链表内输入整数："<

for(int i=0;i

cin>>p->data;

p->next=q->next;