Очистка динамической памяти в структуре

@Faltfromoss · Регистрация: 28.03.2014

Author24 — интернет-сервис помощи студентам

И снова здравствуйте. Столкнулся с проблемой. Есть задача - написать программу "Телефонный справочник" на основе класса Tree (бинарное дерево), реализовать там всякие функции, не суть важно какие. Класс Tree есть, описывать его не буду, вопрос не в нем. Есть структура, которая содержит данные абонента, и которая является узлом бинарного дерева:

C++

struct Subscriber
{
   char * FIO;
   char * Town;
   char * Number;
   int YearOfBirth;
 
   Subscriber * left, * right, * parent;
};

В ней описаны указатели на память, которая будет выделяться при создании "абонента". Ок. Есть некая функция Add (Subscriber *), которая создает "абонента" и помещает его в нужную позицию в бинарном дереве. Функция работает замечательно, без вопросов.
А есть еще такая замечательная функция Del (Subscriber *), которая должна, соответственно, абонента удалять из базы. Весь код приводить не буду, опишу его алгоритм:

C++

void Del (Subscriber *z)
{
... // здесь создается временный указатель Subscriber y, который будет удалён в конце функции.
    // затем выполняются манипуляции с указателями, в результате которых либо в z скопируются данные из y и y удаляется
    // или y == z, удаляется элемент по этому адресу, о чем говорит команда:
 delete y;
}

Вот в связи с этим у меня возникли вопросы. Если бы я создал структуру такого плана:

C++

struct Subscriber
{
   char FIO [50];
   char Town [30];
   char Number [15];
   int YearOfBirth;
 
   Subscriber * left, * right, * parent;
};

То здесь всё ясно, память выделяется в стеке и удаляется вместе с указателем. Но мне захотелось выделить память динамически, в куче. И, по моим соображениям, вот эта команда:

C++

1	... delete y; ...

Удалит структуру со всеми указателями и значением int YearOfBirth, но данные FIO, Town, Number останутся где-то в оперативе и будут висеть до последнего. Собственно для очистки динамически выделенной памяти во время удаления объекта и были придуманы деструкторы для классов. И в структурах их тоже можно применять. В общем попробовал решить вопрос сначала так:

C++

...
   delete [] y -> FIO;
   delete [] y -> Number;
   delete [] y -> Town;
   delete y;
...

После чего мне по завершении программы (не во время выполнения!) выскакивает такое окно:

Попробовал аналогичным путем прописать деструктор в структуре:

C++

struct Subscriber
{
   char * FIO;
   int YearOfBirth;
   char * Town;
   char * Number;
 
   Subscriber * left, * right, * parent;
public:
   ~Subscriber () {
        delete [] FIO;
        delete [] Number;
        delete [] Town;}
};

В результате при попытке удаления объекта - то же самое. И, кстати, ошибки появляются не всегда. Можно запустить прогу, создать и удалить 2 - 3 - х абонентов, и все будет путем. Поглядел отладчиком, память очищается... А в какой-то определенный момент при удалении может вылезти что-то подобное :/ Я не понимаю. Оно либо не работало бы вообще, либо работало бы нормально, а не так как у меня - работает до определенной точки.

PS кому нужно выложил весь код в архиве, он там поделен на 4 файла. Из меню реализованы пока только 2 функции - добавление и удаление. Ну и 3 - я - вывод списка на экран.

Croessmah · 14.07.2014, 23:55

Реализуйте конструктор, конструктор копий, оператор присваивания и деструктор (семантику перемещения при желании).
Ну еще как вариант умные указатели использовать.
А еще лучше воспользуйтесь std::string для хранения строк, а не голыми указателями.

Vourhey · 14.07.2014, 23:59

Сообщение от Faltfromoss

В результате при попытке удаления объекта - то же самое. И, кстати, ошибки появляются не всегда. Можно запустить прогу, создать и удалить 2 - 3 - х абонентов, и все будет путем. Поглядел отладчиком, память очищается... А в какой-то определенный момент при удалении может вылезти что-то подобное :/ Я не понимаю. Оно либо не работало бы вообще, либо работало бы нормально, а не так как у меня - работает до определенной точки.

Значит у тебя где-то в коде бага, и ты портишь кучу. Можно проверить под Valgrind'ом, например, он покажет, если где-то переполнение, или память утекает и так далее.

@castaway · 15.07.2014, 07:22

Выложи код под CUT.

@ShadowFirst · 15.07.2014, 16:49

Если у тебя есть готовый класс дерева, то он у тебя наверное как контейнер сделан, если нет - плохо. Просто суть вот в чем, если у тебя класс поддерживает контейнеры, то создаешь свой класс вместо структуры:

C++

