第3章栈和队列习题练习答案

http://www.educity.cn　作者：不详　来源：　2006年9月4日　发表评论　进入社区

3.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)不能得到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,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321
      不能得到的序列是：
　　　　1423,2413,3124,3142,3412,4123,4132,4213,4231,4312

3.2 链栈中为何不设置头结点?
答：
链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

3.3 循环队列的优点是什么? 如何判别它的空和满?

答：
　　循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
答：
　　当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。

3.5 指出下述程序段的功能是什么?
(1) void Demo1(SeqStack *S){
　　　　int i; arr[64] ; n=0 ;
　　　　while ( StackEmpty(S)) arr[n++]=Pop(S);
　　　　for (i=0, i< n; i++) Push(S, arr[i]);
　　　} //Demo1

(2) SeqStack S1, S2, tmp;
　　DataType x;
　　...//假设栈tmp和S2已做过初始化
　　while ( ! StackEmpty (&S1))
　　　{
　　　　x=Pop(&S1) ;
　　　　Push(&tmp,x);
　　　}
　　while ( ! StackEmpty (&tmp) )
　　　{
　　　　x=Pop( &tmp);
　　　　Push( &S1,x);
　　　　Push( &S2, x);
　　　}

(3) void Demo2( SeqStack *S, int m)
　　　{ // 设DataType 为int 型
　　　　SeqStack T; int i;
　　　　InitStack (&T);
　　　　while (! StackEmpty( S))
　　　　　if(( i=Pop(S)) !=m) Push( &T,i);
　　　　while (! StackEmpty( &T))
　　　　　{
　　　　　　i=Pop(&T); Push(S,i);
　　　　　}
　　　}

(4)void Demo3( CirQueue *Q)
　　　{ // 设DataType 为int 型
　　　　int x; SeqStack S;
　　　　InitStack( &S);
　　　　while (! QueueEmpty( Q ))
　　　　　{x=DeQueue( Q); Push( &S,x);}
　　　　while (! StackEmpty( &s))
　　　　　{ x=Pop(&S); EnQueue( Q,x );}
　　　}// Demo3

(5) CirQueue Q1, Q2; // 设DataType 为int 型
　　int x, i , n= 0;
　　... // 设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, x);}

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

3.6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)

解：
　　根据提示，算法可设计为：
　//以下为顺序栈的存储结构定义
　#define StackSize 100 //假定预分配的栈空间最多为100个元素
　typedef char DataType;//假定栈元素的数据类型为字符
　typedef struct{
　　DataType data[StackSize];
　　int top;
　}SeqStack;

　int IsHuiwen( char *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, t[i]);
　　　while( !EmptyStack( &s))
　　　　{// 每弹出一个字符与相应字符比较
　　　　　temp=Pop (&s);
　　　　　if( temp!=S[i]) return 0 ;// 不等则返回0
　　　　　else i++;
　　　　}
　　　return 1 ; // 比较完毕均相等则返回 1
　　}

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

3.8 利用栈的基本操作，写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数?
解：
　算法如下：
　　int StackSize (SeqStack S)
　　　{//计算栈中结点个数
　　　　int n=0;
　　　　if(!EmptyStack(&S))
　　　　　{
　　　　　　Pop(&S);
　　　　　　n++;
　　　　　}
　　　　return n;
　　　}
　　上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。

3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示：对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。
解：
　　根据提示，可以设计算法如下：
　int PairBracket( char *SR)
　　{//检查表达式ST中括号是否配对
　　　int i;
　　　SeqStack S; //定义一个栈
　　　InitStack (&s);
　　　for (i=0; i<strlen(SR) ; i++)
　　　　{
　　　　　if ( S[i]=='(' ) Push(&S, SR[i]); //遇'('时进栈
　　　　　if ( S[i]==')' ) //遇')'
　　　　　　if (!StackEmpty(S))//栈不为空时，将栈顶元素出栈
　　　　　　　Pop(&s);
　　　　　　else return 0;//不匹配，返回0
　　　　}
　　　if EmptyStack(&s) return 1;// 匹配，返回1
　　　else return 0;//不匹配，返回0
　　}

3.10 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法，其中i为0 或1，用以表示栈号。
解：
　　双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：
　//双向栈的栈结构类型与以前定义略有不同
　#define StackSize 100 // 假定分配了100个元素的向量空间
　#define char DataType
　typedef struct{
　 DataType Data[StackSize]
int top0; //需设两个指针
　　int top1;
　}DblStack
　void InitStack( DblStack *S )
　　{ //初始化双向栈
　　　S->top0 = -1;
　　　S->top1 = StackSize; //这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错
　　}

