第11章查找 主「查找的基本概念 要)静态查找表 知 识动态查找表 点哈希表
第11章 查找 查找的基本概念 静态查找表 动态查找表 哈希表 主 要 知 识 点
111查找的基本概念 查找查询某个关键字是否在(数据元素集合)表中的过程。也 称作检索。 主关键字:能够惟一区分各个不同数据元素的关键字 次关键字通常不能惟一区分各个不同数据元素的关键字 查找成功:在数据元素集合中找到了要查找的数据元素 查找不成功:在数据元素集合中没有找到要查找的数据元素
11.1 查找的基本概念 查找:查询某个关键字是否在(数据元素集合）表中的过程。也 称作检索。 主关键字:能够惟一区分各个不同数据元素的关键字 次关键字:通常不能惟一区分各个不同数据元素的关键字 查找成功:在数据元素集合中找到了要查找的数据元素 查找不成功:在数据元素集合中没有找到要查找的数据元素
静态查找只查找,不改变数据元素集合内的数据元素 动态查找:既查找,又改变(增减)集合内的数据元素 静态查找表:静态查找时构造的存储结构 动态查找表动态查找时构造的存储结构 平均查找长度查找过程所需进行的关键字比较次数的平 均值,是衡量查找算法效率的最主要标准,其数学定 义为: ASL ∑ P XO
= = × n i ASL Pi C i 1 静态查找:只查找，不改变数据元素集合内的数据元素 动态查找:既查找，又改变（增减）集合内的数据元素 静态查找表:静态查找时构造的存储结构 动态查找表:动态查找时构造的存储结构 平均查找长度:查找过程所需进行的关键字比较次数的平 均值,是衡量查找算法效率的最主要标准,其数学定 义为：
其中,P是要查找数据元素出现的概率,C是 查找相应数据元素的比较次数。 定义要查找数据元素的结构体为: typedef struct KeyType key; 3 DataType
其中，Pi是要查找数据元素出现的概率，Ci是 查找相应数据元素的比较次数。 定义要查找数据元素的结构体为： typedef struct { KeyType key; } DataType;
112静态查找表 静态查找表主要有三种结构 顶序表 序顺序表 引顺序表
11.2 静态查找表 静态查找表主要有三种结构： 顺序表 有序顺序表 索引顺序表
1顺序表 在顺序表上查找的基本思想是:从顺序表的一端开始,用 给定数据元素的关键字逐个和顺序表中各数据元素的关键字 匕较,若在顺序表中查找到要查找的数据元素,则查找成功 函数返回该数据元素在顺序表中的位置;否则查找失败,函 数返回-1
1.顺序表 在顺序表上查找的基本思想是：从顺序表的一端开始，用 给定数据元素的关键字逐个和顺序表中各数据元素的关键字 比较，若在顺序表中查找到要查找的数据元素，则查找成功， 函数返回该数据元素在顺序表中的位置；否则查找失败，函 数返回-1
查找函数设计如下 int Seqsearch(Data Type all, int n, Key Type key) inti=0 while(i< n & ai key !=key)i++ if(ai]. key=- key) return i; else return -l 查找成功时的平均查找长度ASL为: ASL=∑PC1=∑=(n+1)/2
查找函数设计如下： int SeqSearch(DataType a[], int n, KeyType key) { int i = 0; while(i < n && a[i].key != key) i++; if(a[i].key == key) return i; else return -1; } 查找成功时的平均查找长度ASL为： = = = = = + n i i n i i i n n ASL PC 1 1 ( 1)/ 2 1
2有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。 、顺序查找 有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同 二、二分查找(又称折半查找) 算法的基本思想:先给数据排序(例如按升序排好),形成 有序表,然后再将key与正中元素值相比,着key小,则缩小 至前半部內查找;再取其中值比较,每次缩小1/2的范围,直 到查找成功或失败为止。反之,如果key大,则缩小至后半部 内查找
2.有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。 一、顺序查找 有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同 二、二分查找（又称折半查找） 算法的基本思想：先给数据排序（例如按升序排好），形成 有序表，然后再将key与正中元素值相比，若key小，则缩小 至前半部内查找；再取其中值比较，每次缩小1/2的范围，直 到查找成功或失败为止。反之，如果key大，则缩小至后半部 内查找
二分查找算法如下 int BiSearch dataType all, int n, Key Type key) int low=0,high=n-1;/确定初始查找区间上下界 int mid; while(low < high) mid=(ow+high)/2;/确定查找区间中心下标 if( amid]. key=key) return mid;/查找成功 else if(a]. key key) low=mid+1 else high= mid-1 return-1; /查找失败
二分查找算法如下： int BiSearch(DataType a[], int n, KeyType key) { int low = 0, high = n - 1; //确定初始查找区间上下界 int mid; while(low <= high) { mid = (low + high)/2;//确定查找区间中心下标 if(a[mid].key == key) return mid; //查找成功 else if(a[mid].key < key) low = mid + 1; else high = mid - 1; } return -1; //查找失败 }
算法分析 平均查找长度ASL为: ASL=∑PC=∑2 n+ log2(n+1)-1≈log2n
算法分析 平均查找长度ASL为： n n n n i n ASL PC n i k i i i i 2 2 1 1 1 log ( 1) 1 log 1 2 1 + − + = = = = = −