《实验2 栈和队列的应用》由会员分享，可在线阅读，更多相关《实验2 栈和队列的应用（6页珍藏版）》请在金锄头文库上搜索。
1、学时：4学时（两次）,时间：第5周 周三（1-2） 第5周 周五（3-4） 地点：图书馆1楼基础实验室,内容：1、算术表达式求值（带括号）； 2、魔王语言；,3、马踏棋盘、迷宫问题（选择）,数 据 结 构,实验2 栈和队列的应用,魔王语言,问题描述： 魔王总是使用自己的一种非常精炼而抽象的语言讲话，没有人能听懂，但他的语言是可以逐步解释成人能听懂的语言的，因为它的语言是由以下两种形式的规则由人的语言逐步抽象上去的： (1) 12 n (2)(12 n)nn-1 1 在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把它的话解释成人能听懂的话。,例如： (1) BtAdA (2)
2、Asae,B(ehnxgz)B,=tsaedsae tsaedsae,ezegexenehe,若将小写字母与汉字建立下表对应关系，,魔王语言,则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。,马踏棋盘,设计一个国际象棋的马踏遍棋盘的演示程序。,将马随机放在国际象棋8x8棋盘Board88的某个 方格中，马按走棋规则进行移动。要求每个方格只 进入一次，走遍棋盘上全部64个方格。编制非递归 程序，求出马的行走路线，并按求出的行走路线， 将数字1,2,64依次填入一个8x8的方阵，输出之。,可自行指定一个马的初始位置（i,j)。（0=i,j=7）,下图显示了马位于
3、方格（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）,每次在多个可走位置中选择其中一个进行试探，其余 未曾试探过的可走位置必须用适当结构妥善管理，以 备试探失败时的“回溯”（悔棋）使用。,迷宫问题,以一个mn的方阵表示迷宫，0和1分别表示迷宫中 的通路和障碍。设计一个程序，对任意设定的迷宫， 求出一条从入口到出口的通路，或得到没有通路的结论。,用二维数组存储迷宫数据，通常设定入口点的下标为（1,1）,出口点的下标为(m,n)。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。,以三元组（i,j,d)的形式输出，其 中： （i,j)指示迷宫中的一个坐标， d表示走到下一坐标的方向。如： 对于下列数据的迷宫，输出的一条 通路为：(1,1,1)， (1,2,2)，. 。,
