前言：
此刻兄弟们对“c深度复制”可能比较关注，看官们都需要学习一些“c深度复制”的相关知识。那么小编也在网摘上收集了一些有关“c深度复制””的相关文章，希望我们能喜欢，咱们一起来了解一下吧！学习工控知识，就来工控小新
农历十一月十八日 2023/12/ 30
往期推荐
2023年12月27日，每日花费一分钟练习C语言
2023年12月28日，每日花费一分钟练习C语言
每日一练
/ Daily Exercises
题目：
克隆图
给你无向连通(连通图/6460995?fr=aladdin)图中一个节点的引用，请你返回该图的深拷贝(深拷贝/22785317?fr=aladdin) (克)。
图中的每个节点都包含它的值 val (int) 和其邻居的列
表 (list[Node])。
class Node f
public int val;
public List<Node> neighbors;
}
题目分析
题目要求我们给定一个无向连通图中的一个节点的引用，返回该图的深拷贝。深拷贝是指创建一个新的图，其中每个节点的值和邻居列表都与原图相同，但是新图中的节点和原图中的节点不是同一个对象，也就是说，修改新图中的节点不会影响原图中的节点，反之亦然。图中的每个节点都包含它的值 val (int) 和其邻居的列表 (list[Node])，其中 Node 是一个自定义的结构体类型。
我们可以用一个哈希表来存储原图中的节点和新图中的节点的对应关系，即 key 是原图中的节点，value 是新图中的节点。我们可以用一个递归的函数来遍历原图中的节点，对每个节点，先检查它是否已经在哈希表中，如果是，就直接返回哈希表中的值，如果不是，就创建一个新的节点，将其加入哈希表，并递归地遍历它的邻居列表，将返回的新节点加入新节点的邻居列表。这样，我们就可以实现深拷贝的功能。这种方法的时间复杂度是O(n)，空间复杂度是O(n)，其中 n 是图中的节点个数。
程序展示
根据上述的分析，我们可以用以下的C语言程序来实现题目的要求。该程序在VC6.0的环境下运行正常，输入一个无向连通图中的一个节点的引用，输出该图的深拷贝。
#include <stdio.h>#include <stdlib.h>// 定义一个结构体类型 Node，表示图中的节点typedef struct Node { int val; // 节点的值 int numNeighbors; // 节点的邻居个数 struct Node** neighbors; // 节点的邻居列表，是一个 Node 类型的指针数组} Node;// 定义一个哈希表的结构体类型 HashTable，用来存储原图和新图的节点的对应关系typedef struct HashTable { int size; // 哈希表的大小，即桶的个数 Node*** buckets; // 哈希表的桶，是一个 Node 类型的指针数组的指针} HashTable;// 定义一个哈希函数，根据节点的值计算它在哈希表中的索引int hash(int val, int size) { return val % size;}// 定义一个初始化哈希表的函数，给定一个大小，创建一个空的哈希表HashTable* initHashTable(int size) { HashTable* ht = (HashTable*)malloc(sizeof(HashTable)); // 分配内存空间 ht->size = size; // 设置哈希表的大小 ht->buckets = (Node***)malloc(size * sizeof(Node**)); // 分配桶的内存空间 int i; for (i = 0; i < size; i++) { ht->buckets[i] = NULL; // 初始化每个桶为空 } return ht; // 返回哈希表的指针}// 定义一个插入哈希表的函数，给定一个原图的节点和一个新图的节点，将它们加入哈希表void insertHashTable(HashTable* ht, Node* oldNode, Node* newNode) { int index = hash(oldNode->val, ht->size); // 计算原图的节点在哈希表中的索引 Node** bucket = ht->buckets[index]; // 获取对应的桶 if (bucket == NULL) { // 如果桶为空，就创建一个新的桶 bucket = (Node**)malloc(2 * sizeof(Node*)); // 分配内存空间，每个桶存储两个节点的指针，一个是原图的节点，一个是新图的节点 bucket[0] = oldNode; // 存储原图的节点 bucket[1] = newNode; // 存储新图的节点 ht->buckets[index] = bucket; // 将桶加入哈希表 } else { // 如果桶不为空，就覆盖原来的桶 bucket[0] = oldNode; // 存储原图的节点 bucket[1] = newNode; // 存储新图的节点 }}// 定义一个查找哈希表的函数，给定一个原图的节点，返回对应的新图的节点，如果不存在，就返回 NULLNode* findHashTable(HashTable* ht, Node* oldNode) { int index = hash(oldNode->val, ht->size); // 计算原图的节点在哈希表中的索引 Node** bucket = ht->buckets[index]; // 获取对应的桶 if (bucket == NULL) { // 如果桶为空，就返回 NULL return NULL; } else { // 如果桶不为空，就返回桶中的第二个节点，即新图的节点 return bucket[1]; }}// 定义一个深拷贝的函数，给定一个原图的节点和一个哈希表，返回对应的新图的节点Node* cloneGraph(Node* node, HashTable* ht) { if (node == NULL) // 如果节点为空，就返回 NULL return NULL; Node* newNode = findHashTable(ht, node); // 在哈希表中查找该节点对应的新节点 if (newNode != NULL) // 如果找到了，就直接返回新节点 return newNode; newNode = (Node*)malloc(sizeof(Node)); // 如果没有找到，就创建一个新的节点 newNode->val = node->val; // 设置新节点的值 newNode->numNeighbors = node->numNeighbors; // 设置新节点的邻居个数 newNode->neighbors = (Node**)malloc(node->numNeighbors * sizeof(Node*)); // 分配新节点的邻居列表的内存空间 insertHashTable(ht, node, newNode); // 将原图的节点和新图的节点加入哈希表 int i; for (i = 0; i < node->numNeighbors; i++) { // 遍历原图的节点的邻居列表 newNode->neighbors[i] = cloneGraph(node->neighbors[i], ht); // 递归地深拷贝每个邻居节点，并将返回的新节点加入新节点的邻居列表 } return newNode; // 返回新节点}// 定义一个打印图的函数，给定一个图中的一个节点，按照广度优先搜索的顺序打印图中的所有节点的值和邻居列表// 定义一个打印图的函数，给定一个图中的一个节点，按照广度优先搜索的顺序打印图中的所有节点的值和邻居列表void printGraph(Node* node) { if (node == NULL) // 如果节点为空，就返回 return; HashTable* ht = initHashTable(100); // 创建一个哈希表，用来存储已经访问过的节点 Node** queue = (Node**)malloc(100 * sizeof(Node*)); // 创建一个队列，用来存储待访问的节点 int front = 0; // 队列的头指针 int rear = 0; // 队列的尾指针 queue[rear++] = node; // 将初始节点加入队列 while (front != rear) { // 当队列不为空时 Node* cur = queue[front++]; // 取出队列的头节点 if (findHashTable(ht, cur) != NULL) // 如果该节点已经访问过，就跳过 continue; insertHashTable(ht, cur, cur); // 将该节点加入哈希表，表示已经访问过 printf("节点%d的邻居列表：", cur->val); // 打印该节点的值 int i; for (i = 0; i < cur->numNeighbors; i++) { // 遍历该节点的邻居列表 printf("%d ", cur->neighbors[i]->val); // 打印每个邻居的值 if (findHashTable(ht, cur->neighbors[i]) == NULL) // 如果该邻居没有访问过，就将它加入队列 queue[rear++] = cur->neighbors[i]; } printf("\n"); // 换行 }}// 主函数int main() { // 创建一个示例的无向连通图，如下所示： // 1 - 2 // | | // 4 - 3 Node* node1 = (Node*)malloc(sizeof(Node)); // 创建节点1 node1->val = 1; // 设置节点1的值 node1->numNeighbors = 2; // 设置节点1的邻居个数 node1->neighbors = (Node**)malloc(2 * sizeof(Node*)); // 分配节点1的邻居列表的内存空间 Node* node2 = (Node*)malloc(sizeof(Node)); // 创建节点2 node2->val = 2; // 设置节点2的值 node2->numNeighbors = 2; // 设置节点2的邻居个数 node2->neighbors = (Node**)malloc(2 * sizeof(Node*)); // 分配节点2的邻居列表的内存空间 Node* node3 = (Node*)malloc(sizeof(Node)); // 创建节点3 node3->val = 3; // 设置节点3的值 node3->numNeighbors = 2; // 设置节点3的邻居个数 node3->neighbors = (Node**)malloc(2 * sizeof(Node*)); // 分配节点3的邻居列表的内存空间 Node* node4 = (Node*)malloc(sizeof(Node)); // 创建节点4 node4->val = 4; // 设置节点4的值 node4->numNeighbors = 2; // 设置节点4的邻居个数 node4->neighbors = (Node**)malloc(2 * sizeof(Node*)); // 分配节点4的邻居列表的内存空间 node1->neighbors[0] = node2; // 设置节点1的第一个邻居为节点2 node1->neighbors[1] = node4; // 设置节点1的第二个邻居为节点4 node2->neighbors[0] = node1; // 设置节点2的第一个邻居为节点1 node2->neighbors[1] = node3; // 设置节点2的第二个邻居为节点3 node3->neighbors[0] = node2; // 设置节点3的第一个邻居为节点2 node3->neighbors[1] = node4; // 设置节点3的第二个邻居为节点4 node4->neighbors[0] = node1; // 设置节点4的第一个邻居为节点1 node4->neighbors[1] = node3; // 设置节点4的第二个邻居为节点3 printf("原图：\n"); // 打印原图 printGraph(node1); // 调用打印图的函数，以节点1为起点 HashTable* ht = initHashTable(100); // 创建一个哈希表，用来存储原图和新图的节点的对应关系 Node* newNode1 = cloneGraph(node1, ht); // 调用深拷贝的函数，以节点1为起点，返回新图中的节点1 printf("新图：\n"); // 打印新图 printGraph(newNode1); // 调用打印图的函数，以新图中的节点1为起点 return 0;}程序测试
为了验证我们的程序是否正确，我们可以用一些测试用例来检验。
源代码获取
#软件下载通道#
我用夸克网盘分享了「20231230」，点击链接即可保存。打开「夸克APP」，无需下载在线播放视频，畅享原画5倍速，支持电视投屏。
链接：
(链接和提取码建议复制粘贴，手动输入容易出现错误）
#支持一下#
分享整理，测试发布不易 如果您方便的话可以帮忙点一下↓↓
谢谢大家！
下期题目
题目：
找出字符串中第一个只出现一次的字符 输入描述: 输入一个非空字符串 输出描述: 输出第一个只出现一次的字符，如果不存在输出-1
点赞加关注，学习不迷路
工控小新
学习工控知识就来工控小新，为你提供工控笔记知识：EPLAN电气绘图 | TIA博图基础 | CAD | C语言教学 | 单片机基础 | 三菱PLC ... 每日持续更新中
#头条挑创作挑战赛#
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #c深度复制
