【免费】数据结构试题及答案文本格式的资源-CSDN文库

共18个文件

txt：15个

c：2个

doc：1个

数据结构试题及答案

需积分: 0 50 浏览量 2008-11-19 09:40:24 上传评论收藏 416KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

.rar （18个子文件）

数据结构试题及答案

第四章串.txt 39KB

第三章栈和队列.txt 68KB

数据结构--求迷宫路径（改） .doc 214KB

第二章.txt 69KB

第六章.txt 179KB

第十章排序.txt 108KB

接口试题.txt 36KB

第九章查找.txt 56KB

第五章.txt 77KB

zhu.txt 3KB

第二章试题.txt 43KB

KECHENGSHEJI.c 9KB

shanshan.txt 2KB

新建文本文档.txt 21KB

接口考试大纲.txt 1KB

第七章.txt 49KB

kebenmigong.c 4KB

zhuzhu.txt 4KB

NANCHANG UNIVERSITY

课程设计报告

课程名称：计算机技术综合课程设计

题目：数据结构求迷宫路径

学院：信息工程系：计算机

专业：计算机科学与技术

班级：计算机 <3> 班

学号： 022008139

学生姓名：罗强

时间： 2006

年

月

日至

月

日

免责声明：文档在线网（文档中国）中所有的文档资料均由文档在线网会员提供。文档在线网会对会员提

供的文档资料进行筛选和编辑，但是并不声明或保证其内容的合法性、正确性或可靠性。该文档资料的版

权属于提供者所有，有关版权的问题请直接与提供者联系。

一、需求分析

1、问题描述

2、基本要求

二、概要设计

1、数据结构

2、序模块

3、算法设计

三、详细设计

1、数据类型定义

2、函数实现代码

3.函数之间调用关系

四、调试分析

五、用户手册

六、测试结果

七、附件

原程序文件清单

数据结构求迷宫路径

题目：以一个m×n长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，

对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。(1)以二维数

组存储迷宫数据；(2)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一

个坐标。

一 . 需求分析

1．问题描述：

在迷宫中求出从入口到出口的路径。经分析，一个简单的求解方法是：从入口出发，

沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索

直到所有可能的通路都探索到为止。即所谓的回溯法。

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，

通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续

往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。

为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到

当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。

假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条

路径的算法的基本思想是：若当前位置可通，则纳入当前路径，并继续朝“下一位置”探

索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应

顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块

的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当

前位置”四周四个方向（东、南、西、北）上相邻的方块。

2. 基本要求

（）以二维数组 表示迷宫，其中 和 

及 和 为添加的一圈障碍，数组中以元素值为  表示通路，

表示障碍，限定迷宫大小 。

（）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数 

和列数 从第  行至第  行（每行  个数）为迷宫值，同一行的两个数之间用空

白字符相隔。

（）迷宫入口为（，），出口为（ ）。

（）每次移动只能从一个无障碍的单元到周围  个方向上任意无障碍的单元，编制程序

给出一条通过迷宫的路径或报告一个“无法通过”的信息。

（）本程序只求出一条成功的通路。

．测试数据见下表，当入口为（，）时，出口为（，）

用一个字符类型的二微数组表示迷宫，数组中的每个元素表示一个小方格，取值“0（表示

可以进出）或“1（表示不可以进出）

随机产生一个 8*8 的迷宫，其中使用迷宫障碍坐标如下：

（1，3），（ 1，7），（ 2，3），（ 2，7），（ 3，5），（ 3，6），

（4，3），（ 4，4），（ 5，4），（ 6，2），（ 6，6），（ 7，2），（ 7，3），

（7，4），（ 7，6），（ 7，7），（ 8，1）。

二. 概要设计

．数据结构

栈（ ）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾

端有特殊含义，称为栈顶（!"）相应的，表头端称为栈底（#!!）。不含元素的空

表称为空栈。

假设栈 $%（&，），则称  为栈底元素， 为栈顶元素。栈的修改是

按后进先出的原则进行的。因此，栈又称为后进先出（'()*+）的线性表。

在迷宫问题中，假设以栈 $ 记录“当前路径”，则栈顶中存放的是“当前路径上最后一个

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

操作即为“出栈”。

基本操作的函数原型说明。

．程序模块

栈的顺序存储表示

#define StackSize 100 //假定预分配的栈空间最多为 100 个元素

 typedef char DataType;//假定栈元素的数据类型为字符

 typedef struct{

 DataType data[StackSize];

 int top;

 }SeqStack;

基本操作的算法描述

（1）置栈空

 void InitStack（SeqStack *S）

 {//将顺序栈置空

  S->top=-1;

 }

（2）判栈空

 int StackEmpty（SeqStack *S）

 {

  return S->top==-1;

 }

（3）判栈满

 int StackFull（SeqStack *SS）

 {

 return S->top==StackSize-1;

 }

（4）进栈

 void Push（S，x）

 {

 if (StackFull(S))

 Error("Stack overflow"); //上溢，退出运行

 S->data[++S->top]=x;//栈顶指针加 1 后将 x 入栈

 }

（5）退栈

 DataType Pop（S）

 {

 if(StackEmpty(S))

 Error("Stack underflow"); //下溢，退出运行

 return S->data[S->top--];//栈顶元素返回后将栈顶指针减 1

 }

（6）取栈顶元素

 DataType StackTop（S）

 {

 if(StackEmpty(S))

 Error("Stack is empty");

 return S->data[S->top];

 }

 各模块之间的调用关系以及算法设计

（）$ , 中调用的 #,

-.+/!,0

-.+/.#,0

-.+/,0

-12345

-1)6'$5

-1*7

-1533*3

-1*853)'*9:

;"<$+

（）主程序 "" 中调用的  ,

#include "base.h"

#define INIT_SIZE 100 //存储空间初始分配量

#define INCREMENT 10 //存储空间分配增量

typedef struct{ //迷宫中 r 行 c 列的位置

int r;

int c;

}PostType;

typedef struct{

int ord; //当前位置在路径上的序号

PostType seat;//当前坐标

int di; //往下一坐标的方向

}SElemType; //栈元素类型

typedef struct{

评论收藏

内容反馈

zhuxuejuan

粉丝: 2
资源: 8

数据结构试题及答案 文本格式的

网络安全试题及答案.doc

东师计算机应用基础16秋在线作业2答案.doc

软考历年上半年考题及答案

计算机应用基础试题(带标准答案).docx

试题库数据库设计.doc

《计算机应用基础》试题二.doc.doc

电子商务大赛试题一(单选100).doc.doc

东财21秋《计算机应用基础》综合作业.docx

程序设计基础答案

TCP-IP详解试题

北交《计算机图形学》在线作业一答卷.txt

ASP ISchool随机抽题考试系统

50用户在线考试系统

在线考试系统文献综述

asp.net知识库

python入门到高级全栈工程师培训 第3期 附课件代码

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

GD32替换STM32注意事项.pdf

XCP协议的规范文档

NPPJSONViewer.zip

CANoe通过CAPL脚本实现自动测试

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

蓝牙BLE协议中文版.pdf

BaiduOCR.zip

AD20官方中文教程.pdf

最新资源

数据结构试题及答案文本格式的

python入门到高级全栈工程师培训第3期附课件代码

Qt 5实现串口调试助手（源工程文件、0积分下载）