关键词：
//随机化算法 跳跃表
#include "stdafx.h"
#include "RandomNumber.h"
#include <cmath>
#include <iostream>
using namespace std;
template<class EType,class KType> class SkipList;
template<class EType,class KType>
class SkipNode
friend SkipList<EType,KType>;
private:
SkipNode(int size)
next = new SkipNode<EType,KType>*[size];
~SkipNode()
delete []next;
EType data;//集合中的元素
SkipNode<EType,EType> **next;//指针数组 next[i]是第i级指针
;
template<class EType,class KType>
class SkipList
public:
SkipList(KType Large,int MaxE = 10000,float p = 0.5);
~SkipList();
bool Search(const KType& k,EType& e) const;
SkipList<EType,KType>& Insert(const EType& e);
SkipList<EType,KType>& Delete(const KType& k,EType& e);
void Output();
private:
int Level();
SkipNode<EType,KType> *SaveSearch(const KType& k);
int MaxLevel; //跳跃表级别上界
int Levels; //当前最大级别
RandomNumber rnd; //随机数产生器
float Prob; //用于分配节点级别
KType TailKey; //元素键值上界
SkipNode<EType,KType> *head; //头结点指针
SkipNode<EType,KType> *NIL; //尾节点指针
SkipNode<EType,KType> **last; //指针数组
;
//构造函数
template<class EType,class KType>
SkipList<EType,KType>::SkipList(KType Large,int MaxE,float p)
Prob = p;
MaxLevel = ceil(log(float(MaxE))/log(1/p))-1; //初始化跳跃表级别上界
TailKey = Large; //元素键值上界
Levels = 0; //初始化当前最大级别
//创建头、尾节点和数组 last
head = new SkipNode<EType,KType>(MaxLevel+1);
NIL = new SkipNode<EType,KType>(0);
last = new SkipNode<EType,KType> *[MaxLevel+1];
NIL->data = Large;
//将跳跃表初始化为空表
for(int i=0; i<=MaxLevel; i++)
head->next[i] = NIL;
//析构函数
template<class EType,class KType>
SkipList<EType,KType>::~SkipList()
SkipNode<EType,KType> *next;
//删除所有节点
while(head!=NIL)
next = head->next[0];
delete head;
head = next;
delete NIL;
delete []last;
class element
friend int main(void);
public:
operator long() const
return key;
element& operator = (long y)
key = y;
return *this;
private:
int data;
long key;
;
//搜索指定元素k
template<class EType,class KType>
bool SkipList<EType,KType>::Search(const KType& k,EType& e) const
if(k>=TailKey)
return false;
//位置p恰好位于指定元素k之前
SkipNode<EType,KType> *p = head;
for(int i=Levels; i>=0; i--)//逐渐向下搜索
while(p->next[i]->data<k)//在第i级链中搜索
p = p->next[i];//每次搜索尽可能滴接近要搜索的元素
e = p->next[0]->data;
return (e==k);
//搜索指定元素k,并将每一级中遇到的上一个节点存放在数组last中
template<class EType,class KType>
SkipNode<EType,KType> *SkipList<EType,KType>::SaveSearch(const KType& k)
//位置p恰好位于指定元素k之前
SkipNode<EType,KType> *p = head;
for(int i = Levels; i>=0; i--)
while(p->next[i]->data<k)
p = p->next[i];
last[i] = p; //上一个第i级结点
return (p->next[0]);
//产生不超过MaxLevel 的随机级别
template<class EType,class KType>
int SkipList<EType,KType>::Level()
int lev = 0;
while(rnd.fRandom()<Prob)
lev++;
return (lev<=MaxLevel)?lev:MaxLevel;
//插入指定元素e
template<class EType,class KType>
SkipList<EType,KType>& SkipList<EType,KType>::Insert(const EType& e)
KType k = e;//取得元素键值
if(k>=TailKey)
cout<<"元素键值超界!"<<endl;
return *this;
//检查元素是否已存在
SkipNode<EType,KType> *p = SaveSearch(k);
if(p->data == e)
cout<<"元素已存在!"<<endl;
return *this;
//元素不存在，确定新节点级别
int lev = Level();
//调整个级别指针
if(lev>Levels)
for(int i=Levels+1; i<=lev; i++)
last[i] = head;
Levels = lev;
//产生新节点，并将新节点插入p之后
SkipNode<EType,KType> *y = new SkipNode<EType,KType>(lev+1);
y->data = e;
for(int i=0; i<=lev; i++)
//插入第i级链
y->next[i] = last[i]->next[i];
last[i]->next[i] = y;
return *this;
//删除键值为k的元素，并将所删除的元素存入e
template<class EType,class KType>
SkipList<EType,KType>& SkipList<EType,KType>::Delete(const KType& k,EType& e)
if(k>=TailKey)
cout<<"元素键值超界!"<<endl;
//搜索待删除元素
SkipNode<EType,KType> *p = SaveSearch(k);
if(p->data!=k)
cout<<"未找到待删除元素!"<<endl;
//从跳跃表中删除节点
for(int i=0; i<=Levels && last[i]->next[i] == p; i++)
last[i]->next[i] = p->next[i];
//更新当前级别
while(Levels>0 && head->next[Levels] == NIL)
Levels--;
e = p->data;
delete p;
return *this;
//输出集合中的元素
template<class EType,class KType>
void SkipList<EType,KType>::Output()
SkipNode<EType,KType> *y = head->next[0];
for(;y!=NIL; y=y->next[0])
cout<<y->data<<' ';
cout<<endl;
int main()
SkipList<int,int> *s = new SkipList<int,int>(100,10,0.5);
//创建
cout<<"=========创建==========="<<endl;
int a[] = 5,3,2,11,7,13,19,17,23;
for(int i=0; i<9; i++)
s->Insert(a[i]);
s->Output();
//搜索
cout<<"=========搜索==========="<<endl;
int k=17,e;
cout<<"搜索元素k="<<k<<"如下:"<<endl;
if(s->Search(17,e))
cout<<"位置搜索结果为：k="<<k<<",e="<<e;
cout<<endl;
//删除
cout<<"=========删除==========="<<endl;
cout<<"删除跳跃表元素k="<<k<<"剩余元素如下:"<<endl;
s->Delete(k,e);
s->Output();
delete s;
return 0;
#include"time.h"
//随机数类
const unsigned long maxshort = 65536L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
class RandomNumber
private:
//当前种子
unsigned long randSeed;
public:
RandomNumber(unsigned long s = 0);//构造函数，默认值0表示由系统自动产生种子
unsigned short Random(unsigned long n);//产生0：n-1之间的随机整数
double fRandom(void);//产生[0,1)之间的随机实数
;
RandomNumber::RandomNumber(unsigned long s)//产生种子
if(s == 0)
randSeed = time(0);//用系统时间产生种子
else
randSeed = s;//由用户提供种子
unsigned short RandomNumber::Random(unsigned long n)//产生0：n-1之间的随机整数
randSeed = multiplier * randSeed + adder;//线性同余式
return (unsigned short)((randSeed>>16)%n);
double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数
return Random(maxshort)/double(maxshort);
c_cpp哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20％〜90％之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。一个包含(
查看详情
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。(代码片段)
题目描述：给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。你可以假设除了数字0之外，这两个数字都不会以零开头。思路:1.定义链表类2.创建两... 查看详情
顺序表和链表的基本操作，用c语言实现！
...序，排序后链表元素按照非递减方式排列（注意：排序时如果要交换两个结点的顺序，不得通过交换结点的内容，而需要使用改变指针的方式交换结点的位置。建议使用直接插入排序算法）。(6)．利用算法5建立两个非递减有序... 查看详情
两个有序链表序列的合并
7-51 两个有序链表序列的合并（20 分）已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。输入格式:输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用?1表示序列的结尾（?1不属... 查看详情
刷题10：归并两个有序的链表
...虚拟头节点pre和一个永远指向链表尾部节点的指针temp，如果两链表都不为空，比较两链表当前节点的值，较小的节点加链表尾部，以此类推，直到退出循环。退出循环时，如果两链表之前就不为空，则退出while一定还有一个链表... 查看详情
138.复制带随机指针的链表(代码片段)
...机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 示例1：输入：head=[[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]示例2：输入：head=[[1,1],[2,1]]输出：[[1,1],... 查看详情
复制带随机指针的链表(代码片段)
...机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 /*//DefinitionforaNode.classNodepublic:intval;Node*next;Node*random;Node(int_val)val=_val;next=NULL;random=NULL;;*/classSolutionpublic:Node*copyRandomList... 查看详情
数据结构合集(代码片段)
...法承受更多的水，删除这个沙漏即可。分类讨论：\\(1.\\)如果删除：\\(O(1)\\)均摊。\\(2.\\)如果不删除：\\(O(1)\\)。综上，总复杂度为\\(O(m)\\)。代码：#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+100;intn,m;//同 查看详情
第三篇双向链表（循环链表）
...用C/C++开发系统中，我们知道用数组或者单链表来开发，如果是数据比较大的话，性能很不好，效率也不高。因此常常需要考虑系统的实用性，常常采用双向链表来开发。示例：1.数据typedefstructnode{ intdata;//数据 structnode*la... 查看详情
两个有序链表序列的交集(代码片段)
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。输入格式:输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。输出格式... 查看详情
对链表进行插入排序(代码片段)
...代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移 查看详情
数据结构与算法--必知必会
数组实现一个支持动态扩容的数组实现一个大小固定的有序数组，支持动态增删改操作实现两个有序数组合并为一个有序数组链表实现单链表、循环链表、双向链表，支持增删操作实现单链表反转实现两个有序的链表合并为一个... 查看详情
c_cpp209.cpp(代码片段)
查看详情
数据结构-线性表错题集锦
...续空间，插入和删除不需要移动元素Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表A.Ⅰ、Ⅱ &nbs 查看详情
7-51两个有序链表序列的合并(20分)(代码片段)
7-51两个有序链表序列的合并(20分)已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。输入格式:输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用?1表示序列的结尾（?1不属于这个... 查看详情
skiplist之详细分析
...级索引，变成如下结构：这里元素不多，体现不出优势，如果元素足够多，这种索引结构就能体现出优势来了。这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的... 查看详情
7-15两个有序链表序列的合并（20分）
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。输入格式:输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。输... 查看详情
7-3两个有序链表序列的交集（20分）(代码片段)
7-3 两个有序链表序列的交集（20 分）已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。输入格式:输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用?1表示序列的结尾（?1不属于这个... 查看详情