第4章 搜索算法.ppt

2016-11-15查找2016-11-15?查找——也叫检索,是根据给定的某个值,在表中确定一个关键字等于给定值的记录或数据元素?关键字——是数据元素中某个数据项的值,它可以标识一个数据元素?查找方法评价?查找速度?占用存储空间多少?算法本身复杂程度?平均查找长度ASL(Average Search Length):为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值个元素所需比较次数为找到表中第个元素的概率,为查找表中第其中:个记录的表,对含有icpipcpASLniniiiniii1==??1=1=基本概念:2016-11-15查找成功—在查找表中找到关键字值等于给定值的记录。查找失败对查找表常进行的操作:查询某个“特定的”数据元素是否在查找表中检索某个“特定的”数据元素的各种属性在查找表中插入一个数据元素从查找表中删除某个元素静态查找表:对查找表只前两种“查找”操作动态查找表:对查找表要进行后两种“查找”操作2016-11-15?一顺序查找(线性查找)?查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较?算法描述i例0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数:查找第n个元素: 1查找第n-1个元素:2……….查找第1个元素: n查找第i个元素: n+1-i查找失败: n+12016-11-15typedef int KeyType;typedef float ElemType;typedef struct{ KeyType key; //记录的关键字 ElemType info; //记录的其他信息}JD;int seqsrch(JD r[], int n, KeyType k) //设置监视哨的算法{ int i=n; r[0].key=k; while(r[i].key!=k) i--; return(i);}2016-11-15int seqsrch(JD r[],int n,KeyType k) //未设置监视哨{ int i=0; while (i<n && r[i].key!=k) i++; if (i>=n) return(-1); else return(i);}2016-11-15顺序查找方法的ASL21+=2)1+(1=1==1=??1=1=nnnnincpASLnpniniiii则概率相等设表中每个元素的查找?1==niiicpASLn个记录的表,对含有2016-11-15?二折半查找?查找过程:每次将待查记录所在区间缩小一半?适用条件:?顺序存储结构?查找表按关键字排序?算法实现?设表长为n,low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值?初始时,令low=1,high=n,mid=?(low+high)/2??让k与mid指向的记录比较?若k==r[mid].key,查找成功?若k<r[mid].key,则high=mid-1?若k>r[mid].key,则low=mid+1?重复上述操作,直至low>high时,查找失败2016-11-15?算法描述lowhighmid例1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115