數據結構學習鏈表 2025年6月14日08點01分

單向鏈表: 線性數據結構由一系列節點組成

每個節點包含:

? ? ? ? ? ? ? ? ? ? ? ? 數據部分:存儲實際數據

? ? ? ? ? ? ? ? ? ? ? ? 指針部分:儲存指向下一個節點的引用

特點1,每個節點只有一個指向下一個節點的指針

特點2,只能從頭到尾 單向遍歷

特點3,不需要連續的內存空間

特點4,插入和刪除效率高

特點5,隨機訪問? ? 效率低

優點: 動態大小 不需要提前知道 數據量

使用場景:

棧和隊列的實現
內存分配(內存管理系統)
圖的鄰接表表示
需要頻繁插入刪除且隨機訪問較少的場景

#include <stdio.h>
#include <stdlib.h>// 定義鏈表節點結構體 參考前面節點包含 數據部分 data 指針部分 next
typedef struct Node {int data;           // 數據域，存儲整型數據 可以是任意類型 例如 char data struct Node* next;  // 指針域，指向下一個節點
} Node;
//這里用 Node 替代了 struct Node的書寫 簡化了代碼/*** @brief 創建新節點* @param data 節點數據* @return 返回新創建的節點指針*/
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node)); // 分配內存if (newNode == NULL) {printf("內存分配失敗!\n");exit(1); // 如果分配失敗，退出程序}newNode->data = data; // 設置新節點數據newNode->next = NULL;  // 初始化next指針為NULL 表示這是最后一個節點 預示 鏈表結束return newNode;
}/*** @brief 在鏈表頭部插入節點* @param head 鏈表頭指針 單向鏈表只能通過頭指針開始訪問 
舉例使用Node* head = NULL; // 初始空鏈表// 第一次插入：head為NULLhead = insertAtHead(head, 10); // 現在鏈表：10 -> NULL// head現在指向data=10的節點// 第二次插入head = insertAtHead(head, 20);// 現在鏈表：20 -> 10 -> NULL// head現在指向data=20的節點// 第三次插入head = insertAtHead(head, 30);// 現在鏈表：30 -> 20 -> 10 -> NULLprintList(head);// 輸出：30 -> 20 -> 10 -> NULL// 釋放鏈表內存freeList(head);* @param data 要插入的數據* @return 返回新的鏈表頭指針*/
Node* insertAtHead(Node* head, int data) {Node* newNode = createNode(data); // 創建新節點newNode->next = head;            // 新節點指向原頭節點return newNode;                  // 返回新節點作為新頭節點
}/*** @brief 在鏈表尾部插入節點* @param head 鏈表頭指針
函數調用示例Node* head = NULL;  // 初始化空鏈表// 示例1：向空鏈表插入節點head = insertAtTail(head, 10); // 鏈表狀態：10 -> NULL// head 指向 10// 示例2：向非空鏈表尾部插入節點head = insertAtTail(head, 20); // 鏈表狀態：10 -> 20 -> NULL// head 仍指向 10（頭節點未變）// 示例3：繼續插入head = insertAtTail(head, 30); // 鏈表狀態：10 -> 20 -> 30 -> NULL// 打印鏈表printList(head);  // 輸出: 10 -> 20 -> 30 -> NULL// 釋放鏈表內存freeList(head);* @param data 要插入的數據* @return 返回鏈表頭指針*/
Node* insertAtTail(Node* head, int data) {Node* newNode = createNode(data); // 創建新節點// 如果鏈表為空，新節點就是頭節點if (head == NULL) {return newNode;}// 遍歷找到最后一個節點Node* current = head;while (current->next != NULL) {current = current->next;}// 將新節點連接到鏈表尾部current->next = newNode;return head;
}/*** @brief 在指定位置插入節點* @param head 鏈表頭指針* @param data 要插入的數據
調用示例Node* head = NULL;  // 初始化空鏈表// 構建基礎鏈表: 10 -> 20 -> 30 -> NULLhead = insertAtTail(head, 10);head = insertAtTail(head, 20);head = insertAtTail(head, 30);printList(head);  // 輸出: 10 -> 20 -> 30 -> NULL// 示例1：在位置0插入（頭部插入）head = insertAtPosition(head, 5, 0);// 鏈表變為: 5 -> 10 -> 20 -> 30 -> NULLprintList(head);// 示例2：在位置2插入（中間插入）head = insertAtPosition(head, 15, 2);// 鏈表變為: 5 -> 10 -> 15 -> 20 -> 30 -> NULLprintList(head);// 示例3：在位置5插入（尾部插入）head = insertAtPosition(head, 35, 5);// 鏈表變為: 5 -> 10 -> 15 -> 20 -> 30 -> 35 -> NULLprintList(head);// 示例4：嘗試越界插入（位置10）head = insertAtPosition(head, 100, 10);// 輸出: "插入位置超出鏈表長度!"// 鏈表保持不變freeList(head);* @param position 插入位置（從0開始）* @return 返回鏈表頭指針*/
Node* insertAtPosition(Node* head, int data, int position) {// 如果位置為0，相當于頭部插入if (position == 0) {return insertAtHead(head, data);}Node* newNode = createNode(data);Node* current = head;// 找到position前一個節點for (int i = 0; i < position - 1 && current != NULL; i++) {current = current->next;}// 如果current為NULL，說明位置超出鏈表長度if (current == NULL) {printf("插入位置超出鏈表長度!\n");free(newNode); // 釋放新節點內存return head;}// 插入新節點newNode->next = current->next;current->next = newNode;return head;
}/*** @brief 刪除頭節點* @param head 鏈表頭指針
調用示例Node* head = NULL;  // 初始化空鏈表// 構建鏈表: 10 -> 20 -> 30 -> NULLhead = insertAtTail(head, 10);head = insertAtTail(head, 20);head = insertAtTail(head, 30);printList(head);  // 輸出: 10 -> 20 -> 30 -> NULL// 示例1：刪除頭節點（非空鏈表）head = deleteAtHead(head);// 鏈表變為: 20 -> 30 -> NULLprintList(head);  // 輸出: 20 -> 30 -> NULL// 示例2：繼續刪除頭節點head = deleteAtHead(head);// 鏈表變為: 30 -> NULLprintList(head);  // 輸出: 30 -> NULL// 示例3：刪除最后一個節點head = deleteAtHead(head);// 鏈表變為: NULLprintList(head);  // 輸出: NULL// 示例4：嘗試刪除空鏈表head = deleteAtHead(head);// 輸出: "鏈表為空，無法刪除!"// 鏈表保持為 NULLfreeList(head);  // 釋放鏈表內存（雖然此時已為空）* @return 返回新的鏈表頭指針*/
Node* deleteAtHead(Node* head) {if (head == NULL) {printf("鏈表為空，無法刪除!\n");return NULL;}Node* temp = head;      // 保存原頭節點head = head->next;      // 頭指針指向下一個節點free(temp);             // 釋放原頭節點內存return head;
}/*** @brief 刪除尾節點* @param head 鏈表頭指針
調用示例Node* head = NULL;  // 初始化空鏈表// 構建初始鏈表: 10 -> 20 -> 30 -> NULLhead = insertAtTail(head, 10);head = insertAtTail(head, 20);head = insertAtTail(head, 30);printList(head);  // 輸出: 10 -> 20 -> 30 -> NULL// 示例1：刪除尾節點（鏈表有多個節點）head = deleteAtTail(head);// 鏈表變為: 10 -> 20 -> NULLprintList(head);  // 輸出: 10 -> 20 -> NULL// 示例2：繼續刪除尾節點head = deleteAtTail(head);// 鏈表變為: 10 -> NULLprintList(head);  // 輸出: 10 -> NULL// 示例3：刪除最后一個節點（鏈表只剩一個節點）head = deleteAtTail(head);// 鏈表變為: NULLprintList(head);  // 輸出: NULL// 示例4：嘗試刪除空鏈表head = deleteAtTail(head);// 輸出: "鏈表為空，無法刪除!"// 鏈表保持為 NULL// 重建鏈表測試邊界條件head = insertAtTail(head, 100);head = insertAtTail(head, 200);printList(head);  // 輸出: 100 -> 200 -> NULL// 示例5：連續刪除測試head = deleteAtTail(head);  // 刪除200head = deleteAtTail(head);  // 刪除100head = deleteAtTail(head);  // 提示空鏈表printList(head);  // 輸出: NULLfreeList(head);  // 釋放內存（安全操作，即使鏈表為空）* @return 返回鏈表頭指針*/
Node* deleteAtTail(Node* head) {if (head == NULL) {printf("鏈表為空，無法刪除!\n");return NULL;}// 如果只有一個節點if (head->next == NULL) {free(head);return NULL;}// 找到倒數第二個節點Node* current = head;while (current->next->next != NULL) {current = current->next;}// 刪除最后一個節點free(current->next);current->next = NULL;return head;
}/*** @brief 刪除指定位置節點* @param head 鏈表頭指針* @param position 要刪除的位置（從0開始）
調用示例
Node* head = NULL;  // 初始化空鏈表// 構建測試鏈表: 10 -> 20 -> 30 -> 40 -> 50 -> NULLhead = insertAtTail(head, 10);head = insertAtTail(head, 20);head = insertAtTail(head, 30);head = insertAtTail(head, 40);head = insertAtTail(head, 50);printList(head);  // 輸出: 10 -> 20 -> 30 -> 40 -> 50 -> NULL// 示例1：刪除頭節點（position = 0）head = deleteAtPosition(head, 0);// 鏈表變為: 20 -> 30 -> 40 -> 50 -> NULLprintList(head);  // 輸出: 20 -> 30 -> 40 -> 50 -> NULL// 示例2：刪除中間節點（position = 2）head = deleteAtPosition(head, 2);// 鏈表變為: 20 -> 30 -> 50 -> NULLprintList(head);  // 輸出: 20 -> 30 -> 50 -> NULL// 示例3：刪除尾節點（position = 2）head = deleteAtPosition(head, 2);// 鏈表變為: 20 -> 30 -> NULLprintList(head);  // 輸出: 20 -> 30 -> NULL// 示例4：嘗試越界刪除（position = 5）head = deleteAtPosition(head, 5);// 輸出: "刪除位置無效!"// 鏈表保持: 20 -> 30 -> NULL// 示例5：刪除剩余節點head = deleteAtPosition(head, 1);  // 刪除30head = deleteAtPosition(head, 0);  // 刪除20printList(head);  // 輸出: NULL// 示例6：嘗試刪除空鏈表head = deleteAtPosition(head, 0);// 輸出: "鏈表為空，無法刪除!"freeList(head);  // 安全釋放* @return 返回鏈表頭指針*/
Node* deleteAtPosition(Node* head, int position) {if (head == NULL) {printf("鏈表為空，無法刪除!\n");return NULL;}// 刪除頭節點if (position == 0) {return deleteAtHead(head);}Node* current = head;// 找到position前一個節點for (int i = 0; i < position - 1 && current != NULL; i++) {current = current->next;}// 如果current或current->next為NULL，說明位置無效if (current == NULL || current->next == NULL) {printf("刪除位置無效!\n");return head;}// 刪除指定位置節點Node* temp = current->next;current->next = current->next->next;free(temp);return head;
}/*** @brief 查找節點數據* @param head 鏈表頭指針* @param value 要查找的值
調用示例
Node* head = NULL;  // 初始化空鏈表// 構建測試鏈表: 10 -> 20 -> 30 -> 40 -> 50 -> NULLhead = insertAtTail(head, 10);head = insertAtTail(head, 20);head = insertAtTail(head, 30);head = insertAtTail(head, 40);head = insertAtTail(head, 50);printList(head);  // 輸出: 10 -> 20 -> 30 -> 40 -> 50 -> NULL// 示例1：查找存在的值（中間位置）int pos1 = search(head, 30);printf("30的位置: %d\n", pos1);  // 輸出: 30的位置: 2// 示例2：查找頭節點int pos2 = search(head, 10);printf("10的位置: %d\n", pos2);  // 輸出: 10的位置: 0// 示例3：查找尾節點int pos3 = search(head, 50);printf("50的位置: %d\n", pos3);  // 輸出: 50的位置: 4// 示例4：查找不存在的值int pos4 = search(head, 99);if (pos4 == -1) {printf("99未找到\n");  // 輸出: 99未找到}// 示例5：空鏈表查找Node* emptyList = NULL;int pos5 = search(emptyList, 10);printf("空鏈表查找結果: %d\n", pos5);  // 輸出: 空鏈表查找結果: -1freeList(head);* @return 返回節點位置（從0開始），未找到返回-1*/
int search(Node* head, int value) {Node* current = head;int position = 0;while (current != NULL) {if (current->data == value) {return position;}current = current->next;position++;}return -1; // 未找到
}/*** @brief 打印鏈表
調用示例Node* head = NULL;  // 初始化空鏈表// 示例1：打印空鏈表printList(head);  // 輸出: 鏈表: NULL// 插入節點head = insertAtTail(head, 10);head = insertAtTail(head, 20);head = insertAtTail(head, 30);// 示例2：打印非空鏈表printList(head);  // 輸出: 鏈表: 10 -> 20 -> 30 -> NULL// 示例3：打印中間狀態的鏈表head = deleteAtHead(head);  // 刪除10printList(head);  // 輸出: 鏈表: 20 -> 30 -> NULLhead = insertAtPosition(head, 25, 1);  // 在位置1插入25printList(head);  // 輸出: 鏈表: 20 -> 25 -> 30 -> NULLhead = deleteAtTail(head);  // 刪除30printList(head);  // 輸出: 鏈表: 20 -> 25 -> NULL// 釋放鏈表內存freeList(head);* @param head 鏈表頭指針*/
void printList(Node* head) {Node* current = head;printf("鏈表: ");while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}/*** @brief 釋放整個鏈表內存* @param head 鏈表頭指針*/
void freeList(Node* head) {Node* current = head;while (current != NULL) {Node* temp = current;current = current->next;free(temp);}
}int main() {Node* head = NULL; // 初始化空鏈表// 測試插入操作head = insertAtHead(head, 10); // 頭部插入10head = insertAtTail(head, 20); // 尾部插入20head = insertAtPosition(head, 15, 1); // 在位置1插入15printList(head); // 輸出: 10 -> 15 -> 20 -> NULL// 測試查找操作int pos = search(head, 15);printf("15的位置: %d\n", pos); // 輸出: 1// 測試刪除操作head = deleteAtHead(head); // 刪除頭節點head = deleteAtTail(head); // 刪除尾節點head = deleteAtPosition(head, 0); // 刪除位置0的節點printList(head); // 輸出: NULL (鏈表已空)// 釋放鏈表內存freeList(head);return 0;
}

