?? b_tree16.c
字號:
/* 2叉B樹(秩為Bi>1)之發明,效率,服務:
(1.1)各節點:實體項數<=Bi*2,各項,依唯獨key,升序排;配有指向孩節點的2指針:
左針所指各實體項key,小于本節點首實體key,右針所指...,大于本節點末實體key
(1.2)滿插而分裂節點:父節點留中位3項,端2*(Bi-1)項,裂入也許新建的左右孩節點
(Bi=3)
對各關鍵[1,25]字k,設檢到k,需F(k)次,處理遞歸,需指令量級M(k)
(2.1)數組存k時,F(k)=k,M(k)=0
總搜索次數=1+2+...+25=325,均次=325/25=13
需指令量級=0
(2.2)當2分搜索判定樹存k,根key=13,F(13)=1,M(13)=0,左孩樹中,
F(6)=2,M(6)=1,F(3)=3,M(3)=2,F(9)=3,M(9)=2,...,F(12)=5,M(12)=4
搜索次=2+2*3+4*4+5*5=49
需指令量級=1+2*2+4*3+5*4=37
得對稱時:
總搜索次=1+2*49=99,均次=99/25=3.96
需指令量級=2*37=74,均=74/25=2.96
(2.3)從中位向兩端,向樹交替插k時,根key=13,F(13)=1,M(13)=0,左孩樹中,
F(9)=2,M(9)=1,F(5)=3,M(5)=2,F(1)=4,M(1)=3,...,F(12)=3,M(12)=2
搜索次=2+3+(3+4+5)+(4+5+6+7)+(4+5+6)=54
需指令量級=1+4*2+7*3=30
得對稱時:
總搜索次=1+2*54=109,均次=109/25=4.36
需指令量級=2*30=60,均=60/25=2.4
(argv[1]:寬生%c%c)
3.對含無符號字節型key,單浮點ton的項,實現:
key升,樹存盤文件(export),從盤建樹(import),增add,刪del,改chg,搜索pry,遍歷tap*/
#include <io.h>
#include <conio.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/stat.h>
typedef unsigned char BYTE;
#define Bi 3
#define older 'o'
#define young 'y'
#define W_mode _O_RDWR|_O_TRUNC|_O_CREAT
#define C_MODE _S_IREAD|_S_IWRITE
#ifdef _DEBUG
// #define Quota
#endif
#ifdef Quota
size_t quota=0;
#endif
struct van_VA{
BYTE key;
float ton;
}van;
struct orb_VA{
BYTE L0R1,van_cnt;
struct van_VA van[Bi*2];
union{
struct van_VA dummy;//自序
struct orb_VA *LP_upp_orb;
}u;
struct orb_VA *LP_Less_orb,*LP_High_orb;
}*LP_top_orb;
typedef struct orb_VA *LP_orb_VA;
int jft;
BYTE orb_suf,age,use;
unsigned short van_tot=0;
union{
BYTE d83f[2+8+1+3+1];
struct van_VA sol[2];
LP_orb_VA lev[2];
}u;
void tile(void *d,void *s,BYTE c){
memmove(d,s,c*sizeof(struct van_VA));
}
void arc(LP_orb_VA L0,LP_orb_VA L1,BYTE van0){
L0->u.LP_upp_orb=L1;
L0->L0R1=orb_suf++;
if(!orb_suf){
printf("\nsuf_ovflow");
exit(0);
}
L0->van_cnt=Bi-1;
tile(&L0->van[0],&L1->van[van0],Bi-1);
}
int dep(BYTE *f,size_t o,size_t p){
if(!f){
printf("\n[d:]83_fname:");
scanf("%s",u.d83f);
f=u.d83f;
}
return(jft=_open(f,o|_O_BINARY,p));
}
void in_key(){
printf("\nBYTE_key:");
scanf("%d",&van.key);
}
void in_ton(BYTE k,float *f){
#ifdef Quota
*f=(float)(k+.1);
#else
printf("\nreal_ton:");
scanf("%f",f);
#endif
}
void heap(void **p){
if(!(*p=calloc(1,sizeof(struct orb_VA))))
exit(0);
#ifdef Quota
quota+=sizeof(struct orb_VA);
#endif
}
void dbl_Bi(LP_orb_VA LP_ear_orb){
LP_ear_orb->van_cnt--;
LP_ear_orb->u.LP_upp_orb=u.lev[0];//恢復
}
void rpl_key_shod_van(LP_orb_VA LP_ear_orb){
if(older==age)//姐
if(LP_ear_orb->LP_Less_orb)
rpl_key_shod_van(LP_ear_orb->LP_Less_orb);
else
tile(&van,&LP_ear_orb->van[0],1);
else
if(LP_ear_orb->LP_High_orb)
rpl_key_shod_van(LP_ear_orb->LP_High_orb);
else
tile(&van,&LP_ear_orb->van[LP_ear_orb->van_cnt-1],1);
}
void rdy_rpl_key_shod_van(LP_orb_VA LP_ear_orb){
tile(&u.sol[0],&van,1);//保存
if(young==age)
rpl_key_shod_van(LP_ear_orb->LP_Less_orb);
else
rpl_key_shod_van(LP_ear_orb->LP_High_orb);
u.sol[1].key=van.key;
tile(&van,&u.sol[0],1);//恢復
}
void add(LP_orb_VA LP_ear_orb){
if(van.key<LP_ear_orb->van[0].key&&LP_ear_orb->LP_Less_orb){
age=young;
rdy_rpl_key_shod_van(LP_ear_orb);
if(van.key<u.sol[1].key||Bi*2==LP_ear_orb->van_cnt){
add(LP_ear_orb->LP_Less_orb);
return;
}
}
if(van.key>LP_ear_orb->van[LP_ear_orb->van_cnt-1].key&&LP_ear_orb->LP_High_orb){
age=older;
rdy_rpl_key_shod_van(LP_ear_orb);
if(van.key>u.sol[1].key||Bi*2==LP_ear_orb->van_cnt){
add(LP_ear_orb->LP_High_orb);
return;
}
}
u.lev[0]=LP_ear_orb->u.LP_upp_orb;//保存
for(age=0;age!=LP_ear_orb->van_cnt;age++)//端捋
if(LP_ear_orb->van[age].key>van.key)//升略
break;
tile(&LP_ear_orb->van[age+1],&LP_ear_orb->van[age],(BYTE)(LP_ear_orb->van_cnt-age));
tile(&LP_ear_orb->van[age],&van,1);//序齊
if(Bi*2+1==++LP_ear_orb->van_cnt)//分裂
if(LP_ear_orb->LP_Less_orb){
tile(&van,&LP_ear_orb->van[0],1);//首項裂入左孩
tile(&LP_ear_orb->van[0],&LP_ear_orb->van[1],Bi*2);
dbl_Bi(LP_ear_orb);
add(LP_ear_orb->LP_Less_orb);
return;
}else
if(LP_ear_orb->LP_High_orb){
tile(&van,&LP_ear_orb->van[Bi*2],1);//末項裂入右孩
dbl_Bi(LP_ear_orb);
add(LP_ear_orb->LP_High_orb);
return;
}else{
heap(&u.lev[1]);LP_ear_orb->LP_Less_orb=u.lev[1];arc(u.lev[1],LP_ear_orb,0);
heap(&u.lev[1]);LP_ear_orb->LP_High_orb=u.lev[1];arc(u.lev[1],LP_ear_orb,(Bi+1)+1);
LP_ear_orb->van_cnt=3;
tile(&LP_ear_orb->van[0],&LP_ear_orb->van[Bi-1],3);
}
LP_ear_orb->u.LP_upp_orb=u.lev[0];//恢復
}
BYTE chg_or_pry1(LP_orb_VA LP_ear_orb){
for(u.sol[0].key=0;u.sol[0].key!=LP_ear_orb->van_cnt;u.sol[0].key++)
if(van.key==LP_ear_orb->van[u.sol[0].key].key){
if('c'==use)
in_ton(van.key,&LP_ear_orb->van[u.sol[0].key].ton);
else
if('p'==use)
printf("\nton=%f",LP_ear_orb->van[u.sol[0].key].ton);
return(1);
}
if(van.key<LP_ear_orb->van[0].key&&LP_ear_orb->LP_Less_orb)
return(chg_or_pry1(LP_ear_orb->LP_Less_orb));
if(van.key>LP_ear_orb->van[LP_ear_orb->van_cnt-1].key&&LP_ear_orb->LP_High_orb)
return(chg_or_pry1(LP_ear_orb->LP_High_orb));
return(0);
}
void del(LP_orb_VA LP_ear_orb){//入口older==age
BYTE i;
for(i=0;i!=LP_ear_orb->van_cnt;i++)
if(van.key==LP_ear_orb->van[i].key){
if(LP_ear_orb->van_cnt>1){
tile(&LP_ear_orb->van[i],&LP_ear_orb->van[i+1],(BYTE)((LP_ear_orb->van_cnt)-(i+1)));
LP_ear_orb->van_cnt--;
}else
if(LP_ear_orb->LP_High_orb){
rpl_key_shod_van(LP_ear_orb->LP_High_orb);
tile(&LP_ear_orb->van[0],&van,1);
del(LP_ear_orb->LP_High_orb);
}else{
u.lev[0]=LP_ear_orb;
if(LP_top_orb==LP_ear_orb)
LP_top_orb=LP_top_orb->LP_Less_orb;
else
if(LP_ear_orb->u.LP_upp_orb->LP_Less_orb==LP_ear_orb)
LP_ear_orb->u.LP_upp_orb->LP_Less_orb=LP_ear_orb->LP_Less_orb;
else
LP_ear_orb->u.LP_upp_orb->LP_High_orb=LP_ear_orb->LP_Less_orb;
if(LP_ear_orb->LP_Less_orb)
LP_ear_orb->LP_Less_orb->u.LP_upp_orb=LP_ear_orb->u.LP_upp_orb;
free(u.lev[0]);
#ifdef Quota
quota-=sizeof(struct orb_VA);
#endif
}
return;
}
if(van.key<LP_ear_orb->van[0].key)
del(LP_ear_orb->LP_Less_orb);
else
del(LP_ear_orb->LP_High_orb);
}
void defix(){
del(LP_top_orb);
van_tot--;
}
void infix(BYTE i){
if(i)
in_ton(van.key,&van.ton);
if(!van_tot){//top_L0R1=0
orb_suf=1;
heap(&LP_top_orb);
}
add(LP_top_orb);
van_tot++;
}
void tap(LP_orb_VA LP_ear_orb){
if(LP_ear_orb->LP_Less_orb)
tap(LP_ear_orb->LP_Less_orb);
if('t'==use){
printf("\norb_L0R1=%02d,upp_key=%02d",LP_ear_orb->L0R1,LP_ear_orb->u.LP_upp_orb?LP_ear_orb->u.LP_upp_orb->L0R1:0);
for(u.sol[0].key=0;u.sol[0].key!=LP_ear_orb->van_cnt;u.sol[0].key++)
printf("\n\tkey=%02d,ton=%f",LP_ear_orb->van[u.sol[0].key].key,LP_ear_orb->van[u.sol[0].key].ton);
while(!kbhit());getch();
}else
write(jft,&LP_ear_orb->van[0],LP_ear_orb->van_cnt*sizeof(struct van_VA));
if(LP_ear_orb->LP_High_orb)
tap(LP_ear_orb->LP_High_orb);
}
typedef union{
int i;
char c[4];
}ic;
void main(ic c,char *v[]){
if(2==c.i&&-1!=dep(v[1],W_mode,C_MODE)){
while(1){
c.c[3]=0;
while(1){
write(jft,&c.c[2],2);
if(!(++c.c[3]))
break;
}
if(!(++c.c[2]))
break;
}
close(jft);
}
for(;;){
#ifdef Quota
printf("\nquota=%#x",quota);
#endif
printf("\narg1<-[0,ff]*[0,ff];Bi=%d;a(dd),b(ye),c(hg),d(el),e(xport),i(mport:(data*mul+add)->mount),p(ry),t(ap,^C)",Bi);
switch(use=getche()){
case 'a':in_key();if(!van_tot||!chg_or_pry1(LP_top_orb))infix(1);continue;
case 'b':return;
case 'c':case 'd':case 'p':case 'e':case 't':
if(van_tot){
switch(use){
case 'c':case 'd':case 'p':
in_key();
if(chg_or_pry1(LP_top_orb)&&'d'==use){
age=older;
defix();
}continue;
case 'e':
if(-1!=dep(NULL,W_mode,C_MODE)){
tap(LP_top_orb);
close(jft);
}continue;
case 't':
printf("\norb_suf=%02d,ascend_van_tot=%d",orb_suf,van_tot);
tap(LP_top_orb);
}
}continue;
case 'i':
if(-1!=dep(NULL,_O_RDONLY,0)){
printf("\n[-128,127]_mul:");
scanf("%d",&c.c[0]);
printf("[-128,127]_add:");
scanf("%d",&c.c[1]);
while(read(jft,&van,sizeof(struct van_VA))){
van.key=van.key*c.c[0]+c.c[1];
van.ton=van.ton*c.c[0]+c.c[1];
if(!van_tot||!chg_or_pry1(LP_top_orb))
infix(0);
}
close(jft);
}
}
}
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -