一.查找
1.静态查找
要求数据集合是稳定的，不能有添加和删除的查找操作。
2.动态查找
数据集合在查找的过程中需要添加或删除元素的查找操作。
二、查找的实现
1.顺序查找
int sq_serch(int *a,int len,int key)
{
int i;
for(i=1;i<=len;i++)//从1开始
{
if(a[i] == key)
return ;
}
return 0;
}
1.1.顺序查找的优化
int sq_serch(int *a,int len,int key)
{
int i=len;//指向末尾
a[0]=key;//设置一个哨兵
while(a[i]!=key)
i--;
return i;
}
2.折半查找
//二分查找或折半查找
#include <stdio.h>
#include <windows.h>
int binary_search(int *a,int n,int key)
{
int low=0,high=n,mid;
while(low<=high)
{
mid = (low + high)/2;//这里写出low+(high-low)/2更好 以防相加溢出
if(key > a[mid])
low = mid+1;
else if(key < a[mid])
high = mid-1;
else
return mid;
}
return 0;
}
int main()
{
int a[10] ={1,3,5,8,10,25,66,84,99,106};
int n=10,key=84;
int ret=binary_search(a,n,key);
if(ret==0)
printf("数据%d在不在数组中");
else
printf("数据%d在数组中下标为%d",key,ret);
system("pause");
return 1;
}
3.插值查找
int chazhi_search(int *a,int n,int key)
{
int low=0,high=n,mid;
while(low<=high)
{
mid = low+(high-low)*(key-a[low])/(a[high]-a[low]);
if(key > a[mid])
low = mid+1;
else if(key < a[mid])
high = mid-1;
else
return mid;
}
return 0;
}
4.斐波那契查找
int fibonacci_search(int *a,int n,int key)
{
int low,high,mid,i,k;
low=0;
high=n;
k=0;
while(n>F(k)-1)//找到n位于斐波那契数列的位置
{
k++;
}
for(i=0;i<F(k)-1;i++)//补齐不满的数据
a[i]=a[n];
while(low<=high)
{
mid = low+F[k-1]-1;//取到黄金值的位置
if(key > a[mid])
{
low = mid+1;
k=k-2;
}
else if(key < a[mid])
{
high = mid-1;
k=k-1;
}
else
{
if(mid<=n)
return mid;
else
return n;
}
return 0;
}
5.二叉排序树(二叉查找树)
1.若它的左子树不为空，则左子树上所有节点的值均小于根节点！
2.若它的右子树不为空，则右子树上所有节点的值均小于根节点！
3.它的左右子树也分别为二叉排序树
二叉排序树
//二叉排序树
#include <stdio.h>
#include <windows.h>
//定义二叉排序树节点
typedef struct BNode
{
int data;//数据
struct BNode *left;//左节点
struct BNode *right;//右节点
}BNode,*BTree;//这里的BTree是一个一级指针
//二叉排序树的查找
int SearchBST(BTree T,int key,BTree f,BTree *p)
{
if(T == NULL)
{
*p=f;//记录上一个节点
return 0;
}
else if(key == T->data)//找到了
{
*p = T;
return 1;
}
else if(key > T->data)//key大的话，访问右子树
{
return SearchBST(T->right,key,T,p);
}
else//访问左子树
return SearchBST(T->left,key,T,p);
}
//二叉树的插入
int InsertBTS(BTree *T,int key)
{
BTree p,s;
if(!SearchBST(*T,key,NULL,&p))//如果找不到该节点
{
s= (BTree)malloc(sizeof(BNode));//创建新节点
s->data = key;
s->left = s->right = NULL;
if(p==NULL)//如果找不到
{
*T=s;//当前节点作为根节点
}
else if(key < p->data)
{
p->left=s;
}
else
{
p->right = s;
}
return 1;
}
else
{
//节点已经存在 就不重复插入
return 0;
}
}
//二叉排序树的中序遍历
void InOrder(BTree T)
{
if(T== NULL)
return;
InOrder(T->left);//访问左子树
printf("%d ",T->data);//访问根
InOrder(T->right);//访问右子树
}
//二叉排序树的删除
int Delete(BTree *p)
{
BTree q,s;
if((*p)->right == NULL)//如果右子树为空,只需将左子树接上去
{
q=*p;//记录当前节点
*p=(*p)->left;
free(q);
}
else if((*p)->left == NULL)//左子树为空，只需将右子树接上去即可
{
q=*p;
*p=(*p)->right;
free(q);
}
else//左右子树都不为空
{
q=*p;//记录当前节点
s=(*p)->left;
while(s->right)
{
q=s;
s=s->right;
}
(*p)->data = s->data;//数据替换
if(q!=*p)
q->right = s->left;//重新接到q的 右子树
else
q->left = s->left; //重新接到q的左子树
}
}
int DeleteBST(BTree *T,int key)
{
if(*T == NULL)//找不到节点
return 0;
else
{
if(key == (*T)->data)
{
Delete(T);
}
else if (key < (*T)->data)//小于->访问左子树
{
return DeleteBST(&(*T)->left,key);
}
else//大于->访问右子树
{
return DeleteBST(&(*T)->right,key);
}
}
}
int main()
{
int i;
int a[10] = {62,88,58,47,35,73,51,99,37,93};
BTree T =NULL;
//二叉排序树的创建
printf("当前数组a为:\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
InsertBTS(&T,a[i]);
}
printf("\n二叉排序BTS创建完毕\n");
printf("二叉排序树的中序遍历为:\n");
InOrder(T);
printf("\n");
DeleteBST(&T,47);
printf("删除节点47后的二叉排序树:\n");
InOrder(T);
system("pause");
return 1;
}
结果
6.平衡二叉树
代码有点复杂，暂时略过
7.2-3树，2-3-4树，B树，B+树
理解即可
8.哈希表查找(散列表查找)
//散列表查找法
#include <stdio.h>
#include <windows.h>
#define HASHSIZE 12 //哈希表长度
#define NULLKEY -36688
typedef struct HashTable
{
int *elem;//动态分配内存
int count;//元素长度
}HashTable;
//初始化散列表
void InitHashTable(HashTable *H)
{
int i;
H->count = HASHSIZE;//
H->elem = (int*)malloc(sizeof(int)*HASHSIZE);
for(i=0;i<HASHSIZE;i++)
H->elem[i] = NULLKEY;
}
//散列函数:除留余数法
int Hash(int key)
{
return key%HASHSIZE;
}
//插入函数
void Insert(HashTable *H,int key)
{
int addr = Hash(key);//求出散列地址
while(H->elem[addr] != NULLKEY)//产生冲突
addr = (addr+1)%HASHSIZE;//开放定指法的线性探测法
H->elem[addr] = key;
printf("%d 存放的地址为：%d,H.elem[%d]=%d\n",key,addr,addr,H->elem[addr]);
}
//散列表的查找
int Search(HashTable *H,int key,int *addr)
{
*addr = Hash(key);
while(H->elem[*addr]!=key)//找不到 继续往下找
{
*addr = (*addr+1)%HASHSIZE;
if(H->elem[*addr]==NULLKEY || *addr ==Hash(key))//回到原点
{
printf("%d 不存在\n",key);
return 0;//key不存在
}
}
printf("%d 在散列表中的地址为%x \n",key,*addr);
return 1;
}
//打印散列表
void showTable(HashTable H)
{
int i=0;
printf("散列后为[");
for(;i<HASHSIZE;i++)
printf("%d ",H.elem[i]);
printf("]\n");
}
int main()
{
HashTable H;
int i,j;
int a[]={12,67,56,16,25,37,22,29,15,47,48,34};
InitHashTable(&H);
for(i=0;i<HASHSIZE;i++)
Insert(&H,a[i]);
printf("散列前为[");
for(i=0;i<HASHSIZE;i++)
printf("%d ",a[i]);
printf("]\n");
showTable(H);
system("pause");
return 1;
}
运行结果
散列函数
网友评论