《数据结构》
第五次实验报告
一、实验内容
1) 利用栈深度优先进行迷宫求解。
? 用数组表示迷宫
? 建立栈，利用栈实现深度优先搜索
2) 利用队列宽度优先进行迷宫求解。
? 用数组表示迷宫
? 建立队列，利用队列实现宽度优先搜索
二、需求分析
利用栈的结构，走过的路入栈，如果不能走出栈，采用遍历法，因此栈内存储的数据就是寻一条路径。
当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。
三、详细设计
（1）基本代码
struct item
{
int x ; //行
int y ; //列
} ;
item move[4] ;
（2）代码
栈构造函数：
void seqstack::Push(int x,int y,int d) //入栈
{
if(top>=StackSize-1)throw"上溢";
top++;
data[top].d=d;
data[top].x=x;
data[top].y=y;
}
寻找路径：
int seqstack::findpath(int a,int b)
{
item move[4]={{0,1},{1,0},{0,-1},{-1,0}};//定义移动结构
int x, y, d, i, j ;
Push(a,b,-1); //起点坐标入栈
while(top!=-1)
{
d=data[top].d+1;
x=data[top].x;
y=data[top].y;
Pop(); //出栈
while (d<4) //方向是否可以移动
{
i=x+move[d].x ; j=y+move[d].y ; //移动后坐标
if(Map[i][j]==0) //是否能移动
{
Push(x,y,d); //移动前坐标入栈
x=i;
y=j;
Map[x][y]= -1 ;
if(x==m&&y==n) //判断是否为终点坐标
{
Push(x,y,-1);
return 1 ;
}
else d=0 ;
}
else d++ ;
}
}
return 0;
}
（3）伪代码
a)栈初始化;
b)将入口点坐标及到达该点的方向（设为-1）入栈
c)while (栈不空)
{
栈顶元素＝（x , y , d）
出栈 ;
求出下一个要试探的方向d++ ;
while （还有剩余试探方向时）
{ if （d方向可走）
则 { （x , y , d）入栈 ;
求新点坐标 (i, j ) ;
将新点（i , j）切换为当前点（x , y） ;
if ( (x ,ｙ)= =(ｍ,n) ) 结束 ;
else 重置 d=0 ;
}
else d++ ;
}
}
（4）时间复杂程度
时间复杂程度为O（1）
2.3 其他
在运行时可选择是否自己构造地图，实现函数如下：
void creatmap() //自创地图函数
{
for(int i=1;i<9;i++)
{
for(int j=1;j<9;j++)
Map[i][j]=0;
}
Map[8][9]=1;
printmap();
cout<<"请设置障碍物位置:（x,y）。(0,0)结束"<<endl;
int p,q;
while(1)
{
cin>>p>>q;
if(p==0&&q==0)
{
cout<<"设置完成"<<endl;
break;
}
if(p<=0||q<=0||p>=9||q>=9)
{
cout<<"输入错误！"<<endl;
}
else Map[p][q]=1;
cout<<"继续输入："<<endl;
}
cout<<endl;
cout<<"请设置终点位置:"<<endl;
cin>>q>>p;
m=p;n=q;
Map[m][n]=0;
}
五、遇到的问题及解决办法
最初程序编写时不知道怎么实现适用于任何迷宫，后来采取了适当的方式，可以自定义迷宫；由于编程不熟练，开始不知道怎么用栈实现，经过查资料并与同学探讨，清楚了它的结构原理；另外还有很多标识符使用的小问题，经反复调试后终于得到了解决。
六、心得体会
编程不是一朝一夕的事，还是熟能生巧，所以一定要多编多练，扎实基础，还要多向别人请教。另外，这次实验使我熟悉了链栈的特点和各种操作，并且体会到了其在实际运用中的重要性。同时，由于这个问题需要考虑多种情况，逻辑上比较复杂，在编写算法的过程中锻炼了我的逻辑思维能力和考虑问题的周密性。
七、附录
运行结果截图。
第二篇：[栈及队列的操作]数据结构实验报告C语言源码
课程名称 数据结构
实验项目名称 栈和队列
（一）实验目的和要求；
熟练掌握栈及队列基本操作的实现
（二）实验主要内容；
（1） 建立栈并进行元素（8，9，5，4）入栈，实现链栈的建立及入栈的基本操作；
（2） 实现元素（9，5）的出栈，实现链栈的出栈的操作；
（3） 建立链队列，并实现元素(4,5,7,6,8)入队，实现链队列的建立，和入队的基本操作；
（4） 实现元素(4,5,7,6,8)出队，实现链队列的出队的基本操作
（三）主要仪器设备
计算机，VC++高级程序语言
（四）实验原理
栈的修改时按照先进后出的原则进行的，试验中用到构造空栈，及入栈出栈操作。队列是一种先进先出的线性表，只允许在表的一端插入，而在另一端删除元素，试验中构造队并且入队出队。
（五）实验步骤及调试分析；
根据课本基本操作写好源程序，基本操作在书本中已经给出，写出主函数，调试分析程序，找出错误，并修改后程序能够运行并得出正确输出。试验中，有些小错误经常犯，比如符号，函数声明等。
（六）实验结果及分析；
实验结果如下：
能够按照实验要求得出正确结果
（七）附录：源程序
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int elemtype;
typedef int status;
typedef struct QNode{
elemtype data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
typedef struct lnode {
elemtype data;
struct lnode *next;
}stacknode, *linkstack;
status initstack(linkstack top) {
top->next = NULL;
}
status isempty(linkstack top) {
if(top->next == NULL) return OK;
return ERROR;
}
status push(linkstack top, elemtype e) {
stacknode *p;
p= (stacknode *)malloc(sizeof(stacknode));
if(p == NULL) return ERROR;
p->data = e;
p->next = top->next;
top->next = p;
return OK;
}
status pop(linkstack top, elemtype *e) {
if(isempty(top)) return ERROR;
stacknode *p = top->next;
*e = p->data;
top->next = p->next;
free(p);
return OK;
}
status shstack(linkstack top){
stacknode *p;
p= (stacknode *)malloc(sizeof(stacknode));
p->next=top->next;
while(p->next!=NULL){
printf("%d ",p->next->data);
p->next=p->next->next;
}
return OK;
}
status initqueue(LinkQueue *q){
(*q).front=(*q).rear=(QueuePtr)malloc(sizeof(QNode));
if (!(*q).front) exit(OVERFLOW);
(*q).front->next=NULL;
return OK;
}
status enqueue(LinkQueue *q,elemtype e){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*q).rear->next=p;
(*q).rear=p;
return OK;
}
status dequeue(LinkQueue *q,elemtype *e){
if((*q).front==(*q).rear) return ERROR;
QueuePtr p;
p=(*q).front->next;
*e=p->data;//注意
(*q).front->next=p->next;
if((*q).rear==p) (*q).rear==(*q).front;
free(p);
return OK;
}
void main()
{
linkstack s;
s=(linkstack)malloc(sizeof(stacknode));
initstack(s);
printf("进入栈的4个元素依次为：\n");
for (int i=0;i<4;i++)
{
elemtype a;
scanf("%d",&a);
push(s,a);
}
printf("\n栈顶到栈底的元素依次为；\n");
shstack(s);
elemtype b,c,d;
pop(s,&b);
pop(s,&c);
pop(s,&d);
push(s,b);
printf("\n\n出栈的元素为:");
printf("%d",c);
printf(" %d\n",d);
printf("\n现在栈中的元素为：");
shstack(s);
LinkQueue q;
initqueue(&q);
elemtype a;
printf("\n\n\n请输入5个进队的元素:\n");
for(int i=0;i<5;i++)
{
scanf("%d",&a);
enqueue(&q,a);
}
printf("\n元素的出列为:\n");
for(int i=0;i<5;i++)
{
elemtype e;
dequeue(&q,&e);
printf(" %d",e);
}
}