数据结构算法设计题详解

木来 木来

52、如果用一个循环数组q[0..m-1]表示队列时,该队列只有一个队列头指针front,不设队列尾指针rear,而改置计数器count用以记录队列中结点的个数。

(1)编写实现队列的三个基本运算:判空、入队、出队

(2)队列中能容纳元素的最多个数是多少?

解析:

(1)

typedef struct

{elemtp q[m];

 intfront,count;  //front是队首指针,count是队列中元素个数。

}cqnode;           //定义类型标识符。

(1)判空:int Empty(cqnode  cq)                       //cq是cqnode类型的变量 

{if(cq.count==0) return(1);elsereturn(0);  //空队列}

入队:int EnQueue(cqnode cq,elemtpx)

{if(count==m){printf(“队满\n”);exit(0);}

             cq.q[(cq.front+count)%m]=x;    //x入队

             count++; return(1);            //队列中元素个数增加1,入队成功。

}

出队:int DelQueue(cqnode cq)

{if (count==0){printf(“队空\n”);return(0);}

 printf(“出队元素”,cq.q[cq.front]);

 x=cq.q[cq.front];

cq.front=(cq.front+1)%m;  //计算新的队头指针。

return(x)

}

(2) 队列中能容纳的元素的个数为m。


 

53、已知队列 Q 以链队列存储。写出 Q 的存储结构类型描述,并试编写算法实现将元素 x 插入队列 Q 的入队操作EnQueue(Q,x)。

 

 typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
 
typedef struct{
QueuePtr front;
QueurPtr rear;
}LinkQueue;
 
Status EnQueue(LinkQueue &Q,QElemTypex){
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(overflow);
 
p->data=x;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
0 条评论