Это не дубликат вопроса с похожим именем. Это включает в себя OOP, а также новые и удаленные вызовы.
Я пытаюсь написать функцию, которая будет перебираться в конец связанного списка, а затем удалять выделенную память в куче последнего узла.
Вот мой код:
void LinkedList::delete_back(){
if(head != NULL){
ListNode *end = head;
while(end->next != NULL)
end = end->next;
delete end;
}
size--;
}
И вот мои определения классов:
class ListNode{
public:
Item data;
ListNode *next;
};
class LinkedList{
private:
ListNode *head;
int size;
public:
LinkedList();
~LinkedList();
bool empty();
void insert_front(Item i);
void insert_back(Item i);
void delete_front();
void delete_back();
void print();
};
Annddddd..... это проблема, я получаю сообщения об ошибках, подобные этому из valgrind, некоторые из которых указывают недопустимое чтение 4-го размера, другие указывают недопустимое чтение 8-го размера:
==4385== Invalid read of size 4
==4385== at 0x400CAA: LinkedList::print() (in /home/jon/jball2_lab06/linkedlist)
==4385== by 0x400EDD: main (in /home/jon/jball2_lab06/linkedlist)
==4385== Address 0x5a04f30 is 0 bytes inside a block of size 16 free'd
==4385== at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4385== by 0x400C5E: LinkedList::delete_back() (in /home/jon/jball2_lab06/linkedlist)
==4385== by 0x400E99: main (in /home/jon/jball2_lab06/linkedlist)
Я опубликую оставшиеся ошибки, если это поможет, но я не чувствую, что ударяю пространство 4 раза на 50 строк, если мне это не нужно. Кто-нибудь знает, что это может быть? Что я делаю не так?
UPDATE----------------------- Я редактировал код:
void LinkedList::delete_back(){
if(head != NULL){
ListNode *end = head;
ListNode *prev_end;
while(end->next != NULL){
prev_end = end;
end = end->next;
}
prev_end->next = NULL;
if(end != NULL) delete end;
size--;
}
}
Теперь я получаю более недопустимое чтение ошибок размера 8/4 и неправильных ошибок free/delete
==5294== Invalid free() / delete / delete[] / realloc()
==5294== at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
и это:
==5294== Use of uninitialised value of size 8
==5294== at 0x400C3D: LinkedList::delete_back() (in /home/jon/jball2_lab06/linkedlist)
==5294== by 0x400EEC: main (in /home/jon/jball2_lab06/linkedlist)
Вот тестовый код im, использующий:
for(Item i = 50; i < 100; i++){
ll.insert_back(i);
cout << "Inserted [" << i << "] in back.\n";
}
ll.print();
for(int i = 0; i < 50; i++)
ll.delete_back();
cout << "Removed 50 elements from the back.\n";
ll.print();
Это происходит, когда последний элемент удаляется из списка с помощью delete_back()
UPDATE----------------------- -
Проблема заключалась в том, что если end-> next имеет значение null, чем цикл while никогда не будет выполнен, prev_end никогда не будет инициализирован. Добавлено ответ с исправлениями.
Когда у вас есть список, содержащий не менее 2 узлов, и вы delete
последний. В предыдущей записи все еще есть ссылка на последнюю (которая больше не существует), что приводит к неопределенному поведению к моменту, когда ваша print
пытается разыменовать недействительный (висячий) указатель. Вместо:
ListNode *end = head;
while(end->next != NULL)
end = end->next;
delete end;
ты должен сделать:
if (head->next == NULL) {
delete head;
head = NULL;
}
else {
ListNode *nextToEnd = head;
ListNode *end = head->next;
while (end->next != NULL) {
nextToEnd = end;
end = end->next;
}
delete end;
nextToEnd->next = NULL;
}
вы не устанавливаете новый конечный узел равным нулю.
Например:
A-> В → C-> NULL
Когда вы удаляете C, B следующий - свисающий указатель
Поэтому в функции удаления вам нужно перейти ко второму последнему узлу и установить его рядом с NULL.
В приведенном выше примере после удаления C список должен выглядеть так:
A-> B-> NULL вместо A-> B → (свисание)
Таким образом, вы можете удалить B в следующей операции delete_back.
Вы можете сделать что-то вроде ниже
void LinkedList::delete_back(){
if(head != NULL){
ListNode *end = head;
//This if block is for when only one element is left
if(end->next == NULL)
{ delete end;
end = NULL;
}
else
while(end!= NULL)
{
if(end->next) /// reach the second last element
if(end->next->next==NULL)
{
delete end->next; //delete the last element
end->next=NULL; // set the next of second last element to NULL
}
end=end->next;
}
size--;
}
}
Не забудьте обновить next
новый элемент.
void LinkedList::delete_back(){
if(head != NULL){
ListNode *end = head;
ListNode *prev_end;
while(end->next != NULL)
{
prev_end = end;
end = end->next;
}
prev_end->next = 0;
delete end;
}
Кроме того, если вы опустошили список, установите главу в NULL.
Самый простой код для удаления:
void DeleteAtLast(){
node *temp=head;
while(temp->next->next!=NULL){
temp=temp->next;
}
temp-next=NULL;
}
как это должно работать
void del_rear()
{
struct node *end, *last
if (head->next != NULL) {
*end=head;
while(end->next!=null){
*last=end;
end=end->next;
}
free(end);
last->next=null;
}
else
{
pf("list is empty\n");
}
}
Исправлены все проблемы.
Код:
void LinkedList::delete_back(){
if(head != NULL){
ListNode *end = head;
if(end->next != NULL){
ListNode *prev_end;
while(end->next != NULL){
prev_end = end;
end = end->next;
}
prev_end->next = NULL;
delete end;
}
else {
delete head;
head = NULL;
}
size--;
}
}
size
в конце ...