循环单链表的建立、插入、删除和查找的各个算法程序
时间: 2024-09-23 17:14:25 浏览: 8
循环单链表是一种特殊的链表结构,节点的最后一个指针指向第一个节点,形成一个环形。以下是循环单链表的一些基本操作:
**建立(创建)循环单链表:**
1. 初始化一个头结点,其next指针通常初始化为头结点本身。
```cpp
struct Node {
int data;
Node* next;
};
Node* createCircularLinkedList() {
Node* head = new Node();
head->data = 0; // 或者设置初始值
head->next = head; // 将next指针指向自身形成循环
return head;
}
```
**插入操作:**
- 插入到头部:在新节点前面插入数据。
```cpp
void insertAtHead(Node*& head, int value) {
Node* newNode = new Node{value, head};
if (head == newNode) {
newNode->next = newNode; // 如果是头结点,也要形成循环
} else {
head->next = newNode;
}
head = newNode;
}
```
- 插入到尾部:遍历链表找到尾节点并插入。
```cpp
void insertAtTail(Node*& head, int value) {
if (!head) {
insertAtHead(head, value);
return;
}
Node* current = head;
while (current->next != head) {
current = current->next;
}
current->next = newNode = new Node{value, head}; // 新节点next指向前一个节点
newNode->next = head;
}
```
**删除操作:**
- 删除指定节点:首先找到目标节点,然后调整前一个节点的next指针跳过它。
```cpp
void deleteNode(Node*& head, int value) {
if (!head) return;
if (head->data == value) { // 如果是头节点
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
bool found = false;
while (!found && current->next != head) {
if (current->next->data == value) {
found = true;
current->next = current->next->next;
} else {
current = current->next;
}
}
if (found) {
delete current->next;
}
}
```
**查找操作:**
- 查找特定值的节点。
```cpp
Node* search(Node* head, int value) {
if (!head) return nullptr;
Node* current = head;
do {
if (current->data == value) return current;
current = current->next;
} while (current != head); // 循环链表需特殊处理
return nullptr;
}
```