数据结构查找第九章

第九章查找9.1基本概念9.2静态查找表9.3动态查找表9.4哈希表

基本概念查找表：是由同一类型的数据元素(或记录)构成的集合。静态查找表：对查找表只作查询或检索操作动态查找表：在对查找表进行查找过程中加入插入和删除操作查找：在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录).关键字：是数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录).主关键字：某关键字可以唯一标识一个记录。次关键字：用以识别若干记录的关键字影响查找效率的因素1.数据结构(查找表的存储结构)2.查找算法3.记录的存放形式(有序,无序)典型的关键字类型说明和数据元素类型说明：

TypedeffloatKeyType;//实型

Typedef

int

KeyType;//整型

Typedefchar*KeyType;//字符串型数据元素类型定义为：

typedef

struct{

KeyTypekey;//关键字域

……//其它域}ElemType;对两个关键字的比较约定为如下的宏定义//对数据类型关键字#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))…//对字符串型关键字#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)

9。2静态查找表顺序表的查找有序表的查找索引顺序表的查找抽象类型静态查找表定义为：ADTStaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。各数据元素均含有类型相同，可唯一数据元素的关键字数据关系R：数据元素同属一个集合基本操作P：Create(&ST,n);操作结果：构造一个含n各数据元素的静态查找表STDestroy(&ST);初始条件：静态查找表ST存在操作结果：销毁表STSearch(ST,key);初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”Traverse(ST,Visit());初始条件：静态查找表ST存在，Visit识对元素操作的应用函数操作结果：按某种次序对ST的每个元素调用函数visit()一次仅一次。一旦visit()失败，则操作失败。}ADTStaticSearchTable以顺序表或线性链表表示静态查找表。静态查找表的顺序存储结构：Typedef

