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

typedef struct HashNode {
    int index;
    int value;
    struct HashNode *next;
} HashNode;

int hashFunction(int index, int size) {
    return index%size;
}

void insert(HashNode *hashTable[], int size, int index, int value) {
    int hashIndex = hashFunction(index, size);
    HashNode *node = hashTable[hashIndex];
    if (node == NULL) {
        HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
        newNode -> index = index;
        newNode -> value = value;
        newNode -> next = NULL;
        hashTable[hashIndex] = newNode;
    } else {
        while (node != NULL) {
            if (node -> index == index) {
                node -> value += value;
                return;
            }
            if (node -> next == NULL) {
                break;
            }
            node = node -> next;
        }
        HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
        newNode -> index = index;
        newNode -> value = value;
        newNode -> next = node -> next;
        node -> next = newNode;
    }
}

void printHashTable(HashNode *hashTable[], int size) {
    for (int i = 0; i < size; i++){
        HashNode *node = hashTable[i];
        while (node != NULL) {
            printf("%d %d\n", node->index, node->value);
            node = node -> next;
        }
    }
}

void freeHashTable(HashNode *hashTable[], int size) {
    for (int i = 0; i < size; i++) {
        HashNode *node = hashTable[i];
        while (node != NULL) {
            HashNode *next = node -> next;
            free(node);
            node = next;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    if (n < 1 || n > 500) {
        printf("n值不在正常范围内\n");
        return 1;
    }
    int hashTableSize = 1000;
    HashNode *hashTable[hashTableSize];
    for (int i = 0; i < hashTableSize; i++) {
        hashTable[i] = NULL;
    }
    for (int i = 0; i < n; i++) {
        int index, value;
        scanf("%d %d", &index, &value);
        insert(hashTable, hashTableSize, index, value);
    }
    printHashTable(hashTable, hashTableSize);
    freeHashTable(hashTable, hashTableSize);
    return 0;
}

​一、问题分析

首先读题，

数据表记录包含表索引index和数值value（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照index值升序进行输出。 

不是特别容易理解,不过看下面的提示(0<=index<=11111111和1<=value<=100000)

应该是给了我们两个正整数:一个是表索引index,另一个是数值value

然后提到了合并

把表索引相同的记录合并

然后又提到了相同索引的数值进行求和运算

输出按照index值(表索引)升序输出

然后看了一下下面的例子,明白了

1.第一行输入给定输入键值对的个数n(1<=n<=500)

2.给定n组键值,每行代表一组键值对,其中左边的数字是表索引index,右边的数字是数值value,中间用空格隔开

3.对于表索引index相同的键值对我们进行合并(但是并不丢弃他们的数值value)

4.合并的时候同时将需要合并的键值对的数值进行求和运算

5.对index进行升序排列

6.输出合并并排序后的键值对

二、解题思路

1.首先定义一个整数n用来接受键值对的数量

2.然后将键值对的数量读取并存储到n中

3.然后开始逐行扫描n次(因为有n行)

4.扫描方式为(这个时候注意到我们默认的代码不就是扫描两个数字吗?难道有什么深意么?)一次扫俩

5.扫描之前要先想好讲他们储存到什么地方,这里想的是定义一个数组array[11111111],然后在读取的时候先把第一个数读到index中然后第二个数读到value中,然后我们array[index] = value

6.这个时候想到了,如果index值相同怎么办呢?所以如果遇到index已经存在的情况下我们直接加(所以要先判断array[index]是否已经赋过值了),如果已经赋过值了那么我们只需要将array[index] += value就可以了

7.扫描完成之后我们只需要对array[index]进行检查,index从小到大,如果被赋值过就输出index和array[index](此时的array[index]相当于value)

三、具体步骤

使用的语言是C

首先我们引入输入输出库#include <stdio.h>这样就可以使用scanf和printf

然后开始主程序int main(void){(打左边大括号的时候就把右边的也打上就不会少

我们先来定义一个整数n

int n;

然后接受n的值scanf("%d",&n);

注意这里对n的值做了一下检查if(n<1 || n>500){如果n的值有问题的话我们需要输出错误信息

printf("n值不在正常范围内\n");

}

int index,value;

int array[11111111] = {0};在加入array的时候想到了我们需要初始化

接下来我们开始逐行扫描for(int i = 0; i < n; i++){

scanf("%d %d",&index,&value);

(这个时候发现还没有定义数组,在前面加上int array[11111111];)

然后我们对index做一个检查,如果array[index]为0(仔细想想不用检查了,因为啥呢,直接加就行了,后面再检查)

array[index] += value;

}

上面的程序完了证明数据已经读取完了下面该输出了

输出的时候我们输出什么呢?排序好的index和value

所以for(int i = 0; i < 11111111; i++){

因为value的值一定大于1所以我们不用担心有漏掉value为0的情况

if(array[i] >0){如果有键值对

我们输出printf("%d %d\n",i,array[i]);

这样就好了

}

}

}

代码如下

#include <stdio.h>

int main(void){

        int n;

        scanf("%d", &n);

        if(n<1 || n>500){

                printf("n值不在正常范围内\n");

                return 1;

        }

        int index,value;

        int array[11111111] = {0};

        for(int i = 0; i < n; i++){

                scanf("%d %d", &index, &value);

                array[index] += value;

        }

        for(int i = 0; i < 11111111; i++){

                if(array[i] > 0){

                        printf("%d %d\n", i, array[i]);

                }

        }

}

测试了一下,内存超限,看了一下题目发现知识点上写着哈希

看来不得不先学一下哈希了

哈希（Hash）在计算机领域有很重要的应用，以下是一些关于哈希的关键知识点：

一、哈希函数

  1. 定义哈希函数是一种将任意长度的数据映射到固定长度数据的函数。例如，对于一个字符串或者一个文件内容等数据，通过哈希函数可以得到一个固定长度的哈希值。常见的哈希函数有 MD5（Message - Digest Algorithm 5）、SHA - 1（Secure Hash Algorithm 1）、SHA - 256 等。
  2. 特性确定性：相同的输入必然得到相同的输出。如果输入数据是A，每次使用同一个哈希函数对A进行计算，得到的哈希值一定相同。高效性：能够快速地计算出哈希值。对于大量数据的处理，快速计算哈希值非常重要，这样才能在实际应用中保证性能。均匀分布：理想情况下，不同的输入数据均匀地映射到哈希值空间。例如，一个好的哈希函数对于不同的输入字符串，其产生的哈希值在整个可能的哈希值范围内应该尽可能均匀分布，避免出现大量输入集中映射到少数几个哈希值的情况。抗碰撞性：很难找到两个不同的输入，使得它们的哈希值相同。虽然从理论上来说，由于哈希值的空间是有限的，而输入数据可以是无限的，必然存在碰撞（两个不同输入得到相同哈希值），但好的哈希函数要使得碰撞很难在实际中发生。

二、哈希表

  1. 结构和原理哈希表是一种数据结构，它使用哈希函数来确定数据的存储位置。哈希表通常由一个数组和一个哈希函数组成。当要插入一个数据时，先通过哈希函数计算出该数据对应的哈希值，然后将数据存储在数组中对应哈希值的位置。例如，哈希函数计算出数据A的哈希值为5，那么A就存储在数组索引为5的位置。查找数据时，也是通过哈希函数计算出要查找数据的哈希值，然后直接到对应的数组位置去查找。这样在理想情况下，插入、查找和删除操作的时间复杂度都可以达到 O (1)。
  2. 解决冲突链地址法：当多个数据通过哈希函数计算得到相同的哈希值（即发生冲突）时，将这些数据以链表的形式存储在该哈希值对应的数组位置。例如，数据A和B都映射到哈希值3，那么在数组索引为3的位置存储一个链表，A和B作为链表的节点。开放定址法：当发生冲突时，按照一定的规则寻找下一个空闲的存储位置。例如，线性探测法是按照顺序依次查找下一个空闲位置来存储冲突的数据。

三、哈希的应用

  1. 数据加密哈希函数可以用于加密数据。例如，在用户登录系统中，用户的密码通常不以明文形式存储，而是存储密码的哈希值。当用户登录时，输入的密码经过哈希计算后与存储的哈希值进行比较，如果相同则允许登录。这样即使数据库被泄露，攻击者也很难直接获取用户的密码。
  2. 数据完整性验证对于文件或者数据传输，可以通过哈希值来验证数据的完整性。发送方在发送数据前计算数据的哈希值并发送给接收方，接收方收到数据后自己计算哈希值，如果两者相同，则说明数据在传输过程中没有被篡改。
  3. 缓存系统在缓存系统中，哈希表可以用来快速定位缓存的数据。例如，一个网页缓存系统，通过对网页的 URL 进行哈希计算，快速找到对应的缓存网页内容，提高访问速度。

使用哈希的思路:

首先我们还是#include <stdio.h>包含我们的输入输出头文件,以使用scanf和printf函数

因为需要使用哈希,所以我们要引入一个库#include "uthash.h"这样我们就可以使用以下的三个函数了

  1. HASH_FIND_INT功能：在哈希表中查找特定整数键（index）对应的节点。用法：HASH_FIND_INT(hashTable, &index, node);，它会在hashTable中查找键值等于index的节点，并将找到的节点（如果存在）赋值给node变量。
  2. HASH_ADD_INT功能：向哈希表中添加一个新节点。用法：HASH_ADD_INT(hashTable, index, node);，它将node添加到hashTable中，使用index作为键来确定节点在哈希表中的位置。
  3. HASH_DEL功能：从哈希表中删除一个节点。用法：HASH_DEL(hashTable, current);，它会从hashTable中删除current节点。

这些函数是uthash库特有的，用于方便地实现哈希表的操作，包括查找、插入和删除节点等功能。

可以看到HASH_FIND_INT(哈希表,索引,返回节点),就是说我们可以将(已经存在在)哈希表的某一个索引的值返回给node,HASH_ADD_INT(哈希表,索引,输入节点)利用这个函数我们将新建的节点加入到哈希表中,HASH_DEL(哈希表,当前节点)利用这个函数我们可以删除表中的节点

包含了库之后因为使用了哈希表所以我们定义一下表结构typedef struct {开始定义一个结构体类型(结构体可以将很多不同类型的数据组合在一起,一个结构体可以包含多种多个变量)

然后我们需要在结构体中定义一个int index;用来存储索引值

定义一个int value;用来储存数值

还需要注意定义我们的UT_hash_handle hh;他是我们使用哈希表的关键,UT_hash_handle是uthash库提供的,他可以帮助我们对哈希表进行链接和操作,在解决哈希冲突、插入和查找节点的时候我们需要使用这个成员

最后是我们的结构体定义结束} HashNode;给这个结构体起一个名字叫HashNode,之后在主程序中我们就可以用它来声明变量,它包含的成员就是我们刚才定义的index,value和hh

     #include <stdio.h>
     #include "uthash.h"

     typedef struct {
         int index;
         int value;
         UT_hash_handle hh;
     } HashNode;

之后我们可以开始我们的主程序int main(void){(使用void就不用返回值了)

int n;这里和之前一样,定义整数变量n来存储键值对的个数

然后读入scanf("%d", &n);

然后对n做一个检查if(n<1 || n>500){

printf("n值不在正常范围内\n");

return 1;返回1证明出现错误

}

HashNode *hashTable = NULL;这里定义了我们的哈希表名叫hashTable并且它的指针指向结构体HashNode

for(int i = 0; i < n; i++){

和前面一样我们读取数据只不过这一次我们吧数据存在哈希表里

int index, value;

scanf("%d %d", &index, &value);

HashNode *node;利用node来建立我们的表

首先我们对index索引做一个查找,如果我们之前的表中已经存在过index了那么我们将node指向该节点方便求和,如果我们之前的表中没有出现过这个索引值那么我们则创建这个节点

先查找HASH_FIND_INT(hashTable, &index, node);在hashTable中找索引为index的节点,并返回给node(node将指向该节点,找不到的话node将为NULL)

if(node == NULL){找不到的话,证明之前没有这个索引

我们创建一个新的node = (HashNode *)malloc(sizeof(HashNode));首先分配内存,大小是HashNode结构体的大小

node -> index = index;

node -> value = value;把值存进去

HASH_ADD_INT(hashTable, index, node);将node存(添加)到hashTable里

}else{这个else的情况是我们找到了这个索引的node的话

node -> value += value;我们对相同索引的数值进行求和

}

}这里是for循环的结束,证明已经读取完所有的数值和索引

既然读取完成也做完求和运算了那么我们可以开始遍历哈希表输出结果

声明一个指向HashNode结构体的current指针用来遍历哈希表

HashNode *current;

for(current = hashTable开始将current指向hashTable; current != NULL; current = current->hh.next){

输出printf("%d %d", current - > index, current -> value);

}

之后因为之前我们malloc了空间所以释放一下

HashNode *tmp;

while(hashTable != NULL){

tmp = hashTable;

HASH_DEL(hashTable, current);

free(current);

hashTable = tmp;

}

}

测试了一下又失败了提示我找不到uthash库

#include <stdio.h>
#include "uthash.h"

typedef struct {
    int index;
    int value;
    UT_hash_handle hh;
} HashNode;
int main(void) {
    int n;
    scanf("%d", &n);
    if (n < 1 || n > 500) {
        printf("n值不在正常范围内\n");
        return 1;
    }
    HashNode* hashTable = NULL;
    for (int i = 0; i < n; i++) {
        int index, value;
        scanf("%d %d", &index, &value);
        HashNode* node;
        // 查找哈希表中是否存在该索引的节点
        HASH_FIND_INT(hashTable, &index, node);
        if (node == NULL) {
            // 如果不存在，创建新节点并插入哈希表
            node = (HashNode*)malloc(sizeof(HashNode));
            node->index = index;
            node->value = value;
            HASH_ADD_INT(hashTable, index, node);
        } else {
            // 如果存在，累加值
            node->value += value;
        }
    }
    // 遍历哈希表并输出结果
    HashNode* current;
    for (current = hashTable; current != NULL; current = current->hh.next) {
        printf("%d %d\n", current->index, current->value);
    }
    // 释放哈希表占用的内存
    HashNode* tmp;
    while (hashTable != NULL) {
        HASH_DEL(hashTable, current);
        free(current);
        current = hashTable;
    }
    return 0;
}

接下来我们尝试不引入uthash

自己实现简单的哈希

首先我们#include <stdio.h>

#include <stdlib.h>调用stdlib.h是为了使用malloc和free分配和释放内存

之后我们定义哈希表节点结构体

typedef struct HashNode {

int index;

int value;

struct HashNode *next; 形成链表解决哈希冲突

} HashNode;

之后我们定义哈希函数,这里使用取余的方法获得哈希值

int hashFunction(int index, int size) {

return index % size;

}

之后我们定义一个insert函数实现节点的插入

void insert(HashNode *hashTable[], int size, int index, int value){

我们需要的有目标哈希表,哈希表大小,要插入的节点的索引,要插入的节点的数值

先计算哈希值int hashIndex = hashFunction(index, size);

然后分情况考虑,如果该哈希值不存在那么我们作为新的节点插入

如果存在那么我们更新他的值(做求和运算)然后将返回(函数结束)

如果我们已经遍历到最后一个节点那么我们停止循环,否则我们继续遍历直到链表末尾

HashNode *node = hashTable[hashIndex];

if(node == NULL){

HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));

newNode->index = index;

newNode ->value = value;

newNode->next = NULL;

hashTable[hashIndex] = newNode;

}else{

while(node != NULL){

if(node->index == index){

node->value += value;

return

}

if(node->next == NULL){

break;

}

node = node->next;

}

HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));

newNode->index = index;

newNode->value = value;

newNode->next = node->next;

node->next = newNode;

}

}

