广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言实现手写Map(数组+链表+红黑树)的示例代码
  • 678

0
分享到

C语言实现手写Map(数组+链表+红黑树)的示例代码

2024-04-02 19:04:59 678人浏览 八月长安
摘要

目录要求结构红黑树和链表转换策略hash使用要求 需要准备数组集合(List) 数据结构 需要准备单向链表(Linked) 数据结构 需要准备红黑树(Rbtree)数据结构 需要准备

要求

需要准备数组集合(List) 数据结构

需要准备单向链表(Linked) 数据结构

需要准备红黑树(Rbtree)数据结构

需要准备红黑树和链表适配策略(文章内部提供,可以自行参考)

建议先去阅读我博客这篇文章C语言-手写Map(数组+链表)(全功能) 有助于理解

HashMap使用红黑树的原因是： 当某个节点值过多的时候那么链表就会非常长,这样搜索的时候查询速度就是O(N) 线性查询了,为了避免这个问题我们使用了红黑树,当链表长度大于8的时候我们转换为红黑树,当红黑树的长度小于6的时候转换为链表,这样既可以利用链表对内存的使用率而且还可以使用红黑树的高效检索，是一种很有效率的数据结构。那么为啥不使用AVL树呢? 因为AVL树是一种高度平衡的二叉树，所以查找的非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多代价。每次插入、删除都要做调整，复杂、耗时。所以，使用红黑树是最好的策略。

结构

红黑树和链表转换策略

#ifndef STUDY_LINKEDKVANDRBTREE_H
#define STUDY_LINKEDKVANDRBTREE_H
#include "charkvlinked.h"
#include "rbtree.h"
typedef int boolean;//定义一个布尔类型
#define TRUE 1
#define FALSE 0
enum LINKEDKV_RBTREE_TYPE{LINKEDKV=0,RBTREE=1};
typedef  struct  linkedKvAndRbTree{
    CharKvLinked *linked; // 链表
    RBTree *rbTree; // 红黑树
    int len;// 长度
    enum LINKEDKV_RBTREE_TYPE type; // 类型
} LinkedKvAndRbTree;
#define  isLinked(linkedKvAndRbTree) ((linkedKvAndRbTree != NULL) && (linkedKvAndRbTree->type == LINKEDKV)) ? TRUE : FALSE
#define  isRbtree(linkedKvAndRbTree) ((linkedKvAndRbTree != NULL) && (linkedKvAndRbTree->type == RBTREE)) ? TRUE : FALSE
LinkedKvAndRbTree *createLinkedKvAndRbTree();
void linked_to_rbtree(LinkedKvAndRbTree *linkedKvAndRbTree);
void rbtree_to_linked(LinkedKvAndRbTree *linkedKvAndRbTree);
void insertOrUpdateLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key,char *value);
void *searchLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key);
void deleteLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key);
CharKvLinked * getAllLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree);
boolean isExistLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key);
void destroyLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree);
// 迭代器结构
typedef struct linkedKvAndRbTreeIterator {
    CharKvLinkednode *next;// 迭代器当前指向
    int count;//迭代次数
    CharKvLinked *linked;//链表
    int index; //位置
}LinkedKvAndRbTreeIterator;

LinkedKvAndRbTreeIterator *createLinkedKvAndRbTreeIterator(LinkedKvAndRbTree *linkedKvAndRbTree);
boolean hasNextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator);
CharKvLinkedNode *nextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator);
#endif //STUDY_LINKEDKVANDRBTREE_H
#include <stdio.h>
#include "linkedKvAndRbTree.h"
#include <stdlib.h>
//创建
LinkedKvAndRbTree *createLinkedKvAndRbTree() {
    LinkedKvAndRbTree *linkedKvAndRbTree= malloc(sizeof(LinkedKvAndRbTree));
    linkedKvAndRbTree->linked=NULL;
    linkedKvAndRbTree->rbTree=NULL;
    linkedKvAndRbTree->len=0;
    linkedKvAndRbTree->type=LINKEDKV;//默认是链表,满足条件则转换为红黑树或者降级为链表
    return linkedKvAndRbTree;
}

