哈希表查找不成功的平均查找长度题目是：将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储

/*
（1）设计哈希表，该表应能够容纳50个英文单词。
（2）对该哈希表进行查询，实现对特定单词的快速查询，并显示经过的节点内容
已经发到你邮箱里了 enochwills@hotmail.com
*/
#include
#include
#include
#include
#include
#define szNAME 80
#define HASH_ROOT 47 /*用于计算哈希地址的随机数*/
#define szHASH 50 /*哈希表总长度*/
#define POPULATION 30 /*学生总数*/
/*哈希表结构体*/
struct THash {
int key; /*钥匙码*/
char name[10]; /*姓名*/
int depth; /*检索深度*/
};
/*根据钥匙码和哈希根计算哈希地址*/
int GetHashAddress(int key, int root)
{
return key % root;
}/*end GetHashAddress*/
/*冲突地址计算，如果发现地址冲突，则用当前地址和钥匙码、哈希根重新生成一个新地址*/
int GetConflictAddress(int key, int address, int root)
{
int addr = address + key % 5 + 1;
return addr % root;
}/*end GetConflictAddress*/
/*根据字符串生成哈希钥匙码，这里的方法是将串内所有字符以数值形式求累加和*/
int CreateKey(char * name)
{
int key = 0;
unsigned char * n = (unsigned char *)name;
while(*n) key += *n++;
return key;
}/*end CreateKey*/
/*输入一个名字，并返回哈希钥匙码*/
int GetName(char * name)
{
scanf("%s", name);
return CreateKey(name);
}/*end CreateKey*/
/*根据学生人数、长度和哈希根构造哈希表*/
struct THash * CreateNames(int size, int root, int population)
{
int i =0, key = 0, addr = 0, depth = 0; char name[10];
struct THash * h = 0, *hash = 0;
/*哈希根和长度不能太小*/
if(size < root || root < 2) return 0;
/*根据哈希表长度构造一个空的哈希表*/
hash = (struct THash *)malloc(sizeof(struct THash) * size);
/*将整个表清空*/
memset(hash, 0, sizeof(struct THash) * size);
for(i = 0; i < population; i++) {
/*首先产生一个随机的学生姓名，并根据姓名计算哈希钥匙码，再根据钥匙码计算地址*/
key = GetName(name);
addr = GetHashAddress(key, root);
h = hash + addr;
if (h->depth == 0) { /*如果当前哈希地址没有被占用，则存入数据*/
h->key = key;
strcpy(h->name , name);
h->depth ++;
continue;
}/*end if*/
/*如果
很高兴回答楼主的问题 如有错误请见谅

应该是D,栈只是一种后进先出的调度方式而已,与数据结构无关
入栈、出栈的可以是各种变量,甚至可以是当前运行环境

h(19)=8,h(1)=1,h(23)=1->2,h(14)=3,h(15)=0,h(68)=2->3->4,h(11)=0->1->2->3->4->5,h(82)=5->6,h(36)=3->4->5->6->7线性探测正确 二次探测H(19)=8H(1)=1H(23)=1,h(23+1^2)=2H(14)=3H(55)=0H(68)=2,h(68+1^2)=3,h(68-1^2)=1,h(68+2^2)=6H(11)=0,h(11+1^2)=1,h(11-1^2)=10H(82)=5H(36)=3,h(36+1^2)=4

哈希表的建立：
key： 0 1 2 3 4 5 6 7 8 9 10 11 12
55 68 11 79 14 27 23 84 19 20 10 1
ASL=(1+1+1+1+1+1+3+2+2+6+11)/12
做此类题应注意哈希冲突函数怎么构建，此题采用线性探测法，即如果产生冲突方法为H+1一直到没有冲突为止。哈希表的建立，是依照key依次算对应的哈希码。
平均查找长度就是查找成功需要的次数除以总个数。答案自己算。这样的题自己多动手。看懂了的话要好评啊！呵呵。

地址空间：0 1 2 3 4 5 6
23
14 23
14 23 9
14 23 9 6
14 23 9 30 6
14 23 9 30 12 6
14 18 23 9 30 12 6

用线性探测法：发生冲突后,从该地址开始顺序向下一个地址探测,直到找到一个空的单元
H(22)=(22*3)mode 11=0
H(41)=(41*3)mode 11=2
H(53)=(53*3)mode 11=5
H(46)=(46*3)mode 11=6
H(30)=(30*3)mode 11=2,和 H(41)冲突,则探测下个地址：H1=(H(41)+1)mode 11=3;
H(13)=(13*3)mode 11=6,和H(46)冲突,则探测下个地址：H1=(H(13)+1)mode 11=7;
H(01)=3; 和H(30)冲突,则探测下个地址：H1=(H(01)+1)mode 11=4
H(67)=(67*3)mode 11=3,和H(01)冲突,则探测下个地址：H1=(H(67)+1)mode 11=4,和冲突,
则探测下个地址：H2=(H(01)+2)mode 11=5; 和H(53)冲突,继续探测:H3=6,和H(46)冲突,继续探测：H4=7,又冲突：H5=8;
则平均查找长度=(4*1+3*2+1*6)/8=2 答案应该是 2；我算几次了,不可能17/8,要不题目错了 方法是对

15,38,61,84除11的余数分别为4,5,6,7,没有重复,因此分别就放在这4个下标
49除11的余数为5,发生冲突,因为是二次探测,所以接下来分别探测+1, -1, +4, -4, +9, -9...
显然5 + 1, 5 - 1的位置都有冲突,5 + 4的位置没有冲突
所以最后放入的位置是9,也就是答案D

很明显,正确的是D
哈希表主要用于查找；有向图的结点有些场合下关系不能是任意的,比如拓扑排序中弧头结点不可能会出现在弧尾结点之前；图的广度优先搜索算法一般采用队列实现；图是一般的数据结构形式,线性结构和树形结构都是图的一种特殊形式.

10%13 = 10 存放在key=10的位置
100 %13 = 9 存放在key=9的位置
32%13 = 6 存放在key=6的位置
45%13 = 6 冲突,会有个冲突处理函数,这里以key = key+1 则放在key=7的位置
58%13 = 6 冲突,key+1 = 7 冲突,再加1 放在key=8的位置
126%13 = 8 放在key=8,冲突,放在key=9的位置
3%13 = 3 放在key=4的位置
29%13=3 冲突,4也冲突,放在key=5的位置
200%13 = 5 冲突,6 冲突,7 冲突,8 冲突,9冲突 放在key=10的位置
400%13 = 10 冲突,放在key=11的位置
0%13=0 放在key=0的位置.
哈希函数一般都要精心设计,尽量减少冲突次数,提高效率
自己数下有都少次冲突.

依次计算已经存放各关键字的位置：
22 % 11 = 0
12 % 11 = 1
24 % 11 = 2
30 % 11 = 7
52 % 11 = 8
43 % 11 = 10
都没有发生冲突,其位置就是散列函数值
63 % 11 = 8
与52 发生冲突,按照线性探测再散列的方法处理冲突,先探查8 + 1 = 9,这个位置空,没有关键字冲突,因此哈希地址为9

由除余法的散列函数计算出的上述关键字序列的散列地址为(12，12，8，9，0，2，11，3，2，2)。
先插入25 T[12]的位置，51也是12，所以再探查（12+1） mod 13 = 0, 插入T[0]位置，8插入T[8]，22插入T[9], 26插入T[0],发现被占，再探查（0+1） mod 13 =1,插入T[1], 67插入T[2],11插入T[11],16插入T[3],54插入T[2],发现T[2]被占，（2+1）mod 13 =3, T[3]依旧被占，再探查，（2+2）mod 13 =4,插入T[4]，41发现T[2]被占，T[3] T [4]也被占，（2+3）mod 13 = 5，T[5]开放，插入,结果如下
地址空间 序列
0 51
1 26
2 67
3 16
4 54
5 41
6
7
8 8
9 22
10
11 11
12 25