哈希表2- 数据结构(C语言)

插入哈希表

1. 这一课我们来学习下如何把元素插入到哈希表里。我们来简单看下插入算法；调用seach 函数，如果哈希表里已有该元素则不做处理；如果冲突次数没达到哈希表长度的一半，则插入到哈希表；如果冲突次数达到哈希表长度的一半，则需要重建哈希表，表示插入失败。
   首先，我们先写好插入函数insert 的定义，insert 是一个返回值类型位int 的 函数，有两个参数，第一个HashTable 类型的指针参数h, 另一个是char 类型的数组 参数value ,value 表示要插入的关键字。
2. 先定义两个int 变量 pos 和 times .search 函数的参数里也有这两个变量的指针形式，他们的作用是一样的，pos 记录关键字value 可以插入的位置，times 记录查找过程中发生的冲突次数。我们需要两个关键字 value 可以插入的位置， times 记录查找过程中发生的冲突次数。我们需要用这两个变量记录查找后value 可以插入的位置，还有发生的冲突次数。
3. 接下来我们调用search 函数看哈希表是否存在value , 这里我们做个标记，如果哈希表存在关键字 value 则 返回 2 结束函数。
   调用search 函数参数依次是h, value, &ops, &times, pos, 和 times 要用引用形式，因为我们要记录变量的值。
4. 如果没有找到value, 那么我们来分析下一种情况， 如果冲突次数 times 小于 哈希表长度一半，冲突次数不是很多表明可以把 value 插入到哈希表里。
5. 如果冲突次数 太多，那么我们就把value 插入到 哈希表里，我们已经通过search 函数找到了 value 可以插入的地方 pos.
   我们先为它分配一块 char * 类型， 大小为 strlen(value) + 1 的内存空间， 然后使用strcpy 函数把value 插入到哈希数组的 第 pos 位 即可。插入后我们再返回 1 结束函数 ，这里我们设置的第二个标记。
6. 我们已经分析了两种情况，剩下的一种情况就是冲突次数达到哈希表数组的一半。因为是最后一种情况，所以这里我们就用else 语句来实现，我们先把else 语句写好吧，稍后再来实现。
7. 这时我们就需要重建哈希表再重新调用 insert 函数 执行插入操作了，调用recreate 函数（参数h） 即可完成哈希表的重建。稍后我们会来学习如何重建哈希表，这里我们先在这两行代码前面加上注释。 最后我们返回0 结束方法，这是我们设置第三个标记。
8. 这样我们就插入函数 insert 写完了， 接下来我们在主函数里输入 n 个 字符串，然后利用 insert 函数- 插入到 哈希表里。
   首先我们来定义两个变量， 一个是char 类型的数组buffer , 大小设置为1000 , 表示输入的字符串；另一个是int 类型的n, 表示有 n 个字符串 。 定义完两个变量后，我们让程序输入n.
9. 接下来我们写一个 for 循环，， 用int 变量 i 从 1 循环到不小于等于 n 时退出，输入字符串buffer, 然后利用insert 函数将其插入到哈希表里，这一步我们把for 循环写好实现即可.
10. 我们先让程序输入buffer , 然后调用 insert 函数，将buffer 插入到哈希表hashtable 中，然后再定义一个int类型的变量 ans 用来接收函数insert 的返回值。
11. 还记得我们在insert 函数里设置的三个标记么，现在排上用场了，首先是ans 为0 的情况，它表示冲突次数达到哈希表长度的一半，需要重建哈希表。如果ans 为 0， 我们就让程序输出recreate while insert ! 作为提示，之后再输出一个换行。
12. 接下来 我们讨论 ans 为 1 的情况，此时关键字成功插入到哈希表里，那么我们就让程序输出 insert success! 作为提示，之后输出一个换行，这里我们用else if 完成。
13. 接下来我们来讨论 ans 为 2 的情况，它表示哈希表里已经存在该关键字了。如果ans 为2 ，那么我们就让程序输出 It already exists ! 作为提示，之后再输出一个换行。这里用 else if 语句实现。
14. 我们往哈希表里插入 n 个 字符串 后，接下来我们输入一个字符串buffer, 并调用 search 函数来查找是否在哈希表 h 里存在该字符串buffer .
    因为search 函数除了变量 value , 还是有两个指针变量 pos和 times , 分别用来记录元素可以插入的位置和发生冲突的次数。所以我们首先在for 循环后面，定义两个int 类型的临时变量 temp_pos 和 temp_times , 然后让程序输入 buffer .