void linked_to_rbtree(LinkedKvAndRbTree *linkedKvAndRbTree){
    //链表转换为红黑树(不保证唯一性(可重复),自行判断)
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isLinked(linkedKvAndRbTree)){
        linkedKvAndRbTree->type = RBTREE;
        linkedKvAndRbTree->rbTree = createRBTree();
        CharKvLinkedNode *node = linkedKvAndRbTree->linked->head;
        while(node != NULL){
            insertRBTreeKeyRepetition(linkedKvAndRbTree->rbTree,createRbTreeNode(node->key,node->value));
            node = node->next;
        }
        linkedKvAndRbTree->len = linkedKvAndRbTree->rbTree->size;
        //清除链表
        destroyCharKvLinked(linkedKvAndRbTree->linked);
        linkedKvAndRbTree->linked=NULL;
    }
}
//红黑树转换为链表(不保证唯一性(可重复),自行判断)
void rbtree_to_linked(LinkedKvAndRbTree *linkedKvAndRbTree){
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isRbtree(linkedKvAndRbTree)){
        linkedKvAndRbTree->type = LINKEDKV;
        linkedKvAndRbTree->linked = createCharKvLinked();
        RBNode *node = linkedKvAndRbTree->rbTree->root;
        while(node != NULL){
            insertCharKvLinkedHeadNode(linkedKvAndRbTree->linked,createCharKvLinkedNode(node->key,node->value));
            node = node->right;
        }
        linkedKvAndRbTree->len = linkedKvAndRbTree->linked->len;
        //清除红黑树
        destroyRbTree(linkedKvAndRbTree->rbTree);
        linkedKvAndRbTree->rbTree=NULL;
    }
}

//插入时候key是唯一的,如果冲突那么就修改value
void insertOrUpdateLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key,char *value){
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isLinked(linkedKvAndRbTree)){
        if(linkedKvAndRbTree->linked==NULL){
            linkedKvAndRbTree->linked= createCharKvLinked();
        }
        //长度大于8的时候转换为红黑树
        if(linkedKvAndRbTree->linked->len >=8){
            linked_to_rbtree(linkedKvAndRbTree);
            insertOrUpdateRBTreeKey(linkedKvAndRbTree->rbTree,createRbTreeNode(key,value));
        }else{
            insertOrUpdateCharKvLinkedHeadNode(linkedKvAndRbTree->linked,createCharKvLinkedNode(key,value));
        }
    }else if(isRbtree(linkedKvAndRbTree)){
        if(linkedKvAndRbTree->rbTree==NULL){
            linkedKvAndRbTree->rbTree=createRBTree();
        }
        insertOrUpdateRBTreeKey(linkedKvAndRbTree->rbTree,createRbTreeNode(key,value));
    }else{
        return;
    }

    linkedKvAndRbTree->len++;
}
//查询,返回节点的value
void *searchLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key){
    if(linkedKvAndRbTree == NULL){
        return NULL;
    }
    if(isLinked(linkedKvAndRbTree)){
        CharKvLinkedNode *pNode = searchCharKvLinked(linkedKvAndRbTree->linked, key);
        return pNode!=NULL?pNode->value:NULL;
    }else if(isRbtree(linkedKvAndRbTree)){
        RBNode *pNode = searchRbTree(linkedKvAndRbTree->rbTree, key);
        return pNode!=NULL?pNode->value:NULL;
    }
    return NULL;
}

//判断是否存在
boolean isExistLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key){
    if(linkedKvAndRbTree == NULL){
        return FALSE;
    }
    if(isLinked(linkedKvAndRbTree)){
        return isExistCharKvLinked(linkedKvAndRbTree->linked,key);
    }else if(isRbtree(linkedKvAndRbTree)){
        return isExistRbTree(linkedKvAndRbTree->rbTree,key);
    }
    return FALSE;
}

//删除
void deleteLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key){
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isLinked(linkedKvAndRbTree)){
        delCharKvLinkedNode(linkedKvAndRbTree->linked,key);
    }else if(isRbtree(linkedKvAndRbTree)){
        //长度小于6的时候转换为链表
        if(linkedKvAndRbTree->rbTree->size <=6){
            rbtree_to_linked(linkedKvAndRbTree);
            delCharKvLinkedNode(linkedKvAndRbTree->linked,key);
        } else{
            removeRbTree(linkedKvAndRbTree->rbTree,key);
        }
    } else{
        return;
    }
    linkedKvAndRbTree->len--;
}

