潍坊专业建站,ueditor wordpress4.7,网站开发 python 工具,广州有哪些区有几个区单向链表: 线性数据结构 由一系列节点组成 每个节点包含: 数据部分:存储实际数据 指针部分:储存指向下一个节点的引用 特点1,每个节点只有一个指向下一个节点的指针 特点2,只能从头到尾 单向遍历 特点3,不需要连续的内存空间 特点4,插入和删除效率高 特点5,随机访问 效率低 …单向链表: 线性数据结构 由一系列节点组成 每个节点包含: 数据部分:存储实际数据 指针部分:储存指向下一个节点的引用 特点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现在指向data10的节点// 第二次插入head insertAtHead(head, 20);// 现在链表20 - 10 - NULL// head现在指向data20的节点// 第三次插入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尝试越界插入位置10head 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 0head deleteAtPosition(head, 0);// 链表变为: 20 - 30 - 40 - 50 - NULLprintList(head); // 输出: 20 - 30 - 40 - 50 - NULL// 示例2删除中间节点position 2head deleteAtPosition(head, 2);// 链表变为: 20 - 30 - 50 - NULLprintList(head); // 输出: 20 - 30 - 50 - NULL// 示例3删除尾节点position 2head deleteAtPosition(head, 2);// 链表变为: 20 - 30 - NULLprintList(head); // 输出: 20 - 30 - NULL// 示例4尝试越界删除position 5head 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);// 输出示例: 创建节点: data10, 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.htypedef 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, vectorint 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. 求解vectorint 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*[lvl1];memset(forward, 0, sizeof(SkipListNode*)*(lvl1));}~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[maxLevel1];memset(update, 0, sizeof(SkipListNode*)*(maxLevel1));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-level1; 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-level1];memset(update, 0, sizeof(SkipListNode*)*(header-level1));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删除元素...
删除键 17Skip 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: 删除键 25Skip 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:
