学步园

  最近的代码产量好低,让我很有罪恶感!到家老是想睡觉,感觉很累.也确实,最近确实很累.也可能是因为,自己老是这么认为,才会去累的吧...

  需要调整调整,各种调整.毕竟,想堕落是很容易的.

  这段代码,写了3天多.毕竟,动态规划给我带来的阴影还是很大的.最近研究算法,搞得自信下去了.还好了,这段代码,及时出现了.

  对于随机函数,我的使用,很烂,希望以后有改进.

  帖!

/* SkipList.h -- 跳跃表头文件 */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <assert.h></p> <p>#define FALSE (0)<br /> #define TRUE (1)<br /> #define UNDECIDED (32768)</p> <p>#define A (48271L)<br /> #define M (2147486647L)<br /> #define Q (M / A)<br /> #define R (M % A)<br /> #define MASK (0x01)</p> <p>#define DEBUG (UNDECIDED)</p> <p>/* 数据类型定义 */</p> <p>typedef int Item ;<br /> typedef struct node<br /> {<br /> Item item ;<br /> struct node * * next ;<br /> int height ;<br /> int times ;<br /> } Node ;<br /> typedef struct skiplist<br /> {<br /> Node * head ;<br /> int current ;<br /> int capacity ;<br /> int maximum_of_height ;<br /> } * SkipList ;</p> <p>typedef int BOOL ;</p> <p>/* 全局变量 */</p> <p>long int Seed ;</p> <p>/* 接口函数声明 */</p> <p>/* 操作: 初始化种子 */<br /> /* 操作前: 种子值不确定*/<br /> /* 操作后: 种子被初始化*/<br /> /* 时间复杂度: O (1) */<br /> void InitializSeed_S (const long int initial_value) ;</p> <p>/* 操作: 产生 FALSE 值或者 TRUE 值并返回 */<br /> /* 操作前: 种子已被初始化 */<br /> /* 操作: 产生 FALSE 值或者 TRUE 值并返回 */<br /> /* 时间复杂度: O (1) */<br /> BOOL Random_S (void) ;</p> <p>/* 操作: 创建并初始化一个跳跃表 */<br /> /* 操作前: psl 指向一个跳跃表, capacity 指示该表的最大大小 */<br /> /* 操作后: 如果内存分配成功, 创建该跳跃表, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL Initialize_S (SkipList * const psl, const int capacity) ;</p> <p>/* 操作: 确定一个跳跃表是否为空 */<br /> /* 操作前: psl 指向一个已初始化的跳跃表 */<br /> /* 操作后: 如果该跳跃表为空, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL IsEmpty_S (const SkipList * const psl) ;</p> <p>/* 操作: 确定一个跳跃表是否已满 */<br /> /* 操作前: psl 指向一个已初始化的跳跃表 */<br /> /* 操作后: 如果该跳跃表已满, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL IsFull_S (const SkipList * const psl) ;</p> <p>/* 操作: 确定指定数据是否在跳跃表中 */<br /> /* 操作前: psl 指向一个已初始化的跳跃表, pi 指向指定数据 */<br /> /* 操作后: 如果 pi 指向的数据在该表中, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (log N) */<br /> BOOL Find_S (const SkipList * const psl, const Item * const pi) ;</p> <p>/* 操作: 查找并返回指向跳跃表中最大数据的指针 */<br /> /* 操作前: psl 指向一个已初始化的跳跃表 */<br /> /* 操作后: 如果该跳跃表不为空, 返回指向最大数据的指针; 否则返回 NULL */<br /> /* 时间复杂度: O (log N) */<br /> Item * FindMax_S (const SkipList * const psl)</p> <p>/* 操作: 向跳跃表中插入指定数据 */<br /> /* 操作前: psl 指向一个已初始化的跳跃表, pi 指向指定数据 */<br /> /* 操作后: 如果该跳跃表未满 && 内存分配成功, 在该跳跃表找插入该数据, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (log N) */<br /> BOOL Insert_S (const SkipList * const psl, const Item * const pi) ;</p> <p>/* 操作: 从跳跃表中删除指定数据 */<br /> /* 操作前: psl 指向一个已初始化的跳跃表, pi 指向指定数据 */<br /> /* 操作后: 如果表不为空 && 该数据在该跳跃表中, 从该跳跃表中删除该数据, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (log N) */<br /> BOOL Delete_S (const SkipList * const psl, const Item * const pi) ;</p> <p>/* 操作: 从头至尾将一个函数作用于跳跃表中所有元素1次 */<br /> /* 操作前: psl 指向一个已初始化的跳跃表, pfun 指向一个没有返回值, 接受一个 Node * 类型参数的函数 */<br /> /* 操作后: 从头至尾将一个函数作用于跳跃表中所有元素1次 */<br /> /* 时间复杂度: O (N) */<br /> void Traversal_S (const SkipList * const psl, void (* pfun) (const Node * const pn)) ;</p> <p>/* 操作: 释放一个跳跃表占用的内存空间 */<br /> /* 操作前: psl 指向一个已初始化的跳跃表 */<br /> /* 操作后: 该跳跃表所占内存空间被释放 */<br /> /* 时间复杂度: O (N) */<br /> void Release_S (const SkipList * const psl) ;