//获取所有的key和value
CharKvLinked * getAllLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree){
    if(linkedKvAndRbTree == NULL){
        return NULL;
    }
    if(isLinked(linkedKvAndRbTree)){
       return copyCharKvLinked(linkedKvAndRbTree->linked);
    }else if(isRbtree(linkedKvAndRbTree)){
        return getAllKeyAndValueRbTree(linkedKvAndRbTree->rbTree);
    }else{
        return NULL;
    }
}
//销毁
void destroyLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree){
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isLinked(linkedKvAndRbTree)){
        destroyCharKvLinked(linkedKvAndRbTree->linked);
    }else if(isRbtree(linkedKvAndRbTree)){
        destroyRbTree(linkedKvAndRbTree->rbTree);
    }
    free(linkedKvAndRbTree);
}



LinkedKvAndRbTreeIterator *createLinkedKvAndRbTreeIterator(LinkedKvAndRbTree *linkedKvAndRbTree) {
    LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator = malloc(sizeof(LinkedKvAndRbTreeIterator));;
    linkedKvAndRbTreeIterator->count = 0;//迭代次数
    linkedKvAndRbTreeIterator->linked = getAllLinkedKvAndRbTree(linkedKvAndRbTree);
    linkedKvAndRbTreeIterator->next = linkedKvAndRbTreeIterator->linked->head;//下次迭代节点
    return linkedKvAndRbTreeIterator;
}
boolean hasNextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator) {
   boolean pd=linkedKvAndRbTreeIterator->count < linkedKvAndRbTreeIterator->linked->len ? TRUE : FALSE;
   if(!pd){
       free(linkedKvAndRbTreeIterator->linked);
       free(linkedKvAndRbTreeIterator);
   }
  return pd;
}

CharKvLinkedNode *nextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator) {
    if(!hasNextLinkedKvAndRbTreeIterator(linkedKvAndRbTreeIterator)){
        return NULL;
    }
    CharKvLinkedNode *pNode = linkedKvAndRbTreeIterator->next;
    linkedKvAndRbTreeIterator->next =pNode->next;//切换到下一个节点
    linkedKvAndRbTreeIterator->count++;
    return pNode;
}

hash

#ifndef STUDY_CHARHASH_H
#define STUDY_CHARHASH_H
#include "charlist.h"

#include "../structure/linkedKvAndRbTree.h"

typedef int boolean;//定义一个布尔类型
#define TRUE 1
#define FALSE 0
// 哈希表结构体
typedef struct hashMap {
    int size;           // 集合元素个数
    int capacity;       // 容量
    int nodeLen;       //节点长度
    LinkedKvAndRbTree **list;         // 存储区域
    int dilatationCount;  //扩容次数
    int dilatationSum;  //扩容总次数

} HashMap;
HashMap *createHashMap(int capacity);
void putHashMap(HashMap *hashMap, char *key, void *value);
void printHashMap(HashMap *hashMap);
void *getHashMap(HashMap *hashMap, char *key);
boolean containsKey(HashMap *hashMap, char *key);
boolean containsValue(HashMap *hashMap, void *value);
void removeHashMap(HashMap *hashMap, char *key);
void updateHashMap(HashMap *hashMap, char *key, void *value);
CharList *geTKEys(HashMap *hashMap);
CharList *getValues(HashMap *hashMap);
HashMap *copyHashMap(HashMap *hashMap);
void mergeHashMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *mergeHashMapNewMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *differenceHashMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *intersectionHashMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *complementHashMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *uNIOnHashMap(HashMap *hashMap1,HashMap *hashMap2);
void hashMapClear(HashMap *hashMap);



// 迭代器结构
typedef struct hashMapiterator {
    LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator;// 迭代器
    CharKvLinkedNode *next;// 下次的值
    int count;//迭代次数
    HashMap *hashMap;
    int index; //位置
}HashMapIterator;
// 创建哈希结构迭代器
HashMapIterator *createHashMapIterator(HashMap *hashMap);
// 迭代器是否有下一个
boolean hasNextHashMapIterator(HashMapIterator *iterator);
// 迭代到下一次
CharKvLinkedNode *nextHashMapIterator(HashMapIterator *iterator);

