博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
哈希表实例
阅读量：5955 次
发布时间：2019-06-19

本文共 8951 字，大约阅读时间需要 29 分钟。

1.#include <stdio.h>

#include <stdlib.h>
#include "Hash.h"
/*  哈希技术的实现  */
struct Student
{
    char* id;
    char* name;
    int age;
};
int compare_id(HashKey* k1, HashKey* k2)
{
    return strcmp((char*)k1, (char*)k2);
}
int main(int argc, char *argv[])
{
    Hash* hash = Hash_Create();
    
    struct Student s1 = {"9001201", "Delphi", 30};
    struct Student s2 = {"0xABCDE", "Java", 20};
    struct Student s3 = {"koabc", "C++", 40};
    struct Student s4 = {"!@#$%^", "C#", 10};
    struct Student s5 = {"Python", "Python", 10};
    struct Student* ps = NULL;
    //add five
    Hash_Add(hash, s1.id, &s1, compare_id);
    Hash_Add(hash, s2.id, &s2, compare_id);
    Hash_Add(hash, s3.id, &s3, compare_id);
    Hash_Add(hash, s4.id, &s4, compare_id);
    Hash_Add(hash, s5.id, &s5, compare_id);
    // by ID get value
    ps = Hash_Get(hash, "koabc", compare_id);
    
    printf("ID: %s\n", ps->id);
    printf("Name: %s\n", ps->name);
    printf("Age: %d\n", ps->age);
    
    Hash_Destroy(hash);
    
    return 0;
}

2.#ifndef _HASH_H_

#define _HASH_H_
typedef void Hash;
typedef void HashKey;
typedef void HashValue;
typedef int (Hash_Compare)(HashKey*, HashKey*);
/*   在二叉排序算法的基础上实现哈希技术的实现   */
Hash* Hash_Create();
void Hash_Destroy(Hash* hash);
void Hash_Clear(Hash* hash);
int Hash_Add(Hash* hash, HashKey* key, HashValue* value, Hash_Compare* compare);
HashValue* Hash_Remove (Hash* hash, HashKey* key, Hash_Compare* compare);
HashValue* Hash_Get(Hash* hash, HashKey* key, Hash_Compare* compare);
int Hash_Count(Hash* hash);
#endif

3.#include <stdio.h>

#include <malloc.h>
#include "Hash.h"
#include "BSTree.h"
typedef struct _tag_HashNode HashNode;
struct _tag_HashNode
{
    BSTreeNode header;
    HashValue* value;
};
void recursive_clear(BSTreeNode* node)
{
    if( node != NULL )
    {
        recursive_clear(node->left);
        recursive_clear(node->right);
        
        free(node);
    }
}
//创建哈希表
Hash* Hash_Create()
{
    return BSTree_Create();
}
//destory
void Hash_Destroy(Hash* hash)
{
    Hash_Clear(hash);
    BSTree_Destroy(hash);
}
//clear
void Hash_Clear(Hash* hash)
{
    recursive_clear(BSTree_Root(hash));
    BSTree_Clear(hash);
}
// add elements
int Hash_Add(Hash* hash, HashKey* key, HashValue* value, Hash_Compare* compare)
{
    int ret = 0;
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    
    if( ret = (node != NULL) )
    {
        node->header.key = key;
        node->value = value;
        // insert
        ret = BSTree_Insert(hash, (BSTreeNode*)node, compare);
        
        if( !ret )
        {
            free(node);
        }
    }
    
    return ret;
}
// remove elements
HashValue* Hash_Remove(Hash* hash, HashKey* key, Hash_Compare* compare)
{
    HashValue* ret = NULL;
    HashNode* node = (HashNode*)BSTree_Delete(hash, key, compare);
    
    if( node != NULL )
    {
        ret = node->value;
        
        free(node);
    }
    
    return ret;
}
// by  key get elements
HashValue* Hash_Get(Hash* hash, HashKey* key, Hash_Compare* compare)
{
    HashValue* ret = NULL;
    HashNode* node = (HashNode*)BSTree_Get(hash, key, compare);
    
    if( node != NULL )
    {
        ret = node->value;
    }
    
    return ret;
}
//count
int Hash_Count(Hash* hash)
{
    return BSTree_Count(hash);
}

4.#ifndef _BSTREE_H_

#define _BSTREE_H_
typedef void BSTree;
typedef void BSKey;
typedef struct _tag_BSTreeNode BSTreeNode;
struct _tag_BSTreeNode
{
    BSKey* key;
    BSTreeNode* left;
    BSTreeNode* right;
};
/*  二叉排序树的封装  */
typedef void (BSTree_Printf)(BSTreeNode*);
typedef int (BSTree_Compare)(BSKey*, BSKey*);
BSTree* BSTree_Create();
void BSTree_Destroy(BSTree* tree);
void BSTree_Clear(BSTree* tree);
int BSTree_Insert(BSTree* tree, BSTreeNode* node, BSTree_Compare* compare);
BSTreeNode* BSTree_Delete(BSTree* tree, BSKey* key, BSTree_Compare* compare);
BSTreeNode* BSTree_Get(BSTree* tree, BSKey* key, BSTree_Compare* compare);
BSTreeNode* BSTree_Root(BSTree* tree);
int BSTree_Height(BSTree* tree);
int BSTree_Count(BSTree* tree);
int BSTree_Degree(BSTree* tree);
void BSTree_Display(BSTree* tree, BSTree_Printf* pFunc, int gap, char div);
#endif