除了insert函数之外我们还需要print,遍历哈希表并且输出结果

void printHashTable(HashNode *hashTable[], int size) {

传入值是hashtable(指针)以及他的size

for (int i = 0; i < size; i++){

HashNode *node = hashTable[i];

while(node != NULL){

printf("%d %d\n", node->index, node->value);

node = node->next;

}

}

}

还需要一个free函数用于释放哈希表占用的内存

void freeHashTable(HashNode *hashTable[], int size){

for(int i = 0;i < size; i++){

HashNode *node = hashTable[i];

while(node != NULL){

HashNode *next = node->next;

free(node);

node = next;

}

}

}

然后开始我们的主程序

int main() {

int n;

scanf("%d", &n);

if(n < 1 || n> 500){

printf("n值不在正常范围内\n");

return 1;

}

int hashTableSize = 1000;

HashNode *hashTable[hashTableSize];声明一个指针数组来表示哈希表

for (int i = 0; i < hashTableSize; i++){

hashTable[i] = NULL;初始化哈希表的每个位置为NULL

}

开始读取数据

for(int i = 0; i < n; i++){

int index, value;

scanf("%d %d, &index, &value);

insert(hashTable, hashTableSize, index, value);

}

最后我们打印、释放

prinfHashTable(hashTable,hashTableSize);

freeHashTable(hashTable, hashTableSize);

return 0;

}

insert的部分(豆包)在做一下解释

  1. 整体解释想象有很多小格子（这就是哈希表），每个小格子可以放一个或者一串小玩具（这些小玩具就是我们的数据，也就是节点）。我们要把新玩具放到格子里，这个函数就是在做这件事。
  2. 详细步骤首先，我们要知道把玩具放到哪个格子里。int hashIndex = hashFunction(index, size);这一行就像是在找格子。我们有一个规则（哈希函数），根据玩具的一个编号（index）和格子的总数（size）来决定把玩具放到哪个格子里。然后我们看看这个格子里有没有玩具。HashNode *node = hashTable[hashIndex];这就是在看找到的那个格子里有没有玩具。如果格子里没有玩具（if (node == NULL)）：那我们就可以直接把新玩具放进去啦。我们要先做一个新玩具（HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));），这个新玩具的编号（index）和它的特点（value）就是我们要放进去的，而且这个新玩具后面没有连着别的玩具（next是NULL）。然后把这个新玩具放到格子里（hashTable[hashIndex] = newNode;）。如果格子里已经有玩具了（else）：我们要看看有没有和我们要放的玩具编号一样的。我们就一个一个检查格子里的玩具（while (node!= NULL)）。如果找到了编号一样的玩具（if (node->index == index)）：那就把这个玩具的特点变得更厉害一点（node->value += value;），然后就不用再放新玩具了，我们就完成啦（return;）。如果一直没找到编号一样的，而且我们已经检查到这一串玩具的最后一个了（if (node->next == NULL)）：那我们就在这一串玩具的最后面加上我们的新玩具。我们先做一个新玩具（HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));），设置好新玩具的编号和特点（newNode->index = index; newNode->value = value;），让新玩具后面没有连着别的玩具（newNode->next = node->next;），然后把新玩具连到这一串玩具的最后（node->next = newNode;）。

