网站图标怎么设置,网站的备案号在哪,软件开发平台公司,猴痘的传播途径在数据结构算法中#xff0c;有一种算法犹如“时空穿梭机”#xff0c;能在瞬间跨越层层障碍#xff0c;直击目标——它就是跳表算法。下面#xff0c;就让我们一起揭开跳表算法的神秘面纱#xff0c;通过实例探究其高效与魅力。
目录
一、跳表算法是什么#xff1f;
… 在数据结构算法中有一种算法犹如“时空穿梭机”能在瞬间跨越层层障碍直击目标——它就是跳表算法。下面就让我们一起揭开跳表算法的神秘面纱通过实例探究其高效与魅力。
目录
一、跳表算法是什么
二、实例解析
1、跳表的构建
2、查找过程
三、跳表算法的优点
四、跳表——C语言实现
1、常规链表查找
2、跳表查找
一、跳表算法是什么 跳表顾名思义是一种能够“跳过”某些节点进行搜索的链表。它通过再链表的基础上增加多级索引实现了对数据的快速定位、插入与删除。想象一下再一条长长的队伍中你能直接跳到接近目标的位置是不是能缩短搜索该目标的时间从而大大提高代码运行效率。
二、实例解析 假设有一个有序的链表存储了数字1到10。现在需要查找数字7.在没有跳表的情况下可能需要从头开始一步步遍历到7。但是有了跳表一切都将变得不同。
1、跳表的构建 首先要为这个链表构建一个跳表。跳表分为多层每一层都是下面一层的部分节点建立的索引。比如
层348
层2246810
层112345678910
2、查找过程 现在开始查找数据7 从层3开始查找首先比较4和7。由于4比7小就继续向右查找直至比较到8仍未找到7于是便下降到层2。 在层2比较6和7。6仍然小于7但接近查找目标。继续向右查找发现8大于7于是再次下降一层到达层1。 在层1直接定位到6便可轻松查找到值7。 通过这个实例可以看到跳表通过多级索引实现了对数据的快速定位大大减少了查找的时间复杂度。但代价是占用更多的空间。典型的空间换时间。
三、跳表算法的优点
高效性跳表的查找、插入和删除操作的平均时间复杂度都是O(log n)媲美平衡树结构。
简单性相对于红黑树等复杂的数据结构跳表的实现更为简单易于理解和维护。
随机性跳表的随机性保证了其性能的稳定性避免了极端情况下的性能下降。
四、跳表——C语言实现
1、常规链表查找
#include stdio.h
#include stdlib.h// 跳表节点定义
typedef struct SkipListNode {int value;struct SkipListNode *next;struct SkipListNode *skip;
} SkipListNode;// 创建跳表节点
SkipListNode* createSkipListNode(int value) {SkipListNode* node (SkipListNode*)malloc(sizeof(SkipListNode));node-value value;node-next NULL;node-skip NULL;return node;
}// 插入节点到跳表
void insertSkipList(SkipListNode** head, int value) {SkipListNode* newNode createSkipListNode(value);if (*head NULL) {*head newNode;return;}SkipListNode* current *head;SkipListNode* skipPrev NULL;// 寻找插入位置while (current ! NULL current-value value) {skipPrev current;current current-next;}// 插入节点newNode-next current;if (skipPrev ! NULL) {skipPrev-next newNode;} else {*head newNode;}// 更新跳过指针if (skipPrev ! NULL skipPrev-skip ! NULL skipPrev-skip-value value) {newNode-skip skipPrev-skip-next;skipPrev-skip-next newNode;}
}// 查找节点
SkipListNode* findSkipList(SkipListNode* head, int value) {SkipListNode* current head;while (current ! NULL) {if (current-value value) {return current;} else if (current-skip ! NULL current-skip-value value) {current current-skip;} else {current current-next;}}return NULL;
}// 打印跳表
void printSkipList(SkipListNode* head) {SkipListNode* current head;while (current ! NULL) {printf(%d , current-value);if (current-skip ! NULL) {printf((skip to %d) , current-skip-value);}current current-next;}printf(\n);
}// 主函数
int main() {SkipListNode* head NULL;// 插入数据insertSkipList(head, 3);insertSkipList(head, 7);insertSkipList(head, 6);insertSkipList(head, 9);insertSkipList(head, 12);insertSkipList(head, 19);insertSkipList(head, 25);insertSkipList(head, 30);// 打印跳表printf(Skip List: );printSkipList(head);// 查找数据int valueToFind 19;SkipListNode* foundNode findSkipList(head, valueToFind);if (foundNode ! NULL) {printf(Value %d found in the skip list.\n, valueToFind);} else {printf(Value %d not found in the skip list.\n, valueToFind);}return 0;
}2、跳表查找
#include stdio.h
#include stdlib.h
#include time.h#define MAXLEVEL 3 // 假设跳表的最大层级为3// 跳表节点定义
typedef struct SkipListNode {int value;struct SkipListNode *forward[MAXLEVEL]; // 指向不同层级的下一个节点
} SkipListNode;// 创建跳表节点
SkipListNode* createSkipListNode(int level, int value) {SkipListNode* newNode (SkipListNode*)malloc(sizeof(SkipListNode));newNode-value value;for (int i 0; i level; i) {newNode-forward[i] NULL;}return newNode;
}// 随机生成节点的层级
int randomLevel() {int level 1;while ((rand() 0xFFFF) (0.5 * 0xFFFF)) {level;if (level MAXLEVEL) break;}return level;
}// 插入节点到跳表
void insertSkipList(SkipListNode **head, int value) {SkipListNode *update[MAXLEVEL];SkipListNode *current *head;// 从最高层开始找到每层中插入位置的前一个节点for (int i MAXLEVEL - 1; i 0; i--) {while (current-forward[i] ! NULL current-forward[i]-value value) {current current-forward[i];}update[i] current;}// 随机决定新节点的层级int level randomLevel();// 创建新节点SkipListNode *newNode createSkipListNode(level, value);// 将新节点插入到跳表中for (int i 0; i level; i) {newNode-forward[i] update[i]-forward[i];update[i]-forward[i] newNode;}
}// 查找节点
int findSkipList(SkipListNode *head, int value) {SkipListNode *current head;int count 0;int ncount 0;for (int i MAXLEVEL - 1; i 0; i--) {count ;while (current-forward[i] ! NULL current-forward[i]-value value) {current current-forward[i];ncount ;printf(ncount %d .\n, ncount);}count ncount;printf(count %d .\n, count);ncount 0;if(current-forward[i] ! NULL current-forward[i]-value value ){return count; // 找到值返回查找次数}}return -1; // 未找到值
}// 打印跳表
void printSkipList(SkipListNode *head) {for (int i MAXLEVEL - 1; i 0; i--) {SkipListNode *current head-forward[i];printf(Level %d: , i);while (current ! NULL) {printf(%d , current-value);current current-forward[i];}printf(\n);}
}int main() {srand((unsigned)time(NULL)); // 初始化随机数生成器// 创建跳表头节点SkipListNode *head createSkipListNode(MAXLEVEL, -1);// 插入数据insertSkipList(head, 3);insertSkipList(head, 6);insertSkipList(head, 7);insertSkipList(head, 9);insertSkipList(head, 12);insertSkipList(head, 19);insertSkipList(head, 25);insertSkipList(head, 29);// 打印跳表printSkipList(head);// 查找数据int valueToFind 7;int searchCount findSkipList(head, valueToFind);if (searchCount ! -1) {printf(Number of steps taken to find the value %d: %d\n, valueToFind, searchCount);} else {printf(Value %d not found in the skip list.\n, valueToFind);}valueToFind 29;searchCount findSkipList(head, valueToFind);if (searchCount ! -1) {printf(Number of steps taken to find the value %d: %d\n, valueToFind, searchCount);} else {printf(Value %d not found in the skip list.\n, valueToFind);}// TODO: 实现删除操作以及内存释放return 0;
}
