久久婷婷香蕉热狠狠综合,精品无码国产自产拍在线观看蜜,寡妇房东在做爰3,中文字幕日本人妻久久久免费,国产成人精品三上悠亚久久

數(shu)據(ju)結構一(yi)(yi)直(zhi)都是(shi)(shi)軟件工程(cheng)師必備技能(neng)之(zhi)一(yi)(yi)，也(ye)是(shi)(shi)難點之(zhi)一(yi)(yi)。數(shu)據(ju)結構其實(shi)是(shi)(shi)數(shu)據(ju)存(cun)(cun)儲結構，它采用不同的(de)(de)(de)(de)(de)(de)存(cun)(cun)儲方式和(he)邏輯思路，實(shi)現(xian)各(ge)種(zhong)數(shu)據(ju)和(he)數(shu)據(ju)之(zhi)間的(de)(de)(de)(de)(de)(de)關(guan)聯，并且加上對(dui)應的(de)(de)(de)(de)(de)(de)算法，來解決問題。哈(ha)(ha)希表(散(san)(san)列表)是(shi)(shi)數(shu)據(ju)結構中一(yi)(yi)種(zhong)散(san)(san)列存(cun)(cun)儲方式，優點在于關(guan)鍵值(zhi)key可(ke)以通過(guo)指(zhi)定的(de)(de)(de)(de)(de)(de)算法直(zhi)接得到數(shu)據(ju)的(de)(de)(de)(de)(de)(de)存(cun)(cun)儲位置hash(key)，這樣(yang)一(yi)(yi)來不需(xu)要(yao)輪詢，時(shi)間復雜度(du)大大的(de)(de)(de)(de)(de)(de)降(jiang)低。從而，哈(ha)(ha)希表滿足了對(dui)數(shu)據(ju)操作高效率的(de)(de)(de)(de)(de)(de)要(yao)求。但是(shi)(shi)，哈(ha)(ha)希表也(ye)不是(shi)(shi)全能(neng)的(de)(de)(de)(de)(de)(de)，它的(de)(de)(de)(de)(de)(de)使用有一(yi)(yi)定的(de)(de)(de)(de)(de)(de)局限性。下面我(wo)們來介紹一(yi)(yi)下哈(ha)(ha)希表的(de)(de)(de)(de)(de)(de)設(she)計(ji)和(he)實(shi)現(xian)。

哈希表的設計

哈(ha)希表主要是確認(ren)關鍵(jian)值key和(he)關鍵(jian)值存儲位置(zhi)hash(key)之間的(de)(de)(de)具體關聯算法。并且保證(zheng)少的(de)(de)(de)哈(ha)希沖(chong)突(多個不同數據通過算法得到(dao)存儲位置(zhi)相同，這時就是哈(ha)希沖(chong)突)產生(sheng)。常(chang)見的(de)(de)(de)哈(ha)希表的(de)(de)(de)設(she)置(zhi)方法如下：

（1）直(zhi)接定址法：直(zhi)接的構(gou)造(zao)哈希表的方法，存儲位置是通過線(xian)性函(han)數得到的：

hash(key) = a * key + b {a、b為(wei)常數}

特點：這(zhe)樣得(de)到的(de) hash(key) 和 key之(zhi)間一一對應，一般不(bu)會產(chan)生(sheng)沖突;

空間：這的哈希表要求地址(zhi)空間大(da)小與key集合大(da)小相(xiang)同(tong);

應(ying)用：一般用于有序的(de)key集合，例如(ru)各種編(bian)號。

（2）數字分(fen)析法： 分(fen)析已(yi)有(you)數據的(de)特點(dian)，選(xuan)擇盡(jin)量沖突少(shao)的(de)數字來構(gou)造哈希表(biao)。

特點(dian)：數據(ju)是多位組(zu)成，數據(ju)和數據(ju)之間有相(xiang)同的(de)(de)也有不同的(de)(de)，根據(ju)數據(ju)中每(mei)位的(de)(de)分布(bu)特點(dian)，選(xuan)取若干位作為哈希表地址。