#endif //STUDY_CHARHASH_H
#include "charHash.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//最好的char类型的hash算法,冲突较少,效率较高
static unsigned int BKDRHash(char *str) {
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;

    while (*str) {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

//hash值长度取模最后获取实际位置的下标
static unsigned int defaultHashCode(HashMap hashMap, char *key) {
    return BKDRHash(key) % hashMap.capacity;
}

// 创建Map集合
HashMap *createHashMap(int capacity) {
    //创建哈希表
    HashMap *hashMap = (HashMap *) malloc(sizeof(HashMap));
    //创建存储区域
    if (capacity < 10) {
        capacity = 10;
    }
    hashMap->size = 0;
    hashMap->dilatationCount = 0;
    hashMap->dilatationSum = 0;
    hashMap->nodeLen = 0;
    hashMap->capacity = capacity;
    hashMap->list = (LinkedKvAndRbTree **) calloc(capacity, sizeof(LinkedKvAndRbTree));
    return hashMap;
}

//扩容基数
static int expansionBase(HashMap *hashMap) {
    int len = hashMap->capacity;
    int dilatationCount = hashMap->dilatationCount;
    hashMap->dilatationSum++;
    //基础扩容
    len += (len >= 100000000 ? len * 0.2 :
            len >= 50000000 ? len * 0.3 :
            len >= 10000000 ? len * 0.4 :
            len >= 5000000 ? len * 0.5 :
            len >= 1000000 ? len * 0.6 :
            len >= 500000 ? len * 0.7 :
            len >= 100000 ? len * 0.8 :
            len >= 50000 ? len * 0.9 :
            len * 1.0);
    hashMap->dilatationCount++;
    //频率扩容
    if (dilatationCount >= 3) {
        len += (len >= 100000000 ? len * 1 :
                len >= 50000000 ? len * 2 :
                len >= 10000000 ? len * 3 :
                len >= 5000000 ? len * 4 :
                len >= 1000000 ? len * 5 :
                len >= 500000 ? len * 6 :
                len >= 100000 ? len * 7 :
                len >= 50000 ? len * 8 :
                len >= 10000 ? len * 9 :
                len >= 1000 ? len * 10 :
                len * 20);
        hashMap->dilatationCount = 0;
    }

    return len;
}

//扩容Map集合
static void dilatationHash(HashMap *hashMap) {
    //原来的容量
    int capacity = hashMap->capacity;
    //扩容后的容量
    hashMap->capacity = expansionBase(hashMap);
    //节点长度清空
    hashMap->nodeLen = 0;
    //创建新的存储区域
    LinkedKvAndRbTree **newList = (LinkedKvAndRbTree **) calloc(hashMap->capacity, sizeof(LinkedKvAndRbTree));

    for (int i = 0; i < capacity; ++i) {
        //获取旧的存储区域的每个节点
        LinkedKvAndRbTree *node = hashMap->list[i];
        //如果节点不为空,将旧的节点所有数据放入新的存储区域
        if (node != NULL) {
            //拿到旧节点的所有key和value
            CharKvLinked *pCharKvLinked = getAllLinkedKvAndRbTree(node);
            //遍历每个key和value,将每个key和value放入新的存储区域
            CharKvLinkedIterator *pIterator = createCharKvLinkedIterator(pCharKvLinked);
            while (hasNextCharKvLinkedIterator(pIterator)) {
                CharKvLinkedNode *pNode = nextCharKvLinkedIterator(pIterator);
                //获取新的存储区域的下标
                unsigned int index = defaultHashCode(*hashMap, pNode->key);
                //将旧的节点放入新的存储区域
                LinkedKvAndRbTree *linkedKvAndRbTree = newList[index];
                if (linkedKvAndRbTree == NULL) {
                    //如果新存储区域的节点为空,创建新的节点
                    LinkedKvAndRbTree *newLinkedKvAndRbTree = createLinkedKvAndRbTree();
                    insertOrUpdateLinkedKvAndRbTree(newLinkedKvAndRbTree, pNode->key, pNode->value);
                    newList[index] = newLinkedKvAndRbTree;
                    hashMap->nodeLen++; //节点长度加1
                } else {
                    //如果新存储区域的节点不为空,将旧的节点放入新的存储区域
                    insertOrUpdateLinkedKvAndRbTree(linkedKvAndRbTree, pNode->key, pNode->value);
                }

            }
        }
    }

    //释放旧的存储区域
    free(hashMap->list);
    //将新的存储区域赋值给旧的存储区域
    hashMap->list = newList;
}

//给Map集合添加元素
void putHashMap(HashMap *hashMap, char *key, void *value) {
    //判断是否需要扩容
    if (hashMap->nodeLen == hashMap->capacity) {
        dilatationHash(hashMap);
    }
    //获取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //获取节点
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果节点是空的那么直接添加
    if (linkedKvAndRbTree == NULL) {
        //如果新存储区域的节点为空,创建新的节点
        LinkedKvAndRbTree *newLinkedKvAndRbTree = createLinkedKvAndRbTree();
        insertOrUpdateLinkedKvAndRbTree(newLinkedKvAndRbTree, key, value);
        hashMap->list[hashCode] = newLinkedKvAndRbTree;
        hashMap->size++;
        hashMap->nodeLen++;
        return;
    }
    //如果节点不为空,那么就插入或者修改
    insertOrUpdateLinkedKvAndRbTree(linkedKvAndRbTree, key, value);
    hashMap->size++;
}

//打印Map集合
void printHashMap(HashMap *hashMap) {
    for (int i = 0; i < hashMap->capacity; i++) {
        LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[i];
        if (linkedKvAndRbTree != NULL) {
            CharKvLinked *pLinked = getAllLinkedKvAndRbTree(linkedKvAndRbTree);
            printCharKvLinked(pLinked);
        }
    }
}


//获取Map集合中的元素
void *getHashMap(HashMap *hashMap, char *key) {
    //获取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //获取节点
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果节点是空的那么直接返回
    if (linkedKvAndRbTree == NULL) {
        return NULL;
    }
    //获取节点中的值
    return searchLinkedKvAndRbTree(linkedKvAndRbTree, key);
}

//判断键是否存在
boolean containsKey(HashMap *hashMap, char *key) {
    //获取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //获取节点
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果节点是空的那么直接返回FALSE
    if (linkedKvAndRbTree == NULL) {
        return FALSE;
    }
    return isExistLinkedKvAndRbTree(linkedKvAndRbTree, key);
}

//删除Map集合中的元素
void removeHashMap(HashMap *hashMap, char *key) {
    //获取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //获取节点
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果节点是空的那么直接返回
    if (linkedKvAndRbTree == NULL) {
        return;
    }
    //判断是否存在该键,并且一样的话,删除该节点
    if (isExistLinkedKvAndRbTree(linkedKvAndRbTree, key)) {
        deleteLinkedKvAndRbTree(linkedKvAndRbTree, key);
        hashMap->size--;
        return;
    }
}


//修改Map集合中的元素
void updateHashMap(HashMap *hashMap, char *key, void *value) {
    //获取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //获取节点
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果节点是空的那么直接返回
    if (linkedKvAndRbTree == NULL) {
        return;
    }
    //判断是否存在该键,然后进行修改
    if (isExistLinkedKvAndRbTree(linkedKvAndRbTree, key)) {
        insertOrUpdateLinkedKvAndRbTree(linkedKvAndRbTree, key, value);
    }
}

HashMapIterator *createHashMapIterator(HashMap *hashMap) {
    HashMapIterator *pVoid = malloc(sizeof(HashMapIterator));
    pVoid->hashMap = hashMap;
    pVoid->index = 0;
    pVoid->count = 0;
    LinkedKvAndRbTree *pTree = hashMap->list[pVoid->index];
    //找到不是空的节点
    while (pTree == NULL) {
        pTree = hashMap->list[++pVoid->index];
    }
    //创建迭代器
    pVoid->linkedKvAndRbTreeIterator = createLinkedKvAndRbTreeIterator(pTree);
    //获取迭代器中的第一个节点
    pVoid->next = nextLinkedKvAndRbTreeIterator(pVoid->linkedKvAndRbTreeIterator);;
    ++pVoid->index;
    return pVoid;
}

boolean hasNextHashMapIterator(HashMapIterator *iterator) {
    boolean pd = iterator->count < iterator->hashMap->size ? TRUE : FALSE;
    if (!pd) {
        free(iterator);
    }
    return pd;
}

CharKvLinkedNode *nextHashMapIterator(HashMapIterator *iterator) {
    if (!hasNextHashMapIterator(iterator)) {
        return NULL;
    }
    CharKvLinkedNode *entry = iterator->next;
    //获取下一个节点
    CharKvLinkedNode *nextNode = nextLinkedKvAndRbTreeIterator(iterator->linkedKvAndRbTreeIterator);
    if (nextNode != NULL) {
        iterator->next = nextNode;
    } else {
        //如果是最后一个节点了,那么就不在找下个节点了
        if (iterator->count + 1 < iterator->hashMap->size) {
            //获取下一个节点
            LinkedKvAndRbTree *pTree = iterator->hashMap->list[iterator->index];
            while (pTree == NULL) {
                pTree = iterator->hashMap->list[++iterator->index];
            }
            iterator->linkedKvAndRbTreeIterator = createLinkedKvAndRbTreeIterator(pTree);
            iterator->next = nextLinkedKvAndRbTreeIterator(iterator->linkedKvAndRbTreeIterator);;
            ++iterator->index;
        }
    }
    iterator->count++;
    return entry;
}


//获取所有的key ,返回一个自定义的List集合
CharList *getKeys(HashMap *hashMap) {
    CharList *pCharlist = createCharList(hashMap->size);
    HashMapIterator *pIterator = createHashMapIterator(hashMap);
    while (hasNextHashMapIterator(pIterator)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator);
        addCharList(&pCharlist, entry->key);
    }
    return pCharlist;
}

//获取所有的value,返回一个自定义的List集合
CharList *getValues(HashMap *hashMap) {
    CharList *pCharlist = createCharList(hashMap->size);
    HashMapIterator *pIterator = createHashMapIterator(hashMap);
    while (hasNextHashMapIterator(pIterator)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator);
        addCharList(&pCharlist, entry->value);
    }
    return pCharlist;
}

