数据结构C语言版栈和队列.doc

《数据结构C语言版栈和队列.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第三章栈和队列重点难点掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法；熟练掌握循环队列和链队列的基本操作实现算法；理解递归算法执行过程中栈的状态变化过程，便于更好地使用递归算法。典型例题1.设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：　　(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)?　　(2)能否得到出栈序列1423和

2、1432?并说明为什么不能得到或者如何得到。(3)请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。【解】(1)出栈序列为：1324(2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push(3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。　　(3)在1，2，3，4的24种排列中，可通过相应入出栈操作得到的序列是：　　12

3、34,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到的序列是：　　　　1423,2413,3124,3142,3412,4123,4132,4213,4231,43122.循环队列的优点是什么?如何判别它的空和满?【解】循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重

4、合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？【解】用队列长度计算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=324.说明线性表、栈与队的异同点。【解】相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。

5、不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。5.设计算法判断一个算术表达式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。)【解】算法如下：　intPairBracket(char*SR)　　{//检查表达式ST中括号是否配对　　　inti;　　　SeqStackS;//定义一个栈　　　InitS

6、tack(&s);　　　for(i=0;i

7、）种情况。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。A．iB．n-iC．n-i+1D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。A．r-fB．(n+f