散列表外拉链法处理冲突

系统管理员 2022-05-21 12:24 167阅读 0赞

散列表线性探测法外拉链法  
![这里写图片描述][70]

#include <iostream>
    #include <algorithm>
    using namespace std;
    struct Node
    {
        int key;
        Node *next;
    };
    Node HashTable[13];
    int a[13];
    int InsertHT(int x,int w)
    {
        int adr;
        Node *p;
        adr=x%w;
        p=&HashTable[adr];
        while(p->next)
        {
            if(p->next->key==x)
            return -1;
            p=p->next;
        }
        Node *s;
        s=new Node;
        s->key=x;
        s->next=p->next;
        p->next=s;
        return 1;
    }
    void CreateHT(int n,int m,int p)
    {
        for(int i=0;i<n;i++)
        {
            HashTable[i].key=i;
            HashTable[i].next=NULL;
        }
        for(int i=0;i<m;i++)
            InsertHT(a[i],p);
    }
    void Display(int n,int m)
    {
       int add[13],j,count;
       Node *q;
       for(int i=0;i<13;i++)
       {
           j=0;count=0;
           q=(&HashTable[i])->next;
           while(q!=NULL)
           {
               add[j]=q->key;
               j++;
               count++;
               q=q->next;
           }
           sort(add,add+count);
           q=(&HashTable[i])->next;
           j=0;
           while(q!=NULL)
           {
               q->key=add[j];
               j++;
               q=q->next;
           }
       }
       cout<<" "<<0<<endl;
       for(int i=1;i<13;i++)
       {
           q=&HashTable[i];
           cout<<" ";
           while(q->next!=NULL)
           {
               cout<<q->key<<" ";
               q=q->next;
           }
           cout<<q->key<<endl;
       }
    }
    int main()
    {
        for(int i=0;i<13;i++)
        cin>>a[i];
        CreateHT(13,13,13);
        Display(13,13);
        return 0;
    }

[70]: /images/20220521/383ce164c4114f87afe1cec1985c5c80.png