//复制一个HashMap
HashMap *copyHashMap(HashMap *hashMap) {
    HashMap *pHashMap = createHashMap(hashMap->capacity);
    HashMapIterator *pIterator = createHashMapIterator(hashMap);
    while (hasNextHashMapIterator(pIterator)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    return pHashMap;
}

//将一个map集合,合并到另一个map集合里   hashMap2合并到hashMap1
void mergeHashMap(HashMap *hashMap1, HashMap *hashMap2) {
    HashMapIterator *pIterator = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator);
        putHashMap(hashMap1, entry->key, entry->value);
    }
}

//合并两个Map集合,返回一个新的Map集合
HashMap *mergeHashMapNewMap(HashMap *hashMap1, HashMap *hashMap2) {
    HashMap *pHashMap = createHashMap(hashMap1->capacity + hashMap2->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator1);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator2);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    return pHashMap;
}

//差集,返回一个新的Map集合,返回hashMap2的差集
HashMap *differenceHashMap(HashMap *hashMap1, HashMap *hashMap2) {
    HashMap *pHashMap = createHashMap(hashMap1->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator1);
        if (!containsKey(hashMap2, entry->key)) {
            putHashMap(pHashMap, entry->key, entry->value);
        }
    }
    return pHashMap;
}

