本文共 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/