下一页
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学计算机教学实验中
心
第 6单元
查找
下一页
上一页
停止放映
第 2 页
上节内容提要 —— 图
– 基本概念
? 有向图、无向图、边、弧、弧头、弧尾、顶点、邻
接点 （有向、无向不同）,度、入度、出度、子图、生成
树、连通图、连通分量、强连通图、权、网、
– 存储结构及实现
? 邻接矩阵、邻接表（对有向、无向图不同）
– 遍历及其它操作
? 深度优先、广度优先遍历
– 应 用
– 最小生成树（ Prim算法,Kruskal算法）,拓扑排序
– 二叉排序树的生成、查找和打印 （有完整程序）,
– Huffman树 (带权路径最短的二叉树 )与 Huffman编码
– 最短路径
下一页
第 6单元
第 3章 查找和排序
查找
下一页
上一页
停止放映
第 4 页
一、查找的基本概念
? 1.查找 就是在给定的 DS中找出满足某种条件
的结点；若存在这样的结点, 查找成功；否
则, 查找失败 。 （ 找 ）
? 2.查找表 是一组待查数据元素的集合 。 待找
? 3.静态查找 是仅仅进行查询和检索操作, 不
改变查找表中数据元素间的逻辑关系的查找 。
（ 不改变元素关系 ）
? 4.动态查找 是除了进行查询和检索操作外, 还对
查找表进行插入, 删除操作的查找, 动态地改变查
找表中数据元素之间的逻辑关系 。 改变元素关系
下一页
上一页
停止放映
第 5 页
平均查找长度
? 5,平均查找长度 （ ASL-Average Search
Length） （ 比较次数 ）
在查找过程中, 要对每个结点记录中的关键字进行
反复比较, 以确定其位置 。 因此, 与关键字进行比
较的平均次数, 就称为 平均查找长度 。 是用来评价
算法好坏的一个依据 。 (算法的评价 )
? 对含有 n个数据元素的查找表, 查找成功时的平均
查找长度为,ASL = ? Pi* Cin
i=1
? Pi = 1
i=1
n
其中,Pi 为查找表中第 i个数据元素的概率, 且
Ci为查找第 i个数据元素时需比较的次数 。
Ci随查找过程及 DS的不同而各异 。 （ Ci与方法和结构有关 ）
下一页
上一页
停止放映
第 6 页
二、主要查找算法
?顺序查找
?折半查找
?分块查找
?树表查找
?哈希查找
下一页
上一页
停止放映
第 7 页
1、顺序查找
? (1)算法思想,
从第 1个元素到最后 1个元素, 逐个进行比
较 。
? (2)特点：
? 最简单, 最普通的查找方法 。
? (3)适用范围 （ 查找表的存储结构 ）,
– 既适用于顺序存储结构
– 也适用于链式存储结构
下一页
上一页
停止放映
第 8 页
顺序查找的算法描述
? (4)操作步骤：
– step1 从第 1个元素开始查找；
– step2 用待查 关键字值与 各结点
（ 记录 ） 的关键字值逐个进行比较；
若找到相等的结点, 则查找成功；否
则, 查找失败 。
– 逐个比较
下一页
上一页
停止放映
第 9 页
顺序查找算法框图
i=0
seq_search(A,n,key)
A 待查表
n 元素个数
key 要找的值
i<n&&A[i]!=key?Y
N
查找 key的循环
显示“查找失败”
返回
开始
i++
A[i]==key? YN
显示“查找成功”
I<n，且还没找到，
循环
下一页
上一页
停止放映
第 10页
(5)顺序查找算法 3-1
seq_search(item,n,key )
int *item,n,key ;
{ int i=0 ;
while ( i < n && item[i] != key )
i++; /* 查找 key的循环 */
if (item[i]= = key )
{ printf(“查找成功 !\n”); return (i); }
else
{ printf(“查找失败 !\n”); return (-1);}
}
item 待查表
n 元素个数
key 要找的值
While中，有两个判断条件，改进一下，可以减少一半
下一页
上一页
停止放映
第 11 页
改进顺序查找算法框图
i=0 ； A[n]=key
s_search_a(A,n,key)
A[i]!=key?Y
N
查找 key的循环
显示“查找失败”
返回
开始
i++
i < n? YN
显示“查找成功”
设置哨兵
下一页
上一页
停止放映
第 12页
(6)顺序查找算法 3-2（改进算法）
seq_search_adv(item,n,key )
int *item,n,key ;
{ int i=0 ; //？ 哨兵的作用？
item[n]=key ; /* 设置哨兵 */
while ( item[i]!= key ) i++; /* 查找 key */
if ( i< n ) /* 如果 i = n,没找到 */
{ printf(“查找成功 !\n”); return (i); }
else
{ printf(“查找失败 !\n”); return (-1); }
}
注, 顺序查找算法中,执行频率最高的是 while语句,改
进后,可以节省近一半的时间 。
改进后与改进前的不同之处？
主要是取消了原来 I<n的判断
下一页
上一页
停止放映
第 13页
顺序查找算法主程序
#include,stdio.h” /*S_search.c*/
#define n 7
main()
｛ int key,loc=0;
int a[10]={43,15,21,37,2,5,82};
printf(“Input key:”);
scanf(“%d”,&key);
loc=s_search_adv(a,n,key);
if (loc >0)
printf(“loc=%d,key=%d\n”,loc,key);
} 示例
下一页
上一页
停止放映
第 14页
(7)算法评价
? 平均查找长度 ASL在等概率的情况下
? 一般情况下
i=1n
1
2
n+1n
i=1
n
ASL = ? Pi*Ci = ? (n-i+1) =
? 优点,
– 对结点的 逻辑次序 (不必有序 )和 存储结构 (顺序、链表均可）
无要求 ；
– 当序列中的记录 按访问概率, 基本有序, 或 N值较小时，是
较好的算法；
? 缺点,ASL较长
? 讨论：能否减少比较次数，以提高效率。
nASL ?
2
? 例如,…… 二分法等,（比较学号查找和姓名查找）
=O(n)
下一页
上一页
停止放映
第 15页
2、折半查找
? (1)思想：
将 有序序列 的 中点 设置为比较对象, 如果要找的
元素值小于该中点元素, 则将待查序列缩小为左
半部分, 否则为右半部分 。
即 通过一次比较, 将查找区间缩小一半 。
(2)特点：
? 二分查找是一种高效的查找方法 。 它可以明显减
少比较次数, 提高查找效率 。 但是, 二分查找的
先决条件是 查找表中的数据元素必须有序 。
下一页
上一页
停止放映
第 16页
(3)算法描述
? 算法步骤：
– step1 首先确定整个查找区间的中间位置,
mid = int(（ left + right ） / 2)
– step2 用待查关键字值与中间位置的关键字值进行
比较；
? 若相等, 则查找成功；
? 若大于, 则在后半区域继续进行二分查找；
? 若小于, 则在前半区域继续进行二分查找 。
– Step3 对确定的缩小区域再按二分公式, 重复上述
步骤；
– 最后, 得到结果,
? 要么, 查找成功, 要么, 查找失败 。
? 存储结构
– 用一维数组存放 。
下一页
上一页
停止放映
第 17页
折半查找算法举例
? 对给定数列（有序） { 3,5,11,17,21,23,28，
30,32,50}，共 10个数，按折半查找算法，查找关
键字值为 30的数据元素。 找 30：
第 1次,{ 3,5,11,17,21,23,28,30,32,50 }
mid1= （ 1+10） /2 = 5
第 2次,{ 23,28,30,32,50 }
mid2 = （ 6+10） /2 = 8
left rightmid
left rightmid
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=4 但 key=9 < 10,向左
key
4 8 9 10 11 13 19
3 4 5 6 7
high=7low=1
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=1,high=7
mid=int[(1+7)/2]=4
比较 key=9 < A[4]=10 向左
High=mid-1=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=4
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3（ mid-1）low=1
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=1,high=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=2key
4 8 9 10 11 13 19
3 4 5 6 7
high=3（ mid-1）low=1
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=1,high=3
mid=int[(1+3)/2]=2
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=2; 但 key=9 > 8,向右key
4 8 9 10 11 13 19
3 4 5 6 7
high=3（ mid-1）low=1
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=1,high=3
mid=int[(1+3)/2]=2
比较 key=9 > A[2]=8 向右
low=mid+1=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3
low=3（ mid+1）
mid=2
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=3,high=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=3;
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3
low=3
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=3,high=3
mid=int[(3+3)/2]=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=3; 但 key=9 中点值也为 9,找到
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3
low=3
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=3,high=3
mid=int[(3+3)/2]=3
比较 key=9 = A[3]=9
查找成功！
,once more》
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=4 但 key=5 < 10,向左
key
4 8 9 10 11 13 19
3 4 5 6 7
high=7low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=7
mid=int[(1+7)/2]=4
比较 key=5 < A[4]=10 向左
High=mid-1=3
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=4
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3（ mid-1）low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=3
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=2key
4 8 9 10 11 13 19
3 4 5 6 7
high=3low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=3
mid=int[(1+3)/2]=2
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=2; 但 key=5 < 8,向左key
4 8 9 10 11 13 19
3 4 5 6 7
high=3low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=3
mid=int[(1+3)/2]=2
比较 key=5 < A[2]=8 向左
high=mid-1=1
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=2key
4 8 9 10 11 13 19
3 4 5 6 7
high=1（ mid-1）
low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=1
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=1key
4 8 9 10 11 13 19
3 4 5 6 7
high=1
low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=1
mid=int[(1+1)/2]=1
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=1; 但 key=5 > 4,向右key
4 8 9 10 11 13 19
3 4 5 6 7
high=1
low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=1
mid=int[(1+1)/2]=1
比较 key=5 > A[4]=4 向右
low=mid+1=2
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=1; 但 key=5 > 4,向右key
4 8 9 10 11 13 19
3 4 5 6 7
high=1
low=2 （ mid+1）
失败条件,low > high; 处于间
隙中的键值导致这种情况！
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=2,high=1
LOW>HIGH,查找失败
,once more》
下一页
上一页
停止放映
第 33页
(4)(算法实现 )折半查找算法 3-3
bin_search ( item,n,key )
int *item,n,key; //n为元素个数
{ int left,right,mid; left=0; right = n-1;
while ( left ? right )
{
mid = ( left + right )/2 ; /* 计算中点位置 */
if ( key < item[mid])
right = mid - 1; /* 待查区间在左部 */
else if (key > item[mid])
left = mid + 1; /* 待查区间在右部 */
else{ printf (, Successful search\n”);
return mid ; /* 查找成功 */
}
printf(, Search failure \n”);
return -1; /* 查找失败 */
}
下一页
上一页
停止放映
第 34页
折半查找算法 3-3主程序
#define,stdio.h” /* b_search.c */
int num;
main( )
{ int res,key ;
int s[10]={1,3,5,7,9,11,13,15,17,19,21,23};
res=b_search(s,12,7);
if(res>0)
printf("res=%d,num=%d\n",res+1,num);
else
printf(“search failure\n”);
}
示例
下一页
上一页
停止放映
第 35页
(5)算法评价
? 优点, ASL ?; 即每经过一次比较,查找范围就
缩小一半。经 次比较就可以完成查找过程。
? 缺点,因 要求有序,所以对所有数据元素按大小排序
是非常费时的操作。另外，顺序存储结构的插入、删
除操作不大便利。
? 考虑：
– 能否一次比较抛弃更多的部分（即一次比较，使查
找范围缩得更小），以达到提高效率的目的；
– ……？
把两种方法（顺序查找和二分查找）结合
起来，即取 顺序查找简单 和 二分查找高效
之所长，来达到提高效率的目的？
下一页
上一页
停止放映
第 36页
3、分块查找
? 分块查找又称 索引顺序 查找, 这是顺序查
找的一种改进方法 。
? (1)分块,将 n个数据元素, 按块有序, 划
分为 m块 （ m ? n） 。 每一块中的结点不必
有序, 但块与块之间必须, 按块有序, ；
即第 1块中任一元素的关键字都必须小于
第 2块中任一元素的关键字；而第 2块中任
一元素又都必须小于第 3块中的任一元
素, …… 。 每个块中元素不一定是有序的 。
下一页
上一页
停止放映
第 37页
分块查找算法描述
? (2)算法描述,
? step1 先选取各块中的最大关键字构
成一个索引表；
? step2 查找分两个部分：
– 先对索引表进行 二分查找 或 顺序查
找,以确定待查记录在哪一块中；
– 在已确定的块中用顺序法进行查找。
下一页
上一页
停止放映
第 38页
分块查找数据描述
? 将查找表分成 3块，每块 3个元素
3 8 7 36 35 21 40 60
1 2 3 4 5 6 7 8 9
47
索引
顺序表
8 36 60
1 4 7
块最大关键字
块起始地址
索引表
块最大关键字有序
块内关键字无序（也可有序）
下一页
上一页
停止放映
第 39页
分块查找举例
? 有数列如下：
{ 22,12,13,9,8,33,42,44,38,24,48,60,58,75,47}
按, 块有序, 分三块,(22,12,13,9,8),(33,42,44,38,24),
(48,60,58,74,47)。选取每块中最大的关键字组成索引表
[22,44,74],查找 关键字值为 60的元素。
? 用二分法，确定在索引表中的位置为 mid=2,key值 60与 a[2]比
较,60>a[2],取第 3个块 ;在第 3块中用顺序法查找,比较两次,就可
以找出 60的元素来。
44
22
74
22
12
13
9
8
33
42
44
38
24
48
60
58
74
47
List[1]
List[2]
List[3]
11
12
13
14
15
1
6
11
下一页
上一页
停止放映
第 40页
索引表结构定义
#include "stdio.h"
typedef struct
{
int key; /*块中元素最大值 */
int link; /* 指向块入口地址 */
} index;
下一页
上一页
停止放映
第 41页
index_seq_search(index ls[],int s[],int m,int key,int l)
{
int i,j; (l=小 L)
i=0; //标记块号
while(i<m && key>ls[i].key)
i++; /* 确定在哪块查找 */
if(i>=m)
{ printf(,Searching failure\n");
return(-1);
}
else /* 否则, 查找成功处理
在第 I块中 */
(3)index_seq_search.c子函数
ls[] 索引表
S[] 待查表
M 块数
key 要找的值
l 块长度
下一页
上一页
停止放映
第 42页
分块查找子函数（续）
{ j=ls[i].link; /* 块入口地址 */
while (key !=s[j] && (j-ls[i].link)<l) j++;
if(key==s[j]&&(j-ls[i].link)<l)/*查找成功 */
{ printf("Successful search\n”）；
LOC(s[%2d])=%d\n",j,s[j]);
return(j); //(l=小 L)
}
else /* 查找失败 */
{ printf("Searching failure\n");
return(-1);
}
}
} /* 结束 */
下一页
上一页
停止放映
第 43页
分块查找主函数
main() /* INDEX_SE.c */
{
index ls[5]={ 14,0,34,5,66,10,85,15,100,20} ;
int a[]={8,4,3,2,14,34,20,17,28,29,58,61,59,66,48,
81,80,79,83,69,89,100,96,86,87}; int i,j=0,key;
for(i=0;i<25;i++)
{ if (j==0) printf("{ ");
if (j==5) { printf(" }"); j=0; printf(" {"); }
printf("%4d",a[i]); j++;
}
printf(" } \n");
printf("Enter key,");
scanf("%d",&key);
index_seq_search(ls,a,25,key,5);
}
示例
下一页
上一页
停止放映
第 44页
(4)算法评价
? 设索引表使用二分法，则有：
其中,n为表长,S为块长（假设各块长度相等）。
? 优点：
插入、删除操作方便；只要找到对应的块，在块中
任意位置操作均可。
? 缺点：
索引表增加了辅助存储空间。
注,索引表在数据库系统中广泛使用。
? 还有什么方法吗？
树表查找
下一页
上一页
停止放映
第 45页
4、树表（二叉排序树）查找
? (1)背景
? 前三种查找方法各有千秋
? 二分法查找效率高,
? 顺序法可以采用链表存储结构, 操作灵活 。
? 鱼与熊掌要兼得
? 但最好是既有二分法的高效率, 又有链表灵活
性的查找方法 。
? 解决之道：二叉排序树
? 就是将数据元素组织成二叉树形式, 以达到与
二分法相同的查找效率, 而又具有链表的插入,
删除操作的灵活性 。
下一页
上一页
停止放映
第 46页
(2)二叉排序树查找（算法 3-4）
? step1 首先建立起二叉排序树 。
? step2 将待查关键字值与树根结点进行比较,
若相等, 查找成功；
? step3 否则根据比较结果确定查找路径：
– 若小于根结点的关键字值, 则与左子树的
根结点的关键字值进行比较；
– 若大于等于根结点的关键字值, 则与右子
树的根结点的关键字值进行比较 。
? step4 重复上述步骤, 直到 要么找到, 查找成
功；要么找不到, 查找失败 。
下一页
上一页
停止放映
第 47页
(3)存储结构描述
二叉排序树结点结构：
struct tree {
char info； //结点
struct tree *left； //左子
struct tree *right； //右子
}
下一页
上一页
停止放映
第 48页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Empty btree\n”);return root; }
while(root->info!=key) /* 查找 key 的循环 */
{ if(key<root->info)
root=root->left; /* 沿左路查找 */
else
root=root->right; /* 沿右路查找 */
if(root= =0) /* 到叶结点也没找到 */
{ printf(“Search Failure\n”); break ; }
}
if (root !=0) /* 查找成功 */
printf(“Successful search\n key=%c\n”,root->info);
return root ;
}
(4)查询 二叉排序树程序
下一页
上一页
停止放映
第 49页
(5)算法评价
? 二叉排序树查找的 ASL ? 。 若其平衡特性
较好的话, ASL与折半查找相同 。
? 二叉排序树是动态生成的, 其特性随插入结点的
先后次序的不同而改变, 为防止其蜕化为单枝树,
要进行 平衡化处理 。
? 二叉排序树因采用链表结构, 需要辅助存储空间 。
? 上述方法都是建立比较基础上的, 能不能通过某
种算法, 直接确定关键元素的位置呢？
? （ 更上一层楼 ）
下一页
上一页
停止放映
第 50页
5、哈希（ hash）查找
? (1)简介
? 哈希查找也称为 散列查找 。 它不同于前面介绍
的几种查找方法 。 上述方法都是把查找建立在
比较的基础上, 而哈希查找则是 通过计算存储
地址 的方法进行 查找 的 。
? 计算是计算机的特点之一, 因此, 建立在计算
基础上的哈希查找是一种快速查找方法 。
下一页
上一页
停止放映
第 51页
（ 2）哈希查找的基本概念
? 哈希表 由 哈希函数 的值组成的表 。 哈希查找是
建立在哈希表的基础上, 它是线性表的一种重要
存储方式和检索方法 。 在哈希表中可以实现对数
据元素的快速检索 。
? 哈希函数 哈希表中元素是由哈希函数确定的 。
将数据元素的关键字 K作为自变量, 通过一定的
函数关系 （ 称为哈希函数 ）, 计算出的值, 即为
该元素的存储地址 。 表示为：
Addr = H（ key） 这个函数就是哈希函数
? 建立哈希函数的原则
– 均匀性 H（ key） 的值均匀分布在哈希表中；
– 简单 以提高地址计算的速度 。
（位置均匀，计算简单）
下一页
上一页
停止放映
第 52页
（ 3）哈希函数常用的构造方法
? 数字分析法
? 平方取中法
? 折叠法
? 除留余数法 （ 求模取余法 ）
? 直接定址法
下一页
上一页
停止放映
第 53页
（ a）,数字分析法
? 思想,当关键字的位数比存储区地址码位数多时,
可合理 选择关键字的某几位组成的哈希地址 。
? （ 有前提 ）
? 选取的原则,尽量避免计算出的地址有冲突 。
? （ 最好单调 ）
? 举例,学校的电话号码是 7位十进制数, 学校的
程控交换机是 10000门 。 但经分析不难得出：
XXXX
266 XXXX
XXXX
前 3位是相同的, 后四位不同, 这样可以用四位
数表示交大不同的电话 。
H（ KEY） = Right（ telenum,4） //（ 取后四位, 不会重 ）
下一页
上一页
停止放映
第 54页
(b).平方取中法
? 思想,取关键字平方后的中间几位为哈希
地址 。
? 这是一种较常用的构造哈希函数的方法 。
通常在选定哈希函数时不知道关键字的全
部情况, 取其中的哪几位也不一定合适,
在这种情况下, 取一个数平方后的中间几
位数作哈希地址 。 取的位数由表长决定 。
? 例如, 3288,平方后是, 10810944”,取后
4位为哈希地址, 即, 0944”。
下一页
上一页
停止放映
第 55页
(c).折叠法
? 思想,将关键字分割成位数相同的几部分 （ 最后一部分的位
数可以不同 ）, 然后取这几部分的叠加和 （ 舍去进位 ） 作为
哈希地址 。
? 适用,关键字位数很多, 且每一位上数字分布大致均匀时,
可采用折叠法 。
? 举例,某资料室藏书近 万册 。 采用国际标准图书编号
（ ISBN）, 每个编号 10位 十进制 数 字 。 可用折叠法构造一个
4位数的哈希函数 。
例如,书号为,0 - 4 4 2 - 2 0 5 8 6 - 4
5 8 6 4
4 2 2 0 H（ key） = 0088
0 4+）
1 0 0 8 8
下一页
上一页
停止放映
第 56页
(d).除留余数法（求模取余法）
? 思想,取关键字被某个不大于哈希表表长 m的数 p除后
所得余数为哈希地址 。
H（ key） = key MOD p (p<=m)
这是一种最简单, 也是最常用的构造哈希函数的方法 。
? 举例, 32834872, 哈希表长为 4位十进制数 。
P值可取小于 9999的数, 例如, 取 5000；
H（ KEY） = 32834872 MOD 5000 = 4872
? 经验 得知,通常选 p为小于哈希表长的最大素数 。
理由：
? 设 key 值都为奇数，选 p 为偶数；则 H(key) = key MOD p
,结果为奇数，一半单元被浪费掉。
? 设 key 值都为 5 的倍数，选 p 为 95；则 H(key) = key MOD
p, 结果为,0,5,10,15,…… 90奇数。 4/5 的单元被浪费掉
。
下一页
上一页
停止放映
第 57页
(e).直接定址法
? 思想,取关键字或关键字的某个线性函数值为哈希
地址, 即：
H（ key） = key
H（ key） = a * key + b （ a,b为常数 ）
? 例如, 在 1~100岁的人口统计表中, 年龄作为关
键字, 哈希函数取关键字本身 。
? 再如, 解放后出生人口统计表中, 年份作为关键
字, 哈希函数取为：
H（ key） = key +（ -1948）
地址
年份
人数
01 02 42
1949 1950 1990
…..
…..
43
1991
3000 3500 2500 2300…..
下一页
上一页
停止放映
第 58页
(4)冲突及冲突处理
由于哈希函数是一个压缩映象, 因此, 在一般情况
下, 很容易产生, 冲突, 现象
? 在哈希元素 （ 地址 ） 求解过程中, 不同关键字值对
应到同一个存储地址的现象称为冲突 。 即关键字 K1
? K2,但哈希函数值 H（ K1） = H（ K2） 。
? 均匀的哈希函数可以减少冲突, 但不能避免冲突 。
发生冲突后, 必须解决；也即必须寻找下一个可用
地址 。
? 处理冲突是建立哈希表过程中不可缺少的一部分 。
? 处理冲突有两种方法：
– 开放地址法
– 链地址法
下一页
上一页
停止放映
第 59页
（ a）处理冲突 —— 开放地址法
? 当发生地址冲突后, 求解下一个地址 用
Hi =( H（ key） +di） MOD m
i=1,2,…,k(k ? m-1)
其中, H(key)为哈希函数,m为哈希表长度,di为增
量序列 。 增量序列的不同取法, 又构成不同的开放
地址法 。
? 线性探测再散列
di=1,2,…,m-1
? 二次探测再散列
di=12,-12,22,-22,…,+k2,-k2(k ? m/2)
下一页
上一页
停止放映
第 60页
(b)处理冲突 —— 链地址法
? 当发生地址冲突后,将所有函数
值相同的记录连成一个单链表 。
0
1
2
3
4
5
6
7
8
9
∧
∧
∧
∧
∧
∧
∧
∧
∧
K1 K2 K3 ∧
K4 K5 K6 ∧
同义链，同一散列地址。
同义链，同一散列地址。
下一页
上一页
停止放映
第 61页
(5) 哈希查找操作步骤
? 用给定的哈希函数构造哈希表
? 根据选择的冲突处理方法解决地
址冲突
? 在哈希表的基础上执行哈希查找
下一页
上一页
停止放映
第 62页
(a)建立哈希表
? 建立哈希表操作步骤,
– step1 取数据元素的关键字 key,计算其哈希函
数值 （ 地址 ） 。 若该地址对应的存储空间还没有
被占用, 则将该元素存入；否则执行 step2解决
冲突 。
– step2 根据选择的冲突处理方法, 计算关键字
key的下一个存储地址 。 若下一个存储地址仍被
占用, 则继续执行 step2,直到找到能用的存储
地址为止 。
下一页
上一页
停止放映
第 63页
举例
? 对给定数列 { 22,41,53,46,30,13,1,67 },建立哈希表 。 表长
取 9,即 [0~8]。 哈希函数设定为, H(key) = key MOD 8,用 线
性探测 解决冲突 Hi=(H(key)+di) MOD m,di=1,2,…,m-1。
? 取 22,计算 H（ 22） =22 mod 8 = 6,该地址空, 可用；
? 取 41,计算 H（ 41） =41 mod 8 = 1,该地址空, 可用；
0 1 2 3 4 5 6 7 8
22
22
0 1 2 3 4 5 6 7 8
41
比较次数,1 1
下一页
上一页
停止放映
第 64页
举例（续一）
? 取 53，计算 H（ 53） = 53 mod 8 = 5，该地址空，可用；
? 取 46，计算 H（ 46） = 6，该地址冲突，用线性探测法计算下一个
可用地址 Hi=（ 6+1） MOD 8 = 7，
该地址空，可用；
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
0 1 2 3 4 5 6 7 8
比较次数,1 1 1
比较次数,1 1 1 2
下一页
上一页
停止放映
第 65页
举例（续二）
? 取 30，计算 H（ 30） = 6，该地址冲突，用线性探测
法计算下一个可用地址 Hi=（ 6+1） MOD 8 = 7，
该地址冲突，再用线性探测法计算下一个可用地址；
Hi=0，地址空，可用；
? 取 13，计算 H（ 13） = 5，依法解决冲突，得出：
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
0 1 2 3 4 5 6 7 8
比较次数,3 1 1 1 2
比较次数,3 1 6 1 1 2
4630
30 13
下一页
上一页
停止放映
第 66页
举例（续三）
? 取 1，计算 H（ 1） = 1，该地址冲突，解决冲突可得；
? 取 67，计算 H（ 67） = 3，冲突，解决冲突，得出：
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
4630
30
13
比较次数,3 1 6 3 1 1 2
1
13 1 67
比较次数,3 1 6 3 2 1 1 2
0 1 2 3 4 5 6 7 8
下一页
上一页
停止放映
第 67页
(b)哈希查找
哈希查找的过程和建立哈希表的过程是一致的 。
设哈希表为 HST[0~M-1],哈希函数取 H（ key）, 解
决冲突的方法为 R（ x）, 则哈希查找步骤为：
– Step1 对给定 k值, 计算哈希地址 Di=H（ k） ；
若 HST[i]为空, 则查找失败；若 HST[i]=k,则查
找成功；否则, 执行 step2（ 处理冲突 ） 。
– Step2 重复计算处理冲突的下一个存储地址
Dk=R （ Dk-1 ）, 直到 HST[Dk] 为空, 或
HST[Dk}=k为止 。
若 HST[Dk]=K,则查找成功, 否则查找失败 。
下一页
上一页
停止放映
第 68页
查找举例
以上述哈希表为例 。 哈希函数为 H(key)=key MOD 8,
设有数列 {22,41,53,46,30,13,1,67},用线性探测法解决
冲突,建立的哈希的表为,
平均查找长度 ASL= (3+1+6+3+2+1+1+2)=
? 查找 key = 67 比较两次找到,查找成功 ;
? 查找 key = 21 比较 8次找不到,查找失败 。
？ 怎样删除哈希表中的一个元素？
0 1 2 3 4 5 6 7 8
比较次数,3 1 6 3 2 1 1 2
2241 53 4630 13 1 67
8
1
8
19
下一页
上一页
停止放映
第 69页
链地址法处理冲突
? 以上述数列为例, 产生的哈希表为：
H(41)=H(1)=1
H(67)=3
H(53)=H(13)=5
H(22)=H(46)=H(30)=6
1
2
3
4
5
6
7
41 1 ^
46
13 ^
30 ^22
^
53
^
^
^
67
下一页
上一页
停止放映
第 70页
6.平均查找长度的计算举例
? P100
? 折半查找判定树
下一页
上一页
停止放映
第 71页
作业、思考题
第 3章
思考题, p112 第 2,3,5~7,11题
作 业, p113 第 13题
?欢迎参加, 软件基础, 课程的学习
?网 址,http,//ctec.xjtu.edu.cn
?课件地址, ftp,//ctec.xjtu.edu.cn/teacher
http://202.117.35.70/~studyhard/
?E-mail地址, xjtuzhao@sina.com
?答 疑,星期五 晚 7,00～ 9,00
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学计算机教学实验中
心
第 6单元
查找
下一页
上一页
停止放映
第 2 页
上节内容提要 —— 图
– 基本概念
? 有向图、无向图、边、弧、弧头、弧尾、顶点、邻
接点 （有向、无向不同）,度、入度、出度、子图、生成
树、连通图、连通分量、强连通图、权、网、
– 存储结构及实现
? 邻接矩阵、邻接表（对有向、无向图不同）
– 遍历及其它操作
? 深度优先、广度优先遍历
– 应 用
– 最小生成树（ Prim算法,Kruskal算法）,拓扑排序
– 二叉排序树的生成、查找和打印 （有完整程序）,
– Huffman树 (带权路径最短的二叉树 )与 Huffman编码
– 最短路径
下一页
第 6单元
第 3章 查找和排序
查找
下一页
上一页
停止放映
第 4 页
一、查找的基本概念
? 1.查找 就是在给定的 DS中找出满足某种条件
的结点；若存在这样的结点, 查找成功；否
则, 查找失败 。 （ 找 ）
? 2.查找表 是一组待查数据元素的集合 。 待找
? 3.静态查找 是仅仅进行查询和检索操作, 不
改变查找表中数据元素间的逻辑关系的查找 。
（ 不改变元素关系 ）
? 4.动态查找 是除了进行查询和检索操作外, 还对
查找表进行插入, 删除操作的查找, 动态地改变查
找表中数据元素之间的逻辑关系 。 改变元素关系
下一页
上一页
停止放映
第 5 页
平均查找长度
? 5,平均查找长度 （ ASL-Average Search
Length） （ 比较次数 ）
在查找过程中, 要对每个结点记录中的关键字进行
反复比较, 以确定其位置 。 因此, 与关键字进行比
较的平均次数, 就称为 平均查找长度 。 是用来评价
算法好坏的一个依据 。 (算法的评价 )
? 对含有 n个数据元素的查找表, 查找成功时的平均
查找长度为,ASL = ? Pi* Cin
i=1
? Pi = 1
i=1
n
其中,Pi 为查找表中第 i个数据元素的概率, 且
Ci为查找第 i个数据元素时需比较的次数 。
Ci随查找过程及 DS的不同而各异 。 （ Ci与方法和结构有关 ）
下一页
上一页
停止放映
第 6 页
二、主要查找算法
?顺序查找
?折半查找
?分块查找
?树表查找
?哈希查找
下一页
上一页
停止放映
第 7 页
1、顺序查找
? (1)算法思想,
从第 1个元素到最后 1个元素, 逐个进行比
较 。
? (2)特点：
? 最简单, 最普通的查找方法 。
? (3)适用范围 （ 查找表的存储结构 ）,
– 既适用于顺序存储结构
– 也适用于链式存储结构
下一页
上一页
停止放映
第 8 页
顺序查找的算法描述
? (4)操作步骤：
– step1 从第 1个元素开始查找；
– step2 用待查 关键字值与 各结点
（ 记录 ） 的关键字值逐个进行比较；
若找到相等的结点, 则查找成功；否
则, 查找失败 。
– 逐个比较
下一页
上一页
停止放映
第 9 页
顺序查找算法框图
i=0
seq_search(A,n,key)
A 待查表
n 元素个数
key 要找的值
i<n&&A[i]!=key?Y
N
查找 key的循环
显示“查找失败”
返回
开始
i++
A[i]==key? YN
显示“查找成功”
I<n，且还没找到，
循环
下一页
上一页
停止放映
第 10页
(5)顺序查找算法 3-1
seq_search(item,n,key )
int *item,n,key ;
{ int i=0 ;
while ( i < n && item[i] != key )
i++; /* 查找 key的循环 */
if (item[i]= = key )
{ printf(“查找成功 !\n”); return (i); }
else
{ printf(“查找失败 !\n”); return (-1);}
}
item 待查表
n 元素个数
key 要找的值
While中，有两个判断条件，改进一下，可以减少一半
下一页
上一页
停止放映
第 11 页
改进顺序查找算法框图
i=0 ； A[n]=key
s_search_a(A,n,key)
A[i]!=key?Y
N
查找 key的循环
显示“查找失败”
返回
开始
i++
i < n? YN
显示“查找成功”
设置哨兵
下一页
上一页
停止放映
第 12页
(6)顺序查找算法 3-2（改进算法）
seq_search_adv(item,n,key )
int *item,n,key ;
{ int i=0 ; //？ 哨兵的作用？
item[n]=key ; /* 设置哨兵 */
while ( item[i]!= key ) i++; /* 查找 key */
if ( i< n ) /* 如果 i = n,没找到 */
{ printf(“查找成功 !\n”); return (i); }
else
{ printf(“查找失败 !\n”); return (-1); }
}
注, 顺序查找算法中,执行频率最高的是 while语句,改
进后,可以节省近一半的时间 。
改进后与改进前的不同之处？
主要是取消了原来 I<n的判断
下一页
上一页
停止放映
第 13页
顺序查找算法主程序
#include,stdio.h” /*S_search.c*/
#define n 7
main()
｛ int key,loc=0;
int a[10]={43,15,21,37,2,5,82};
printf(“Input key:”);
scanf(“%d”,&key);
loc=s_search_adv(a,n,key);
if (loc >0)
printf(“loc=%d,key=%d\n”,loc,key);
} 示例
下一页
上一页
停止放映
第 14页
(7)算法评价
? 平均查找长度 ASL在等概率的情况下
? 一般情况下
i=1n
1
2
n+1n
i=1
n
ASL = ? Pi*Ci = ? (n-i+1) =
? 优点,
– 对结点的 逻辑次序 (不必有序 )和 存储结构 (顺序、链表均可）
无要求 ；
– 当序列中的记录 按访问概率, 基本有序, 或 N值较小时，是
较好的算法；
? 缺点,ASL较长
? 讨论：能否减少比较次数，以提高效率。
nASL ?
2
? 例如,…… 二分法等,（比较学号查找和姓名查找）
=O(n)
下一页
上一页
停止放映
第 15页
2、折半查找
? (1)思想：
将 有序序列 的 中点 设置为比较对象, 如果要找的
元素值小于该中点元素, 则将待查序列缩小为左
半部分, 否则为右半部分 。
即 通过一次比较, 将查找区间缩小一半 。
(2)特点：
? 二分查找是一种高效的查找方法 。 它可以明显减
少比较次数, 提高查找效率 。 但是, 二分查找的
先决条件是 查找表中的数据元素必须有序 。
下一页
上一页
停止放映
第 16页
(3)算法描述
? 算法步骤：
– step1 首先确定整个查找区间的中间位置,
mid = int(（ left + right ） / 2)
– step2 用待查关键字值与中间位置的关键字值进行
比较；
? 若相等, 则查找成功；
? 若大于, 则在后半区域继续进行二分查找；
? 若小于, 则在前半区域继续进行二分查找 。
– Step3 对确定的缩小区域再按二分公式, 重复上述
步骤；
– 最后, 得到结果,
? 要么, 查找成功, 要么, 查找失败 。
? 存储结构
– 用一维数组存放 。
下一页
上一页
停止放映
第 17页
折半查找算法举例
? 对给定数列（有序） { 3,5,11,17,21,23,28，
30,32,50}，共 10个数，按折半查找算法，查找关
键字值为 30的数据元素。 找 30：
第 1次,{ 3,5,11,17,21,23,28,30,32,50 }
mid1= （ 1+10） /2 = 5
第 2次,{ 23,28,30,32,50 }
mid2 = （ 6+10） /2 = 8
left rightmid
left rightmid
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=4 但 key=9 < 10,向左
key
4 8 9 10 11 13 19
3 4 5 6 7
high=7low=1
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=1,high=7
mid=int[(1+7)/2]=4
比较 key=9 < A[4]=10 向左
High=mid-1=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=4
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3（ mid-1）low=1
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=1,high=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=2key
4 8 9 10 11 13 19
3 4 5 6 7
high=3（ mid-1）low=1
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=1,high=3
mid=int[(1+3)/2]=2
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=2; 但 key=9 > 8,向右key
4 8 9 10 11 13 19
3 4 5 6 7
high=3（ mid-1）low=1
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=1,high=3
mid=int[(1+3)/2]=2
比较 key=9 > A[2]=8 向右
low=mid+1=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3
low=3（ mid+1）
mid=2
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=3,high=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=3;
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3
low=3
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=3,high=3
mid=int[(3+3)/2]=3
下一页
上一页
停止放映
折半查找演示（ 1）
0 1 2
mid=3; 但 key=9 中点值也为 9,找到
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3
low=3
在有序数 4,8,9,10,11,13,19中查找 9
初始,low=3,high=3
mid=int[(3+3)/2]=3
比较 key=9 = A[3]=9
查找成功！
,once more》
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=4 但 key=5 < 10,向左
key
4 8 9 10 11 13 19
3 4 5 6 7
high=7low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=7
mid=int[(1+7)/2]=4
比较 key=5 < A[4]=10 向左
High=mid-1=3
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=4
key
4 8 9 10 11 13 19
3 4 5 6 7
high=3（ mid-1）low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=3
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=2key
4 8 9 10 11 13 19
3 4 5 6 7
high=3low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=3
mid=int[(1+3)/2]=2
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=2; 但 key=5 < 8,向左key
4 8 9 10 11 13 19
3 4 5 6 7
high=3low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=3
mid=int[(1+3)/2]=2
比较 key=5 < A[2]=8 向左
high=mid-1=1
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=2key
4 8 9 10 11 13 19
3 4 5 6 7
high=1（ mid-1）
low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=1
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=1key
4 8 9 10 11 13 19
3 4 5 6 7
high=1
low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=1
mid=int[(1+1)/2]=1
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=1; 但 key=5 > 4,向右key
4 8 9 10 11 13 19
3 4 5 6 7
high=1
low=1
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=1,high=1
mid=int[(1+1)/2]=1
比较 key=5 > A[4]=4 向右
low=mid+1=2
下一页
上一页
停止放映
折半查找演示（ 2）
0 1 2
mid=1; 但 key=5 > 4,向右key
4 8 9 10 11 13 19
3 4 5 6 7
high=1
low=2 （ mid+1）
失败条件,low > high; 处于间
隙中的键值导致这种情况！
在有序数 4,8,9,10,11,13,19中查找 5
初始,low=2,high=1
LOW>HIGH,查找失败
,once more》
下一页
上一页
停止放映
第 33页
(4)(算法实现 )折半查找算法 3-3
bin_search ( item,n,key )
int *item,n,key; //n为元素个数
{ int left,right,mid; left=0; right = n-1;
while ( left ? right )
{
mid = ( left + right )/2 ; /* 计算中点位置 */
if ( key < item[mid])
right = mid - 1; /* 待查区间在左部 */
else if (key > item[mid])
left = mid + 1; /* 待查区间在右部 */
else{ printf (, Successful search\n”);
return mid ; /* 查找成功 */
}
printf(, Search failure \n”);
return -1; /* 查找失败 */
}
下一页
上一页
停止放映
第 34页
折半查找算法 3-3主程序
#define,stdio.h” /* b_search.c */
int num;
main( )
{ int res,key ;
int s[10]={1,3,5,7,9,11,13,15,17,19,21,23};
res=b_search(s,12,7);
if(res>0)
printf("res=%d,num=%d\n",res+1,num);
else
printf(“search failure\n”);
}
示例
下一页
上一页
停止放映
第 35页
(5)算法评价
? 优点, ASL ?; 即每经过一次比较,查找范围就
缩小一半。经 次比较就可以完成查找过程。
? 缺点,因 要求有序,所以对所有数据元素按大小排序
是非常费时的操作。另外，顺序存储结构的插入、删
除操作不大便利。
? 考虑：
– 能否一次比较抛弃更多的部分（即一次比较，使查
找范围缩得更小），以达到提高效率的目的；
– ……？
把两种方法（顺序查找和二分查找）结合
起来，即取 顺序查找简单 和 二分查找高效
之所长，来达到提高效率的目的？
下一页
上一页
停止放映
第 36页
3、分块查找
? 分块查找又称 索引顺序 查找, 这是顺序查
找的一种改进方法 。
? (1)分块,将 n个数据元素, 按块有序, 划
分为 m块 （ m ? n） 。 每一块中的结点不必
有序, 但块与块之间必须, 按块有序, ；
即第 1块中任一元素的关键字都必须小于
第 2块中任一元素的关键字；而第 2块中任
一元素又都必须小于第 3块中的任一元
素, …… 。 每个块中元素不一定是有序的 。
下一页
上一页
停止放映
第 37页
分块查找算法描述
? (2)算法描述,
? step1 先选取各块中的最大关键字构
成一个索引表；
? step2 查找分两个部分：
– 先对索引表进行 二分查找 或 顺序查
找,以确定待查记录在哪一块中；
– 在已确定的块中用顺序法进行查找。
下一页
上一页
停止放映
第 38页
分块查找数据描述
? 将查找表分成 3块，每块 3个元素
3 8 7 36 35 21 40 60
1 2 3 4 5 6 7 8 9
47
索引
顺序表
8 36 60
1 4 7
块最大关键字
块起始地址
索引表
块最大关键字有序
块内关键字无序（也可有序）
下一页
上一页
停止放映
第 39页
分块查找举例
? 有数列如下：
{ 22,12,13,9,8,33,42,44,38,24,48,60,58,75,47}
按, 块有序, 分三块,(22,12,13,9,8),(33,42,44,38,24),
(48,60,58,74,47)。选取每块中最大的关键字组成索引表
[22,44,74],查找 关键字值为 60的元素。
? 用二分法，确定在索引表中的位置为 mid=2,key值 60与 a[2]比
较,60>a[2],取第 3个块 ;在第 3块中用顺序法查找,比较两次,就可
以找出 60的元素来。
44
22
74
22
12
13
9
8
33
42
44
38
24
48
60
58
74
47
List[1]
List[2]
List[3]
11
12
13
14
15
1
6
11
下一页
上一页
停止放映
第 40页
索引表结构定义
#include "stdio.h"
typedef struct
{
int key; /*块中元素最大值 */
int link; /* 指向块入口地址 */
} index;
下一页
上一页
停止放映
第 41页
index_seq_search(index ls[],int s[],int m,int key,int l)
{
int i,j; (l=小 L)
i=0; //标记块号
while(i<m && key>ls[i].key)
i++; /* 确定在哪块查找 */
if(i>=m)
{ printf(,Searching failure\n");
return(-1);
}
else /* 否则, 查找成功处理
在第 I块中 */
(3)index_seq_search.c子函数
ls[] 索引表
S[] 待查表
M 块数
key 要找的值
l 块长度
下一页
上一页
停止放映
第 42页
分块查找子函数（续）
{ j=ls[i].link; /* 块入口地址 */
while (key !=s[j] && (j-ls[i].link)<l) j++;
if(key==s[j]&&(j-ls[i].link)<l)/*查找成功 */
{ printf("Successful search\n”）；
LOC(s[%2d])=%d\n",j,s[j]);
return(j); //(l=小 L)
}
else /* 查找失败 */
{ printf("Searching failure\n");
return(-1);
}
}
} /* 结束 */
下一页
上一页
停止放映
第 43页
分块查找主函数
main() /* INDEX_SE.c */
{
index ls[5]={ 14,0,34,5,66,10,85,15,100,20} ;
int a[]={8,4,3,2,14,34,20,17,28,29,58,61,59,66,48,
81,80,79,83,69,89,100,96,86,87}; int i,j=0,key;
for(i=0;i<25;i++)
{ if (j==0) printf("{ ");
if (j==5) { printf(" }"); j=0; printf(" {"); }
printf("%4d",a[i]); j++;
}
printf(" } \n");
printf("Enter key,");
scanf("%d",&key);
index_seq_search(ls,a,25,key,5);
}
示例
下一页
上一页
停止放映
第 44页
(4)算法评价
? 设索引表使用二分法，则有：
其中,n为表长,S为块长（假设各块长度相等）。
? 优点：
插入、删除操作方便；只要找到对应的块，在块中
任意位置操作均可。
? 缺点：
索引表增加了辅助存储空间。
注,索引表在数据库系统中广泛使用。
? 还有什么方法吗？
树表查找
下一页
上一页
停止放映
第 45页
4、树表（二叉排序树）查找
? (1)背景
? 前三种查找方法各有千秋
? 二分法查找效率高,
? 顺序法可以采用链表存储结构, 操作灵活 。
? 鱼与熊掌要兼得
? 但最好是既有二分法的高效率, 又有链表灵活
性的查找方法 。
? 解决之道：二叉排序树
? 就是将数据元素组织成二叉树形式, 以达到与
二分法相同的查找效率, 而又具有链表的插入,
删除操作的灵活性 。
下一页
上一页
停止放映
第 46页
(2)二叉排序树查找（算法 3-4）
? step1 首先建立起二叉排序树 。
? step2 将待查关键字值与树根结点进行比较,
若相等, 查找成功；
? step3 否则根据比较结果确定查找路径：
– 若小于根结点的关键字值, 则与左子树的
根结点的关键字值进行比较；
– 若大于等于根结点的关键字值, 则与右子
树的根结点的关键字值进行比较 。
? step4 重复上述步骤, 直到 要么找到, 查找成
功；要么找不到, 查找失败 。
下一页
上一页
停止放映
第 47页
(3)存储结构描述
二叉排序树结点结构：
struct tree {
char info； //结点
struct tree *left； //左子
struct tree *right； //右子
}
下一页
上一页
停止放映
第 48页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Empty btree\n”);return root; }
while(root->info!=key) /* 查找 key 的循环 */
{ if(key<root->info)
root=root->left; /* 沿左路查找 */
else
root=root->right; /* 沿右路查找 */
if(root= =0) /* 到叶结点也没找到 */
{ printf(“Search Failure\n”); break ; }
}
if (root !=0) /* 查找成功 */
printf(“Successful search\n key=%c\n”,root->info);
return root ;
}
(4)查询 二叉排序树程序
下一页
上一页
停止放映
第 49页
(5)算法评价
? 二叉排序树查找的 ASL ? 。 若其平衡特性
较好的话, ASL与折半查找相同 。
? 二叉排序树是动态生成的, 其特性随插入结点的
先后次序的不同而改变, 为防止其蜕化为单枝树,
要进行 平衡化处理 。
? 二叉排序树因采用链表结构, 需要辅助存储空间 。
? 上述方法都是建立比较基础上的, 能不能通过某
种算法, 直接确定关键元素的位置呢？
? （ 更上一层楼 ）
下一页
上一页
停止放映
第 50页
5、哈希（ hash）查找
? (1)简介
? 哈希查找也称为 散列查找 。 它不同于前面介绍
的几种查找方法 。 上述方法都是把查找建立在
比较的基础上, 而哈希查找则是 通过计算存储
地址 的方法进行 查找 的 。
? 计算是计算机的特点之一, 因此, 建立在计算
基础上的哈希查找是一种快速查找方法 。
下一页
上一页
停止放映
第 51页
（ 2）哈希查找的基本概念
? 哈希表 由 哈希函数 的值组成的表 。 哈希查找是
建立在哈希表的基础上, 它是线性表的一种重要
存储方式和检索方法 。 在哈希表中可以实现对数
据元素的快速检索 。
? 哈希函数 哈希表中元素是由哈希函数确定的 。
将数据元素的关键字 K作为自变量, 通过一定的
函数关系 （ 称为哈希函数 ）, 计算出的值, 即为
该元素的存储地址 。 表示为：
Addr = H（ key） 这个函数就是哈希函数
? 建立哈希函数的原则
– 均匀性 H（ key） 的值均匀分布在哈希表中；
– 简单 以提高地址计算的速度 。
（位置均匀，计算简单）
下一页
上一页
停止放映
第 52页
（ 3）哈希函数常用的构造方法
? 数字分析法
? 平方取中法
? 折叠法
? 除留余数法 （ 求模取余法 ）
? 直接定址法
下一页
上一页
停止放映
第 53页
（ a）,数字分析法
? 思想,当关键字的位数比存储区地址码位数多时,
可合理 选择关键字的某几位组成的哈希地址 。
? （ 有前提 ）
? 选取的原则,尽量避免计算出的地址有冲突 。
? （ 最好单调 ）
? 举例,学校的电话号码是 7位十进制数, 学校的
程控交换机是 10000门 。 但经分析不难得出：
XXXX
266 XXXX
XXXX
前 3位是相同的, 后四位不同, 这样可以用四位
数表示交大不同的电话 。
H（ KEY） = Right（ telenum,4） //（ 取后四位, 不会重 ）
下一页
上一页
停止放映
第 54页
(b).平方取中法
? 思想,取关键字平方后的中间几位为哈希
地址 。
? 这是一种较常用的构造哈希函数的方法 。
通常在选定哈希函数时不知道关键字的全
部情况, 取其中的哪几位也不一定合适,
在这种情况下, 取一个数平方后的中间几
位数作哈希地址 。 取的位数由表长决定 。
? 例如, 3288,平方后是, 10810944”,取后
4位为哈希地址, 即, 0944”。
下一页
上一页
停止放映
第 55页
(c).折叠法
? 思想,将关键字分割成位数相同的几部分 （ 最后一部分的位
数可以不同 ）, 然后取这几部分的叠加和 （ 舍去进位 ） 作为
哈希地址 。
? 适用,关键字位数很多, 且每一位上数字分布大致均匀时,
可采用折叠法 。
? 举例,某资料室藏书近 万册 。 采用国际标准图书编号
（ ISBN）, 每个编号 10位 十进制 数 字 。 可用折叠法构造一个
4位数的哈希函数 。
例如,书号为,0 - 4 4 2 - 2 0 5 8 6 - 4
5 8 6 4
4 2 2 0 H（ key） = 0088
0 4+）
1 0 0 8 8
下一页
上一页
停止放映
第 56页
(d).除留余数法（求模取余法）
? 思想,取关键字被某个不大于哈希表表长 m的数 p除后
所得余数为哈希地址 。
H（ key） = key MOD p (p<=m)
这是一种最简单, 也是最常用的构造哈希函数的方法 。
? 举例, 32834872, 哈希表长为 4位十进制数 。
P值可取小于 9999的数, 例如, 取 5000；
H（ KEY） = 32834872 MOD 5000 = 4872
? 经验 得知,通常选 p为小于哈希表长的最大素数 。
理由：
? 设 key 值都为奇数，选 p 为偶数；则 H(key) = key MOD p
,结果为奇数，一半单元被浪费掉。
? 设 key 值都为 5 的倍数，选 p 为 95；则 H(key) = key MOD
p, 结果为,0,5,10,15,…… 90奇数。 4/5 的单元被浪费掉
。
下一页
上一页
停止放映
第 57页
(e).直接定址法
? 思想,取关键字或关键字的某个线性函数值为哈希
地址, 即：
H（ key） = key
H（ key） = a * key + b （ a,b为常数 ）
? 例如, 在 1~100岁的人口统计表中, 年龄作为关
键字, 哈希函数取关键字本身 。
? 再如, 解放后出生人口统计表中, 年份作为关键
字, 哈希函数取为：
H（ key） = key +（ -1948）
地址
年份
人数
01 02 42
1949 1950 1990
…..
…..
43
1991
3000 3500 2500 2300…..
下一页
上一页
停止放映
第 58页
(4)冲突及冲突处理
由于哈希函数是一个压缩映象, 因此, 在一般情况
下, 很容易产生, 冲突, 现象
? 在哈希元素 （ 地址 ） 求解过程中, 不同关键字值对
应到同一个存储地址的现象称为冲突 。 即关键字 K1
? K2,但哈希函数值 H（ K1） = H（ K2） 。
? 均匀的哈希函数可以减少冲突, 但不能避免冲突 。
发生冲突后, 必须解决；也即必须寻找下一个可用
地址 。
? 处理冲突是建立哈希表过程中不可缺少的一部分 。
? 处理冲突有两种方法：
– 开放地址法
– 链地址法
下一页
上一页
停止放映
第 59页
（ a）处理冲突 —— 开放地址法
? 当发生地址冲突后, 求解下一个地址 用
Hi =( H（ key） +di） MOD m
i=1,2,…,k(k ? m-1)
其中, H(key)为哈希函数,m为哈希表长度,di为增
量序列 。 增量序列的不同取法, 又构成不同的开放
地址法 。
? 线性探测再散列
di=1,2,…,m-1
? 二次探测再散列
di=12,-12,22,-22,…,+k2,-k2(k ? m/2)
下一页
上一页
停止放映
第 60页
(b)处理冲突 —— 链地址法
? 当发生地址冲突后,将所有函数
值相同的记录连成一个单链表 。
0
1
2
3
4
5
6
7
8
9
∧
∧
∧
∧
∧
∧
∧
∧
∧
K1 K2 K3 ∧
K4 K5 K6 ∧
同义链，同一散列地址。
同义链，同一散列地址。
下一页
上一页
停止放映
第 61页
(5) 哈希查找操作步骤
? 用给定的哈希函数构造哈希表
? 根据选择的冲突处理方法解决地
址冲突
? 在哈希表的基础上执行哈希查找
下一页
上一页
停止放映
第 62页
(a)建立哈希表
? 建立哈希表操作步骤,
– step1 取数据元素的关键字 key,计算其哈希函
数值 （ 地址 ） 。 若该地址对应的存储空间还没有
被占用, 则将该元素存入；否则执行 step2解决
冲突 。
– step2 根据选择的冲突处理方法, 计算关键字
key的下一个存储地址 。 若下一个存储地址仍被
占用, 则继续执行 step2,直到找到能用的存储
地址为止 。
下一页
上一页
停止放映
第 63页
举例
? 对给定数列 { 22,41,53,46,30,13,1,67 },建立哈希表 。 表长
取 9,即 [0~8]。 哈希函数设定为, H(key) = key MOD 8,用 线
性探测 解决冲突 Hi=(H(key)+di) MOD m,di=1,2,…,m-1。
? 取 22,计算 H（ 22） =22 mod 8 = 6,该地址空, 可用；
? 取 41,计算 H（ 41） =41 mod 8 = 1,该地址空, 可用；
0 1 2 3 4 5 6 7 8
22
22
0 1 2 3 4 5 6 7 8
41
比较次数,1 1
下一页
上一页
停止放映
第 64页
举例（续一）
? 取 53，计算 H（ 53） = 53 mod 8 = 5，该地址空，可用；
? 取 46，计算 H（ 46） = 6，该地址冲突，用线性探测法计算下一个
可用地址 Hi=（ 6+1） MOD 8 = 7，
该地址空，可用；
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
0 1 2 3 4 5 6 7 8
比较次数,1 1 1
比较次数,1 1 1 2
下一页
上一页
停止放映
第 65页
举例（续二）
? 取 30，计算 H（ 30） = 6，该地址冲突，用线性探测
法计算下一个可用地址 Hi=（ 6+1） MOD 8 = 7，
该地址冲突，再用线性探测法计算下一个可用地址；
Hi=0，地址空，可用；
? 取 13，计算 H（ 13） = 5，依法解决冲突，得出：
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
0 1 2 3 4 5 6 7 8
比较次数,3 1 1 1 2
比较次数,3 1 6 1 1 2
4630
30 13
下一页
上一页
停止放映
第 66页
举例（续三）
? 取 1，计算 H（ 1） = 1，该地址冲突，解决冲突可得；
? 取 67，计算 H（ 67） = 3，冲突，解决冲突，得出：
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
4630
30
13
比较次数,3 1 6 3 1 1 2
1
13 1 67
比较次数,3 1 6 3 2 1 1 2
0 1 2 3 4 5 6 7 8
下一页
上一页
停止放映
第 67页
(b)哈希查找
哈希查找的过程和建立哈希表的过程是一致的 。
设哈希表为 HST[0~M-1],哈希函数取 H（ key）, 解
决冲突的方法为 R（ x）, 则哈希查找步骤为：
– Step1 对给定 k值, 计算哈希地址 Di=H（ k） ；
若 HST[i]为空, 则查找失败；若 HST[i]=k,则查
找成功；否则, 执行 step2（ 处理冲突 ） 。
– Step2 重复计算处理冲突的下一个存储地址
Dk=R （ Dk-1 ）, 直到 HST[Dk] 为空, 或
HST[Dk}=k为止 。
若 HST[Dk]=K,则查找成功, 否则查找失败 。
下一页
上一页
停止放映
第 68页
查找举例
以上述哈希表为例 。 哈希函数为 H(key)=key MOD 8,
设有数列 {22,41,53,46,30,13,1,67},用线性探测法解决
冲突,建立的哈希的表为,
平均查找长度 ASL= (3+1+6+3+2+1+1+2)=
? 查找 key = 67 比较两次找到,查找成功 ;
? 查找 key = 21 比较 8次找不到,查找失败 。
？ 怎样删除哈希表中的一个元素？
0 1 2 3 4 5 6 7 8
比较次数,3 1 6 3 2 1 1 2
2241 53 4630 13 1 67
8
1
8
19
下一页
上一页
停止放映
第 69页
链地址法处理冲突
? 以上述数列为例, 产生的哈希表为：
H(41)=H(1)=1
H(67)=3
H(53)=H(13)=5
H(22)=H(46)=H(30)=6
1
2
3
4
5
6
7
41 1 ^
46
13 ^
30 ^22
^
53
^
^
^
67
下一页
上一页
停止放映
第 70页
6.平均查找长度的计算举例
? P100
? 折半查找判定树
下一页
上一页
停止放映
第 71页
作业、思考题
第 3章
思考题, p112 第 2,3,5~7,11题
作 业, p113 第 13题
?欢迎参加, 软件基础, 课程的学习
?网 址,http,//ctec.xjtu.edu.cn
?课件地址, ftp,//ctec.xjtu.edu.cn/teacher
http://202.117.35.70/~studyhard/
?E-mail地址, xjtuzhao@sina.com
?答 疑,星期五 晚 7,00～ 9,00
