*****************************************************************************
//静态查找——顺序查找
*****************************************************************************
//静态查找——索引顺序表，效果比顺序表查找较好，但远不及折半查找
*****************************************************************************
//静态查找——折半查找
#include "stdio.h"#define SIZE 11
int Bsearch(int num[SIZE],int number,int low,int high){ int mid; while(low<=high) { mid=(low+high)/2; if(number==num[mid]) return mid; else if(number>num[mid]) low=mid+1; else high=mid-1; } return 0;}
main(){ int num[SIZE],number,index,i; for(i=1;i<SIZE;i++) num[i]=i;//前提是已排序 printf("please input a number:"); scanf("%d",&number); index=Bsearch(num,number,1,SIZE-1); if(index==0) printf("not find!"); else printf("/nlocation:%d",index); getch();}
*****************************************************************************
//静态查找——次优查找树
#include "stdio.h"#include "stdlib.h"#include "math.h"#include "conio.h"#define SIZE 11
struct Node{ int num; int weight; struct Node *lchild,*rchild;};
typedef struct{ int num[SIZE]; int weight[SIZE];}NUM;
Pratition(NUM *array,int low,int high){ array->num[0]=array->num[low]; array->weight[0]=array->weight[low]; while(low<high) { while(low<high&&array->num[high]>array->num[0]) --high; { array->num[low]=array->num[high]; array->weight[low]=array->weight[high]; } while(low<high&&array->num[low]<=array->num[0]) ++low; { array->num[high]=array->num[low]; array->weight[high]=array->weight[low]; } } array->num[low]=array->num[0]; array->weight[low]=array->weight[0]; return low;}
Sort(NUM *array,int low,int high){ int mid; if(low<high) { mid=Pratition(array,low,high); Sort(array,low,mid-1); Sort(array,mid+1,high); }}
CreateSW(int sw[SIZE],int weight[SIZE]){ int i,j; for(i=0;i<SIZE;i++) { sw[i]=0; for(j=1;j<=i;j++) sw[i]+=weight[j]; }}
CreateTree(struct Node *p,int sw[SIZE],NUM array,int low,int high){ int i=low,j,min=abs(sw[high]-sw[low]),dw=sw[high]-sw[low-1]; for(j=low+1;j<=high;j++) if(abs(dw-sw[j]-sw[j-1])<min) { i=j; min=abs(dw-sw[j]-sw[j-1]); } p=(struct Node *)malloc(sizeof(struct Node)); p->num=array.num[i]; p->weight=array.weight[i]; if(i==low) p->lchild=NULL; else CreateTree(p->lchild,sw,array,low,i-1); if(i==high) p->rchild=NULL; else CreateTree(p->rchild,sw,array,i+1,high); return p;}
main(){ NUM array; struct Node *p,*head; int i,sw[SIZE],number; randomize(); for(i=1;i<SIZE;i++) { array.num[i]=rand()0; array.weight[i]=rand(); } Sort(&array,1,SIZE-1); array.num[0]=0; array.weight[0]=0; CreateSW(sw,array.weight); head=CreateTree(p,sw,array,1,SIZE-1); for(i=0;i<SIZE;i++) printf("%d %d/n",array.num[i],array.weight[i]); for(i=0;i<SIZE;i++) printf("%d ",sw[i]); getch();}
*****************************************************************************
//动态查找——二叉排序树
#include "stdio.h"#include "conio.h"
struct BitTree{ int data; struct BitTree *lchild,*rchild;};
struct BitTree *Insert(struct BitTree *root,int key){ struct BitTree *p,*pr,*s; p=root; pr=p; s=new struct BitTree; s->data=key; s->lchild=s->rchild=NULL; while(p) { printf("p->data:%d",p->data); if(p->data==key) {printf("find!");getch();return root;} else if(key>p->data) {printf("search right/n");getch();pr=p;p=p->rchild;} else {printf("search left/n");getch();pr=p;p=p->lchild;} } printf("have not this node!"); getch(); if(!pr) {root=s;printf("create tree!/n");getch();return root;} else { if(key>pr->data) {printf("input right/n");pr->rchild=s;getch();} else {printf("input left/n");pr->lchild=s;getch();} return root; }}
int Search(struct BitTree *&p,struct BitTree *&pr,int key){ while(p) { if(p->data==key) return 1; else if(key>p->data) {pr=p;p=p->rchild;} else {pr=p;p=p->lchild;} } printf("have not this node!");}
void Delete(struct BitTree *&p,struct BitTree *&pr){ struct BitTree *pt; getch(); if(!p->lchild&&!p->rchild) pt=NULL; else if(p->lchild&&!p->rchild) {pt=p->lchild;} else if(!p->lchild&&p->rchild) {pt=p->rchild;} else { pt=p->lchild; pr=p; while(pt->rchild) {pr=pt;pt=pt->rchild;} p->data=pt->data; if(pr==p) pr->lchild=pt->rchild; else pr->rchild=pt->rchild; } if(pr->lchild==p) pr->lchild=pt; else if(pr->rchild==p) pr->rchild=pt;}
void Print(struct BitTree *p){ if(p) { Print(p->lchild); printf("%d/n",p->data); Print(p->rchild); }}
main(){ int quit=0,key; struct BitTree *root,*pr,*p; root=NULL; while (!quit) { char ch; puts("1 Insert"); puts("2 Delete"); puts("3 Print"); puts("4 Exit"); ch=getch(); switch(ch) { case '1': printf("Please input:"); scanf("%d",&key); root=Insert(root,key); break; case '2': printf("Please input:"); scanf("%d",&key); p=root; pr=NULL; Search(p,pr,key); Delete(p,pr); break; case '3': p=root; Print(p); getch(); break; case '4':quit=1;break; } }}
*****************************************************************************
//动态查找——平衡二叉树
#include "stdio.h"#include "conio.h"#define EH 0;#define LH 1;#define RH -1;#define TRUE 1;#define FALSE 0;
typedef struct BSTNode { int data; int bf; struct BSTNode *lchild,*rchild;}*BitTree;
void R_Rotate(BitTree &p){ BitTree lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc;}
void L_Rotate(BitTree &p){ BitTree rc; rc=p->rchild; p->rchild=rc->lchild; rc->lchild=p; p=rc;}
int LeftBalance(BitTree &p){ BitTree lc,rd; lc=p->lchild; switch(lc->bf) { case 1: lc->bf=p->bf=EH; R_Rotate(p); break; case -1: rd=lc->rchild; switch(rd->bf) { case 1: p->bf=RH;lc->bf=EH;break; case 0: p->bf=lc->bf=EH;break; case -1: p->bf=EH;lc->bf=LH;break; } rd->bf=EH; L_Rotate(p->lchild); R_Rotate(p); break; } }
int RightBalance(BitTree &p){ BitTree rc,ld; rc=p->rchild; switch(rc->bf) { case -1: rc->bf=p->bf=EH; L_Rotate(p); break; case 1: ld=rc->lchild; switch(ld->bf) { case 1: p->bf=LH;rc->bf=EH;break; case 0: p->bf=rc->bf=EH;break; case -1: p->bf=EH;rc->bf=RH;break; } R_Rotate(p->rchild); L_Rotate(p); break; }}
int Insert(BitTree &p,int key,int &taller){ if(!p) { p=new BSTNode; p->lchild=p->rchild=NULL; p->data=key; p->bf=EH; taller=TRUE; } else { if(key==p->data) {taller=TRUE;return 0;} if(key<p->data) { if(!Insert(p->lchild,key,taller)) return 0; if(taller) switch(p->bf) { case 1: LeftBalance(p);taller=FALSE;break; case 0: p->bf=LH;taller=TRUE;break; case -1: p->bf=EH;taller=FALSE;break; } } else { if(!Insert(p->rchild,key,taller)) return 0; if(taller) switch(p->bf) { case 1: p->bf=EH;taller=FALSE;break; case 0: p->bf=RH;taller=TRUE;break; case -1: RightBalance(p);taller=FALSE;break; } } }}
void Print(BitTree &p){ if(p) { printf("%d %d/n",p->data,p->bf); Print(p->lchild); Print(p->rchild); }}
main(){ BitTree root,p; int quit=0,key,taller; char ch; root=NULL; while(!quit) { puts("1 Insert"); puts("2 Print"); puts("3 Exit"); ch=getch(); switch(ch) { case '1': p=root; printf("Please Input:"); scanf("%d",&key); Insert(p,key,taller); root=p; break; case '2':p=root;Print(p);getch();break; case '3':quit=1;break; } } }
*****************************************************************************
//动态查找——B+和B-树，在文件系统中很好用
*****************************************************************************//哈希表查找（简单的算法描述）
#define SIZE 100#define DUPLICATE -1 //表示已有该元素
typedef struct { int key[SIZE]; int count; int sizeindex;}HashTable;
int SearchHash(HashTable H,int keynum,int &position,int &count){ position=Hash(key); while(H.key[position]!=0&&H.key[postion]!=keynum) collision(position,++count);//求下一个探测地址 if(keynum==H.key[position]) return 1; else return 0;}
int InsertHash(HashTable &H,int e){ int count=0,position; if(SearchHash(H,e,position,count)) return DUPLICATE; else if(count<hashsize[H.sizeindex]/2) { H.key[position]=e;++H.count;return 1; } else { RecreateHashTable(H);return 0;//重建哈希表 }}
