题解 | #合并表记录#
合并表记录
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; }