2025年6月14日 09點19分?

雙向鏈表:

與單向不同的是多了一個指針(前驅指針)prev

默認的next 為后繼指針
typedef struct DNode {int data;               // 數據域struct DNode* prev;     // 前驅指針struct DNode* next;     // 后繼指針
} DNode;

調用示例// 示例1：創建單個節點DNode* node1 = createDNode(10);printf("創建節點: data=%d, prev=%p, next=%p\n", node1->data, (void*)node1->prev, (void*)node1->next);// 輸出示例: 創建節點: data=10, prev=(nil), next=(nil)// 示例2：創建多個節點并連接DNode* node2 = createDNode(20);DNode* node3 = createDNode(30);// 手動連接節點 (實際應用中建議用insert函數)node1->next = node2;node2->prev = node1;node2->next = node3;node3->prev = node2;// 驗證連接printf("鏈表結構:\n");printf("node1: %d <-> node2: %d <-> node3: %d\n", node1->data, node1->next->data, node1->next->next->data);printf("反向驗證: node3: %d <- node2: %d <- node1: %d\n",node3->data, node3->prev->data, node3->prev->prev->data);// 示例3：在循環中批量創建節點DNode* head = NULL;DNode* tail = NULL;for (int i = 1; i <= 5; i++) {DNode* newNode = createDNode(i * 10);if (head == NULL) {head = tail = newNode;} else {tail->next = newNode;newNode->prev = tail;tail = newNode;}}// 打印創建的鏈表DNode* current = head;printf("批量創建的鏈表: ");while (current != NULL) {printf("%d <-> ", current->data);current = current->next;}printf("NULL\n");// 釋放內存free(node1); free(node2); free(node3);current = head;while (current != NULL) {DNode* temp = current;current = current->next;free(temp);}//創建新節點函數
DNode* createDNode(int data) {DNode* newNode = (DNode*)malloc(sizeof(DNode));if (newNode == NULL) {printf("內存分配失敗!\n");exit(1);}newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;
}