class Subscriber
{
   Subscriber::Subscriber ();
   virtual ~Subscriber ();
private:
   char * FIO;
   char * Town;
   char * Number;
   int YearOfBirth;
};

Ну ты понял со всеми пологающими атрибутами.

А вот в дереве у тебя должно быть:

C++

template <class T>
struct treeStruct {
    T data;
    treeStruct * left, * right, * parent;
};

Если у тебя не подобным образом то организация программы не очень хорошая, так как по фен шую класс дерева должен быть универсальным для любых классов или чисел или что ты туда запихнешь.

@Faltfromoss · 16.07.2014, 00:23 **[ТС]**

Сообщение от castaway

Выложи код под CUT.

Вообще он есть в архиве, но если нужно могу и здесь. Просто его там много. Итак:

Tree.h:

Кликните здесь для просмотра всего текста

C++

#ifndef TREE_H
#define TREE_H
 
 
struct Subscriber
{
   char * FIO;
   int YearOfBirth;
   char * Town;
   char * Number;
 
   Subscriber * left, * right, * parent;
public:
   ~Subscriber () {
        delete [] FIO;
        delete [] Number;
        delete [] Town;}
};
 
class Tree
{
   // корень
   Subscriber * root;
   int Counter;
public:
   Tree();
   ~Tree();
   // печать от указанного узла
   void Print(Subscriber * Node);
   // поиск от указанного узла
   Subscriber * Search(Subscriber * Node, char * key);
   // min от указанного узла
   Subscriber * Min(Subscriber * Node);
   // max от указанного узла
   Subscriber * Max(Subscriber * Node);
   // следующий для указанного узла
   Subscriber * Next(Subscriber * Node);
   // предыдущий для указанного узла
   Subscriber * Previous(Subscriber * Node);
   //// вставка узла
   void Insert(Subscriber * z);
   // удаление ветки для указанного узла, 
   // 0 - удаление всего дерева
   void Del(Subscriber * z = 0);
   //// получить корень
   Subscriber * GetRoot();
};
 
 
#endif

Func.h

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#include <conio.h>
#include <cstring>
#include "Tree.h"
using namespace std;
 
#ifndef FUNC_H
#define FUNC_H
 
int menu ()
{
    int key;
    system ("cls");
        cout<<endl<<"\t\t\tТелефонный справочник"<<endl<<endl;
        cout<<"\t\t\t\tМеню"<<endl<<endl;
        cout<<"\t1 - Добавление абонентов в базу."<<endl<<endl;
        cout<<"\t2 - Удаление абонентов из базы."<<endl<<endl;
        cout<<"\t3 - Вывод списка абонентов на экран."<<endl<<endl;
        cout<<"\t4 - Поиск абонентов по телефонному номеру или фамилии."<<endl<<endl;
        cout<<"\t5 - Распечатка в алфавитном порядке абонентов из заданного диапазона"<<endl<<"\t    номеров или фамилий"<<endl<<endl;
        cout<<"\t6 - Возможность сохранения найденной информации в файл."<<endl<<endl;
        cout<<"\t7 - Сохранение базы в файл."<<endl<<endl;
        cout<<"\t8 - Загрузка базы из файла."<<endl<<endl;
        cout<<"\tEsc - выход из программы"<<endl<<endl;
        key = _getch();
        return key;
}
 
void Add (Tree & T)     //добавление абонента
{
    Subscriber *temp = new Subscriber;
    char buffer [1000];
    cout<<endl<<endl<<"\tВведите фамилию, имя, отчество абонента:"<<endl<<"\t";
    gets_s (buffer);
    temp->FIO = new char [10];
    strcpy (temp->FIO, buffer);
    cout<<endl<<"\tВведите год рождения абонента: ";
    cin>>temp->YearOfBirth;
    cin.ignore(cin.rdbuf()->in_avail());    //очистка буфера после cin>>
    cout<<endl<<"\tВведите город проживания абонента: ";
    gets_s (buffer);
    temp->Town = new char [strlen (buffer) + 1];
    strcpy (temp->Town, buffer);
    cout<<endl<<"\tВведите номер телефона абонента: ";
    gets_s (buffer);
    temp->Number = new char [strlen (buffer) + 1];
    strcpy (temp->Number, buffer);
    T.Insert (temp);
}
 
 
void Delete (Tree & T)
{
    system ("cls");
    cout<<endl;
    T.Print (T.GetRoot());
    cout<<endl<<endl<<"\tВведите часть фамилии или фамилию целиком удаляемого абонента:";
    cout<<endl<<endl<<"\t";
    char buffer [256];
    int temp = 0;
    gets_s (buffer);
    Subscriber *S = T.Search (T.GetRoot (), buffer);
    if (S)  //если результат поиска не нулевой
    {
        do
        {
            system ("cls");
            cout<<endl<<endl<<"\tПо вашему запросу был найден абонент: "<<S -> FIO<<endl<<endl;
            cout<<"\tВы подтверждаете удаление записи? (Y/N): ";
            temp = _getch ();
        } while (temp != 110 && temp != 121 && temp != 78 && temp != 89);
        if (temp == 'y' || temp == 'Y')
        {
            T.Del (S);
            cout<<endl<<endl<<"\tУдаление выполнено успешно"<<endl;
        }
        else
            return;
    }
    else
    {
        cout<<endl<<endl<<"\tПо вашему запросу не найдено ни одной записи. Повторите поиск."<<endl<<endl;
    }
}
#endif

