strcmp发生冲突

strcmp函数是C语言中用于比较两个字符串的函数。它的原型为：

int strcmp(const char *str1, const char *str2);

该函数会比较两个字符串str1和str2的内容，并返回一个整数值，表示它们的大小关系。具体而言，返回值为0表示两个字符串相等，返回值大于0表示str1大于str2，返回值小于0表示str1小于str2。

当使用strcmp函数时，可能会出现冲突的情况。一种常见的冲突是在比较字符串时，忽略了字符串的长度限制。如果字符串的长度超过了函数所能处理的范围，就可能导致内存越界或者其他错误。

另一种冲突是在比较字符串时，没有考虑到字符串的编码方式。strcmp函数是按照字符的ASCII码值进行比较的，如果字符串中包含非ASCII字符（如中文字符），就可能导致比较结果不准确。

为了避免这些冲突，可以使用更安全的字符串比较函数，如strncmp函数。strncmp函数在比较字符串时，可以指定比较的长度，并且可以指定字符的编码方式。

相关问题

用c语言探究冲突处理方法对散列函数平均查找长度的影响规律，给出相应代码及测试数据用例和预期实验结果

散列表是一种用于快速访问数据的数据结构，它通过将数据映射到一个固定范围的索引位置来实现快速访问。散列函数是将数据映射到索引位置的算法，但是当多个数据映射到同一个索引位置时，就会产生冲突。因此，散列函数的冲突处理方法对散列表的性能有很大影响。

常见的冲突处理方法有开放定址法、链地址法和再散列法。开放定址法是在冲突发生时，以一定的步长在散列表中寻找下一个空闲位置。链地址法是将散列到同一位置的数据存储在同一个链表中。再散列法是在冲突发生时，使用另一个散列函数重新计算索引位置。

下面是一份用C语言实现散列表并比较不同冲突处理方法对平均查找长度的影响的代码：

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

#define TABLE_SIZE 100
#define MAX_LENGTH 20

typedef struct node {
    char *key;
    int value;
    struct node *next;
} Node;

typedef struct hash_table {
    Node **table;
    int size;
} HashTable;

unsigned int hash(char *str) {
    unsigned int hash = 5381;
    int c;

    while ((c = *str++))
        hash = ((hash << 5) + hash) + c;

    return hash;
}

Node *create_node(char *key, int value) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

HashTable *create_table(int size) {
    HashTable *table = (HashTable *) malloc(sizeof(HashTable));
    table->table = (Node **) malloc(sizeof(Node *) * size);
    table->size = size;

    for (int i = 0; i < size; i++)
        table->table[i] = NULL;

    return table;
}

void set(HashTable *table, char *key, int value, int method) {
    unsigned int index = hash(key) % table->size;
    Node *node = table->table[index];

    if (node == NULL) {
        table->table[index] = create_node(key, value);
        return;
    }

    while (node->next != NULL && strcmp(node->key, key) != 0)
        node = node->next;

    if (strcmp(node->key, key) == 0) {
        node->value = value;
        return;
    }

    Node *new_node = create_node(key, value);

    if (method == 1) { // 开放定址法
        int i = 1;

        while (node->next != NULL) {
            index = (hash(key) + i) % table->size;
            node = table->table[index];
            i++;
        }

        table->table[index] = new_node;
    } else if (method == 2) { // 链地址法
        node->next = new_node;
    } else { // 再散列法
        unsigned int new_index = (hash(key) * 2 + 1) % table->size;
        table->table[new_index] = new_node;
    }
}

int get(HashTable *table, char *key) {
    unsigned int index = hash(key) % table->size;
    Node *node = table->table[index];

    while (node != NULL) {
        if (strcmp(node->key, key) == 0)
            return node->value;

        node = node->next;
    }

    return -1;
}

