题解 | #合并表记录#

【内存少】【全通过】【源码】

由于最多只有500对数输入，因此索引范围0~11111111不考虑作为索引列表进行存储。 而是采用链表存储

本方案采用链表动态生成过程完成，过程自带排序。

1. 链表采用单向链表，单个节点包括index、value和next指针。通过malloc()函数申请空间
2. 每输入一对数字，则从数组头部进行检索，检索结果分四种情况，
   • 当前节点index和输入的idx相等，则在当前节点value基础上加上输入的val值
   • 输入idx比当前节点的index大，但比下一节点的index小，则插入新节点
   • 输入idx比当前节点的index大，同时当前为尾节点，则插入新节点
   • 输入idx大于下一节点的index，则向下继续索引
3. 对头部节点初始化和更新的补偿

#include<stdio.h>

struct node
{
    int value;
    int index;
    struct node* next;
};
typedef struct node Node;

int main()
{
    // 最多只有500对数字，那么index的范围0~11111111就是无所谓的
    // 完全可以用链表来存储数据
    int n;
    int i;
    int idx, val;
    Node head;
    head.next = NULL;
    head.value = 0;
    head.index = 0;
    Node *p = &head;
    Node *tmp;
    scanf("%d",&n);
    
    for(i=0;i<n;i++)
    {
        scanf("%d %d", &idx, &val);
        p = &head;
        while(p)
        {
            if(p->index==idx) // 直接求和
            {
                p->value += val;
                break;
            }
            else if(p->next->index > idx || p->next == NULL) // 新节点在链表尾部或中间，则插入节点
            {
                tmp = (Node *)malloc(sizeof(Node));
                tmp->next = p->next;
                tmp->index = idx;
                tmp->value = val;
                p->next = tmp;
                p = p->next;
                break;
            }
            else
                p=p->next;
        }
    }
    if(head.value == 0)
        p = head.next;
    else
        p = &head;
    while(p)
    {
        printf("%d %d\n",p->index,p->value);
        p = p->next;
    }
    return 0;
}