题解 | #合并表记录#

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



//找到key在key_tab中的索引，如果找不到返回-1（-1表示这个key第一次出现）
int find_key_index(int key,int n,int *key_tab)
{
    n--;
    while(n >= 0)
    {
        if(key == *(key_tab+n))
        {break;}
        n--;
    }
    return n;
}

//冒泡排序，对key_tab和key_val同时进行升序排序
void sort(int n, int *key_tab, int *key_val)
{
    int temp;
    for (int a = 1; a <= n-1; a++)//外层循环是比较的轮数，数组内有10个数，那么就应该比较10-1=9轮
	{
		for (int b = 0; b <= n-1-a; b++)//内层循环比较的是当前一轮的比较次数，例如：第一轮比较9-1=8次，第二轮比较9-2=7次
		{
			if (key_tab[b] > key_tab[b + 1])//相邻两个数如果逆序，则交换位置
			{
				temp = key_val[b];
				key_val[b] = key_val[b + 1];
				key_val[b + 1] = temp;

                temp = key_tab[b];
				key_tab[b] = key_tab[b + 1];
				key_tab[b + 1] = temp;
			}
		}
	}

}

int main() {
    //为了节省空间，使用malloc，用户指定数组大小
    int *key_val = NULL;
    int *key_tab = NULL;
    int n=0,key=0,val=0;
    int count = 0;              //记录合并后，不同key的个数
    int index = 0;              //排序之前，用于key和val的索引
    scanf("%d\n",&n);
    // printf("%d",n);
    key_val=(int*)malloc(sizeof(int)*n);        //数组默认初始化赋值0
    key_tab=(int*)malloc(sizeof(int)*n);        //数组默认初始化赋值0
    for(int x=0;x<n;x++)
    {key_tab[x] = -1;}          //初始为-1，表示key还没有存入key_tab中
    

    //下面的while进行了hash的映射
    //最终效果：key_tab和key_val使用相同的数组下标，0到count
    while(scanf("%d %d",&key,&val) != EOF)
    {
        // printf("key = %d, val = %d\n", key, val);        //测试key和val是否被正确scanf
        index = find_key_index(key, n, key_tab);
        // printf("index = %d\n", index);       //测试索引返回是否正确，key第一次出现返回-1
        if(index == -1)
        {
            key_val[count] = val;
            *(key_tab+count) = key;
            // printf("key = %d\n",*(key_tab+i));   //测试key是否被正确存入key_tab中
            count++;
        }
        else {
            key_val[index] += val;          //索引出现两次及以上
        }
    }

    //按照key的顺序也就是key_tab进行排序，key_val同时进行排序
    sort(count,key_tab,key_val);

    for(int j=0;j<count;j++)
    {
        printf("%d %d\n",key_tab[j],key_val[j]);
    }
    return 0;
}