题解 | #合并表记录#
合并表记录
https://www.nowcoder.com/practice/de044e89123f4a7482bd2b214a685201
解题思路：使用带头结点的静态链表，头结点的index字段存储尾结点位置，链表元素按照index从小到大排序，如果index大小相同则合并同类项，否则找到合适的位置，将结点插入到该位置。所有结点输入完毕后，遍历链表输出index和value即可。
#include <stdio.h>
typedef struct ListNode {
int index;
int value;
int next;
} ListNode;
// 静态链表
void initList(ListNode *list) {
list[0].index = 0;
list[0].value = 0;
list[0].next = -1;
}
void newNode(ListNode *list, int index, int value) {
int i = ++list[0].index; // 头结点的index字段存储链表尾指针
list[i].index = index;
list[i].value = value;
list[i].next = -1;
}
int insertNode(ListNode *list, int index, int value) {
int i = list[0].next, prev = 0;
while (i != -1) {
// 合并相同index
if (list[i].index == index) {
list[i].value += value;
return 0;
}
// 索引按顺序排列
if (list[i].index > index) {
break;
}
prev = i;
i = list[i].next;
}
// 在合适位置插入节点
newNode(list, index, value);
int idx = list[0].index;
list[idx].next = i;
list[prev].next = idx;
return 0;
}
int main() {
ListNode list[501];
initList(list);
int num, i;
int idx, value;
scanf("%d", &num);
for (i = 0; i < num; ++i) {
scanf("%d %d", &idx, &value);
insertNode(list, idx, value);
}
for (i = list[0].next; i != -1; i = list[i].next) {
printf("%d %d\n", list[i].index, list[i].value);
}
return 0;
}
