ds实验教案3
- 格式:doc
- 大小:38.50 KB
- 文档页数:2
数据结构教案(供本科学生使用)
1--1
实验三:栈和队列的应用
一、实验目的
(1)熟练掌握栈或队列在实际系统中的应用
(2)掌握栈和队列在顺序和链式存储结构下的插入、删除算法
(3)充分体会在程序设计中数据的重要作用,学会在程序设计中运用栈或队列的
相关知识解决问题。
二、实验内容
1:迷宫求解
问题描述:
以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。
试设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有
通路的结论。
基本要求
首先实现以顺序表或链表作存储结构的栈类型,然后编写一个求解迷宫的程
序。求得的通路以三元(i,j,d)的形式输出,其中:(i,j)指出迷宫中的一个坐
标,d表示走到下一个坐标的方向。
测试数据: 0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
实现提示:
1、
可以二维数组mg存储迷宫数据,通常设定入点的下标为(1,1),出口点的下
标为(m,n)。为处理方便起见,可在迷宫的四周加一圈障碍。对于迷宫中的任
一位置,均可约定有东西南北四个方向可通。
2、
四个方向依次为东南西北,其下标(或坐标)的变化:
mx[1]=0;my[1]=1;(东)
mx[2]=1;my[2]=0;(南)
mx[3]=0;my[3]=-1;(西)
mx[4]=-1;my[4]=0;(北)
3、
留下足迹
Status FootPrint(PosType e){
int i,j;
i=e.x;
j=e.y;
mg[i][j]=-1;
return ok;}
2:表达式求值问题
问题描述:
求一个数学表达式的值:用户输入一个包含正整数、括号和四则运算
符(“+”、 “—”、 “*”、 “/”)的算术表达式,计算其结果。
设计分析:
首先置操作数栈为空栈,表达式起始符“#”为运算符栈底元素;依
次读入表达式中每个字符,若是操数则进操作数栈,若是操作符则和操作符栈顶的
运算符进行比较优先权后作相应的操作,直到整个表达式求值完毕(即操作符栈顶
元素和当前读入的字符均为“#”)。
结点结构类型描述如下:
typedef struct
{ char *base,*top;
int stacksize;
}sqstack;