15. 接下来我们调用search 函数完成哈希表 hashtable 对buffer 的查找，参数依次是 hashtable, buffer , &temp_pos , &temp_times. 如果返回为真，那么就提示查找成功。 这一步先把if 条件语句写好。
16. 如果返回1 ，也就是查找成功，那么我们输出search success! 作为提示，为了显示美观，输出后再输出换行。
17. 我们已经处理了serach 函数返回1 的情况，如果返回0，查找失败，那么我们就让程序输出search failed! 作为提示，之后再输出一个换行，这里用else 实现。

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

typedef struct HashTable {
    char **elem;
    int size;
} HashTable;

void init(HashTable *h);
int hash(HashTable *h, char value[]);
int search(HashTable *h, char value[], int *pos, int *times);
int insert(HashTable *h, char value[]);

void init(HashTable *h) {
    h->size = 2000;
    h->elem = (char **)malloc(sizeof(char *) * h->size);
    for (int i = 0; i < h->size; i++) {
        h->elem[i] = NULL;
    }
}

int hash(HashTable *h, char value[]) {
    int code = 0;
    for (size_t i = 0; i < strlen(value); i++) {
        code = (code * 256 + value[i] + 128) % h->size;
    }
    return code;
}

int search(HashTable *h, char value[], int *pos, int *times) {
    *pos = hash(h, value);
    *times = 0;
    while (h->elem[*pos] != NULL && strcmp(h->elem[*pos], value) != 0) {
        (*times)++;
        if (*times < h->size) {
            *pos = (*pos + 1) % h->size;
        } else {
            return 0;
        }
    }
    if (h->elem[*pos] != NULL && strcmp(h->elem[*pos], value) == 0) {
        return 1;
    } else {
        return 0;
    }
}

// 请在下面实现插入函数 insert
int insert(HashTable *h, char value[]) {
    
    int pos, times;
    if (search(h, value, &pos, &times)) {
        return 2;
    } else if (times < h->size / 2 ) {
         //  如果 冲突的次数不多，那么我们就把value 插入到 哈希表里。 我们已经通search
         //  函数找到了 value  可以 插入的地方 pos   我们先为 它分配 一块 char *  类型 ，
        //大小为 strlen(value) + 1 的内 空间 ， 然后 使 strcpy  函数  把 value插入到  
        // 哈希数组的 第 pos 位即可.
        h->elem[pos] = (char *)malloc(strlen(value)  + 1);
        strcpy(h->elem[pos],  value);
        return 1;
    } else {
    
        return 0;
    }
}

void clear(HashTable *h) {
    for (int i = 0; i < h->size; ++i) {
        if (h->elem[i] != NULL) {
            free(h->elem[i]);
        }
    }
    free(h->elem);
    free(h);
}



int main() {
    HashTable *hashtable = (HashTable*)malloc(sizeof(HashTable));
    init(hashtable);
     //  设置是 char 类型的  数组 buffer， 大小设置为 1000
    
    char buffer[1000];
    int n;
    scanf("%d", &n); 
    for(int i = 1; i <= n; i++) {
        scanf("%s", buffer);
        int ans = insert(hashtable,buffer);
        if (ans == 0) {
            printf("recreate while insert!\n");
        } else if (ans == 1) {
            printf("insert success!\n");
        } else if (ans == 2) {
            printf("It already exists!\n");
        }
    }
    int temp_pos, temp_times;
    scanf("%s", buffer);
    if(search(hashtable, buffer, &temp_pos, &temp_times)) {
        printf("search success!\n");
    } else {
        printf("search failed!\n");
    }
   
    clear(hashtable);
   
    
    return 0;
}