哈希链表的基本操作

#include <stdio.h>
#include <stdlib.h>

#define HASHSIZE 5

typedef struct __Node {
    int val;
    struct __Node *next;
}Node;

int hash(int value) {
    return value % HASHSIZE;
}

void Init_hash(Node **chain) {
    int i;
    for(i=0; i<HASHSIZE; i++) {
        chain[i] = NULL;//初始化每个槽位
    }
}

int Traverse(Node *slot, int value) {
    Node *pNode = slot;
    while(pNode != NULL) {
        if(pNode->val == value) return -1;
        pNode = pNode->next;
    }
    return 0;
}

int Insert(Node **chain) {
    int value, key;
    Node *newNode;
    printf("Please input the value you want to insert: ");
    scanf("%d", &value);

    key = hash(value);
    // 遍历链表避免插入相同的值
    if(Traverse(chain[key], value) == 0) {
        // 申请新节点内存
        if ((newNode = (Node *)malloc(sizeof(Node)))
            != NULL) {
            newNode->val = value;
            // 把新节点插入原第一个节点之前
            newNode->next = chain[key];
            chain[key] = newNode;
            return 0;
        }
    } else {
        printf("the value already existsn");
        return -1;
    }
}

int Delete(Node **chain) {
    int value, key, i = 1;
    Node *pCur, *pPrev;
    printf("Please input the value you want to delete: ");
    scanf("%d", &value);

    key = hash(value);
    pPrev = chain[key];
    pCur = pPrev;
    while(pCur != NULL) {
        if(pCur->val == value) {
            if(i == 1) //如果匹配删除的值是第一个节点,
                chain[key] = pCur->next;
            //把上一个节点直接指向当前节点的下一个节点
            pPrev->next = pCur->next;
            free(pCur);
            return 0;
        }
        //如果没查找到value, 操作下一个节点.
        pPrev = pCur;
        pCur = pCur->next;
        i++;
    }
    printf("Can't find the value!n");
    return -1;
}

void Search(Node **chain) {
    int value, key, flag = 0, i = 1;
    Node *pNode;
    printf("Please input the value you want to search: ");
    scanf("%d", &value);

    key = hash(value);
    pNode = chain[key];

    while(pNode != NULL) {
        if(pNode->val == value) {
            printf("Hit, the value in %d chain %d noden", key, i);
            flag = 1;
            break;
        }
        pNode = pNode->next;
        i++; //计数第几个节点
    }
    if(!flag)    printf("Miss, the value has not been foundn");
    printf("n");
}

void Destroy(Node **chain) {
    int i;
    Node *pCur, *pNext;
    for(i=0; i<HASHSIZE; i++) {
        if(chain[i] != NULL) {
            pCur = chain[i];
            do { //保存下个节点的指针
                pNext = pCur->next;
                //printf("Destroy val = %dn", pCur->val);
                free(pCur); // 释放当前节点内存
                pCur = pNext; //操作下一个节点
            } while(pCur != NULL);
            chain[i] = pCur;
        }
    }
}

void Invert(Node **chain) {
    int i;
    Node *pCur, *pPrev, *pNext;
    for(i=0; i<HASHSIZE; i++) {
        if(chain[i] != NULL) {
            pPrev = chain[i]; //指向第一个节点
            pCur = pPrev->next; //指向第二个节点
            while(pCur != NULL) {
                pNext = pCur->next; //指向第三个节点
                pCur->next = pPrev; //让第中间节点指向前面一个节点
                pPrev = pCur; //上一个节点的指针指向当前节点
                pCur = pNext; //指向当前节点的指针指向下一个节点
            }
        /*
        让指针反向后第一个节点成为最后一个节点,
        所以把原第一个节点的指针域设置为NULL,
        最后一个节点成为了第一个节点, 把它的地址存入哈希表中.
        */
            chain[i]->next = NULL;
            chain[i] = pPrev;
        }
    }
}

void Print_hash(Node **chain) {
    int i;
    Node *pNode;
    printf("n");
    for(i=0; i<HASHSIZE; i++) {
        printf("%d:", i);
        pNode = chain[i];
        while(pNode != NULL) {
            printf("-->%d", pNode->val);
            pNode = pNode->next;
        }
        printf("n");
    }
    printf("n");
}

int main(void) {
    Node *chain[HASHSIZE];
    Init_hash(chain);
    int value = 1;
    while (value) {
        printf("[1]:Insert ");
        printf("[2]:Delete ");
        printf("[3]:Search ");
        printf("[4]:Destroy ");
        printf("[5]:Invert ");
        printf("[0]:Exit ");
        scanf("%d", &value);
        switch (value) {
            case 0:
                return 0;
            case 1:
                Insert(chain);
                break;
            case 2:
                Delete(chain);
                break;
            case 3:
                Search(chain);
                continue;
            case 4:
                Destroy(chain);
                break;
            case 5:
                Invert(chain);
                break;
            default:
                break;
        }
        Print_hash(chain);
    }

    return 0;
}