struct{

ElemType*elem;//数据元素存储空间基址，建表时按实际长度分

//配，0号单元留空

intlength;//表长度}SSTable;顺序表的查找顺序查找的查找过程从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。顺序查找的缺点：平均查找长度较大优点：算法简单且适应面广

顺序查找顺序查找算法实现int

Search_Seq(SSTable

ST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0

ST.elem[0].key=key;//”哨兵“for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//从后往前找returni;//找不到时，i为0}//Search_Seq顺序查找操作的性能分析平均查找长度(AverageSearchLength)

为确定记录在查找表中的位置,需要和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度.

对于n个记录的表,查找成功时的平均查找长度为ASL=∑i=1n

pici

pi:为查找表中第i个记录的概率

ci:为查找到表中其关键字与给定值相等的第i个记录时,和给定值已经进行过比较的关键字个数.顺序查找平均查找长度在顺序查找过程中,ci取决于所查记录在表中的位置.一般情况下ci=n-i+1假设每个记录的查找概率相等即pi=1/n则在等概率下顺序查找平均查找长度为:ASLss=∑i=1n

pici

=1/n∑i=1n(n-i+1)ASLss

=(n+1)/2以有序表作为静态查找表时。

折半查找的查找过程：先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止，一般折半查找都是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或者查找区间的大小小于0时（表明查找不成功）为止。

有序表的查找折半查找算法

int

Search_Bin(SSTable

ST,KeyTypekey){//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;if(EQ(key.ST.elem[mid].key)returnmid;//找到待查元素elseifLT(key.ST.elem[mid].key)high=mid-1;//继续在前半区间查找

elselow=mid+1;//继续在后半区间查找}

return0;//顺序表中不存在待查元素}Search_Bin例：已知如下11个数据元素的有序表(关键字既为数据元素的值)：(05,13,19,21,37,56,64,75,80,88,92）现要查找关键字为21的数据元素,mid=(high+low)/2上界取整0513192137566475808892lowmidhighhighmidLowmid7581110924136图9.2折半查找操作过程的判定树折半查找操作的性能分析折半查找操作的过程可以用二叉树表示折半查找操作的性能分析假设有序表的长度n=2h-1,即h=log2(n+1),则描述折半查找的判定树是深度为h的满二叉树,树中层次为1的结点有一个,层次为2的结点有两个,…,层次为h的结点有2h-1.再假设pi=

1/n.ASLbs=∑i=1n

pici=1/n∑j=1h

j.2j-1=(n+1)/n.log2(n+1)-1ASLbs=log2(n+1)-1以索引顺序表表示静态查找表。分块查找又称索引顺序查找，是顺序查找的一种改进方法。此查找表中，除表本身外，尚需建立一个“索引表”分块查找过程：先确定待查记录所在的块(子表)，然后在块中顺序查找例：下图为一个表及其索引表索引顺序表的查找224886159索引表最大关键字起始地址22128203324483860748653子表(R1,R2,..,R4)(R5,R6,…,R8)(R9,R10….,R12)分块查找过程：先确定待查记录所在的块(子表)，然后在块中顺序查找

9.2动态查找表二叉排序树和平衡二叉树B-树和B+树动态查找表特点：表结构本身是在查找过程中动态生成，既对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。ADTDynamicSearchTable{

数据对象D:D是具有相同特性的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字

数据关系R：数据元素同属一个集合基本操作P：

InitDSTable(&DT);

操作结果：构造一个空的动态查找表DT

DestroyDSTable(&DT);

初始条件：动态查找表DT存在操作结果：销毁动态查找表DT

SearchDSTable(DT,key);

初始条件：动态查找表DT存在，key为和关键字类型相同的给定值操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”

InsertDSTable(&DT,e);初始条件：动态查找表DT存在，e为待插入的数据元素操作结果：若DT中不存在其关键字等于e.key的数据元素，则函数值为该元素的值或在表中的位置，否则为0DeleteDSTable(&DT,key);

初始条件：动态查找表DT存在，key为和关键字类型相同的给定值操作结果：若DT中存在其关键字等于key的数据元素，则删除之TraverseDSTable(DT,Visit());初始条件：动态查找表DT存在，Visit是对结点操作的应用函数操作结果：按某种次序对DT的每个接点调用函数Visit()

一次且至多一次。一旦Visit()失败，则操作失败}ADTDynamicSearchTable二叉排序树：或者是一棵空树；或者是具有下列性质的二叉树：⑴若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；⑵若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值⑶它的左，右子树也分别为二叉排序树二叉排序树及其平衡二叉树45531006190782437312二叉排序树图二叉排序树查找过程二叉排序树查找过程：当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根接点的关键字之间的大小关系，分别在左子树或右子树上继续查找例：查找关键字61的记录如图4553100619078243731261>4561>5361<10061=61查找成功查找右子树继续查找右子树查找左子树BiTree

SearchBST(BiTree

T,KeyTypekey){//在根指针T所指二叉排序树种递归地查找某关键字等于key的数据元素，若查找成功，则返回指向该数组元素结点地指针，否则返回空指针

if(!T)||EQ(key,T->data.key))return(T);//查找结束elseifLT(key,T->data.key)return(SearchBST(T->lchild.key));//在左子树中继续查找elsereturn(SearchBST(T->rchild,key));//在右子树中查找}//SearchBST二叉排序树查找算法插入过程：二叉排序树的结构通常不时一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点二叉排序树的插入例：查找的关键字序列为{45,24,53,45,12,24,90}则生成的二叉排序树如图：Φ空树45插入4524插入2453插入5312插入1290插入90StatusSearchBST(BiTree

T,KeyType

key,BiTree

f,BiTree&p)}//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULLif(!T){p=f;returnFALSE;}//查找不成功elseifEQ(key,T->data.key){p=T;returnTRUE;}//查找成功elseifLT(key,T->data.key)

searchBST(T->lchild,key,T,p);//在左子树中查找elseSearchBST(T->rchild,key,T,p);//在右子树中查}//SearchBST二叉排序树的插入算法StatusInsertBST(BiTree&T,ElemTypee){//当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回FALSEif(!SearchBST(T,e.key,NULL,p){//查找不成功

s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//被插结点*s为新的根结点elseifLT(e.key,p->data.key)p->lchild=s;//被插结点*s为左孩子

elsep->rchild=s;//被插结点*s为右孩子

returnTRUE;}elsereturnFALSE;//树中已有关键字相同的结点，不再插入}//InsertBST二叉排序树的删除设在二叉排序树上被删结点为*p(指向结点的指针p),其双亲结点为*f（结点指针为f)，且不失一般性，可设*p是*f的左孩子删除分三种情况：⑴若*p结点为叶子结点，既PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可⑵若*p结点只有左子树PL或者只有右子树PR，此时只有令PL或

