main.c

桶型散列文件算法

//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <conio.h> 

/*定义散列表长度，其值取决于待三列的元素数量 
和选取的装填因α的大小，在此假定为13*/ 
#define HASH_NUM 13

/*定义关键字类型，这里假定为整型*/ 
typedef int KeyType; 

struct ElemType     //元素类型 
{ 
    KeyType key;    //关键字域 
    char rest[10];  //其他域，假定用字符数组表示 
}; 

struct FLNode   //索引文件中的结点类型 
{ 
    struct ElemType data;   //值域 
    int next;       //指向下一个结点的指针域 
}; 

const int b1 = sizeof(KeyType); //用全局常量b1保存索引表文件中的记录（元素）长度 
const int b2 = sizeof(struct FLNode);   //用全局常量b2保存索引主文件中的记录（结点）长度 

//建立并初始化散列表文件 
void InitHashFile(char *fname) 
{ 
    int i; 
    int *A; 
    //以读写方式新建二进制散列文件 
    FILE *fp; 
    fp = fopen(fname, "wb+"); 
    if(NULL == fp) 
    { 
        printf("Cannot open this file!\n"); 
        exit(1); 
    } 

    //动态分配具有N+1个整型储存空间的数组A 
    A = (int *)calloc(HASH_NUM + 1, b1);
    if(NULL == A) 
    { 
        printf("Memory alloction failare!\n"); 
        exit(1); 
    } 
     
    //给数组A中的每个元素赋初值-1，表示空指针 
    for(i = 0; i < HASH_NUM + 1; i++)
    { 
        A[i] = -1; 
    } 

    //初始化散列文件 
    fwrite((char *)A, (HASH_NUM + 1)*b1, 1, fp);

    //删除数组A 
    free(A); 

    //关闭fp对应的文件 
    fclose(fp); 
} 

//检测是否存在散列文件 
void existHash(char *fname) 
{ 
    char bcreate; 
    char filename[128]; 
    FILE *fp; 
    fp = fopen(fname, "rb"); 
    if(NULL == fp) 
    { 
        printf("--- 散列文件不存在, 是否新建散列文件(y:从新建立/n:打开其他散列文件)? ---\n"); 
        scanf("%c", &bcreate); 
        if('y' == bcreate || 'Y' == bcreate) 
        { 
            InitHashFile(fname); 
            printf("--- 新建散列文件完毕! ---\n"); 
        } 
        else 
        { 
            printf("请输入散列文件路径:\n"); 
            scanf("%s", filename); 
            strcpy(fname, filename); 
            existHash(fname); 
        } 
    } 
    else 
    { 
        fclose(fp); 
    } 
} 

//把元素x插入到散列文件中 
void HFInsertOne(char *fname, struct ElemType x) 
{ 
    int p; 
    int len;    //文件尾结点位置序号 
    int *A; 
    int d; 
    struct FLNode temp; 
    struct FLNode pn; 

    //以读写和不新建方式打开散列文件 
    FILE *fp; 
    fp = fopen(fname, "rb+"); 
    if(NULL == fp) 
    { 
        printf("Cannot open this file!\n"); 
        exit(1); 
    } 

    //动态分配具有N + 1个整型存储空间的数组 
    A = (int *)calloc(HASH_NUM + 1, b1);
    if(!A) 
    { 
        printf("Memory alloction failare!\n"); 
        exit(1); 
    } 

    //将散列文件的表头读入到数组A中 
    fread((char *)A, (HASH_NUM + 1) * b1, 1, fp);

    //以关键字x.key计算x的散列地址，采用除留余数法 
    d = x.key % HASH_NUM;
    //以x和A[d]的值构成待插入散列文件的内存节点temp    
    temp.data = x; 
    temp.next = A[d]; 
    //将temp结点的值写入到散列文件中，并链接到散列文件表头 
    //下表d单链表的表头 
    if(-1 == A[HASH_NUM])
    { 
        //将文件指针移至文件尾 
        fseek(fp, 0L, 2); 
        //计算出文件尾的结点位置序号 
        len = (ftell(fp) - (HASH_NUM+1)*b1)/b2; 
        //将temp结点的值写入文件尾 
        fwrite((char *)&temp, b2, 1, fp); 
        //使A[d]指向新插入的结点 
        A[d] = len; 
    } 
    else 
    { 
        //p指向空闲单链表的表头结点 
        p = A[HASH_NUM];
        //使空闲单链表的表头指针指向其下一个结点 
        fseek(fp, b1 * (HASH_NUM+1) + p*b2, 0);
        fread((char *)&pn, b2, 1, fp); 
        A[HASH_NUM] = pn.next;
        //使temp的值写入到p位置的结点上 
        fseek(fp, -b2, 1); 
        fwrite((char *)&temp, b2, 1, fp); 
        //使A[p]指向新插入的p结点 
        A[d] = p; 
    } 
    //将数组A中的全部内容写回到散列文件的表头中 
    fseek(fp,0L,0); 
    fwrite((char *)A, b1 * (HASH_NUM+1), 1, fp);
    //删除动态数组A和关闭散列文件 
    free(A); 
    fclose(fp); 
} 

