У меня есть проблема со связанным списком, которую я попытался решить ниже. Буду признателен за любой вклад в мой подход, правильность алгоритма (и даже стиль кодирования). Проблема вызывает функцию, которая удаляет все вхождения int в круговом связанном списке и возвращает любой узел из списка или NULL (когда список нулевой).
Вот некоторый код C ++, который у меня есть:
struct Node{
Node* next;
int data;
};
Node* deleteNode(Node* &node, int num){
if(!node){
return NULL;
}
Node* given = node;
Node* del;
while(node->next != given){
if(node->next->data == num){
del = node->next;
node->next = node->next->next;
delete del;
}
node = node->next;
}
//Check if the first node needs to be deleted, with variable node pointing to last element
if(given->data == num){
node->next = given->next;
delete given;
}
return node;
}
delete node;
должно быть delete del;
,
Также используйте Node* node
в качестве параметра, а не Node* &node
что предотвратит передачу не-значений
постскриптум Забыли точку с запятой после определения структуры? 🙂
Не следуя всей вашей логике, я могу сразу увидеть, что этот код не может работать.
Вы проверяете, что список ввода пуст, и это единственный случай, когда ваш код возвращает NULL
, Но что произойдет, если вам передадут список, в котором все элементы должны быть удалены?
Эта проблема также имеет тонкость в этом. Чтобы проверить, что вы заполнили циклический список, вам нужно сравнить его с первым адресом, чтобы узнать, не вернулись ли вы к началу. Однако, если этот элемент был удален, то по стандарту C ++ вы даже не разрешается использовать его адрес в сравнении.
Чтобы избежать двух проходов по удаляемым элементам, одним из возможных трюков является «разорвать цикл» при запуске итерации, чтобы вы могли проверить NULL
вместо проверки адреса начального узла.