Форум программистов, компьютерный форум CyberForum.ru

Освобождение памяти, удаление бинарного дерева - C++

Восстановить пароль Регистрация
 
TonyPride
2 / 2 / 1
Регистрация: 22.10.2012
Сообщений: 47
23.06.2013, 18:00     Освобождение памяти, удаление бинарного дерева #1
Добрый день.
Написал программу, которая ищет в файле неиспользуемые переменные, т.е. те, которые объявлены. Всё в общем-то работает, но препод говорит, что нужно освободить память. Поставил обнуление локальных переменных в конце функций и в main, но этого не достаточно. Со слов препода: "После каждого вызова функции дерево разрушается, затем строится с нуля, затем передаётся в следующую функцию".
Код прилагаю
Кликните здесь для просмотра всего текста
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<stdio.h> 
#include<conio.h>
#include<ctype.h>
#include<string.h>
#include<iostream>
#define N 200
using namespace std;
// описываем дерево
struct btree
{
  char name[N];
  int count; // число использований переменной
  struct btree *left, *right;
};
// описываем список типов данных
struct list
{ 
  char type[N];
  struct list *next;
};
//работа со списком
list *Ins_first(list *head, char *str)
{
    list *q=new list, *t;
    strcpy(q->type,str);
    q->next=NULL;
    if (head!=NULL) q->next=head;
    return q;
}
 
void Print_list(list *head)
{
     list *t = head;
     if (head==NULL) {cout<<"Empty List"<<endl;}
     cout<<"TYPES:"<<endl;
     while (t->next!=NULL)
     {
      cout<<t->type<<endl;
      t=t->next;
     }
     cout<<t->type<<endl;
}
 
list *Create_list()
{
     int i=0;
char *Types[] = {"char","define","double","float", "int","long", "FILE"};
list *first=NULL;
while (i<7)
{
    first=Ins_first(first, Types[i]);Print_list(first);
    i++;
}   
return first;
}
 
//проверка на принадлежность к буквам
int Letter(char ch)
{
  if (isalpha(ch)>0) return 1;
  if (ch=='_') return 1;
  return 0;
}
 
//разбиение на слова
int Words (char *String, char w[][N])
{
 int i=0, j=0, k=0, key=0, n=strlen(String);//i-буквы k-слово
 if(strstr(String, "(")!=0) {while(String[j]!='(') j++;} // если есть скобки, то всё что до них отсекается, например, если строка - объявление функции
 for (; j<=n; j++)//пока j меньше длины строки
if (Letter(String[j]) or (String[j]>='0' && String[j]<='9' && Letter(String[j-1]))) {w[k][i]=String[j]; i++; key=1; }
/*если элемент-слово/почёркивание, формируем
массив, с этим словом, плюсуем кол-во букв, счётчик=1*/
else
//иначе, если ключ есть, заканчиваем слово
if (key)
{w[k][i]='\0'; i=0; k++; key=0; }
 return k;
}
 
// Функция проверяет, является ли слово типом данных
int Type_Word(char *s, list *head)
{
    list *p=head;
while(p!=NULL)
{
 if (strcmp(s,p->type)==0)return 1;
 p=p->next;
}
delete p; return 0;
}
// вставка в дерево
void Ins_Btree (char *w, btree **q)
{
 
 if(*q == NULL)
 {
   *q=new btree;
   (*q)->left=(*q)->right=NULL;
   strcpy ((*q)->name, w);
   (*q)->count=1;
   q=NULL; return;
 }
 if (strcmp((*q)->name,w)==0)//строки равны
  {
   (*q)->count++;
   return;
  }
 if (strcmp((*q)->name,w)>0) //строка меньше
     Ins_Btree (w, &(*q)->left);
  else //строка больше
 Ins_Btree (w, &(*q)->right);
}
 
//Функция выводит всё дерево
void Print_Btree (btree *p)
{
  if (p==NULL) return;
   Print_Btree (p->left);
   cout<<p->name<<"  "<<p->count<<endl;
   Print_Btree(p->right);
   p=NULL;
}
 
// Функция выводит только те эл-ты дерева, значение count которых = 1
void Print_Result (btree *p)
{
  if (p==NULL) return;
   Print_Result (p->left);
   if(p->count==1) cout<<p->name<<"  "<<p->count<<endl;
   Print_Result(p->right); p=NULL;
}
// сравнение с уже имеющимися элементами дерева
int Compare (char *key, btree **node) // Функция определяет, является ли слово элементом дерева (по сути, укороченная и переделанная функция удаления из дерева)
{
//cout<<"Key:"<<key<<endl; // вывод слова, которое сравнивается с элементами дерева (для отладки)
if(*node == NULL) return 0;
if(strcmp((*node)->name,key)==0) {(*node)->count++; return 0;} // если слово является элементом дерева, то счётчик увеличивается, потому что данная переменная где-то использовалась
if(strcmp((*node)->name,key)<0) {if((*node)->right == NULL) return 0; else return Compare (key, &(*node)->right);}
if(strcmp((*node)->name,key)>0) {if((*node)->left == NULL) return 0; else return Compare (key, &(*node)->left);} 
node = NULL;
}
 
