首頁 > 軟體

C語言實現手寫Map(陣列+連結串列+紅黑樹)的範例程式碼

2022-09-02 18:01:49

要求

需要準備陣列集合(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 %sn", entry->key, entry->value);
//    }

//    void *pVoid = getHashMap(pMap, "999999");   // O(1) 查詢速度  
//    printf("=====%sn",pVoid);

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

    hashMapClear(pMap);


}

以上就是C語言實現手寫Map(陣列+連結串列+紅黑樹)的範例程式碼的詳細內容，更多關於C語言 Map的資料請關注it145.com其它相關文章！


相關文章

  • 德漢姆中學就讀條件 德漢姆中學就讀條件

    <em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011

    2021-06-01 09:32:01

  • 黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列 黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列

    综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所

    2021-06-01 09:31:42

  • 吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！ 吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！

    除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让

    2021-06-01 09:31:34

  • IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？ IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？

    目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加

    2021-06-01 09:31:24

  • 有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊 有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊

    开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的

    2021-06-01 09:30:48

  • iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？ iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？

    不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它

    2021-06-01 09:30:45

IT145.com E-mail:sddin#qq.com