哈希表操作

向右看齐 2022-04-14 06:12 190阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    #define HASHTABLE_LINE 1000
    
    typedef int ElemType;
    typedef struct hashNode
    {
        ElemType site;
        ElemType key;
        struct hashNode*next;
    } HashNode,*pHNode;
    typedef struct  hashHead
    {
        int count;
        HashNode*head;
    
    } headNode;
    typedef struct hNode
    {
        headNode HT[HASHTABLE_LINE];//哈希表表头数组
        int length;//长度
    
    } HashTable;
    
    //初始化哈希表
    HashTable* init_hashTable()
    {
        HashTable* ht=(HashTable*)malloc(sizeof(HashTable));
        ht->length=0;
        int i;
        for(i=0; i<HASHTABLE_LINE; i++)
        {
            ht->HT[i].count=0;//哈希表每个数量初始化为空
            ht->HT[i].head=NULL;//整个哈希表的头结点初始化为空
    
        }
        printf("哈希表初始化成功!\n");
        return ht;
    }
    
    //哈希函数求出关键字的地址
    ElemType hash(ElemType key)
    {
        int h=key%10+1;
        return h;
    }
    
    //在哈希表中查询该元素是否存在,如果存在将不会插入该元素
    int searchByKey(HashTable*ht,ElemType h,ElemType key)
    {
        HashNode*p=ht->HT[h].head;
        while(p)
        {
            if(p->key==key)
            {
                return p->site;
            }
            p=p->next;
    
        }
        return 0;
    }
    
    //在哈希表中插入一个元素
    int hash_insertKey(HashTable*ht,ElemType key)
    {
        int h=hash(key);//把关键字用哈希函数处理得到一个哈希地址
        if(searchByKey(ht,h,key))      //查找此关键字在表中是否存在
        {
            printf("该关键字在表中已经存在!\n");
            return 0;
        }
        if(ht->HT[h].head==NULL)    ht->length+=1;//基本表为空时
        pHNode p=(pHNode)malloc(sizeof(HashNode));
        if(!p)
        {
            printf("空间分配失败！");
            exit(1);
        }
        p->key=key;
        p->site=h;
        p->next=ht->HT[h].head;
        ht->HT[h].head=p;
        ht->HT[h].count++;
        //printf("插入成功!");
        return 1;
    }
    int modify_hashElem(HashTable*ht,ElemType key,ElemType mKey)
    {
    
           int h=hash(key);
           int h2=hash(mKey);
           HashNode *p=NULL;
           if(searchByKey(ht,h2,mKey))
           {
                 printf("要修改到的元素已经存在!\n");
                 return 0;
           }
           if(searchByKey(ht,h,key))
           {
                 p=ht->HT[h].head;
                 while(p)
                 {
                       if(p->key==key)
                       {
                             p->key=mKey;
                             printf("修改成功!");
                             return 1;
                       }
                       p=p->next;
                 }
    
           }
           printf("未找到要修改元素!");
           return 0;
    
    }
    int hash_deleteKey(HashTable*ht,ElemType key)
    {
        int h=hash(key);
        HashNode *p=NULL;
    
        if(searchByKey(ht,h,key))//查询
        {
    
    
            p=ht->HT[h].head;
            if(p->next==NULL)
            {
                //  printf("删除只有一个结点的!\n");
                ht->HT[h].head=NULL;
                ht->length=0;
                free(ht->HT[h].head);
                printf("删除成功!\n");
                return 1;
            }
    
            if(p->key==key)//如果头结点为关键字
            {
                HashNode*q=p->next;
                ht->HT[h].head=q;
                free(p);
                printf("删除成功!\n");
                ht->HT[h].count--;
                return 1;
    
    
            }
            while(p->next)
            {
    
    
                if(p->next->key==key)
                {
                    HashNode *q=p->next;
                    p->next=q->next;
                    free(q);
                    printf("删除成功!\n");
                    ht->HT[h].count--;
                    return 1;
                }
    
                p=p->next;
            }
        }
        else
        {
            printf("该元素不存在!\n");
        }
        return 0;
    }
    
    //打印哈希表
    void print_hashList(HashTable*ht)
    {
        int i;
        HashNode*p;
        for(i=0; i<HASHTABLE_LINE; i++)
        {
            p=ht->HT[i].head;
            while(p)
            {
                printf("key:%d  site: %d\n",p->key,p->site);
                p=p->next;
            }
        }
    }
    
    int main()
    {
        HashTable* ht;
        int n,i,a[HASHTABLE_LINE],delElem,insertElem,key,mKey,operate;
        printf("\t\t\t\t**********哈希表操作************\n");
        printf("\t\t\t\t*                              *\n");
        printf("\t\t\t\t*       1.创建哈希表           *\n");
        printf("\t\t\t\t*       2.添加一个元素         *\n");
        printf("\t\t\t\t*       3.删除一个元素         *\n");
        printf("\t\t\t\t*       4.修改一个元素         *\n");
        printf("\t\t\t\t*       5.打印哈希表           *\n");
        printf("\t\t\t\t*       0.结束                 *\n");
        printf("\t\t\t\t*                              *\n");
        printf("\t\t\t\t*                              *\n");
        printf("\t\t\t\t********************************\n");
    
        while(1)
        {
            printf("请输入操作(0-4):");
            scanf("%d",&operate);
            switch(operate)
            {
            case 1:
                ht=init_hashTable();
                printf("请输入元素个数:\n");
                scanf("%d",&n);
                printf("请输入%d个元素:\n",n);
                for(i=0; i<n; i++)
                {
                    scanf("%d",&a[i]);
                    hash_insertKey(ht,a[i]);
                }
                break;
            case 2:
                printf("请输入一个元素:\n");
                scanf("%d",&insertElem);
                hash_insertKey(ht,insertElem);
                break;
            case 3:
                printf("请输入要删除的元素关键字:\n");
                scanf("%d",&delElem);
                hash_deleteKey(ht,delElem);
                break;
            case 4:
                  printf("请输入要修改的元素关键字和修改后元素关键字:\n");
                 scanf("%d %d",&key,&mKey);
                 modify_hashElem(ht,key,mKey);
                break;
            case 5:
                print_hashList(ht);
                break;
            case 0:
                exit(0);
                break;
            default:
                printf("输入错误\n");
                break;
            }
            printf("请按任意键继续..\n");
            getch();
            continue;
        }
    
        return 0;
    }