静态查找表：只作查找操作的查找表
动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素
顺序查找(时间复杂度O(n))：又叫线性查找，是最基本的查找技术，它的查找过程：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，器关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
/*有哨兵顺序查找*/
int Sequentia_Search2(int *a, int n, int key) {
int i;
a[0]=key;/*设置a[0]为关键字值，我们称为“哨兵”*/
i = n;
while(a[i]!= key) {
i--;
}
return i; /*返回0则说明查找失败*/
}
有序表查找
1、折半查找(时间复杂度O(logn))
折半查找技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大），线性表必须采用顺序结构。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等；则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
/*折半查找*/
int Binary_Search(int *a, int n, int key) {
int low, high, mid;
low = 1;/*定义最低下标为记录首位*/
high = n;/*定义最高小标为记录末位*/
while(low <= high) {
mid = (low + high) / 2;/*折半*/
if(key<a[mid])/*若查找值比中值小*/
high=mid-1;
else if(key > a[mid])
low=mid+1;
else
return mid;
}
return 0;
}
对于需要频繁插入或删除数据的数据集来说，维护有序的排序会带来不小的工作量，这时候不建议使用折半查找。
插值查找
只需将折半查找中的一行代码改成
mid = low + (high-low) * (key-a[low])/(a[high]-a[low]);
插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心在于插值的计算公式(key-a[low])/(a[high]-a[low]);
斐波那契查找
int Fibonacci_Search(int *a, int n, int key) {
int low,high,mid,i,k;
low = 1;/*定义最低下标为记录首位*/
high =n;/*定义最高下标为记录末位*/
k= 0;
while(n>F[k] - 1)/*计算n位于斐波那契数列的位置*/
k++;
for(i = n; i < F[k] - 1; i++)/*将不满的数值补全*/
a[i] = a[n];
while(low <= high) {
mid = low + F[k - 1]- 1;/*计算当前分隔的下标*/
if (key<a[mid]) {/*若查找记录小于当前分隔记录*/
high = mid - 1;/*最高小标调整到分隔小标mid- 1处*/
k = k - 1;/*斐波那契数列下标减1*/
}
else if (key > a[mid])/*若查找记录大于当前分隔记录*/
{
low = mid + 1;/*最低下标调整到分隔下标mid+1处*/
k = k -2;/*斐波那契数列下标位-2*/
} else {
if (mid <= n)
return mid; /*若相等则说明mid即为查找到的位置*/
else
return n; /*若mid>n说明是补全数值,返回n */
}
}
return 0;
}
折半查找是进行加法和除法运算，插值查找进行复杂的四则运算，斐波那契查找只是简单的加减运算，在海量查找过程中，这种细微差别会影像最终的查找效率。
线性索引查找
线性索引就是将索引项集合组织为线性结构，也称为索引表。
稠密索引
稠密索引是指在线性索引中，将数据集每个记录对应一个索引项，对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。
分块索引
把数据集的记录分成若干块，块内无序，块间有序。
倒排索引
存储具有相同次关键字的所有记录的记录号，这样的索引方法就是倒排索引。
二叉排序树
二叉排序树，又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
·若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
·若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
·它的左、右子树也分别是二叉树。
二叉排序树查找
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode/*结点结构*/
{
int data;/*结点数据*/
struct BiTNode *lchild, *rchild;/*左右孩子指针*/
}BiTNode, *BiTree;
/*递归查找二叉排序树T中是否存在key,*/
/*指针f指向T的双亲，其初始调用值为NULL*/
/*若查找成功，则指针p指向该元素结点，并返回true*/
/*否则指针p指向查找路径上访问的最后一个结点并返回false*/
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
if(!T)/*查找不成功*/
{
*p = f;
return false;
}
else if (key == T->data)/*查找成功*/
{
*p = T;
return true;
}
else if (key < T->data)
return SearchBST(T->lchild, key, T, p);/*在左子树继续查找*/
else
return SearchBST(T->rchild, key, T, p);/*在右子树继续查找*/
}
二叉排序树插入操作
/*当二叉排序树T中不存在关键字等于key的数据元素时,*/
/*插入key并返回true,否则返回false*/
Status InsertBST(BiTree *T, int key)
{
BiTree p,s;
if(!SearchBST(*T, key, NULL, &p))/*查找不成功*/
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->richild = NULL;
if(!p)
*T = s;/*插入s为新的根结点*/
else if(key < p->data)
p->lchild = s;/*插入s为左孩子*/
else
p->rchild = s;/*插入s为右孩子*/
return true;
}
else
return false;/树中已有关键字相同的结点，不再插入*/
}
二叉排序树删除操作
/*若二叉排序树T中存在关键字等于key的数据元素时，删除该数据元素结点*/
/*并返回TRUE;否则返回FALSE*/
Status DeleteBST (BiTree *T, int key) {
if(!*T)/*不存在关键字等于key的数据元素*/
return FALSE;
else
{
if(key == (*T)->data)/*找到关键字等于key的数据元素*/
return Delete(T);
else if(key < (*T) -> data)
return DeleteBST(&(*T)->lchild, key);
else
return DeleteBST(&(*T)->rchild, key);
}
}
/*从二叉排序树中删除结点p,并重接它的左或右子树。*/
Status Delete(BiTree *po)
{
BiTree q,s;
if((*p)->rchild==NULL)/*右子树空则只需重接它的左子树*/
{
q = *p；
*p = (*p)->lchild;
free(q);
}
else if((*p)->lchild==NULL)/*只需重接它的右子树*/
{
q = *p；
*p = (*p)->rchild;
free(q);
}
else/*左右子树均不空*/
{
q = *p;
s = (*p)->lchild;
while (s->rchild)/*转左，然后向右到尽头（找到待删除结点的前驱）*/
{
q=s; s = s->rchild;
}
(*p)->data = s->data;/*s指向被删结点的直接前驱*/
if(q!=*p)
q->rchild=s->lchild;/*重接q的右子树*/
else
q->lchild=s->lchild;/*重接q的左子树*/
free(s)
}
return true;
}
平衡二叉树(AVL树)
平衡二叉树是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor）。
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。
平衡二叉树实现算法
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode /*结点结构*/
{
int data; /*结点数据*/int bf; /*结点的平衡因子*/
struct BiTNode *lchild, *rchild; /*左右孩子指针*/
} BiTNode, *BiTree;
/*对以p为根的二叉排序树作右旋处理*/
/*处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点*/
void R_Rotate(BiTree *p)
{
BiTree L;
L=(*p)->lchild; /*L指向p的左子树根结点*/
(*p)->lchild=L->rchild; /*L的右子树挂接为P的左子树*/
L->rchild=(*p);
*p=L; /*p指向新的根结点*/
}
/*对以P为根的二叉排序树作左旋处理,*/
/*处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0*/
void L_Rotate(BiTree *p)
{
BiTree R;
R = (*p)->rchild; /*R指向P的右子树根结点*/
(*p)->rchild=R->lchild; /*R的左子树挂接为P的右子树*/
R->lchild=(*p);
*p = R; /*p指向新的根结点*/
}
#define LH + 1 /*左高*/
#define EH 0 /*等高*/
#define RH -1 /*右高*/
/*对以指针T所指结点为根的二叉树作左平衡旋转处理*/
/*本算法结束时，指针T指向新的根结点*/
void LeftBalance(BiTree *T)
{
BiTree L,Lr;
L=(*T)->lchild;/*L指向T的左子树根结点*/
switch(L->bf)
{/*检查T的左子树的平衡度，并作相应平衡处理*/
case LH:/*新结点插入在T的左孩子的左子树上，要作单右旋处理*/
(*T)->bf=L->bf=EH;
R_Rotate(T);
break;
case RH:/*新结点插入在T的左孩子的右子树上，要作双旋处理*/
Lr=L->rchild;/*Lr指向T的左孩子的右子树根*/
switch(Lr->bf)/*修改T及其左孩子的平衡因子*/
{
case LH:
(*T)->bf=RH;
L->bf=EH;
break;
case EH: (*T)->bf=L->bf=EH;
break;
case RH:(*T)->bf=EH;
L->bf=LH;
break;
}
Lr->bf=EH;
L_Rotate(&(*T)->lchild); /*对T的左子树作左旋平衡处理*/
R_Rotate(T); /*对T作右旋平衡处理*/
}
}
/*若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个*/
/*数据元素为e的新结点并返回1，否则返回0。若因插入而使二叉排序树*/
/*失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。*/
Status InsertAVL(BiTree *T, int e, Status *taller) {
if(!*T) {
/*插入新结点，树“长高”,置taller为TRUE*/
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=e;
(*T)->lchild=(*T)->rchild=NULL;
(*T)->bf=EH;
*taller=TRUE;
}
else {
if(e==(*T)->data) {
/*树中已存在和e有相同关键字的结点则不再插入*/
*taller=FALSE;
return FALSE;
}
if(e<(*T)->data) {
/*应继续在T的左子树中进行搜索*/
if(!InsertAVL(&(*T)->lchild,e,taller))/*未插入*/
return FALSE;
if(*taller)/*已插入到T的左子树中且左子树“长高”*/
{
switch((*T)->bf)/*检查T的平衡度*/
{
case LH:/*原本左子树比右子树高，需要作左平衡处理*/
LeftBalance(T);
*taller=FALSE;
break;
case EH:/*原本左右子树等高，现因左子树增高而树增高*/
(*T)->bf=LH;
*taller=TRUE;
break;
case RH:/*原本右子树比左子树高，现左右子树等高*/
(*T)->bf=EH;
*taller=FALSE;
break;
}
}
}
else
{/*应继续在T的右子树中进行搜索*/
if(!InsertAVL(&(*T)->rchild,e,taller))/*未插入*/
return FALSE;
if(*taller) /*已插入到T的右子树且右子树“长高”*/
{
switch((*T)->bf) {
/*检查T的平衡度*/
case LH:/*原本左子树比右子树高，现在左、右子树等高*/
(*T)->bf=EH;
*taller=FALSE;
break;
case EH:/*原本左右子树等高，现因右子树增高而树增高*/
(*T)->bf=RH;
*taller=TRUE;
break;
case RH:/*原本右子树比左子树高，需要作右平衡处理*/
RightBalance(T);
*taller=FALSE;
break;
}
}
}
}
return TRUE;
}
网友评论