3. 设计实现单链表,具备基本的增、删、改、查功能,要求使用到new、delete及引用,并进行必要的测试。
时间: 2024-09-10 15:25:28 浏览: 41
java实现单链表增删改查的实例代码详解
在设计一个简单的单链表数据结构时,我们需要创建几个关键类:节点(Node)、链表(LinkedList),以及提供操作方法的链表管理类。这里是一个基础的C++实现:
```cpp
// 定义链表节点
class Node {
public:
int data;
Node* next;
// 构造函数
Node(int value) : data(value), next(nullptr) {}
};
// 链表类
class LinkedList {
private:
Node* head; // 头结点
public:
// 初始化链表
LinkedList() : head(nullptr) {}
// 插入新元素
void insert(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
// 删除指定位置的节点(假设按0索引计数)
void remove(int index) {
if (index < 0 || index >= size()) return;
if (index == 0) {
Node* temp = head;
head = head->next;
delete temp;
} else {
Node* current = head;
for (int i = 0; i < index - 1 && current != nullptr; ++i) {
current = current->next;
}
if (current != nullptr) {
Node* temp = current->next;
current->next = temp->next;
delete temp;
}
}
}
// 修改元素值
void update(int index, int newValue) {
if (index < 0 || index >= size()) return;
Node* current = head;
for (int i = 0; i < index; ++i) {
current = current->next;
}
current->data = newValue;
}
// 查找元素
bool search(int value) const {
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
return true;
}
current = current->next;
}
return false;
}
// 获取链表长度
int size() const {
int count = 0;
Node* current = head;
while (current != nullptr) {
++count;
current = current->next;
}
return count;
}
};
// 测试部分
int main() {
LinkedList list;
list.insert(10);
list.insert(20);
list.insert(30);
std::cout << "Size: " << list.size() << std::endl;
std::cout << "Search 20: " << (list.search(20) ? "Found" : "Not Found") << std::endl;
list.update(1, 50);
std::cout << "Updated value at position 1: " << list.head->data << std::endl;
list.remove(0);
std::cout << "After removing first element: ";
printList(list); // 自定义打印链表的函数
return 0;
}
```
在这个例子中,`printList`函数用于显示链表的内容,但它未在此处列出。完成上述核心功能后,你可以编写更多的测试用例来验证链表的各种操作是否正确。
阅读全文