• 团团圆圆
    了解作者
  • C/C++
    开发工具
  • 7KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 2
    下载次数
  • 2018-12-29 15:29
    上传日期
利用avl树实现的hash表,自己测试成功。
hashtest_avltree.zip
  • hashtest_avltree
  • DSLibrary
  • Hash
  • Hash.h
    548B
  • Hash.c
    2KB
  • AvlTree
  • AvlTree.c
    13.9KB
  • AvlTree.h
    913B
  • main.c
    7.7KB
  • Makefile
    584B
内容介绍
#include <stdio.h> #include <malloc.h> #include "AvlTree.h" #define Max(a,b) (((a) > (b)) ? (a) : (b)) #define Min(a,b) (((a) < (b)) ? (a) : (b)) typedef struct _tag_AvlTree TAvlTree; struct _tag_AvlTree { int count; AvlTreeNode *root; }; /* static int Max(int Lhs,int Rhs) { return Lhs > Rhs ? Lhs : Rhs; } */ static int Height(AvlTreeNode *P) { if(NULL == P) return -1; else return (P->height); } //RR旋转 static AvlTreeNode *SingleRotateWithLeft(AvlTreeNode *K2) { AvlTreeNode *K1 = NULL; K1 = K2->left; K2->left = K1->right; K1->right = K2; K2->height = Max(Height(K2->left), Height(K2->right)) + 1; K1->height = Max(Height(K1->left), K2->height) + 1; return K1; } //LL旋转 static AvlTreeNode *SingleRotateWithRight(AvlTreeNode *K1) { AvlTreeNode *K2 = NULL; K2 = K1->right; K1->right = K2->left; K2->left = K1; K1->height = Max(Height(K1->left), Height(K1->right)) + 1; K2->height = Max(Height(K2->right), K1->height) + 1; return K2; } //LR旋转 static AvlTreeNode *DoubleRotateWithLeft(AvlTreeNode *K3) { K3->left = SingleRotateWithRight(K3->left); return SingleRotateWithLeft(K3); } //RL旋转 static AvlTreeNode *DoubleRotateWithRight(AvlTreeNode *K3) { K3->right = SingleRotateWithLeft(K3->right); return SingleRotateWithRight(K3); } static int RecursiveInsert(AvlTreeNode **pRoot, AvlTreeNode* node, AvlTree_Compare* compare) { int s32Ret = -1; s32Ret = compare(node->key, (*pRoot)->key); if(s32Ret < 0) { if(NULL != (*pRoot)->left) { s32Ret = RecursiveInsert(&((*pRoot)->left), node, compare); if(s32Ret < 0) { s32Ret = -1; printf("[MSG::%s::%d]: RecursiveInsert error.\n", __func__, __LINE__); goto exit; } } else { (*pRoot)->left = node; (*pRoot)->left->height++; } if(2 == (Height((*pRoot)->left) - Height((*pRoot)->right))) { s32Ret = compare(node->key, (*pRoot)->left->key); if(s32Ret < 0) { (*pRoot) = SingleRotateWithLeft((*pRoot)); } else if(s32Ret > 0) { (*pRoot) = DoubleRotateWithLeft((*pRoot)); } } } else if(s32Ret > 0) { if(NULL != (*pRoot)->right) { s32Ret = RecursiveInsert(&((*pRoot)->right), node, compare); if(s32Ret < 0) { s32Ret = -1; printf("[MSG::%s::%d]: RecursiveInsert error.\n", __func__, __LINE__); goto exit; } } else { (*pRoot)->right = node; (*pRoot)->right->height++; } if(2 == (Height((*pRoot)->right) - Height((*pRoot)->left))) { s32Ret = compare(node->key, (*pRoot)->right->key); if(s32Ret > 0) { (*pRoot) = SingleRotateWithRight((*pRoot)); } else if(s32Ret < 0) { (*pRoot) = DoubleRotateWithRight((*pRoot)); } } } else if(0 == s32Ret) { //key in the tree already, do nothing. s32Ret= -1; goto exit; } (*pRoot)->height = Max(Height((*pRoot)->left), Height((*pRoot)->right)) + 1; s32Ret = 0; exit: return s32Ret; } static AvlTreeNode* RecursiveGet(AvlTreeNode* root, AvlKey* key, AvlTree_Compare* compare) { if(NULL == root) { printf("[MSG::%s::%d]: This Avl tree does not have the key.\n", __func__, __LINE__); return NULL; } AvlTreeNode* pAvlTreeNode = NULL; int s32Compare = compare(key, root->key); if(0 == s32Compare) { pAvlTreeNode = root; } else if(s32Compare == -1) { pAvlTreeNode = RecursiveGet(root->left, key, compare); } else if(s32Compare > 0) { pAvlTreeNode = RecursiveGet(root->right, key, compare); } return pAvlTreeNode; } static AvlTreeNode *RecursiveDelete(AvlTreeNode **pRoot, AvlKey *key, AvlTree_Compare *compare) { //printf("[MSG::%s::%d]: RecursiveDelete.\n", __func__, __LINE__); if(NULL == *pRoot) { printf("[MSG::%s::%d]: This Avl tree does not have the key.\n", __func__, __LINE__); return NULL; } AvlTreeNode *deleteNode = NULL; int s32Compare = compare(key, (*pRoot)->key); if(0 == s32Compare) { //printf("[MSG::%s::%d]: ==0.\n", __func__, __LINE__); deleteNode = (*pRoot); //printf("[MSG::%s::%d]: &deleteNode = 0x%x.\n", __func__, __LINE__, deleteNode); //printf("[MSG::%s::%d]: deleteNode->key = %d.\n", __func__, __LINE__, *((short *)(deleteNode->key))); if((NULL != (*pRoot)->left) && (NULL != (*pRoot)->right)) { //printf("[MSG::%s::%d]: debug_0001.\n", __func__, __LINE__); if(Height((*pRoot)->left) > Height((*pRoot)->right)) { //printf("[MSG::%s::%d]: debug_0002.\n", __func__, __LINE__); AvlTreeNode *tmpNode = (*pRoot); AvlTreeNode *maxNode = AvlTree_FindMax((*pRoot)->left); if(NULL != maxNode) { deleteNode = RecursiveDelete(&(tmpNode->left), maxNode->key, compare); maxNode->left = tmpNode->left; maxNode->right = (*pRoot)->right; maxNode->height = (*pRoot)->height; tmpNode = (*pRoot); (*pRoot) = maxNode; deleteNode = tmpNode; } } else { //printf("[MSG::%s::%d]: debug_0003.\n", __func__, __LINE__); AvlTreeNode *tmpNode = (*pRoot); AvlTreeNode *minNode = AvlTree_FindMin((*pRoot)->right); if(NULL != minNode) { deleteNode = RecursiveDelete(&(tmpNode->right), minNode->key, compare); minNode->right = tmpNode->right; minNode->left = (*pRoot)->left; minNode->height = (*pRoot)->height; tmpNode = (*pRoot); (*pRoot) = minNode; deleteNode = tmpNode; } } } else { (*pRoot) = ((*pRoot)->left) ? ((*pRoot)->left) : ((*pRoot)->right); } } else if(s32Compare == -1) { //printf("[MSG::%s::%d]: <0.\n", __func__, __LINE__); deleteNode = RecursiveDelete(&((*pRoot)->left), key, compare); if(Height((*pRoot)->right) - Height((*pRoot)->left) == 2) { if(Height((*pRoot)->right->left) > Height((*pRoot)->right->right)) { (*pRoot) = DoubleRotateWithRight((*pRoot)); } else { (*pRoot) = SingleRotateWithRight((*pRoot)); } } } else if(s32Compare > 0) { //printf("[MSG::%s::%d]: >0.\n", __func__, __LINE__); deleteNode = RecursiveDelete(&((*pRoot)->right), key, compare); if(Height((*pRoot)->left) - Height((*pRoot)->right) == 2) { if(Height((*pRoot)->left->right) > Height((*pRoot)->left->left)) { (*pRoot
评论
    相关推荐
    • hash.zip
      创建一个AVL树算法,并在此基础上完成部分功能
    • 左程云leetcode-algorithm-and-data-structure:算法+数据结构=程序
      左程云leetcode 数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 ...二维数组(Array2D) ...哈希Hash Table) 哈希函数(Hash Functions) 6. 优先队列(Priority Queue) 堆
    • 数据结构名校课件压缩文件
      高校数据结构的课件。比较概括的叙述了有关链表,,堆栈的基本概念,对初学者很有帮助。
    • goadsl:Go 算法和数据结构库
      目标 Go 算法和数据结构库 变更日志: 2014-09-09 初始发布 2014-09-13 添加单向链表(狄凯敏) 2014-09-14 修复了单向链表中的 InsertLast() 和 Print() 方法,添加了双向链表 (Dikaimin) 2014-09-16 添加队列 ...
    • leetcode下载-leetcode:leetcode练习
      结构:主干为数组,相同hash值碰撞为链表,链表长度超过8转为红黑(1.8新增,查找效率更高) 14 . HashMap 的resize 和 负载因子 负载因子大 时间开销大 空间开销小 负载因子小 时间开销小 空间开销大 如果负载因子...
    • java中负数的源码反码补码-interviews:CS面试学习
      数组是具有指定大小的集合动态数组:某些语言的实现会在您添加元素时自动扩展 通过索引直接访问元素 时间复杂度: 按索引访问: O(1) 按值搜索: O(n) 插入: O(n) (需要移位值) 删除: O(n) (需要移动值) 链表 ...
    • leetcode力扣是什么-Interview-Arithmetic:算法练习,主要针对面试过程中遇到的算法题目,所以难度不会太
      AVL树和红黑有什么区别 2021-04-06 快速排序 2021-04-07 路径总合(力扣题目:112) 2021-04-08 如何通过一个不均匀的硬币得到公平的结果 2021-04-09 数组中的第 K 个最大元素 (Leetcode) 2021-04-10 删除排序链表中...
    • CTCI-master.zip
      java二八杠源码破解编码面试 目录 第 1 章:数组和字符串 ...下面的代码实现了一个非常基本的单向链表。 class Node { Node next = null ; int data; public Node ( int d ) { data = d; } void appendToTail
    • basic-java-data-structures:多种(基本)数据结构,以简单易读的Java实现
      基本的Java数据结构 用简单易读的Java实现的各种(基本)数据结构。...AVL树 最小堆 基本/各种数据结构 链表 哈希 队列(ArrayQueue,ListQueue) 堆栈(ArrayListStack,ListStack) 演算法 二进制搜索 N皇后问题
    • matlabcnhelp.rar
      matlab中文帮助很难找的,快速下载