5.#include <stdio.h>

#include <malloc.h>
#include "BSTree.h"
typedef struct _tag_BSTree TBSTree;
struct _tag_BSTree
{
    int count;
    BSTreeNode* root;
};
/*  二叉排序算法的实现  */
static void recursive_display(BSTreeNode* node, BSTree_Printf* pFunc, int format, int gap, char div) // O(n)
{
    int i = 0;
    
    if( (node != NULL) && (pFunc != NULL) )
    {
        for(i=0; i<format; i++)
        {
            printf("%c", div);
        }
        
        pFunc(node);
        
        printf("\n");
        
        if( (node->left != NULL) || (node->right != NULL) )
        {
            recursive_display(node->left, pFunc, format + gap, gap, div);
            recursive_display(node->right, pFunc, format + gap, gap, div);
        }
    }
    else
    {
        for(i=0; i<format; i++)
        {
            printf("%c", div);
        }
        printf("\n");
    }
}
static int recursive_count(BSTreeNode* root) // O(n)
{
    int ret = 0;
    
    if( root != NULL )
    {
        ret = recursive_count(root->left) + 1 + recursive_count(root->right);
    }
    
    return ret;
}
static int recursive_height(BSTreeNode* root) // O(n)
{
    int ret = 0;
    
    if( root != NULL )
    {
        int lh = recursive_height(root->left);
        int rh = recursive_height(root->right);
        
        ret = ((lh > rh) ? lh : rh) + 1;
    }
    
    return ret;
}
static int recursive_degree(BSTreeNode* root) // O(n)
{
    int ret = 0;
    
    if( root != NULL )
    {
        if( root->left != NULL )
        {
            ret++;
        }
        
        if( root->right != NULL )
        {
            ret++;
        }
        
        if( ret == 1 )
        {
            int ld = recursive_degree(root->left);
            int rd = recursive_degree(root->right);
            
            if( ret < ld )
            {
                ret = ld;
            }
            
            if( ret < rd )
            {
                ret = rd;
            }
        }
    }
    
    return ret;
}
static int recursive_insert(BSTreeNode* root, BSTreeNode* node, BSTree_Compare* compare)
{
    int ret = 1;
    int r = compare(node->key, root->key);
    
    if( r == 0 )
    {
        ret = 0;
    }
    else if( r < 0 )
    {
        if( root->left != NULL )
        {
            ret = recursive_insert(root->left, node, compare);
        }
        else
        {
            root->left = node;
        }
    }
    else if( r > 0 )
    {
        if( root->right != NULL )
        {
            ret = recursive_insert(root->right, node, compare);
        }
        else
        {
            root->right = node;
        }
    }
}
static BSTreeNode* recursive_get(BSTreeNode* root, BSKey* key, BSTree_Compare* compare)
{
    BSTreeNode* ret = NULL;
    
    if( root != NULL )
    {
        int r = compare(key, root->key);
        
        if( r == 0 )
        {
            ret = root;
        }
        else if( r < 0 )
        {
            ret = recursive_get(root->left, key, compare);
        }
        else if( r > 0 )
        {
            ret = recursive_get(root->right, key, compare);
        }
    }
    
    return ret;
}
static BSTreeNode* delete_node(BSTreeNode** pRoot)
{
    BSTreeNode* ret = *pRoot;
    
    if( (*pRoot)->right == NULL )
    {
        *pRoot = (*pRoot)->left;
    }
    else if( (*pRoot)->left == NULL )
    {
        *pRoot = (*pRoot)->right;
    }
    else
    {
        BSTreeNode* g = *pRoot;
        BSTreeNode* c = (*pRoot)->left;
        
        while( c->right != NULL )
        {
            g = c;
            c = c->right;
        }
        
        if( g != *pRoot )
        {
            g->right = c->left;
        }
        else
        {
            g->left = c->left;
        }
        c->left = (*pRoot)->left;
        c->right = (*pRoot)->right;
        
        *pRoot = c;
    }
    
    return ret;
}
static BSTreeNode* recursive_delete(BSTreeNode** pRoot, BSKey* key, BSTree_Compare* compare)
{
    BSTreeNode* ret = NULL;
    
    if( (pRoot != NULL) && (*pRoot != NULL) )
    {
        int r = compare(key, (*pRoot)->key);
        
        if( r == 0 )
        {
            ret = delete_node(pRoot);
        }
        else if( r < 0 )
        {
            ret = recursive_delete(&((*pRoot)->left), key, compare);
        }
        else if( r > 0 )
        {
            ret = recursive_delete(&((*pRoot)->right), key, compare);
        }
    }
    
    return ret;
}
BSTree* BSTree_Create() // O(1)
{
    TBSTree* ret = (TBSTree*)malloc(sizeof(TBSTree));
    
    if( ret != NULL )
    {
        ret->count = 0;
        ret->root = NULL;
    }
    
    return ret;
}
void BSTree_Destroy(BSTree* tree) // O(1)
{
    free(tree);
}
void BSTree_Clear(BSTree* tree) // O(1)
{
    TBSTree* btree = (TBSTree*)tree;
    
    if( btree != NULL )
    {
        btree->count = 0;
        btree->root = NULL;
    }
}
int BSTree_Insert(BSTree* tree, BSTreeNode* node, BSTree_Compare* compare)
{
    TBSTree* btree = (TBSTree*)tree;
    int ret = (btree != NULL) && (node != NULL) && (compare != NULL);
    
    if( ret )
    {
        node->left = NULL;
        node->right = NULL;
        
        if( btree->root == NULL )
        {
            btree->root = node;
        }
        else
        {
            ret = recursive_insert(btree->root, node, compare);
        }
        
        if( ret )
        {
            btree->count++;
        }
    }
    
    return ret;
}
BSTreeNode* BSTree_Delete(BSTree* tree, BSKey* key, BSTree_Compare* compare)
{
    TBSTree* btree = (TBSTree*)tree;
    BSTreeNode* ret = NULL;
    
    if( (btree != NULL) && (key != NULL) && (compare != NULL) )
    {
        ret = recursive_delete(&btree->root, key, compare);
        
        if( ret != NULL )
        {
            btree->count--;
        }
    }
    
    return ret;
}
BSTreeNode* BSTree_Get(BSTree* tree, BSKey* key, BSTree_Compare* compare)
{
    TBSTree* btree = (TBSTree*)tree;
    BSTreeNode* ret = NULL;
    
    if( (btree != NULL) && (key != NULL) && (compare != NULL) )
    {
        ret = recursive_get(btree->root, key, compare);
    }
    
    return ret;
}
BSTreeNode* BSTree_Root(BSTree* tree) // O(1)
{
    TBSTree* btree = (TBSTree*)tree;
    BSTreeNode* ret = NULL;
    
    if( btree != NULL )
    {
        ret = btree->root;
    }
    
    return ret;
}
int BSTree_Height(BSTree* tree) // O(n)
{
    TBSTree* btree = (TBSTree*)tree;
    int ret = 0;
    
    if( btree != NULL )
    {
        ret = recursive_height(btree->root);
    }
    
    return ret;
}
int BSTree_Count(BSTree* tree) // O(1)
{
    TBSTree* btree = (TBSTree*)tree;
    int ret = 0;
    
    if( btree != NULL )
    {
        ret = btree->count;
    }
    
    return ret;
}
int BSTree_Degree(BSTree* tree) // O(n)
{
    TBSTree* btree = (TBSTree*)tree;
    int ret = 0;
    
    if( btree != NULL )
    {
        ret = recursive_degree(btree->root);
    }
    
    return ret;
}
void BSTree_Display(BSTree* tree, BSTree_Printf* pFunc, int gap, char div) // O(n)
{
    TBSTree* btree = (TBSTree*)tree;
    
    if( btree != NULL )
    {
        recursive_display(btree->root, pFunc, 0, gap, div);
    }
}

 

