一般线性表的顺序查找
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef struct
{
int *elem; //元素存储空间基址，建表时按照实际长度分配，0号单元留空
int TableLen; //表的长度
}SSTable;
void InitList(SSTable *L){ //初始化线性表
L->elem = (int*)malloc(sizeof(int)*MAXSIZE);
L->TableLen = 0;
int i;
for(i=0;i<MAXSIZE;i++) //记住0号留空
{
printf("scanf number %d :", i);
scanf("%d", &L->elem[i]);
printf("\n");
L->TableLen++;
}
}
int Search_Seq(SSTable L, int key){
int i;
L.elem[0] = key; //哨兵操作
for(i = L.TableLen;L.elem[i] != key;i--); //从后面往前找
return i;
}
int main(int argc, char const *argv[])
{
SSTable L;
InitList(&L);
printf("%d", Search_Seq(L,4));
return 0;
}
ASL求法：首先要知道的是第 i 元素，需要进行 n-i+1 次比较，ASL(成功) = (n+1)/2 次，失败时是 n+1 次。
注意平均查找长度是每个点的概率乘以该点的查找长度。
需要注意的是，对于顺序查找，查找成功平均时间不会因为线性表是有序还是无序的改变。
有序表的顺序查找
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef struct
{
int *elem; //元素存储空间基址，建表时按照实际长度分配
int TableLen; //表的长度
}SSTable;
void InitList(SSTable *L){ //初始化线性表
L->elem = (int*)malloc(sizeof(int)*MAXSIZE);
L->TableLen = 0;
int i;
for(i=0;i<MAXSIZE;i++)
{
printf("scanf number %d :", i);
scanf("%d", &L->elem[i]);
printf("\n");
L->TableLen++;
}
}
int Search_Seq(SSTable L, int key){
int i;
for(i = 0;i<L.TableLen;i++){
if (L.elem[i] == key)
{
return i;
}
else if (L.elem[i]<key&&L.elem[i+1]>key) //关键步骤，降低查找失败的平均长度
{
return -1;
}
}
}
int main(int argc, char const *argv[])
{
SSTable L;
InitList(&L);
printf("%d", Search_Seq(L,3));
return 0;
}
ASL求法：( 1+2+…+n+n)/(n+1) = n/2 + n/(n+1) 这两个n的原因是我们所到达的虚拟结点长度看作其上一个真实结点的长度，所以看作 n
折半查找（仅仅适用于有序的顺序表）
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 7
typedef struct
{
int *elem; //元素存储空间基址，建表时按照实际长度分配，0号单元留空
int TableLen; //表的长度
}SSTable;
void InitList(SSTable *L){ //初始化线性表
L->elem = (int*)malloc(sizeof(int)*MAXSIZE);
L->TableLen = 0;
int i;
for(i=0;i<MAXSIZE;i++) //记住0号留空
{
printf("scanf number %d :", i);
scanf("%d", &L->elem[i]);
printf("\n");
L->TableLen++;
}
}
int Search_Bin(SSTable L, int key){
int low=0,high= L.TableLen-1,mid;
while(low<=high){
mid = (low+high)/2;
if(L.elem[mid] == key){
return mid;
}
else if (L.elem[mid] > key)
{
high = mid - 1; //从前半部分开始找
}
else
{
low = mid + 1; //从后半部分开始找
}
}
return -1;
}
int main(int argc, char const *argv[])
{
SSTable L;
InitList(&L);
printf("%d", Search_Bin(L,4));
return 0;
}
ASL求法：利用判定树结点与路径进行模拟与计算 \(1/n*(1*1 + 2*2 +...+h*2^{h-1} )\) 至于怎么化简可以使用这个方法：
需要注意查找失败的次数，经常考，即最多不会超过判定树的高度。
另外，折半查找法需要存储结构属于随机存取特性，因此不适合链式存储解构。
折半查找相比于顺序查找来说，它的快体现在一般情况，而顺序查找可以在某些特殊情况快于折半查找。
关于判定树有可能出很多题目，比如判定树是一颗平衡二叉树（这是因为每次折半查找操作都是把数组分为两个数量最多相差一个的数组，这样所得到的判定字树高度绝对值相差不超过 1 ），这个可能成为考点。
为什么折半查找查找不存在的元素时，可以出现至少比较多少次和最多比较多少次呢？因为是平衡二叉树，自然有达不到最大高度就出现查找失败的情况。
判定树中有个特别坑的地方就是：折半查找的mid判定是不一定的，有可能向上取整，也可能向下取整，只要整个算法都采取相同的判定就好了，这个一定要记住，坑死老夫了。
分块查找（索引顺序查找）
#include <stdio.h>
struct number//结构体，定义每个分块中的数据结构，且每个分块的数据结构能相同
{
int start;
int end;
int key; //记录最大关键字
}number_table[4];//结构体中这个分号一定要有。
int block(int key,int a[])
{
int i,j;
i=0;
while( key>number_table[i].key && i<4)//确定为哪个分的块中
i++;
if(i>4) //这就说明失败了
return 0;
j=number_table[i].start; //设置j为每个块中的首数据。
while(key!=j && j<number_table[i].end)//在块中的什么位置。相等时循环结束
{
j++;
}
if(j>number_table[i].end)
j=0;
return j;
}
int main()
{
int i,j,k;
int iStars;
int a[17];
j=0;
printf("please enter fifth numbers.\n");
for(i=1;i<=16;i++)
{
scanf("%d",&a[i]);
}
//这个循环刚开始没写。
for(i=1;i<=2;i++)//i的上限表示分组情况，但有个疑问为什么上限为2的时候依旧正确呢
{
number_table[i].start=j+1;//第一次循环 开始的下标为1 2循环，开始的下标为6
j++;
number_table[i].end=j+5;//第一次循环 结尾的下标为5
j=j+5;
number_table[i].key=a[j];//限定了最大值为最后一位 为a[5].
}
printf("please enter the number that you want:\n");
scanf("%d",&iStars);
j=block(iStars,a);
if(j==0)
printf("Failed\n");
else
printf("success. the number on %d\n",j);
}
ASL计算方法：
1. 平均查找长度为索引块查找与块内查找的平均长度之和。
2. 假设均匀分为b块，每块有s个记录。 3. （b+1）/2 + (s+1)/2一般来说，分块查找不是分成了两份嘛，而且都采用顺序查找，但如果想获得最理想的平均查找长度，块长和每个块的长度，应该相同，并且块长取总元素数目的根号。为什么呢？（b+1）/2 + ((n/b)+1)/2 = (b + n/b + 2)/2。
B树定义理解：B 树又叫平衡多路查找树。一棵m阶的B 树或为空树，或为满足如下特性的m叉树，特性如下： (切勿简单的认为一棵m阶的B树是m叉树，虽然存在四叉树，八叉树等空间划分树，但与B树完全不等同)
每个结点最多有m个子树（分支），而最少分支数要看是否为根结点，如果是根结点且不是叶子结点，则至少要有两个分支，非根非叶结点至少有ceil(m/2)个分支，这里ceil代表向上取整。
如果一个结点有n-1个关键字，那么该结点有n个分支。这n-1个关键字按照递增顺序排列。
每个结点的结构为：
| n | k1 | k2 | … | kn |
|---|---|---|---|---|
| p0 | p1 | p2 | … | pn |
其中，n为该结点中关键字的个数；ki为该结点的关键字且满足ki<ki+1（代表关键字按照递增顺序排列），pi为该结点的孩子结点指针且满足pi所指结点上的关键字大于ki且小于ki+1，p0所指结点上的关键字小于k1，pn所指结点上的关键字大于kn。
结点内各关键字互不相等且按从小到大排列。
叶子结点处于同一层，可以用空指针表示，是查找失败到达的位置（类似于折半查找判定树）。
B树具体操作理解：
B+树定义理解（通过与B树比较进行理解）：
B树高度问题：首先应该明确B树的高度不包括最后的不带任何信息的叶结点所处的那一层（当然有些书可能也不带，具体看题目怎么说）。
小问题：
B树与B+树都可以进行随机查找，B+树叶结点本身按照关键字从小到大链接，因此可以顺序查找，而B树不支持顺序查找（多路查找）。B+树比B树更适合于操作系统的文件索引和数据库索引，因为其磁盘读写代价更低，查询效率更稳定。
Comments
😅 Commenting is disabled on this post.