空間(jian)：根據選擇的位的個數而(er)定;

應用：數據位(wei)數多，且都相似， 例如生日，日期(qi)等(deng)等(deng)。

（3）除留余數法：n個(ge)數據,選取(qu)一個(ge)接近于n的質數p，這時哈希(xi)地址公式(shi)：

hash(key) = key % p 除法后得到的余(yu)數就是數據(ju)存儲(chu)位置

特點：余數(shu)的取值(zhi)范圍(wei) 0 到 p-1 內，這樣(yang)存儲數(shu)據(ju)空間大小(xiao)是固定(ding)的 p 個;

空間：p個存儲空間;

應用： 數(shu)據值較大(da)，數(shu)據個數(shu)較少。

(4)乘余取整法：先讓關鍵值key乘上一個常數A(0 <1),提取乘積的小數部分。然后再用整數n乘以這個值，對結果向下取整，這個結果就是存儲位置。<>

公式：hash(key) = (int)((((float)key*A) - (int)(key*A))*n)

應用(yong)：數據是小(xiao)數，并(bing)且相差(cha)很少。

(5)平方取中法：一般哈希(xi)地址位置數據2的(de)某次冪，例如：哈希(xi)地址總數為 m = 2^r。哈希(xi)地址hash(key) = 2^key 值中間的(de)r位。

(6)折疊法(fa)：數據信(xin)息很長(chang)，可以將數據從左到有分(fen)成幾個部分(fen)，每部分(fen)位數應與hash(key)存儲位置(zhi)的位數相同，將每部分(fen)都疊加求和，這個和就(jiu)是hash(key)存儲位置(zhi)。

應用：例如：圖書(shu)館中(zhong)圖書(shu)的(de)標準編號。

(7)隨(sui)機(ji)數法：獲取一個隨(sui)機(ji)數，作為存儲位置，公式：hash(key) = random(key);

應用：key關鍵字長度不等(deng)時使(shi)用。

哈希表的實現

這里我們以第三(san)種方(fang)式除留余數法舉例。

例子：已知存(cun)在以下(xia)數據 ： 23 , 26 ， 29 ，30，34 ，40

利用哈希表存儲上面數據，并(bing)寫(xie)出(chu)查找(zhao)方法。

第一步：確認hash(key)和key之間的(de)關聯公式

數據有6個，先(xian)選取一個質數p = 7 或 11或 13

為盡量減少哈希沖突，當選擇(ze)p=7時：余數2 5 1 2 6 5有沖突

當選擇p=11時：余(yu)數1 4 7 8 1 6有沖突

當選擇p=13時：余數10 0 3 4 8 1無沖突

所以(yi)公式(shi)：hash(key) = key % 13;

實現代碼：
#include<stdio.h>
typedef int data_t;
#define M 13
int emptyHash(data_t *p)  // 判斷哈希地址中是否空閑
{
         return *p == 0 ? 1:0;
}
int setHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(emptyHash(&hp[i]))      // 判讀指定位置是否空閑
                   hp[i] = key;                  // 存儲到哈希表中
         else 
return 0;       // 失敗
         return 1;           // 成功
}
int getHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(hp[i] != key)    
         {
                   printf("數據沒有存儲到哈希表中\n");
                   return 0;
         }
         else
                   printf("數據在哈希表中,位置%d --> %d\n",i, hp[i]);
         return 1;
}
int main()
{
         data_t hash[13] = {0};          // 定義一個哈希表（數組）存儲數據空間
         setHash(hash,23);
         setHash(hash,26);
         setHash(hash,29);           // 哈希表中存入數據
         setHash(hash,30);
         setHash(hash,34);
         setHash(hash,40);
         getHash(hash,34);           // 查找哈希表
         getHash(hash,32);                    
         return 0;
}