C++ 链表去重算法详解：代码实现与优化

该程序实现了链表去重的功能。给定一个链表的起始地址和长度，程序会将链表中重复的节点去除，并输出去重后的链表。

程序功能

该程序接收两个参数：

链表的起始地址（start）
链表的长度（n）

程序会读取链表中每个节点的地址、关键字和指向下一个节点的地址，并进行去重操作。最后输出去重后的链表，每个节点的输出格式为：地址关键字下一个节点的地址。

设计思路

定义结构体 node：用来表示链表的节点，包含节点的地址 (add)，关键字 (key) 和指向下一个节点的地址 (next)。为了方便排序，还添加了两个辅助字段：tag 和 no。
定义 hash 数组：用于标记链表中是否出现过某个关键字。hash[abs(key)] 为 1 表示关键字 key 出现过，为 0 表示 key 未出现过。
循环读取链表节点信息：根据 start 和 n，读取链表的节点信息，包括地址、关键字和下一个节点的地址。
去重操作：使用 hash 数组标记每个节点的关键字是否重复。如果 key 未出现过，则将该节点的 tag 标记为 2，表示未重复。如果 key 已经出现过，则将该节点的 tag 标记为 1，表示重复。
排序：根据 tag 和 no 对链表节点进行排序。tag 为 2 的节点 (未重复) 排在前面，tag 为 1 的节点 (重复) 排在后面。no 用于区分相同 tag 的节点，保证排序的稳定性。
输出去重后的链表：按照排序后的顺序输出去重后的链表，每个节点输出其地址、关键字和下一个节点的地址。

程序结构说明

包含头文件：包括 cstdio (用于输入输出)、cmath (用于数学计算)、algorithm (用于排序) 和 cstring (用于内存操作)。
定义结构体 node：包含节点的地址、关键字、指向下一个节点的地址以及用于去重操作和排序的辅助字段 tag 和 no。
定义 hash 数组：用于标记链表中是否出现过某个关键字。
定义 cmp 函数：用于排序，按照 tag (降序) 和 no (升序) 进行排序。
主函数 main：
- 读取链表的起始地址和长度。
- 初始化 hash 数组。
- 循环读取链表节点信息，进行去重操作。
- 对节点进行排序。
- 按照要求输出去重后的链表。

代码示例

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

struct node {
  int add, key, next;
  int no, tag;
} Node[100005];

int hash[100005];

bol cmp(node a, node b) {
  if (a.tag != b.tag) return a.tag > b.tag;
  else return a.no < b.no;
}

int main() {
  int start, n, x;
  scanf("%d %d", &start, &n);
  memset(hash, 0, sizeof(hash));
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    Node[x].add = x;
    scanf("%d %d", &Node[x].key, &Node[x].next);
  }

  int p = start;
  int cnt = 0;
  int num1 = 0, num2 = 0;
  while (p != -1) {
    if (hash[abs(Node[p].key)] == 0) {
      hash[abs(Node[p].key)] = 1;
      Node[p].tag = 2;
      num1++;
    } else {
      Node[p].tag = 1;
      num2++;
    }
    Node[p].no = cnt;
    cnt++;
    p = Node[p].next;
  }

  sort(Node, Node + 100000, cmp);
  for (int i = 0; i < num1; i++) {
    if (i != num1 - 1) {
      printf("%05d %d %05d\n", Node[i].add, Node[i].key, Node[i + 1].add);
    } else {
      printf("%05d %d -1\n", Node[i].add, Node[i].key);
    }
  }
  for (int i = num1; i < cnt; i++) {
    if (i != cnt - 1) {
      printf("%05d %d %05d\n", Node[i].add, Node[i].key, Node[i + 1].add);
    } else {
      printf("%05d %d -1\n", Node[i].add, Node[i].key);
    }
  }
  return 0;
}

优化建议

使用 unordered_set 代替 hash 数组：unordered_set 可以更有效地进行关键字的查找和标记，并且代码更简洁。
使用 unique 和 stable_sort 进行去重和排序：unique 可以快速地去除重复元素，stable_sort 可以保证排序的稳定性，避免使用额外的 no 字段。
使用 vector 存储节点信息：vector 更适合存储动态变化的数据，避免使用固定大小的数组。

通过这些优化措施，可以进一步提升链表去重算法的效率和代码可读性。

总结

本文详细介绍了使用 C++ 实现链表去重算法的原理和代码，并提供了优化建议。通过理解链表去重算法的实现过程，可以更好地掌握 C++ 语言的特性和数据结构的应用，并为解决更复杂的编程问题奠定基础。