//交集,返回一个新的Map集合
HashMap *intersectionHashMap(HashMap *hashMap1, HashMap *hashMap2) {
    HashMap *pHashMap = createHashMap(hashMap1->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator1);
        if (containsKey(hashMap2, entry->key)) {
            putHashMap(pHashMap, entry->key, entry->value);
        }
    }
    return pHashMap;
}

//补集,返回一个新的Map集合
HashMap *complementHashMap(HashMap *hashMap1, HashMap *hashMap2) {
    HashMap *pHashMap = createHashMap(hashMap1->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator1);
        if (!containsKey(hashMap2, entry->key)) {
            putHashMap(pHashMap, entry->key, entry->value);
        }
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator2);
        if (!containsKey(hashMap1, entry->key)) {
            putHashMap(pHashMap, entry->key, entry->value);
        }
    }
    return pHashMap;
}

//并集,返回一个新的Map集合 (如果有相同的key,则取hashMap2的值)
HashMap *unionHashMap(HashMap *hashMap1, HashMap *hashMap2) {
    HashMap *pHashMap = createHashMap(hashMap1->capacity + hashMap2->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator1);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator2);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    return pHashMap;
}

void hashMapClear(HashMap *hashMap) {
    for (int i = 0; i < hashMap->nodeLen; i++) {
        // 释放冲突值内存
        LinkedKvAndRbTree *pTree = hashMap->list[i];
        if (pTree != NULL) {
            destroyLinkedKvAndRbTree(pTree);
        }
    }
    // 释放存储空间
    free(hashMap->list);
    free(hashMap);
}

