答是要 8.1查找的基本概念 8.2静态查找表 无序表查找 有序表查找 ●分块查找 ★8.3动态查找表 B树 B·树 8.4哈表
内容提要 8.1 查找的基本概念 8.2 静态查找表 • 无序表查找 • 有序表查找 • 分块查找 8.3 动态查找表 • B树 • B+树 8.4 哈希表
:表示数据元素的数据项 :寻找关键字满足待定条件的数据元素的过 程 查找表:用于查找的数据结构,可能是线性结构 ,也可能是非线性结构 静态查找:查找过程中,不会修改查找表的查找 操作 动态查找:查找的目的是为了修改查找表,通常 是查找成功则删除结点,查找失败则插入结 平均查找长度:查找过程中的平均比较次数, 是比较查找算法优劣的依据
8.1 查找的基本概念 关键字：表示数据元素的数据项 查找：寻找关键字满足特定条件的数据元素的过 程 查找表：用于查找的数据结构，可能是线性结构 ，也可能是非线性结构 静态查找：查找过程中，不会修改查找表的查找 操作 动态查找：查找的目的是为了修改查找表，通常 是查找成功则删除结点，查找失败则插入结 点 平均查找长度：查找过程中的平均比较次数，它 是比较查找算法优劣的依据
石中本的查找 int sqsearch(SQL/ST L, int aidkey dint j, for=O j<L. len, ++ 静态查找表基本 if(L elem]. key==aidkey return j 不作插入和删除操 return -1 作,一般采用顺序 存储结构 (2)有序表的查找 .线性查找算法 int sqsearch(sQLIST L, int aidkey dint ji for=O, <L. len&&L elem. key<=aidkey; j++) if(Lelem key==aidkey return j, return -1
2、静态查找表 (1)无序表的查找 int sqsearch(SQLIST L, int aidkey) {int j; for(j=0;j<L.len;j++) if(L.elem[j].key==aidkey) return j; return -1; } (2)有序表的查找 I.线性查找算法： int sqsearch(SQLIST L, int aidkey) {int j; for(j=0;j<L.len&&L.elem[j].key<=aidkey;j++) if(L.elem[j].key==aidkey) return j; return -1; } 静态查找表基本上 不作插入和删除操 作，一般采用顺序 存储结构
2345678910 int binsearch(SQLIST L, int aidkey) t int low, high, mid, low=0: high=L/en- ( while(low<=high t mid=(low+high)/2 1+2*2+4*3+3*4=29 if(Lelem/mid]==aidkey) return mid, else if( L elem(mid >aidkey high=mid-1; e/se ow=mid+1 return
2、静态查找表(cont’d) (2)有序表的查找 II.折半查找算法： int binsearch(SQLIST L, int aidkey) { int low,high, mid; low=0; high=L.len-1; while(low<=high) { mid=(low+high)/2; if(L.elem[mid]==aidkey) return mid; else if(L.elem[mid]>aidkey) high=mid-1; else low=mid+1; } return -1; } 1 2 2 3 3 3 3 4 4 4 1+2*2+4*3+3*4=29 O(29/10) 1 2 3 4 5 6 7 8 9 10
农的 根据菱波那契序列的特点对有序表分制 0.618法 菱波那契序列 1235813213455……f(m f(n+2)=f(m)+(n+1) 从20个数的数表中查找一个纪录 先找比较第13个,如果小,再比较第8个, 如果大比较后几个数的第5个 每次都比较位于这个数列的黄金分割点0.618处 比如123456789101112131415 16 查找15的位置
2、静态查找表(cont’d) (2)有序表的查找 III.斐波那契查找： 根据斐波那契序列的特点对有序表分割 0.618法 斐波那契序列 1 2 3 5 8 13 21 34 55······f(n)······ f(n+2)=f(n)+f(n+1) 从20个数的数表中查找一个纪录 先找比较第13个，如果小，再比较第8个，···· 如果大 比较后几个数的第5个······ 每次都比较位于这个数列的黄金分割点0.618处 比如 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 查找15的位置