《实验二栈和队列应用》由会员分享，可在线阅读，更多相关《实验二栈和队列应用（17页珍藏版）》请在金锄头文库上搜索。
1、LOGO数据结构实验数据结构实验二 栈和队列应用v实验题目 1.算术表达式求值 问题描述由输入的四则算术表达式字符串，动态生成算术表 达式所对应的后缀式，通过后缀式求值并输出。数据结构 v实验题目 1.算术表达式求值 实验要求 十进制整数四则运算计算器。 1)采用顺序栈等数据结构，可以将数据存储在顺序表中。 2)给定表达式字符串，后缀表达式。 3)对后缀表达式求值并输出。数据结构 v实验题目 2.停车场管理 问题描述设停车场采用南北方向的双口，每个口都有一个入 口和出口。另外停车场入口处各有一个单车道的等候 通道，并允许等候的车辆因急事从等候通道直接开走 。数据结构 v实验题目 2.停车场管理
2、 实验要求 设计停车场模拟管理程序。 1)采用栈或队列等数据结构。 2)等候车辆的管理。 3)停车位的管理。数据结构 v实验题目 3.运动员混合双打组合 问题描述设有M个男羽毛球运动员和N个女羽毛球运动员，现 进行男女混合双打组合K轮配对。男女运动员分别编号 排队在等候队列，按顺序依次从男女运动员中各出队1 人组合配对。本轮没成功配对者等待下一轮次配对。数据结构 v实验题目 3.运动员混合双打组合 实验要求 设计程序模拟完成运动员组合配对过程。 1)采用队列等数据结构。 2)输出每轮的配对信息。数据结构 v实验题目 4.电路布线问题 问题描述印刷电路板将布线区域划分为nn个方格阵列。在布 线时
3、，电路只能沿直线或直角布线。为避免线路相交， 已布线的方格要做封锁标记。设起始位置为a，终止位 置为b，求解电路布线问题。数据结构 v实验题目 4.电路布线问题 实验要求 设计印刷电路板的布线模拟程序。 1)采用栈或队列等数据结构。 2)采用穷举法的回溯搜索，求a到b可能的布线线路。 3)推荐采用层次优先搜索，求a到b最优的布线线路。数据结构 v实验题目 5.迷宫问题 问题描述 设一个MN的迷宫，0和1分别表示通道和障碍。实验要求 设计程序实现求从入口到出口的任意通道。 1)采用栈等数据结构。 2)应用穷举法回溯策略求解。 3)尝试求解所有通路或最佳路径。数据结构 v实验题目 6.车厢调度 问
4、题描述 假设停在铁路调度入口处的列车编号依次为1,2,n。 实验要求 设计程序求出所有可能的长度为n的输出车厢序列。 1)采用栈或队列等数据结构。 2)输出调度序列。 3)推荐采用双栈结构求解。数据结构 v实验题目 7.八皇后问题 问题描述设一个88的棋盘里放置8个皇后，要求在每行、每 列、没斜线只允许放置1个皇后。 实验要求 设计实现所有可能解的程序。 1)采用栈等数据结构。 2)应用穷举法回溯策略求解。 3)尝试采用递归和非递归算法求解。数据结构 v实验题目 8.马踏棋盘问题 问题描述中国象棋中的“马”走子的规则是：马走日字形。 实验要求设计实现求象棋盘中的某一点出发踏遍棋盘所有点 的程序
5、。 1)采用栈等数据结构。 2)应用穷举法回溯策略求解。 3)尝试求解所有出发点的可能 解。数据结构 v实验题目 9.简单背包问题 问题描述设一个背包所允许的重量是M，假设有N件物品， 物品的重量分别是Wi，可以任意挑选物品将背包装满。数据结构 v实验题目 9.简单背包问题 实验要求 设计程序实现将给定背包装满的可能解。 1)采用栈等数据结构。 2)应用穷举法回溯策略求解。 3)尝试采用递归和非递归算法求解。数据结构 v实验题目 10. 公交车站台排队问题 问题描述假设某公交车站站点有4路公交车都可以到达某商 业区，人们排队等候上车。现要调研统计每天每路公交 车的乘客平均人数和等候时间。数据结构 v实验题目 10.公交车站台排队问题 实验要求 设计程序模拟公交车的乘客运营情况。 1)采用线性表等数据结构。 2)可随机产生乘客到达车站的时间和等候时间。 3)设每路公交车都按规定时间运营。 4)可以简化给定条件。
