Data-Structures:链表实现

链表是一种基础且重要的数据结构，它在计算机科学中扮演着关键角色，特别是在处理动态数据集合时。不同于数组，链表中的元素不连续存储在内存中，而是通过指针链接在一起，每个节点包含数据和指向下一个节点的引用。在C++中，链表的实现通常涉及自定义节点结构和相应的操作函数。 ### 链表的节点结构 在C++中，链表的每个元素被称为节点。一个简单的节点结构可以定义为： ```cpp struct Node { int data; // 存储的数据 Node* next; // 指向下一个节点的指针 }; ``` ### 链表的基本操作 1. **创建新节点**：创建新节点时，需要分配内存并初始化数据和指针。 ```cpp Node* newNode(int data) { Node* temp = new Node(); if (temp == NULL) { // 处理内存分配失败 } temp->data = data; temp->next = NULL; return temp; } ``` 2. **插入节点** - **在链表开头插入**：需要更新头节点。 ```cpp void insertAtBegin(Node*& head, int data) { Node* newNode = newNode(data); newNode->next = head; head = newNode; } ``` - **在链表结尾插入**：需要遍历链表找到尾部。 ```cpp void append(Node*& head, int data) { Node* newNode = newNode(data); if (head == NULL) { head = newNode; return; } Node* temp = head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } ``` 3. **删除节点** - **删除指定值的节点**：需查找并移除匹配的节点。 ```cpp void deleteNode(Node*& head, int key) { Node* temp = head, *prev; if (temp != NULL && temp->data == key) { head = temp->next; // 删除头节点 delete temp; return; } while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; // 节点不存在 prev->next = temp->next; delete temp; } ``` 4. **打印链表** ```cpp void printList(Node* node) { while (node != NULL) { std::cout << node->data << " "; node = node->next; } } ``` ### 队列与链表 队列是一种先进先出（FIFO）的数据结构。在C++中，可以使用链表来实现队列。队列的基本操作包括`enqueue`（入队，即在队尾添加元素）和`dequeue`（出队，即移除队首元素）。 ```cpp class Queue { private: Node* front; Node* rear; public: Queue() { front = rear = NULL; } // 入队 void enqueue(int data) { Node* newNode = newNode(data); if (rear == NULL) front = newNode; else rear->next = newNode; rear = newNode; } // 出队 int dequeue() { if (isEmpty()) { throw "Queue is empty"; } int item = front->data; Node* temp = front; front = front->next; if (front == NULL) rear = NULL; delete temp; return item; } // 检查队列是否为空 bool isEmpty() { return front == NULL; } // 打印队列 void printQueue() { Node* temp = front; while (temp != NULL) { std::cout << temp->data << " "; temp = temp->next; } std::cout << "\n"; } }; ``` 通过以上代码，我们已经了解了如何在C++中使用链表实现基本操作以及如何用链表实现队列。链表和队列是构建复杂算法和数据结构的基础，如堆栈、图和树等。理解它们的工作原理和实现方法对于深入学习计算机科学至关重要。