数据结构(C语言版)课后习题答案 下载本文

}

(2) 判队空

int EmptyQueue( LinkQueue *Q)

{ //判队空。当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; }

(3) 入队

void EnQueue( LinkQueue *Q, Datatype x) { //入队。也就是在尾结点处插入元素 QueueNode *p=new 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(\

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;//摘下结点p delete p;//释放被删结点 return x; }

XXI

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

[算法描述] (1)初始化

SeQueue QueueInit(SeQueue Q) {//初始化队列

Q.front=Q.rear=0; Q.tag=0; return Q; } (2)入队

SeQueue QueueIn(SeQueue Q,int e) {//入队列

if((Q.tag==1) && (Q.rear==Q.front)) cout<<\队列已满\else

{Q.rear=(Q.rear+1) % m; Q.data[Q.rear]=e;

if(Q.tag==0) Q.tag=1; //队列已不空 } return Q; } (3)出队

ElemType QueueOut(SeQueue Q) {//出队列

if(Q.tag==0) { cout<<\队列为空\else

{Q.front=(Q.front+1) % m; e=Q.data[Q.front];

if(Q.front==Q.rear) Q.tag=0; //空队列 }

return(e); }

(8)如果允许在循环队列的两端都可以进行插入和删除操作。要求: ① 写出循环队列的类型定义;

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

[题目分析] 用一维数组 v[0..M-1]实现循环队列,其中M是队列长度。设队头指针 front和队尾指针rear,约定front指向队头元素的前一位置,rear指向队尾元素。定义

XXII

front=rear时为队空,(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展,队尾端入队向下标大的方向发展。

[算法描述] ①

#define M 队列可能达到的最大长度 typedef struct {elemtp data[M]; int front,rear; }cycqueue; ②

elemtp delqueue ( cycqueue Q)

//Q是如上定义的循环队列,本算法实现从队尾删除,若删除成功,返回被删除元素,

否则给出出错信息。

{if (Q.front==Q.rear) { cout<<\队列空\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) { cout<<\队满\ 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)); }//算法结束

① Ack(2,1)的计算过程

XXIII

Ack(2,1)= Ack(1,Ack(2,0)) //因m<>0,n<>0而得 ②

int Ackerman(int m, int n) {int akm[M][N];int i,j;

for(j=0;j

{akm[i][0]=akm[i-1][1]; for(j=1;j

akm[i][j]=akm[i-1][akm[i][j-1]]; }

return(akm[m][n]); }//算法结束

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

① 求链表中的最大整数; ② 求链表的结点个数; ③ 求所有整数的平均值。 [算法描述]

int GetMax(LinkList p) {

= Ack(1,Ack(1,1)) //因m<>0,n=0而得 = Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得 = Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得 = Ack(1,Ack(0,2)) // 因m=0而得 = Ack(1,3) // 因m=0而得 = Ack(0,Ack(1,2)) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,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而得

if(!p->next) else

XXIV

return p->data;