数据结构C语言版第三章栈和队列.pdf

《数据结构C语言版第三章栈和队列.pdf》由会员分享，可在线阅读，更多相关《数据结构C语言版第三章栈和队列.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、p(),Pop(),Push(4),Pop(),Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出则出栈的数字序列为何栈的数字序列为何(这里这里 Push(i)Push(i)表示表示 i i 进栈，进栈，Pop()Pop()表示出栈表示出栈)?)?(2)(2)能否得到出栈序列能否得到出栈序列 14231423 和和 1432?1432?并说明为什么不能得到或者如何得到。并说明为什么不能得到或者如何得到。(3)(3)请分析请分析 1 1，2 2，3 3，4 4 的的 2424 种排列中，哪些序列是可以通过相应的入出栈操作得到种排列

3、中，哪些序列是可以通过相应的入出栈操作得到的。的。【解】(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 种排列中，可通过相应入出栈操作得到的序列是：1234,1243,1

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

5、重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.3.设循环队列的容量为设循环队列的容量为 4040（序号从（序号从 0 0 到到 3939），现经过一系列的入队和出队运算后，有），现经过一系列的入队和出队运算后，有 front=11front=11，rear=19;rear=19;front=19front=19，rear=11rear=11；问在这两种情况下，循环队列中各；问在这两种情况下，循环队列中各有元素多少个？有元素多少个？【解】用队列长度计算公式：(Nrf)%N L=（401911）%40=8 L=（401119）%40=32

6、4.4.说明线性表、栈与队的异同点。说明线性表、栈与队的异同点。【解】相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表 LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表 FIFO。用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。5.5.设计算法判断一个算术表达式的圆括号是否正确配对。设计算法判断一个算术表达式的圆括号是否正确配对。(提示：提示：对

7、表达式进行扫描，对表达式进行扫描，凡遇到凡遇到(就进栈，遇就进栈，遇)就退掉栈顶的就退掉栈顶的(，表达式被扫描完毕，栈应为空。，表达式被扫描完毕，栈应为空。)【解】算法如下：【解】算法如下：int PairBracket(char*SR)/检查表达式 ST 中括号是否配对int i;SeqStack S;/定义一个栈InitStack(&s);for(i=0;idata;top=top-link；Cx=top;top=top-link；（5）设有一个递归算法如下int fact(int n)/n 大于等于 0if(nlink;x=top-link；Dx=top-link；则计算 fact(n)

8、需要调用该函数的次数为（）。A n+1B n-1C nD n+2（6）栈在（）中有所应用。A递归调用B函数调用C表达式求值D前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A队列 B栈C 线性表D有序表（8）设栈S 和队列 Q 的初始状态为空，元素e1、e2、e3、e4、e5 和 e6 依次进入栈 S，一个元素出栈后即进入 Q，若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和 e1，则栈 S 的容量至少应该是（）。A2B3C4D 6（9）在一

9、个具有 n 个单元的顺序栈中，假设以地址高端作为栈底，以 top 作为栈顶指针，则当作进栈处理时，top 的变化为（）。Atop 不变Btop=0Ctop-Dtop+（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B队列C.线性表的链式存储结构 D.栈（11）用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针 B.仅修改尾指针C.头、尾指针都要修改 D.头、尾指针可能都要修改（12）循环队列存储在数组A0.m中，则入队时的操作为（）。A.rear=rear+1 B.rear=(rear+1)%(m-1)C.rear=(rear+

10、1)%m D.rear=(rear+1)%(m+1)（13）最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是（）。Crear+1=front D.(rear-l)%n=front（14）栈和队列的共同点是（）。A.都是先进先出 B.都是先进后出C.只允许在端点处插入和删除元素 D.没有共同点（15）一个递归算法必须包括（）。A.递归部分 B.终止条件和递归部分C.迭代部分 D.终止条件和迭代部分二、算法设计题二、算法设计题1.Ackerman1.Ackerman 函数定义如下：请写出递归算法。函数定义如下：请写出递归算法。n+1n+1当当 m=0m=0 时时

11、AKM(m,n)=AKM(m,n)=AKM(m-1,1)AKM(m-1,1)当当 mm0 0，n=0n=0 时时 AKM(m-1,AKM(m,n-1)AKM(m-1,AKM(m,n-1)当当 mm0,n0,n 0 0 时时解：A.(rear+1)%n=front B.rear=front算法如下int AKM(int m,int n)if(m=0)return n+1;if(m0&n=0)return AKM(m-1,1);if(m0&n0)return AKM(m-1,AKM(m,n-1);2.2.设结点结构为设结点结构为(data,link)(data,link)，试用一个全局指针，试用一

12、个全局指针 p p 和某种链接结构实现一个队列和某种链接结构实现一个队列,给出入给出入队队 addqaddq 和出队和出队 deleteqdeleteq 过程过程,要求它们的时间复杂性都是要求它们的时间复杂性都是 O(l)O(l)题目分析本题要求用链接结构实现一个队列，我们可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针 p”，且要求入队和出队操作的时间复杂性是O（1），因此我们用只设尾指针的循环链表来实现队列。（1）VoidVoid addq(linklist p,elemtp x)/p 是数据域为 data、链域为 link

13、的用循环链表表示的队列的尾指针，本算法是入队操作。new(s);/申请新结点。假设有内存空间，否则系统给出出错信息。s-data=x;s-link:=p-link;/将 s 结点入队。p-link:=s;p=s;/尾指针 p 移至新的队尾。（2）VoidVoid deleq(linklist p,elemtp x)/p 是数据域为 data、链域为link 的用循环链表表示的队列的尾指针，本算法实现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息。ifif（p-link=p）printf(“空队列”);returnreturn(0);/带头结点的循环队列。elseelses=p-li

14、nk-link;/找到队头元素。p-link-link=s-link;/删队头元素。x=s-data;/返回出队元素。ifif(p=s)p=p-link;/队列中只有一个结点，出队后成为空队列。free(s);/回收出队元素所占存储空间。算法讨论上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队列。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。3.3.如果允许在循环队列的两端都可以进行插入和删除操作。要求：如果允许在循环队列的两端都可以进行插入和删除操作。要求：（1 1）写出循环队列的

15、类型定义；）写出循环队列的类型定义；（2 2）写出“从队尾删除”和“从队头插入”的算法。）写出“从队尾删除”和“从队头插入”的算法。题目分析 用一维数组 v0.M-1实现循环队列，其中 M 是队列长度。设队头指针 front和队尾指针rear，约定 front 指向队头元素的前一位置，rear 指向队尾元素。定义front=rear 时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。（1）#define M队列可能达到的最大长度typedeftypedef structstruct elemtp dataM;intint fro

16、nt,rear;cycqueue;（2）elemtp delqueue(cycqueue Q)/Q 是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。ifif(Q.front=Q.rear)printf(“队列空”);exit(0);Q.rear=(Q.rear-1+M)%M;/修改队尾指针。/从队尾删除算法结束voidvoid enqueue(cycqueue Q,elemtp x)/Q 是顺序存储的循环队列，本算法实现“从队头插入”元素x。ifif(Q.rear=(Q.front-1+M)%M)printf(“队满”;exit(0);)Q.dataQ.front=x;/x 入队列Q.front=(Q.front-1+M)%M;/修改队头指针。/结束从队头插入算法。returnreturn(Q.data(Q.rear+1+M)%M);/返回出队元素。