10-8.c

数据结构的经典实现算法

#include  < stdio.h>
#include  < alloc.h>
#include  < atdlib.h>
#define WORD_SIZE 5      
#define PAGE_SIZE 10    
#define DIRECTORY _SIZE 32    
typedef struct page *paddr ; 
typedef struct page{
        int local_depth ; 
        char *name[PAGE_SIZE] ; 
        int num_idents ;  
} ; 
typedef struct cord{
        char *key ;     
        /* 其他数据 */
}brecord ; 
int globle_depth ;  
paddr directory[DIRECTORY_SIZE] ;  
paddr hash  ( char *key,short int precision )
{

}
paddr buddy  ( paddr index )
{

}
int size  ( paddr ptr )
{   
	/* 返回页的识别体个数*/
}
void coalesce  ( paddr ptr,paddr buddy )
{
/* 把ptr，buddy合成一页*/
}
short int pgsearch  ( char *key,paddr index )
{
/* 查找关键字为key的页,找到返回1，找不到饭后0*/
}
int convert  ( paddr ptr )
{
	/*把ptr转换给整数*/
}
void enter  ( brecord r,paddr ptr )
{
	/* 插入新记录*/
}
void pgdelete  ( char *key,paddr ptr )
{
	/* 删除关键字为key的记录*/
}
short int find  ( char *key,paddr *ptr )
{
/* 找不到关键字则返回0，否则返回1以及把ptr指向要找的页*/
        paddr index ; 
        int intindex ;        
        index = hash  ( key,globle_depth ) ; 
        intindex = convert  ( index ) ; 
        *ptr = directory[intindex] ; 
        return pgsearch  ( key,ptr ) ; 
}
void insert  ( brecord r,char *key )
{
        paddr ptr ; 
        if find  ( key,&ptr ){
            printf("关键字不在记录中.\n" ) ; 
            exit(1) ; 
        }
        if   ( ptr->num_idents !=  PAGE_SIZE ){
            enter  ( r,ptr ) ; 
            ptr->num_idents++ ; 
        }
        else {
		/* 把页一分为二，插入新关键字，如果globle_depth溢出，则显示错误然后中止*/          
        } ; 
}
void delete_rec( brecord r,char *key )
{/* 找到并删除r记录*/
        paddr ptr ; 
        if  ( !find  ( key,&ptr ) ){
            printf ("关键字不在记录中\n" ) ; 
            return ;  
        }
        pgdelete  ( key,ptr ) ; 
        if   ( size  ( ptr ) + size  ( buddy  ( ptr ) ) <= PAGE_SIZE )
            coalesce  ( ptr,buddy  ( ptr ) ) ; 
}