第四章查找与排序技术 41基本的查找技术 查找:查找是在一个给定的数据结构中,根据给定的 条件查找满足条件的结点。 不同的数据结构采用不同的查找方法。 查找的效率直接影响数据处理的效率 查找的结果: 查找成功:找到满足条件的结点 查找失败:找不到满足条件的结点
第四章 查找与排序技术 4.1 基本的查找技术 查找：查找是在一个给定的数据结构中，根据给定的 条件查找满足条件的结点。 不同的数据结构采用不同的查找方法。 查找的效率直接影响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点
411顺序查找(线性查找) 查找过程: 对给定的一关键字K,从线性表的一端开始,逐个进 行记录的关键字和K的比较,直到找到关键字等于K的记 录或到达表的另一端。 可以采用从前向后查,也可采用从后向前查的方法。 在平均情况下,大约要与表中一半以上元素进行比较,效 率较低。平均查找长度较大。 在下面两种情况下只能采取顺序查找: a.线性表为无序表(元素排列是无序的) b.即使是有序线性表,但采用的是链式存储结构
·可以采用从前向后查，也可采用从后向前查的方法。 ·在平均情况下，大约要与表中一半以上元素进行比较，效 率较低。平均查找长度较大。 ·在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。 4.1.1 顺序查找（线性查找） 查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进 行记录的关键字和K的比较，直到找到关键字等于K的记 录或到达表的另一端
1.顺序查找(线性表在顺序存储结构下的顺序查找) 数据结构: typedef struct( 每个结点包含两部分 Int key, 内容:Key和info float info: ISSTable 其他 信
1 . 顺序查找 (线性表在顺序存储结构下的顺序查找） 数据结构： typedef struct{ int key; float info; }SSTable; 每个结点包含两部分 内容：Key 和info 其他 信息
顺序查找的算法: 使用了监视哨, int Search seq( ssTable ST,intn, int key))在查找过程中, i int i=n; 不用每一步都去 判断是否查找结 stio. key=key; 束。 while(sti. key!=key)i-;/从表尾往前查找到:返回元素 return i 01234在线性表中的存 10|204080储位置; (a)初乱未找到:返回0 314567 8010204080306025 ○ 监视哨 (b)K-80 (return i=4) 0123456 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 顺序查找的优点：算法简单，无需排序，采用顺序 和链式存储均可。 缺点：平均查找长度较大