金牌、银牌、铜牌--链表

这道题是链表常规题中很经典的一道题目，充分利用了链表当中的多种操作，存储，有一定的难度，但是当你理解这道题你一定会受益匪浅，此题会不断完善解题思路及有关解释，力求将此题解透。 完整题目题面：

金牌、银牌、铜牌

Problem Description

Acm——大学中四大竞赛之首——是极具挑战性的大学生竞赛形式。在一场acm比赛中，一个参赛队伍由三人组合而成，在最短的时间内做出尽可能多的题目而且要尽量少提交错误代码，这样才能得到更高的排名。现在让我们模拟一次不正规的acm比赛，假设在比赛开始后30分钟（这时已经有不少同学提交了代码，在rating中已经出现），到比赛结束前，又有新的同学提交（在rating中出现），同时rating在不断变化着，还有一些同学因为一些原因中途退出比赛（这时rating中自动删除，当然在正式比赛中不会有这种情况）。最后终于比赛结束啦，看看rating，都有谁能拿到奖牌呢？

Input

第一行一个整数n（n<=1000），代表开始比赛后30分钟已经有n个人提交了代码。从第二行到第n+1行每行包括名字name（小于20个字符），分数p（0<=p<=10000)，同时行数代表目前排名情况，第二行的排名第一，第三行排名第二，依次类推。 从第n+2行起，每行有一个字符，是A,Q,C，S，O中的一个： . A代表新加进rating中一名同学，紧随其后是名字name（小于20个字符），分数p（0<=p<=10000)； . Q代表有一名同学退出了，接着是他的名字name（小于20个字符）； . C代表有一个人的分数发生的改变，接着是此人的名字name，他的分数加多少（分数只会增加不会减少）； . .S代表一次显示此时rating的请求，这时输出所有在rating中的同学名字及他们的分数。 . O代表比赛结束。 .

Output

对每次请求，输出此时rating中的所有同学名字和对应分数，在比赛结束时输出金牌获得者（一名），银牌获得者（两名），铜牌获得者（三名）（测试数据保证此时有至少6名同学在rating上）。注意：有同学添加到rating中或者分数改变后，在rating中有和这名同学有相同的分数，那么这名同学排在最后一个与他有相同分数同学的后面。

Example Input

7 cze 90 qch 87 zff 70 shangcf 66 zhaohq 50 zhrq 46 yah 20 A pc 56 Q zff C qch 4 S A von 66 O

Example Output

qch 91 cze 90 shangcf 66 pc 56 zhaohq 50 zhrq 46 yah 20 #1 : qch #2 : cze shangcf von #3 : pc zhaohq zhrq

分析此题，链表结构体中将会有name和score。 step1：链表将会有初始n个元素，顺序建立n个元素链表。 step2： A操作，链表加入新结点，链表的插入。 Q操作，链表结点的查找以及查找到以后的删除操作。 C操作，链表结点的查找以及查找到以后的链表结点的更改操作。 S操作，显示ranklist，即链表的输出show操作。 O操作，输入操作结束的标志，即跳出break操作。 step3：操作结束后，需要输出获得奖牌情况，金牌一名，银牌两名，铜牌三名，看起来不难实现，但特殊的是允许并列情况的出现！所以这里是一个难点，会在完整代码中详细说。

完整代码如下：

#include <stdio.h> #include <stdlib.h> #include <string.h> struct node { char name[21]; //选手名字 int score; //选手分数 struct node *next; //结点的后继指针用于链接结点 }; struct node *creat(int n); //链表初始n个结点的建立 struct node *A(struct node *head1, char name1[21], int s); //A操作，结点的插入 struct node *Q(struct node *head1, char name1[21]); //Q操作，结点的查找以及删除 struct node *C(struct node *head1, char name1[21], int s); //C操作，结点的查找以及更改 void Show(struct node *head1); //S操作，显示ranklist void End(struct node *head1); //O操作，即操作结束以后的排名及奖牌情况 struct node *rank(struct node *head1); //成绩表的排序函数 int main() { int n, f; char ch, name[21]; scanf("%d", &n); struct node *head; head = creat(n); //链表初始n个结点的建立 getchar(); while(~scanf("%c", &ch)) { if(ch == 'O') {End(head);break;} //O操作，即操作结束以后的排名及奖牌情况 else if(ch == 'A') //A操作，结点的插入 { scanf("%s %d", name, &f); head = A(head, name, f); } else if(ch == 'Q') //Q操作，结点的查找以及删除 { scanf("%s", name); head = Q(head, name); } else if(ch == 'C') //C操作，结点的查找以及更改 { scanf("%s %d", name, &f); head = C(head, name, f); } else if(ch == 'S') Show(head); //S操作，显示ranklist } return 0; } struct node *creat(int n) //链表初始n个结点的建立 { struct node *head1, *p, *q; head1 = (struct node * )malloc(sizeof(struct node)); //为开头结点开辟空间 head1 -> next = NULL; q = head1; while(n--) //插入结点 { p = (struct node *) malloc (sizeof(struct node)); scanf("%s %d", p->name, &p->score); p -> next = NULL; q -> next = p; q = p; } return head1; }; void Show(struct node *head1) //S操作，显示ranklist { struct node *q; head1 = rank(head1); q = head1->next; while(q != NULL) { printf("%s %d", q->name, q->score); printf("\n"); q = q->next; } }; struct node *A(struct node *head1, char name1[21], int s) //A操作，结点的插入 { struct node *q, *p; q = (struct node *) malloc (sizeof(struct node)); strcpy(q->name, name1); q->score = s; q->next = NULL; for(p = head1->next; p->next != NULL; p = p->next) {} q->next = p->next; p->next = q; return head1; } ; struct node *Q(struct node *head1, char name1[21]) //Q操作，结点的查找以及删除 { struct node *q, *p; for(p = head1->next; p != NULL; p = p->next) { q = p->next; if(strcmp(q->name, name1) == 0) { p->next = q->next; free(q); break; } } return head1; }; struct node *C(struct node *head1, char name1[21], int s) //C操作，结点的查找以及更改 { struct node *p; for(p = head1->next; p != NULL; p = p->next) { if(strcmp(p->name, name1) == 0) { p->score = p->score + s; } } return head1; }; void End(struct node *head1) //O操作，即操作结束以后的排名及奖牌情况 { struct node *q, *p; int i; head1 = rank(head1); p = head1->next; q = head1; printf("#1 :"); do { printf(" %s", p->name); p = p->next; q = q->next; }while(p->score == q->score); printf("\n#2 :"); for(i = 1; i <= 2; i++) { do { printf(" %s", p->name); p = p->next; q = q->next; }while(p->score == q->score); } printf("\n#3 :"); for(i = 1; i <= 3; i++) { do { printf(" %s", p->name); p = p->next; q = q->next; }while(p->score == q->score); } } struct node *rank(struct node *head1) //成绩表的排序函数 { struct node *q, *p; char i[21]; int a; for(p = head1->next; p != NULL; p = p->next) //开始排序 { for(q = p->next; q != NULL; q = q->next) //用两个指针来冒泡排序 { if(p->score < q->score) //如果前面的比后面的小 { strcpy(i, p->name); //交换名字 strcpy(p->name, q->name); strcpy(q->name, i); a = p->score; //交换成绩 p->score = q->score; q->score = a; } } } return head1; }