样例输出 Copy

AAA BBB CCC DDD

Aa Bbb Ee

这题相信大家都会想到使用结构来解决，但是如何找到一个过程简单，运行高效的方法却不容易。于是，我现在使用哈希表来解决问题。

先来简单介绍一下哈希表：

基本概念：哈希表是一种存储键值对的数据结构，它通过哈希函数将键映射到数组中的某个位置（称为槽或桶），以此来存储和查找数据。这样做的目的是为了能够快速地定位和操作元素，提高数据存储和检索的效率。

哈希函数：哈希函数是哈希表的核心，它将输入的键（可以是各种类型的数据，如整数、字符串等）转换为一个在数组范围内的整数，这个整数就是存储或查找元素的索引。例如，对于一个存储学生信息的哈希表，你可以使用学生的学号作为键，通过哈希函数计算出一个在数组范围内的索引，将学生信息存储在该索引对应的位置。

哈希函数我们可以根据实际情况自己编写，以实现等更加高级的功能。这篇文章我使用的哈希函数均来源于Github网站的uthash库（乌塔什）。下面先展示代码：

#include

#include

#include

#include"uthash.h"

typedef struct{

char a[21];

int score, ball;

}Team;

typedef struct{ //哈希表的结构类型

char key[21];

int score, ball;

UT_hash_handle hh; //*1

}HashTeam;

HashTeam *team;

Team *rank;

void AddTeam(const char *key, int score, int ball); //向哈希表添加或更新球队信息

int Compare_score(const void *a, const void *b); //用于排序的比较函数

void FreeTeamHash(void); //释放哈希表的内存

int main()

{

int n, len, i, x, y, cnt;

char a[21], b[21];

while(~scanf("%d" , &n)){

while(getchar() != '\n');

if(n == 0)

break;

len = n*(n - 1)/2;

while(len){

scanf("%[^:]:%s %d:%d" , a, b, &x, &y);

while(getchar() != '\n');

AddTeam(a, x > y ? 3 : (x < y ? 0 : 1), x - y);

AddTeam(b, x < y ? 3 : (x > y ? 0 : 1), y - x);

len --;

}

rank = (Team *)malloc(HASH_COUNT(team) * sizeof(Team));

if (!rank) {

printf("Memory allocation failed");

exit(EXIT_FAILURE);

}

i = 0;

HashTeam *p, *tmp;

HASH_ITER(hh, team, p, tmp){

strcpy(rank[i].a, p->key);

rank[i].score = p->score;

rank[i].ball = p->ball;

i ++;

}

cnt = HASH_COUNT(team); //*6

qsort(rank, cnt, sizeof(Team), Compare_score);

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

printf("%s" , rank[i].a);

if(i < n - 1)

printf(" ");

}

printf("\n\n");

FreeTeamHash();

free(rank);

}

return 0;

}

void AddTeam(const char *key, int score, int ball){

HashTeam *s;

HASH_FIND_STR(team, key, s); //*2

if(!s){

s = (HashTeam *)malloc(sizeof(HashTeam));

if(!s){

printf("Memory allocation failed");

exit(EXIT_FAILURE);

}

strcpy(s->key, key);

s->score = 0;

s->ball = 0;

HASH_ADD_STR(team, key, s); //*3

}

s->score += score;

s->ball += ball;

}

int Compare_score(const void *a, const void *b){

Team *p = (Team *)a;

Team *q = (Team *)b;

if(q->score - p->score != 0)

return q->score - p->score;

else{

if(q->ball - p->ball != 0)

return q->ball - p->ball;

else

return strcmp(p->a, q->a);

}

}

void FreeTeamHash(void){

HashTeam *p, *tmp;

HASH_ITER(hh, team, p, tmp){ //*4

HASH_DEL(team, p); //*5

free(p);

}

team = NULL;

}

对六处" * "进行解释：

*1：UT_hash_handle hh 是 uthash 库中非常重要的一个结构体成员，它是 uthash 库用于管理哈希表内部链接和操作的关键部分。当你使用 uthash 库来创建哈希表时，需要在存储元素的结构体中添加这个成员。

