第9章查找案例.ppt

设哈希地址值为1～10。可以看到，K1和K5的哈希函数值相等，H(K1)=H(K5)=2，K2，K4，K6的哈希函数值相等，H(K2)=H(K4)= H(K6)=5。若采用链地址法处理冲突，图9-6所示为链地址法的示意图。 图9-6 链地址法示意图 从图9-6中可以看到，K1、K5发生冲突，组成哈希函数值为2的哈希链，而K2、K4、K6组成哈希函数值为5的哈希链。其中第一次存入的记录装在基本哈希表中，如K1、K3、K2、K6。 链地址法的算法如下： max=100； struct node { int key； char ch； struct node * next； } ht[max]； CHASH(ht，r) /* ht为基本哈希表，k为待查记录r的关键字值，n为哈希表的长度，j为表指针，h[k]为哈希函数 */ { j=h[k]； /* 计算哈希地址 */ if(ht[j]==k) /* 基本哈希表第j位有k，查找成功 */ puts(查找成功)； else if(ht[j]==0) { ht[j]=k； link[j]-next=NULL； } /* 找到基本哈希表的空位，装入待查找记录k */ else if(link[j]-next==NULL) /* 有冲突且只有基本哈希表一个记录 */ { p=malloc(sizeof[Lnode])； link[j]-next=p； p-key=k； p-next=NULL； } /* 成为哈希链的第一个记录 */ else { q=link[j] -next； while(( q-key!=k)(q-next!=NULL)) q=q-next； /* 查找哈希链中待查找记录k */ if(q-key==k) printf(查找成功)； else { p=malloc(sizeof(Lnode))； q-next=p； p-key=k； q-next=NULL； } /* 待查找记录k不在哈希链中，装入链尾 */ } } 9.5 各种查找方法的比较 对各种查找方法进行分析和比较，将有利于在实际应用中根据不同的要求选用适当的查找算法，提高查找的效率和程序运行速度。 综合本章所讨论的各种查找方法，可知每种方法都有一定的优点和存在相应的不足。 就顺序查找而言，其查找的效率很低，但是，由于顺序查找算法简单，对文件的结构没有任何要求，因此，在文件比较小，记录比较少的情况下，采用顺序查找是较好的。顺序查找的存储结构往往与线性表相关，具体表现为数组形式，这将有利于程序的实现。 折半查找实现的前提是查找的文件有序，因此只能用于顺序存储结构。折半查找的平均查找长度小，查找速度快。若文件中记录要经常变化，即进行插入和删除记录的操作，为了保持文件的有序性，文件就要不断进行调整，重新排序，这在一定程度上要降低查找速度。因此，对于不经常变动的有序文件，采用折半查找是比较理想的。 分块查找的平均查找长度介于顺序查找和折半查找之间。由于分块查找的主要结构形式是分块的，而且块之间是有序的，块内记录是无序的，因此，当表中记录有变化时，要调整相应块中的记录，从而减少整个文件的移动。分块查找的不足在于，实施查找之前首先要把记录或数据按结构分块，并建立块索引表。分块查找可用于顺序存储结构，也可用于链式存储结构。 二叉查找树的查找性能取决于二叉查找树的结构，若二叉查找树退化为单支二叉树，则其查找速度很慢，等同于链的顺序查找；若二叉查找树接近二叉平衡树，则查找速度最快，其速度等同于折半查找。而且在二叉查找树结构的基础上容易实现插入、删除记录。因此对经常变动的表，二叉查找树是非常理想的。但是，二叉查找树要占用一定的附加空间存放指针，在查找之前首先还要建立一棵二叉查找树。 哈希法是一种直接通过哈希函数计算地址的查