int main() {
    HashTable *table;
    char keys[10][MAX_LENGTH] = {"hello", "world", "apple", "banana", "orange", "pear", "watermelon", "grape", "lemon", "peach"};

    // 开放定址法
    table = create_table(TABLE_SIZE);
    for (int i = 0; i < 10; i++)
        set(table, keys[i], i, 1);

    int sum = 0;
    for (int i = 0; i < 10; i++)
        sum += get(table, keys[i]);

    printf("开放定址法平均查找长度：%f\n", (double) sum / 10);

    // 链地址法
    table = create_table(TABLE_SIZE);
    for (int i = 0; i < 10; i++)
        set(table, keys[i], i, 2);

    sum = 0;
    for (int i = 0; i < 10; i++)
        sum += get(table, keys[i]);

    printf("链地址法平均查找长度：%f\n", (double) sum / 10);

    // 再散列法
    table = create_table(TABLE_SIZE);
    for (int i = 0; i < 10; i++)
        set(table, keys[i], i, 3);

    sum = 0;
    for (int i = 0; i < 10; i++)
        sum += get(table, keys[i]);

    printf("再散列法平均查找长度：%f\n", (double) sum / 10);

    return 0;
}

其中，`set`函数用于插入数据，`get`函数用于查找数据。`method`参数指定了冲突处理方法，1表示开放定址法，2表示链地址法，3表示再散列法。`main`函数测试了三种不同的冲突处理方法，并输出了平均查找长度。

这里给出一个测试数据例子：

hello 0
world 1
apple 2
banana 3
orange 4
pear 5
watermelon 6
grape 7
lemon 8
peach 9

预期实验结果是，开放定址法的平均查找长度应该最小，再散列法的平均查找长度应该略小于链地址法的平均查找长度。但是，这个结果可能会因为数据分布的不同而有所不同。

为班级42个人的姓名设计一个哈希表，假设姓名用汉语拼音表示。要求用线性探测再散列法处理冲突，平均查找长度的上限为2。 编写数据结构和算法来实现。c语言

好的，我来回答你的问题。

首先，我们需要确定哈希表的大小，为了方便，我们可以选择一个大于等于 42 的质数，比如 47。然后，我们需要确定哈希函数，可以选择将姓名的拼音转化为一个整数，然后对哈希表的大小取模得到其在哈希表中的位置。具体的哈希函数可以自行设计。

接下来，我们需要解决冲突的问题。我们采用线性探测再散列法，即当发生冲突时，我们顺序查找哈希表中的下一个位置，直到找到一个空的位置为止。如果到达了哈希表的末尾，则从头开始继续查找。

为了保证平均查找长度的上限为 2，我们需要控制哈希表的填装因子，即哈希表中元素的数量与哈希表大小的比值。一般来说，填装因子应该小于等于 0.5，这样可以保证哈希表的性能。

下面是一个简单的 C 语言实现：

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

#define SIZE 47 // 哈希表大小
#define MAX_NAME_LEN 20 // 最大姓名长度
#define MAX_PROBE_LEN 2 // 最大查找长度

typedef struct {
    char name[MAX_NAME_LEN];
} Person;

typedef struct {
    Person* data[SIZE];
} HashTable;

int hash(char* name) {
    // 哈希函数
    int sum = 0;
    for (int i = 0; i < strlen(name); i++) {
        sum += name[i];
    }
    return sum % SIZE;
}

int probe(int pos, int i) {
    // 探测函数
    return (pos + i) % SIZE;
}

void insert(HashTable* ht, Person* p) {
    int pos = hash(p->name);
    int i = 0;
    while (ht->data[pos] != NULL) {
        i++;
        if (i > MAX_PROBE_LEN) {
            printf("Error: Hash table is full!\n");
            exit(1);
        }
        pos = probe(pos, i);
    }
    ht->data[pos] = p;
}

Person* find(HashTable* ht, char* name) {
    int pos = hash(name);
    int i = 0;
    while (ht->data[pos] != NULL && strcmp(ht->data[pos]->name, name) != 0) {
        i++;
        if (i > MAX_PROBE_LEN) {
            printf("Error: Person not found!\n");
            exit(1);
        }
        pos = probe(pos, i);
    }
    return ht->data[pos];
}

int main() {
    // 初始化哈希表
    HashTable ht;
    for (int i = 0; i < SIZE; i++) {
        ht.data[i] = NULL;
    }

    // 插入数据
    Person p1 = {"zhangsan"};
    insert(&ht, &p1);
    Person p2 = {"lisi"};
    insert(&ht, &p2);
    Person p3 = {"wangwu"};
    insert(&ht, &p3);

    // 查找数据
    Person* result = find(&ht, "lisi");
    printf("%s\n", result->name);

    return 0;
}