数据结构链表的C++实现

在C++中实现链表是一种常见的练习，有助于理解指针和动态内存分配的概念。下面是一个简单的单向链表（Singly Linked List）的实现示例，包括基本的操作如插入、删除和遍历。

单向链表 (Singly Linked List) 实现

1. 定义节点结构

首先定义一个节点结构体，包含数据部分和指向下一个节点的指针。

cpp

深色版本

#include <iostream>
using namespace std;// 定义节点结构
struct Node {int data;Node* next;
};

2. 链表类定义

接下来定义一个链表类，包含链表的基本操作：插入、删除、查找和打印。

cpp

深色版本

class LinkedList {
public:Node* head;// 构造函数初始化头节点为NULLLinkedList() : head(nullptr) {}// 插入节点到链表末尾void append(int value) {Node* newNode = new Node();newNode->data = value;newNode->next = nullptr;if (head == nullptr) {head = newNode;} else {Node* temp = head;while (temp->next != nullptr) {temp = temp->next;}temp->next = newNode;}}// 在指定位置插入节点void insertAt(int index, int value) {Node* newNode = new Node();newNode->data = value;if (index == 0) {newNode->next = head;head = newNode;} else {Node* temp = head;for (int i = 0; temp != nullptr && i < index - 1; i++) {temp = temp->next;}if (temp == nullptr || temp->next == nullptr) {cout << "Index out of bounds" << endl;return;}newNode->next = temp->next;temp->next = newNode;}}// 删除指定值的节点void deleteValue(int value) {if (head == nullptr) {cout << "List is empty" << endl;return;}if (head->data == value) {Node* temp = head;head = head->next;delete temp;return;}Node* temp = head;while (temp->next != nullptr && temp->next->data != value) {temp = temp->next;}if (temp->next == nullptr) {cout << "Value not found" << endl;return;}Node* nodeToDelete = temp->next;temp->next = temp->next->next;delete nodeToDelete;}// 查找指定值的节点bool search(int value) {Node* temp = head;while (temp != nullptr) {if (temp->data == value) {return true;}temp = temp->next;}return false;}// 打印链表void printList() {Node* temp = head;while (temp != nullptr) {cout << temp->data << " -> ";temp = temp->next;}cout << "NULL" << endl;}
};

3. 测试链表功能

最后，编写一个主函数来测试上述实现的功能。

cpp

深色版本

int main() {LinkedList list;// 插入一些节点list.append(1);list.append(2);list.append(3);// 打印链表cout << "Initial list: ";list.printList();// 在索引1处插入新节点list.insertAt(1, 4);cout << "After inserting at index 1: ";list.printList();// 删除值为2的节点list.deleteValue(2);cout << "After deleting value 2: ";list.printList();// 查找值为3的节点if (list.search(3)) {cout << "Value 3 found in the list." << endl;} else {cout << "Value 3 not found in the list." << endl;}return 0;
}

运行结果示例

假设你运行了上述代码，输出可能会如下所示：

深色版本

Initial list: 1 -> 2 -> 3 -> NULL
After inserting at index 1: 1 -> 4 -> 2 -> 3 -> NULL
After deleting value 2: 1 -> 4 -> 3 -> NULL
Value 3 found in the list.

这个示例展示了如何创建一个单向链表，并实现了插入、删除、查找和打印链表的基本功能。