栈和队列习题答案

1、第三章 栈和队列习题答案一、基础知识题设将整数 1 ， 2， 3， 4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ), 则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)(2)能否得到出栈序列1423 和 1432 并说明为什么不能得到或者如何得到。(3)请分析 1 ， 2 ， 3 ， 4 的 24 种排列中，哪些序列是可以通过相应的入出栈操作得到的。答： (1)出栈序列为： 1324(2)不

2、能 得 到 1423 序 列 。 因 为 要 得 到 14 的 出 栈 序 列 ， 则 应做 Push(1),Pop(),Push(2),Push ,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,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,

3、3421,4321不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,4312链栈中为何不设置头结点答 ：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。循环队列的优点是什么如何判别它的空和满答 ：循环队列的优点是：它可以克服顺序队列的 " 假上溢 " 现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种

4、方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。设长度为 n 的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何 若只设尾指针呢答：当只设头指针时，出队的时间为 1,而入队的时间需要n,因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为 1 。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。指出下述程序段的功能是什么(1) voi

5、d Demo1(SeqStack *S) int i; arr64 ; n=0 ; while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); . / 设 Q1 已有内容， Q2 已初始化过while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+;for (i=0; i< n; i+) x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2

6、, x); 答：(1)程序段的功能是将一栈中的元素按反序重新排列， 也就是原来在栈顶的元素放到栈底， 栈底的元素放到栈顶。此栈中元素个数限制在64 个以内。(2)程序段的功能是利用tmp 栈将一个非空栈s1 的所有元素按原样复制到一个栈s2 当中去。(3)程序段的功能是利用栈T,将一个非空栈S中值等于m的元素全部删去。(4)程序段的功能是将一个循环队列 Q 经过 S 栈的处理，反向排列，原来的队头变成队尾，原来 的队尾变成队头。(5)这段程序的功能是将队列 1 的所有元素复制到队列 2 中去， 但其执行过程是先把队列 1 的元素全部出队，进入队列2，然后再把队列2 的元素复制到队列 1 中。二

7、、算法设计题回文是指正读反读均相同的字符序列，如 "abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)解 ：根据提示，算法可设计为：/ 以下为顺序栈的存储结构定义#define StackSize 100 /假定预分配的栈空间最多为 100 个元素typedef char DataType;/ 假定栈元素的数据类型为字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( cha

