博客
关于我
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/

    你可能感兴趣的文章
    Multimodal Unsupervised Image-to-Image Translation多通道无监督图像翻译
    查看>>
    MySQL Cluster与MGR集群实战
    查看>>
    multipart/form-data与application/octet-stream的区别、application/x-www-form-urlencoded
    查看>>
    mysql cmake 报错,MySQL云服务器应用及cmake报错解决办法
    查看>>
    Multiple websites on single instance of IIS
    查看>>
    mysql CONCAT()函数拼接有NULL
    查看>>
    multiprocessing.Manager 嵌套共享对象不适用于队列
    查看>>
    multiprocessing.pool.map 和带有两个参数的函数
    查看>>
    MYSQL CONCAT函数
    查看>>
    multiprocessing.Pool:map_async 和 imap 有什么区别?
    查看>>
    MySQL Connector/Net 句柄泄露
    查看>>
    multiprocessor(中)
    查看>>
    mysql CPU使用率过高的一次处理经历
    查看>>
    Multisim中555定时器使用技巧
    查看>>
    MySQL CRUD 数据表基础操作实战
    查看>>
    multisim变压器反馈式_穿过隔离栅供电:认识隔离式直流/ 直流偏置电源
    查看>>
    mysql csv import meets charset
    查看>>
    multivariate_normal TypeError: ufunc ‘add‘ output (typecode ‘O‘) could not be coerced to provided……
    查看>>
    MySQL DBA 数据库优化策略
    查看>>
    multi_index_container
    查看>>