设计一个带头结点的单链表类,要求: (1)带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。 (2)设计一个测试主函数,实际运行验证所设计循环单链表类的正确性
时间: 2024-11-25 20:12:55 浏览: 6
创建一个带头节点的单链表类,我们可以将其命名为`HeaderLinkedList`,其主要功能和成员函数可以如下所示:
```cpp
class HeaderNode {
public:
int data;
HeaderNode* next;
};
class HeaderLinkedList {
private:
HeaderNode* head;
public:
// 构造函数
HeaderLinkedList() : head(nullptr) {}
// 取数据元素个数
int size() const {
int count = 0;
HeaderNode* current = head;
while (current != nullptr) {
count++;
current = current->next;
}
return count;
}
// 插入元素
void insert(int value) {
HeaderNode* newNode = new HeaderNode();
newNode->data = value;
newNode->next = head;
head = newNode;
}
// 删除所有值为k的元素
void removeAll(int k) {
if (head == nullptr || head->data != k) return; // 如果头节点不是k,直接返回
HeaderNode* prev = nullptr;
HeaderNode* current = head;
while (current != nullptr && current->data == k) {
prev = current;
current = current->next;
delete prev; // 释放当前节点内存
}
if (prev != nullptr) prev->next = current; // 更新前驱节点的next指针
else head = current; // 如果原头节点已删除,则新头节点为下一个非k节点
}
// 取数据元素
int getData() const {
if (head == nullptr) return -1; // 空链表,返回错误值
return head->data;
}
// 主要用于测试
friend void testList(HeaderLinkedList& list);
};
// 测试主函数
void testList(HeaderLinkedList& list) {
// 初始化并添加元素
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(2); // 插入重复元素
list.insert(4);
// 检查大小、获取数据和删除操作
cout << "Size: " << list.size() << endl;
cout << "Data at head: " << list.getData() << endl;
list.removeAll(2); // 删除值为2的所有节点
cout << "After removing all 2s, size: " << list.size() << endl;
}
int main() {
HeaderLinkedList list;
testList(list);
return 0;
}
```
在这个实现中,我们创建了一个带头节点的单链表,并提供了一些基本操作的实现。`testList`函数用于测试链表的基本功能。在`main`函数中,我们实例化了这个链表并进行了简单的操作演示。
阅读全文