、主要查找算法 顺序查找 折半查找 分块查找 树表查找 上一页 哈希查找 停止放映 下一页 第6页
下一页 上一页 停止放映 第 6 页 二、主要查找算法 •顺序查找 •折半查找 •分块查找 •树表查找 •哈希查找
1、顺序查找 ●(1)算法思想: 从第1个元素到最后1个元素,逐个进行比 较。 ●(2)特点 ●最简单、最普通的查找方法。 ●(3)适用范围(查找表的存储结构) 上一页 既适用于顺序存储结构 停止放映 也适用于链式存储结构 下一页 第7页
下一页 上一页 停止放映 第 7 页 1、顺序查找 ⚫ (1)算法思想： 从第1个元素到最后1个元素，逐个进行比 较。 ⚫ (2)特点： ⚫ 最简单、最普通的查找方法。 ⚫ (3)适用范围（查找表的存储结构）： –既适用于顺序存储结构 –也适用于链式存储结构
顺序查找的算法描述 ●(4)操作步骤 stepl从第1个元素开始查找; step2用待查关键字值与各结点 (记录)的关键字值逐个进行比较; 若找到相等的结点,则查找成功;否 则,查找失败。 上★-逐个比较 停止放映 下一页 第8页
下一页 上一页 停止放映 第 8 页 顺序查找的算法描述 ⚫ (4)操作步骤： –step1 从第1个元素开始查找； –step2 用 待 查 关 键 字 值 与 各 结 点 （记录）的关键字值逐个进行比较； 若找到相等的结点，则查找成功；否 则，查找失败。 –逐个比较
顺序查找算法框图 开始 seg search(A, n, key) A待查表 i=0 n元素个数 key要找的值 查找key的循环 I++ isn&&Ali:=key? I<n,且还没找到, 循环 Y Ai=ke 上一页 显示“查找失败” 显示“查找成功” 停止放映 下一页 返回 第9页
下一页 上一页 停止放映 第 9 页 顺序查找算法框图 i=0 seq_search(A，n，key) A 待查表 n 元素个数 key 要找的值 i<n&&A[i]!=key? Y N 查找key的循环 显示“查找失败” 返回 开始 i++ A[i]==key? N Y 显示“查找成功” I<n，且还没找到， 循环
(5)顺序查找算法3-1 tem待查表 seg search(item key n元素个数 int *item, n, key key要找的值 i int i=0 while (i<n&& item[i]! key i++ /*查找key的循环* if (item[i]== key printf(“查找成功!\n”); return(i);} 上一页 e⊥se 停止放映 printf(“查找失败!n”); return(-1);} 下一页 WHile I中,有两个判断条件,改进一下,可以减少一半 第10页
下一页 上一页 停止放映 第 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中，有两个判断条件，改进一下，可以减少一半