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

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

每个节点包含:

                        数据部分:存储实际数据

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

特点1,每个节点只有一个指向下一个节点的指针

特点2,只能从头到尾 单向遍历

特点3,不需要连续的内存空间

特点4,插入和删除效率高

特点5,随机访问    效率低

优点: 动态大小 不需要提前知道 数据量

使用场景:

  1. 栈和队列的实现
  2. 内存分配(内存管理系统)
  3. 图的邻接表表示
  4. 需要频繁插入删除且 随机访问较少的场景

 

#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;
}

 

扩展应用

  1. N皇后问题

  2. 图着色问题

  3. 拼图游戏

  4. 调度问题

  5. 蛋白质折叠

跳跃表

一种概率性数据结构，它允许在有序序列中进行快速的搜索、插入和删除操作，平均时间复杂度为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.pswp.cn/diannao/87484.shtml
繁体地址，请注明出处：http://hk.pswp.cn/diannao/87484.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

使用 Kubernetes 部署 PHP 留言板应用（含 Redis 架构）

使用 Kubernetes 部署 PHP 留言板应用（含 Redis 架构）

使用 Kubernetes 部署 PHP 留言板应用&#xff08;含 Redis 架构&#xff09; 文章目录 使用 Kubernetes 部署 PHP 留言板应用&#xff08;含 Redis 架构&#xff09;教程概述技术架构特点 准备工作环境要求 Redis 数据库部署Redis 主从架构原理创建 Redis 领导者 Deployment部…
阅读更多...
MATLAB提供的两种画误差矩阵的函数

MATLAB提供的两种画误差矩阵的函数

MATLAB在统计学和机器学习工具包中提供了两种画误差矩阵&#xff08;Confusion matrix&#xff09;的函数。 figure; plotconfusion(YValidation,YPred)figure; cm confusionchart(YValidation,YPred) cm.Title Confusion Matrix for Validation Data; cm.RowSummary row-n…
阅读更多...
【Java学习笔记】泛型

【Java学习笔记】泛型

