首页 > 试题广场 >

假定用一个单循环链表来表示队列(也称为循环队列),该队列只设

[问答题]
假定用一个单循环链表来表示队列(也称为循环队列),该队列只设一个队尾指针,不设队首指针,试编写下列各种运算的算法:
1)向循环链队列插入一个元素值为x的结点;
2)从循环链队列中删除一个结点。

本题是对一个循环链队列做插入和删除运算,假设不需要保留被删结点的值和不需要回收结点,算法描述如下:
(1)插入(即入队)算法:
insert(LinkList *rear, elemtype x)
{  //设循环链队列的队尾指针为rear,x为待插入的元素
LinkList *p;
p=(LinkList *)malloc(sizeof(LinkList));
if(rear= =NULL)  //如为空队,建立循环链队列的第一个结点
{  rear=p;
rear->next=p;   //链接成循环链表
}
else  //否则在队尾插入p结点
{  p->next=rear->next;
rear->next=p;
rear=p;
}
}
(2)删除(即出队)算法:
delete(LinkList  *rear)
{  //设循环链队列的队尾指针为rear
if (rear= =NULL)  //空队
printf("underflow\n");
if(rear->next= =rear)  //队中只有一个结点
rear=NULL;
else
rear->next=rear->next->next;  //rear->next指向的结点为循环链队列的队头结点
}
发表于 2017-07-31 13:44:23 回复(1)