我正在处理一个以图为主题的挑战问题，所以我决定实现一个多重链表(这个数据结构可以表示有向图)。尝试为列表创建节点时遇到问题。该程序编译得很好，但当它运行时，它只会到达某个点并在没有警告的情况下退出。在VS2019中以调试模式运行它，IDE显示我正在尝试取消引用空指针。事实上，在它编译之前，它就强调了这条可疑的线，并警告说这可能会发生。但我完全不明白为什么。以下是链表的实现(使用最小的工作示例，确实意味着最小，我尽了最大努力…)：
#include<stdlib.h>
#include<stdio.h>
typedef unsigned int uint;
typedef struct Node {
uint id;
uint data;
size_t num_parents;
size_t size_parents;
struct Node * parents;
size_t num_children;
size_t size_children;
struct Node * children;
} Node;
/*/ ORIGINAL PROBLEMATIC REALLOCATING FUNCTION
Node * reallocate_node_array(Node * array, size_t* size) {
Node * new_array = new_array(Node, *size * 2); // this doesn't seem to be working as I expected
for (size_t i = 0; i < *size; i++) {
new_array[i] = array[i]; // FAULTY LINE
}
*size *= 2;
return new_array;
}
/**/
//NEW VERSION EDITED TO REFLECT CRAIG ESTEY'S COMMENTS AND ANSWER
Node * reallocate_node_array(Node * array, size_t* size) {
array = realloc(array, (*size) * 2);
if (array == NULL) {
perror("realloc");
exit(1);
}
*size *= 2;
return array;
}
void remove_node(Node * array, size_t * size, size_t index) {
for (int i = index; i < *size - 1; i++) {
array[i] = array[i + 1];
}
(*size)--;
}
void remove_parent (Node * node, uint id) {
for (int i = 0; i < node->num_parents; i++) {
if (node->parents[i].id == id) {
remove_node(node->parents, &node->num_parents, i);
}
}
}
void remove_child(Node * node, uint id) {
for (int i = 0; i < node->num_children; i++) {
if (node->children[i].id == id) {
remove_node(node->children, &node->num_children, i);
}
}
}
void add_child(Node * node, Node * child) {
if (node->num_children >= node->size_children) {
node->children = reallocate_node_array(node->children, &node->size_children);
}
node->children[++node->num_children] = *child;
}
void add_parent(Node * node, Node * parent) {
if (node->num_parents >= node->size_parents) {
node->parents = reallocate_node_array(node->parents, &node->size_parents);
}
node->parents[++node->num_parents] = *parent;
}
int main() {
char * file_name = "input.txt";
FILE * data_file = fopen(file_name, "r");
if (data_file == NULL) {
printf("Error: invalid file %s", file_name);
return 1;
}
uint num_nodes, num_relationships;
fscanf(data_file, "%u %un", &num_nodes, &num_relationships);
// I'm sorry that I'm not checking for the result of malloc in this block.
// I promise I'll be more responsible in the future.
Node * nodes = (Node*)malloc((num_nodes + 1) * sizeof(Node));
for (size_t i = 1; i <= num_nodes; i++) {
nodes[i].id = i;
fscanf(data_file, "%u ", &nodes[i].data);
nodes[i].num_children = 0;
nodes[i].size_children = 10;
nodes[i].children = (Node*)malloc(10 * sizeof(Node)); // FAULTY LINE #1
nodes[i].num_parents = 0;
nodes[i].size_parents = 10;
nodes[i].parents = (Node*)malloc(10 * sizeof(Node)); // FAULTY LINE #2
}
for (uint i = 0; i < num_relationships; i++) {
uint parent_id, child_id;
fscanf(data_file, "%u %un", &parent_id, &child_id);
add_child(&employees[parent_id], &employees[child_id]);
add_parent(&employees[child_id], &employees[parent_id]);
}
return 0;
}
上面写着"；故障线路#1"；以及"#2〃；，调试器告诉程序已到达断点(抛出异常)。
主要功能的要点是构建以下结构(图)：具有少量节点的有向图。最简洁的方法是从文件中读取指令。以下是input.txt:的内容
7 8
21 33 33 18 42 22 26
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
第一行：7是节点数；8是连接(关系)的数量
所有其他行：左边的编号为父节点；右边的数字是子节点。
所以，我的问题是我无法通过reallocate_node_array函数，后来从"；故障线路#1"；以及"#2〃；。
编辑
所以我编辑了上面的很多内容，以便提供一个最低限度的工作示例，并进一步澄清我的背景和困难。不管我做错了什么，如果你能告诉我，我将不胜感激。
然而，在我根据Craig Estey的评论编辑了我的reallocate_node_array函数后，我能够在调试方面取得更大的进展，并在上述实现中意识到了一些可怕的错误。最重要的是，我的结构体Node的字段parents和children的类型需要是Node**，而不是Node*，因为它们应该是数组，以便表示乘法链表。考虑到这一点，我将实现重写如下，的行为与预期的一样。然而，我在使用此代码的进一步任务中遇到了问题，这些问题不在本问题的范围内。如果我要提出一个新问题，我一定会记住你所有的批评，下次试着写一个好问题。
感谢大家的反馈。
#include<stdlib.h>
#include<stdio.h>
typedef unsigned int uint;
typedef struct Node {
uint id; // identifier of the node
int data; // actual data
size_t num_parents; // actual number of parent nodes
size_t size_parents; // current maximum capacity of array of parent nodes
struct Node** parents; // all nodes that connect from "upstream"
size_t num_children; // actual number of child nodes
size_t size_children; // current maximum capacity of array of children nodes
struct Node** children; // all nodes that connect "downstream"
} Node;
void reallocate_node_array(Node** array, size_t* size) {
array = realloc(array, sizeof(Node*) * (*size) * 2);
if (array == NULL) {
perror("realloc");
exit(1);
}
*size *= 2;
}
// The intention is to pass `num_children` or `num_parents` as `size` in order to decrease them
void remove_node(Node** array, size_t* size, size_t index) {
for (size_t i = index; i < *size - 1; i++) {
array[i] = array[i + 1];
}
(*size)--; // the decrement to either `num_children` or `num_parents`
}
void remove_parent(Node* node, uint id) {
for (size_t i = 0; i < node->num_parents; i++) {
if (node->parents[i]->id == id) {
remove_node(node->parents, &node->num_parents, i);
}
}
}
void remove_child(Node* node, uint id) {
for (size_t i = 0; i < node->num_children; i++) {
if (node->children[i]->id == id) {
remove_node(node->children, &node->num_children, i);
}
}
}
void add_parent(Node* node, Node* parent) {
if (node->num_parents >= node->size_parents) {
reallocate_node_array(node->parents, &node->size_parents);
}
node->parents[node->num_parents++] = parent;
}
void add_child(Node* node, Node* child) {
if (node->num_children >= node->size_children) {
reallocate_node_array(node->children, &node->size_children);
}
node->children[node->num_children++] = child;
}
int main() {
char* file_name = "input.txt";
FILE* data_file = fopen(file_name, "r");
if (data_file == NULL) {
printf("Error: invalid file %s", file_name);
return 1;
}
uint num_nodes, num_relationships;
fscanf(data_file, "%u %un", &num_nodes, &num_relationships);
Node* nodes = (Node*)malloc((num_nodes + 1) * sizeof(Node));
for (size_t i = 1; i <= num_nodes; i++) {
nodes[i].id = i;
fscanf(data_file, "%u ", &nodes[i].data);
nodes[i].num_children = 0;
nodes[i].size_children = 10;
nodes[i].children = (Node**)malloc(10 * sizeof(Node*));
for (size_t j = 0; j < 10; j++) nodes[i].children[j] = (Node*)malloc(sizeof(Node));
nodes[i].num_parents = 0;
nodes[i].size_parents = 10;
nodes[i].parents = (Node**)malloc(10 * sizeof(Node*));
for (size_t j = 0; j < 10; j++) nodes[i].parents[j] = (Node*)malloc(sizeof(Node));
}
for (uint i = 0; i < num_relationships; i++) {
uint parent_id, child_id;
fscanf(data_file, "%u %un", &parent_id, &child_id);
add_child(&nodes[parent_id], &nodes[child_id]);
add_parent(&nodes[child_id], &nodes[parent_id]);
}
return 0;
}
来自我的热门评论：
对
reallocate_node_array的调用在哪里？请编辑您的问题并发布。如果是(例如)：myarray = reallocate_node_array(myarray,&myarray_size)，则myarray的原始值会泄漏(因为函数没有释放旧的/原始的数组指针)。除非你试图创建一个单独的重复副本，为什么不直接使用realloc呢Craig Estey
您的回复表明这确实是问题所在。
因此，这里有一个简单的解决方案：
Node *
reallocate_node_array(Node *array, size_t *size)
{
array = realloc(array,sizeof(*array) * *size * 2);
if (array == NULL) {
perror("realloc");
exit(1);
}
*size *= 2;
return array;
}
但是，当我看到数组大小作为单独的参数传递时，我想创建一个新的"；阵列"；结构，其中包含大小/长度。这类似于c++向量的作用：
typedef struct {
Node *data;
size_t size;
} NodeArray;
void
reallocate_node_array(NodeArray *array)
{
array->data = realloc(array->data,sizeof(*array->data) * array->size * 2);
if (array->data == NULL) {
perror("realloc");
exit(1);
}
array->size *= 2;
}
这有点过分，因为调用者仍然需要跟踪事情。
这通常是初学者C程序员的练习。
这里有一个增强功能：
typedef struct {
Node *data; // pointer to data
size_t size; // number of elements currently in use
size_t capacity; // number of elements available
} NodeArray;
void
reallocate_node_array(NodeArray *array,size_t need)
// array -- pointer to node array
// need -- number of elements to grow by
{
size_t size = array->size + need;
if (size >= array->capacity) {
array->capacity = size + 100;
array->data = realloc(array->data,
sizeof(*array->data) * array->capacity);
if (array->data == NULL) {
perror("realloc");
exit(1);
}
}
}
更新：
您应该始终将realloc的结果分配给一个临时变量-如果realloc无法扩展缓冲区，它将返回NULL，但保留原始缓冲区。如果将结果分配回数组->如果数据为NULL，则会出现内存泄漏。【修订】-John Bode
JohnNode我知道这个技巧，但检查NULL并退出也可以。在大多数程序/系统上，内存不足是致命的。没有办法有意义地恢复。您可以处理错误，但程序如何进行Craig Estey
我也这么认为。我从来没有写过分配数组是可选的珊瑚漂白
是。正如我所说，对于大多数程序来说，这是致命的。TL；DR是不要担心——要高兴，因为这是我的一个"；皂盒"；问题/nts；-)
对于那些基于某些外部操作进行分配的程序(例如，许多客户端连接到服务器)，该程序应该/必须以另一种方式限制事情，并且不等待malloc/realloc返回NULL，当它"是"时；太迟了"；在这个过程中。
例如，它应该限制可以同时处理的传入请求的数量。如果我们限制为N个请求，并且每个请求需要分配M个字节，那么我们必须事先知道N * M可以安全地分配。
对于任务关键型实时应用程序，通常所有[可能的]分配都是在程序初始化期间完成的，并且具有预先分配的结构/缓冲区的各种子库。这就是我过去为商业级产品级应用程序/系统所做的。
对于实时应用程序；实时安全"；。也就是说，该程序将具有"；确定性执行"；。还有其他一些，但它的一个原则要求在初始化期间完成所有分配，以使内存不足的情况不可能[通过设计]。
此外，当分配失败时，程序现在处于不确定且不安全的状态。在之前发生了什么让我们进入这种状态的？
分配失败了吗只是，因为它要求太多内存？也就是说，我们是否没有进行足够的资源限制检查。这将是一个设计缺陷。
或者，是因为(其他地方)有一个bug，堆被破坏了吗？或者，程序数据/状态的其他部分现在已损坏？
我们不能确定。
为了安全起见，唯一要做的就是尽快中止。否则，当我们不再知道后果会是什么时，允许它继续下去的风险是什么？
(例如)它会[进一步]损坏数据库或删除错误的文件等吗？。分配失败可能表明UB(未定义的行为)，其后果是继续操作，将错误的值发送到实时控制设备，导致设备的危险行为。思考：机器人控制、起搏器控制等
简而言之，在现代系统上，通常有足够的内存(例如千兆字节)来满足所有正常的请求。因此，内存不足表示存在错误(例如执行分配的失控循环)。
内存有限的实时嵌入式系统必须事先精心制作(遵循"实时安全"规则/指南)，以从一开始就防止/避免这种情况的发生。