学步园

/* box.c -- 盒子问题实现文件 */<br /> #ifndef GENERIC<br /> #include "box.h"<br /> #endif</p> <p>/* 局部函数声明 */</p> <p>static Box * Make_Box (const Weight capacity) ;<br /> static Box * Find_Max (Box * box) ;<br /> static Box * Find_Min (Box * box) ;<br /> static int Insert_ (BoxTree * const pbt, const Weight capacity, const Weight unoccupied) ;<br /> static Box * Delete_ (Box * root, const Weight unoccupied) ;<br /> static Box * Inorder_Find (Box * box, const Weight unoccupied) ;<br /> static void Work_For_Release (Box * const box) ;</p> <p>/* 接口函数定义 */</p> <p>int InitializeBoxTree (BoxTree * const pbt, const Weight capacity)<br /> {<br /> *pbt = (struct boxtree *) malloc (sizeof (struct boxtree)) ;<br /> if (NULL == *pbt)<br /> return 0 ;<br /> (*pbt) -> root = NULL ;<br /> (*pbt) -> size = 0 ;<br /> (*pbt) -> usual = capacity ;</p> <p> return 1 ;<br /> }</p> <p>// 此套例程中的 size 测量不可靠, 主要是时间差的关系<br /> int BoxTreeIsEmpty (const BoxTree * const pbt)<br /> {<br /> return NULL == (*pbt) -> root ;<br /> }</p> <p>int DealWithTheBiggest (BoxTree * const pbt, const Weight triangle)<br /> {<br /> Box * max, * parent ;<br /> Weight capacity, unoccupied ;</p> <p> capacity = triangle > (*pbt) -> usual ? triangle : (*pbt) -> usual ;<br /> if (BoxTreeIsEmpty (pbt))<br /> {<br /> unoccupied = capacity - triangle ;<br /> if (Insert_ (pbt, capacity, unoccupied))<br /> return 1 ;<br /> else<br /> return 0 ;<br /> }<br /> max = Find_Max ((*pbt) -> root) ;<br /> // 没有盒子能够容纳当前物品重量时<br /> if (triangle > max -> unoccupied)<br /> {<br /> unoccupied = capacity - triangle ;<br /> if (Insert_ (pbt, capacity, unoccupied))<br /> return 1 ;<br /> else<br /> return 0 ;<br /> }<br /> // 最大节点能够容纳当前物品时<br /> else<br /> {<br /> unoccupied = max -> unoccupied - triangle ;<br /> // 65行 - 71行是简化了的删除操作<br /> parent = max -> parent ;<br /> free (max) ;<br /> if (parent)<br /> parent -> right = NULL ;<br /> else<br /> (*pbt) -> root = NULL ;<br /> (*pbt) -> size-- ;<br /> if (Insert_ (pbt, capacity, unoccupied))<br /> return 1 ;<br /> else<br /> return 0 ;<br /> }<br /> }</p> <p>int DealWithTheSmallest (BoxTree * const pbt, const Weight triangle)<br /> {<br /> Box * min, * max ;<br /> Weight capacity, unoccupied ;</p> <p> if (BoxTreeIsEmpty (pbt))<br /> {<br /> capacity = triangle > (*pbt) -> usual ? triangle : (*pbt) -> usual ;<br /> unoccupied = capacity - triangle ;<br /> if (Insert_ (pbt, capacity, unoccupied))<br /> return 1 ;<br /> else<br /> return 0 ;<br /> }<br /> max = Find_Max ((*pbt) -> root) ;<br /> // 如果存在能够容纳当前物品重量的盒子<br /> if (max -> unoccupied >= triangle)<br /> {<br /> // 找到符合要求的最小的盒子<br /> min = Inorder_Find ((*pbt) -> root, triangle) ;<br /> capacity = min -> capacity ;<br /> unoccupied = min -> unoccupied - triangle ;<br /> (*pbt) -> root = Delete_ ((*pbt) -> root, min -> unoccupied) ;<br /> (*pbt) -> size-- ;<br /> // 处理特殊情况<br /> if ((*pbt) -> root)<br /> if ((*pbt) -> root -> parent != NULL)<br /> (*pbt) -> root -> parent = NULL ;<br /> // 添加新min<br /> if (Insert_ (pbt, capacity, unoccupied))<br /> return 1 ;<br /> else<br /> return 0 ;<br /> }<br /> // 如果不存在能够容纳当前物品重量的盒子<br /> else<br /> {<br /> capacity = triangle > (*pbt) -> usual ? triangle : (*pbt) -> usual ;<br /> unoccupied = capacity - triangle ;<br /> if (Insert_ (pbt, capacity, unoccupied))<br /> return 1 ;<br /> else<br /> return 0 ;<br /> }<br /> }</p> <p>void InorderTraversal (const Box * const box, void (* pfun) (const Box * const box))<br /> {<br /> if (box)<br /> {<br /> InorderTraversal (box -> left, pfun) ;<br /> (* pfun) (box) ;<br /> InorderTraversal (box -> right, pfun) ;<br /> }<br /> }</p> <p>void Release (const BoxTree * const pbt)<br /> {<br /> Work_For_Release ((*pbt) -> root) ;<br /> free (*pbt) ;<br /> }</p> <p>/* 局部函数定义 */</p> <p>static Box * Make_Box (const Weight capacity)<br /> {<br /> Box * new_box ;</p> <p> new_box = (Box *) malloc (sizeof (Box)) ;<br /> if (NULL == new_box)<br /> return NULL ;<br /> new_box -> capacity = capacity ;<br /> // 此处没有定义指向父节点的指针和剩余容量, 牺牲了模块性<br /> new_box -> left = new_box -> right = NULL ;</p> <p> return new_box ;<br /> }</p> <p>static Box * Find_Max (Box * box)<br /> {<br /> if (NULL == box)<br /> return NULL ;<br /> while (box -> right)<br /> box = box -> right ;</p> <p> return box ;<br /> }</p> <p>static Box * Find_Min (Box * box)<br /> {<br /> if (NULL == box)<br /> return NULL ;<br /> while (box -> left)<br /> box = box -> left ;</p> <p> return box ;<br /> }</p> <p>static int Insert_ (BoxTree * const pbt, const Weight capacity, const Weight unoccupied)<br /> {<br /> int index ;<br /> Box * new_box, * scan ;</p> <p> new_box = Make_Box (capacity) ;<br /> if (NULL == new_box)<br /> return 0 ;<br /> if (BoxTreeIsEmpty (pbt))<br /> {<br /> new_box -> parent = NULL ;<br /> new_box -> unoccupied = unoccupied ;<br /> (*pbt) -> root = new_box ;<br /> }<br /> else<br /> {<br /> scan = (*pbt) -> root ;<br /> while (scan)<br /> {<br /> if (unoccupied > scan -> unoccupied)<br /> {<br /> if (NULL == scan -> right)<br /> {<br /> index = RIGHT ;<br /> break ;<br /> }<br /> else<br /> scan = scan -> right ;<br /> }<br /> // 使空盒子向左靠拢<br /> else if (unoccupied <= scan -> unoccupied)<br /> {<br /> if (NULL == scan -> left)<br /> {<br /> index = LEFT ;<br /> break ;<br /> }<br /> else<br /> scan = scan -> left ;<br /> }<br /> }<br /> if (LEFT == index)<br /> scan -> left = new_box ;<br /> else<br /> scan -> right = new_box ;<br /> new_box -> parent = scan ;<br /> new_box -> unoccupied = unoccupied ;<br /> }</p> <p> (*pbt) -> size++ ;</p> <p> return 1 ;<br /> }</p> <p>static Box * Delete_ (Box * box, const Weight unoccupied)<br /> {<br /> Box * temp ;</p> <p> if (box)<br /> {<br /> if (unoccupied > box -> unoccupied)<br /> box -> right = Delete_ (box -> right, unoccupied) ;<br /> else if (unoccupied < box -> unoccupied)<br /> box -> left = Delete_ (box -> left, unoccupied) ;<br /> else if (box -> left && box -> right)<br /> {<br /> temp = Find_Min (box -> right) ; // 取右子树中最大关键字所在节点<br /> box -> unoccupied = temp -> unoccupied ; // 单纯地替换数据<br /> box -> capacity = temp -> capacity ; // 单纯地替换数据<br /> box -> right = Delete_ (box -> right, box -> unoccupied) ; // 删除倒霉蛋<br /> }<br /> else<br /> {<br /> temp = box ;<br /> if (box -> left) // 不知不觉, 风格有些变了<br /> box = box -> left ;<br /> else<br /> box = box -> right ;<br /> free (temp) ;<br /> }<br /> return box ;<br /> }<br /> else<br /> return NULL ;<br /> }</p> <p>// 自以为这个函数是这套例程的精髓所在.嗑毛磕的时候想到的 ^_^<br /> static Box * Inorder_Find (Box * box, const Weight unoccupied)<br /> {<br /> Box * temp ;</p> <p> if (box)<br /> {<br /> if ((temp = Inorder_Find (box -> left, unoccupied)) != NULL)<br /> return temp ;<br /> if (box -> unoccupied >= unoccupied)<br /> return box ;<br /> if ((temp = Inorder_Find (box -> right, unoccupied)) != NULL)<br /> return temp ;<br /> else<br /> return NULL ;<br /> }<br /> else<br /> return NULL ;<br /> }</p> <p>static void Work_For_Release (Box * const box)<br /> {<br /> if (box)<br /> {<br /> Work_For_Release (box -> left) ;<br /> Work_For_Release (box -> right) ;<br /> free (box) ;<br /> }<br /> }