//从散列文件中删除关键字尾x.key的元素，并有x带回该 
//元素，若删除成功则返回1，否则返回0 
int HFDelete(char *fname, struct ElemType *x) 
{ 
    struct FLNode tp,tq; 
    int p, q; 
    int *A; 
    int d; 
    FILE *fp; 

    //打开散列文件 
    fp = fopen(fname, "rb+"); 
    if(NULL == fp) 
    { 
        printf("Cannot open this file!\n"); 
        exit(1); 
    } 

    //申请动态数组A 
    A = (int *)calloc(HASH_NUM+1, b1);
    if(NULL == A) 
    { 
        printf("Memory alloction failare!\n"); 
        exit(1); 
    } 

    //将散列文件表头读入数组A中 
    fread((char *)A, (HASH_NUM+1)*b1, 1, fp);
     
    //计算散列地址d 
    d = x->key % HASH_NUM;
    p= A[d]; 
    while(-1 != p) 
    { 
        fseek(fp, (HASH_NUM+1)*b1+p*b2, 0);
        fread((char*)&tp, b2, 1, fp); 
        if(tp.data.key  == x->key) 
        { 
            //被删除结点的元素值赋给x带回 
            *x = tp.data; 

            //从单链表中删除p结点 
            if(p == A[d]) 
            { 
                A[d] = tp.next; 
            } 
            else 
            { 
                tq.next = tp.next; 
                fseek(fp, (HASH_NUM+1)*b1+q*b2, 0);
                fwrite((char *)&tq, b2, 1, fp); 
            } 
            //将p结点连接到空闲单链表的表头 
            tp.next = A[HASH_NUM];
            fseek(fp, (HASH_NUM+1)*b1+p*b2, 0);
            fwrite((char *)&tp, b2, 1,fp); 
            A[HASH_NUM] = p; 
            //结束while循环 
            break; 
        } 
        else 
        { 
            //使p指针的值赋给q，tp结点的值赋值给tq结点 
            q = p; 
            tq = tp; 
            //p指向单链表中的下一个结点 
            p = tp.next; 
        }//if分支结束 
    }//while循环结束 

    //将文件指针移到文件头部，并将散列文件的表头重新写入散列文件 
    fseek(fp, 0L, 0); 
    fwrite((char *)A, (HASH_NUM + 1) * b1, 1, fp);
    //释放A数组申请的内存空间 
    free(A); 
    //关闭散列文件 
    fclose(fp); 

    if(-1 == p) 
    { 
        return 0;   //没有找到要删除的结点 
    }    
    else 
    { 
        return 1;   //成功删除要删除的结点 
    }//if分支结构结束 
} 

//从散列文件中查找关键字为x.key的元素，并由x带回 
//元素，若查找成功则返回1，否则返回0 
int HFSearch(char *fname, struct ElemType *x) 
{ 
    int d; 
    int p; 
    int *A; 
    struct FLNode temp; 
    //以读写方式打开散列文件 
    FILE *fp; 
    fp = fopen(fname, "rb+"); 
    if(NULL == fp) 
    { 
        printf("Cannot open this file!\n"); 
        exit(1); 
    } 
    //申请动态数组A 
    A = (int *)calloc(HASH_NUM+1, b1); 
    if(NULL == A) 
    { 
        printf("Momery alloction failare!\n"); 
        exit(1); 
    } 

    fread((char *)A, (HASH_NUM+1)*b1, 1, fp);
    d = x->key % HASH_NUM;
    //取出d单链表的表头指针 
    p = A[d]; 
    //从d点链表中查找关键字为x.key的元素 
    while(p != -1) 
    { 
        fseek(fp, (HASH_NUM+1)*b1 + p*b2, 0);
        fread((char *)&temp, b2, 1, fp); 
        if(temp.data.key == x->key) 
        { 
            *x = temp.data; //被查找到的元素由x带回 
            break; 
        } 
        else 
        { 
            p = temp.next;  //把结点指针移到下一个结点 
        } 
    } 
    //释放A数组申请的内存空间 
    free(A); 
    //关闭散列文件 
    fclose(fp); 

    if(-1 == p) 
    { 
        return 0;    
    }    
    else 
    { 
        return 1;    
    }//if分支结构结束 
} 

