实验二栈和队列应用分析.ppt

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