C中的结构链表连接不好

Question

我试图在C中制作一个链表，其中每个节点都连接到右侧和左侧。使用insert_node函数，我输入了4个节点，值:2,3,5,2

如果我写的逻辑正确，插入节点应该自动对列表进行排序，使其对齐为:2,2,3,5

如果我检查print_list中的中间值，值显示为3，这是我所期望的。然而，只要我使用临时节点temp移动到左侧节点，temp就变成了nullptr。

我不明白为什么会发生这种情况，因为print_list中的temp节点是用列表的中间节点初始化的，并且中间节点被分配了一个左节点。

typedef struct ListNode{
struct ListNode* right;
struct ListNode* left;
int value;
} ListNode;
//a linked list that saves the middle node of the list
typedef struct LinkedList{
ListNode* middle;
int left_size;
int right_size;
}LinkedList;
//a function to reduce repeating malloc
ListNode* init_node() {
return (ListNode*)malloc(sizeof(ListNode*) * 2 + 4);
}
LinkedList* init_list() {
return (LinkedList*)malloc(sizeof(ListNode*) + sizeof(int) * 2);
}

//function to assign NULL to unassigned pointers in structs 
void nullify_node(ListNode* node) {
node->left = NULL;
node->right = NULL;
}
void nullify_list(LinkedList* list) {
list->middle = NULL;
}
//sorts the list so that the leftmost node has smallest value
void insert_node(LinkedList* list, int value) {
ListNode* new_node = init_node();
new_node->value = value;
nullify_node(new_node);
printf("initialized new noden");

//if no node was ever inserted in the list, make the new node be the middle one
if (list->left_size+list->right_size==0) { 
list->middle = new_node;
list->right_size += 1;
}
else {
//make a temporary node to traverse the list
ListNode* temp =list->middle;
nullify_node(temp);
printf("initialized tempn");

//if given value is smaller or equal to that of the middle node, traverse to the left
if (value <= list->middle->value) {
int left_size = list->left_size;

//if no node was ever inserted to the left, make the new node the first left node
if (left_size == 0) {
printf("initialized first left");
list->middle->left=new_node;
list->left_size += 1;

}
else {
//temp->left should be the left node to new node
//traverse temp until temp->left->value is smaller than value while temp->value is bigger than value
for (; left_size > 0; left_size--) {
if (temp->left) {//only if temp->left exist check temp->left->value
//if temp->left->value is bigger than value, hop once more
if (value < temp->left->value) {
temp = temp->left;
}//if it is the same or bigger, stop there.
else {
break;
}
}
}
//put new node between temp->left and temp
if (temp->left) {
new_node->right = temp;
new_node->left = temp->left;
temp->left->right = new_node;
temp->left = new_node;
}
else {//if temp was the leftmost node, make new node be the leftmost node.
new_node->right = temp;
temp->left = new_node;
}

//balance list
list->left_size += 1;
if (list->left_size > list->right_size + 1) {
list->middle = list->middle->left;
list->left_size -= 1;
list->right_size += 1;
}


}
}//traverse to the right side of the list if given value is bigger than the middle node's value
else if (value > list->middle->value) {
int right_size = list->right_size;
//since middle value is considered as one of the right side's nodes, hop minus 1 time than the right_size
for (; right_size > 1; right_size--) {
if (temp->right) {// if temp has a right node, compare temp->right->value with given value
//if given value is bigger, move temp to the right
if (value > temp->right->value) {
temp = temp->right;
}
else {
break;
}
}               
}
//if temp wasn't the rightmost node,
if (temp->right) {
//insert new node between temp and temp->right
new_node->left = temp;
new_node->right = temp->right;
temp->right->left = new_node;
temp->right = new_node;
}
else {//if temp was the rightmost node, make the new node be the rightmost node
temp->right = new_node;
new_node->left = temp;
}
//balance list
list->right_size += 1;
if (list->right_size > list->left_size + 1) {
list->middle = list->middle->right;
list->left_size += 1;
list->right_size -= 1;
}
}

}
}
void print_list(LinkedList*list) {
//move to leftmost node
ListNode*temp = list->middle;
printf("middlevalue:%d", temp->value);
for (int i = 0; i < list->left_size ; i++) {
//when input 2, 3, 5, 2, from the second interation temp is nullptr for some reason
temp = temp->left;
printf("%dth value:%d",i, temp->value);
}
for (int j = 0; j < list->left_size + list->right_size; j++) {
printf("t%d", temp->value);
temp = temp->right;
}
}

Answer 1

init_node和init_list都假定为硬结构包装，这是完全错误的。它们看起来应该像这样(尽管缺少错误检查):

ListNode *init_node(int value) // note argument
{
ListNode * p = malloc(sizeof *p);
p->left = p->right = NULL;
p->value = value;
return p;
}
LinkedList *init_list()
{
LinkedList *p = malloc(sizeof *p);
p->left_size = p->right_size = 0;
p->middle = NULL;
return p;
}

注意init_node中添加的参数。这允许这样做:

ListNode* new_node = init_node();
new_node->value = value;
nullify_node(new_node);

变成:

ListNode *new_node = init_node(value);

接下来，你显然很难理解指针是如何工作的。当你这样做时:

//make a temporary node to traverse the list
ListNode *temp = list->middle;
nullify_node(temp);
printf("initialized tempn");

您实际上将temp指向您的list->middle指向的相同节点，然后将该节点的左指针和右指针清空。也就是说，你刚刚把左边或右边的任何东西都泄露到了以太中。更糟糕的是，大小参数(您在整个代码中严重依赖的参数)保持原样，这意味着它们现在正在考虑不再存在的列表微粒(因为您使用nullify_node孤立/泄露了它们)。

删除这一行:

nullify_node(temp);

，理想情况下，随着新的init_node实现的出现，只需删除该函数。它实际上毫无价值。

最后，print_list。实参应该是const，并且不应该依赖于LinkedList结构体的大小成员。例如

void print_list(const LinkedList *list)
{
//move to leftmost node
const ListNode *temp = list->middle;
if (temp)
{
while (temp->left)
temp = temp->left;
}
while (temp)
{
printf("%d ", temp->value);
temp = temp->right;
}
}