C语言-手写有序Map(数组+链表+红黑树+有序遍历)(全功能)

矫情吗；* 2023-10-02 20:53 1阅读 0赞

### 原理图 ###

![在这里插入图片描述][3a1c8809f6804a618f18ed653e2e70cc.png]

通过维护一条链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。根据经验而言单向链表足以无须双向链表,绝大部分场景根本不需要反向查询,所以我们只需要能保证,按照插入的顺序进行迭代即可

### 要求 ###

自己需要准备一套HashMap的数据结构(数组+链表+红黑树) ,没有的可以自己在我博客里学习 ,当然(数组+链表的HashMap也可以)

### 代码 ###

#ifndef STUDY_CHARLINKEDHASHMAP_H
    #define STUDY_CHARLINKEDHASHMAP_H
    #include "charkvlinked.h"
    #include "charhashmap.h"
    typedef  struct charLinkedHashMap{
        
        CharHashMap *charHashMap;
        struct CharKvLinked *charKvLinked; //单向链表,来维护hash插入的顺序,主要是为了能按照顺序迭代元素
    } CharLinkedHashMap;
    
    CharLinkedHashMap *createCharLinkedHashMap(int size);
    void putCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key, void *value);
    void *getCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key);
    void removeCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key);
    void updateCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key, void *value);
    int sizeCharLinkedHashMap(CharLinkedHashMap *charLinkedHash);
    boolean containsKeyCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key);
    
    
    // 迭代器结构
    typedef struct charLinkedHashIterator {
        
        CharKvLinkedIterator *charKvLinkedIterator;    // 链表的迭代器
    } CharLinkedHashIterator;
    // 创建哈希结构迭代器
    CharLinkedHashIterator *createCharLinkedHashMapIterator(CharLinkedHashMap *charLinkedHash);
    // 迭代器是否有下一个
    boolean hasNextCharLinkedHashMapIterator(CharLinkedHashIterator *iterator) ;
    // 迭代到下一次
    CharKvLinkedNode *nextCharLinkedHashMapIterator(CharLinkedHashIterator *iterator);
    
    CharLinkedHashMap *copyCharLinkedHashMap(CharLinkedHashMap *charLinkedHash);
    
    void mergeCharLinkedHashMap(CharLinkedHashMap *charLinkedHash1, CharLinkedHashMap *charLinkedHash2);
    
    CharLinkedHashMap *mergeCharLinkedHashMapNewMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap12);
    
    CharLinkedHashMap *differenceCharLinkedHashMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap2);
    
    CharLinkedHashMap *intersectionCharLinkedHashMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap2);
    
    CharLinkedHashMap *complementCharLinkedHashMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap2);
    
    CharLinkedHashMap *unionCharLinkedHashMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap2);
    
    void clearCharLinkedHashMap(CharLinkedHashMap *linkedHashMap);
    
    
    #endif //STUDY_CHARLINKEDHASHMAP_H

