中南大学数据结构与算法栈和队列课后作业答案讲解

1、第 3 章栈和队列习题练习答案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) 出栈序列为：

2、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,324

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

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

5、 Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S); for (i=0, i n; i+) Push(S, arri); /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) voi

6、d 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);

7、 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) 程序段的

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

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

10、ack s;int i , len;char temp;InitStack( &s);len=strlen(t); / 求向量长度for ( i=0; iTop = -1; / 其实只是将栈置空因为要置空的是栈 S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响， 系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作 的结果返回给实参的话，就只能用指针来做参数传递了。3.8 利用栈的基本操作， 写一个返回 S 中结点个数的算法 int StackSize( SeqStack S),并说明 S 为何不作为 指针参数 ?解：算法如下：in

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

12、)/检查表达式 ST 中括号是否配对int i;SeqStack S; /定义一个栈InitStack (&s);for (i=0; itop0 = -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 =

13、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 )r

14、eturn ( S-Data S-top0- );/ 返回栈顶元素，指针值减 1if( i=1 )return ( S-Data S-top1+ ); / 因为这个栈是以另一端为底的，所以指针值加1。3.11 Ackerman 函数定义如下：请写出递归算法。 n+1当 m=0 时AKM ( m , n ) = AKM(- 1m ,1) 当 m0 ，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 ( m0 & n=0 ) return AKM( m-1, 1)

15、;if ( m0 & n0 ) return AKM( m-1, AKM( m, n-1);3.12 用第二种方法 ，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判 队空，判队满、出队、入队及取队头元素等六个基本操作的算法。解：算法设计如下 :/循环队列的定义#define QueueSize 100typedef char Datatype ; / 设元素的类型为 char 型 typedef struct int front;int rear;DataType DataQueueSize;CirQueue;(1) 置空队void InitQueue ( CirQu

16、eue *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-DataQ-fr

17、ont ;/ 保存元素值Q-front= ( Q-front+1 ) %QueueSize;/ 循环意义上的加 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( 队空

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

19、) / 置空队：就是使头结点成为队尾元素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, Datatyp

20、e 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 指

21、向将要摘下的结点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;3.14 对于循环向量中的循环队列，写出求队列长度的公式。解：公式如下 (设采用第二种方法， front 指向真正的队首元素， rear 指向真正队尾后一位置， 向量空间大小：QueueSizeQueuelen=(QueueSize+rear-front)%QueueSize3.15 假设循环队列中只设 rear 和 quelen 来分别