*2：HASH_FIND_STR 是 uthash 库中的一个宏，它的主要功能是在哈希表中查找一个元素，该元素的键是一个字符串。下面是宏的原型：

#define HASH_FIND_STR(head,findstr,out) \

do { \

unsigned _uthash_hfstr_keylen = (unsigned)uthash_strlen(findstr); \

HASH_FIND(hh, head, findstr, _uthash_hfstr_keylen, out); \

} while (0)

(head):是一个指向哈希表的指针，它指向存储元素的起始位置，通常是一个存储元素的结构体指针，该结构体包含 UT_hash_handle hh 成员。head是查找操作的起点，代表存储元素的哈希表。

(findstr)：这是一个字符串，作为要查找元素的键。该字符串将作为查找元素的依据。

(out)：这是一个指向结构体的指针，用于存储查找结果。当查找成功时，(out) 将指向查找到的元素；如果查找失败，(out) 将被设置为 NULL。

*3：HASH_ADD_STR 是 uthash 库中的一个宏，主要用于向哈希表中添加元素，其中元素的键是一个字符串。下面是该宏的原型：

#define HASH_ADD_STR(head,strfield,add) \

do { \

unsigned _uthash_hastr_keylen = (unsigned)uthash_strlen((add)->strfield); \

HASH_ADD(hh, head, strfield[0], _uthash_hastr_keylen, add); \

} while (0)

（strfield）：这是结构体中表示键的字段名，该字段必须是字符串类型。这个字段将作为元素的键，用于计算哈希值和查找元素。

（add）：这是一个指向要添加的元素的指针。该元素将被添加到哈希表中，元素的结构体中必须包含 UT_hash_handle hh 成员。

*4：HASH_ITER 是 uthash 库中的一个宏，主要用于遍历哈希表中的元素。

#ifdef NO_DECLTYPE

#define HASH_ITER(hh,head,el,tmp) \

for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \

(el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL)))

#else

#define HASH_ITER(hh,head,el,tmp) \

for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \

(el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL)))

#endif

（el）：这是一个指向结构体的指针，用于存储当前迭代的元素。在遍历过程中，el 将依次指向哈希表中的每个元素。

（tmp）：这是一个指向结构体的指针，通常用作临时存储，辅助 el 进行迭代。它在遍历过程中用于存储下一个元素的指针，确保迭代的正确性。

*5：HASH_DEL 是 uthash 库中的一个宏，主要用于从哈希表中删除元素。宏的原型如下：

#define HASH_DEL(head,delptr) \

HASH_DELETE(hh,head,delptr)

（delptr）：这是一个指向要删除的元素的指针。该元素将从哈希表中被移除，元素的结构体中必须包含 UT_hash_handle hh 成员。HASH_DEL 宏实际上是调用了 HASH_DELETE 宏，将 hh 作为第一个参数传递给 HASH_DELETE。HASH_DELETE宏在uthash库中出现了非常多次，也有不同程度的变体，这里不做详细介绍，感兴趣的可以去查uthash库。

*6：HASH_COUNT宏的原型如下：

#define HASH_COUNT(head) HASH_CNT(hh,head)

#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U)

#define HASH_COUNT(head) HASH_CNT(hh,head)：这个宏是一个高级别的接口，用于计算哈希表中的元素数量。它通过调用 HASH_CNT 宏来完成实际的计数操作。

#define HASH_CNT(hh,head) ((head!= NULL)?((head)->hh.tbl->num_items):0U)这个宏是 HASH_COUNT 的具体实现，用于计算哈希表中元素的数量。

(head!= NULL)?((head)->hh.tbl->num_items):0U：这个条件表达式，用于判断 head 是否为 NULL。如果 head 不为 NULL，则通过 (head)->hh.tbl->num_items 来获取元素的数量。否则元素数量为 0U（无符号零）。

孩子们，上面六处" * "就是哈希表的简单使用，四个函数能够实现基本的查找元素，添加元素，遍历全表和删除元素。哈希表在面对大量数据时具有显著优势，可以极大地提升程序运行的效率，同时也有较高的灵活性。这么厉害的数据结构，快去试试吧。What can I say ？