循环链表中如何判断完成遍历链表,分为有无头结点和只有一个rear指针的情形说明
时间: 2023-07-15 09:10:33 浏览: 69
1. 有头结点的循环链表
在有头结点的循环链表中,可以使用一个指针从头结点开始遍历,当指针回到头结点时,就完成了一次遍历。具体代码如下:
```
// 假设链表头结点为 head
Node *p = head->next; // 从第一个结点开始遍历
while (p != head) { // 当指针回到头结点时结束循环
// 遍历操作
p = p->next;
}
```
2. 只有一个rear指针的循环链表
在只有一个rear指针的循环链表中,可以使用一个指针从rear指针指向的结点开始遍历,直到指针回到rear指针所指向的结点时,就完成了一次遍历。具体代码如下:
```
// 假设只有一个rear指针指向链表尾结点
Node *p = rear->next; // 从第一个结点开始遍历
while (p != rear) { // 当指针回到尾结点时结束循环
// 遍历操作
p = p->next;
}
// 遍历尾结点
// 遍历操作
```
相关问题
假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的置空队、入队列和出队列,遍历的算法。
置空队:
```
void initQueue(LinkList rear){
rear->next = rear; //将队尾指针指向自己,表示队列为空
}
```
入队列:
```
void enQueue(LinkList rear, ElemType x){
LNode *p = (LNode*)malloc(sizeof(LNode)); //申请新结点
p->data = x;
p->next = rear->next; //新结点插入到队尾之后
rear->next = p;
rear = p; //更新队尾指针
}
```
出队列:
```
bool deQueue(LinkList rear, ElemType &x){
if(rear == rear->next){ //队列为空
return false;
}
LNode *p = rear->next->next; //找到队头元素的后继结点
x = p->data;
rear->next->next = p->next; //删除队头元素结点
if(p == rear){ //如果队列只有一个元素,更新队尾指针
rear = rear->next;
}
free(p); //释放结点
return true;
}
```
遍历:
```
void traverseQueue(LinkList rear){
if(rear == rear->next){
printf("队列为空");
return;
}
LNode *p = rear->next->next; //找到队头元素的后继结点
while(p != rear->next){ //遍历队列
printf("%d ", p->data);
p = p->next;
}
}
```
以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(不设头指针)。试编写相应的置空队列、判断队列是否为空、入队和出队 等算法。
### 回答1:
```C++
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
class Queue{
public:
Queue(){
rear = new Node;
rear->next = rear;
}
~Queue(){
Node* p = rear->next;
while(p != rear){
Node* q = p;
p = p->next;
delete q;
}
delete rear;
}
bool isEmpty(){
return rear->next == rear;
}
void makeEmpty(){
Node* p = rear->next;
while(p != rear){
Node* q = p;
p = p->next;
delete q;
}
rear->next = rear;
}
void enQueue(int x){
Node* p = new Node;
p->data = x;
p->next = rear->next;
rear->next = p;
rear = p;
}
int deQueue(){
if(isEmpty()){
cout<<"Queue is empty."<<endl;
exit(1);
}
else{
Node* p = rear->next->next;
int x = rear->next->data;
delete rear->next;
rear->next = p;
if(p == rear) rear = rear->next;
return x;
}
}
private:
Node* rear;
};
int main(){
Queue q;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout<<q.deQueue()<<endl;
cout<<q.deQueue()<<endl;
cout<<q.deQueue()<<endl;
q.enQueue(4);
q.enQueue(5);
cout<<q.deQueue()<<endl;
cout<<q.deQueue()<<endl;
q.makeEmpty();
cout<<q.isEmpty()<<endl;
return 0;
}
```
### 回答2:
以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点的算法如下:
置空队列的算法:
1. 创建一个空的循环链表,并在头结点上设置一个指针rear,指向NULL。
2. 如果rear指针不为空,则将rear指针置为NULL。
判断队列是否为空的算法:
1. 如果rear指针为空,则队列为空;否则,队列非空。
入队的算法:
1. 输入要插入的元素elem。
2. 创建一个新的结点newNode,并将elem保存到newNode的数据域中。
3. 如果rear指针为空,表示队列为空,则将newNode的指针域指向自身,同时将rear指针指向newNode。
4. 如果rear指针不为空,则将newNode的指针域指向rear指针指向的结点的指针域,然后将rear指针指向newNode。
5. 更新rear指针指向的结点的指针域,使其指向newNode。
出队的算法:
1. 如果rear指针为空,表示队列为空,则无法进行出队操作。
2. 如果rear指针指向的结点的指针域指向rear指针本身,表示队列中只有一个元素,则将rear指针置为NULL。
3. 否则,将rear指向的结点的指针域指向rear指针指向的结点的指针域。
以上是利用带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点的算法。
### 回答3:
以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(不设头指针)。可以通过以下算法实现相关操作:
1. 置空队列算法:
首先创建一个指向头结点的指针rear,将其指向自身即可。
2. 判断队列是否为空算法:
判断队尾指针rear是否指向自身,如果指向自身则说明队列为空。
3. 入队算法:
首先创建一个新的结点node,并将其数据设置为待入队的元素值。
如果队列为空,即rear指向自身,将rear指向node即可。
否则,将node的next指针指向rear的下一个结点,再将rear的next指针指向node,并将rear指向node。
4. 出队算法:
首先判断队列是否为空,如果为空,则无法出队,输出错误信息。
否则,将rear的next指针指向其下一个结点的下一个结点,即删除队尾元素所在的结点。
接着判断删除后队列是否为空,若不为空,则将rear指针指向删除后的队尾元素。
通过上述算法,可以实现带头结点的循环链表表示队列的置空、判断是否为空、入队和出队等操作。这样设计可以实现高效、方便的队列操作,并且不需要每次都遍历整个队列来查找队尾元素。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)