C语言检索汇总.pptx

数据结构;揭安全;第9章　检索;检索（查找）;计算机是如何帮用户 查找数据的？;9.1 检索的基本概念;静态检索表：检索的前后不会改变查找表的内容。;9.2 线性表的检索;9.2.1顺序检索;/*******************************************************************/ /* 线性表检索用的头文件 文件名:seqlist.h */ /*******************************************************************/ #include stdio.h #define maxsize 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct { datatype data[maxsize]; /*此处假设数据元素只包含一个整型的关键字域*/ int len; /*线性表长度*/ } seqlist; /*预定义的顺序表类型*/;算法9.1给出了基于顺序查找表的顺序检索方法。 /* 顺序检索算法 文件名:s_search.c */ /* 函数名: seqSearch() */ #include seqlist.h /*--------顺序查找的非递归实现------*/ int seqsearch(seqlist l,datatype key) { int k=l.len-1; while (k=0 l.data[k]!=key ) k--; return(k); };linklist linkSearch(linklist head, datatype key) { linklist p=head-next; while (p p-data!=key) p=p-next; return p; };顺序检索;顺序检索;顺序检索;顺序查找效率分析;9.2.2二分法检索; 每比较一次，有哪些信誉好的足球投注网站区间缩小一半。如果有哪些信誉好的足球投注网站区间已缩小到一个对象，仍未找到想要有哪些信誉好的足球投注网站的对象，则有哪些信誉好的足球投注网站失败。;10;10;下面给出二分检索法的非递归与递归实现算法，算法中使用seqlist.h中定义的顺序查找表。 ;if (l.data[mid]==key) return mid; /*检索成功返回*/ if (l.data[mid]key) high=mid-1; /*继续在前半部分进行二分检索*/ else low=mid+1; /*继续在后半部分进行二分检索*/ } return -1;/* 当lowhigh时表示查找区间为空，检索失败*/ };binsearch2(l,key,mid+1,high);;有哪些信誉好的足球投注网站成功的情形 有哪些信誉好的足球投注网站不成功的情形;ASLbins= ;图书检索策略;9.2.3分块检索;（2）索引表??? 　抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。 ;图9.2 分块有序表的索引存储表示;2、分块查找的基本思想　　（1）首先查找索引表　　索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。; 分块检索方法通过将查找缩小在某个块中从而提高了检索的效率，其查找的效率由两部分组成，一是为确定某一块对索引表的平均查找长度El，二是块内查找所需的平均查找长度Eb 。; 若以顺序检索来确定块，则分块查找成功时的平均查找长度为：; 若以二分检索来确定块，则分块检索查找成功时的平均查找长度为： ASL’ids=El+Eb ?log2（b+1）-1+（s+1）/2 ?log2（n/s+1）+s/2;/**************************************************************/ /* 分块查找算法 */ /* 文件名：i_search.c 函数名：indexseqsearch() */ /*