PR直接成为其双亲结点*f的左子树即可。⑶若*p结点的左子树和右子树均不空时，分两种情况：方法一:是令*p的左子树为*f的左子树，而*p的右子树为*s(p左孩子的最右孩子)的右子树。方法二:是令*p的直接前驱s(p左孩子的最右孩子)替代*p,同时将s的左子树作为其双亲的右子树.或者是令*p的直接后继s(p右孩子的最左孩子)替代*p,同时将s的右子树作为其双亲的左子树.FPfp以*f为根的子树P1子树P1PR子树PR在二叉排序树上删除一个结点的算法StatusDeleteBST(BiTree&T,KeyTypekey){//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，并返回TRUE；否则返回FALSEIf(!T)returnFALSE;//不存在关键字等于key的数据元素Else{ifEQ(key,T->data.key)Delete(T);//找到关键字等于key的数据元素elseifLT(key,T->data.key)

DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);returnTRUE;}}//DeleteBST如前述三种情况综合所得删除操作算法：VoidDelete(BiTree&P){//从二叉排序树中删除结点p,并重接它得左或右子树

if(!p->rchild){//右子树空则只需重接它的左子树

q=p;p=p->lchild;free(q);}elseif(!p->lchild){//只需重接它的右子树

q=p;p=p->rchild;free(q);}从二叉排序树中删除结点pelse{//左右子树均不空

q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild}//转左，然后向右到尽头

p->data=s->data;//s指向被删结点的“前驱”

if(q!=p)q->rchild=s->lchild;//重接*q的右子树elseq->lchild=s->lchild;//重接*q的左子树Deletes;}}//Delete二叉排序树的查找分析在二叉排序树上查找其关键字等于给定值的结点的过程,恰是走了一条从根结点到该结点的路径的过程,和给定值比较的关键字个数不超过树的深度.因此,含有n个结点的二叉排序树的平均查找长度和树的形状有关.最差情况:单枝树ASL=(n+1)/2最好情况:平衡二叉树ASL=log2(n+1)-1平衡二叉树:或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1.平衡因子（BF)：该结点的左子树的深度减去它的右子树的深度.平衡二叉树上所有结点的平衡因子只可能是-1,0,和1.在构造二叉排序树的过程中,需要进行”平衡化”处理,成为二叉平衡树平衡二叉树

-1-101001平衡二叉树其中-1,0,1为平衡因子设:a为二叉排序树上插入结点而失去平衡的最小子树的根结点的指针⑴单向右旋平衡处理(LL型平衡旋转)⑵单向左旋平衡处理(RR型平衡旋转)

⑶双向旋转(先左后右)平衡处理(LR型平衡旋转)⑷双向旋转(先右后左)平衡处理(RL型平衡旋转)插入结点失去平衡后进行调整规律构成的二叉排序树为平衡树方法：例：设关键字序列为(13,24,37,90,53),构成平衡树过程如下Φ132413133724(a)空树(b)插入130(c)插入24-10(d)插入37-2-10371324000(e)向左逆时针右旋转平衡1353903724-20-210(f)相继插入90和531390533724(g)第一次向右顺时针旋转3713905324-10000(h)第二次向左逆时针旋转平衡之B-树的结构:一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：⑴树中每个结点至多有m棵子树⑵若根结点不是叶子结点，则至少有两棵子树⑶除根之外的所有非终端结点至少有m/2棵子树⑷所有的非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)其中:Ki为关键字，且

Ki<Ki+1,Ai为指向子树根结点的指针，n为关键字的个⑸所有的叶子结点都出现在同一层次上，并且不带信息B-树和B+树

一棵4阶的B-树图135199139127111118243783475364FFFFFFFFFFFFB-树查找过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程B-树结点类型说明：#definem3//B树的阶Typedef

struct