　int EmptyStack( DblStack *S, int i )
　　{ //判栈空(栈号 i)
　　　　return (i == 0 && 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入栈
　　　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--] );//返回栈顶元素，指针值减1
　　　if( i==1 )
　　　　return ( S->Data[ S->top1++] ); //因为这个栈是以另一端为底的，所以指针值加1。
　　}

3.11 Ackerman 函数定义如下：请写出递归算法。
　　　　　　　　┌ n+1　　　当m=0时
AKM ( m , n ) = │ AKM( m-1 ,1) 当m≠0 ，n=0时
　　　　　　　　└ AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 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));
　　　}

3.12 用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。
解：
　算法设计如下:
//循环队列的定义
#define QueueSize 100
　typedef char Datatype ; //设元素的类型为char型
　typedef struct {
　　int front;
　　int rear;
　　DataType Data[QueueSize];
}CirQueue;

(1)置空队
　　void InitQueue ( CirQueue *Q)
　　　{ // 置空队
　　　　Q->front=Q->rear=0;
　　　}

　(2)判队空
　　int EmptyQueue( CirQueue *Q)
　　　{ //判队空
　　　　return Q->front==Q->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->Data[Q->front] ;//保存元素值
　　　　Q->front= ( Q->front+1 ) %QueueSize;//循环意义上的加1
　　　　return temp; //返回元素值
　　　}

　(5)入队
　　void EnQueue (CirQueue *Q, DataType x)
　　　{ // 入队
　　　　if( FullQueue( Q))
　　　　　Error ("队已满，不可以入队");
　　　　Q->Data[Q->rear]=x;
　　　　Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一个空元素位置
　　　}

　(6)取队头元素
　　DataType FrontQueue( CirQueue *Q)
　　　{ //取队头元素
　　　　if (EmptyQueue( Q))
　　　　　Error( "队空，无元素可取");
　　　　return Q->Data[Q->front];
　　　}

3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空、入队和出队等算法。

解：
　　算法如下：
　//先定义链队结构:
　typedef struct queuenode{
　　　Datatype data;
　　　struct queuenode *next;
　　}QueueNode; //以上是结点类型的定义

　typedef struct{
　　　queuenode *rear;
　　}LinkQueue; //只设一个指向队尾元素的指针

　(1)置空队
　　void InitQueue( LinkQueue *Q)
　　　{ //置空队：就是使头结点成为队尾元素
　　　　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->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;
　　　　QueueNode *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;}
　　　　else
　　　　　　Q->rear->next->next=p->next;//摘下结点p
　　　　free(p);//释放被删结点
　　　　return x;
　　　}

3.14 对于循环向量中的循环队列，写出求队列长度的公式。
解：
　　公式如下(设采用第二种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSize
　　　　Queuelen=(QueueSize+rear-front)%QueueSize

3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。

解：
　　根据题意，可定义该循环队列的存储结构：
　#define QueueSize 100
　typedef char Datatype ; //设元素的类型为char型
　typedef struct {
　　　int quelen;
　　　int rear;
　　　Datatype Data[QueueSize];
　　}CirQueue;
　CirQueue *Q;
　　循环队列的队满条件是：Q->quelen==QueueSize
　　知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下：

　(1)判断队满
　　　int FullQueue( CirQueue *Q)
　　　　{//判队满,队中元素个数等于空间大小
　　　　　　return Q->quelen==QueueSize;
　　　　}

　(2)入队
　　　void EnQueue( CirQueue *Q, Datatype x)
　　　　{// 入队
　　　　　if(FullQueue( Q))
　　　　　　Error("队已满，无法入队");
　　　　　Q->Data[Q->rear]=x;
　　　　　Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1
　　　　　Q->quelen++;
　　　　}

　(3)出队
　　　Datatype DeQueue( CirQueue *Q)
　　　　{//出队
　　　　　if(Q->quelen==0)
　　　　　　Error("队已空，无元素可出队");
　　　　　int tmpfront; //设一个临时队头指针
　　　　　tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//计算头指针位置
　　　　　Q->quelen--;
　　　　　return Q->Data[tmpfront];
　　　　}

【大中小】【收藏到我的学赛】【发表评论】【进入社区】