使用

int main() {

    HashMap *pMap = createHashMap(10);
    for (int i = 0; i < 100; i++) {  //插入从0~1亿数据大约60~90秒
        char *str = (char *) malloc(sizeof(char) * 10);
        sprintf(str, "%d", i);
        putHashMap(pMap, str, str);
    }

//打印
    printHashMap(pMap);

    //迭代器
//    HashMapIterator *pIterator = createHashMapIterator(pMap);
//    while (hasNextHashMapIterator(pIterator)) {
//        CharKvLinkedNode *entry = nextHashMapIterator(pIterator);
//        printf("%s %s\n", entry->key, entry->value);
//    }

//    void *pVoid = getHashMap(pMap, "999999");   // O(1) 查询速度  
//    printf("=====%s\n",pVoid);

//    CharList *pCharlist = getValues(pMap);
//    printCharList(pCharlist);

    hashMapClear(pMap);


}

以上就是C语言实现手写Map(数组+链表+红黑树)的示例代码的详细内容，更多关于C语言 Map的资料请关注编程网其它相关文章！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言实现手写Map(数组+链表+红黑树)的示例代码

本文链接: https://www.lsjlt.com/news/166682.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • C语言实现手写Map(数组+链表+红黑树)的示例代码
    目录要求结构红黑树和链表转换策略hash使用要求 需要准备数组集合(List) 数据结构 需要准备单向链表(Linked) 数据结构 需要准备红黑树(Rbtree)数据结构 需要准备...
    99+
    2022-11-13
  • C语言实现手写红黑树的示例代码
    目录前沿红黑树代码测试前沿 写C的红黑树前建议先看我博客这篇文章Java-红黑树 主要看原理 红黑树代码 #ifndef STUDY_RBTREE_H #define ...
    99+
    2022-11-13
  • C语言实现手写Map(全功能)的示例代码
    目录为啥需要Map结构主流Map结构数组+链表的Map结构hash函数创建Map集合扩容基数扩容Map集合给Map集合添加元素打印Map集合获取Map集合中的指定元素判断键是否存在判...
    99+
    2022-11-13
  • C语言实现动态链表的示例代码
    目录结构体定义已经函数声明函数实现创建一个链表判断链表是否为空获得链表中节点的个数在某个特定的位置插入一个元素获得指定下标的节点的元素删除一个节点链表逆序链表的清空链表的销毁链表的遍...
    99+
    2022-11-13
  • C语言实现无头单向链表的示例代码
    目录一、易错的接口实现 1.1 新节点开辟函数 1.2 尾插 1.3 尾删 二、常见简单接口 2.1 打印链表 2.2 节点计数器 2.3 判断是否为空链表 2.4 通过值查找节点 ...
    99+
    2022-11-12
  • C语言实现链表与文件存取的示例代码
    目录此处为main函数的内容一、输入数据到链表中二、把链表数据存入文件三、输出文件完整代码本程序主要功能是建立链表，然后把链表数据存储到文件中，然后把文件数据存储到数组中并输出。 不...
    99+
    2022-11-13
  • C语言实现线性动态(单向)链表的示例代码
    目录什么是链表为什么不用结构体数组链表的操作创建表删除元素插入元素代码及运行结果什么是链表 链表是数据结构里面的一种，线性链表是链表的一种，线性链表的延伸有双向链表和环形链表。在编程...
    99+
    2022-11-13
  • C语言实现手写字符串处理工具的示例代码
    目录头文件实现文件头文件 #ifndef STUDY_STR_UTIL_H #define STUDY_STR_UTIL_H #include "../structure/cha...
    99+
    2022-11-13
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作