在學習數據結構的過程中，鏈表是一個非常重要的基礎數據結構。今天，我們將通過C++手動實現一個單鏈表，并添加一個逆序打印的功能，幫助大家更好地理解鏈表的實現和操作。
一、鏈表簡介
鏈表是一種線性數據結構，其中每個元素（稱為節點）包含數據部分和指向下一個節點的指針。與數組不同，鏈表的內存空間是動態分配的，因此可以靈活地插入和刪除節點，而不需要移動其他元素。
單鏈表是最簡單的鏈表形式，每個節點只有一個指向下一個節點的指針。
二、單鏈表的實現
1. 定義鏈表節點
我們首先定義鏈表節點的結構。每個節點包含一個整數值和一個指向下一個節點的指針。
#include <iostream>
using namespace std;// 定義鏈表節點結構
struct ListNode {int val; // 節點存儲的數據ListNode* next; // 指向下一個節點的指針// 構造函數ListNode(int x) : val(x), next(nullptr) {}
};2. 定義鏈表類
接下來，我們定義一個鏈表類，包含鏈表的基本操作，如插入、刪除和遍歷。
class LinkedList {
private:ListNode* head; // 鏈表的頭指針public:// 構造函數LinkedList() : head(nullptr) {}// 析構函數，釋放鏈表內存~LinkedList() {ListNode* current = head;while (current != nullptr) {ListNode* temp = current;current = current->next;delete temp;}}// 插入節點到鏈表頭部void insertAtHead(int value) {ListNode* newNode = new ListNode(value);newNode->next = head;head = newNode;}// 插入節點到鏈表尾部void insertAtTail(int value) {ListNode* newNode = new ListNode(value);if (head == nullptr) {head = newNode;return;}ListNode* current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;}// 刪除節點void deleteNode(int value) {if (head == nullptr) return; // 鏈表為空if (head->val == value) {ListNode* temp = head;head = head->next;delete temp;return;}ListNode* current = head;while (current->next != nullptr && current->next->val != value) {current = current->next;}if (current->next != nullptr) {ListNode* temp = current->next;current->next = current->next->next;delete temp;}}// 打印鏈表void printList() {ListNode* current = head;while (current != nullptr) {cout << current->val << " -> ";current = current->next;}cout << "nullptr" << endl;}// 逆序打印鏈表void reversePrint(ListNode* node) {if (node == nullptr) return;reversePrint(node->next);cout << node->val << " ";}// 調用逆序打印void reversePrint() {reversePrint(head);cout << endl;}
};3. 測試鏈表
我們編寫一個簡單的測試程序來驗證鏈表的功能，包括插入、刪除、正序打印和逆序打印。
int main() {LinkedList list;// 插入節點list.insertAtHead(3);list.insertAtHead(2);list.insertAtHead(1);list.insertAtTail(4);list.insertAtTail(5);// 打印鏈表cout << "鏈表內容: ";list.printList();// 逆序打印鏈表cout << "逆序打印鏈表: ";list.reversePrint();// 刪除節點list.deleteNode(3);cout << "刪除節點 3 后的鏈表: ";list.printList();// 刪除頭節點list.deleteNode(1);cout << "刪除頭節點后的鏈表: ";list.printList();return 0;
}4. 輸出示例
運行上述代碼后，輸出如下：
鏈表內容: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
逆序打印鏈表: 5 4 3 2 1
刪除節點 3 后的鏈表: 1 -> 2 -> 4 -> 5 -> nullptr
刪除頭節點后的鏈表: 2 -> 4 -> 5 -> nullptr三、逆序打印的實現
逆序打印鏈表的關鍵在于遞歸。我們定義了一個遞歸函數 reversePrint，它先遞歸到鏈表的尾部，然后在回溯過程中打印每個節點的值。這種方法利用了遞歸的調用棧，自然地實現了逆序打印。
逆序打印函數
void reversePrint(ListNode* node) {if (node == nullptr) return;reversePrint(node->next);cout << node->val << " ";
}調用逆序打印
void reversePrint() {reversePrint(head);cout << endl;
}四、總結
通過手動實現單鏈表，我們不僅加深了對鏈表數據結構的理解，還學會了如何操作鏈表節點，包括插入、刪除和遍歷。此外，逆序打印功能的實現進一步展示了遞歸在鏈表操作中的強大作用。
