Question

用循环单链表实现循环队列,写出插入,和删除的算法,只要这两个函数的算法就行了，有头尾指针。

主函数什么的都不用写,只写这两个算法!急!急!急!

Answer 1

先写个循环链表的实现
然后 C++ 用继承
C就组合吧,下面写个C的实现
typedef struct CircleListNode{
Datatype d;
struct CircleList *pre,*nxt;
}*CircleList,CirListNode;

typedef struct

{
CircleList Head;
int num;
}CircleQueue;

void insertFront(CircleList *L,d);

{
if(!L)return NULL;
if(*L==NULL)
{
*L=(CircleList) malloc(sizeof(CirListNode));
*L->nxt= *L->pre=*L ;
*L->d=d;
}
else
{

CircleList p =(CircleList) malloc(sizeof(CirListNode));
p->nxt=*L;
p->pre=*L->pre;
*L->pre->nxt=p;
*L->pre=p;
*L=p;
}
}
void DeleteBack(CircleList *L)
{ CircleList r=*L->pre;
if(*L->nxt =*L){ free(*L);*L=NULL;return ;}

r->pre->nxt =*L;
*L->pre=r->pre;

free(r);

}

void InsertQueue(CircleQueue *que, Datatype d)
{
if(!que)return;
insertFront(&que->Head,d);
que->num ++;

}
void DeletQueue(CircleQueue *que)
{
if(que->num>0)
{
DeleteBack(&que->Head);
que->num--;
}
}

void InitQueue(CircleQueue *que)
{
if(!que)return;
que->Head=NULL;
que->num=0;
}

Datatype * GetBackData(const CircleQueue *que)
{
if(!que)return NULL;
if(!que->Head)return NULL;
if(que->num<=0)return NULL;
return &(que->Head->pre->d);
}

void ClearQueue(CircleQueue *que)
{
if(!que)return ;
while(que->num>0)
{
DeletQueue(que);
}
}

Answer 2

/**************************************************************************************
*函数名称：insert
*函数功能：在链表中插入元素.
*输入：head 链表头指针，p新元素插入位置，x 新元素中的数据域内容
*返回值：无
*************************************************************************************/
void insert(Node * head,int p,int x){
Node * tmp = head;
//for循环是为了防止插入位置超出了链表长度
for(int i = 0;i<p;i++)
{
if(tmp == NULL)
return ;
if(i<p-1）
tmp = tmp->next;
}
Node * tmp2 = new Node;
tmp2->data = x;
tmp2->next = tmp->next;
tmp->next = tmp2;
}
/**************************************************************************************
*函数名称：del
*函数功能：删除链表中的元素
*输入：head 链表头指针，p 被删除元素位置
*返回值：被删除元素中的数据域.如果删除失败返回-1
**************************************************************************************/
int del(Node * head,int p){
Node * tmp = head;
for(int i = 0;i<p;i++)
{
if(tmp == NULL)
return -1;
if(i<p-1）
tmp = tmp->next;
}
int ret = tmp->next->data;
tmp->next = tmp->next->next;
return ret;
}

追问

我说的是循环队列不是链表,循环队列的链式结构。循环队列只在表头删除,表尾插入。

追答

① 置队空
void InitQueue(CirQueue *Q)
{
Q->front=Q->rear=0;
Q->count=0; //计数器置0
}
② 判队空
int QueueEmpty(CirQueue *Q)
{
return Q->count==0; //队列无元素为空
}
③ 判队满
int QueueFull(CirQueue *Q)
{
return Q->count==QueueSize; //队中元素个数等于QueueSize时队满
}
④ 入队
void EnQueue(CirQueuq *Q,DataType x)
{
if(QueueFull(Q))
Error("Queue overflow"); //队满上溢
Q->count ++; //队列元素个数加1
Q->data[Q->rear]=x; //新元素插入队尾
Q->rear=(Q->rear+1)%QueueSize; //循环意义下将尾指针加1
⑤ 出队
DataType DeQueue(CirQueue *Q)
{
DataType temp;
if(QueueEmpty(Q))
Error("Queue underflow"); //队空下溢
temp=Q->data[Q->front];
Q->count--; //队列元素个数减1
Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1
return temp;
}