BTNode{

int

keynum;//结点大小

struct

BTNode*parent;//指向双亲结点

KeyTypeKey[m+1];//关键字向量，0号单元未用

struct

BTNode*ptr[m+1];//子树指针向量

Record*recptr[m+1];//记录指针向量}BTNode,*Btree;//B树结点和B树类型Typedef

struct{

BTNode*pt;//指向找到的结点

inti;//1…m，在结点中的关键字序号

inttag;//1查找成功，0查找失败}Result;//B树的查找结果类型B-树查找算法实现ResultSearchBTree(Btree

T,KeyTypeK){//在n阶B树T上查找关键字K，返回结果(pt,i,tag).若查找成功，则tag=1.指针pt所指向结点第i个关键字等于K，否则tag=0，等于K的关键字应插入在指针pt所指向结点中第i个和i+1个关键字之间P=T;q=NULL;found=FALSE;i=0;While(p&&!found){n=p->keynum;i=Search(p,K);//在p->key[1..keynum]中查找if(i>0&&p->key[i]==K)found=TRUE;//找到待查关键字else{q=p;p=p->ptr[i];}}if(found)return(p,i,1);//查找成功elsereturn(q,i,0);//查找不成功，返回K的插入位置信息}//SearchBTreeB-树的查找分析在B-树上进行查找包含两种操作:1.在B-树中找结点(在磁盘上进行)2.在结点中找关键字(在内存中进行)显然.在磁盘上进行一次查找比在内存中进行一次查找耗费时间多的多.在磁盘上进行查找次数,即待查关键字所在结点在B-树上的层次数,是决定B-树查找效率的主要因素.考虑最坏情况,即待查结点在B-树中的最大层次数,也就是,求含N个关键字的m阶B-树的最大深度是多少?

先讨论深度为L+1层的m阶B-树所具有的最少结点数

根据B-树的定义:

第一层至少有1个结点;第二层至少有2个结点;第三层至少有2(m/2上取整)个结点;........第L+1层至少有2(m/2上取整)L-1结点因为含N个关键字的m阶B-树中叶结点为N+1个,因此有N+1>=2(m/2上取整)L-1

反之L<=log[m/2]((N+1)/2)+1也就是说,含N个关键字的m阶B-树上进行查找时,所涉及的结点数不超过log[m/2]((N+1)/2)+1B-树的插入B-树的生成是从空树起，逐个插入关键字而得。由于B-树结点的关键字个数必须>=m/2-1，所以，每次插入一个关键字不是在树中填加一个叶子结点，而是首先在最低层的某个非终端结点中填加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的“分裂”.如图：B-树的插入

在3阶B-树中进行插入示例4524539037100617050312btabcdefgh一棵B-树4524539030

37100617050312btabcdefgh插入30之后45245390263037100617050312btabcdefgh4524

30539037100617050312btabcdefgh26d插入26之后4524305390

371006170

8550312btabcd’efgh26d4524305370903710050312btabcd’efgh266185g’d45

702430btab53901003726312615085插如85之后e’cdd’efgg’hStatusInsertBTree(Btree&T,KeyTypeK,Btreeq,inti){//在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字k若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B树X=K;ap=NULL;finished=FALSE;While(q&&!finished){

Insert(q,i,x,ap);//将x和ap分别插入q->key[i]和q->ptr[i]之间if(q->keynum<m)finished=TRUE;//插入完成

在B-树上插入关键字算法：else{//否则分裂结点qs=m/2+1;

splist(q,ap);x=q->key[s];//将q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新结点*apq=q->parent;if(q)i=Search(q,x);//在双亲结点*q中查找x的插入位置}//else}//whileif(!finished)//如果T是空树或者根结点分裂为结点*q和*ap

newRoot(T,q,x,ap);//生成含(T,x,ap)的新的根结点*T,原T和ap为子树的指针}//InsertBTreeB-树的删除删除一个关键字：首先找到该关键字所在的结点，并从中删除之，若该结点为最下层的非终端结点，且其中的关键字数目不少于m/2，则删除完成，否则要进行“合并”结点的操作。假若所删关键字为非终端结点中的Ki，则可以指针所指子树中的最小关键字Y替代Ki，

然后在相应的结点中删去Y.所以,我们只要讨论删除最下层的非终端结点中的关键字的情形.B-树的删除

(1)被删关键字所在结点中的关键字数目大于m/2上界取整-1,则只需从该结点中删除关键字Ki和相应的指针Ai该结点,树的其它部分不变.例：删去下图中关键字124524539037100617050312btabcdefgh例：删去下图中关键字12后的图312bt45245390371006170503(2)被删关键字所在结点中的关键字数目等于m/2上界取整-1，而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于m/2上界取整-1，则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在的结点中例：删去下图中关键字50312bt45245390371006170503例：下图中删去50后5390617050ef452437100361907053

bt删去50,61上移至*e结点中，53移至*f⑶被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于m/2上界取整-1，假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所有结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟结点中(若没有右兄弟，则合并至左兄弟结点中)：例：在下图中删去535390617050ef452437100361907053

bt4524371003906170

bt从该B-树中删去53，删去53结点，并将53结点的的剩余信息(指针“空”)和双亲结点*e结点中的61一起合并到右兄弟结点*g中。删除后变化如上图。ehgabcd4524371003906170

bt再从该B-树中删去37。ehgabcd如果因此使双亲结点中的关键字数目小于m/2上界取整-1，则依次类推。如在上图删去53结点后的图基础上，删去关键字37之后，双亲b结点中剩余信息(指针c)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中，删除后如下图：45901006170324bteghB+树是B-树的一个变型.一个m阶B-树和B+树的区别:1.有n棵子树的结点中含有n个关键字.2.所有叶结点中包含了全部关键字信息,及指向这些关键字的记录.3.所有非终端结点可以看成是索引部分,结点中仅含有子树中最大(或者最小)关键字见p246图9.18

9.3哈希表什么是哈希表哈希函数的构造方法处理冲突的方法哈希表的查找及其分析哈希函数：在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应，称这个对应关系f为hash函数哈希表：通过hash函数计算，将集合中元素存储在一个数组中，这个数组为hash表哈希冲突：对不同的关键字可能得到同一哈希地址，即key1≠key2,而f(key1)=f(key2),这种现象叫冲突

⑴直接定址法取关键字或关键字的某个线性函数值为哈希地址。即：H(key)=key或H(key)=a.key+b其中a和b为常数(这种哈希函数叫做自身函数)⑵数字分析法将关键字中的某几位进行运算后作为hash地址⑶折叠法将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址哈希函数的构造方法⑸除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址，既H(key)=keyMODpp<=m⑹随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机函数，通常，当关键字长度不等时采用此法构造哈希函数较恰当。处理冲突的方法⑴开放定址法公式：Hi=(H(key)+di)MODmi=1,2,…,k(k<=m-1)其中：H(key)为哈希函数；m为哈希表表长；di为增量序列，可有下列三种取法：①di=1,2,3,…,m-1,称线性探测再散列；②di=12,-12,22,-22,32,…,+k2,(k<=m/2)称二次探测再散列③di=伪随机数序列，称伪随机探测再散列例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录(hash函数H(key)=keyMOD11)，现有第四个记录，其关键字为38，由哈希函数H(38)=38MOD11得到哈希地址为5，产生冲突.下面分别用三种取法解决冲突601729012345678910设38插入前表如下所示60172938012345678910一：用线性探测法解决冲突MOD11=5冲突(5+1)MOD11=6冲突(5+2)MOD11=7冲突(5+3)MOD11=8插入38601729012345678910二：用二次探测法解决冲突MOD11=5冲突(5+12)MOD11=6冲突(5+(-12))MOD11=4插入38601729012345678910三：伪随机探测法解决冲突取伪随机数列为9,则38MOD11=5冲突(5+9)MOD11=3插入⑵再哈希法Hi=RHi(key)i=1,2,…,kRhi均是不同的哈希函数，既在同义词产生地址冲突时计算机另一个哈希函数地址，直到冲突不再发生。⑶链地址法思想：将具有相同hash函数值(hash地址)的元素放在同一个链表中例：已知一组关键字为(19,14,23,01,68,11,10,55),则按哈希函数H(key)=keyMOD13和链地址