Tree.cpp

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#include <string.h>
#include "Tree.h"
using namespace std;
 
 
Tree::Tree()
: root (0), Counter (0)
{
}
 
Tree::~Tree()
{
   Del();
}
 
// Рекурсивный обход дерева
void Tree::Print(Subscriber * Node)
{
   if(Node != 0)
   {
      Print(Node->left);
            cout  << "   "<<++Counter<<". "<<Node->FIO;
    (strlen (Node->FIO)<24)?cout<<"\t\t": cout<<"\t";
            cout<< Node->YearOfBirth<<"\t"
                << Node->Town<<"\t"
                << Node->Number<<"\t"
                << endl << endl;
      Print(Node->right);
    /*++Counter;*/
   }
}
 
Subscriber * Tree::Search(Subscriber * Node, char * k)
{
    int n = strlen (k);
   // Пока есть узлы и ключи не совпадают
   while(Node != 0 && strnicmp(k, Node->FIO, n) != 0)
   {
      if(strnicmp(k, Node->FIO, n) < 0)
         Node = Node->left;
      else
         Node = Node->right;
   }
   return Node;
}
 
Subscriber * Tree::Min(Subscriber * Node)
{
   // Поиск самого "левого" узла
   if(Node != 0)
      while(Node->left != 0)
         Node = Node->left;
    
   return Node;
}
 
Subscriber * Tree::Max(Subscriber * Node)
{
   // Поиск самого "правого" узла
   if(Node != 0)
      while(Node->right != 0)
         Node = Node->right;
    
   return Node;
}
 
Subscriber * Tree::Next(Subscriber * Node)
{
   Subscriber * y = 0;
   if(Node != 0)
   {
      // если есть правый потомок
      if(Node->right != 0)
         return Min(Node->right);
        
      // родитель узла
      y = Node->parent;
      // если Node не корень и Node справа
      while(y != 0 && Node == y->right)
      {
         // Движемся вверх
         Node = y;
         y = y->parent;
      }
   }
   return y;
}
 
Subscriber * Tree::Previous(Subscriber * Node)
{
   Subscriber * y = 0;
   if(Node != 0)
   {
      // если есть левый потомок
      if(Node->left != 0)
         return Max(Node->left);
        
      // родитель узла
      y = Node->parent;
      // если Node не корень и Node слева
      while(y != 0 && Node == y->left)
      {
         // Движемся вверх
         Node = y;
         y = y->parent;
      }
   }
   return y;
}
 
Subscriber * Tree::GetRoot()
{
   return root;
}
 
void Tree::Insert(Subscriber * z)
{
   // потомков нет
   z->left = NULL;
   z->right = NULL;
 
   Subscriber * y = NULL;
   Subscriber * Node = root;
 
   // поиск места
   while(Node != 0)
   {
      // будущий родитель
      y = Node;
      if(strcmp(z->FIO, Node->FIO) < 0)
         Node = Node->left;
      else
         Node = Node->right;
   }
   // заполняем родителя
   z->parent = y;
 
   if(y == 0) // элемент первый (единственный)
      root = z;
   // чей ключ больше?
   else if(strcmp(z->FIO, y->FIO) < 0) 
      y->left = z;
   else
      y->right = z;
   Counter++;
}
 
void Tree::Del(Subscriber * z)
{
   // удаление куста
   if(z != 0)
   {
      Subscriber * Node, * y;
 
      // не 2 ребенка
      if(z->left == 0 || z->right == 0)
         y = z;
      else
         y = Next(z);
 
      if(y->left != 0)
         Node = y->left;
      else
         Node = y->right;
 
      if(Node != 0)
         Node->parent = y->parent;
      // Удаляется корневой узел?
      if(y->parent == 0)
         root = Node;
      else if(y == y->parent->left) // слева от родителя?
         y->parent->left = Node;
      else
         y->parent->right = Node;  // справа от родителя?
        
      if(y != z)
      {
         // Копирование данных узла
         strcpy (z->FIO, y->FIO);
         z->YearOfBirth = y->YearOfBirth;
         strcpy (z->Town, y->Town);
         strcpy (z->Number, y->Number);
      }
 
    delete y;
     
   }
   else // удаление всего дерева
      while(root != 0)
         Del(root);
}

