哈希表和高效數組鍊表的實現

哈希表

• 程序中需要保存數據，而且需要通過給定標號快速找到數據。這個標號叫做鍵，數據叫做值。
• 若採用for循環，當數據太多時會循環好多次，效率太低。因此出現了二分法，使得效率提高。
• 而我們可以通過數組實現，將數組下標和鍵綁定在一起，直接找下標實現。但是這樣會浪費大量存儲空間（有些下標不存儲數據），為了解決空間浪費問題，我們引入了哈希函數（散列函數）
• 散列函數：如將鍵/10取餘數，得到的數為數組下標。但是這又產生了空間衝突問題，為解決此問題我們規定，若此下標空間衝突，則+1後再看下標是否空餘，直到有空位為止。
• 但查看下標是否空餘得一個個看，又會影響效率。因此我們需要合理設計散列函數，以防止空間衝突，如/100取餘數等

哈希表類CBHashLK

哈希表編程嘗試：輸入鍵，快速查找值

• 根據模板創建項目
• 具體代碼實現

#include "resource.h"
#include "BForm.h"

CBForm form1(ID\\_form1);
CBHashLK mHashTest;

void cmdFind\\_Click()
{
    int iKey=form1.Control(ID\\_txtID).TextInt();
    if(mHashTest.IsKeyExist(iKey))
    {
        form1.Control(ID\\_txtResult).TextSet(mHashTest.Item(iKey,false));
        form1.Control(ID\\_txtResult2).TextSet(mHashTest.ItemStr(iKey,false));
    }
    else
    {
        form1.Control(ID\\_txtResult).TextSet(TEXT("該鍵不存在"));
        form1.Control(ID\\_txtResult2).TextSet(TEXT("該鍵不存在"));
    }
}

void form1\\_Load()
{
    const int cMaxItems=1000000;
    mHashTest.AlloMem(cMaxItems\\*2);
    //預先分配空間以提高效率，儘管不預先分配後邊也會自動分配空間，但這樣會提高效率（即使預先分配的空間不夠也沒事
    for (int i=1;i<=cMaxItems;i++)
    {
        mHashTest.Add(i\\*10,i,0,0,TEXT("zhr"));
    }

    mHashTest.Remove(100,false);
    mHashTest.Remove(1000,false);

    MsgBox(TEXT("哈希表建立完畢！請任意輸入1~1000000之間的鍵，來快速查找其值"));
}

int main()
{
    form1.EventAdd(0,eForm\\_Load,form1\\_Load);
    form1.EventAdd(ID\\_cmdFind,eCommandButton\\_Click,cmdFind\\_Click);

    form1.Show();
}

高效數組鍊表

• 儲存數據有兩種方式：數組和鍊表。其中鍊表由一個個節點組成，節點包括數據+下一個數據的地址，最後一個節點的next為0。
• 就查找元素而言，數組可以由下標直接找到，鍊表則需要從頭開始倒騰；但對於插入刪除而言，數組後邊的數據都要移動，鍊表則只需要調整兩個地址。因此兩者都有缺點
• 為此，我們將兩者結合，發明了數組鍊表。數組鍊表由若干小型數組連結而成，由於數組元素個數較少，移動也不會移動太多；而查找時也不必一個個倒騰，以四個元素的數組為例，先/4，再%4,得到第幾個數組的第幾個元素（但要注意都要從0開始數！！）
• 值得一提的是，數組鍊表的動態分配，每次至少要分配一個小數組的空間，不可能只分配一個元素的空間。與計算機的簇類似，一次是4096位元組（或者8192、16384），若是16385位元組就得分配兩個16384位元組。在磁碟格式化時，可以設置簇的大小。過大會浪費空間，過小會影響處理速度（一次讀取一簇）。因此我們存小文件多的盤，設置簇小一點（如1024位元組）；存儲電影時，則可以設置大一點，看的會更加流暢
• 為何是0位元組？？

數組鍊表類CBArrLink

數組鍊表編程嘗試

• 根據模板創造項目
• 引入combo box，注意設置屬性type，以及sort（程序自作聰明設成true）
• 代碼

#include "resource.h"
    #include "BForm.h"
    #include 
    
    CBForm form1(ID\\_form1);
    CBArrLink m\\_al;
    
    struct SArrType
    {
        //定義結構體，僅用於指針法訪問數組鍊表
        int Item;
        int Item2;
    };
    
    void cmdAdd\\_Click()
    {
        long iClockStart=clock();
        int ct=5000000;
    
        for(int i=1;i<=ct;i++){
            m\\_al.Add(i,i\\*10);
        }
    
        form1.Control(ID\\_lblAdd).TextSet(m\\_al.Count());
        form1.Control(ID\\_lblAdd).TextAdd(TEXT("個數據添加完成，"));
        form1.Control(ID\\_lblAdd).TextAdd(TEXT("共用時"));
        form1.Control(ID\\_lblAdd).TextAdd((double)(clock()-iClockStart));
        form1.Control(ID\\_lblAdd).TextAdd(TEXT("毫秒"));
    }
    
    void cmdAccess\\_Click()
    {
        long iClockStart=clock();
        int iMethod=form1.Control(ID\\_cboAccessMethod).ListIndex();
        int ct=m\\_al.Count();
        int i;
        if(1==iMethod)
        {
            for(i=1;i<=ct;i++)
            {
                if(m\\_al.Item2(i)!=m\\_al.Item(i)\\*10)
                {
                    MsgBox(i,TEXT("發現數據錯誤"));
                    break;
                }
            }
        }
        else
        {
            //指針效率更高
            //獲得m\\_al所有數據的首地址p
            struct SArrType \\*p=(struct SArrType\\*)m\\_al.GetItemsArr();
    
            for(i=1;i<=ct;i++)
            {
                if(p\\[i\\].Item2!=p\\[i\\].Item\\*10)
                {
                    MsgBox(i,TEXT("發現數據錯誤"));
                    break;
                }
            }
        }
    
        if(i>ct)
        {
            form1.Control(ID\\_lblAccess).TextSet(TEXT("測試完成"));
            form1.Control(ID\\_lblAccess).TextAdd(ct);
            form1.Control(ID\\_lblAccess).TextAdd(TEXT("個數據，未發現錯誤。用時："));
            form1.Control(ID\\_lblAccess).TextAdd((double)(clock()-iClockStart));
            form1.Control(ID\\_lblAccess).TextAdd(TEXT("毫秒"));
        }
    }
    
    void cmdDel\\_Click()
    {
        int index=form1.Control(ID\\_txtDelIndex).TextInt();
        m\\_al.Remove(index);
    
        form1.Control(ID\\_lblDel).TextSet(TEXT("刪除後，剩餘數據個數："));
        form1.Control(ID\\_lblDel).TextAdd(m\\_al.Count());
    }
    
    int main()
    {
        form1.EventAdd(ID\\_cmdAdd,eCommandButton\\_Click,cmdAdd\\_Click);
        form1.EventAdd(ID\\_cmdAccess,eCommandButton\\_Click,cmdAccess\\_Click);
        form1.EventAdd(ID\\_cmdDel,eCommandButton\\_Click,cmdDel\\_Click);
        
        form1.Control(ID\\_cboAccessMethod).AddItem(TEXT("數組法訪問元素"));
        form1.Control(ID\\_cboAccessMethod).AddItem(TEXT("指針法訪問元素"));
        form1.Control(ID\\_cboAccessMethod).ListIndexSet(1);
        form1.Show();
    
        return 0;
    }