鏈地址演算法
Ⅰ 比較開放地址和鏈地址法沖突處理技術的優缺點
開放地址法將所有結點均存放在散列表（Hash）T[0..m-1]中，鏈址法將互為同義詞的結點鏈成一個但鏈表，而將此鏈表的頭指針放在散列表T[0..m-1]中。
與開放地址相比鏈地址法有如下優點：1，鏈地址法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短。2，鏈地址法中鏈表的結點是動態申請的，故它更適合造表前無法確定表長的情況，3，開放定址法為了減少沖突要求填充因子較小，故結點規模較大時會浪費很多空間，而鏈地址法中填充因子可以大於1且結點較大時，拉鏈法中增加的指針域可以忽略不計，因此節省空間，4，鏈地址法構造的散列表刪除結點很方便，只需簡單的刪去鏈表上相應的結點即可。
Ⅱ 查找的計算機演算法
⒈順序查找的思想是：
將查找值順序逐個與結點值進行比較，相等即為查找成功，否則查找失敗.
程序如下：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
b:boolean;
place:integer;
procere search(r:arr;m,x:integer; var found:boolean;var p:integer);
begin
p:=1;found:=false;
while(p<=m) and not found do
if r[p]=x then found:=true else p:=p+1;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
search(a,n,x1,b,place);
if b then begin writeln('yes');writeln('Place of',x1:5,'is:',place); end
else writeln('no');
end. ⒈二分查找的基本思想：首先將結點按關鍵字排序，其次將查找值與中間位置的值比較，相等，查找成功；不等，則中間數據大於或小於查找值，無論怎樣查找將在一半的數據中查找。
⒉例：輸入序列數據查找指定值.
程序：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
place:integer;
procere paixv(var r:arr;m:integer);
var k,j,i,t:integer;
begin
k:=m;
while k>0 do
begin
j:=k-1;k:=0;
for i:=1 to j do
if r[i]>r[i+1] then
begin t:=r[i];a[i]:=r[i+1];r[i+1]:=t;k:=i;end;
end;
end;
procere search(r:arr;m,x:integer; var p:integer);
var low,high,mid:integer;
begin
p:=0;low:=1;high:=m;
while low<=high do
begin
mid:=(low+high) div 2;
if x>r[mid] then low:=mid+1 else
if x<r[mid] then high:=mid-1 else
begin p:=mid;exit;end;
end;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
paixv(a,n);
search(a,n,x1,place);
if place<>0 then writeln('yes') else writeln('no');
end. 因為二叉排序樹的左子樹若不為空則左子樹的所有結點的值均小於它的根結點的值，而右子樹若不為空，則右子樹的所有結點的值均不小大於它的根結點的值，根據這個性質查找演算法如下：
program pxtree;
const
a:array[1..8] of integer=（10,18,3,8,12,2,7,3）；
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i,x:integer;
procere maketr(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d>=w then maketr(d,right) else maketr(d,left);
end;
function searchtr(x:integer;p:point):boolean;
begin
if p=nil then searchtr:=false
else if x=p^.w then searchtr:=true
else if x<p^.w then searchtr:=searchtr(x,p^.left)
else searchtr:=searchtr(x,p^.right);
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do maketr(a[i],first);
write('want find data x:');read(x);
if searchtr(x,first) then writeln('yes') else writeln('No');
end. 以上講的查找方法基於比較的，查找效率依賴比較次數，其實理想的查找希望不經比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，這樣查找k時，只要根據這個對應關系f找到給定值k的像f(k）。這種對應關系f叫哈希（hash）函數。按這種思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存儲時容易沖突（collision）：即不同的關鍵字可以對應同一哈希地址。如何確定哈希函數和解決沖突是關鍵。
⒈哈希函數的構造方法
直接定址法：H(k)=k 或H(k)=a*k+b（線形函數）
如：人口數字統計表 地址 1 2 3 ... 100 年齡 1 2 3 ... 100 人數 67 3533 244 ... 4 數字分析法：取關鍵字的若干數位組成哈希地址
如：關鍵字如下：若哈希表長為100則可取中間兩位10進制數作為哈希地址。 81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537 平方取中法：關鍵字平方後取中間幾位數組成哈希地址
折疊法：將關鍵數字分割成位數相同的幾部分（最後一部分的位數可以不同）然後取幾部分的疊加和（捨去進位）作為哈希地址。
除留余數法：取關鍵字被某個不大於表長m的數p除後所得的余數為哈希地址。
H(k)=k mod p p<=m
隨機數法：H(k)=rondom(k）。
⒉處理沖突的方法
假設地址集為0..n-1，由關鍵字得到的哈希地址為j(0<=j<=n-1）的位置已存有記錄，處理沖突就是為該關鍵字的記錄找到另一個空的哈希地址。在處理中可能得到一個地址序列Hi i=1，2，...k
0<=Hi<=n-1），即在處理沖突時若得到的另一個哈希地址H1仍發生沖突，再求下一地址H2，若仍沖突，再求H3...。怎樣得到Hi呢？
開放定址法：Hi=(H(k)+di) mod m （H(k）為哈希函數；m為哈希表長；di為增量序列）
當di=1，2，3，... m-1 時叫線性探測再散列。
當di=1，-1，2，-2，3，-3，...,k,-k時叫二次探測再散列。
當di=random（m）時叫偽隨機探測序列。
例：長度為11的哈希表關鍵字分別為17，60，29，哈希函數為H(k)=k mod 11，第四個記錄的關鍵字為38，分別按上述方法添入哈希表的地址為8，4，3（隨機數=9）。
再哈希法：Hi=RHi(key) i=1,2,...,k，其中RHi均為不同的哈希函數。
鏈地址法：這種方法很象基數排序，相同的地址的關鍵字值均鏈入對應的鏈表中。
建立公益區法：另設一個溢出表，不管得到的哈希地址如何，一旦發生沖突，都填入溢出表。
⒊哈希表的查找
例：如下一組關鍵字按哈希函數H(k)=k mod 13和線性探測處理沖突所得的哈希表a[0..15]: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 01 68 27 55 19 20 84 79 23 11 10 當給定值k=84，則首先和a[6]比在依次和a[7],a[8]比結果a[8]=84查找成功。
當給定值k=38，則首先和a[12]比，再和a[13]比，由於a[13]沒有，查找不成功，表中不存在關鍵字等於38的記錄。 查找第k小元素即在n個元素中（未排序）找到第k小的元素。方法同快速排序，採用遞歸方式。
程序如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
b:arr;
i,k:integer;
function p(s,t:integer):integer;
var i,j,t1,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
p:=i;
end;
function find(s,t,k:integer):integer;
var p1,q:integer;
begin
if s=t then find:=b[s] else
begin
p1:=p(s,t);
q:=p1-s+1;
if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);
end;
end;
begin
write('input data:');
for i:=1 to n do read(b[i]);readln;
write('input k:');read(k);
write('output data:');
writeln('kthsmall:=',find（1,n,k));
end.
Ⅲ 演算法與數據結構的一個題目，用鏈地址法和開放定址法，求等概率情況下查找成功時的平均查找長度
1)用開放定址法處理沖突，選用線性探測再散列處理沖突，即Hi=(H(k)+di) MOD m，m=6。並求等概率情況下查找成功時的平均查找長度。
查找長度為： 1、 1、 3、 1、 4 等概率情況下查找成功時的平均查找長度為 10/5=2.0
2)用鏈地址法處理沖突，並求等概率情況下查找成功時的平均查找長度。
查找長度為： 1、 1、 2、 1、 2 等概率情況下查找成功時的平均查找長度為 7/5=1.4
Ⅳ 用數據結構鏈地址法解決沖突，編寫插入、刪除和查找演算法
多看看數據結構里的鏈接地址法的相關知識，像基本的插入刪除，查找都有講的。看一點樹，圖的知識。很久沒看書了，也忘記了，呵呵。書上有目錄的都有聯接地址發的敘述的。就是一般的數據結構的書都有吧。主要是在講二叉樹和圖的那些地方有這些存儲方法的數據結構。
Ⅳ java 哈希表 鏈地址法
我有時間就跟你講了,java中的話用Hashset類，c裡面也應該有對應的庫函數吧。。hash的機制你知道吧？？？
Ⅵ 一道數據結構題，請問，這個18題，鏈地址法查找失敗的ASL，是怎麼分析的，求解釋，謝謝
圖看的不是太清楚，重新畫了一下：
等概率下鏈地址查找失敗的ASL是這樣計算的：
散列地址為1、4、7、8、9時，對應鏈表中都沒有元素，無需比較，總比較次數為0；
散列地址為0、3、5、6、10時，對應鏈表中都只有一個元素，比較一次就可以判斷失敗，總比較次數為：1x5 = 5；
散列地址為2時，對應鏈表中有兩個元素，需比較兩次，總比較次數為2；
散列地址為12時，對應鏈表中有4個元素，需比較4次，總比較次數為4；
前提是等概率，13個地址，因此查找失敗的ASL = (0+5+2+4) / 13 = 11/13。
Ⅶ 鏈地址法處理沖突的散列表: 試實現用除留余法構造散列表,鏈地址法處理沖突的散列表類
#include <stdio.h>
#include <malloc.h>
#define NULLKEY 0 // 0為無記錄標志
#define N 10 // 數據元素個數
typedef int KeyType;// 設關鍵字域為整型
typedef struct
{
KeyType key;
int ord;
}ElemType; // 數據元素類型
// 開放定址哈希表的存儲結構
int hashsize[]={11,19,29,37}; // 哈希表容量遞增表，一個合適的素數序列
int m=0; // 哈希表表長，全局變數
typedef struct
{
ElemType *elem; // 數據元素存儲基址，動態分配數組
int count; // 當前數據元素個數
int sizeindex; // hashsize[sizeindex]為當前容量
}HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
// 構造一個空的哈希表
int InitHashTable(HashTable *H)
{
int i;
(*H).count=0; // 當前元素個數為0
(*H).sizeindex=0; // 初始存儲容量為hashsize[0]
m=hashsize[0];
(*H).elem=(ElemType*)malloc(m*sizeof(ElemType));
if(!(*H).elem)
exit(0); // 存儲分配失敗
for(i=0;i<m;i++)
(*H).elem[i].key=NULLKEY; // 未填記錄的標志
return 1;
}
// 銷毀哈希表H
void DestroyHashTable(HashTable *H)
{
free((*H).elem);
(*H).elem=NULL;
(*H).count=0;
(*H).sizeindex=0;
}
// 一個簡單的哈希函數(m為表長，全局變數)
unsigned Hash(KeyType K)
{
return K%m;
}
// 開放定址法處理沖突
void collision(int *p,int d) // 線性探測再散列
{
*p=(*p+d)%m;
}
// 演算法9.17
// 在開放定址哈希表H中查找關鍵碼為K的元素,若查找成功,以p指示待查數據
// 元素在表中位置,並返回SUCCESS;否則,以p指示插入位置,並返回UNSUCCESS
// c用以計沖突次數，其初值置零，供建表插入時參考。
int SearchHash(HashTable H,KeyType K,int *p,int *c)
{
*p=Hash(K); // 求得哈希地址
while(H.elem[*p].key!=NULLKEY&&!(K == H.elem[*p].key))
{
// 該位置中填有記錄．並且關鍵字不相等
(*c)++;
if(*c<m)
collision(p,*c); // 求得下一探查地址p
else
break;
}
if (K == H.elem[*p].key)
return SUCCESS; // 查找成功，p返回待查數據元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置
}
int InsertHash(HashTable *,ElemType); // 對函數的聲明
// 重建哈希表
void RecreateHashTable(HashTable *H) // 重建哈希表
{
int i,count=(*H).count;
ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
p=elem;
printf("重建哈希表\n");
for(i=0;i<m;i++) // 保存原有的數據到elem中
if(((*H).elem+i)->key!=NULLKEY) // 該單元有數據
*p++=*((*H).elem+i);
(*H).count=0;
(*H).sizeindex++; // 增大存儲容量
m=hashsize[(*H).sizeindex];
p=(ElemType*)realloc((*H).elem,m*sizeof(ElemType));
if(!p)
exit(0); // 存儲分配失敗
(*H).elem=p;
for(i=0;i<m;i++)
(*H).elem[i].key=NULLKEY; // 未填記錄的標志(初始化)
for(p=elem;p<elem+count;p++) // 將原有的數據按照新的表長插入到重建的哈希表中
InsertHash(H,*p);
}
// 演算法9.18
// 查找不成功時插入數據元素e到開放定址哈希表H中，並返回1；
// 若沖突次數過大，則重建哈希表。
int InsertHash(HashTable *H,ElemType e)
{
int c,p;
c=0;
if(SearchHash(*H,e.key,&p,&c)) // 表中已有與e有相同關鍵字的元素
return DUPLICATE;
else if(c<hashsize[(*H).sizeindex]/2) // 沖突次數c未達到上限,(c的閥值可調)
{
// 插入e
(*H).elem[p]=e;
++(*H).count;
return 1;
}
else
RecreateHashTable(H); // 重建哈希表
return 0;
}
// 按哈希地址的順序遍歷哈希表
void TraverseHash(HashTable H,void(*Vi)(int,ElemType))
{
int i;
printf("哈希地址0～%d\n",m-1);
for(i=0;i<m;i++)
if(H.elem[i].key!=NULLKEY) // 有數據
Vi(i,H.elem[i]);
}
// 在開放定址哈希表H中查找關鍵碼為K的元素,若查找成功,以p指示待查數據
// 元素在表中位置,並返回SUCCESS;否則,返回UNSUCCESS
int Find(HashTable H,KeyType K,int *p)
{
int c=0;
*p=Hash(K); // 求得哈希地址
while(H.elem[*p].key!=NULLKEY&&!(K == H.elem[*p].key))
{ // 該位置中填有記錄．並且關鍵字不相等
c++;
if(c<m)
collision(p,c); // 求得下一探查地址p
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
if (K == H.elem[*p].key)
return SUCCESS; // 查找成功，p返回待查數據元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
void print(int p,ElemType r)
{
printf("address=%d (%d,%d)\n",p,r.key,r.ord);
}
int main()
{
ElemType r[N] = {
{17,1},{60,2},{29,3},{38,4},{1,5},
{2,6},{3,7},{4,8},{60,9},{13,10}
};
HashTable h;
int i, j, p;
KeyType k;
InitHashTable(&h);
for(i=0;i<N-1;i++)
{
// 插入前N-1個記錄
j=InsertHash(&h,r[i]);
if(j==DUPLICATE)
printf("表中已有關鍵字為%d的記錄，無法再插入記錄(%d,%d)\n",
r[i].key,r[i].key,r[i].ord);
}
printf("按哈希地址的順序遍歷哈希表:\n");
TraverseHash(h,print);
printf("請輸入待查找記錄的關鍵字: ");
scanf("%d",&k);
j=Find(h,k,&p);
if(j==SUCCESS)
print(p,h.elem[p]);
else
printf("沒找到\n");
j=InsertHash(&h,r[i]); // 插入第N個記錄
if(j==0) // 重建哈希表
j=InsertHash(&h,r[i]); // 重建哈希表後重新插入第N個記錄
printf("按哈希地址的順序遍歷重建後的哈希表:\n");
TraverseHash(h,print);
printf("請輸入待查找記錄的關鍵字: ");
scanf("%d",&k);
j=Find(h,k,&p);
if(j==SUCCESS)
print(p,h.elem[p]);
else
printf("沒找到\n");
DestroyHashTable(&h);
system("pause");
return 0;
}
/*
輸出效果：
表中已有關鍵字為60的記錄，無法再插入記錄(60,9)
按哈希地址的順序遍歷哈希表:
哈希地址0～10
address=1 (1,5)
address=2 (2,6)
address=3 (3,7)
address=4 (4,8)
address=5 (60,2)
address=6 (17,1)
address=7 (29,3)
address=8 (38,4)
請輸入待查找記錄的關鍵字: 17
address=6 (17,1)
重建哈希表
按哈希地址的順序遍歷重建後的哈希表:
哈希地址0～18
address=0 (38,4)
address=1 (1,5)
address=2 (2,6)
address=3 (3,7)
address=4 (4,8)
address=6 (60,2)
address=10 (29,3)
address=13 (13,10)
address=17 (17,1)
請輸入待查找記錄的關鍵字: 13
address=13 (13,10)
請按任意鍵繼續. . .
*/
Ⅷ c語言哈希表鏈地址法問題
結構體的成員x_和y_保存的是什麼？
你的
intp=Hash(cell);
找到所項後，因為該項中要有一個鏈保存一系列元素，所以該鏈應為一指向hash元素的指針。
判斷條件因為該項是否為NULL，若為NULL（地址不沖突），否則沖突，執行的是鏈表的插入操作，插入到前後首位隨你意願（一般插前邊）。
Ⅸ 散列表鏈地址法查找成功的平均查找長度怎麼計算
一、舉個例子：數組長度10 散列函數x%7。
如 13 先計算散列 13%7 = 6 如果沒有沖突的話會被放在第六個格子里。
現在散列表中 ： (x為已經有一個元素 o表示空)
0 x
1 x
2 x
3 o
4 o
5 x
6 x
7 x
8 x
9 o
計算失敗概率 ：
思路如下，任意出現一個數字（概率均等）經過hash函數以後 0 ~ 6的概率均等 現在假設 輸入一個數字 hash計算結果是1，去1里查找，結果發現位置1(接下來簡稱pos1)不是目標元素（查找失敗），於是線性探查找到了2（還是失敗）然後找三，發現沒有，於是確定所找元素不在哈希表裡。
以上是查找過程，以此類推失敗的情況下需要找 4，3，2，1，1，5，4 （7和7以後沒得找，因為任何數膜7都<7）失敗概率。
二、查找不成功的次數表如下表所示
Key 7 8 30 11 18 9 14
Count 3 2 1 2 1 5
所以ASLunsuccess= （3+2+1+2+1+5+4）/ 7 = 18/7。
(9)鏈地址演算法擴展閱讀：
散列函數
在進行查找時，在記錄的存儲位置與它的關鍵字之間建立一個確定的對應關系h,以線性表中每個元素的關鍵字K為自變數，通過函數h(K)計算出該元素的存儲位置，我們將h函數稱為散列函數或哈希函數。h(K)的值稱為散列地址或哈希地址。
例：
假定一個線性表為A=(18,75,60,43,54,90,46)，選取散列函數為：
h(K)=K%m 取m=13
則得每個元素散列地址：
h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8 h(43)=43 % 13=4
h(54)=54 % 13=2 h(90)=90 % 13=12 h(46)=46 % 13=7
Ⅹ 假設散列函數為H(K)＝k%11，採用鏈地址法處理沖突，設計演算法
ASL=p1c1+p2c2+p3c3+....... 也可以表示為 ASL=1/n(c1+c2+c3+....) 其中c是每個數查詢的次數 按照H（K）=k mod 7得： 38----1 25----1 74----2 63----1 52----4 48----3 所以ASL=1/6（1+1+2+1+4+3）=2