//頭部插入

//頭部插入
DNode* insertAtHead(DNode* head, int data) {DNode* newNode = createDNode(data);if (head == NULL) {return newNode;}newNode->next = head;head->prev = newNode;return newNode;
}調用示例
#include <stdio.h>
#include <stdlib.h>typedef struct DNode {int data;struct DNode* prev;struct DNode* next;
} DNode;// 創建新節點函數（前文已實現）
DNode* createDNode(int data) {DNode* newNode = (DNode*)malloc(sizeof(DNode));if (!newNode) {printf("內存分配失敗\n");exit(1);}newNode->data = data;newNode->prev = newNode->next = NULL;return newNode;
}// 正向打印鏈表函數
void printList(DNode* head) {DNode* current = head;printf("當前鏈表: NULL <- ");while (current) {printf("%d", current->data);if (current->next) printf(" <-> ");else printf(" -> ");current = current->next;}printf("NULL\n");
}int main() {DNode* head = NULL; // 初始化為空鏈表// 示例1：向空鏈表插入頭節點head = insertAtHead(head, 10);printList(head);/* 輸出：當前鏈表: NULL <- 10 -> NULL*/// 示例2：繼續頭部插入head = insertAtHead(head, 20);printList(head);/* 輸出：當前鏈表: NULL <- 20 <-> 10 -> NULL*/// 示例3：再次頭部插入head = insertAtHead(head, 30);printList(head);/* 輸出：當前鏈表: NULL <- 30 <-> 20 <-> 10 -> NULL*/// 驗證反向鏈接printf("驗證反向鏈接:\n");printf("頭節點: %d\n", head->data);printf("下一個節點的前驅應指向頭節點: %d\n", head->next->prev->data);/* 輸出：驗證反向鏈接:頭節點: 30下一個節點的前驅應指向頭節點: 30*/// 內存釋放while (head) {DNode* temp = head;head = head->next;free(temp);}return 0;
}

