L2-002 链表去重

链表问题

#include <stdio.h>  // 标准输入输出库，用于 scanf 和 printf
#include <stdlib.h> // 标准库，用于 abs 函数
#include <stdbool.h> // 布尔类型支持，用于 bool、true、false

#define MAX_ADDRESS 100000  // 最大地址范围，用于数组大小
#define MAX_KEY 10000      // 键值绝对值的最大值，用于 visited 数组大小

// 定义链表节点结构
typedef struct Node {
    int address;          // 节点地址
    int key;              // 节点键值
    int next;             // 下一个节点的地址
} Node;

// 定义全局变量
Node nodes[MAX_ADDRESS];  // 存储所有节点，以地址为索引
bool visited[MAX_KEY];    // 记录键值绝对值是否已访问
Node uniqueList[MAX_ADDRESS];  // 去重后的链表
Node removedList[MAX_ADDRESS]; // 被删除的链表

int main() {
    int head, N;  // head 是链表头节点地址，N 是节点总数
    scanf("%d %d", &head, &N);  // 输入链表头节点地址和节点总数

    // 读取所有节点信息
    for (int i = 0; i < N; i++) {
        int address, key, next;  // 当前节点的地址、键值和下一个节点地址
        scanf("%d %d %d", &address, &key, &next);  // 读取节点信息
        nodes[address].address = address;  // 存储节点地址
        nodes[address].key = key;          // 存储节点键值
        nodes[address].next = next;        // 存储下一个节点地址
    }

    // 初始化 visited 数组，记录键值绝对值是否已访问
    for (int i = 0; i <= MAX_KEY; i++) {
        visited[i] = false;  // 初始化为未访问
    }

    int uniqueCount = 0;  // 去重后链表的节点数量
    int removedCount = 0; // 被删除链表的节点数量
    int current = head;   // 当前节点地址，从链表头开始

    // 遍历链表
    while (current != -1) {  // 当前节点地址不为 -1（链表未结束）
        int keyAbs = abs(nodes[current].key);  // 当前节点键值的绝对值

        if (!visited[keyAbs]) {  // 如果键值绝对值未访问过
            visited[keyAbs] = true;  // 标记为已访问
            uniqueList[uniqueCount++] = nodes[current];  // 加入去重后的链表
        } else {  // 如果键值绝对值已访问过
            removedList[removedCount++] = nodes[current];  // 加入被删除的链表
        }

        current = nodes[current].next;  // 移动到下一个节点
    }

    // 输出去重后的链表
    for (int i = 0; i < uniqueCount; i++) {
        printf("%05d %d ", uniqueList[i].address, uniqueList[i].key);  // 输出节点地址和键值
        if (i < uniqueCount - 1) {  // 如果不是最后一个节点
            printf("%05d\n", uniqueList[i + 1].address);  // 输出下一个节点地址
        } else {  // 如果是最后一个节点
            printf("-1\n");  // 输出 -1 表示链表结束
        }
    }

    // 输出被删除的链表
    for (int i = 0; i < removedCount; i++) {
        printf("%05d %d ", removedList[i].address, removedList[i].key);  // 输出节点地址和键值
        if (i < removedCount - 1) {  // 如果不是最后一个节点
            printf("%05d\n", removedList[i + 1].address);  // 输出下一个节点地址
        } else {  // 如果是最后一个节点
            printf("-1\n");  // 输出 -1 表示链表结束
        }
    }

    return 0;  // 程序正常结束
}