文档介绍：数据结构实验内容 栈和队列
栈和队列魔王语言解释
一、问题描述:有一个魔王总是使用自己的一种非常精练而抽象的语言讲话,没有人能听得懂,但他的语言是可以逐步解释***能听懂的语言,因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的;
α→β1β2…βm
(θδ1δ2…δn)→θδnθδn-1…θδ1θ
在这两种形式中,从左到右均表示解释。试写一个魔王语言的解释系统,把他的话解释***能听得懂得话。
栈和队列魔王语言解释
基本要求:用下述具体规则和上述规则形式2实现。设大写字母表示魔王语言的词汇;小写字母表示人的语言词汇;希腊字母表示可以用大写字母或小写字母代换得变量。魔王语言可含人的词汇。
B→tAdA
A→sae
测试数据:
B(einxgz)B解释成tsaedsaeezegexeneietsaedsae;
若将小写字母与汉字建立下表对应关系,则魔王说的话是:“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。
t
d
s
a
e
z
g
x
n
i
天
地
上
一只
鹅
追
赶
下
蛋
恨
栈和队列魔王语言解释
实验提示:将魔王的语言自右至左进栈,总是处理栈顶字符。若是开括号,则逐一出栈,将字母顺序入队列,直至闭括号出栈,并按规则要求逐一出队列再处理后入栈。其他情形较简单,请思考应如何处理。应首先实现栈和队列的基本操作。
由于问题的特殊性,可以实现栈和队列的顺序存储空间共享
代换变量的数目不限,则在程序开始运行时首先读入一组第一种形式的规则,而不是把规则固定在程序中(第二种形式的规则只能固定在程序中)
选作内容:
栈和队列马踏棋盘
二、问题描述:设计一个国际象棋的马踏遍棋盘的演示程序。
基本要求:将马随机放在国际象棋8x8棋盘Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。编制非递归程序,求出马的行走路线,并按求出的行走路线,将数字1,2,…,64依次填入一个8x8的方阵,输出之。
测试数据:由自己制订。可自行指定一个马的初始位置(i,j),0<=i,j<=7。
栈和队列马踏棋盘
实现提示:下图显示了马位于方格(2,3)时,8个可能的移动位置。一般来说,当马位于位置(i,j)时,可以走到下列8个位置之一。
( i-2,j+1), ( i-1,j+2), ( i+1,j+2), ( i+2,j+1)
( i+2,j-1), ( i+1,j-2), ( i-1,j-2), ( i-2,j-1)
8
1
7
2
H
6
3
5
4
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
栈和队列马踏棋盘
但是,如果( i,j)靠近棋盘的边缘,上述有些位置可能超出棋盘范围,成为不允许的位置。8个可能位置可以用两个一维数组HTry1[0..7]和HTry2[0..7]来表示:
0 1 2 3 4 5 6 7
-2
-1
1
2
2
1
-1
-2
HTry1
0 1 2 3 4 5 6 7
1
2
2
1
-1
-2
-2
-1
HTry2
位于( i,j)的马可以走到的新位置是在棋盘范围内的(i+HTry1[h] ,j+HTry2[h]),其中h=0,1,…,7。
每次在多个可走位置中选择其中一个进行试探,其余未曾试探过的可走位置必须用适当结构妥善管理,以备试探失败时的“回溯”(悔棋)使用。
求出从某一起点出发的多条以至全部行走路线。
探讨每次选择位置的“最佳策略”,以减少回溯的次数。
演示寻找行走路线的回溯过程。
选作内容:
栈和队列马踏棋盘
栈和队列迷宫问题
三、问题描述:以一个m*n的方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得到没有通路的结论。
基本要求:首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序;求得的通路以三元组(i,j,d)的形式输出,其中: (i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列数据的迷宫,输出的一条通路为:(1,1,1), (1,2,2), (2,2,2), (3,2,3), (3,1,2),…. 。
栈和队列迷宫问题
测试数据:迷宫的测试数据如下:左上角(1,1)为入口,右下角(8,9)为出口。
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
0
0
0
1
0
0
0
0
0