//尾部插入

DNode* insertAtTail(DNode* head, int data) {DNode* newNode = createDNode(data);if (head == NULL) {return newNode;}DNode* current = head;while (current->next != NULL) {current = current->next;}current->next = newNode;newNode->prev = current;return head;
}調用示例
DNode* head = NULL; // 初始為空鏈表// 依次插入1, 2, 3
head = insertAtTail(head, 1);
head = insertAtTail(head, 2);
head = insertAtTail(head, 3);// 現在鏈表是 1 ? 2 ? 3// 在尾部插入4
head = insertAtTail(head, 4);// 現在鏈表是 1 ? 2 ? 3 ? 4//驗證是否插入成功
// 正向遍歷
DNode* current = head;
while (current != NULL) {cout << current->data << " ";current = current->next;
}
// 輸出: 1 2 3 4// 反向遍歷（先到尾部）
current = head;
while (current->next != NULL) {current = current->next;
}
while (current != NULL) {cout << current->data << " ";current = current->prev;
}
// 輸出: 4 3 2 1

?//指定位置插入

DNode* insertAtPosition(DNode* head, int data, int position) {if (position == 0) {return insertAtHead(head, data);}DNode* newNode = createDNode(data);DNode* current = head;for (int i = 0; i < position - 1 && current != NULL; i++) {current = current->next;}if (current == NULL) {printf("插入位置無效!\n");free(newNode);return head;}newNode->next = current->next;if (current->next != NULL) {current->next->prev = newNode;}current->next = newNode;newNode->prev = current;return head;
}調用示例
DNode* head = NULL; // 初始為空鏈表// 插入 1 和 3
head = insertAtTail(head, 1); // 鏈表: 1
head = insertAtTail(head, 3); // 鏈表: 1 ? 3// 在位置 1 插入 2
head = insertAtPosition(head, 2, 1); // 鏈表: 1 ? 2 ? 3// 遍歷驗證
DNode* current = head;
while (current != NULL) {printf("%d ", current->data);current = current->next;
}
// 輸出: 1 2 3

