实现散列查找（数据结构与算法 - 查找）

柔光的暖阳◎ 2023-05-21 08:43 11阅读 0赞

#### 相关知识 ####

本关讨论散列存储，散列函数使用除留余数法，冲突解决方法采用独立链表地址法。假设有 8 个关键码： 7 , 15 , 23 , 31 , 12 , 14 , 10 , 17 ，采用散列函数hash(key)=key%7，其存储结构图如图 1 所示，它由 7 个独立链表组成，散列值相同的关键码在同一个链表里，独立链表的头结点组成散列表，一共 7 行，编号 0 , 1 , … , 6 。独立链表的每个结点是一个 struct HNode 结构，其定义如下：

struct HNode 
    { 
        int key; //假设关键码为整数
        HNode* next;
    };

在散列表中，如果表项的key字段等于 0 （假设有效的关键码值不等于 0 ），则表示该行是一条空链表，例如图 1 中编号为 4 和编号为 6 的行。  
散列表的开始地址保存在pn中，散列表的行数为n（图 1 中，n=7），将pn和n组织成结构：

struct LHTable 
    { 
        HNode* pn;  //指向散列表，每个表结点是独立链表的表头结点
        int n; //散列表的长度，一般取（小于等于数据个数的最大）质数
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]  
定义如下操作，各操作函数的功能详见下面给出的代码文件 indLnkHash.cpp 的代码框架：

LHTable* ILH_Create(int n);
    void ILH_Free(LHTable* pt);
    bool ILH_InsKey(LHTable* pt, int x);
    bool ILH_FindKey(LHTable* pt, int x);
    bool ILH_DelKey(LHTable* pt, int x);
    void ILH_Print(LHTable *pt);

输入输出格式说明  
输入格式：  
首先输入一个正整数n，创建一个长n的散列表。  
然后输入多个操作：如果输入 “insert” ，则后面跟一个数x，表示将x插入；如果输入 “delete” ，则后面跟一个数x，表示将x删除；如果输入 “end” ，表示输入结束。  
输出格式：  
输出n个独立链表。  
以下是平台对 step2/Main.cpp 的样例测试集：  
样例输入：

11
    insert 54
    insert 77
    insert 94
    insert 89
    insert 14
    insert 45
    insert 76
    insert 23
    insert 43
    insert 47
    end

样例输出：

0: 
     77
    1:  89  -> 45  -> 23
    2:  -
    3:  14  -> 47
    4:  -
    5:  -
    6:  94
    7:  -
    8:  -
    9:  -
    10:  54  -> 76  -> 43

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include "indLnkHash.h"
    LHTable* ILH_Create(int n)
    //创建散列表, n为表长度，最佳取值：n取小于等于数据个数的最大质数
    { 
        HNode* pn=(HNode*)malloc(sizeof(HNode)*n);
        for (int i=0; i<n; i++) 
        { 
            pn[i].key=0;
            pn[i].next=NULL;
        }
        LHTable* pt=(LHTable*)malloc(sizeof(LHTable));
        pt-> pn=pn;
        pt->n=n;
        return pt;
    }
    void ILH_Free(LHTable* pt)
    //释放散列表
    { 
        if (pt==NULL) return;
        for (int i=0; i<pt->n; i++) 
        { 
            HNode* curr=pt->pn[i].next;
            while (curr) 
            { 
                HNode* next=curr->next;
                free(curr);
                curr=next;
            }
        }
        free(pt->pn);
        free(pt);
    }
    bool ILH_InsKey(LHTable* pt, int x)
    //插入关键码x
    //返回true，表示插入成功
    //返回false，表示插入失败(关键码已经存在)
    { 
        int d=x%pt->n;
        if (pt->pn[d].key==0) 
        { 
            pt->pn[d].key=x;
            return true;
        }
        else if (pt->pn[d].key==x) 
        { 
            return false;
        }  
        HNode* prev=&(pt->pn[d]);
        HNode* curr=pt->pn[d].next;
        while (curr && curr->key!=x) 
        { 
            prev=curr; 
            curr=curr->next;
        }
        if (curr) 
        { 
            return  false;
        }
        HNode* pnode=(HNode*)malloc(sizeof(HNode));
        pnode->key=x;
        pnode->next=NULL;//pt->pn[d].next;
        prev->next=pnode;
        return true;
    }
    bool ILH_FindKey(LHTable* pt, int x)
    //查找关键码x
    //返回true表示找到
    //返回false表示没找到
    { 
        int d=x%pt->n;
        if (pt->pn[d].key==0) 
        { 
            return false;
        }
        else if (pt->pn[d].key==x) 
        { 
            return true;
        }
        HNode* curr=pt->pn[d].next;
        while (curr && curr->key!=x) 
        { 
            curr=curr->next;
        }
        if (curr) 
        { 
            return  true; 
        }
        else 
        { 
            return false;
        }
    }
    bool ILH_DelKey(LHTable* pt, int x)
    //删除关键码
    //返回true表示该关键码存在，且成功删除
    //返回false表示该关键码不存在
    { 
        int d=x%pt->n;//关键码x的散列值d
        if (pt->pn[d].key==0) 
        { 
            return false;
        }
        else if (pt->pn[d].key==x)  
        { 
            if (pt->pn[d].next ==NULL) 
            { 
                pt->pn[d].key=0;
            } 
            else 
            { 
                HNode* first=pt->pn[d].next;
                pt->pn[d].key=first->key;
                pt->pn[d].next=first->next;
                free(first);
            }
            return true;
        }
        HNode* prev=&(pt->pn[d]);
        HNode* curr=pt->pn[d].next;
        while (curr && curr->key!=x) 
        { 
            prev=curr; 
            curr=curr->next;
        }
        if (curr==NULL) 
        { 
            return false;
        }
        prev->next=curr->next;
        free(curr);
        return true;
    }
    void ILH_Print(LHTable *pt)
    { 
        for (int i=0; i<pt->n; i++) 
        { 
            printf("%5d:", i);
            if (pt->pn[i].key) 
            { 
                printf("%d", pt->pn[i].key);
                HNode* curr=pt->pn[i].next;
                while (curr) 
                { 
                    printf("->%d", curr->key);
                    curr=curr->next;
                }
                printf("\n");
            }
            else 
            { 
                printf("-\n");
            } 
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]: /images/20230521/c44150bcfc924cd089d8762d5cf90a33.png