*****************************************************************************
//靜态查找——順序查找
*****************************************************************************
//靜态查找——索引順序表，效果比順序表查找較好，但遠不及折半查找
*****************************************************************************
//靜态查找——折半查找
#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()%100;
array.weight[i]=rand()%10;
}
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;//重建哈希表
}
}
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)