// 頭部刪除? 尾部刪除指定位置刪除

//頭部刪除
DNode* deleteAtHead(DNode* head) {if (head == NULL) {printf("鏈表為空!\n");return NULL;}DNode* newHead = head->next;if (newHead != NULL) {newHead->prev = NULL;}free(head);return newHead;
}
//尾部刪除
DNode* deleteAtTail(DNode* head) {if (head == NULL) {printf("鏈表為空!\n");return NULL;}if (head->next == NULL) {free(head);return NULL;}DNode* current = head;while (current->next != NULL) {current = current->next;}current->prev->next = NULL;free(current);return head;
}
//指定位置刪除
DNode* deleteAtPosition(DNode* head, int position) {if (head == NULL) {printf("鏈表為空!\n");return NULL;}if (position == 0) {return deleteAtHead(head);}DNode* current = head;for (int i = 0; i < position && current != NULL; i++) {current = current->next;}if (current == NULL) {printf("刪除位置無效!\n");return head;}if (current->next != NULL) {current->next->prev = current->prev;}current->prev->next = current->next;free(current);return head;
}//調用示例
int main() {DNode* head = NULL;head = insertAtTail(head, 1);head = insertAtTail(head, 2);head = insertAtTail(head, 3);printf("初始鏈表: ");printList(head); // 1 2 3head = deleteAtHead(head);printf("刪除頭部后: ");printList(head); // 2 3head = deleteAtTail(head);printf("刪除尾部后: ");printList(head); // 2head = insertAtTail(head, 4);head = insertAtTail(head, 5);printf("插入 4,5 后: ");printList(head); // 2 4 5head = deleteAtPosition(head, 1);printf("刪除位置1后: ");printList(head); // 2 5return 0;
}

