一，字典的基本概念
操作:检索、插入元素和删除元素,其中最主要的运算是进行检索
●检索:给定一个key ,在字典中找出关键码等于key的元素
字典有顺序存储，链式存储和散列表示三种存储方式，其中，链式存储又有跳跃链表和树形结构两种方式存储。
静态字典: 一旦建立好，基本不动
动态字典:经常需要更新
评价标准:平均检索长度( Average Search Length )
二，跳跃链表
1，跳跃链表的基本概念
链表其缺点是只能顺序查找,即使是有序的链表也不能实现二分查找操作。跳跃链表(skiplist) 是有序链表的变种，它能够达到O(log n)的查找性能,是一种高效的字典结构。在单链表中只有一个指向直接后继的指针，而在跳跃链表中增加指向其他后继结点的指针，使得访问链表的过程中可以交替的跳过他的直接后继结点,
横向叫做层，竖向叫做塔。
越高层链表结点是底层链表结点的子集，底层结点包含了所有词条，跳跃链表查找时从最高层开始找，最坏的情况就是找到最低层。
2，跳跃链表的建立和查找
#define MAX_ LEVEL 6 //定义最大层数 typedef int KeyType; //跳跃链表结点结构定义 typedef struct node { int level; //结点层数 KeyType key; //结点的值 struct node *next[MAX_ LEVEL]; // 指针数组 }*PNode; //跳跃链表结构定义 typedef struct { int num; //跳跃链表数据个数 int maxLevel; //跳跃链表最大层数 PNode head; // 跳跃链表的头指针 }*SkipList;
//创建带有头结点的空跳跃链表 SkipList SetNullSkipList(int level) { SkipList list = (SkipList)malloc(sizeof(SkipList)); if (list == NULL)//申请内存失败 return NULL; list->num= 0; //空跳跃链表计数器赋值0 list->maxLevel = level; //跳跃链表的层数 list->head = CreateNode(level, -1://头结点的数据域赋值为-1 if (list->head == NULL) { free(list); return NULL; } for (inti= 0;i< level; i++) //头结点的每一层的后继为空 list- >head->next[i] = NUL; return list; }
生成一个新结点
PNode CreateNode(int level, KeyType key) //生成个一新结点 { PNode p = (PNode)malloc(sizeof(struct node) + sizeof(PNode)*level); if (p == NULL) return NULL; p->level = level; p->key = key; return p; }
查找：
PNode SkipListSearch(SkipList list, KeyType key) //按值查找，存在返回key的位置，失败返回NULL { int n = 0;PNode p = NULL, q = NULL; p = list->head; for (int i-lit->maxLevel- 1;i>= 0; i) //从高层开始，纵向逐层比较 { while ((q = p->next[i]) && (q->key <= key)) //横向比较 { p= q; n++; //记录比较次数 if (p->key == key) { printf("%d\n", n); return p; } } } return NULL; }
查找算法过程:假设要查找元素key,从最高层的指针开始，如果找到该元素，则返回结点指针。如果到达了链表的末尾，或者找到大于key的某个元素elem,接着降低一层，从包含elem的那个结点的前一个结点重新开始查找。重复该过程直到找到key,或者在第一层查找达到了链表末尾，或者找到了一个大于key的元素。
3，跳跃链表的插入和删除：
插入过程:首先进行查找，查找成功，返回0 (因为在这里约定不能有相同的key)故不再插入。查找失败，则创建一个结点， 接着，逐层修改关联的指针，跳跃链表的计数器加1.
创建结点的层数根据投币产生，在算法中使用逻辑表达式rand() % 2来模拟投币过程，通过(伪)随机数的奇偶来模拟一次理想的投币过程。 根据RandomLevel的返回值插入到相应的层。
//插入结点，成功返回1,否则返回0 int SkipListInsert(SkipList list, KeyType key) { int level = 0; PNode Pre[MAX_ LEVEL]; //记录每层的前驱结点位置 PNode p, q = NULL; p = list->head; //查找位置，记录前驱结点信息 for (int i= list->maxLevel- 1; i>= 0; i--) //纵向控制层 { //横向查找插入位置，而for循环是 纵向移动查找位置 while ((q = p->next[i]) && (q->key< key)) p= q; Pre[i]= p; } //已经存在相同的key,不能插入 if ((q != NULL) && (q->key == key)) return 0; level = RandomLevel(list->maxLevel); /产生-一个随机层数 p = CreateNode(level, key); //创建新结点 if (p == NULL) return 0; //纵向逐层修改指针 for (inti= 0;i< level; i++) { p->next[i] = Pre[i]->next[i]; Pre[i]->next[i]= p; } list->num++; //跳跃链表的计数器加1 return 1; }
int RandomLevelint maxlevel)//产生随机层数,在各塔中自底向上逐层生长。 { int i= 1; while (rand() % 2) i++; i= (i> maxlevel) ? maxlevel :i; return i; }
三，散列表的概念
这个地方的内容我会放到数据结构里面讲，这里就不做讲解了。
