46_哈希表

混合数据结构

平衡二叉排序树

冲突不支持,但是不冲突的信息不一定记得住

如存在姓名和id查找,插入同一姓名的时候不知道插在哪里

可以结点里面挂一个单向链表,挂中间[][1][]

        [][2][1][]

查找给迭代器

删除两个孩子的时候链表也要交换过去,析构的时候可以递归删除链表

相对平衡,avl变种

  1. 红黑树(红黑树),父节点是红色,孩子只能是黑色。每个根节点到叶子节点的高度都是一致

哈希表

  1. 平均时间复杂度(0(1))增加、删除、修改、查询
  2. 学号当数组下标 数组大小固定,后面挂链表,多于的模上数组大小,保证了平均
  3. 表大小要预知的刚好
  4. 表大小为奇数比较好,避免0链表比较好
  5. 数组下标转成ascii加数组大小转成整形
  6. hash(散列算法)
  7. 使用好成O(1),使用不好成0(n)
  8. 插入进去每一项链表的平均长度差不多相等
  9. 根据数据样本给出一个好的计算方法
  10. 数据量不支持太大

作业

1.实现哈希表

 //CHashTable.h
#pragma once
#include "CMystring.h"
#include "CStudent.h"

class CHashTable
{
    /*
    key:名称
    value:学生结构体信息
    */
private:
    class HashNode
    {
    public:
        HashNode(CStudent* stu = nullptr, HashNode  * next = nullptr)
        {
            m_pStu = stu;
            m_pNext = next;
        }
        ~HashNode()
        {
            if (m_pStu != nullptr)
            {
                delete m_pStu;
            }

            HashNode *pNode = m_pNext;
            while (pNode != nullptr)
            {
                delete pNode;
            }
        }
    public:
        CStudent* m_pStu;           //表值
        HashNode *m_pNext;          //解决冲突链地址法
    };
public:
    CHashTable(unsigned int tableSize)
    {
        m_pTable = new HashNode[tableSize];
        m_uTableSize = tableSize;
        m_iSameCount = 0;
    }

    ~CHashTable()
    {
        if (m_pTable != nullptr)
        {
            delete m_pTable;
        }
    }

    //非数字关键字,数字化处理
    unsigned int hashKey(CMyString& str)
    {
        unsigned int uToNumber = 1;
        const char *pStr = str.getBuff();
        for (unsigned i = 0U; i < str.getLength(); i++)
        {
            uToNumber *= (*pStr);
        }

        //printf("%u\r\n", uToNumber);
        return uToNumber % m_uTableSize;
    }

    void insert(CStudent& stu)
    {
        unsigned int uKey = hashKey(stu.m_strName);
        if(m_pTable[uKey].m_pStu == nullptr)
        {
            m_pTable[uKey].m_pStu = &stu;
        }
        else
        {
            HashNode *pNode = new HashNode(&stu);
            if (m_pTable[uKey].m_pNext == nullptr)
            {
                m_pTable[uKey].m_pNext = pNode;
                m_iSameCount++;
            }
            else
            {
                //[1]->[2]  [3]
                //[1]->[3]->[2]
                pNode->m_pNext = m_pTable[uKey].m_pNext;
                m_pTable[uKey].m_pNext = pNode;
                m_iSameCount++;
            }
        }
    }

    void remove(CMyString& str)
    {
        unsigned int uKey = hashKey(str);
        if (m_pTable[uKey].m_pStu != nullptr)
        {
            if (m_pTable[uKey].m_pNext != nullptr)
            {
                HashNode *pNode = m_pTable;
                while (pNode->m_pNext != nullptr)
                {
                    if (str.myStrcmp(pNode->m_pStu->m_strName) == 0)
                    {
                        HashNode *pOld = pNode;
                        pNode = pNode->m_pNext;
                        delete pOld;
                        return;
                    }

                    pNode = pNode;
                }

                return;
            }
            else
            {
                m_pTable[uKey] = nullptr;
            }
        }
    }

    void search(CMyString& str)
    {
        unsigned int uKey = hashKey(str);
        int nSerachCount = 0;

        if (m_pTable[uKey].m_pStu != nullptr)
        {
            if (m_pTable[uKey].m_pNext != nullptr)
            {
                HashNode *pNode = m_pTable;
                while (pNode->m_pNext != nullptr)
                {
                    if (pNode->m_pStu->m_strName.myStrstr(str) == true)
                    {
                        pNode->m_pStu->printfInfo();
                        nSerachCount++;
                    }

                    pNode = pNode;
                }
            }
            else
            {
                m_pTable[uKey].m_pStu->printfInfo();
                nSerachCount++;
            }
        }

        if (nSerachCount == 0)
        {
            printf("没有找到\r\n");
        }
    }

    void test()
    {
        printf("same count = %d\r\n", m_iSameCount);
    }

private:
    HashNode *m_pTable;     //表指针
    unsigned int m_uTableSize;  //表大小
    int m_iSameCount;
};

0 条评论
发表一条评论