跳舞鏈

一種高效實現精確覆蓋問題的技術，由Donald Knuth提出。它主要用于解決如數獨、N皇后等約束滿足問題，其核心思想是使用雙向十字循環鏈表來高效實現回溯算法中的覆蓋與恢復操作。

跳舞鏈使用雙向十字循環鏈表表示稀疏矩陣：

每個1對應一個節點

節點鏈接：左、右、上、下

每列有特殊的列頭節點

所有列頭組成環形鏈表

給定一個由0和1組成的矩陣，找出行的集合使得每列恰好包含一個1。例如：text
A B C D
1 1 0 0
1 0 1 0
0 1 1 0
0 0 0 1
解為{1, 4}或{2, 4}

//數據結構定義
struct Node {Node *left, *right, *up, *down;Node *column; // 指向列頭int row;      // 行號int size;     // 列大小（僅列頭使用）
};//核心操作 
//覆蓋列
void cover(Node *col) {// 斷開列頭col->left->right = col->right;col->right->left = col->left;// 遍歷該列所有行for (Node *i = col->down; i != col; i = i->down) {// 遍歷該行所有節點for (Node *j = i->right; j != i; j = j->right) {// 從所在列移除j->up->down = j->down;j->down->up = j->up;j->column->size--;}}
}//恢復列
void uncover(Node *col) {// 逆向操作for (Node *i = col->up; i != col; i = i->up) {for (Node *j = i->left; j != i; j = j->left) {j->column->size++;j->up->down = j;j->down->up = j;}}// 恢復列頭col->left->right = col;col->right->left = col;
}//主框架
bool search(Node *head, vector<int> &solution) {if (head->right == head) return true; // 所有列被覆蓋// 選擇最小size的列Node *col = head->right;for (Node *j = col->right; j != head; j = j->right)if (j->size < col->size) col = j;cover(col);// 嘗試該列的每一行for (Node *row = col->down; row != col; row = row->down) {solution.push_back(row->row);// 覆蓋該行所有節點所在的列for (Node *j = row->right; j != row; j = j->right)cover(j->column);if (search(head, solution)) return true;// 回溯solution.pop_back();for (Node *j = row->left; j != row; j = j->left)uncover(j->column);}uncover(col);return false;
}=============調用示例=============================
// 示例調用
int main() {// 示例：解決數獨的精確覆蓋問題（9x9數獨轉換為729行324列的矩陣）const int ROWS = 729; // 9x9x9 (每個格子9種可能)const int COLS = 324; // 行+列+宮+數字 約束// 1. 初始化舞蹈鏈Node* head = initDLX(ROWS, COLS);// 2. 填入已知數字（示例）// 這里需要根據具體問題填充矩陣...// 例如：在第(0,0)格子填入5// int row = 0 * 81 + 0 * 9 + 5; // 轉換為行號// 在對應列置1// 3. 求解vector<int> solution;if (search(head, solution)) {cout << "找到解：" << endl;for (int r : solution) {// 將行號轉換為原始問題的解int num = (r-1) % 9 + 1;int col = ((r-1) / 9) % 9;int row = (r-1) / 81;cout << "(" << row << "," << col << ") = " << num << endl;}} else {cout << "無解" << endl;}// 4. 釋放內存（實際應用需要實現）return 0;
}

