用c++编写带头结点链表实现。
时间: 2024-09-24 08:23:08 浏览: 19
在 C++ 中,我们可以使用结构体(struct)和指针来实现带头结点的链表。首先,我们定义一个 Node 结构体,它包含数据域和指向下一个节点的指针:
```cpp
// 定义头节点和普通节点
struct ListNode {
int val; // 数据域,存储整数值
ListNode* next; // 指针,指向下一个节点
ListNode(int x) : val(x), next(NULL) {} // 构造函数,初始化值和next指针
};
```
然后,我们创建一个 LinkedList 类来管理这个链表,包括添加、删除、查找等基本操作:
```cpp
class LinkedList {
private:
ListNode* head; // 头节点指针
public:
// 初始化一个空链表
LinkedList() : head(nullptr) {}
// 添加新元素到链表末尾
void addNode(int value) {
if (!head) {
head = new ListNode(value);
} else {
ListNode* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = new ListNode(value);
}
}
// 删除指定位置的节点,如果不存在则不做任何操作
void removeNode(int value) {
if (head == nullptr || head->val != value) return;
ListNode* temp = head;
head = head->next;
delete temp;
return;
}
// 查找节点是否存在,返回 true 或 false
bool contains(int value) const {
ListNode* current = head;
while (current != nullptr) {
if (current->val == value) {
return true;
}
current = current->next;
}
return false;
}
// 其他操作...
};
```