原创
查找
今天是2018年11月23日，又是开心的一天。
今天写篇查找的文章。查找发生在日常生活中，时时刻刻在发生。每一个回忆，发出的有意义的声音，包括
我现在打字都需要去大脑里查找相应的经验。查找是在大量的信息中寻找一个特定的信息元素。在计算机中查找是非常基本又很重要的操作。
查找表是有同一种数据元素构成的集合。
对查找经常进行的操作有：1、查询某个“特定的”数据元素是否在查找表中。2、检索某个特定的数据元素的各种属性。3、在查找表里插入某个元素。4、在查找表里删去一个元素。
只能前两种完成操作，静态查找表。对这四种操作，称为动态查找表。
关键字是数据元素中某个数据项的值，用它可以标识一个记录。如果一个关键字可以唯一表示一个记录，主关键字，如果可以表示若干关键字，次关键字。
对于静态查找表的查找操作
对顺序表的查找。
int Search_Seq(SStable ST,KeyType){
ST.elem[0].key=key;//卫兵。想想这一步的好处？
for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//i代表顺序表下标索引。EQ为equals。
return i;
}
查找操作的分析
平均查找长度：为确定记录在查找表中的位置，需要给定值进行比较的关键字的个数的期望值。[图片上传失
折半查找即二分查找。伪代码如下。
int Search_bin(SSTable ST,KeyType key)
{
low=1;high=ST.length;
while(low<=high)
{
int mid=(low+high)/2;
if(EQ(key,ST.elem[mid].key))return mid;
else if
(LT(key,ST.elem[mid].key))high=mid-1;
else
low=mid+1;
}
return 0;
}
有序链表的二分查找java代码
static int binarySerach(int[] array, int key) {
int left = 0;
int right = array.length - 1;
// 这里必须是 <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] == key) {
return mid;
}
else if (array[mid] < key) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
没有无序链表的二分查找，因为二分查找是在有序基础上得到的简化查找，如果是无序数组二分查找查找就毫无意义。
二分查找的平均查找长度
静态数表的查找
次优查找树的构造，应该不会考，it's too hard for anybody except ACMer。
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<queue>
using namespace std;
struct Binode{
char data;
Binode *lchild,*rchild;
};
typedef Binode* Bitree;
void vist(char c){
cout<<c<<" ";}
void Creatsw(int sw[],int quan[],int n){
for(int i=0;i!=n+1;++i){ int x=0;
for(int j=0;j!=i;++j){
x+=quan[j];
} sw[i]=x;
}
}
void Second_option(Bitree &T,char ch[],int sw[],int low,int high){
int mins=abs(sw[high]-sw[low]),dw=sw[high]+sw[low-1];
int i=low;
for(int j=low+1;j<=high;++j){
if(abs(dw-sw[j]-sw[j-1])<mins){
i=j;
mins=abs(dw-sw[j]-sw[j-1]);
}
}
T=new Binode;
T->data=ch[i-1];
if(i==low)T->lchild=NULL;
else Second_option(T->lchild,ch,sw,low,i-1);
if(i==high)T->rchild=NULL;
else Second_option(T->rchild,ch,sw,i+1,high);
}
void Traval_bitree_cengci(Bitree T){//层次遍历
queue<Bitree>sq;
sq.push(T);
Bitree P;
while(!sq.empty()){
P=sq.front();
vist(P->data);
if(P->lchild){sq.push(P->lchild);}
if(P->rchild){sq.push(P->rchild);}
sq.pop();
}
}
int main(){
ifstream infile("rebuf.txt");
streambuf* backup=cin.rdbuf();
cin.rdbuf(infile.rdbuf());
int n;
cin>>n;
char ch[n];
int quan[n];
for(int i=0;i!=n;++i){
cin>>ch[i]>>quan[i];
}
int sw[n+1];
Creatsw(sw,quan,n);//建立累计权值和。sw[0]=0;
Bitree T;
int low=1,high=9;
Second_option(T,ch,sw,low,high);//建立次优查找树
cout<<endl;
Traval_bitree_cengci(T);//层次遍历的结果
return 0;
}
索引顺序表的查找。即分块查找和块中的最大值相比较。
动态查找表
二叉排序树又称二叉查找树及其查找过程。二叉树是空树或者是具有下列性质的二叉树：若它的左子树不为空则左子树小于根节点的值，若它的右子树不为空，则右子树的值大于根节点的值。
#include <stdio.h>
#include <stdlib.h>
* * *
typedef struct tree{
struct tree *lchild,*rchild;
int data;
}*BiTree,BiNode;
void Insert(BiTree bt,int data)
{//关键字的插入
BiTree p,s,parent;
p=bt;
while(p)
{
if(data<p->data)
{
parent=p;
p=p->lchild;
}
else if(data>p->data)
{
parent=p;
p=p->rchild;
}
else
return ;
}
s=(BiTree)malloc(sizeof(BiNode));
s->data=data;
s->lchild=s->rchild=NULL;
if(s->data<parent->data)
parent->lchild=s;
else
parent->rchild=s;
}
void InitTree(BiTree &bt,int n)
{//建立二叉排序树
int data,i;
scanf("%d",&data);
bt=(BiTree)malloc(sizeof(BiNode));
bt->data=data;
bt->lchild=bt->rchild=NULL;
for(i=1;i<n;i++)
{
scanf("%d",&data);
Insert(bt,data);
}
}
void InOrder(BiTree bt)
{//树的中序遍历
if(!bt)
return ;
InOrder(bt->lchild);
printf("%d ",bt->data);
InOrder(bt->rchild);
}
int Search(BiTree bt,int key)
{
BiTree p;
p=bt;
while(p)
{
if(key<p->data)
p=p->lchild;
else if(key>p->data)
p=p->rchild;
else
{
printf("数字%d查找成功。\n",key);
return 1;
}
}
printf("未找到数据%d。\n",key);
return 0;
}
void Delete_BiTree(BiTree &bt,int key)
{
BiTree p,cur,par;
p=bt;
while(p){
if(key==p->data)
break;
else if(key<p->data){
par=p;
p=p->lchild;
}
else{
par=p;
p=p->rchild;
}
}
if(!p){
printf("该数据不存在.\n");
return ;
}
if(!p->lchild) //没有左子树
{
if(p==bt)
bt=p->rchild;
else if(par->lchild==p)
par->lchild=p->rchild;
else
par->rchild=p->rchild;
free(p);
}
else
{
cur=p->lchild;
par=cur;
while(cur->rchild)
{
par=cur;
cur=cur->rchild;
}
if(par==p->lchild) //p的左孩子没有右子树
{
p->data=par->data;
p->lchild=par->lchild;
free(par);
}
else //p的左孩子有右子树
{
p->data=cur->data;
par->rchild=cur->lchild;
free(cur);
}
}
printf("删除成功.\n");
}
int main()
{
BiTree bt;
int n,key,selet;
while(1)
{
printf(" ------------------\n");
printf(" 1、建立二叉排序树\n");
printf(" 2、输出中序遍历结果\n");
printf(" 3、搜索数据\n");
printf(" 4、删除数据\n");
printf(" 5、插入数据\n");
printf(" 6、退出\n");
printf(" ------------------\n");
scanf("%d",&selet);
switch(selet)
{
case 1:
printf("输入数字的个数:");
scanf("%d",&n);
printf("请输入每个数字:");
InitTree(bt,n);
break;
case 2:
printf("中序遍历结果为：");
InOrder(bt);
putchar('\n');
break;
case 3:
printf("请输入查找的关键字：");
scanf("%d",&key);
Search(bt,key);
break;
case 4:
printf("请输入删除的关键字：");
scanf("%d",&key);
Delete_BiTree(bt,key);
break;
case 5:
printf("请输入要插入的数据：");
scanf("%d",&key);
Insert(bt,key);
printf("插入成功.\n");
break;
default:
return 0;
}
}
}
关于平衡二叉树的单次左旋RR，单次右旋LL，先左旋再右旋RL，先右旋再左旋。
如图：
关于旋转这部分该博客还是awesome的。
这部分是比较难的，注意B树的性质。
http://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html
网友评论