学步园

  一晃又是好几天.总算今天是有代码出现了.

  自顶向下伸展树,比去年写的那个伸展树轻松多了.

  人家总结出来的东西,我看懂了,完全让我自己写的话,很难啊.

  这段代码,有些技巧.说的就是"NullNode"到底是怎么回事,具体的自己看代码吧.而且,发现自己的C语言功底还不够,自己补了下,而且接下来会有意识地学一学了.

  不多说了.还有,下周去报名,程序员考试.我干劲.

 /* SplayTree.h -- 自顶向下伸展树头文件 */<br /> /* 酒后写的头文件哦. */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <assert.h></p> <p>/* 明显常量定义 */</p> <p>#define FALSE (0)<br /> #define TRUE (1)</p> <p>/* 数据类型定义 */</p> <p>typedef int BOOL ;</p> <p>typedef int Item ;<br /> typedef struct node<br /> {<br /> Item item ;<br /> struct node * left, * right ;<br /> int leftSubTreeCount, rightSubTreeCount ;<br /> } Node ;<br /> typedef struct splayTree<br /> {<br /> Node * root ;<br /> int current ;<br /> } * SplayTree ;</p> <p>/* 全局变量声明 */</p> <p>static Node * NullNode = NULL ;</p> <p>/* 接口函数声明 */</p> <p>/* 操作: 创建一棵伸展树, 初始化为空, 并且为 NullNode 分配内存空间 */<br /> /* 操作前: pst 指向一棵伸展树 */<br /> /* 操作后: 如果内存分配成功, 创建一棵伸展树, 将其初始为空, 并为 NullNode 分配内存空间, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL Create_S (SplayTree * const pst) ;</p> <p>/* 操作: 确定一棵伸展树是否为空 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树 */<br /> /* 操作后: 如果该伸展树为空, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL IsEmpty_S (const SplayTree * const pst) ;</p> <p>/* 操作: 向伸展树中插入一个元素 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树, pi 指向待添加数据 */<br /> /* 操作后: 如果内存分配成功, 向该伸展树中添加数据域为 *pi 的新结点, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (log N) */<br /> BOOL Insert_S (const SplayTree * const pst, const Item * const pi) ;</p> <p>/* 操作: 返回指向伸展树中根节点的指针 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树 */<br /> /* 操作后: 如果该伸展树不为空, 返回指向该伸展树根结点的指针; 否则返回 NULL */<br /> /* 时间复杂度: O (1) */<br /> Node * Retrieve_S (const SplayTree * const pst) ;</p> <p>/* 操作: 在伸展树中查找指定数据 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树, pi 指向待查找数据 */<br /> /* 操作后: 如果该伸展树不为空 && 找到该数据, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (log N) */<br /> BOOL Find_S (const SplayTree * const pst, const Item * const pi) ;</p> <p>/* 操作: 返回指向伸展树中数据域第k小结点的指针 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树, k 指示待查找数据的序数 */<br /> /* 操作后: 如果该伸展树的大小 >= k && k > 0, 返回指向该伸展树中数据域第 k 小的结点的指针 ; 否则返回 NULL */<br /> /* 时间复杂度: O (log N) */<br /> Node * FindKthMin_S (const SplayTree * const pst, int k) ;</p> <p>/* 操作: 返回指向伸展树中数据域第k大结点的指针 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树, k 指示待查找数据的序数 */<br /> /* 操作后: 如果该伸展树的大小 >= k && k > 0, 返回指向该伸展树中数据域第 k 大的结点的指针 ; 否则返回 NULL */<br /> /* 时间复杂度: O (log N) */<br /> Node * FindKthMax_S (const SplayTree * const pst, int k) ;</p> <p>/* 操作: 返回指向伸展树中最小结点的指针 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树 */<br /> /* 操作后: 如果该伸展树不为空, 返回指向该伸展树中最小结点的指针 ; 否则返回 NULL */<br /> /* 时间复杂度: O (log N) */<br /> Node * FindMin_S (const SplayTree * const pst) ;</p> <p>/* 操作: 返回指向伸展树中最大结点的指针 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树 */<br /> /* 操作后: 如果该伸展树不为空, 返回指向该伸展树中最大结点的指针 ; 否则返回 NULL */<br /> /* 时间复杂度: O (log N) */<br /> Node * FindMax_S (const SplayTree * const pst) ;</p> <p>/* 操作: 删除伸展树中数据域为指定数据的结点 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树, pi 指向待删除数据 */<br /> /* 操作后: 如果该伸展树不为空 && 找到该结点, 删除该结点, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (log N) */<br /> BOOL Delete_S (const SplayTree * const pst, const Item * const pi) ;</p> <p>/* 操作: 以中序将一个函数依次作用于伸展树中所有结点1次 */<br /> /* 操作前: pr 指向一棵已初始化的伸展树的根, pfun 指向一个没有返回值, 接受一个 Node * 类型参数的函数 */<br /> /* 操作后: pfun 指向的函数以中序作用于该伸展树中所有结点1次 */<br /> /* 时间复杂度: O (log N) */<br /> void Traversal_S (const Node * const pr, void (* pfun) (const Node * const pn)) ;</p> <p>/* 操作: 释放一棵伸展树占用的内存空间 */<br /> /* 操作前: pst 指向一棵已初始化的伸展树 */<br /> /* 操作后: 该伸展树占用的内存空间被释放 */<br /> /* 时间复杂度: O (log N) */<br /> void Release_S (const SplayTree * const pst) ;