所以最终代码是:

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

typedef struct HashNode {
    int index;
    int value;
    struct HashNode *next;
} HashNode;

int hashFunction(int index, int size) {
    return index%size;
}

void insert(HashNode *hashTable[], int size, int index, int value) {
    int hashIndex = hashFunction(index, size);
    HashNode *node = hashTable[hashIndex];
    if (node == NULL) {
        HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
        newNode -> index = index;
        newNode -> value = value;
        newNode -> next = NULL;
        hashTable[hashIndex] = newNode;
    } else {
        while (node != NULL) {
            if (node -> index == index) {
                node -> value += value;
                return;
            }
            if (node -> next == NULL) {
                break;
            }
            node = node -> next;
        }
        HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
        newNode -> index = index;
        newNode -> value = value;
        newNode -> next = node -> next;
        node -> next = newNode;
    }
}

void printHashTable(HashNode *hashTable[], int size) {
    for (int i = 0; i < size; i++){
        HashNode *node = hashTable[i];
        while (node != NULL) {
            printf("%d %d\n", node->index, node->value);
            node = node -> next;
        }
    }
}

void freeHashTable(HashNode *hashTable[], int size) {
    for (int i = 0; i < size; i++) {
        HashNode *node = hashTable[i];
        while (node != NULL) {
            HashNode *next = node -> next;
            free(node);
            node = next;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    if (n < 1 || n > 500) {
        printf("n值不在正常范围内\n");
        return 1;
    }
    int hashTableSize = 1000;
    HashNode *hashTable[hashTableSize];
    for (int i = 0; i < hashTableSize; i++) {
        hashTable[i] = NULL;
    }
    for (int i = 0; i < n; i++) {
        int index, value;
        scanf("%d %d", &index, &value);
        insert(hashTable, hashTableSize, index, value);
    }
    printHashTable(hashTable, hashTableSize);
    freeHashTable(hashTable, hashTableSize);
    return 0;
}

​