// Формирование дерева
void Build_tree(FILE *in)
{
list *L=NULL; // список типов данных
L=Create_list();
//cout<<"Current list is:"<<endl; Print_list(L);
char str1[N];  // строка для считывания и пр. операций
int i=0;
btree *q=NULL; // дерево переменных
char w[N][N];
int k=0;
 while(!feof(in))               // цикл по файлу
 {
 
   fgets (str1, N, in); // чтение строки
  // cout<<str1<<endl;
  /*разбиение на слова*/
  if(strstr(str1, "/*")==0 && strstr(str1, "//")==0) k=Words(str1, w); // если строка не закомментирована, то работаем с ней
   i=0;
   while(i!=k)
   {
              if(strcmp(w[i], "struct")==0) {L=Ins_first(L, w[i+1]); i++;} // если нашли пользовательский тип данных (слово после struct), добавляем его в список типов
        /*если первое слово - тип данных, то последующие слова заносятся в дерево*/
     if (Type_Word(w[0], L)==1) { /*cout<<"YES"<<endl;*/ i=1; while(i<k) {if(Type_Word(w[i], L)==0 && isalpha(w[i][0])) Ins_Btree(w[i], &q); i++;}}
        else {while(i<k) {if (Type_Word(w[i], L)==1) Ins_Btree(w[i+1], &q); Compare(w[i], &q); i++;}} /*если в "середине" строки нашли тип данных, то следующее слово заносится в дерево
  а также идёт сравнение слов с элементами дерева*/
   }
  }
  cout<<"Tree is: "<<endl; Print_Btree(q); // вывод всего дерева
  cout<<"Result is:"<<endl; Print_Result(q); // вывод результата
  q=NULL; L=NULL; return;
}
 
int main()
{//system( "color 17" );
    cout<<"**************************SEARCH NON USABLE VARIABLES***************************"<<endl; 
 FILE *f1;
 btree *root;
 char filename[N];
 while(1)
 {
         cout<<"Enter name of file"<<endl;
        gets(filename);
 f1=fopen(filename, "r");
 if(f1==NULL) printf ("Error!");
 else break;
}
 Build_tree(f1);
 root=NULL;
 fclose(f1);
 getch();
}

Вообще, основные манипуляции проходят в цикле в функции Build_tree, значит там следует "разрушать и перестраивать" дерево?
Заранее спасибо.

Добавлено через 9 часов 46 минут
Люди добрые, подкиньте мысль, пожалуйста, "автомат" горит!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2013, 18:00     Освобождение памяти, удаление бинарного дерева
Посмотрите здесь:

C++ удаление бинарного дерева по слоям С++
Удаление Узла Бинарного Дерева. C++
Освобождение памяти (удаление массива char) и raised exception class EAccessViolation C++
Удаление вершины бинарного дерева C++
Удаление Узла бинарного дерева C++
C++ Удаление объекта и освобождение памяти
C++ Удаление элементов из бинарного дерева (не дерево поиска)
C++ Удаление элемента из бинарного дерева

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
simkara26
2 / 2 / 0
Регистрация: 26.05.2013
Сообщений: 32
23.06.2013, 18:08     Освобождение памяти, удаление бинарного дерева #2
В каждом узле бинарного дерева должна быть пара указателей на левое (left) и правое (right) поддеревья (в "листьях" они нулевые). Освобождение всего дерева можно сделать с помощью следующей простой рекурсивной функции (TREE – структура узла дерева)

C++
1
2
3
4
5
void FreeTree( TREE * tree ) { 
    if (tree->left)   FreeTree(*tree->left); 
    if (tree->right)  FreeTree(*tree->right); 
    delete tree; 
}
Этой же функцией легко освободить любое из поддеревьев и любой "лист", передав ей указатель на него... Надо только в этих случаях не забывать обнулять указатели освобожденных элементов
TonyPride
2 / 2 / 1
Регистрация: 22.10.2012
Сообщений: 47
23.06.2013, 18:12  [ТС]     Освобождение памяти, удаление бинарного дерева #3
Мне говорили, достаточно обнулить корень, но это следует выполнять после каждой передачи дерева в функцию, т.е. получается у меня цикл по файлу и, при каждом повторении цикла, дерево обнуляется и строится заново. Может быть я не правильно понял смысл. Спасибо за ответ, попробую ваш способ.
Yandex
Объявления
23.06.2013, 18:12     Освобождение памяти, удаление бинарного дерева
Ответ Создать тему
Опции темы

Текущее время: 18:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru