第三章 栈与队列 习题及答案(2)

if( IsHuiwen(Str)) printf(\这个字符串是回文。\ else printf(\这个字符串不是回文。\}

3.7解： 算法如下

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

因为我们要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。 3.8 解：算法如下：

int StackSize (SeqStack S) { //计算栈中结点个数 int n=0; if(!EmptyStack(&S)) { Pop(&S); n++; } return n; }

类似于上面的原因，我们要计算栈中元素个数就要弹出元素才能\数\得出来，那如果用指针做参数的话，就会把原来的栈中元素\弹\光，要恢复还得用别的办法给它装回去，而不用指针做参数，则可以避免对原来的栈中元素进行任何操作，系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数就可以了。

3.9 解：根据提示，可以设计算法如下： #include #include \

int PairBracket( char *S) { //检查表达式中括号是否配对 int i; SeqStack T; //定义一个栈 InitStack (&T); for (i=0; i

if ( S[i]==')' ) Pop(&T); //遇')'时出栈 } return !EmptyStack(&T); // 由栈空否返回正确配对与否 }

3.10 解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：

//双向栈的栈结构类型与以前定义略有不同

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

//其余算法略 ,以上算法没有上机调试过，请学友自行验证一下。主要是我们理解了算法也就可以了。

3.11 解：算法如下

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 解：算法设计如下:

//存为Queue2.h文件

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

int EmptyQueue( CirQueue *Q) { //判队空 return Q->front==Q->rear; }

int FullQueue( CirQueue *Q)

{ // 判队满//如果尾指针加1后等于头指针，则认为满 return (Q->rear+1)%QueueSize== Q->front; }

Datatype DeQueue( CirQueue *Q) { //出队 if(EmptyQueue(Q)) Error(\队已空，无元素可以出队\ Datatype temp; temp=Q->Data[Q->front] ;//保存元素值 Q->front= ( Q->front+1 ) %QueueSize;//循环意义上的加1

return temp; //返回元素值 }

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

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

//为了验证上述算法是否正确，晓津设计了以下程序 //循环队列的定义 存入StructQ.h文件中

#define QueueSize 10 //为便与验证，这里假设为10个元素的空间 typedef char Datatype ; //设元素的类型为char型 typedef struct { int front; int rear; Datatype Data[QueueSize]; }CirQueue;

//以下是主程序,用来验证算法 #include #include

#include \包含队列结构 #include \包含算法头文件

//------------------出错控制程序 #include

void Error(char * message) { fprintf(stderr, \ exit(1); }

//------------------------主函数-----

void main( ) { int i; CirQueue Q;// 定义一个循环队列 InitQueue( &Q );//初始化队列 printf(\ for (i=0; i< QueueSize-1 ; i++) EnQueue(&Q, getchar()); printf(\ if(!EmptyQueue(&Q)) //先输出一个头元素 printf(\ printf(\ while(!EmptyQueue(&Q)) //如果非空就把队列中的元素输出 printf(\ printf(\ for(i=0; i

//上机时可以输入字符，也可以直接输入回车的次数来验证，注意：一个回车也是一个字符。 3.13 解：算法如下： //先定义链队结构:

typedef struct queuenode{ Datatype data; struct queuenode *next;

}QueueNode; //以上是结点类型的定义

typedef struct{ queuenode *rear;

}LinkQueue; //只设一个指向队尾元素的指针

//linkQ.h 相应算法

void InitQueue( LinkQueue *Q)

{ //置空队：就是使头结点成为队尾元素 Q->rear = Q->rear->next;//头结点成为尾结点 Q->rear->next = Q->rear;//形成循环链表 }

int EmptyQueue( LinkQueue *Q)