8、r *t)/ 判断 t 字符向量是否为回文，若是，返回 1，否则返回 0 SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); / 求向量长度for ( i=0; i<len/ 2; i+)/ 将一半字符入栈Push( &s, ti);while( !EmptyStack( &s)/ 每弹出一个字符与相应字符比较temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等则返回 0 else i+;return 1 ; / 比较完毕均相等则返回 1利用栈的基本操

9、作，写一个将栈S 中所有结点均删去的算法void ClearStack( SeqStack *S) ，并说明S为何要作为指针参数解 ：算法如下void ClearStack (SeqStack *S) / 删除栈中所有结点S->Top = -1; /其实只是将栈置空因为要置空的是栈 S,如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影 响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。利用栈的基本操作，写一个返回S中结点个数的算法int StackSize( SeqStack

10、S),并说明S为何不作为指针参数解 ：算法如下：int StackSize (SeqStack S)/ 计算栈中结点个数int n=0;if(!EmptyStack(&S) Pop(&S);n+;return n;上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。设计算法判断一个算术表达式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到 '('就进栈，遇 ')'就退掉栈顶的'('

11、，表达式被扫描完毕，栈应为空。解 ：根据提示，可以设计算法如下：int PairBracket( char *SR)/ 检查表达式ST 中括号是否配对int i;SeqStack S; /定义一个栈InitStack (&s);for (i=0; i<strlen(SR) ; i+)if ( Si='(' ) Push(&S, SRi); /遇'('时进栈if ( Si=')' ) / 遇')'if (!StackEmpty(S)/ 栈不为空时，将栈顶元素出栈Pop(&s);else return 0

12、;/ 不匹配，返回 0if EmptyStack(&s) return 1;/ 匹配，返回1else return 0;/ 不匹配，返回 0一个双向栈S 是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化 InitStack ( S ) 、 入栈 Push( S , i , x) 和出栈 Pop( S , i )等算法，其中 i 为 0 或 1 ， 用以表示栈号。解 ：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：/ 双向栈的栈结构类型与以前定义略有不同#define

13、 StackSize 100 / 假定分配了 100 个元素的向量空间#define char DataTypetypedef structDataType DataStackSizeint top0; / 需设两个指针int top1;DblStackvoid InitStack( DblStack *S ) / 初始化双向栈S->top0 = -1;S->top1 = StackSize; /这里的top2 也指出了向量空间，但由于是作为栈底，因此不会出错int EmptyStack( DblStack *S, int i ) / 判栈空(栈号i)return (i = 0 &

14、amp;& S->top0 = -1| i = 1 && S->top1= StackSize) ;int FullStack( DblStack *S) / 判栈满 ,满时肯定两头相遇return (S->top0 = S-top1-1);void Push(DblStack *S, int i, DataType x) / 进栈(栈号i)if (FullStack( S )Error("Stack overflow");/ 上溢、退出运行if ( i = 0) S->Data + S->top0= x; /栈 0 入

15、栈if ( i = 1) S->Data - S->top1= x; / 栈 1 入栈DataType Pop(DblStack *S, int i) / 出栈(栈号i)if (EmptyStack ( S,i) )Error("Stack underflow");/ 下溢退出if( i=0 )return ( S->Data S->top0- );/ 返回栈顶元素，指针值减1if( i=1 )return ( S->Data S->top1+ ); / 因为这个栈是以另一端为底的，所以指针值加 1 。 Ackerman 函数定义如下：请

16、写出递归算法。厂n+1 当m=0时AKM ( m , n ) =AKMO0 , n=0 时L AKM( ml, AKM( m,n-1)当 rn0, n w日0解： 算法如下int AKM( int m, int n)if ( m= 0) return n+1;if ( m<>0 && n=0 ) return AKM( m-1, 1);if ( m<>0 && n<>0 ) return AKM( m-1, AKM( m, n-1);用第二种方法 ，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，

17、判队满、出队、入队及取队头元素等六个基本操作的算法。解 ：算法设计如下:/ 循环队列的定义#define QueueSize 100typedef char Datatype ; / 设元素的类型为 char 型typedef struct int front;int rear;DataType DataQueueSize;CirQueue;(1)置空队void InitQueue ( CirQueue *Q) / 置空队Q->front=Q->rear=0;(2)判队空int EmptyQueue( CirQueue *Q) / 判队空return Q->front=Q-&

18、gt;rear;(3)判队满int FullQueue( CirQueue *Q) / 判队满 / 如果尾指针加1 后等于头指针，则认为满return (Q->rear+1)%QueueSize= Q->front;(4) 出队DataType DeQueue( CirQueue *Q) / 出队DataType temp;if(EmptyQueue(Q)Error(" 队已空，无元素可以出队");temp=Q->DataQ->front ;/ 保存元素值Q->front= ( Q->front+1 ) %QueueSize;/ 循环意义

19、上的加1return temp; / 返回元素值(5)入队void EnQueue (CirQueue *Q, DataType x) / 入队if( FullQueue( Q)Error (" 队已满，不可以入队");Q->DataQ->rear=x;Q->rear=(Q->rear+1)%QueueSize; /rear 指向下一个空元素位置(6)取队头元素DataType FrontQueue( CirQueue *Q) / 取队头元素if (EmptyQueue( Q)Error( " 队空，无元素可取");return

20、Q->DataQ->front;假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点 (注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。解 ：算法如下：/ 先定义链队结构:typedef struct queuenodeDatatype data;struct queuenode *next;QueueNode; / 以上是结点类型的定义typedef structqueuenode *rear;LinkQueue; / 只设一个指向队尾元素的指针(1)置空队void InitQueue( LinkQueue *Q) / 置空队：就是使头结点成为队

21、尾元素QueueNode *s;Q->rear = Q->rear->next;/ 将队尾指针指向头结点while (Q->rear!=Q->rear->next)/ 当队列非空，将队中元素逐个出队s=Q->rear->next;Q->rear->next=s->next;free(s);/ 回收结点空间(2)判队空int EmptyQueue( LinkQueue *Q) / 判队空/ 当头结点的 next 指针指向自己时为空队return Q->rear->next->next=Q->rear->

22、;next;(3)入队void EnQueue( LinkQueue *Q, Datatype x) / 入队/ 也就是在尾结点处插入元素QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/ 申请新结点 p->data=x; p->next=Q->rear->next;/ 初始化新结点并链入Q-rear->next=p;Q->rear=p;/ 将尾指针移至新结点(4) 出队Datatype DeQueue( LinkQueue *Q)/ 出队 ,把头结点之后的元素摘下Datatype t;QueueNo

23、de *p;if(EmptyQueue( Q )Error("Queue underflow");p=Q->rear->next->next; /p 指向将要摘下的结点x=p->data; / 保存结点中数据if (p=Q->rear)/ 当队列中只有一个结点时， p 结点出队后，要将队尾指针指向头结点Q->rear = Q->rear->next; Q->rear->next=p->next;elseQ->rear->next->next=p->next;/ 摘下结点 pfree(p);/ 释放被删结点return x;对于循环向量中的循环队列，写出求队列长度的公式。解：公式如下 (设采用第二种方法， front 指向真正的队首元素， rear 指向真正队尾后一位置，向量空 间大小： QueueSizeQueuelen=(QueueSize+rear-front)%QueueSize假设循环队列中只设rear