学步园

  学树第四天,第一课伸展树.写了8小时,好困啊.感觉真好.写完自己又读了一遍,记下了.

  贴出来,还希望有人愿意跟我交流.

/* splay_tree.c -- 伸展树实现文件 */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include "splay_tree.h"</p> <p>/* 局部数据类型定义 */<br /> typedef Position Stack_Item ;<br /> typedef struct stack_node<br /> {<br /> Stack_Item item ;<br /> struct stack_node * next ;<br /> } Stack_Node ;<br /> typedef Stack_Node * Stack ;</p> <p>/* 局部函数声明 */<br /> Position Make_Node (const Item item) ;<br /> int Left_Is_Greater_Than_Right (const Item left, const Item right) ;<br /> int Left_Is_Lesser_Than_Right (const Item left, const Item right) ;<br /> void Copy_Item_To_Node (const Item * const pitem, Position * const pnew_node) ;<br /> Position Discover_Item (const SplayTree tree, const Item item) ;<br /> Position The_Parent_Of (const SplayTree tree, const Position target) ;<br /> Position Single_Rotate_With_Left (Position K2) ;<br /> Position Single_Rotate_With_Right (Position K2) ;<br /> Position Zig_Zig_Rotate_With_Left (Position K3) ;<br /> Position Zig_Zig_Rotate_With_Right (Position K3) ;<br /> Position Zig_Zag_Rotate_With_Left (Position K3) ;<br /> Position Zig_Zag_Rotate_With_Right (Position K3) ;<br /> void Initialize_Stack (Stack * pstack) ;<br /> int Stack_Is_Empty (const Stack * const pstack) ;<br /> int Stack_Is_Full (void) ;<br /> int Push (Stack * pstack, const Stack_Item item) ;<br /> Stack_Item Top (const Stack * const pstack, const int number) ;<br /> int Stack_Item_Count (const Stack * const pstack) ;<br /> int Pop (Stack * pstack, const int number) ;<br /> void Empty_The_Stack (Stack * pstack) ;<br /> Stack Discover_Item_By_Use_Stack (const SplayTree tree, const Item item) ;</p> <p>/* 接口函数定义 */</p> <p>void IintializeSplayTree (SplayTree * ptree)<br /> {<br /> (*ptree) = NULL ;<br /> }</p> <p>int SplayTreeIsEmpty (const SplayTree tree)<br /> {<br /> return NULL == tree ;<br /> }</p> <p>int SplayTreeIsFull (void)<br /> {<br /> Position temp ;</p> <p> temp = (Node *) malloc (sizeof (Node)) ;<br /> if (NULL == temp)<br /> return 1 ;<br /> else<br /> {<br /> free (temp) ;<br /> return 0 ;<br /> }<br /> }</p> <p>SplayTree AddItem (SplayTree tree, const Item item)<br /> {<br /> Position new_node, scan = tree ;</p> <p> new_node = Make_Node (item) ;<br /> if (NULL == new_node)<br /> return tree ;<br /> if (SplayTreeIsEmpty (tree))<br /> return tree = new_node ;<br /> while (scan != NULL)<br /> {<br /> if (Left_Is_Greater_Than_Right (item, scan -> item))<br /> {<br /> if (NULL == scan -> right)<br /> break ;<br /> else<br /> scan = scan -> right ;<br /> }<br /> else if (Left_Is_Lesser_Than_Right (item, scan -> item))<br /> {<br /> if (NULL == scan -> left)<br /> break ;<br /> else<br /> scan = scan -> left ;<br /> }<br /> /* 发生需要重复添加的情况 */<br /> else<br /> return tree ;<br /> }<br /> if (Left_Is_Greater_Than_Right (item, scan -> item))<br /> scan -> right = new_node ;<br /> else if (Left_Is_Lesser_Than_Right (item, scan -> item))<br /> scan -> left = new_node ;</p> <p> return tree ;<br /> }</p> <p>SplayTree Insert (SplayTree tree, const Item item)<br /> {<br /> Position new_node ;</p> <p> if (NULL == tree)<br /> {<br /> new_node = Make_Node (item) ;<br /> return new_node ;<br /> }<br /> if (Left_Is_Greater_Than_Right (item, tree -> item))<br /> tree -> right = Insert (tree -> right, item) ;<br /> else if (Left_Is_Lesser_Than_Right (item, tree -> item))<br /> tree -> left = Insert (tree -> left, item) ;<br /> /* 发生需要重复添加的情况 */<br /> else<br /> return tree ;</p> <p> return tree ;<br /> }</p> <p>Position FindMax (const SplayTree tree)<br /> {<br /> Position scan = tree ;</p> <p> if (NULL == scan)<br /> return NULL ;<br /> while (scan -> right != NULL)<br /> scan = scan -> right ;</p> <p> return scan ;<br /> }</p> <p>Position FindMin (const SplayTree tree)<br /> {<br /> Position scan = tree ;</p> <p> if (NULL == scan)<br /> return NULL ;<br /> while (scan -> left != NULL)<br /> scan = scan -> left ;</p> <p> return scan ;<br /> }</p> <p>SplayTree Find (SplayTree tree, const Item item)<br /> {<br /> Position target, parent, grandfather, greatgrandfather ;</p> <p> target = Discover_Item (tree, item) ;<br /> /* 如果未找到 */<br /> if (NULL == target)<br /> return tree ;<br /> /* 循环条件:当前结点不是根节点 */<br /> while ((parent = The_Parent_Of (tree, target)) != NULL)<br /> {<br /> /* 如果父节点是根节点 */<br /> if (tree == parent)<br /> {<br /> if (Left_Is_Greater_Than_Right (item, parent -> item))<br /> target = Single_Rotate_With_Right (parent) ;<br /> else<br /> target = Single_Rotate_With_Left (parent) ;<br /> }<br /> else<br /> {<br /> grandfather = The_Parent_Of (tree, parent) ;<br /> /* 如果在父结点左侧 */<br /> if (Left_Is_Lesser_Than_Right (target -> item, parent -> item))<br /> {<br /> if (Left_Is_Greater_Than_Right (parent -> item, grandfather -> item))<br /> target = Zig_Zag_Rotate_With_Right (grandfather) ; /* 右之字形旋转 */<br /> else<br /> target = Zig_Zig_Rotate_With_Left (grandfather) ; /* 左一字形旋转 */<br /> }<br /> /* 如果在父结点右侧 */<br /> else<br /> {<br /> if (Left_Is_Greater_Than_Right (parent -> item, grandfather -> item))<br /> target = Zig_Zig_Rotate_With_Right (grandfather) ; /* 右一字形旋转 */<br /> else<br /> target = Zig_Zag_Rotate_With_Left (grandfather) ; /* 左之字形旋转 */<br /> }<br /> /* 如果爷结点之上才是根节点 */<br /> if (grandfather != tree)<br /> {<br /> greatgrandfather = The_Parent_Of (tree, grandfather) ;<br /> if (Left_Is_Greater_Than_Right (grandfather -> item, greatgrandfather -> item))<br /> greatgrandfather -> right = target ;<br /> else<br /> greatgrandfather -> left = target ;<br /> /* 更新循环条件.即目标结点在树中位置 */<br /> target = Discover_Item (tree, item) ;<br /> }<br /> }<br /> }</p> <p> return target ;<br /> }</p> <p>SplayTree Find_By_Use_Stack (SplayTree tree, const Item item)<br /> {<br /> Stack stack ;<br /> Position target, parent, grandfather, greatgrandfather ;</p> <p> target = Discover_Item (tree, item) ;<br /> if (NULL == target)<br /> return tree ;<br /> stack = Discover_Item_By_Use_Stack (tree, item) ;<br /> while (!Stack_Is_Empty (&stack))<br /> {<br /> parent = Top (&stack, 1) ;<br /> /* 如果父结点是根节点(即栈中只有一个结点) */<br /> if (1 == Stack_Item_Count (&stack))<br /> {<br /> if (Left_Is_Greater_Than_Right (item, parent -> item))<br /> target = Single_Rotate_With_Right (parent) ;<br /> else<br /> target = Single_Rotate_With_Left (parent) ;<br /> Pop (&stack, 1) ;<br /> }<br /> else<br /> {<br /> grandfather = Top (&stack, 2) ;<br /> /* 如果在父结点左侧 */<br /> if (Left_Is_Lesser_Than_Right (target -> item, parent -> item))<br /> {<br /> if (Left_Is_Greater_Than_Right (parent -> item, grandfather -> item))<br /> target = Zig_Zag_Rotate_With_Right (grandfather) ; /* 右之字形旋转 */<br /> else<br /> target = Zig_Zig_Rotate_With_Left (grandfather) ; /* 左一字形旋转 */<br /> }<br /> /* 如果在父结点右侧 */<br /> else<br /> {<br /> if (Left_Is_Greater_Than_Right (parent -> item, grandfather -> item))<br /> target = Zig_Zig_Rotate_With_Right (grandfather) ; /* 右一字形旋转 */<br /> else<br /> target = Zig_Zag_Rotate_With_Left (grandfather) ; /* 左之字形旋转 */<br /> }<br /> if (Stack_Item_Count (&stack) > 2)<br /> {<br /> greatgrandfather = Top (&stack, 3) ;<br /> if (Left_Is_Greater_Than_Right (grandfather -> item, greatgrandfather -> item))<br /> greatgrandfather -> right = target ;<br /> else<br /> greatgrandfather -> left = target ;<br /> }<br /> Pop (&stack, 2) ;<br /> }<br /> }</p> <p> return target ;<br /> }</p> <p>SplayTree Delete (SplayTree tree, const Item item)<br /> {<br /> SplayTree left_subtree, right_subtree ;<br /> Position new_root, temp ;</p> <p> /* 如果未找到 */<br /> if (NULL == Discover_Item (tree, item))<br /> return tree ;<br /> tree = Find_By_Use_Stack (tree, item) ;<br /> left_subtree = tree -> left ;<br /> right_subtree = tree -> right ;<br /> temp = tree ;<br /> if (NULL == left_subtree && NULL == right_subtree)<br /> tree = NULL ;<br /> /* 如果左子树为空,右子树不为空 */<br /> else if (NULL == tree -> left)<br /> {<br /> new_root = FindMin (right_subtree) ;<br /> tree = Find_By_Use_Stack (right_subtree, new_root -> item) ;<br /> }<br /> /* 否则左子树不为空,则当前正在处理理想情况.右子树是否为空无关紧要 */<br /> else<br /> {<br /> new_root = FindMax (left_subtree) ;<br /> left_subtree = Find_By_Use_Stack (left_subtree, new_root -> item) ;<br /> /* 左子树中最大数据的结点被旋转到根结点的位置,它一定没有右子树 */<br /> left_subtree -> right = right_subtree ;<br /> tree = left_subtree ;<br /> }<br /> free (temp) ;</p> <p> return tree ;<br /> }</p> <p>void InorderTraversal (const SplayTree tree, void (* pfun) (const Item item))<br /> {<br /> if (tree != NULL)<br /> {<br /> InorderTraversal (tree -> left, pfun) ;<br /> (*pfun) (tree -> item) ;<br /> InorderTraversal (tree -> right, pfun) ;<br /> }<br /> }</p> <p>/* 局部函数定义 */</p> <p>Position Make_Node (const Item item)<br /> {<br /> Position new_node ;</p> <p> new_node = (Node *) malloc (sizeof (Node)) ;<br /> if (NULL == new_node)<br /> return NULL ;<br /> else<br /> {<br /> Copy_Item_To_Node (&item, &new_node) ;<br /> new_node -> left = NULL ;<br /> new_node -> right = NULL ;<br /> return new_node ;<br /> }<br /> }<br /> int Left_Is_Greater_Than_Right (const Item left, const Item right)<br /> {<br /> return left > right ;<br /> }</p> <p>int Left_Is_Lesser_Than_Right (const Item left, const Item right)<br /> {<br /> return left < right ;<br /> }</p> <p>void Copy_Item_To_Node (const Item * const pitem, Position * const pnew_node)<br /> {<br /> (*pnew_node) -> item = *pitem ;<br /> }</p> <p>Position Discover_Item (const SplayTree tree, const Item item)<br /> {<br /> Position scan = tree ;</p> <p> while (scan != NULL)<br /> {<br /> if (Left_Is_Greater_Than_Right (item, scan -> item))<br /> scan = scan -> right ;<br /> else if (Left_Is_Lesser_Than_Right (item, scan -> item))<br /> scan = scan -> left ;<br /> /* 接下来找到了,返回该结点的指针 */<br /> else<br /> return scan ;<br /> }</p> <p> return NULL ;<br /> }</p> <p>Position The_Parent_Of (const SplayTree tree, const Position target)<br /> {<br /> Position parent = tree, scan = tree ;</p> <p> if (tree == target)<br /> return NULL ;<br /> while (scan != NULL)<br /> {<br /> if (Left_Is_Greater_Than_Right (target -> item, scan -> item))<br /> {<br /> parent = scan ;<br /> scan = scan -> right ;<br /> }<br /> else if (Left_Is_Lesser_Than_Right (target -> item, scan -> item))<br /> {<br /> parent = scan ;<br /> scan = scan -> left ;<br /> }<br /> else<br /> return parent ;<br /> }</p> <p> return NULL ;<br /> }</p> <p>Position Single_Rotate_With_Left (Position K2)<br /> {<br /> Position K1 = K2 -> left ;</p> <p> K2 -> left = K1 -> right ;<br /> K1 -> right = K2 ;</p> <p> return K1 ;<br /> }<br /> Position Single_Rotate_With_Right (Position K2)<br /> {<br /> Position K1 = K2 -> right ;</p> <p> K2 -> right = K1 -> left ;<br /> K1 -> left = K2 ;</p> <p> return K1 ;<br /> }</p> <p>/* 一字型旋转是从K3 - K2 - K1 */<br /> Position Zig_Zig_Rotate_With_Left (Position K3)<br /> {<br /> Position K2 = K3 -> left ;<br /> Position K1 = K2 -> left ;</p> <p> K3 -> left = K2 -> right ;<br /> K2 -> right = K3 ;<br /> K2 -> left = K1 -> right ;<br /> K1 -> right = K2 ;</p> <p> return K1 ;<br /> }<br /> Position Zig_Zig_Rotate_With_Right (Position K3)<br /> {<br /> Position K2 = K3 -> right ;<br /> Position K1 = K2 -> right ;</p> <p> K3 -> right = K2 -> left ;<br /> K2 -> left = K3 ;<br /> K2 -> right = K1 -> left ;<br /> K1 -> left = K2 ;</p> <p> return K1 ;<br /> }</p> <p>/* 之字形旋转是从K1 - K2 - K3 */<br /> Position Zig_Zag_Rotate_With_Left (Position K3)<br /> {<br /> Position K2 = K3 -> left ;<br /> Position K1 = K2 -> right ;</p> <p> K2 -> right = K1 -> left ;<br /> K1 -> left = K2 ;<br /> K3 -> left = K1 -> right ;<br /> K1 -> right = K3 ;</p> <p> return K1 ;<br /> }<br /> Position Zig_Zag_Rotate_With_Right (Position K3)<br /> {<br /> Position K2 = K3 -> right ;<br /> Position K1 = K2 -> left ;</p> <p> K2 -> left = K1 -> right ;<br /> K1 -> right = K2 ;<br /> K3 -> right = K1 -> left ;<br /> K1 -> left = K3 ;</p> <p> return K1 ;<br /> }</p> <p>/* 栈部分函数定义 */<br /> void Initialize_Stack (Stack * pstack)<br /> {<br /> *pstack = NULL ;<br /> }</p> <p>int Stack_Is_Empty (const Stack * const pstack)<br /> {<br /> return NULL == *pstack ;<br /> }</p> <p>int Stack_Is_Full (void)<br /> {<br /> Stack_Node * temp ;</p> <p> temp = (Stack_Node *) malloc (sizeof (Stack_Node)) ;<br /> if (NULL == temp)<br /> return 1 ;<br /> else<br /> {<br /> free (temp) ;<br /> return 0 ;<br /> }<br /> }</p> <p>int Push (Stack * pstack, const Stack_Item item)<br /> {<br /> Stack_Node * new_node ;</p> <p> new_node = (Stack_Node *) malloc (sizeof (Stack_Node)) ;<br /> if (NULL == new_node)<br /> return 0 ;<br /> new_node -> item = item ;<br /> if (Stack_Is_Empty (pstack))<br /> {<br /> new_node -> next = NULL ;<br /> *pstack = new_node ;<br /> }<br /> else<br /> {<br /> new_node -> next = *pstack ;<br /> *pstack = new_node ;<br /> }</p> <p> return 1 ;<br /> }</p> <p>Stack_Item Top (const Stack * const pstack, const int number)<br /> {<br /> Stack_Node * scan = *pstack ;<br /> int count = 1 ;</p> <p> while (count < number)<br /> {<br /> if (NULL == scan)<br /> return NULL ;<br /> scan = scan -> next ;<br /> /* Don't forgrt this line!!! */<br /> count++ ;<br /> }</p> <p> return scan -> item ;<br /> }</p> <p>int Stack_Item_Count (const Stack * const pstack)<br /> {<br /> Stack_Node * temp = *pstack ;<br /> int count = 0 ;</p> <p> while (temp != NULL)<br /> {<br /> temp = temp -> next ;<br /> /* Don't forget this line!!! */<br /> count++ ;<br /> }</p> <p> return count ;<br /> }</p> <p>int Pop (Stack * pstack, const int number)<br /> {<br /> Stack_Node * temp ;<br /> int count = 0 ;</p> <p> while (count < number)<br /> {<br /> if (NULL == *pstack)<br /> return 0 ;<br /> temp = *pstack ;<br /> *pstack = (*pstack) -> next ;<br /> free (temp) ;<br /> /* Don't forget this line!!! */<br /> count++ ;<br /> }</p> <p> return 1 ;<br /> }</p> <p>void Empty_The_Stack (Stack * pstack)<br /> {<br /> Stack_Node * temp ;</p> <p> while (*pstack != NULL)<br /> {<br /> temp = *pstack ;<br /> *pstack = (*pstack) -> next ;<br /> free (temp) ;<br /> }<br /> }</p> <p>Stack Discover_Item_By_Use_Stack (const SplayTree tree, const Item item)<br /> {<br /> Stack stack ;<br /> Position scan = tree ;</p> <p> Initialize_Stack (&stack) ;<br /> while (scan != NULL)<br /> {<br /> Push (&stack, scan) ;<br /> if (Left_Is_Greater_Than_Right (item, scan -> item))<br /> scan = scan -> right ;<br /> else if (Left_Is_Lesser_Than_Right (item, scan -> item))<br /> scan = scan -> left ;<br /> else<br /> {<br /> /* 弹出目标找到的结点 */<br /> Pop (&stack, 1) ;<br /> return stack ;<br /> }<br /> }<br /> Empty_The_Stack (&stack) ;</p> <p> return NULL ;<br /> }