本文已使用 Google Cloud Translation API 自动翻译。
某些文档最好以原文阅读。
循环链表是链表的变体,其中最后一个节点指向第一个节点(或头节点)而不是指向空。即它是一个尾节点指向头节点的链表。
循环链表是一种包含节点序列的数据结构。每个节点包含两个字段:
循环链表的最后一个节点指向第一个节点(或头节点)。这使得循环链表成为一个循环的数据结构。
正如您在上图中看到的,最后一个节点(节点 4)指向第一个节点(节点 1)。
循环链表支持以下操作:
循环链表与其他数据结构相比有以下优点:
循环链表有以下缺点:
您可以在列表的开头、结尾或中间的任何位置插入新节点。
开头插入:
void insertAtBeginning(int data) {
// Create a new node
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
// Set the next field of the new node to point to the head node
newNode->next = head;
// Set the next field of the last node to point to the new node
if(head != NULL) {
struct Node* temp = head;
while(temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
} else {
// If the list is empty, set the new node as the head node
newNode->next = newNode;
}
// Set the new node as the head node
head = newNode;
}
最后插入:
void insertAtEnd(int data) {
// Create a new node
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
// Set the next field of the new node to point to the head node
newNode->next = head;
// If the list is empty, set the new node as the head node
if(head == NULL) {
head = newNode;
} else {
// Set the next field of the last node to point to the new node
struct Node* temp = head;
while(temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
}
}
中间插入:
void insertInMiddle(int data, int position) {
// Create a new node
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
// Set the next field of the new node to point to the head node
newNode->next = head;
// If the list is empty, set the new node as the head node
if(head == NULL) {
head = newNode;
} else {
// Find the node at the given position
struct Node* temp = head;
int i;
for(i=0; i<position-1; i++) {
temp = temp->next;
}
// Set the next field of the new node to point to the node at the given position
newNode->next = temp->next;
// Set the next field of the node at the given position to point to the new node
temp->next = newNode;
}
}
您可以从列表的开头、结尾或中间的任何位置删除节点。
从头开始删除:
void deleteFromBeginning() {
// If the list is empty, return
if(head == NULL) {
return;
}
// Find the last node
struct Node* temp = head;
while(temp->next != head) {
temp = temp->next;
}
// Set the next field of the last node to point to the head node
temp->next = head->next;
// Free the memory occupied by the head node
free(head);
// Set the head node to the node at the given position
head = temp->next;
}
从末尾删除:
void deleteFromEnd() {
// If the list is empty, return
if(head == NULL) {
return;
}
// Find the last node
struct Node* temp = head;
while(temp->next != head) {
temp = temp->next;
}
// Set the next field of the last node to point to the head node
temp->next = head;
// Free the memory occupied by the last node
free(temp);
}
从中间删除:
void deleteFromMiddle(int position) {
// If the list is empty, return
if(head == NULL) {
return;
}
// Find the node at the given position
struct Node* temp = head;
int i;
for(i=0; i<position-1; i++) {
temp = temp->next;
}
// Set the next field of the node at the given position to point to the node at the given position
struct Node* toBeDeleted = temp->next;
// Set the next field of the node at the given position to point to the node at the given position
temp->next = toBeDeleted->next;
// Free the memory occupied by the node at the given position
free(toBeDeleted);
}
您可以在列表中搜索特定节点。
void search(int data) {
// If the list is empty, return
if(head == NULL) {
return;
}
// Find the node with the given data
struct Node* temp = head;
int position = 1;
while(temp->next != head) {
if(temp->data == data) {
break;
}
temp = temp->next;
position++;
}
// If the data is not found, return
if(temp->data != data) {
return;
}
// Print the data
printf("%d", temp->data);
}
您可以遍历列表以打印每个节点中存储的数据。
void traverse() {
// If the list is empty, return
if(head == NULL) {
return;
}
// Print the data in each node
struct Node* temp = head;
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp != head);
}
编写程序创建一个循环链表,并在链表的开头、结尾和中间插入节点。
编写程序删除链表的开头、结尾和中间的节点。
编写一个程序来搜索列表中的特定节点。
编写程序遍历链表,打印每个节点存储的数据。