两天时间,白天看虚拟存储器,晚上到家写这个东西,刚刚写完.缺点不少,功能实现是必须的.
这个东西,是根据习题的要求写的,关于盒子问题,所以我给它取了个名字--盒子树.呵呵.
在写代码的过程中,我希望写完之后大肆庆祝下,.可写完之后,又觉得没什么...呵呵
对于这个东西,我解释下我的分析.
总体要求,就是要求有序.于是我选择了二叉搜索树,考虑过AVL树,后来觉得新东西,还是先简单地实现下.
之后,根据编写过程中的实际情况,一点一点写.做了许多模拟,这次伪代码先出来的.虽然后来被我模块化了.
很高兴的一点,对于二叉搜索树的顺序查找,我想到了中序遍历查找,这是我所高兴的,我觉得这是精髓了,呵呵.
基本上就是这些,我根据要求和现有知识创造了这个东西,我很有成就感.我很高兴!
并不知道,我的这个实现是不是最好的解决方法,虽然是限于我目前的知识水平而言.
对于今后的学习,我决定每套ADT都给出时间复杂度.虽然目前给出的数据不能保证准确.而且决定不时复习以前学过的,刚才写Delete ()居然都卡壳,哎.温故而知新,希望我能这么做.于是不亦乐乎.
不说了,烟抽太多了,贴出代码.
#define GENERIC 10
#define LEFT 1
#define RIGHT 2
/* 数据类型定义 */
typedef int Weight ; // 重量
typedef struct box
{
Weight unoccupied ; // 可用重量
Weight capacity ; // 容量
struct box * parent ;
struct box * left ;
struct box * right ;
} Box ;
typedef struct boxtree
{
Box * root ;
Weight usual ; // 通常情况下的重量
int size ;
} * BoxTree ;
/* 接口函数声明 */
/* 操作: 创建并初始化一个BoxTree */
/* 操作前: pbt 指向一个BoxTree */
/* 操作后: 如果内存分配成功, 创建并初始化一个BoxTree, 默认容量为 capacity, 返回1; 否则返回0 */
/* 时间复杂度: O(1) */
int InitializeBoxTree (BoxTree * const pbt, const Weight capacity) ;
/* 操作: 确定一个BoxTree是否为空 */
/* 操作前: pbt 指向一个已初始化的BoxTree */
/* 操作后: 如果该BoxTree为空, 返回1; 否则返回0 */
/* 时间复杂度: O(1) */
int BoxTreeIsEmpty (const BoxTree * const pbt) ;
/* 操作: 减小指定BoxTree中 >= triangle 最大关键字的值 */
/* 操作前: pbt 指向一个已初始化的BoxTree, triangle 是放入的重量 */
/* 操作后: 如果操作期间内存分配成功, 完成操作, 返回1; 否则返回0 */
/* 时间复杂度: O(2logN) */
int DealWithTheBiggest (BoxTree * const pbt, const Weight triangle) ;
/* 操作: 减小指定BoxTree中 >= triangle 最小关键字的值 */
/* 操作前: pbt 指向一个已初始化的BoxTree, triangle 是放入的重量 */
/* 操作后: 如果操作期间内存分配成功, 完成操作, 返回1; 否则返回0 */
/* 时间复杂度: O(7logN) */
int DealWithTheSmallest (BoxTree * const pbt, const Weight triangle) ;
/* 操作: 以中序将一个函数作用于一棵BoxTree中所有节点1次 */
/* 操作前: pbt 指向一棵已初始化的BoxTree, pfun 指向一个没有返回值, 接受一个Box *类型参数的函数 */
/* 操作后: pfun 指向的函数被以中序作用于BoxTree中所有节点1次 */
/* 时间复杂度: O(logN) */
void InorderTraversal (const Box * const box, void (* pfun) (const Box * const box)) ;
/* 操作: 释放一棵BoxTree所占用的内存空间 */
/* 操作前: pbt 指向一棵已初始化的BoxTree */
/* 操作后: 该BoxTree所占用的内存空间被释放 */
/* 时间复杂度: O(1) */
void Release (const BoxTree * const pbt) ;