27查找 查找:查找是在一个给定的数据结构中,根据给定 的条件查找满足条件的结点。不同的数据结 构采用不同的查找方法。查找的效率直接影 响数据处理的效率。 查找的结果: 查找成功:找到满足条件的结点 查找失败:找不到满足条件的结点
2.7 查找 查找：查找是在一个给定的数据结构中，根据给定 的条件查找满足条件的结点。不同的数据结 构采用不同的查找方法。查找的效率直接影 响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点
2.7.1顺序查找(线性查找) 查找过程: 对给定的一关键字K,从线性表的一端开始,逐个进 行记录的关键字和K的比较,直到找到关键字等于K的记 录或到达表的另一端。 可以采用从前向后查,也可采用从后向前查的方法 在平均情况下,大约要与表中一半以上元素进行比较,效 率较低。平均查找长度较大 在下面两种情况下只能采取顺序查找: a.线性表为无序表(元素排列是无序的); b.即使是有序线性表,但采用的是链式存储结构
·可以采用从前向后查，也可采用从后向前查的方法。 ·在平均情况下，大约要与表中一半以上元素进行比较，效 率较低。平均查找长度较大。 ·在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。 2．7．1顺序查找（线性查找） 查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进 行记录的关键字和K的比较，直到找到关键字等于K的记 录或到达表的另一端
1.顺序查找(线性表在顺序存储结构下的顺序查找) 数据结构: typedef struct( 每个结点包含两部分 int key; 内容:Key和 Into float info: ISSTable 其他 信息
1 . 顺序查找 (线性表在顺序存储结构下的顺序查找） 数据结构： typedef struct{ int key; float info; }SSTable; 每个结点包含两部分 内容：Key 和info 其他 信息
顺序查找的算法: 使用了监视哨, int Search seq( SSTable stu,intn, int key)在查找过程中 i int i=n; 不用每一步都去 判断是否查找结 stio. key=key; 束。 while(st叫. key! =key))i-;/从表尾往前查找到:返回元素 return 1; 01234在线性表中的存 10|204080储位置; ()初乱未找到:返回0 2 314567 8010204080306025 ○ 监视哨 (b)K=80 (return i=4) 01234567 9010204080306025 (c) K-90(return i=0)
0 1 2 3 4 5 6 7 （a） 初态 10 20 40 80 30 60 25 (b) K=80 (return i=4) 80 10 20 40 80 30 60 25 0 1 2 3 4 5 6 7 (c) K=90 (return i=0 ) 0 1 2 3 4 5 6 7 90 10 20 40 80 30 60 25 顺序查找的算法： int Search_seq(SSTable ST[ ], int n, int key) { int i=n; ST[0].key=key; while(ST[i].key!=key) i- -; /*从表尾往前查*/ return i; } 监视哨 使用了监视哨， 在查找过程中， 不用每一步都去 判断是否查找结 束。 找到：返回元素 在线性表中的存 储位置； 未找到：返回0
根据上述算法可知: 查找成功时的平均查找次数为: ASL=(1+2+3+4+……+n)/n=(n+1)/2 查找不成功时的比较次数为:n+1 则顺序查找的平均查找长度为: AsL==(n+1)2+n+1)/2=(n+1)3/4 顺序查找的优点:算法简单,无需排序,采用顺序 和链式存储均可。 缺点:平均查找长度较大
根据上述算法可知： 查找成功时的平均查找次数为： ASL=(1+2+3+4+……+n)/n=(n+1)/2 查找不成功时的比较次数为： n+1 则顺序查找的平均查找长度为： ASL==((n+1)/2+n+1)/2=(n+1)3/4 顺序查找的优点：算法简单，无需排序，采用顺序 和链式存储均可。 缺点：平均查找长度较大