数据结构实验报告
实验名称： 实验2——题目3
学生姓名：
班 级：
班内序号：
学 号：
日 期： 20##年11月17日
1． 实验要求
1.实验目的
通过选择下面五个题目之一进行实现，掌握如下内容：
· 进一步掌握指针、模板类、异常处理的使用
· 掌握栈的操作的实现方法
· 掌握队列的操作的实现方法
· 学习使用栈解决实际问题的能力
· 学习使用队列解决实际问题的能力
2 .实验内容
利用栈结构实现迷宫求解问题。迷宫求解问题如下：
心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。
提示：
1、可以使用递归或非递归两种方法实现
2、老鼠能够记住已经走过的路，不会反复走重复的路径
3、可以自己任意设置迷宫的大小和障碍
4、使用“穷举求解”的方法
2. 程序分析
2.1 存储结构
存储结构：顺序栈
data data data
top
top
top
（1）空栈 (2)A1A2入栈 (3)A3出栈
2.2 关键算法分析
1.试探方向：
（1）基本思想
每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move [ 4 ]中，在move 数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。
增量move数组
（2）基本代码
struct item
{
int x ; //行
int y ; //列
} ;
item move[4] ;
2.寻找路径
（1） 基本思想：
利用栈的结构，走过的路入栈，如果不能走出栈，采用遍历法，因此栈内存储的数据就是寻一条路径。
当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。
（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;
}
3. 程序运行结果
1.主函数流程
是
否
否
是
2.测试条件
当构造的迷宫符合要求，出入的起点正确则能输出正确路径
3.测试结果
4. 总结
最初程序编写时不知道怎么实现适用于任何迷宫，后来采取了适当的方式，可以自定义迷宫；由于编程不熟练，开始不知道怎么用栈实现，经过查资料并与同学探讨，清楚了它的结构原理；另外还有很多标识符使用的小问题，经反复调试后终于得到了解决。
编程不是一朝一夕的事，还是熟能生巧，所以一定要多编多练，扎实基础，还要多向别人请教。另外，这次实验使我熟悉了链栈的特点和各种操作，并且体会到了其在实际运用中的重要性。同时，由于这个问题需要考虑多种情况，逻辑上比较复杂，在编写算法的过程中锻炼了我的逻辑思维能力和考虑问题的周密性。
下一步需要改进的是思考如何将复杂的算法简化，程序时间复杂度还有待降低，并且采用队列与树可以实现求解最小路径的算法。
第二篇：数据结构实验二：栈和队列的应用
数据结构实验报告
实验二 栈和队列的应用
一、 实验目的：
1．深入了解栈和队列的特性；
2．熟练掌握栈和队列的存储结构及实现方式
二、 实验要求：
1．C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．写出算法设计小结和心得。
三、 实验内容：
1．用栈实现：识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。
2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列等操作。
四、 程序源代码：
1、#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define EMPTY 0
#define FULL 10000
#define MAX 10000
typedef char data;
typedef struct elem {
data d;
struct elem *next;
}elem;
typedef struct stack {
int cnt;
elem *top;
}stack;
void initialize(stack *stk);
void push(data d, stack *stk);
data pop(stack *stk);
bool empty(const stack *stk);
bool full(const stack *stk); //栈操作函数
void initialize(stack *stk)
{
stk->cnt = 0;
stk->top = NULL;
}
bool empty(const stack *stk)
{
return stk->cnt == EMPTY;
}
bool full(const stack *stk)
{
return stk->cnt == FULL;
}
void push(data d, stack *stk)
{
elem *p;
if (!full(stk))
{
p = (elem *)malloc(sizeof(elem));
p->d = d;
p->next = stk->top;
stk->top = p;
stk->cnt++;
}
}
data pop(stack *stk)
{
data d;
elem *p;
if(!empty(stk))
{
d = stk->top->d;
p = stk->top;
stk->top = stk->top->next;
stk->cnt--;
free(p);
}
return d;
}
int main(void)
{
data input[MAX];
stack temp;
int i = 0;
int flag = 0;
initialize(&temp);//初始化临时栈
printf("输入字符串:\n");
scanf("%s", &input); //输入字符串
while (input[i] != '@')//字符串入栈
{
push(input[i], &temp);
i++;
}
while (!empty(&temp))//字符依次出栈和字符数组比较，判断是否符合“序列1&序列2@”形式
{
if (temp.top->d == input[flag])
{
pop(&temp);
flag++;
}
else
{
printf("此字符序列不符合“序列1@序列2@”形式\n");
break;
}
}
if (empty(&temp))
printf("此字符序列符合“序列1@序列2@”形式\n");
return 1;
}
2、#include "iostream.h"
typedef int ElmeType;
struct Node
{
ElmeType date;
Node* next;
};
typedef Node Queue;
void InitQueue(Queue* &rear)//InitQueue对队列进行初始化
{
rear->date=-1;
rear->next=rear;
}
void InQueue(Queue* &rear,ElmeType e)//入列
{
Queue* p=new Queue;
p->date=e;
if (rear->next==rear)
{
p->next=rear;
rear->next=p;
rear=p;
}
else
{
p->next=rear->next->next;
rear->next->next=p;
}
cout<<"插入"<<e<<endl;
}
ElmeType Outqueue(Queue* &rear)//出列
{
if (rear->next==rear)
{
cout<<"队列空"<<endl;
return NULL;
}
Queue* p=rear;
while (p->next!=rear)
p=p->next;
ElmeType e=rear->date;
p->next=rear->next;
delete rear;
rear=p;
return e;
}
void show(Queue* rear)//队列的输出
{
Queue* p=rear->next;
p=p->next;
while (p->date!=-1)
{
cout<<p->date<<" ";
p=p->next;
}
cout<<endl;
}
void main()
{
Queue s;
Queue* rear=&s;
InitQueue(rear);
show(rear);
InQueue(rear,12);
InQueue(rear,96);
InQueue(rear,23);
InQueue(rear,56);
InQueue(rear,6);
InQueue(rear,8);
show(rear);
ElmeType e;
e=Outqueue(rear);
cout<<"出队队尾元素："<<endl<<e<<endl;
e=Outqueue(rear);
cout<<e<<endl;
e=Outqueue(rear);
cout<<e<<endl;
e=Outqueue(rear);
cout<<e<<endl;
show(rear);
}
五、 测试结果
1、
2、
六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）
本次实验是对栈和队列的初步应用，实现了栈和队列的初始化、出入栈、出入队列等的基本操作。通过以实验的形式编写代码来实现栈和队列的各种应用及操作，我们对于课本上的基本算法从能够看懂变成能够写出来，进一步加深了对各种基本的算法的理解，对于以后的学习也打好了基础。