9.1静态查找表 9.1.1顺序表的查找 应用范围：以顺序表或线性链表表示的静态查找 表，表内元素之间无序 顺序查找的基本思想是：从表中最后一个记录 开始，逐个进行记录的关键字和给定值的比较，若 某个记录的关键字和给定值比较相等，则查找成功； 若直至第一个记录，其关键字和给定值比较都不等， 则查找不成功
9.1 静态查找表 9.1.1 顺序表的查找 应用范围：以顺序表或线性链表表示的静态查找 表，表内元素之间无序。 顺序查找的基本思想是：从表中最后一个记录 开始，逐个进行记录的关键字和给定值的比较，若 某个记录的关键字和给定值比较相等，则查找成功； 若直至第一个记录，其关键字和给定值比较都不等， 则查找不成功
9.1.1顺序表的查找 找64 0 23 4 5 6 8 9 1011 64 5 13 19 21 37 56 64 75 80 88 92 监视哨 比较次数=5 比较次数： 查找第n个元素：1 查找第n-1个元素：2 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1
9.1.1 顺序表的查找 i 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 i i i i 比较次数=5 比较次数： 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1
顺序表的查找 顺序存储结构的表示： typedef int KeyType; typedef struct{ KeyType key;- 关键字域 ElemType; 记录类型 typedef struct{ ElemType *elem ElemType elem[maxsize+1]; R[O用作监视哨单元 int length }SSTable; 顺序表长度
顺序存储结构的表示： typedef int KeyType; typedef struct{ KeyType key; … }ElemType; 顺序表的查找 typedef struct{ ElemType *elem ; int length ; } SSTable;
顺序查找算法 若则查找成功，返回该记录的下标； 若则查找不成功，返回0。 int Search_Seq(SSTable ST,KeyType key){ ST.elem[0].key=key; 设置监视哨 for (i=ST.length;ST.elem[i].key!=key;--i); return i; 设置查找的起始位置 从后往 前查找
若则查找成功，返回该记录的下标； 若则查找不成功，返回0。 int Search_Seq(SSTable ST, KeyType key){ ST.elem[0].key=key; for (i=ST.length;ST.elem[i].key!=key;--i); return i; } 顺序查找算法
举例说明 例1：在下表中查找key=8的结点。 key ST.elem 8 100 10 0 77 1 3 0 1 2 n-3 n-2 n-1 查找不成功，i=0 例2：在下表中查找key=8的结点。 key ST.elem 8 100 10 0 8 3 0 2 n-3 n-2 n-1 查找成功，i=n-2
8 0 1 2 n-3 n-2 n-1 n ST.elem key 例1：在下表中查找 key = 8 的结点。 100 10 ……………… 0 7 1 3 i i i i i i i 查找不成功，i = 0 8 0 1 2 n-3 n-2 n-1 n ST.elem key 例2：在下表中查找 key = 8 的结点。 100 10 ……………… 0 8 1 3 i i i 查找成功，i = n-2 举例说明