博客
关于我
2021-04-20
阅读量:677 次
发布时间:2019-03-14

本文共 3022 字,大约阅读时间需要 10 分钟。

为了解决这个问题,我们需要从一个带有整数键值的链表中去除绝对值重复的键值节点,只保留第一个出现的结点,并将被删除的结点保存在另一个链表中。

方法思路

  • 输入处理:首先读取输入数据,建立链表的结构,记录每个结点的地址、键值及其下一个结点。
  • 哈希表记录:使用一个哈希表来记录每个绝对值键值的第一个出现的结点地址。
  • 遍历链表:从链表的第一个结点开始,遍历每一个结点:
    • 如果键值不在哈希表中,记录到保留链表中,并更新哈希表。
    • 如果键值已经存在,记录到被删除链表中。
  • 输出结果:将保留链表和被删除链表按顺序输出。
  • 解决代码

    #include 
    #include
    #include
    #include
    #include
    using namespace std;#define MAX_NODES 100002struct Node { int address; int key; int next;};int main() { int head_address; int n; scanf("%d %d", &head_address, &n); // 初始化链表数组:nodes数组存储每个address对应的Node信息 Node* nodes = new Node[MAX_NODES]; for (int i = 0; i < n; ++i) { int addr, k, next_addr; scanf("%d %d %d", &addr, &k, &next_addr); nodes[addr].address = addr; nodes[addr].key = k; nodes[addr].next = next_addr; } // 处理head地址是否有效 if (head_address != -1 && head_address < MAX_NODES) { // 确保链表是正确的 // 读取n个node,包括head_address所在的node // 这里可能调整一下,确保head_address所在的node已被读取进去 // 例如,如果head_address对应的行没有被读取到吗?可能需要调整读入的顺序 // 根据输入样例,输入的节点是从头开始的 } // 创建哈希表 unordered_map
    hash_key; // 两个链表数组:preserved_next和deleted_next vector
    preserved_next(MAX_NODES, -1); vector
    deleted_next(MAX_NODES, -1); int current_address = head_address; while (current_address != -1 && current_address < MAX_NODES) { Node current_node = nodes[current_address]; int key = current_node.key; if (hash_key.find(key) == hash_key.end()) { // 该key尚未被记录,加入保留链表 hash_key[key] = current_address; preserved_next[current_address] = current_node.next; if (preserved_next[current_address] == -1) { // 最后的结点 } } else { // 被加入删除链表 deleted_next[current_address] = current_node.next; } // 往后处理 current_address = current_node.next; } // 输出保留链表 int current = head_address; while (current != -1 && current < MAX_NODES) { Node node = nodes[current]; printf("%d %d %d\n", node.address, node.key, node.next); current = node.next; } // 输出删除链表 current = find_first_of_deleted(nodes, deleted_next); while (current != -1 && current < MAX_NODES) { node = nodes[current]; printf("%d %d %d\n", nodes[current].address, node.key, node.next); current = node.next; } delete[] nodes; return 0;}vector
    find_chainaddresses(vector
    & next_arr, vector
    & nodes) { vector
    addresses; int current = 0; while (current != -1) { if (current <= 0) { addresses.push_back(-1); break; } if (current < nodes.size() && next_arr[current] != -1) { addresses.push_back(next_arr[current]); current = next_arr[current]; } else { addresses.push_back(-1); } } return addresses;}int find_first_of_deleted(Node* nodes, vector
    & deleted_next) { int current = head_address; while (current != -1 && current < MAX_NODES) { if (deleted_next[current] != -1) { return current; } else { current = nodes[current].next; } } return -1;}

    代码解释

    • 读取输入:从标准输入读取链表的第一个结点地址和节点数目,然后读取每个结点的信息,存储在节点数组中。
    • 哈希表:记录每个键值的第一个出现位置,用于去重。
    • 遍历链表:逐个处理每个结点,决定其归入保留链表还是被删除链表。
    • 输出:按顺序输出保留链表和被删除链表,确保链表结构完整。

    这种方法确保了在处理大规模数据时的效率,并且结构清晰,易于维护。

    转载地址:http://bculz.baihongyu.com/

    你可能感兴趣的文章
    MySQL 数据类型和属性
    查看>>
    mysql 敲错命令 想取消怎么办?
    查看>>
    Mysql 整形列的字节与存储范围
    查看>>
    mysql 断电数据损坏,无法启动
    查看>>
    MySQL 日期时间类型的选择
    查看>>
    Mysql 时间操作(当天,昨天,7天,30天,半年,全年,季度)
    查看>>
    MySQL 是如何加锁的?
    查看>>
    MySQL 是怎样运行的 - InnoDB数据页结构
    查看>>
    mysql 更新子表_mysql 在update中实现子查询的方式
    查看>>
    MySQL 有什么优点?
    查看>>
    mysql 权限整理记录
    查看>>
    mysql 权限登录问题:ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)
    查看>>
    MYSQL 查看最大连接数和修改最大连接数
    查看>>
    MySQL 查看有哪些表
    查看>>
    mysql 查看锁_阿里/美团/字节面试官必问的Mysql锁机制,你真的明白吗
    查看>>
    MySql 查询以逗号分隔的字符串的方法(正则)
    查看>>
    MySQL 查询优化:提速查询效率的13大秘籍(避免使用SELECT 、分页查询的优化、合理使用连接、子查询的优化)(上)
    查看>>
    mysql 查询,正数降序排序,负数升序排序
    查看>>
    MySQL 树形结构 根据指定节点 获取其下属的所有子节点(包含路径上的枝干节点和叶子节点)...
    查看>>
    mysql 死锁 Deadlock found when trying to get lock; try restarting transaction
    查看>>