好文档 - 专业文书写作范文服务资料分享网站

(完整版)数据结构(C语言版)第三四章习题答案

天下 分享 时间: 加入收藏 我要投稿 点赞

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, 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(\

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 free(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; } private:

int rear, front, tag; Type *Q; int m; }

//队尾指针、队头指针和队满标志

//存放队列元素的数组 //队列最大可容纳元素个数

//循环队列的类定义

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

构造函数

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; Q[rear] = item; tag = 1;

//判队列是否不满,满则出错处理

//队尾位置进1, 队尾指针指示实际队尾位置 //进队列

//标志改1,表示队列不空

位置

删除函数

template

Type Queue :: DeQueue ( ) {

assert ( ! IsEmpty ( ) ); front = ( front + 1 ) % m; tag = 0;

//判断队列是否不空,空则出错处理

//队头位置进1, 队头指针指示实际队头的前一//标志改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)) //因m<>0,n<>0而得 =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而得 (2)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为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算

的递归算法:

① 求链表中的最大整数;

② 求链表的结点个数; ③ 求所有整数的平均值。

#include class List;

//链表结点类

class ListNode { friend class List; private:

}; class List { private:

};

ListNode* List :: NewNode ( const int item ) {

}

void List :: NewList ( const int retvalue ) {

cout << \; cin >> value;

while ( value != retvalue ) {

q = NewNode ( value );

//建立链表, 以输入retvalue结束

//提示

first = NULL; int value; ListNode *q;

//输入 //输入有效

//建立包含value的新结点

ListNode *newnode = new ListNode (item); return newnode;

//创建新链表结点

ListNode *first, current; int Max ( ListNode *f ); int Num ( ListNode *f );

float Avg ( ListNode *f, int& n ); List ( ) : first(NULL), current (NULL) { } ~List ( ){ }

ListNode* NewNode ( const int item ); void NewList ( const int retvalue ); void PrintList ( );

//构造函数

//链表类

int data;

//结点数据 //结点指针

ListNode *link;

//定义在头文件\中

ListNode ( const int item ) : data(item), link(NULL) { } //构造函数

public:

//析构函数

//创建链表结点, 其值为item //建立链表, 以输入retvalue结束 //输出链表所有结点数据 //求链表所有数据的最大值 //求链表中数据个数 //求链表所有数据的平均值

int GetMax ( ) { return Max ( first ); } int GetNum ( ) { return Num ( first ); } float GetAvg ( ) { return Avg ( first ); }

(完整版)数据结构(C语言版)第三四章习题答案

Q->rear=Q->rear->next;//将队尾指针指向头结点while(Q->rear!=Q->rear->next)//当队列非空,将队中元素逐个出队{s=Q->rear->next;Q->rear->next=s->next;free(s);}//回收结点空间}(
推荐度:
点击下载文档文档为doc格式
1xz2g04jz27px008twlp8xswm2yhdw015k1
领取福利

微信扫码领取福利

微信扫码分享