Question

用循环单链表实现循环队列,如何写出插入和删除的算法？

Answer 1

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;           

}  

}

循环单链表是单链表的另一种形式，其结构特点链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。和单链表相同，循环链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作较为方便。