『壹』 線性表的散列方法是什麼
散列表又叫做哈希表
1. 引言
哈希表（Hash Table）的應用近兩年才在NOI中出現，作為一種高效的數據結構，它正在競賽中發揮著越來越重要的作用。
哈希表最大的優點，就是把數據的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間；而代價僅僅是消耗比較多的內存。然而在當前可利用內存越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比較容易也是它的特點之一。
哈希表又叫做散列表，分為「開散列」 和「閉散列」。考慮到競賽時多數人通常避免使用動態存儲結構，本文中的「哈希表」僅指「閉散列」，關於其他方面讀者可參閱其他書籍。
2. 基礎操作
2.1 基本原理
我們使用一個下標范圍比較大的數組來存儲元素。可以設計一個函數（哈希函數， 也叫做散列函數），使得每個元素的關鍵字都與一個函數值（即數組下標）相對應，於是用這個數組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素「分類」，然後將這個元素存儲在相應「類」所對應的地方。
但是，不能夠保證每個元素的關鍵字與函數值是一一對應的，因此極有可能出現對於不同的元素，卻計算出了相同的函數值，這樣就產生了「沖突」，換句話說，就是把不同的元素分在了相同的「類」之中。後面我們將看到一種解決「沖突」的簡便做法。
總的來說，「直接定址」與「解決沖突」是哈希表的兩大特點。
2.2 函數構造
構造函數的常用方法（下面為了敘述簡潔，設 h(k) 表示關鍵字為 k 的元素所對應的函數值）：
a) 除余法：
選擇一個適當的正整數 p ，令 h(k ) = k mod p
這里， p 如果選取的是比較大的素數，效果比較好。而且此法非常容易實現，因此是最常用的方法。
b) 數字選擇法：
如果關鍵字的位數比較多，超過長整型範圍而無法直接運算，可以選擇其中數字分布比較均勻的若干位，所組成的新的值作為關鍵字或者直接作為函數值。
2.3 沖突處理
線性重新散列技術易於實現且可以較好的達到目的。令數組元素個數為 S ，則當 h(k) 已經存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發現空單元，這就是哈希表已經滿了，發生了錯誤。當然這是可以通過擴大數組范圍避免的）。
2.4 支持運算
哈希表支持的運算主要有：初始化(makenull)、哈希函數值的運算(h(x))、插入元素(insert)、查找元素(member)。
設插入的元素的關鍵字為 x ，A 為存儲的數組。
初始化比較容易，例如
const empty=maxlongint; // 用非常大的整數代表這個位置沒有存儲元素
p=9997; // 表的大小
procere makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函數值的運算根據函數的不同而變化，例如除余法的一個例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我們注意到，插入和查找首先都需要對這個元素定位，即如果這個元素若存在，它應該存儲在什麼位置，因此加入一個定位的函數 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//當這個循環停下來時，要麼找到一個空的存儲單元，要麼找到這個元
//素存儲的單元，要麼表已經滿了
locate:=(orig+i) mod S;
end;
插入元素
procere insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函數的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即為發生了錯誤，當然這是可以避免的
end;
查找元素是否已經在表中
procere member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
這些就是建立在哈希表上的常用基本運算。
下文提到的所有程序都能在附錄中找到。
3. 效率對比
3.1簡單的例子與實驗
下面是一個比較簡單的例子：
===================================================================
集合 ( Subset )
問題描述：
給定兩個集合A、B，集合內的任一元素x滿足1 ≤ x ≤ 109，並且每個集合的元素個數不大於104 個。我們希望求出A、B之間的關系。只需確定在B 中但是不在 A 中的元素的個數即可。
這個題目是根據 OIBH NOIP 2002 模擬賽 # 1 的第一題改編的。
分析：我們先不管A 與 B 的具體關系如何，注意到這個問題的本質就是對於給定的集合A ，確定B 中的元素是否在 A 中。所以，我們使用哈希表來處理。至於哈希函數，只要按照除余法就行了，由於故意擴大了原題的數據規模， H(x) = x mod 15889;
當然本題可以利用別的方法解決，所以選取了速度最快的快速排序+二分查找，讓這兩種方法作效率對比。
我們假定 |A|=|B| ，對於隨機生成的數據，計算程序重復運行50次所用時間。
對比表格如下：
哈希表（sec） 快速排序+二分查找(sec)
復雜度 O(N) (只有忽略了沖突才是這個結果。當然實際情況會比這個大，但是重復的幾率與哈希函數有關，不容易估計) O(N log N+ N) = O(N log N)
測試數據規模 —— ——
500 0.957 0.578
1000 1.101 0.825
2500 1.476 1.565
5000 2.145 2.820
7500 2.905 4.203
10000 3.740 5.579
13500 7.775 7.753
15000 27.550 8.673
對於數據的說明：在 Celeron566 下用 TP 測試，為了使時間的差距明顯，讓程序重復運了行50次。同時哈希表中的P= 15889 ，下標范圍 0..15888 。由於快速排序不穩定，因此使用了隨機數據。
3．2 對試驗結果的分析：
注意到兩個程序的用時並不像我們期望的那樣，總是哈希錶快。設哈希表的大小為 P .
首先，當規模比較小的時候（大約為a< 10% * P，這個數據僅僅是通過若干數據估記出來的，沒有嚴格證明，下同），第二種方法比哈希錶快。這是由於，雖然每次計算哈希函數用O(1) 的時間，但是這個系數比較大。例如這道題的 H(x)=x mod 15589 ，通過與做同樣次數的加法相比較，測試發現系數 > 12 ，因為 mod 運算本身與快速排序的比較大小和交換元素運算相比，比較費時間。所以規模小的時候，O(N)（忽略沖突）的演算法反而不如 O(NlogN)。這一點在更復雜的哈希函數上會體現的更明顯，因為更復雜的函數系數會更大。
其次，當規模稍大 （大約為 15%*P < a < 85%*P） 的時候，很明顯哈希表的效率高。這是因為沖突的次數較少。
再次，當規模再大 （大約為 90%*P < a < P ）的時候，哈希表的效率大幅下降。這是因為沖突的次數大大提高了，為了解決沖突，程序不得不遍歷一段都存儲了元素的數組空間來尋找空位置。用白箱測試的方法統計，當規模為13500的時候，為了找空位置，線性重新散列平均做了150000 次運算；而當規模為15000 的時候，平均竟然高達2000000 次運算，某些數據甚至能達到4265833次。顯然浪費這么多次運算來解決沖突是不合算的，解決這個問題可以擴大表的規模，或者使用「開散列」（盡管它是動態數據結構）。然而需要指出的是，沖突是不可避免的。
初步結論：
當數據規模接近哈希表上界或者下界的時候，哈希表完全不能夠體現高效的特點，甚至還不如一般演算法。但是如果規模在中央，它高效的特點可以充分體現。我們可以從圖像直觀的觀察到這一點。
試驗表明當元素充滿哈希表的 90% 的時候，效率就已經開始明顯下降。這就給了我們提示：如果確定使用哈希表，應該盡量使數組開大（由於競賽中可利用內存越來越多，大數組通常不是問題，當然也有少數情況例外），但對最太大的數組進行操作也比較費時間，需要找到一個平衡點。通常使它的容量至少是題目最大需求的 120% ，效果比較好（這個僅僅是經驗，沒有嚴格證明）。
4. 應用舉例
4.1 應用的簡單原則
什麼時候適合應用哈希表呢？如果發現解決這個問題時經常要詢問：「某個元素是否在已知集合中？」，也就是需要高效的數據存儲和查找，則使用哈希表是最好不過的了！那麼，在應用哈希表的過程中，值得注意的是什麼呢？
哈希函數的設計很重要。一個不好的哈希函數，就是指造成很多沖突的情況，從前面的例子已經可以看出來，解決沖突會浪費掉大量時間，因此我們的目標就是盡力避免沖突。前面提到，在使用「除余法」的時候，h(k)=k mod p ，p 最好是一個大素數。這就是為了盡力避免沖突。為什麼呢？假設 p=1000 ，則哈希函數分類的標准實際上就變成了按照末三位數分類，這樣最多1000類，沖突會很多。一般地說，如果 p 的約數越多，那麼沖突的幾率就越大。
簡單的證明：假設 p 是一個有較多約數的數，同時在數據中存在 q 滿足 gcd(p,q)=d >1 ，即有 p=a*d , q=b*d, 則有 q mod p= q – p* [q div p] =q – p*[b div a] . ① 其中 [b div a ] 的取值范圍是不會超過 [0，b] 的正整數。也就是說， [b div a] 的值只有 b+1 種可能，而 p 是一個預先確定的數。因此 ① 式的值就只有 b+1 種可能了。這樣，雖然mod 運算之後的余數仍然在 [0，p-1] 內，但是它的取值僅限於 ① 可能取到的那些值。也就是說余數的分布變得不均勻了。容易看出， p 的約數越多，發生這種余數分布不均勻的情況就越頻繁，沖突的幾率越高。而素數的約數是最少的，因此我們選用大素數。記住「素數是我們的得力助手」。
另一方面，一味的追求低沖突率也不好。理論上，是可以設計出一個幾乎完美，幾乎沒有沖突的函數的。然而，這樣做顯然不值得，因為這樣的函數設計很浪費時間而且編碼一定很復雜，與其花費這么大的精力去設計函數，還不如用一個雖然沖突多一些但是編碼簡單的函數。因此，函數還需要易於編碼，即易於實現。
綜上所述，設計一個好的哈希函數是很關鍵的。而「好」的標准，就是較低的沖突率和易於實現。
另外，使用哈希表並不是記住了前面的基本操作就能以不變應萬變的。有的時候，需要按照題目的要求對哈希表的結構作一些改進。往往一些簡單的改進就可以帶來巨大的方便。
這些只是一般原則，真正遇到試題的時候實際情況千變萬化，需要具體問題具體分析才行。
『貳』 對於線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K %9作為散列函數
答案選D，
4個。分別是：55，64，46，10.
H（K）=
K%9，表示除以9的余數。由於地址重疊造成沖突，所以散列存儲時，通常還要有解決沖突的辦法，如線性探查法等等。
『叄』 《數據結構》考試復習
通常有集中復習、分散復習、穿插復習三種形式。課後復習宜於分散、經常進行。以記憶為主的學習內容，如英語的單詞、語文的背誦課文，要今年多次重復以強化記憶，應分散復習。階段復習最好集中用整塊時間，一次復習深透為好。當然集中復習又可將性質不同的課程（如史地、數理）交替安排，穿插復習，使大腦各神經區得到輪換休息，腦的工作效率高。
『肆』 線性表的順序存儲結構通過________來直接反映數據元素之間的邏輯關系,而鏈式存儲結構則通過_______
在線性表的順序存儲結構中，元素之間的邏輯關系是通過（
元素的存儲地址
）決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過（
結點中的指針
）決定的。
『伍』 高分求數據結構與演算法答案
1-5 ACDCC 6.你寫的我分不清,答案是2的（i-1）次方7-10 CCCB 11-15 BDA()C
16-18 CDA 46-50 CCACB
14題 B_樹 是不是biinary tree（二叉樹)啊？,沒說清楚，沒法回答。
就一題了，估計你自己也能解決，這些題都很基礎，不難。
『陸』 在線性表的順序存儲結構中，邏輯上相鄰的兩個元素在物理位置上並不一定緊鄰，是對是錯
是錯的，在線性表的順序存儲結構中，邏輯上相鄰的兩個元素在存儲位置上一定是相鄰的，所以說題目中的說法是錯誤的。
順序存儲結構是存儲結構類型中的一種，該結構是把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元中，結點之間的邏輯關系由存儲單元的鄰接關系來體現。
在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素,稱作線性表的順序存儲結構。
(6)在線性表的散列存儲中擴展閱讀：
順序存儲結構的優缺點：
優點：隨機存取表中元素、儲存密度大。
缺點：插入和刪除操作需要移動元素。
線性表的特徵：
1、集合中必存在唯一的一個「第一元素」。
2、集合中必存在唯一的一個「最後元素」。
3、除最後一個元素之外，均有唯一的後繼(後件)。
4、除第一個元素之外，均有唯一的前驅(前件)。
線性表的結構特點：
1、均勻性，雖然不同數據表的數據元素可以是各種各樣的，但對於同一線性表的各數據元素必定具有相同的數據類型和長度。
2、有序性，各數據元素在線性表中的位置只取決於它們的序號，數據元素之前的相對位置是線性的，即存在唯一的「第一個」和「最後一個」的數據元素，除了第一個和最後一個外，其它元素前面均只有一個數據元素和後面均只有一個數據元素。
參考資料來源：網路-順序存儲結構
參考資料來源：網路-線性表
『柒』 數據結構的存儲方式有哪幾種
數據結構的存儲方式有順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法這四種。
1、順序存儲方式：順序存儲方式就是在一塊連續的存儲區域一個接著一個的存放數據，把邏輯上相連的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接掛安息來體現。順序存儲方式也稱為順序存儲結構，一般採用數組或者結構數組來描述。
2、鏈接存儲方法：它比較靈活，其不要求邏輯上相鄰的結點在物理位置上相鄰，結點間的邏輯關系由附加的引用欄位表示。一個結點的引用欄位往往指導下一個結點的存放位置。鏈接存儲方式也稱為鏈接式存儲結構，一般在原數據項中增加應用類型來表示結點之間的位置關系。
3、索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。它細分為兩類：稠密索引：每個結點在索引表中都有一個索引項，索引項的地址指示結點所在的的存儲位置；稀疏索引：一組結點在索引表中只對應一個索引項，索引項的地址指示一組結點的起始存儲位置。
4、散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。
(7)在線性表的散列存儲中擴展閱讀
順序存儲和鏈接存儲的基本原理
在順序存儲中，每個存儲空間含有所存元素本身的信息，元素之間的邏輯關系是通過數組下標位置簡單計算出來的線性表的順序存儲，若一個元素存儲在對應數組中的下標位置為i，則它的前驅元素在對應數組中的下標位置為i-1，它的後繼元素在對應數組中的下標位置為i+1。
在鏈式存儲結構中，存儲結點不僅含有所存元素本身的信息，還含有元素之間邏輯關系的信息。數據的鏈式存儲結構可用鏈接表來表示。其中data表示值域，用來存儲節點的數值部分。Pl，p2，…，Pill(1n≥1)均為指針域，每個指針域為其對應的後繼元素或前驅元素所在結點的存儲位置。
在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同；而在數據的鏈接存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到，訪問任一元素的時間與該元素結點在鏈式存儲結構中的位置有關。
『捌』 在線性表的散列儲存中，處理沖突的常用方法有哪兩種
線性表的散列存儲時中,處理沖突有
『玖』 在線性表的順序存儲結構中元素間的邏輯關系是通過什麼決定的鏈式存儲結構呢
在線性表的順序存儲結構中，元素之間的邏輯關系是通過（
元素的存儲地址
）決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過（
結點中的指針
）決定的。