链地址算法
Ⅰ 比较开放地址和链地址法冲突处理技术的优缺点
开放地址法将所有结点均存放在散列表（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