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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
TonyPride
2 / 2 / 1
Регистрация: 22.10.2012
Сообщений: 47
#1

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

23.06.2013, 18:00. Просмотров 1309. Ответов 2
Метки нет (Все метки)

Добрый день.
Написал программу, которая ищет в файле неиспользуемые переменные, т.е. те, которые объявлены. Всё в общем-то работает, но препод говорит, что нужно освободить память. Поставил обнуление локальных переменных в конце функций и в 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 минут
Люди добрые, подкиньте мысль, пожалуйста, "автомат" горит!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2013, 18:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Освобождение памяти, удаление бинарного дерева (C++):

Удаление объекта и освобождение памяти - C++
Есть вот такой код. Интересуют выделенные ф-и. Последняя ясна - мы просто возвращаем память нашей ОС. Предпоследняя уничтожает объект...

Удаление из бинарного дерева - C++
Здравствуйте! Помогите с удалением узла из бинарного дерева. Номер узла вводится пользователем #include &quot;stdafx.h&quot; #include...

Удаление элемента из бинарного дерева - C++
Ругается компилятор в Visual Studio при выполнении кода удаления элемента, а именно в том месте, где нужно удалить элемент с двумя...

Удаление бинарного дерева по слоям - C++
вот задачка такая встала и ни че в голову не приходит. как будет выглядеть функция чтоб удаляла бинарное дерево по слоям? плиззз...

Удаление узла бинарного дерева - C++
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени помогите плиз. .cpp #include &lt;iostream&gt;...

Удаление Узла бинарного дерева - C++
Добрый вечер. Имеем Бинарное дерево поиска. При удалении некоторого узла . возникают три случая. Один из случаев , наличие у...

2
simkara26
2 / 2 / 0
Регистрация: 26.05.2013
Сообщений: 36
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; 
}
Этой же функцией легко освободить любое из поддеревьев и любой "лист", передав ей указатель на него... Надо только в этих случаях не забывать обнулять указатели освобожденных элементов
1
TonyPride
2 / 2 / 1
Регистрация: 22.10.2012
Сообщений: 47
23.06.2013, 18:12  [ТС] #3
Мне говорили, достаточно обнулить корень, но это следует выполнять после каждой передачи дерева в функцию, т.е. получается у меня цикл по файлу и, при каждом повторении цикла, дерево обнуляется и строится заново. Может быть я не правильно понял смысл. Спасибо за ответ, попробую ваш способ.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.06.2013, 18:12
Привет! Вот еще темы с ответами:

Удаление вершины бинарного дерева - C++
Как удалять вершины бинарного дерева вместе с потомками?

Удаление Узла Бинарного Дерева. - C++
Добрый День.Возникла проблема с реализацией части функции контейнера для удаления элемента с двумя узлами(по всем правилам бинарных...

Удаление элемента из сбалансированого бинарного дерева - C++
Задание: написать программу, которая создает сбалансированное бинарное дерево, написать процедуру, которая удалит все парные элементы...

Удаление элементов из бинарного дерева (не дерево поиска) - C++
Задание заключается в создании бинарного дерева, из букв введенной строки, обходе дерева и удалении согласных букв из дерева. проблема...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru