大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大 线性表检索用的头文件 /*文件名 seqlist. h #include <stdio. h> # define maxsize100/预定义最大的数据域空间* typedef int datatype;/假设数据类型为整型 typedef struct i datatype data[maxsize];/此处假设数据元素只包含一个整 型的关键字域 nten;/线性表长度 } seqlist;/^预定义的顺序表类型*
/************************************/ /* 线性表检索用的头文件 */ /* 文件名:seqlist.h */ /************************************/ #include <stdio.h> #define maxsize 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct { datatype data[maxsize]; /*此处假设数据元素只包含一个整 型的关键字域*/ int len; /*线性表长度*/ } seqlist; /*预定义的顺序表类型*/
算法9.1给出了基于顺序查找表的顺序检索方法。 大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大 顺序检索算法文件名 s search.c* /函数名: seqsearch10、 seqsearch20 大大大大火大大大大大大大大大大大大大大大大大大大大★大大大大大大火大大大大大大大大大大大大大大大大大 include "seqlist. h /-顺序查找的非递归实现--* int seqsearch 1(seqlist L, datatype key) i int k=L. len-1 while(k>=0 & I data[]!=key)k return(k)
算法9.1给出了基于顺序查找表的顺序检索方法。 /***************************************************/ /* 顺序检索算法 文件名:s_search.c */ /* 函数名: seqsearch1()、seqsearch2() */ /***************************************************/ #include "seqlist.h" /*--------顺序查找的非递归实现------*/ int seqsearch1(seqlist l,datatype key) { int k=l.len-1; while (k>=0 && l.data[k]!=key ) k--; return(k); }
顸序查找的递归实现 int seqsearch2 (seqlist I, int n, datatype key) int k=0 else if(I data[n]==key) k=n else k=seqsearch2(, n-1, key) eturn(k) 算法9.1线性表的顺序检索(顺序存储)
/*-------------顺序查找的递归实现----------*/ int seqsearch2(seqlist l,int n,datatype key) { int k=0; if (n==-1) k=-1; else if (l.data[n]==key) k=n; else k=seqsearch2(l,n-1,key); return(k); } 算法9.1 线性表的顺序检索（顺序存储）
算法分析 顺序检索的缺点是查找时间长。假设顺序表中每个 记录的查找概率相同,即P=1/(=0,1 n-1) 查找表中第个记录所需的进行的比较次数C=n。因 此,顺序查找算法查找成功时的平均查找长度为 n-1 -1 ASL seg ∑PC1=∑(n-1)=(n+1)/ i=0 查找失败时,算法的平均查找长度为: AS 1=n seg 0
顺序检索的缺点是查找时间长。假设顺序表中每个 记录的查找概率相同，即Pi=1/n（i=0，1，…，n-1）， 查找表中第i个记录所需的进行的比较次数Ci=n-i。因 此，顺序查找算法查找成功时的平均查找长度为： 算法分析： − = − = = − = + 1 0 1 0 ( ) ( 1) / 2 1 n i n i i i n i n n ASLseq= P C 查找失败时，算法的平均查找长度为： n n n n i = − = 1 0 1 ASLseq =
9.2.2二分法检索 分法检索又称为折半查找,采用二分法检索可以 大大提高查找效率,它要求线性表结点按其关键字从小 到大(或从大到小)按序排列并采用顺序存储结构。 采用二分搜索时,先求位于搜索区间正中的对象的 下标mid,用其关键码与给定值x比较 >I[mid].Key=X,搜索成功; I[mid].Key>ⅹ,把搜索区间缩小到表的前半 阝分,再继续进行对分搜索 I[mid].Key<ⅹ,把搜索区间缩小到表的后半 部分,再继续进行对分搜索
9.2.2二分法检索 二分法检索又称为折半查找，采用二分法检索可以 大大提高查找效率，它要求线性表结点按其关键字从小 到大（或从大到小）按序排列并采用顺序存储结构。 采用二分搜索时，先求位于搜索区间正中的对象的 下标mid，用其关键码与给定值x比较: ➢ l[mid]. Key = x，搜索成功； ➢ l[mid]. Key > x，把搜索区间缩小到表的前半 部分，再继续进行对分搜索； ➢ l[mid]. Key < x，把搜索区间缩小到表的后半 部分，再继续进行对分搜索