以下验证性实验都做
（1）顺序栈
● 顺序栈的C语言描述
● 基本运算的算法——置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满
（2）链栈
● 链栈的C语言描述
● 基本运算的算法——置空栈、判栈空、进栈、出栈、读栈顶
（3）循环队列
● 循环队列的C语言描述
● 基本运算的算法——置空队、判队空、进队、出队、读队头元素、输出循环队列
（4）链队列
● 链队列的C语言描述
● 基本运算的算法——置空队、判队空、进队、出队、读队头元素
以下设计性实验都做
（1）迷宫问题
问题描述
这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。
简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。
图1 迷宫示意图
迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。
基本要求
● 设计迷宫的存储结构。
● 设计通路的存储结构。
● 设计求解通路的算法。
● 设计迷宫显示和通路的显示方式。
● 输入：迷宫、入口及出口可在程序中设定，也可从键盘输入。
● 输出：迷宫、入口、出口及通路路径。
实现提示
● 存储设计
迷宫：以一个m×n的数组表示迷宫，如图3所示。数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。
图2 迷宫存储示意图
方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把东、南、西、北依次编号为0、1、2、3.其增量数组move[4]如图3所示。
图3 数组move[4]
通路：通路上的每一个点有3个属性：一个横坐标属性x、一个列坐标属性y和一个方向属性d，表示其下一点的位置。如果约定尝试的顺序为东、南、西、北，则每尝试一个方向不通时，d值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。
● 算法设计
要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步，重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。
寻找通路的算法思想如下：
Setp1：入口点坐标及到达该点方向（设为-1）入栈。
Step2：当栈不空时循环执行下列操作：
2.1 栈顶元素出栈至（x,y,d）。
2.2 按预设定顺序求出下一个要试探的方向d++，执行下述操作：
2.2.1 如果方向d可走，则：
2.2.1.1 将（x,y,d）入栈。
2.2.1.2 求新点坐标，得新（x,y）。
2.2.1.3 如果新点（x,y）是终点，则试探结束；否则，置d=0。
2.2.2 否则，试探下一个方向，d++。
Setp3：栈空，表示没有通路；否则，出栈，得到通路路径。
测试与运行
● 当迷宫数组为图3所示时，（1,1）为入口，（4,6）为出口，则可能的通路为：通路1：（1,1）、（1,2）、（2,2）、（3,2）、（4,2）、（4,3）、（4,4）、（4,5）、（4,6）通路2：（1,1）、（1,2）、（2,2）、（2,3）、（2,4）、（3,4）、（4,4）、（4,5）、（4,6）通路3：（1,1）、（1,2）、（2,2）、（2,3）、（2,4）、（2,5）、（2,6）、（3,6）、（4,6）
● 重设迷宫，使得没有通路，进行测试。
思考
● 若每个点有8个试探方向（东、东南、南、西南、西、西北、北、东北），如何修改程序？
● 如何求得所有通路？
● 如何求得最短通路？
（2）火车车厢重排问题
问题描述
一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1～n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。
车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。
基本要求
● 设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨；
● 设计并实现车厢重排算法；
● 分析算法的时间性能。
设计思想
假设有3个缓冲轨，入轨中有9节车厢，次序为5,8,1,7,4,2,9,6,3，重排后，9节车厢出轨次序为9,8,7,6,5,4,3,2,1。重排过程如下：
3号车厢不能直接移至出轨（因为1号车厢和2号车厢必须排在3号车厢之前），因此，把3号车厢移至H1。6号车厢可放在H1中3号车厢之后（因为6号车厢将在3号车厢之后出轨）。9号车厢可以继续放在H1中6号车厢之后，而接下来的2号车厢不能放在9号车厢之后（因为2号车厢必须在9号车厢之前出轨）。因此，应把2号车厢移至H2，4号车厢可以放在H2中2号车厢之后，7号车厢可以继续放在4号车厢之后，如图4所示。至此，1号车厢可通过H3直接移至出轨，如图5所示。由于5号车厢此时仍在入轨中，所以把8号车厢移动至H2，这样就可以把5号车厢直接从入轨移至出轨，如图6所示。此后，可依次从缓冲轨中移出6号、7号、8号和9号车厢，如图7所示。
图4 将369、247依次入缓冲轨
图5 将1移至出轨，234移至出轨
图6 将8入缓冲轨，5移至出轨
图7 将6789移至出轨
由上述重排过程可知：在把车厢c移至缓冲轨时，车厢c应移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于c；如果有多个缓冲轨满足这一条件，则选择队尾车厢编号最大的缓冲轨；否则选择一个空的缓冲轨。
思考
● 如果缓冲轨按后进先出的方式工作，即用栈表示缓冲轨，应如何解决火车车厢重排问题？
以下综合性实验都做
（1）表达式求值问题
问题描述
表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。
基本要求
● 从文件或键盘读入中缀表达式。
● 设计操作数为多位整数，操作符为加、减、乘、除、求模的中缀表达式求值算法。
● 设计将中缀表达式转换为后缀表达式的算法。
● 设计将中缀表达式转换为前缀表达式的算法。
● 设计后缀表达式求值算法。
● 设计前缀表达式求值算法。
● 输出各种形式的表达式。
设计要点提示
● 算数表达式的计算往往是通过栈来实现的。
● 读入或扫描表达式的同时，完成运算符和操作数的识别处理。
● 识别操作数时，注意将其字符序列转换成整数（如：‘15’→15）或实数（如：‘15.4’ →15.4）形式进行存储。
● 可以将表达式转换成一棵二叉树，通过先序、中序、后序遍历得到前缀、中缀、后缀表达式。
● 仿表1来构建测试用例。
表1 表达式计算测试用例示例
（2）任务调度
问题描述
多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。
● 忽略任务提交的时间差，即认为各任务同时提交。
● 各任务不同时提交。
基本要求
● 为任务列表设计数据结构和存储结构。
● 任务输入，至少包括任务编号及所需CPU的服务时间，任务数不得少于5个。
● 如果按提交顺序执行，求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间。
● 按平均等待时间最短，设计任务调度算法，输出任务的执行序列；求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间；并把结果与上一时间对比。
设计要点提示
● 为使各任务平均等待时间最短，如果忽略任务提交的时间差，调度时应该按短任务优先进行调度，即：按照各任务需要CPU服务时间的长短，确定执行顺序，短的在前，长的在后。例：任务列表2如下，则执行序列如表3所示。
表2 任务列表
表3 任务执行序列
● 根据上一问题的分析，需要根据任务列表，按任务的CPU服务时间进行排序。
● 如果考虑任务提交的时间差，应该按“最短剩余时间”优先进行调度。调度发生在每次任务提交时，从未完成任务中选择需要CPU时间最短的任务。例：任务提交情况如表4所示。
表4 任务列表
0时刻，只有P1，所以运行P1。
1s时，P2提交，此时，P2需要CPU服务时间为4，P1还需7，则暂停P1，先运行P2。
2s时，P3提交，此时，P1、P2、P3各自需CPU服务时间为：7、3、12，所以继续运行P2。
依次类推，直至所有任务完成。
思考
● 最短作业优先，存在“长任务饥饿”的问题，即如果动态地不断加入作业，只要提交作业所需要的CPU服务时间比较短，则先提交的长任务将一直得不到服务，如何解决该问题？
本文来源：https://www.2haoxitong.net/k/doc/7672b46d58fafab069dc026a.html
文档为doc格式