数据结构(C语言第2版) 课后习题答案之 第三章 栈和队列

目录

第3章  栈和队列

1．选择题

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

（3）设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。

（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。

（5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

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

（7）假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。

试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

(8）如果允许在循环队列的两端都可以进行插入和删除操作。要求：

（9）已知Ackermann函数定义如下:

（10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：

第3章  栈和队列 1．选择题

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（  ）种情况。

A．5，4，3，2，1   B．2，1，5，4，3    C．4，3，1，2，5    D．2，3，5，4，1

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（  ）。

    A．i               B．n-i               C．n-i+1            D．不确定

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（  ）。

A．r-f             B．(n+f-r)%n       C．n+r-f           D．（n+r-f)%n

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（  ）。

A．x=top->data;top=top->link；   B．top=top->link;x=top->link；    

C．x=top;top=top->link；       D．x=top->link；

（5）设有一个递归算法如下

        int fact(int n) {  //n大于等于0

             if(nrear!=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;//摘下结点pfree(p);//释放被删结点return x;}

（7）假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。 试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

【解答】循环队列类定义

#include 

template class Queue { //循环队列的类定义

public:

   Queue ( int=10 );

   ~Queue ( ) { delete [ ] Q; }

   void EnQueue ( Type & item );

   Type DeQueue ( );

   Type GetFront ( );

   void MakeEmpty ( ) { front = rear = tag = 0; } //置空队列

   int IsEmpty ( ) const { return front == rear && tag == 0; } //判队列空否

   int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否

private:

   int rear, front, tag; //队尾指针、队头指针和队满标志

   Type *Q; //存放队列元素的数组

   int m; //队列最大可容纳元素个数

}

构造函数

template

Queue:: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) {

//建立一个最大具有m个元素的空队列。

   Q = new Type[m]; //创建队列空间

   assert ( Q != 0 ); //断言: 动态存储分配成功与否

}

插入函数

template

void Queue :: EnQueue ( Type &item ) {

assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理

rear = ( rear + 1 ) % m; //队尾位置进1, 队尾指针指示实际队尾位置

Q[rear] = item; //进队列

tag = 1; //标志改1，表示队列不空

}

删除函数

template

Type Queue :: DeQueue ( ) {

assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理

front = ( front + 1 ) % m; //队头位置进1, 队头指针指示实际队头的前一位置

tag = 0; //标志改0, 表示栈不满

return Q[front]; //返回原队头元素的值

}

读取队头元素函数

template

Type Queue :: GetFront ( ) {

assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理

return Q[(front + 1) % m]; //返回队头元素的值

}

(8）如果允许在循环队列的两端都可以进行插入和删除操作。要求：

① 写出循环队列的类型定义；

② 写出“从队尾删除”和“从队头插入”的算法。

[题目分析] 用一维数组 v[0..M-1]实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。

（1）#define M  队列可能达到的最大长度

typedef struct

  { elemtp data[M];

    int front,rear;

  } cycqueue;

（2）elemtp delqueue ( cycqueue Q)

     //Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。

{ if (Q.front==Q.rear)  {printf(“队列空”); exit(0);}

   Q.rear=(Q.rear-1+M)%M;          //修改队尾指针。

        return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。

}//从队尾删除算法结束

void enqueue (cycqueue Q, elemtp x)

// Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。

{if (Q.rear==(Q.front-1+M)%M)  {printf(“队满”; exit(0);)

 Q.data[Q.front]=x;        //x 入队列

Q.front=(Q.front-1+M)%M;    //修改队头指针。

}// 结束从队头插入算法。

（9）已知Ackermann函数定义如下:

   

① 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。

② 写出计算Ack(m,n)的非递归算法。

int Ack(int m,n)

    {if (m==0) return(n+1);

     else if(m!=0&&n==0) return(Ack(m-1,1));

         else return(Ack(m-1,Ack(m,m-1));

     }//算法结束

（1）Ack(2,1)的计算过程

     Ack(2,1)=Ack(1,Ack(2,0))           //因m0,n0而得

            =Ack(1,Ack(1,1))            //因m0,n=0而得

            =Ack(1,Ack(0,Ack(1,0)))     // 因m0,n0而得

            = Ack(1,Ack(0,Ack(0,1)))    // 因m0,n=0而得

            =Ack(1,Ack(0,2))            // 因m=0而得

            =Ack(1,3)                   // 因m=0而得

            =Ack(0,Ack(1,2))            //因m0,n0而得

            = Ack(0,Ack(0,Ack(1,1)))    //因m0,n0而得

            = Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m0,n0而得

            = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m0,n=0而得

            = Ack(0,Ack(0,Ack(0,2)))    //因m=0而得

            = Ack(0,Ack(0,3))           //因m=0而得

            = Ack(0,4)                  //因n=0而得

            =5                          //因n=0而得

（2）int Ackerman( int m, int n)

       {int akm[M][N];int i,j;

        for(j=0;j> value; //再输入

}

current->link = NULL; //链尾封闭

}

void List :: PrintList ( ) { //输出链表

cout data; //递归结束条件

int temp = Max ( f ->link ); //在当前结点的后继链表中求最大值

if ( f ->data > temp ) return f ->data; //如果当前结点的值还要大, 返回当前检点值

else return temp; //否则返回后继链表中的最大值

}

int List :: Num ( ListNode *f ) { //递归算法 : 求链表中结点个数

if ( f == NULL ) return 0; //空表, 返回0

return 1+ Num ( f ->link ); //否则, 返回后继链表结点个数加1

}

float List :: Avg ( ListNode *f , int& n ) { //递归算法 : 求链表中所有元素的平均值

if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件

{ n = 1;  return ( float ) (f ->data ); }

else { float Sum = Avg ( f ->link, n ) * n;  n++;  return ( f ->data + Sum ) / n; }

}

#include "RecurveList.h" //定义在主文件中

int main ( int argc, char* argv[ ] ) {

List test;   int finished;

cout > finished; //输入建表结束标志数据

test.NewList ( finished ); //建立链表

test.PrintList ( ); //打印链表

cout