#include "charlinkedhashmap.h"
    #include <stdlib.h>
    
    //创建一个map
    CharLinkedHashMap *createCharLinkedHashMap(int size) {
        
        CharLinkedHashMap *charLinkedHash = (CharLinkedHashMap *) malloc(sizeof(CharLinkedHashMap));
        charLinkedHash->charHashMap = createCharHashMap(size);
        charLinkedHash->charKvLinked = createCharKvLinked();
        return charLinkedHash;
    }
    //添加一个元素
    void putCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key, void *value) {
        
        putCharHashMap(charLinkedHash->charHashMap, key, value);
        insertCharKvLinkedEndNode(charLinkedHash->charKvLinked, createCharKvLinkedNode(key, value));
    }
    
    //获取一个元素
    void *getCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key) {
        
        return getCharHashMap(charLinkedHash->charHashMap, key);
    }
    //删除一个元素
    void removeCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key) {
        
        removeCharHashMap(charLinkedHash->charHashMap, key);
        delCharKvLinkedNode(charLinkedHash->charKvLinked, key);
    }
    //更新一个元素
    void updateCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key, void *value) {
        
        updateCharHashMap(charLinkedHash->charHashMap, key, value);
        updateCharKvLinkedNode(charLinkedHash->charKvLinked, key, value);
    }
    
    //获取map的大小
    int sizeCharLinkedHashMap(CharLinkedHashMap *charLinkedHash) {
        
        return sizeCharHashMap(charLinkedHash->charHashMap);
    }
    //判断是否包含key
    boolean containsKeyCharLinkedHashMap(CharLinkedHashMap *charLinkedHash, char *key) {
        
        return containsKeyCharHashMap(charLinkedHash->charHashMap, key);
    }
    
    
    //创建一个迭代器
    CharLinkedHashIterator *createCharLinkedHashMapIterator(CharLinkedHashMap *charLinkedHash) {
        
        CharLinkedHashIterator *charLinkedHashIterator = (CharLinkedHashIterator *) malloc(sizeof(CharLinkedHashIterator));
        CharKvLinkedIterator *pIterator = createCharKvLinkedIterator(charLinkedHash->charKvLinked);
        charLinkedHashIterator->charKvLinkedIterator = pIterator;
        return charLinkedHashIterator;
    }
    //迭代器是否有下一个
    boolean hasNextCharLinkedHashMapIterator(CharLinkedHashIterator *iterator) {
        
        return hasNextCharKvLinkedIterator(iterator->charKvLinkedIterator);
    }
    //迭代到下一次
    CharKvLinkedNode *nextCharLinkedHashMapIterator(CharLinkedHashIterator *iterator) {
        
        return nextCharKvLinkedIterator(iterator->charKvLinkedIterator);
    }
    
    //复制一个map
    CharLinkedHashMap *copyCharLinkedHashMap(CharLinkedHashMap *charLinkedHash) {
        
        CharLinkedHashMap *copyCharLinkedHash = createCharLinkedHashMap(charLinkedHash->charHashMap->size);
        CharKvLinkedNode *pNode = charLinkedHash->charKvLinked->head;
        while (pNode != NULL) {
        
            putCharLinkedHashMap(copyCharLinkedHash, pNode->key, pNode->value);
            pNode = pNode->next;
        }
        return copyCharLinkedHash;
    }
    //将一个map集合,合并到另一个map集合里  charLinkedHash2合并到charLinkedHash1
    void mergeCharLinkedHashMap(CharLinkedHashMap *charLinkedHash1, CharLinkedHashMap *charLinkedHash2) {
        
        CharKvLinkedNode *pNode = charLinkedHash2->charKvLinked->head;
        while (pNode != NULL) {
        
            putCharLinkedHashMap(charLinkedHash1, pNode->key, pNode->value);
            pNode = pNode->next;
        }
    }
    //合并两个Map集合,返回一个新的Map集合
    CharLinkedHashMap *mergeCharLinkedHashMapNewMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap12) {
        
        CharLinkedHashMap *pHashMap = createCharLinkedHashMap(sizeCharLinkedHashMap(linkedHashMap1) + sizeCharLinkedHashMap(linkedHashMap12) );
        CharLinkedHashIterator *pIterator1 = createCharLinkedHashMapIterator(linkedHashMap1);
        while (hasNextCharLinkedHashMapIterator(pIterator1)) {
        
            CharKvLinkedNode *entry = nextCharLinkedHashMapIterator(pIterator1);
            putCharLinkedHashMap(pHashMap, entry->key, entry->value);
        }
        CharLinkedHashIterator *pIterator2 = createCharLinkedHashMapIterator(linkedHashMap12);
        while (hasNextCharLinkedHashMapIterator(pIterator2)) {
        
            CharKvLinkedNode *entry = nextCharLinkedHashMapIterator(pIterator2);
            putCharLinkedHashMap(pHashMap, entry->key, entry->value);
        }
        return pHashMap;
    }
    //差集,返回一个新的Map集合,返回hashMap2的差集
    CharLinkedHashMap *differenceCharLinkedHashMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap2) {
        
        CharLinkedHashMap *pHashMap = createCharLinkedHashMap(sizeCharLinkedHashMap(linkedHashMap1) );
        CharLinkedHashIterator *pIterator1 = createCharLinkedHashMapIterator(linkedHashMap1);
        while (hasNextCharLinkedHashMapIterator(pIterator1)) {
        
            CharKvLinkedNode *entry = nextCharLinkedHashMapIterator(pIterator1);
            if (!containsKeyCharLinkedHashMap(linkedHashMap2, entry->key)) {
        
                putCharLinkedHashMap(pHashMap, entry->key, entry->value);
            }
        }
        return pHashMap;
    }
    //交集,返回一个新的Map集合
    CharLinkedHashMap *intersectionCharLinkedHashMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap2) {
        
        CharLinkedHashMap *pHashMap = createCharLinkedHashMap(sizeCharLinkedHashMap(linkedHashMap1) );
        CharLinkedHashIterator *pIterator1 = createCharLinkedHashMapIterator(linkedHashMap1);
        while (hasNextCharLinkedHashMapIterator(pIterator1)) {
        
            CharKvLinkedNode *entry = nextCharLinkedHashMapIterator(pIterator1);
            if (containsKeyCharLinkedHashMap(linkedHashMap2, entry->key)) {
        
                putCharLinkedHashMap(pHashMap, entry->key, entry->value);
            }
        }
        return pHashMap;
    }
    
    //补集,返回一个新的Map集合
    CharLinkedHashMap *complementCharLinkedHashMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap2) {
        
        CharLinkedHashMap *pHashMap = createCharLinkedHashMap(sizeCharLinkedHashMap(linkedHashMap1) );
        CharLinkedHashIterator *pIterator1 = createCharLinkedHashMapIterator(linkedHashMap1);
        while (hasNextCharLinkedHashMapIterator(pIterator1)) {
        
            CharKvLinkedNode *entry = nextCharLinkedHashMapIterator(pIterator1);
            if (!containsKeyCharLinkedHashMap(linkedHashMap2, entry->key)) {
        
                putCharLinkedHashMap(pHashMap, entry->key, entry->value);
            }
        }
        CharLinkedHashIterator *pIterator2 = createCharLinkedHashMapIterator(linkedHashMap2);
        while (hasNextCharLinkedHashMapIterator(pIterator2)) {
        
            CharKvLinkedNode *entry = nextCharLinkedHashMapIterator(pIterator2);
            if (!containsKeyCharLinkedHashMap(linkedHashMap1, entry->key)) {
        
                putCharLinkedHashMap(pHashMap, entry->key, entry->value);
            }
        }
        return pHashMap;
    }
    
    //并集,返回一个新的Map集合 (如果有相同的key,则取linkedHashMap2的值)
    CharLinkedHashMap *unionCharLinkedHashMap(CharLinkedHashMap *linkedHashMap1, CharLinkedHashMap *linkedHashMap2) {
        
        CharLinkedHashMap *pHashMap = createCharLinkedHashMap(sizeCharLinkedHashMap(linkedHashMap1) + sizeCharLinkedHashMap(linkedHashMap2) );
        CharLinkedHashIterator *pIterator1 = createCharLinkedHashMapIterator(linkedHashMap1);
        while (hasNextCharLinkedHashMapIterator(pIterator1)) {
        
            CharKvLinkedNode *entry = nextCharLinkedHashMapIterator(pIterator1);
            putCharLinkedHashMap(pHashMap, entry->key, entry->value);
        }
        CharLinkedHashIterator *pIterator2 = createCharLinkedHashMapIterator(linkedHashMap2);
        while (hasNextCharLinkedHashMapIterator(pIterator2)) {
        
            CharKvLinkedNode *entry = nextCharLinkedHashMapIterator(pIterator2);
            putCharLinkedHashMap(pHashMap, entry->key, entry->value);
        }
        return pHashMap;
    }
    
    //清除map
    void clearCharLinkedHashMap(CharLinkedHashMap *linkedHashMap) {
        
        charHashMapClear(linkedHashMap->charHashMap);
        destroyCharKvLinked(linkedHashMap->charKvLinked);
        free(linkedHashMap);
    }

![在这里插入图片描述][241d60d901ab468c8532f2a2d4413093.gif]

点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复在本博客学习的技术不得以任何方式直接或者间接的从事违反中华人民共和国法律,内容仅供学习、交流与参考 免责声明：本文部分素材来源于网络，版权归原创者所有，如存在文章/图片/音视频等使用不当的情况，请随时私信联系我、以迅速采取适当措施，避免给双方造成不必要的经济损失。感谢,配合,希望我的努力对你有帮助^\_^

[3a1c8809f6804a618f18ed653e2e70cc.png]: https://img-blog.csdnimg.cn/3a1c8809f6804a618f18ed653e2e70cc.png
[241d60d901ab468c8532f2a2d4413093.gif]: https://img-blog.csdnimg.cn/241d60d901ab468c8532f2a2d4413093.gif