UseTree.cpp

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#include <Windows.h>
#include <cstring>
#include "Tree.h"
#include "Func.h"
using namespace std;
 
int main ()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    setlocale (LC_ALL, "rus");
    Tree Telefon;
    int key = 0;
    do
    {
        key = menu ();
        switch (key)
        {
        case '1':           
            system ("cls");
            Add (Telefon);
            do
            {
                cout<<endl<<"\tBackspace - выход в главное меню\n\n\tEsc - выход из программы";
                key = _getch ();
            } while (key !=8 && key!=27);
            break;
        case '2':
            do
            {
                system ("cls");
                Delete (Telefon);
                cout<<endl<<"\tBackspace - выход в главное меню\n\n\tEsc - выход из программы";
                key = _getch ();
            } while (key !=8 && key!=27);
            break;
        case '3':
            do
            {
                system ("cls");
                cout<<endl<<"\tФИО"<<"\t\tГод рожд.\tГород прож.\tНомер телефона"<<endl<<endl;
                Telefon.Print(Telefon.GetRoot());
                cout<<endl<<"\tBackspace - выход в главное меню\n\n\tEsc - выход из программы";
                key = _getch ();
            } while (key !=8 && key!=27);
            break;
 
        default:
            break;
        }
    } while (key != 27);
}

Добавлено через 10 минут

Сообщение от ShadowFirst

Если у тебя есть готовый класс дерева, то он у тебя наверное как контейнер сделан, если нет - плохо. Просто суть вот в чем, если у тебя класс поддерживает контейнеры, то создаешь свой класс вместо структуры:

C++

class Subscriber
{
* *Subscriber::Subscriber ();
* *virtual ~Subscriber ();
private:
* *char * FIO;
* *char * Town;
* *char * Number;
* *int YearOfBirth;
};

Ну ты понял со всеми полагающими атрибутами.

А вот в дереве у тебя должно быть:

C++

template <class T>
struct treeStruct {
* * T data;
* * treeStruct * left, * right, * parent;
};

Если у тебя не подобным образом то организация программы не очень хорошая, так как по фен шую класс дерева должен быть универсальным для любых классов или чисел или что ты туда запихнешь.

Просто материал проходили в таком формате - структура это узел бинарного дерева и класс Tree - определяет методы управления этим деревом. И на основе этой конструкции нужно забацать справочник.
У меня, в принципе сейчас задача не стоит шаблонный класс описать, нужно сделать под определенный тип - Subscriber. Кроме того что такое virtual я пока понятия не имею :/
Если бы создал поля структуры не в куче, а в стэке, что собственно я могу сделать и сейчас, то и вопросов не было. Но вот захотелось выделить память динамически и теперь уже из принципа хочется понять что не так.

Добавлено через 2 часа 52 минуты
И еще, люди, подскажите как это всё добро сохранить в файл? Как там сохранить одну строку, я вроде бы понимаю, но как мне сохранить все дерево с сохранением его структуры и данных, тоже уперся в стену в данном вопросе :/

@castaway · 16.07.2014, 07:53

ФИО всегда умещается в 9 символов?
Выделяй память под поля Subscriber в конструкторе, раз ты освобождаешь её в деструкторе.

Croessmah Неэпический 17870 / 10635 / 2054 Регистрация: 27.09.2012 Сообщений: 26,737 Записей в блоге: 1
	14.07.2014, 23:55	2
	Реализуйте конструктор, конструктор копий, оператор присваивания и деструктор (семантику перемещения при желании). Ну еще как вариант умные указатели использовать. А еще лучше воспользуйтесь std::string для хранения строк, а не голыми указателями. 0

Vourhey Почетный модератор 7393 / 2639 / 281 Регистрация: 29.07.2006 Сообщений: 13,696
	14.07.2014, 23:59	3
	Сообщение от Faltfromoss В результате при попытке удаления объекта - то же самое. И, кстати, ошибки появляются не всегда. Можно запустить прогу, создать и удалить 2 - 3 - х абонентов, и все будет путем. Поглядел отладчиком, память очищается... А в какой-то определенный момент при удалении может вылезти что-то подобное :/ Я не понимаю. Оно либо не работало бы вообще, либо работало бы нормально, а не так как у меня - работает до определенной точки. Значит у тебя где-то в коде бага, и ты портишь кучу. Можно проверить под Valgrind'ом, например, он покажет, если где-то переполнение, или память утекает и так далее. 0

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	15.07.2014, 07:22	4
	Выложи код под CUT. 0

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	16.07.2014, 07:53	7
	ФИО всегда умещается в 9 символов? Выделяй память под поля Subscriber в конструкторе, раз ты освобождаешь её в деструкторе. 0