//顺序打印出散列文件中的每个单链表中的每个结点位置序号及元素值 
void HFPrint(char *fname) 
{ 
    int i; 
    int p; 
    int *A; 
    struct FLNode pn; 
    //以读写方式打开散列文件 
    FILE *fp; 
    fp = fopen(fname, "rb+"); 
    if(NULL == fp) 
    { 
        printf("Cannot open this file!\n"); 
        exit(1); 
    } 
     
    //申请动态数组A 
    A = (int *)calloc(HASH_NUM+1, b1);
    if(NULL == A) 
    { 
        printf("Momery alloction failare!\n"); 
        exit(1); 
    } 

    fread((char *)A, (HASH_NUM+1)*b1, 1, fp);

    for(i = 0; i < HASH_NUM+1; i++)
    { 
        printf("%d:", i); 
        p = A[i]; 
        while(-1 != p) 
        { 
            fseek(fp, (HASH_NUM+1)*b1 + p*b2, 0); 
            fread((char *)&pn, b2, 1, fp); 
            printf("%d->%d  ", p, pn.data.key); 
            p = pn.next; 
        } 
        printf("\n"); 
    } 
     
    //删除动态数组A申请的内存 
    free(A); 
    //关闭散列文件 
    fclose(fp); 
} 

//main函数 
void main() 
{ 
    struct ElemType x; 
    int number; //选择的功能号表 
    char ch; 
    //定义tag用于保存或查找函数的返回值 
    int tag; 
    //定义散列文件的名字，为字符指针filename指向的字符串 
    char filename[128]; 
    strcpy(filename, "Hash"); 

    //检测散列文件是否存在 
    existHash(filename); 

    while(1) 
    { 
        printf("\n"); 
        printf("\03-----------------------------------\03\n"); 
        printf("\03------------ 散列文件 -------------\03\n"); 
        printf("\03 1---- 初始化散列文件 -------------\03\n"); 
        printf("\03 2---- 向散列文件中插入一个元素 ---\03\n"); 
        printf("\03 3---- 从散列文件中删除一个元素 ---\03\n"); 
        printf("\03 4---- 从散列文件中查找一个元素 ---\03\n"); 
        printf("\03 5---- 打印散列文件 ---------------\03\n"); 
        printf("\03 0---- 结束运行 -------------------\03\n"); 
         
        printf("\03 请输入你的选择(1-5):"); 
        scanf("%d", &number); 

        switch(number) 
        { 
            case 0: 
                return; 
            case 1: 
                //初始化散列文件 
                printf("确实要重新初始化散列文件(y/n)？"); 
                getchar(); 
                scanf("%c", &ch); 
                if('y' == ch || 'Y' == ch) 
                { 
                    //重新初始化散列文件 
                    InitHashFile(filename);  
                    printf("--- 重新初始化散列文件完毕! ---\n"); 
                } 
                else 
                { 
                    printf("--- 未执行重建散列文件操作! ---\n"); 
                } 
                break; 
            case 2: 
                //向散列文件中插入一个元素 
                printf("输入待插入元素x的值(一个整数和一个字符串(长度小于10)):\n"); 
                scanf("%d", &x.key); 
                scanf("%s", &x.rest); 
                HFInsertOne(filename, x); 
                break; 
            case 3: 
                //从散列文件中删除一个元素 
                printf("输入待删除元素x的关键字："); 
                scanf("%d", &x.key); 
                tag = HFDelete(filename, &x); 
                if(1 == tag) 
                { 
                    printf("--- 删除成功!%d %s ---\n", x.key, x.rest); 
                } 
                else 
                { 
                    printf("--- 删除失败 ---\n"); 
                }   //if分支结构结束 
                break; 
            case 4: 
                //从散列文件中查找一个元素 
                printf("输入待查找元素x的关键字：\n"); 
                scanf("%d", &x.key); 
                tag = HFSearch(filename, &x); 
                if(1 == tag) 
                { 
                    printf("--- 查找成功!%d %s ---\n", x.key, x.rest); 
                } 
                else 
                { 
                    printf("查找失败!\n"); 
                } 
                break; 
            case 5: 
                //打印散列文件 
                HFPrint(filename); 
                break; 
            default: 
                printf("\n--- 输入功能号表错误 ---\n"); 
                break; 
        }   //switch结束 

        printf("--- 按任意键继续 ---\n"); 
        getch();    //接收任意字符 
    } 
} 

//---------------------------------------------------------------------------