设计一个循环单链表:实现循环单链表的初始化、求元素个数、插入、删 除、取元素操作;设计一个测试主函数验证设计的循环单链表的正确性
时间: 2024-10-15 10:30:07 浏览: 57
循环单链表是一种特殊的链表结构,其中最后一个节点指向第一个节点,形成一个环形。以下是实现循环单链表的一些基本操作:
1. **初始化**:
- 定义一个`Node`类,包含数据域`data`和指针域`next`。
```cpp
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(this) {} // 循环链表构造,使得下一个节点指向自身
};
```
2. **求元素个数**:
- 创建一个`size`方法,通过遍历链表直到找到循环的开始。
```cpp
int size(Node* head) {
int count = 0;
Node* current = head;
while (current != head->next) {
++count;
current = current->next;
}
return count;
}
```
3. **插入**:
- 分为头部插入和中间插入:
- `insertAtHead`: 新节点指向头节点,然后头节点的next指向新节点。
- `insertAtPosition`: 找到目标位置并更新指针。
```cpp
void insertAtHead(Node*& head, int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
void insertAtPosition(Node*& head, int position, int value) {
if (position <= 0) insertAtHead(head, value);
else {
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; ++i)
current = current->next;
if (current == nullptr) return;
Node* newNode = new Node(value);
newNode->next = current->next;
current->next = newNode;
}
}
```
4. **删除**:
- 删除指定位置的节点,同样处理边界情况。
```cpp
void removeAtPosition(Node*& head, int position) {
if (position <= 0) {
if (head == head->next) { // 如果只有一个节点
head = nullptr;
delete head;
} else {
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; ++i)
current = current->next;
if (current == nullptr) return;
current->next = current->next->next;
delete current->next;
}
} else {
Node* current = head;
for (int i = 0; i < position; ++i)
current = current->next;
if (current == nullptr) return;
current->next = current->next->next;
delete current->next;
}
}
```
5. **取元素**:
- 根据位置获取元素,如果越界则返回默认值或抛异常。
```cpp
int get(int position, Node* head = head) {
if (position <= 0) return -1; // 越界处理
int index = 0;
Node* current = head;
while (index < position) {
if (current == nullptr) return -1;
current = current->next;
++index;
}
return current->data;
}
```
**测试主函数**:
```cpp
int main() {
Node* list = new Node(1); // 初始化一个单节点链表
insertAtHead(list, 2);
insertAtPosition(list, 0, 3);
cout << "Size: " << size(list) << endl;
cout << "Get element at position 0: " << get(0) << endl;
cout << "Insert at position 2: New element is " << get(2) << endl;
removeAtPosition(list, 1);
// 验证循环单链表是否正常
// ...
delete list;
return 0;
}
```
测试主函数中应包括更多的插入、删除和获取操作,并检查结果是否符合预期。你可以通过比较实际结果和预设的期望值来验证循环单链表的正确性。
阅读全文