編程學(xué)習(xí)筆記10--哈希表
[導(dǎo)讀]導(dǎo)引問題
Problem Description
給你n個(gè)整數(shù)，請(qǐng)按從大到小的順序輸出其中前m大的數(shù)。
Input
每組測(cè)試數(shù)據(jù)有兩行，第一行有兩個(gè)數(shù)n,m (0
導(dǎo)引問題
Problem Description
給你n個(gè)整數(shù)，請(qǐng)按從大到小的順序輸出其中前m大的數(shù)。
Input
每組測(cè)試數(shù)據(jù)有兩行，第一行有兩個(gè)數(shù)n,m (0
思考： 常規(guī)算法的缺陷？ 常規(guī)算法需要先對(duì)輸入的值進(jìn)行存儲(chǔ)，然后進(jìn)行排序，最后再進(jìn)行輸出前m個(gè)數(shù)，n的數(shù)值很大是，對(duì)整體排序的時(shí)間會(huì)很長。
是否可以將“數(shù)據(jù)值”和“存儲(chǔ)位置”做某種對(duì)應(yīng)？ 因?yàn)閿?shù)據(jù)的范圍有限制的，數(shù)據(jù)量的多少也是有限制的，所以必然可以想辦法讓大的數(shù)據(jù)對(duì)應(yīng)大的存儲(chǔ)位置，小的數(shù)據(jù)對(duì)應(yīng)小的存儲(chǔ)位置。--優(yōu)點(diǎn)，存儲(chǔ)完畢，排序完畢，省去了排序的時(shí)間，缺點(diǎn)，對(duì)應(yīng)關(guān)系找的不好的話，對(duì)空間的要求估計(jì)會(huì)比原來大很多。
哈希表 基本原理 哈希表（散列表）的基本原理： 使用一個(gè)下標(biāo)范圍比較大的數(shù)組來存儲(chǔ)元素，一般通過設(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)，即散列函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)）相對(duì)應(yīng)，然后用該數(shù)組單元來存儲(chǔ)對(duì)應(yīng)元素。
函數(shù)構(gòu)造 最常見的方法：除余法?H(k ) = k mod p (p一般選取適當(dāng)大的素?cái)?shù))
沖突 由于不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因此很有可能出現(xiàn)如下情況：“對(duì)于不同的元素關(guān)鍵字，Hash函數(shù)計(jì)算出了相同的函數(shù)值”，這就是產(chǎn)生了所謂的“沖突”。換句話說，就是Hash函數(shù)把不同的元素分在了相同的下標(biāo)單元。 沖突解決 常用方法：線性探測(cè)再散列技術(shù) 即：當(dāng) h(k)位置已經(jīng)存儲(chǔ)有元素的時(shí)候，依次探查 (h(k)+i) mod S, i=1,2,3…，直到找到空的存儲(chǔ)單元為止。其中， S為數(shù)組長度。 特別地，如果將數(shù)組掃描一圈仍未發(fā)現(xiàn)空單元，則說明哈希表已滿，這會(huì)帶來麻煩，但是，該情況完全可以通過擴(kuò)大數(shù)組范圍來避免。 基本操作 Hash表初始化（0或-1或其它） 哈希函數(shù)運(yùn)算 插入元素（包含沖突解決） 定位（需考慮可能沖突的情況） 優(yōu)缺點(diǎn)總結(jié) Hash函數(shù)評(píng)價(jià)標(biāo)準(zhǔn)： 低沖突率 易于編碼 Hash函數(shù)特點(diǎn)： 優(yōu)點(diǎn)：數(shù)據(jù)存儲(chǔ)和查找效率高 （幾乎是常數(shù)時(shí)間） 缺點(diǎn)：消耗較多內(nèi)存（內(nèi)存很便宜哪～） Hash主要應(yīng)用： 查找元素是否屬于集合 搜索中的狀態(tài)表示
Hash的應(yīng)用 n給定一個(gè)包含N(N<=3000)個(gè)正整數(shù)的序列，每個(gè)數(shù)不超過5000，對(duì)它們兩兩相加得到的N*(N-1)/2個(gè)和，求出其中前M大的數(shù)(M<=1000)并按從大到小的順序排列。 n?Input n輸入可能包含多組數(shù)據(jù)，其中每組數(shù)據(jù)包括兩行： n第一行兩個(gè)數(shù)N和M， n第二行N個(gè)數(shù)，表示該序列。 n? nOutput n對(duì)于輸入的每組數(shù)據(jù)，輸出M個(gè)數(shù)，表示結(jié)果。輸出應(yīng)當(dāng)按照從大到小的順序排列。
思考： 常規(guī)算法的缺陷？ 常規(guī)算法需要先對(duì)輸入的值進(jìn)行存儲(chǔ)，然后進(jìn)行排序，最后再進(jìn)行輸出前m個(gè)數(shù)，n的數(shù)值很大是，對(duì)整體排序的時(shí)間會(huì)很長。
是否可以將“數(shù)據(jù)值”和“存儲(chǔ)位置”做某種對(duì)應(yīng)？ 因?yàn)閿?shù)據(jù)的范圍有限制的，數(shù)據(jù)量的多少也是有限制的，所以必然可以想辦法讓大的數(shù)據(jù)對(duì)應(yīng)大的存儲(chǔ)位置，小的數(shù)據(jù)對(duì)應(yīng)小的存儲(chǔ)位置。--優(yōu)點(diǎn)，存儲(chǔ)完畢，排序完畢，省去了排序的時(shí)間，缺點(diǎn)，對(duì)應(yīng)關(guān)系找的不好的話，對(duì)空間的要求估計(jì)會(huì)比原來大很多。
哈希表 基本原理 哈希表（散列表）的基本原理： 使用一個(gè)下標(biāo)范圍比較大的數(shù)組來存儲(chǔ)元素，一般通過設(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)，即散列函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)）相對(duì)應(yīng)，然后用該數(shù)組單元來存儲(chǔ)對(duì)應(yīng)元素。
函數(shù)構(gòu)造 最常見的方法：除余法?H(k ) = k mod p (p一般選取適當(dāng)大的素?cái)?shù))
沖突 由于不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因此很有可能出現(xiàn)如下情況：“對(duì)于不同的元素關(guān)鍵字，Hash函數(shù)計(jì)算出了相同的函數(shù)值”，這就是產(chǎn)生了所謂的“沖突”。換句話說，就是Hash函數(shù)把不同的元素分在了相同的下標(biāo)單元。 沖突解決 常用方法：線性探測(cè)再散列技術(shù) 即：當(dāng) h(k)位置已經(jīng)存儲(chǔ)有元素的時(shí)候，依次探查 (h(k)+i) mod S, i=1,2,3…，直到找到空的存儲(chǔ)單元為止。其中， S為數(shù)組長度。 特別地，如果將數(shù)組掃描一圈仍未發(fā)現(xiàn)空單元，則說明哈希表已滿，這會(huì)帶來麻煩，但是，該情況完全可以通過擴(kuò)大數(shù)組范圍來避免。 基本操作 Hash表初始化（0或-1或其它） 哈希函數(shù)運(yùn)算 插入元素（包含沖突解決） 定位（需考慮可能沖突的情況） 優(yōu)缺點(diǎn)總結(jié) Hash函數(shù)評(píng)價(jià)標(biāo)準(zhǔn)： 低沖突率 易于編碼 Hash函數(shù)特點(diǎn)： 優(yōu)點(diǎn)：數(shù)據(jù)存儲(chǔ)和查找效率高 （幾乎是常數(shù)時(shí)間） 缺點(diǎn)：消耗較多內(nèi)存（內(nèi)存很便宜哪～） Hash主要應(yīng)用： 查找元素是否屬于集合 搜索中的狀態(tài)表示
Hash的應(yīng)用 n給定一個(gè)包含N(N<=3000)個(gè)正整數(shù)的序列，每個(gè)數(shù)不超過5000，對(duì)它們兩兩相加得到的N*(N-1)/2個(gè)和，求出其中前M大的數(shù)(M<=1000)并按從大到小的順序排列。 n?Input n輸入可能包含多組數(shù)據(jù)，其中每組數(shù)據(jù)包括兩行： n第一行兩個(gè)數(shù)N和M， n第二行N個(gè)數(shù)，表示該序列。 n? nOutput n對(duì)于輸入的每組數(shù)據(jù)，輸出M個(gè)數(shù)，表示結(jié)果。輸出應(yīng)當(dāng)按照從大到小的順序排列。
#include
#define MAX1 3000*2999/2+10//N最大取3000，最多有3000*2999/2個(gè)數(shù),擴(kuò)大了5倍
#define MAX2 3000
int mask[MAX1]={0};
/**因?yàn)樘幚聿缓霉_突，經(jīng)常出現(xiàn)小的數(shù)被存儲(chǔ)在大的數(shù)據(jù)后面，和原來的大的存在高地址，小數(shù)
存儲(chǔ)在低地址相違背了。因?yàn)樵瓉淼囊?guī)則是存在k%MAX1的位置，如果位置有的話，就繼續(xù)向后找，但是很可能出現(xiàn)后面
已經(jīng)存儲(chǔ)了比較大的數(shù)，所以處理不好，即使把k和k+1的間隔擴(kuò)大幾倍也很可能出現(xiàn)。就是k存儲(chǔ)在k*10%MAX位置，
也有可能出錯(cuò)，所以設(shè)置了掩碼位，計(jì)算相同的數(shù)個(gè)數(shù)*/
int h1[MAX1]={0};
int h2[MAX2]={0};//存儲(chǔ)用的
int main()
{
int M,N,count=0;
int i,j,k,t,s=0;
while(scanf("%d %d",&N,&M)!=EOF)
{
memset(h1,0,MAX1);
memset(h2,0,MAX2);
memset(mask,0,MAX1);
for(i=0;i=0;t--)
{
while(mask[t])
{
mask[t]--;
printf("%d ",h1[t]);
count++;
}
if(count==M)
{
printf("n");
break;
}
}
}
return 0;
} 
下載文檔