转载于:https://www.cnblogs.com/wxb20/p/6197111.html

你可能感兴趣的文章
Git 忽略文件
查看>>
Zabbix-server安装后的故障处理及Zabbix-agent的配置添加过程
查看>>
电子罗盘的分类
查看>>
分布式链路追踪工具skywalking 介绍
查看>>
struct和typedef struct
查看>>
Linux基础管理——磁盘管理及文件系统（全）
查看>>
【自用】手工编译lnmp环境
查看>>
普通用户通过Putty密钥方式登录
查看>>
网页显示3D模型
查看>>
第六章：thymeleaf页面模版-1. 信息输出
查看>>
Azure Table storage 基本用法
查看>>
Ubuntu 16.04 install Docker 1.12.0
查看>>
2012《Linux杂志》读者选择奖 （Readers' Choice Awards 2012- Linux Journal）
查看>>
21天让你成为Horizon View高手—Day11:手动池的创建
查看>>
Python迭代对象、迭代器、生成器
查看>>
请求转发与重定向的区别
查看>>
大数据分析 | 百年奥运往事知多少
查看>>
js面向对象开发
查看>>
矩形覆盖-----批了外皮的亲蛙跳
查看>>
java设计模式之责任链模式
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-12-28 21:13:51   当前IP: 3.135.199.179   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我