c语言栈和队列精讲

《c语言栈和队列精讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单元实验三------栈和队列题目（基本要求：三选一）后缀表达式求值（栈的应用）离散事件模拟（队列的应用）*括号匹配问题（栈的应用）表达式的三种表示方法设S1与S2进行OP运算则OPS1S2为前缀表示法（波兰表示法）S1OPS2为中缀表示法S1S2OP为后缀表示法（逆波兰表示法）例如，表达式a+b*(c–d)–e/f的后缀式为abcd–*+ef/–题目后缀表达式求值abcd–*+ef/–bacdbat1t2at1=c–dt2=b*t1t3=a+t2t3et3ft4=e/ft4t3t5t5=t3–t4––*+/题目后缀表达式求值

2、使用栈，用于保存操作数和计算结果难点：表达式以字符串方式表示，需要从字符串中分解出每个操作数和运算符。思路：字符串中的空格分隔了操作数和运算符，因此，从左至右扫描字符串，遇到空格时暂停，取出操作数（从串转换为数）或运算符（一个字符），若是操作数则入栈，若是运算符，则从栈顶弹出操作数进行相应的运算，结果再入栈；重复以上过程，直到表达式结束。题目-后缀表达式求值算法输入：合法的后缀表达式（仅包含二元的算术运算符号+、-、*、/，操作数为整数），以字符串形式存在字符数组中输出：表达式的值步骤：1）构造一个空栈（用于存放操作数及结果）

3、；2）表达式是否结束？若是，则转4）；否则转3）；3）从表达式中截取一个符号，若是操作数，则入栈；若是运算符，则从栈中弹出两个操作数进行运算，结果入栈，转2）；4）返回计算结果，结束算法。题目表达式中的括号匹配问题使用栈，用于保存左括号"{,[,("思路：自左至右扫描表达式，若遇左括号，则将左括号入栈，若遇右括号，则将其与栈顶的左括号进行匹配，若配对，则栈顶的左括号出栈，否则出现括号不匹配错误。程序运行时，对输入的每个表达式，判断其括号匹配情况。若其中的括号是匹配的，则输出“yes”，否则输出“no”。题目--判断表达式中的括

4、号是否匹配算法输入：表达式（包含三种括号()、{}、[]），以字符串形式存在字符数组中输出：匹配时为"yes"，否则为"no"步骤：1）构造一个空栈（用于暂存左括号）；2）表达式到达结尾？若是，则转4）；否则转3）；3）从表达式中取一个字符，若是左括号，则入栈；若是右括号，则判断其是否与栈顶的左括号相匹配，若不匹配则转4），否则转2）；若不是括号，则转2）；4）若栈空且表达式结束则输出"yes"，否则输出"no"，结束算法。题目离散事件模拟使用队列，模拟银行的服务窗口场景设定：三个窗口，因此需要模拟客户排队的三个队列；再加一个

5、事件队列，按时间顺序存放发生的事件：某客户来了，某客户离开某服务窗口了（一号窗口客户离开，二号窗口客户离开，三号窗口客户离开）。思路：由于是模拟，所以事件队列中的数据用伪随机函数产生。第一个事件产生的时刻为0，显然应该是客户到达事件。后面的客户什么时候来呢？由上个客户到达时产生的随机数表示。题目离散事件模拟思路：由于是模拟，所以事件队列中的数据用伪随机函数产生。第一个事件产生的时刻为0，显然应该是客户到达事件。后面的客户什么时候来呢？由上个客户到达时产生的随机数表示。因此，在客户到达事件发生时产生两个随机数；一为该时刻到达的客

6、户办理业务所需要的时间durtime；二为下一客户将要到达的时间间隔interval，假设当前事件的发生时刻为occurTime，则下一个客户到达事件发生的时刻为occurTime+interval。由此应产生一个新的客户到达事件。刚到达的客户则应插入到长度最短的队列中；若该队列在插入前为空（表明会立即得到服务），则还应产生一个客户离开事件。没有否是有否（客户离开事件）是初始化：客户数count＝0，客户逗留时间总和totaltime＝0，银行开门营业（occurtime=0），银行关门时间（endtime=*****）有一客

7、户到达(arrivetime=0，开始营业时第一个客户到来)，在事件表（初始为空）中插入一个事件，三个服务窗口置空队列。事件表中有事件吗？取出事件表的第一个事件是客户到达事件吗？用随机函数产生当前客户办理业务所需时间durtime和下一个客户将要到达的时间间隔interval下一客户到达时银行关门了吗？在事件表中插入一个客户到达事件，客户数count加1将当前客户加在人数最少的队列尾部。若当前客户为其所在队列的唯一客户，则其离开时间可确定（occurtime+durtime），因此在事件表中加入一个客户离开事件。结束计算并将客

8、户的逗留时间加入totaltime，若当前窗口还有客户，则正在办理业务的第一个客户离开时间可确定（occurtime+办理业务时间），因此在事件表中加入一个客户离开事件。开始离散事件模拟流程图事件表的元素按时间排序程序设计风格问题注释程序模块化（函数功能单一，代码长度适当）命