【精品数据结构】查找2.pptVIP

第二章?数据结构与算法 在此幻灯片插入公司的徽标 从“插入”菜单 选择图片 找到徽标文件 单击“确定” 重新设置徽标大小 单击徽标内任意位置。徽标外部出现的方框是“调整控点” 使用这些重新设置对象大小 如果在使用尺寸调整控点前按下 shift 键，则对象改变大小但维持原比例。 10 65 865 姓名 学号 成绩 班级 李红 9761059 95 机97.6 A B C D E F G (续) 2.7 查找 查找：查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。 · 可以采用从前向后查，也可采用从后向前查的方法。 · 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。 · 在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。 2．7．1 顺序查找（线性查找） 查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。 1 . 顺序查找 (线性表在顺序存储结构下的顺序查找） 数据结构： typedef struct{ int key; float info; }SSTable; 每个结点包含两部分内容：Key 和info 其他信息 0 1 2 3 4 5 6 7 （a） 初态 40 80 30 60 10 20 25 (b) K=80 (return i=4) 80 40 80 30 60 10 20 25 0 1 2 3 4 5 6 7 (c) K=90 (return i=0 ) 0 1 2 3 4 5 6 7 90 40 80 30 60 10 20 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 顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。 缺点：平均查找长度较大。 2. 线性表在链式存储结构下的顺序查找 struct node { int data; struct node *next; }; int searlb(struct node *h,int x) { struct node *m; m=h; while (m-next!=NULLm-data!=x) m=m-next; return(m); } 2.7.2 折半查找（二分法查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。 查找23和79的过程如下图： mid=(low+high)/2不进位取整 ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) ( 08, 14, 23,