Я вставляю узел в двоичное дерево поиска и столкнулся с непредвиденным поведением.
Мой вопрос: почему последняя строка в функции insert
не является обязательной?
Последняя строка позаботится о рекурсивном случае, и она должна быть обязательной, но когда я запускаю без последней строки, она также работает.
Это работает, значит, он успешно вставил узел в BST.
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *left;
struct node *right;
};
typedef struct node Node;
struct node *insert(Node *root, int val)
{
if (root == NULL){
struct node *root = malloc(sizeof(struct node));
root->data = val;
root->left = root->right = NULL;
return root;
}
if (root->data < val)
root->right = insert(root->right,val);
else if (root->data > val)
root->left = insert(root->left,val);
//return root; //WHY THIS LINE IS OPTIONAL
}
int main(){
Node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 5);
root = insert(root, 1);
}
@JohnBollinger Это работает, значит, он успешно вставляет узел в BST. Да, я также подозревал неопределенное поведение. Спасибо за подтверждение.
Попробуйте вставить одинаковые значения друг за другом.
Откуда вы знаете, что он успешно вставляет узел? Представленная программа не производит никакого вывода. Несмотря на это, ваша реализация C может рассматривать его как эквивалент int main(void) {}
.
Последняя строка в insert()
не обязательна, но только в том случае, если вы готовы смириться с неопределенным поведением. В вашем конкретном случае UB работает правильно, и это, безусловно, один возможность UB.
На самом деле, это одна из его наиболее коварных функций, поскольку кажущееся правильное поведение может привести к тому, что ваш код с ошибками будет выпущен для вас, бедных ничего не подозревающих пользователей :-)
Например, когда стек перемещается вверх и вниз из-за вызовов функций, может случиться так, что предыдущее значение root
будет возвращено просто потому, что вы не загружаете в него новое значение. И, если новое значение такое же, как и предыдущее, уже находящееся в стеке, вполне может показаться, что оно работает.
Однако тот факт, что он работает в одном конкретном случае, делает нет хорошей идеей полагаться на него.
Дальнейшее расширение произвольных значений, рассмотрим этот код:
#include<stdio.h>
int get42(void) { return 42; }
int getX(void) {}
int main(){
int x = get42();
//printf("123456789\n");
int y = getX();
printf("%d\n", x);
printf("%d\n", y);
}
Имея в виду, что это UB, поэтому он может действовать по-разному для вас, для меня это дает:
prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
4 | int getX(void) {}
| ^
42
42
Таким образом, несмотря на предупреждение, кажется, что оно дает то же значение, что и предыдущий вызов функции. Вы можете проверить это, раскомментировав printf()
и увидев:
prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
4 | int getX(void) {}
| ^
123456789
42
10
10
есть возвращаемое значение из вызова printf
(он возвращает количество напечатанных символов, девять цифр и \n
).
Итак, в этом случае очень похоже, что пропуск оператора return
просто позволит вызывающей стороне выбрать все, что было в стеке из предыдущего вызова (или какое-то произвольное значение, если это первый вызов на этой глубине), например с:
#include<stdio.h>
int get42(void) { return 42; }
int getX(void) {}
int main(){
int x = 42;//get42();
//printf("123456789\n");
int y = getX();
printf("%d\n", x);
printf("%d\n", y);
}
производство для меня:
prog.c: In function ‘getX’:
prog.c:4:17: warning: control reaches end of non-void function [-Wreturn-type]
4 | int getX(void) {}
| ^
42
-1539029341
Но, как указывалось ранее, не полагайтесь на это. Поведение может измениться, когда вы переключитесь на новый компилятор, новую версию компилятора, новую машину или даже решите скомпилировать его в субботу вместо рабочего дня :-)
Что для вас значит «работает»? Вы не представили ничего, что свидетельствовало бы об успешном построении BST, содержащего указанные элементы. Однако даже если бы вы это сделали, не исключено, что иногда это может быть проявлением неопределенного поведения вашей программы.