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

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

1. 界说节点结构

起首界说一个节点结构体，包罗数据部分和指向下一个节点的指针。

1. [/code] cpp
2. 深色版本
3. [code]#include <iostream>
4. using namespace std;
6. // 定义节点结构
7. struct Node {
8.     int data;
9.     Node* next;
10. };

复制代码

2. 链表类界说

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

1. [/code] cpp
2. 深色版本
3. [code]class LinkedList {
4. public:
5.     Node* head;
7.     // 构造函数初始化头节点为NULL
8.     LinkedList() : head(nullptr) {}
10.     // 插入节点到链表末尾
11.     void append(int value) {
12.         Node* newNode = new Node();
13.         newNode->data = value;
14.         newNode->next = nullptr;
16.         if (head == nullptr) {
17.             head = newNode;
18.         } else {
19.             Node* temp = head;
20.             while (temp->next != nullptr) {
21.                 temp = temp->next;
22.             }
23.             temp->next = newNode;
24.         }
25.     }
27.     // 在指定位置插入节点
28.     void insertAt(int index, int value) {
29.         Node* newNode = new Node();
30.         newNode->data = value;
32.         if (index == 0) {
33.             newNode->next = head;
34.             head = newNode;
35.         } else {
36.             Node* temp = head;
37.             for (int i = 0; temp != nullptr && i < index - 1; i++) {
38.                 temp = temp->next;
39.             }
40.             if (temp == nullptr || temp->next == nullptr) {
41.                 cout << "Index out of bounds" << endl;
42.                 return;
43.             }
44.             newNode->next = temp->next;
45.             temp->next = newNode;
46.         }
47.     }
49.     // 删除指定值的节点
50.     void deleteValue(int value) {
51.         if (head == nullptr) {
52.             cout << "List is empty" << endl;
53.             return;
54.         }
56.         if (head->data == value) {
57.             Node* temp = head;
58.             head = head->next;
59.             delete temp;
60.             return;
61.         }
63.         Node* temp = head;
64.         while (temp->next != nullptr && temp->next->data != value) {
65.             temp = temp->next;
66.         }
68.         if (temp->next == nullptr) {
69.             cout << "Value not found" << endl;
70.             return;
71.         }
73.         Node* nodeToDelete = temp->next;
74.         temp->next = temp->next->next;
75.         delete nodeToDelete;
76.     }
78.     // 查找指定值的节点
79.     bool search(int value) {
80.         Node* temp = head;
81.         while (temp != nullptr) {
82.             if (temp->data == value) {
83.                 return true;
84.             }
85.             temp = temp->next;
86.         }
87.         return false;
88.     }
90.     // 打印链表
91.     void printList() {
92.         Node* temp = head;
93.         while (temp != nullptr) {
94.             cout << temp->data << " -> ";
95.             temp = temp->next;
96.         }
97.         cout << "NULL" << endl;
98.     }
99. };

复制代码

3. 测试链表功能

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

1. [/code] cpp
2. 深色版本
3. [code]int main() {
4.     LinkedList list;
6.     // 插入一些节点
7.     list.append(1);
8.     list.append(2);
9.     list.append(3);
11.     // 打印链表
12.     cout << "Initial list: ";
13.     list.printList();
15.     // 在索引1处插入新节点
16.     list.insertAt(1, 4);
17.     cout << "After inserting at index 1: ";
18.     list.printList();
20.     // 删除值为2的节点
21.     list.deleteValue(2);
22.     cout << "After deleting value 2: ";
23.     list.printList();
25.     // 查找值为3的节点
26.     if (list.search(3)) {
27.         cout << "Value 3 found in the list." << endl;
28.     } else {
29.         cout << "Value 3 not found in the list." << endl;
30.     }
32.     return 0;
33. }

复制代码

运行结果示例

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

1. [/code] 深色版本
2. [code]Initial list: 1 -> 2 -> 3 -> NULL
3. After inserting at index 1: 1 -> 4 -> 2 -> 3 -> NULL
4. After deleting value 2: 1 -> 4 -> 3 -> NULL
5. Value 3 found in the list.

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。