《数据结构C语言版第三章栈和队列.doc》由会员分享，可在线阅读，更多相关《数据结构C语言版第三章栈和队列.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 栈和队列重点难点掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法； 熟练掌握循环队列和链队列的基本操作实现算法；理解递归算法执行过程中栈的状态变化过程，便于更好地使用递归算法。典型例题 1.设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2) 能否得到出栈序
2、列1423和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种排列中，可通过相应入出栈操
3、作得到的序列是： 1234,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；问在这两种情况下，循环队列中各有元素多少个？【解】用队列长度计算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=324. 说明线性表、栈与队的异同点。【解】相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不
5、同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。5. 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到(就进栈，遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空。)【解】算法如下：int PairBracket( char *SR)/检查表达式ST中括号是否配对int i;SeqStack S; /定义一个栈InitStack (&s);for (i
6、=0; idata;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；（5）设有一个递归算法如下 int fact(int n) /n大于等于0 if(n=0) return 1; else return n*fact(n-1); 则计算fact(n)需要调用该函数的次数为（ ）。An+1 Bn-1 C n D n+2（6）栈在（ ）中有所应用。A递归调用 B函数调用 C表达式求值 D前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该
7、缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。A队列 B栈 C 线性表 D有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A2 B3 C4 D 6（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。 Atop不变 Btop=0 Ctop- Dtop+（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存
8、储结构 B队列 C. 线性表的链式存储结构 D. 栈（11）用链接方式存储的队列，在进行删除运算时（）。A. 仅修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针可能都要修改（12）循环队列存储在数组A0.m中，则入队时的操作为（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) （13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=fron
9、t D. (rear-l)%n=front（14）栈和队列的共同点是（）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点（15）一个递归算法必须包括（）。A. 递归部分 B. 终止条件和递归部分C. 迭代部分 D. 终止条件和迭代部分二、算法设计题1.Ackerman 函数定义如下：请写出递归算法。 n+1 当m=0时 AKM ( m , n ) = AKM( m-1 ,1) 当m0 ，n=0时 AKM( m-1, AKM( m,n-1) 当m0, n 0时 解：算法如下int AKM( int m, int n)if ( m= 0) return
10、 n+1;if ( m0 & n=0 ) return AKM( m-1, 1);if ( m0 & n0 ) return AKM( m-1, AKM( m, n-1);2. 设结点结构为(data,link)，试用一个全局指针p和某种链接结构实现一个队列,给出入队addq和出队deleteq过程,要求它们的时间复杂性都是O(l) 题目分析本题要求用链接结构实现一个队列，我们可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”，且要求入队和出队操作的时间复杂性是O（1），因此我们用只设尾指针的循环链表来实现队列。（1） Void
11、 addq(linklist p , elemtp x )/p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法是入队操作。new(s); /申请新结点。假设有内存空间，否则系统给出出错信息。s-data=x; s-link:=p-link;/将s结点入队。p-link:=s; p=s; /尾指针p移至新的队尾。（2） Void deleq(linklist p , elemtp x )/ p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法实现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息。if（p-link=p）printf(“空队列
12、”);return(0);/带头结点的循环队列。elses=p-link-link; /找到队头元素。 p-link-link=s-link; /删队头元素。 x=s-data; /返回出队元素。 if(p=s) p=p-link; /队列中只有一个结点，出队后成为空队列。 free(s); /回收出队元素所占存储空间。 算法讨论上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队列。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。3.如果允许在循环队列的两端都可以进行插入和删除操作。要求
13、：（1）写出循环队列的类型定义；（2）写出“从队尾删除”和“从队头插入”的算法。题目分析 用一维数组 v0.M-1实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。（1）#define M 队列可能达到的最大长度typedef struct elemtp dataM; int front,rear; cycqueue;（2）elemtp delqueue ( cycqueu
14、e Q) /Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。 if (Q.front=Q.rear) printf(“队列空”); exit(0); Q.rear=(Q.rear-1+M)%M; /修改队尾指针。 return(Q.data(Q.rear+1+M)%M); /返回出队元素。/从队尾删除算法结束void enqueue (cycqueue Q, elemtp x)/ Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。if (Q.rear=(Q.front-1+M)%M) printf(“队满”; exit(0);) Q.dataQ.front=x; /x 入队列Q.front=(Q.front-1+M)%M; /修改队头指针。/ 结束从队头插入算法。