实验二栈和队列应用

1、LOGO 数据结构实验数据结构实验数据结构数据结构 实验二实验二 栈和队列应用栈和队列应用v实验题目实验题目1.算术表达式求值问题描述问题描述 由输入的四则算术表达式字符串，动态生成算术表达式所对应的后缀式，通过后缀式求值并输出。数据结构数据结构 v实验题目实验题目1.算术表达式求值实验要求实验要求十进制整数四则运算计算器。1)采用顺序栈等数据结构，可以将数据存储在顺序表中。2)给定表达式字符串，后缀表达式。3)对后缀表达式求值并输出。数据结构数据结构 v实验题目实验题目2.停车场管理问题描述问题描述 设停车场采用南北方向的双口，每个口都有一个入口和出口。另外停车场入口处各有一个单车道的等候通

2、道，并允许等候的车辆因急事从等候通道直接开走。数据结构数据结构 v实验题目实验题目2.停车场管理实验要求实验要求设计停车场模拟管理程序。1)采用栈或队列等数据结构。2)等候车辆的管理。3)停车位的管理。数据结构数据结构 v实验题目实验题目3.运动员混合双打组合问题描述问题描述 设有M个男羽毛球运动员和N个女羽毛球运动员，现进行男女混合双打组合K轮配对。男女运动员分别编号排队在等候队列，按顺序依次从男女运动员中各出队1人组合配对。本轮没成功配对者等待下一轮次配对。数据结构数据结构 v实验题目实验题目3.运动员混合双打组合实验要求实验要求设计程序模拟完成运动员组合配对过程。1)采用队列等数据结构。

3、2)输出每轮的配对信息。数据结构数据结构 v实验题目实验题目4.电路布线问题问题描述问题描述 印刷电路板将布线区域划分为nn个方格阵列。在布线时，电路只能沿直线或直角布线。为避免线路相交，已布线的方格要做封锁标记。设起始位置为a，终止位置为b，求解电路布线问题。数据结构数据结构 v实验题目实验题目4.电路布线问题实验要求实验要求设计印刷电路板的布线模拟程序。1)采用栈或队列等数据结构。2)采用穷举法的回溯搜索，求a到b可能的布线线路。3)推荐采用层次优先搜索，求a到b最优的布线线路。数据结构数据结构 v实验题目实验题目5.迷宫问题问题描述问题描述设一个MN的迷宫，0和1分别表示通道和障碍。实验

4、要求实验要求设计程序实现求从入口到出口的任意通道。1)采用栈等数据结构。2)应用穷举法回溯策略求解。3)尝试求解所有通路或最佳路径。数据结构数据结构 v实验题目实验题目6.车厢调度问题描述问题描述假设停在铁路调度入口处的列车编号依次为1,2,n。实验要求实验要求设计程序求出所有可能的长度为n的输出车厢序列。1)采用栈或队列等数据结构。2)输出调度序列。3)推荐采用双栈结构求解。数据结构数据结构 v实验题目实验题目7.八皇后问题问题描述问题描述 设一个88的棋盘里放置8个皇后，要求在每行、每列、没斜线只允许放置1个皇后。实验要求实验要求设计实现所有可能解的程序。1)采用栈等数据结构。2)应用穷举

5、法回溯策略求解。3)尝试采用递归和非递归算法求解。数据结构数据结构 v实验题目实验题目8.马踏棋盘问题问题描述问题描述 中国象棋中的“马”走子的规则是：马走日字形。实验要求实验要求 设计实现求象棋盘中的某一点出发踏遍棋盘所有点的程序。1)采用栈等数据结构。2)应用穷举法回溯策略求解。3)尝试求解所有出发点的可能 解。数据结构数据结构 v实验题目实验题目9.简单背包问题问题描述问题描述 设一个背包所允许的重量是M，假设有N件物品，物品的重量分别是Wi，可以任意挑选物品将背包装满。数据结构数据结构 v实验题目实验题目9.简单背包问题实验要求实验要求设计程序实现将给定背包装满的可能解。1)采用栈等数据结构。2)应用穷举法回溯策略求解。3)尝试采用递归和非递归算法求解。数据结构数据结构 v实验题目实验题目10. 公交车站台排队问题问题描述问题描述 假设某公交车站站点有4路公交车都可以到达某商业区，人们排队等候上车。现要调研统计每天每路公交车的乘客平均人数和等候时间。数据结构数据结构 v实验题目实验题目10.公交车站台排队问题实