1樓：匿名使用者
有些圖打不上去。如果想要完整的資料告訴我郵箱，我發給你 。
雜湊表及其應用
一、定義
二、基本原理
雜湊表的基本原理是：使用乙個下標範圍比較大的陣列a來儲存元素，設計乙個函式h，對於要儲存的線性表的每個元素node，取乙個關鍵字key，算出乙個函式值h(key)，把h(key)作為陣列下標，用a[h(key)]這個陣列單元來儲存node。也可以簡單的理解為，按照關鍵字為每乙個元素「分類」，然後將這個元素儲存在相應「類」所對應的地方（這一過程稱為「直接定址」）。
但是，不能夠保證每個元素的關鍵字與函式值是一一對應的，因此極有可能出現對於不同的元素，卻計算出了相同的函式值，這樣就產生了「衝突」，換句話說，就是把不同的元素分在了相同的「類」之中。例如，假設乙個結點的關鍵碼值為key，把它存入雜湊表的過程是：根據確定的函式h計算出h(key)的值，如果以該值為位址的儲存空間還沒有被佔用，那麼就把結點存入該單元；如果此值所指單元裡已存了別的結點（即發生了衝突），那麼就再用另乙個函式i進行映象算出i(h(key)),再看用這個值作為位址的單元是否已被佔用了，若已被佔用，則再用i映象，……，直到找到乙個空位置將結點存入為止。
當然這只是解決「衝突」的一種簡單方法，如何避免、減少和處理「衝突」是使用雜湊表的乙個難題。
在雜湊表中查詢的過程與建立雜湊表的過程相似，首先計算h(key)的值，以該值為位址到基本區域中去查詢。如果該位址對應的空間未被佔用，則說明查詢失敗，否則用該結點的關鍵碼值與要找的key比較，如果相等則檢索成功，否則要繼續用函式i計算i(h(key))的值，……。如此反覆到某步或者求出的某位址空間未被佔用（查詢失敗）或者比較相等（查詢成功）為止。
三、基本概念和簡單實現
1、兩個集合：u是所有可能出現的關鍵字集合；k是實際儲存的關鍵字集合。
2、函式h將u對映到表t[0..m-1]的下標上，可以表示成 h：u→，通常稱h為「雜湊函式(hash function)」，其作用是壓縮待處理的下標範圍，使待處理的|u|個值減少到m個值，從而降低空間開銷（注：
|u|表示u中關鍵字的個數，下同）。
3、將結點按其關鍵字的雜湊位址儲存到雜湊表（雜湊表）中的過程稱為「雜湊(hashing)」。方法稱為「雜湊法」。
4、h(ki)(ki∈u)是關鍵字為ki的結點的「儲存位址」，亦稱雜湊值、雜湊位址、雜湊位址。
5、用雜湊法儲存的線性表稱為「雜湊表（hash table）」，又稱雜湊表。圖中t即為雜湊表。在雜湊表裡可以對結點進行快速檢索（查詢）。
6、對於關鍵字為key的結點，按照雜湊函式h計算出位址h(key)，若發現此位址已被別的結點佔用，也就是說有兩個不同的關鍵碼值key1和key2對應到同乙個位址，即h(key1)=h(key2)，這個現象叫做「衝突（碰撞）」。碰撞的兩個（或多個）關鍵碼稱為「同義詞」（相對於函式h而言）。如圖1中的關鍵字k2和k5，h(k2)=h(k5)，即發生了「衝突」，所以k2和k5稱為「同義詞」。
假如先存了k2，則對於k5，我們可以儲存在h(k2)+1中，當然h(k2)+1要為空，否則可以逐個往後找乙個空位存放。這是另外一種簡單的解決衝突的方法。
發生了碰撞就要想辦法解決，必須想辦法找到另外乙個新位址，這當然要降低處理效率，因此我們希望儘量減少碰撞的發生。這就需要分析關鍵碼集合的特性，找適當的雜湊函式h使得計算出的位址盡可能「均勻分布」在位址空間中。同時，為了提高關鍵碼到位址轉換的速度，也希望雜湊函式「盡量簡單」。
然而對於各種取值的關鍵碼而言，乙個好的雜湊函式通常只能減少碰撞發生的次數，無法保證絕對不產生碰撞。因此雜湊除去要選擇適當的雜湊函式以外，還要研究發生碰撞時如何解決，即用什麼方法儲存同義詞。
7、負載因子
我們把h(key)的值域所對應到的位址空間稱為「基本區域」，發生碰撞時，同義詞可以存放在基本區域還沒有被佔用的單元裡，也可以放到基本區域以外另開闢的區域中（稱為「溢位區」）。下面引入雜湊的乙個重要引數「負載因子或裝填因子(load factor)」，它定義為：
а= 負載因子的大小對於碰撞的發生頻率影響很大。直觀上容易想象，а越大，雜湊表裝得越滿，則再要載入新的結點時碰上已有結點的可能性越大，衝突的機會也越大。特別當а＞1時碰撞是不可避免的。
一般總是取а＜1，即分配給雜湊表的基本區域大於所有結點所需要的空間。當然分配的基本區域太大了也是浪費。例如，某校學生幹部的登記表，每個學生幹部是乙個結點，用學號做關鍵碼，每個學號用7位數字表示，如果分配給這個雜湊表的基本區域為107個儲存單元，那麼雜湊函式就可以是個恒等變換，學號為7801050的學生結點就存入相對位址為7801050的單元，這樣一次碰撞也不會發生，但學校僅幾百個學生幹部，實際僅需要幾百個單元的空間，如果佔用了107個儲存單元，顯然太浪費了，所以這是不可取的。
負載因子的大小要取得適當，使得既不過多地增加碰撞，有較快的檢索速度，也不浪費儲存空間。
下面結合引例說明一下上面的思想和方法。
【例1】用雜湊儲存線性表：a=（18，75，60，43，54，90，46）。
分析：假定選取的雜湊函式為：h(k)=k mod m，k為元素的關鍵字，m為雜湊表的長度，用餘數作為儲存該元素的雜湊位址。
這裡假定k和m均為正整數，並且m要大於等於線性表的長度n。此例n=7，故假定取m=13，則得到的每個元素的雜湊位址為：
h(18)=18 mod 13=5 h(75)=75 mod 13 =10 h(60)=60 mod 13=8
h(43)=43 mod 13=4 h(54)=54 mod 13=2 h(90)=90 mod 13=12
h(46)=46 mod 13=7
根據雜湊位址按順序把元素儲存到雜湊表h（0：m-1）中，儲存映象為：
0 1 2 3 4 5 6 7 8 9 10 11 12
54 43 18 46 60 75 90
當然這是乙個比較理想的情況。假如再往表中插入第8個元素30，h(30)=30 mod 13=4，我們會發現h[4]已經存了43，此時就發生了衝突。我們可以從h[4]往後按順序找乙個空位置存放30，即可以把它插入到h[6]中。
四、雜湊函式的構造方法
選擇適當的雜湊函式是實現雜湊的重中之重，構造雜湊函式有兩個標準：簡單和均勻。簡單是指雜湊函式的計算要簡單快速；均勻是指對於關鍵字集合中的任一關鍵字，雜湊函式能以等概率將其對映到表空間的任何乙個位置上。
也就是說，雜湊函式能將子集k隨機均勻地分布在表的位址集上，以使衝突最小化。
為簡單起見，假定關鍵碼是定義在自然數集合上，常見的雜湊函式構造方法有：
1、直接定址法
以關鍵字key本身或關鍵字加上某個數值常量c作為雜湊位址的方法。雜湊函式為：h(key)= key+c，若c為0，則雜湊位址就是關鍵字本身。
2、除餘法
選擇乙個適當的正整數m，用m去除關鍵碼，取其餘數作為位址，即：h(key)= key mod m，這個方法應用的最多，其關鍵是m的選取,一般選m為小於某個區域長度n的最大素數（如例1中取m=13），為什麼呢？就是為了盡力避免衝突。
假設取m=1000 ，則雜湊函式分類的標準實際上就變成了按照關鍵字末三位數分類，這樣最多1000類，衝突會很多。一般地說，如果 m 的約數越多，那麼衝突的機率就越大。
簡單的證明：假設m是乙個有較多約數的數，同時在資料中存在q滿足***(m,q)=d >1 ，即有m=a*d,q=b*d,則有以下等式：q mod m= q – m* [q div m] =q – m*[b div a] 。
其中，[b div a]的取值範圍是不會超過[0，b]的正整數。也就是說，[b div a]的值只有b+1種可能，而m是乙個預先確定的數。因此上式的值就只有b+1種可能了。
這樣，雖然mod 運算之後的餘數仍然在[0，m-1]內，但是它的取值僅限於等式可能取到的那些值。也就是說餘數的分布變得不均勻了。容易看出，m的約數越多，發生這種餘數分布不均勻的情況就越頻繁，衝突的機率越高。
而素數的約數是最少的，因此我們選用大素數。記住「素數是我們的得力助手」。
3、數字分析法
常有這樣的情況：關鍵碼的位數比儲存區域的位址的位數多，在這種情況下可以對關鍵碼的各位進行分析，丟掉分布不均勻的位留下分布均勻的位作為位址。
本方法適用於所有關鍵字已知，並對關鍵字中每一位的取值分布情況作出了分析。
【例2】對下列關鍵碼集合（表中左邊一列）進行關鍵碼到位址的轉換，要求用三位位址。
key h(key)
000319426 326
000718309 709
000629443 643
000758615 715
000919697 997
000310329 329
分析：關鍵碼是9位的，位址是3位的，需要經過數字分析丟掉6位。丟掉哪6位呢？
顯然前3位是沒有任何區分度，第5位1太多、第6位基本都是8和9、第7位都是3、4、5，這幾位的區分度都不好，而相對來說，第4、8、9位分布比較均勻，所以留下這3位作為位址（表中右邊一列）。
4、平方取中法
將關鍵碼的值平方，然後取中間的幾位作為雜湊位址。具體取多少位視實際要求而定，取哪幾位常常結合數字分析法。
【例3】將一組關鍵字(0100，0110，1010，1001，0111)平方後得(0010000，0012100，1020100，1002001，0012321)，若取表長為1000，則可取中間的三位數作為雜湊位址集：
(100，121，201，020，123)。
5、摺疊法
如果關鍵碼的位數比位址碼的位數多，而且各位分布較均勻，不適於用數字分析法丟掉某些數字，那麼可以考慮用摺疊法。摺疊法是將關鍵碼從某些地方斷開，分關鍵碼為幾個部分，其中有一部分的長度等於位址碼的長度，然後將其餘部分加到它的上面，如果最高位有進製，則把進製丟掉。
一般是先將關鍵字分割成位數相同的幾段（最後一段的位數可少一些），段的位數取決於雜湊位址的位數，由實際需要而定，然後將它們的對應位疊加和（捨去最高位進製）作為雜湊位址。
【例4】如關鍵碼key=58422241，要求轉換為3位的位址碼。
分析：分如下3段：5 8 4 | 2 2 2 | 4 1，則相加：
5 8 4
2 2 2
4 18 4 7
h(key)=847
6、基數轉換法
將關鍵碼值看成在另乙個基數製上的表示，然後把它轉換成原來基數制的數，再用數字分析法取其中的幾位作為位址。一般取大於原來基數的數作轉換的基數，並且兩個基數要是互質的。如：
key=(236075)10是以10為基數的十進位製數，現在將它看成是以13為基數的十三進製數(236075)13,然後將它轉換成十進位製數。
（236075）13=2*135+3*134+6*133+7*13+5
=(841547)10
再進行數字分析，比如選擇第2,3,4,5位，於是h(236075)=4154
五、雜湊表支援的運算
雜湊表支援的運算主要有：初始化(makenull)、雜湊函式值的運算(h(x))、插入元素(insert)、查詢元素(member)。設插入元素的關鍵字為 x ，a 為雜湊表，則各種運算過程如下：
1、初始化比較容易，例如：
const empty=maxlongint;
p=9997;
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do a[i]:=empty;
end;
2、雜湊函式值的運算，根據函式的不同而變化，例如除餘法的乙個例子：
function h(x:longint):integer;
begin
h:= x mod p;
end;
3、我們注意到，插入和查詢首先都需要對這個元素定位，因此加入乙個定位的函式 locate：
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (ix)and(a[(orig+i)mod p]<>empty) do inc(i);
locate:=(orig+i) mod p;
end;
4、插入元素：
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x);
if a[posi]=empty then a[posi]:=x
else error;
end;
5、查詢元素是否已經在表中：
procedure member(x:longint):boolean;
var pos:integer;
begin
pos:=locate(x);
if a[pos]=x then member:=true
else member:=false;
end;
資料結構c語言描述，資料結構（C語言描述）
include include include define datatype int define maxsize 1000 typedef struct nodebitreenode datatype bt maxsize bitreenode buildbtree datatype bt,in...
資料結構作用是什麼，資料結構的用途
假如將程式的目的很簡單的比作是將一個物品從一個地方運到另外一些地方，物品就是資料，怎麼裝物品，比如用火車，汽車什麼的，這個就是資料結構，至於怎麼運過去，走哪條線路怎麼走，這個就是演算法了。不知道這樣子的解釋你能不能明白。所謂結構就是組織形式，資料的結構就是資料怎麼組織，即怎麼描述，怎麼在電腦中儲存。...
學習資料結構需要什麼基礎,學習資料結構需要什麼基礎嗎
首先要有c或c 語言的基礎，還得會點離散數學 圖論 簡單說必須會一門語言的基礎語法，否則你學了也無法自己實踐一邊看看對不對，推薦java，c 學習資料結構需要什麼基礎嗎 1.熟悉你所看的資料結構書本所使用的語言。2.離散數學 不是必須，會的話更好 一門程式語言，一般推薦c語言 知道你為什麼一開始看，...