hnust 1968 链地址法的哈希表

            理解一下题目意思，给出了一个n，所谓的地址x(我设的)其实就是（插入的数%n），x也就是哪条链。接下来的插入，查找和删除就和我们以前学的链表差不多了，代码中都有注释的！！

#include 
#include 
#include 
using namespace std;

typedef struct node
{
    int key;
    struct node *next;
} Node, *PNode;

typedef struct
{
    PNode *elem;
    int sz; //size of hashtable
} HashTable;

void InitHashTable(HashTable &ht, int n)
{
    ht.sz = n;
    ht.elem = new PNode[n]();
}


//将k插入ht中对应的链表尾部，如果表中k已经存在，直接返回false，否则插入k后返回true
bool InsertHashTable(HashTable &h, int k)
{
    
    int x=k%h.sz;//判断是哪条链
    Node *ht=h.elem[x];
    if(h.elem[x]==NULL)//头节点可能没有值
    {
        h.elem[x]=new Node;
        h.elem[x]->key=k;
        h.elem[x]->next=NULL;
        return 1;
    }
    while(ht->next)//循环到链尾
    {
        //cout<key<<" ";
        if(ht->key==k)return 0;//已经存在了
        ht=ht->next;
    }
    if(ht->key==k)//最后一个值上面的循环没判断
    {
        return 0;
    }

    Node *t=new Node;//在链尾加结点
    t->key=k;
    t->next=NULL;
    ht->next=t;

    return 1;
    
}

//如果表中存在k，返回指向对应结点的指针，否则返回NULL
PNode SearchHashTable(HashTable h, int k)
{
    
    int x=k%h.sz;
    HashTable ht=h;
    while(ht.elem[x])//一直找过去就行了
    {
        if(ht.elem[x]->key==k)return ht.elem[x];
        ht.elem[x]=ht.elem[x]->next;
    }
    return 0;
    
}

//删除表中韩关键字k的结点并返回true。如果不存在，直接返回false。
bool DeleteHashTable(HashTable &ht, int k)
{
    

    int x=k%ht.sz;//判断是哪条链
    Node *h;
    if(h)//这条链存在
    {
        //cout<<"           "<key==k)//第一个就是要找的值
        {
            ht.elem[x]=h->next;
            return 1;
        }
        while(h->next)//找到要删的前一个结点
        {
            if(h->next->key==k)
            {
               // cout<key<<"zhanfe:";
                h->next=h->next->next;//要删结点的前一个结点直接指到下一个结点
                return 1;
            }
            h=h->next;
        }

    }

    return 0;
    
}

static void PrintLinklist(PNode h)
{
    for(PNode p = h; p; p = p->next)
    {
        cout << "->" << p->key;
    }
    cout << endl;
}

void  PrintHashTable(HashTable ht)
{
    cout << "Print the hash tablen";
    for(int i = 0; i < ht.sz; i++)
    {
        cout << '[' << i << ']';
        PrintLinklist(ht.elem[i]);
    }
}

void DestroyHashTable(HashTable &ht)
{
    //You should do this!
}

int main()
{
    int n;
    HashTable ht;
    string op;
    cin >> n;
    InitHashTable(ht, n);
    while(cin >> op)
    {
        int k;
        if(op == "insert")
        {
            cin >>  k;
            if(!InsertHashTable(ht, k))
                cout << k << " is " <<  "already existed in hash tablen";
        }
        else if(op == "search")
        {
            cin >>  k;
            cout << k << " is" << (SearchHashTable(ht, k) ? "" : " not") << " foundn";
        }
        else if(op == "delete")
        {
            cin >>  k;
            if(DeleteHashTable(ht, k))
            {
                PrintHashTable(ht);
            }
            else
                cout << k << " is " <<  "not existed in hash tablen";
        }
        else if(op == "print")
        {
            PrintHashTable(ht);
        }
    }
    DestroyHashTable(ht);
    return 0;
}