栈和队列习习题答案

PAGE4第三章栈和队列习题答案一、基础知识题设将整数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链栈中为何不设置头结点？

答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。循环队列的优点是什么如何判别它的空和满

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

答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。指出下述程序段的功能是什么

(1)voidDemo1(SeqStack*S){

inti;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(i=0,i<n;i++)Push(S,arr[i]);

}..//设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中。二、算法设计题回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)

解：根据提示，算法可设计为：//以下为顺序栈的存储结构定义#defineStackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据类型为字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;

intIsHuiwen(char*t){//判断t字符向量是否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;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])

return0;//不等则返回0elsei++;}

return1;//比较完毕均相等则返回1}利用栈的基本操作，写一个将栈S中所有结点均删去的算法voidClearStack(SeqStack*S)，并说明S为何要作为指针参数

解：

算法如下voidClearStack(SeqStack*S){//删除栈中所有结点S->Top=-1;//其实只是将栈置空}

因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。利用栈的基本操作，写一个返回S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数

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

解：根据提示，可以设计算法如下：intPairBracket(char*SR){//检查表达式ST中括号是否配对inti;SeqStackS;//定义一个栈InitStack(&s);for(i=0;i<strlen(SR);i++){

if(S[i]=='(')Push(&S,SR[i]);//遇'('时进栈if(S[i]==')')//遇')'if(!StackEmpty(S))//栈不为空时，将栈顶元素出栈Pop(&s);elsereturn0;//不匹配，返回0}ifEmptyStack(&s)return1;//匹配，返回1elsereturn0;//不匹配，返回0}一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)等算法，其中i为0或1，用以表示栈号。

解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：//双向栈的栈结构类型与以前定义略有不同#defineStackSize100//假定分配了100个元素的向量空间#definecharDataTypetypedefstruct{

DataTypeData[StackSize]

inttop0;//需设两个指针inttop1;}DblStackvoidInitStack(DblStack*S){//初始化双向栈S->top0=-1;S->top1=StackSize;//这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错}

intEmptyStack(DblStack*S,inti){//判栈空(栈号i)return(i==0&&S->top0==-1||i==1&&S->top1==StackSize);}intFullStack(DblStack*S){//判栈满,满时肯定两头相遇return(S->top0==S-top1-1);}voidPush(DblStack*S,inti,DataTypex){//进栈(栈号i)if(FullStack(S))Error("Stackoverflow");//上溢、退出运行if(i==0)S->Data[++S->top0]=x;//栈0入栈if(i==1)S->Data[--S->top1]=x;//栈1入栈}DataTypePop(DblStack*S,inti){//出栈(栈号i)if(EmptyStack(S,i))Error("Stackunderflow");//下溢退出if(i==0)

return(S->Data[S->top0--]);//返回栈顶元素，指针值减1if(i==1)return(S->Data[S->top1++]);//因为这个栈是以另一端为底的，所以指针值加1。}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时

解：算法如下intAKM(intm,intn){if(m==0)returnn+1;if(m<>0&&n==0)returnAKM(m-1,1);if(m<>0&&n<>0)returnAKM(m-1,AKM(m,n-1));}用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。

解：算法设计如下:

//循环队列的定义

#defineQueueSize100

typedefcharDatatype;//设元素的类型为char型typedefstruct{intfront;intrear;DataTypeData[QueueSize];

}CirQueue;

(1)置空队voidInitQueue(CirQueue*Q){//置空队Q->front=Q->rear=0;}(2)判队空intEmptyQueue(CirQueue*Q){//判队空returnQ->front==Q->rear;}(3)判队满intFullQueue(CirQueue*Q){//判队满//如果尾指针加1后等于头指针，则认为满return(Q->rear+1)%QueueSize==Q->front;}(4)出队DataTypeDeQueue(CirQueue*Q){//出队DataTypetemp;if(EmptyQueue(Q))Error("队已空，无元素可以出队");temp=Q->Data[Q->front];//保存元素值Q->front=(Q->front+1)%QueueSize;//循环意义上的加1returntemp;//返回元素值}(5)入队voidEnQueue(CirQueue*Q,DataTypex){//入队if(FullQueue(Q))Error("队已满，不可以入队");Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//rear指向下一个空元素位置}(6)取队头元素DataTypeFrontQueue(CirQueue*Q){//取队头元素if(EmptyQueue(Q))Error("队空，无元素可取");returnQ->Data[Q->front];}假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。

解：算法如下：//先定义链队结构:typedefstructqueuenode{Datatypedata;structqueuenode*next;}QueueNode;//以上是结点类型的定义typedefstruct{queuenode*rear;}LinkQueue;//只设一个指向队尾元素的指针(1)置空队voidInitQueue(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)判队空

intEmptyQueue(LinkQueue*Q){//判队空//当头结点的next指针指向自己时为空队returnQ->rear->next->next==Q->rear->next;}(3)入队voidEnQueue(LinkQueue*Q,Datatypex){//入队//也就是在尾结点处插入元素QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点p->data=x;p->next=Q->rear->next;//初始化新结点并链入Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点}(4)出队DatatypeDeQueue(LinkQueue*Q){//出队,把头结点之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q))Error("Queueunderflow");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;//摘下结点pfree(p);//释放被删结点returnx;}对于循环向量中的循环队列，写出求队列长度的公式。

解：公式如下(设采用第二种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSizeQueuelen=(QueueSize+rear-front)%QueueSize假设循环队列中只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队