数据结构第三章(栈与队列)习题参考答案

数据结构第三章(栈与队列)习题参考答案  

　　一 基础知识题

　　 设将整数 依次进栈 但只要出栈时栈非空 则可将出栈操作按任何次序夹入其中 请回答下述问题

　　( )若入 出栈次序为Push( ) Pop() Push( ) Push( ) Pop() Pop( ) Push( ) Pop( ) 则出栈的数字序列为何(这里Push(i)表示i进栈 Pop( )表示出栈)?

　　( ) 能否得到出栈序列 和 ?并说明为什么不能得到或者如何得到

　　( )请分析 的 种排列中 哪些序列是可以通过相应的入出栈操作得到的

　　 链栈中为何不设置头结点?

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

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

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

　　 设长度为n的链队用单循环链表表示 若设头指针 则入队出队操作的时间为何? 若只设尾指针呢?

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

　　 指出下述程序段的功能是什么?

　　( ) void Demo (SeqStack *S){

　　int i; arr[ ] ; n= ;

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

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

　　} //Demo

　　( ) SeqStack S S tmp;

　　DataType x;

　　 //假设栈tmp和S 已做过初始化

　　while ( ! StackEmpty (&S ))

　　{

　　x=Pop(&S ) ;

　　Push(&tmp x);

　　}

　　while ( ! StackEmpty (&tmp) )

　　{

　　x=Pop( &tmp);

　　Push( &S x);

　　Push( &S x);

　　}

　　( ) void Demo ( 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);

　　}

　　}

　　( )void Demo ( 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 );}

　　}// Demo

　　( ) CirQueue Q Q ; // 设DataType 为int 型

　　int x i m = ;

　　 // 设Q 已有内容 Q 已初始化过

　　while ( ! QueueEmpty( &Q ) )

　　{ x=DeQueue( &Q ) ; EnQueue(&Q x); m++;}

　　for (i= ; i< n; i++)

　　{ x=DeQueue(&Q ) ;

　　EnQueue( &Q x) ; EnQueue( &Q x);}

　　答

　　( )程序段的功能是将一栈中的元素按反序重新排列 也就是原来在栈顶的元素放到栈底 栈底的元素放到栈顶 此栈中元素个数限制在 个以内

　　( )程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去

　　( )程序段的功能是将一个非空栈中值等于m的元素全部删去

　　( )程序段的功能是将一个循环队列反向排列 原来的队头变成队尾 原来的队尾变成队头

　　( )首先指出程序可能有印刷错误 for语句中的n应为m才对 这段程序的功能是将队列 的所有元素复制到队列 中去 但其执行过程是先把队列 的元素全部出队 进入队列 然后再把队列 的元素复制到队列 中

　　二 算法设计题

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

　　解 根据提示 算法可设计为

　　//ishuiwen h 存为头文件

　　int IsHuiwen( char *S)

　　{

　　SeqStack T;

　　int i l;

　　char t;

　　InitStack( &T);

　　l=strlen(S); //求向量长度

　　for ( i= ; i

　　Push( &T S[i]);

　　while( !EmptyStack( &T))

　　{

　　// 每弹出一个字符与相应字符比较

　　t=Pop (&T);

　　if( t!=S[l i]) { return ;}// 不等则返回

　　i ;

　　}

　　return ; // 比较完毕均相等则返回

　　}

　　// 以下程序用于验证上面的算法

　　//以下是栈定义( 存为stack h)

　　//出错控制函数

　　#include

　　#include

　　void Error(char * message)

　　{

　　fprintf(stderr Error: %sn message);

　　exit( );

　　}

　　// 定义栈类型

　　#define StackSize

　　typedef char Datatype;

　　typedef struct{

　　Datatype data[StackSize];

　　int Top;

　　} SeqStack;

　　void InitStack( SeqStack *S)

　　{

　　//初始化(置空栈)

　　S >Top= ;

　　}

　　int EmptyStack(SeqStack *S)

　　{ //判栈空

　　return S >Top == ;

　　}

　　int FullStack (SeqStack *S)

　　{ // 判栈满

　　return S >Top==StackSize ;

　　}

　　void Push (SeqStack *S Datatype x)

　　{ //进栈

　　if(FullStack(S))

　　Error( Stack overflow );

　　S >data[++S >Top]=x;

　　}

　　Datatype Pop(SeqStack *S)

　　{ // 出栈(退栈)

　　if (EmptyStack( S) )

　　Error( Stack underflow );

　　return S >data[S >Top ];

　　}

　　//取栈顶元素(略)

　　//

　　//以下是主程序

　　#include

　　#include

　　#include stack h>

　　#include ishuiwen h

　　void main( )

　　{

　　char Str[ ]= ;

　　printf( 输入一个字符串:n );

　　scanf( %s Str);

　　if( IsHuiwen(Str))

　　printf( n这个字符串是回文 );

　　else printf( n这个字符串不是回文 );

　　}

　　附 肖平来信指出问题

　　个人认为如题目所言 abba 和 abdba 均是回文 但对于这两种回文需要区别对待 原算法在判断类似 abdba 的回文时 会认为其不是回文而与题意相违背!

　　我的编程思想是 设置一个float型的变量 用于存放字符串的长度 再利用取整函数对长度为奇数的回文进行判别 若将字符串长度附给一整型变量 那么无论该整形变量除任何整数 其结果仍然是一整数 因此必须设一实型变量!判断结束后 若是回文返回 不是则返回

　　我的算法如下 已验证通过

　　int HuiWen(char *p)

　　{

　　int i;

　　float t;

　　SeqStack S;

　　InitStack(&S);

　　t=strlen(p);

　　for(i= ;i<=t/ ;i++)

　　Push(&S p[i]);

　　if(floor(t/ )!=(t/ )) //针对 abdba 类的回文

　　i++;

　　while(p[i]!= )

　　if(Pop(&S)==p[i])

　　i++;

　　else

　　return( );

　　return( );

　　}

　　=================================================

　　也可以直接用字符指针而不用字符数组来处理 只需对算法稍作修改!

　　算法如下 已验证通过

　　int HuiWen(char *p)

　　{

　　int i;

　　float t;

　　SeqStack S;

　　InitStack(&S);

　　t=strlen(p);

　　for(i= ;i<=t/ ;i++ p++)

　　Push(&S *p);

　　if(floor(t/ )!=(t/ )) //针对 abdba 类的回文

　　p++;

　　while(*p!= )

　　if(Pop(&S)==*p)

　　p++;

　　else

　　return( );

　　return( );

　　}