编写一个程序,分别实现单链表的各种基本操作,要求:初始化单链表,建立单链表,求单链表的长度,按位置查找操作,按值查找操作,插入操作,删除操作,显示操作,最后编写一个主程序,分别调用上述几个函数实现相应得操作,c++
时间: 2024-09-14 14:15:10 浏览: 32
在C++中,单链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。以下是一个简单的单链表实现,包含了你要求的基本操作:
首先定义链表节点和链表类:
```cpp
#include <iostream>
// 定义链表节点
struct ListNode {
int data;
ListNode* next;
ListNode(int x) : data(x), next(nullptr) {}
};
// 定义单链表类
class SingleLinkedList {
private:
ListNode* head; // 链表头指针
public:
SingleLinkedList() : head(nullptr) {}
// 初始化单链表
void initialize() {
head = nullptr;
}
// 建立单链表(尾插法)
void createList(const std::initializer_list<int>& elements) {
for (auto it = elements.begin(); it != elements.end(); ++it) {
append(*it);
}
}
// 求单链表的长度
int getLength() const {
int length = 0;
ListNode* current = head;
while (current != nullptr) {
length++;
current = current->next;
}
return length;
}
// 按位置查找操作
ListNode* positionSearch(int position) const {
int index = 0;
ListNode* current = head;
while (current != nullptr && index < position) {
current = current->next;
index++;
}
return (index == position) ? current : nullptr;
}
// 按值查找操作
ListNode* valueSearch(int value) const {
ListNode* current = head;
while (current != nullptr && current->data != value) {
current = current->next;
}
return current;
}
// 插入操作
void insert(int position, int value) {
if (position < 0) return;
ListNode* newNode = new ListNode(value);
if (position == 0 || head == nullptr) {
newNode->next = head;
head = newNode;
} else {
ListNode* current = head;
for (int i = 0; current != nullptr && i < position - 1; ++i) {
current = current->next;
}
if (current == nullptr) return;
newNode->next = current->next;
current->next = newNode;
}
}
// 删除操作
void remove(int position) {
if (position < 0 || head == nullptr) return;
ListNode* current = head;
if (position == 0) {
head = head->next;
delete current;
} else {
ListNode* prev = nullptr;
for (int i = 0; current != nullptr && i < position; ++i) {
prev = current;
current = current->next;
}
if (current == nullptr) return;
prev->next = current->next;
delete current;
}
}
// 显示操作
void display() const {
ListNode* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
// 析构函数,用于释放链表内存
~SingleLinkedList() {
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next;
delete current;
current = next;
}
head = nullptr;
}
};
```
然后编写主程序调用上述函数:
```cpp
int main() {
SingleLinkedList list;
list.initialize(); // 初始化单链表
list.createList({1, 2, 3, 4, 5}); // 建立单链表
std::cout << "链表长度: " << list.getLength() << std::endl; // 显示链表长度
std::cout << "按位置查找: ";
ListNode* node = list.positionSearch(2); // 按位置查找
if (node != nullptr) {
std::cout << node->data << std::endl;
} else {
std::cout << "未找到" << std::endl;
}
std::cout << "按值查找: ";
node = list.valueSearch(3); // 按值查找
if (node != nullptr) {
std::cout << node->data << std::endl;
} else {
std::cout << "未找到" << std::endl;
}
list.display(); // 显示链表
list.insert(1, 9); // 插入操作
list.display(); // 显示链表
list.remove(2); // 删除操作
list.display(); // 显示链表
return 0;
}
```
这段代码展示了如何创建一个单链表,并实现了初始化、建立链表、求链表长度、按位置查找、按值查找、插入节点、删除节点和显示链表的功能。在主函数中,我们对这些操作进行了简单的测试。