擴展應用

N皇后問題
圖著色問題
拼圖游戲
調度問題
蛋白質折疊

跳躍表

一種概率性數據結構，它允許在有序序列中進行快速的搜索、插入和刪除操作，平均時間復雜度為O(log n)。它由William Pugh于1989年提出，結合了鏈表和二分查找的優點。

跳躍表由多層有序鏈表組成：

最底層（第0層）包含所有元素

每一高層都是下一層的"快速通道"，元素以一定概率出現在更高層

每個節點包含：

鍵值（key）

數據（value）

前進指針數組（forward），指向各層的下一個節點

節點高度（level）

struct SkipListNode {int key;int value;int level;  // 節點所在最高層SkipListNode** forward; // 前進指針數組SkipListNode(int k, int v, int lvl) {key = k;value = v;level = lvl;forward = new SkipListNode*[lvl+1];memset(forward, 0, sizeof(SkipListNode*)*(lvl+1));}~SkipListNode() {delete[] forward;}
};//隨機層數生成
int randomLevel(int maxLevel) {int lvl = 0;while (rand() % 2 == 0 && lvl < maxLevel) {lvl++;}return lvl;
}//搜索操作
SkipListNode* search(SkipListNode* header, int searchKey) {SkipListNode* current = header;// 從最高層開始查找for (int i = header->level; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->key < searchKey) {current = current->forward[i];}}current = current->forward[0];return (current != nullptr && current->key == searchKey) ? current : nullptr;
}//插入操作
void insert(SkipListNode* header, int key, int value, int maxLevel) {// 創建更新數組并初始化SkipListNode* update[maxLevel+1];memset(update, 0, sizeof(SkipListNode*)*(maxLevel+1));SkipListNode* current = header;// 查找插入位置for (int i = header->level; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->key < key) {current = current->forward[i];}update[i] = current;}current = current->forward[0];// 如果鍵已存在，更新值if (current != nullptr && current->key == key) {current->value = value;} else {// 隨機生成新節點層數int newLevel = randomLevel(maxLevel);// 如果新節點層數高于當前跳躍表層數if (newLevel > header->level) {for (int i = header->level+1; i <= newLevel; i++) {update[i] = header;}header->level = newLevel;}// 創建新節點SkipListNode* newNode = new SkipListNode(key, value, newLevel);// 更新各層指針for (int i = 0; i <= newLevel; i++) {newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}}
}//刪除操作
void remove(SkipListNode* header, int key) {// 創建更新數組SkipListNode* update[header->level+1];memset(update, 0, sizeof(SkipListNode*)*(header->level+1));SkipListNode* current = header;// 查找要刪除的節點for (int i = header->level; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->key < key) {current = current->forward[i];}update[i] = current;}current = current->forward[0];// 如果找到鍵if (current != nullptr && current->key == key) {// 更新各層指針for (int i = 0; i <= header->level; i++) {if (update[i]->forward[i] != current) break;update[i]->forward[i] = current->forward[i];}// 刪除節點delete current;// 降低跳躍表高度（如果最高層變空）while (header->level > 0 && header->forward[header->level] == nullptr) {header->level--;}}
}調用示例int main() {srand(time(0)); // 初始化隨機數種子const int MAX_LEVEL = 4;SkipListNode* header = new SkipListNode(INT_MIN, 0, MAX_LEVEL);// 插入示例cout << "插入元素..." << endl;insert(header, 3, 30, MAX_LEVEL);insert(header, 6, 60, MAX_LEVEL);insert(header, 7, 70, MAX_LEVEL);insert(header, 9, 90, MAX_LEVEL);insert(header, 12, 120, MAX_LEVEL);insert(header, 19, 190, MAX_LEVEL);insert(header, 17, 170, MAX_LEVEL);insert(header, 26, 260, MAX_LEVEL);insert(header, 21, 210, MAX_LEVEL);insert(header, 25, 250, MAX_LEVEL);printSkipList(header);// 搜索示例cout << "\n搜索元素..." << endl;int searchKey = 17;SkipListNode* found = search(header, searchKey);if (found) {cout << "找到鍵 " << searchKey << ", 值 = " << found->value << endl;} else {cout << "未找到鍵 " << searchKey << endl;}searchKey = 99;found = search(header, searchKey);if (found) {cout << "找到鍵 " << searchKey << ", 值 = " << found->value << endl;} else {cout << "未找到鍵 " << searchKey << endl;}// 刪除示例cout << "\n刪除元素..." << endl;cout << "刪除鍵 17" << endl;remove(header, 17);printSkipList(header);cout << "刪除鍵 25" << endl;remove(header, 25);printSkipList(header);// 清理內存SkipListNode* current = header->forward[0];while (current != nullptr) {SkipListNode* next = current->forward[0];delete current;current = next;}delete header;return 0;
}輸出效果 示例
插入元素...
===== Skip List =====
Level 0: 3(30) 6(60) 7(70) 9(90) 12(120) 17(170) 19(190) 21(210) 25(250) 26(260) 
Level 1: 3(30) 7(70) 12(120) 17(170) 19(190) 25(250) 26(260) 
Level 2: 12(120) 17(170) 25(250) 
Level 3: 17(170) 
Level 4: 
====================搜索元素...
找到鍵 17, 值 = 170
未找到鍵 99刪除元素...
刪除鍵 17
===== Skip List =====
Level 0: 3(30) 6(60) 7(70) 9(90) 12(120) 19(190) 21(210) 25(250) 26(260) 
Level 1: 3(30) 7(70) 12(120) 19(190) 25(250) 26(260) 
Level 2: 12(120) 25(250) 
Level 3: 
Level 4: 
====================
刪除鍵 25
===== Skip List =====
Level 0: 3(30) 6(60) 7(70) 9(90) 12(120) 19(190) 21(210) 26(260) 
Level 1: 3(30) 7(70) 12(120) 19(190) 26(260) 
Level 2: 12(120) 
Level 3: 
Level 4: 
====================