.设计一个带头结点的单链表类,要求: (1)带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。 (2)设计一个测试主函数,实际运行验证所设计循环单链表类的正确性。
时间: 2024-12-06 19:24:30 浏览: 21
ShiYan1_单链表_C++_顺序表_数据结构_
5星 · 资源好评率100%
设计一个带头结点的单链表类(Head-Referenced Linked List),可以按照以下步骤进行:
```cpp
// 首先,我们定义链表节点结构体
struct Node {
int data; // 数据域
Node* next; // 指向下一个节点的指针
};
// 然后,创建链表类
class LinkedList {
public:
// 构造函数,初始化头节点为nullptr
LinkedList() : head(nullptr), size(0) {}
// 取数据元素个数
int getCount() const {
return size;
}
// 插入元素
void insert(int value) {
if (head == nullptr) {
head = new Node{value, nullptr};
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = new Node{value, nullptr};
}
size++;
}
// 删除所有值为k的元素
void removeElements(int k) {
if (head == nullptr) {
return;
}
Node* temp = head, *prev = nullptr;
while (temp != nullptr && temp->data == k) {
prev = temp;
temp = temp->next;
delete prev;
}
if (temp == nullptr) { // 如果链表中没有值为k的元素,则直接返回
return;
}
while (temp->next != nullptr && temp->next->data != k) {
prev = temp;
temp = temp->next;
}
if (temp->next != nullptr) {
prev->next = temp->next;
} else {
// 如果链表尾部是值为k的元素
delete temp;
}
size -= (temp == nullptr); // 减去删除的元素个数
}
// 取数据元素
int getElement(int index) const {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range");
}
Node* current = head;
for (int i = 0; i < index; ++i) {
current = current->next;
}
return current->data;
}
private:
Node* head; // 链表头节点
int size; // 链表元素个数
// 防止直接复制构造和赋值操作,以维护数据完整性
LinkedList(const LinkedList&) = delete;
LinkedList& operator=(const LinkedList&) = delete;
};
// 测试主函数
int main() {
LinkedList list;
// 测试插入元素
list.insert(5);
list.insert(10);
list.insert(15);
// 打印初始链表长度
std::cout << "Initial list length: " << list.getCount() << std::endl;
// 删除所有值为10的元素并检查长度变化
list.removeElements(10);
std::cout << "After removing elements with value 10: " << list.getCount() << std::endl;
// 获取和打印特定索引的元素
try {
std::cout << "Element at index 1: " << list.getElement(1) << std::endl;
} catch (std::out_of_range& e) {
std::cerr << e.what() << std::endl;
}
// 清理内存
delete list.head;
return 0;
}
```
这个示例展示了如何设计一个带头结点的单链表类,并提供了一个简单的测试主函数来验证其功能。请注意,在实际项目中,可能需要添加更多错误处理和内存管理功能。
阅读全文