泛型 一、泛型的引出 代码示例 public class pra {public static void main(String[] args) {ArrayList arrayList new ArrayList();arrayList.add("java");arrayList.add("jack");arrayList.add("jom");arrayList.add(new a());for (Object…
阅读更多...
SpringMVC系列（一）（介绍，简单应用以及路径位置通配符）

SpringMVC系列（一）（介绍，简单应用以及路径位置通配符）

0 引言 作者正在学习SpringMVC相关内容&#xff0c;学到了一些知识&#xff0c;希望分享给需要短时间想要了解SpringMVC的读者朋友们&#xff0c;想用通俗的语言讲述其中的知识&#xff0c;希望与诸位共勉&#xff0c;共同进步&#xff01; 1 SpringMVC介绍 SpringMVC本质上…
阅读更多...
Java中如何使用lambda表达式分类groupby

Java中如何使用lambda表达式分类groupby

Java中如何使用lambda表达式分类groupby Java中如何使用lambda表达式分类groupby分类问题场景传统手写方式lambda使用groupBy()方法一行结束&#xff01;&#xff01;&#xff01;完整代码 Java中如何使用lambda表达式分类groupby 分类问题场景 比如一群学生根据性别和年龄排…
阅读更多...
无人机开发分享——无人机集群基于braft实现长机动态推选算法

无人机开发分享——无人机集群基于braft实现长机动态推选算法

在无人机集群项目的算法开发中&#xff0c;推选长机作为集群的动态中心&#xff0c;往往承担着集群管理、通讯中继等重要功能。由于通讯链路的有限性和任务的实时性需要&#xff0c;需要保证动态长机时刻工作正常&#xff0c;并在异常情况下快速切换新长机。 本文主要分享基于b…
阅读更多...
python 解码 jwt

python 解码 jwt

import base64 import jsondef base64url_decode(base64url_data):# 将URL安全的base64编码数据转换为标准的base64编码数据base64_data base64url_data.replace(-, ).replace(_, /)# 如果数据长度不是4的倍数&#xff0c;则补齐padding_length 4 - len(base64_data) % 4base…
阅读更多...
腾讯云TCCA认证考试报名 - TDSQL数据库交付运维工程师(MySQL版)

腾讯云TCCA认证考试报名 - TDSQL数据库交付运维工程师(MySQL版)

数据库交付运维工程师-腾讯云TDSQL(MySQL版)认证 适合人群&#xff1a; 适合从事TDSQL(MySQL版)交付、初级运维、售前咨询以及TDSQL相关项目的管理人员。 认证考试 单选*40道多选*20道 成绩查询 70分及以上通过认证&#xff0c;官网个人中心->认证考试 查询 考试费用&am…
阅读更多...
Spring Boot的Security安全控制——认识SpringSecurity！

Spring Boot的Security安全控制——认识SpringSecurity！

Spring Boot的Security安全控制 在Web项目开发中&#xff0c;安全控制是非常重要的&#xff0c;不同的人配置不同的权限&#xff0c;这样的系统才安全。最常见的权限框架有Shiro和Spring Security。Shiro偏向于权限控制&#xff0c;而Spring Security能实现权限控制和安全控制…
阅读更多...
深入理解ArrayList：从Java原生实现到手写一个ArrayList

深入理解ArrayList：从Java原生实现到手写一个ArrayList

Java原生ArrayList解析 基本结构 Java的ArrayList是基于数组实现的动态列表&#xff0c;主要特点包括&#xff1a; 动态扩容&#xff1a;当元素数量超过当前容量时&#xff0c;自动扩容&#xff08;通常增加50%&#xff09; 快速随机访问&#xff1a;通过索引访问元素的时间…
阅读更多...
【力扣 简单 C】206. 反转链表

【力扣 简单 C】206. 反转链表

目录 题目 解法一&#xff1a;迭代 解法二&#xff1a;递归 题目 解法一&#xff1a;迭代 struct ListNode* reverse(struct ListNode* head) {struct ListNode* retHead NULL;while (head){struct ListNode* nextNode head->next;head->next retHead;retHead he…
阅读更多...
明代大模型：智能重构下的文明再发现

明代大模型：智能重构下的文明再发现

引言&#xff1a;当紫禁城遇见生成式AI 一幅动态的《紫禁城图卷》正通过全息投影技术演绎永乐年间的宫廷盛景。这个虚实交融的场景&#xff0c;恰似明代大模型技术的隐喻——以人工智能为纽带&#xff0c;连接起永乐盛世的恢弘气象与数字时代的文明重构。作为人工智能与历史学…
阅读更多...
推荐使用的Unity插件（行为树Behavior ）

推荐使用的Unity插件（行为树Behavior ）

在 Unity 6.0 中使用 Behavior Designer 行为树插件开发 AI 系统&#xff0c;需结合其核心节点设计、变量管理和代码控制。以下是详细指南&#xff0c;整合了最新版本的最佳实践&#xff1a; &#x1f6e0;️ 1. 安装与基础配置 安装插件 通过 Unity Asset Store 安装 “Behav…
阅读更多...
107. Java 继承 - 总结：方法重写与隐藏

107. Java 继承 - 总结：方法重写与隐藏

文章目录 107. Java 继承 - 总结&#xff1a;方法重写与隐藏**详细解释&#xff1a;****方法重载** **总结** 107. Java 继承 - 总结&#xff1a;方法重写与隐藏 在 Java 中&#xff0c;定义与超类中的方法具有相同签名的方法时&#xff0c;不同类型的方法之间会有不同的行为。…
阅读更多...
Spring Cloud使用Eureka调用接口，超时设置（二）

Spring Cloud使用Eureka调用接口，超时设置（二）

在 Spring Cloud 微服务架构中&#xff0c;当同时配置了 Ribbon 和 Feign 的超时时间时&#xff0c;Feign 的配置优先级高于 Ribbon。具体规则和底层逻辑如下&#xff1a; ⚙️ 1. 配置优先级规则 Feign 显式配置 > Ribbon 配置 若在 Feign 中显式设置了超时时间&#xff0…
阅读更多...
iOS-SM3加密算法N种集成

iOS-SM3加密算法N种集成

近期的一个项目需要用到SM3加密算法&#xff0c;需要在iOS中使用Objective-C实现SM3国密加密算法。 SM3&#xff1a;是中国国家密码管理局发布的密码杂凑算法标准&#xff0c;适用于商用密码应用中的数字签名和验证、消息认证码的生成与验证以及随机数的生成等 由于iOS系统并未…
阅读更多...
[逆向工程]什么是TEB 与 PEB（二十九）

[逆向工程]什么是TEB 与 PEB（二十九）

[逆向工程]什么是TEB 与 PEB（二十九） 一、引言：为什么需要了解 TEB/PEB？ 在 Windows 系统开发、调试或逆向工程中，TEB（Thread Environment Block） 和 PEB（Process Environment Block） 是理解程序执行机制的关键。它们如同进程与线程的“身份证”，存储了从内存布局到…
阅读更多...
逆向分析贝壳网人机验证JS加密逻辑

逆向分析贝壳网人机验证JS加密逻辑

引言 在数据爬取和自动化测试过程中&#xff0c;人机验证&#xff08;如滑块、点选、短信验证等&#xff09;是常见的反爬手段。贝壳网&#xff08;ke.com&#xff09;作为国内领先的房产平台&#xff0c;其人机验证机制较为复杂&#xff0c;涉及前端JS加密、动态Token、行为检…
阅读更多...
Vue3 + Element Plus中el-table加载状态分析

Vue3 + Element Plus中el-table加载状态分析

在 Vue 3 中&#xff0c;当 onMounted 钩子被触发时&#xff0c;父组件的 DOM 已经挂载完成&#xff0c;但子组件&#xff08;如 el-table&#xff09;可能尚未完成其内部渲染。具体分析如下&#xff1a; 1. onMounted 的执行时机 父组件挂载完成&#xff1a;onMounted 表示当前…
阅读更多...
OpenCV图像拼接技术详解：从特征匹配到全景合成

OpenCV图像拼接技术详解：从特征匹配到全景合成

本文将详细介绍如何使用OpenCV实现两幅图像的自动拼接&#xff0c;涵盖特征提取、单应性矩阵计算和图像融合等关键技术。 一、图像拼接概述 图像拼接是将多张有重叠区域的图像合并成一幅全景图的技术&#xff0c;广泛应用于全景摄影、卫星图像处理、医学影像等领域。其核心技术…
阅读更多...
最新文章

Copyright @ 2022~2023