当前位置：首页 > news >正文

数据结构学习链表 2025年6月14日08点01分

news 2025/6/15 5:36:09

单向链表: 线性数据结构由一系列节点组成

每个节点包含:

数据部分:存储实际数据

指针部分:储存指向下一个节点的引用

特点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: 
====================

查看全文

http://www.xdnf.cn/news/1032355.html