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

Создание бинарного дерева поиска - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Файлы: вывести предложения, состоящие из заданного количества слов http://www.cyberforum.ru/cpp-beginners/thread839556.html
написать программу, которая считывает текст из файла и выводит на экран только предложения состоящие из заданного количества слова.
C++ Считая, что количество символов в слове не превосходит 20, определить сколько в файле имеется слов, состоящих из одного, 2, 3 и.т.д Добрый день,помогите пожалуйста сделать Дан символьный файл f. Считая, что количество символов в слове не превосходит 20, определить сколько в файле имеется слов, состоящих из одного, 2, 3 и.т.д. символов. найти количество слов в файле f http://www.cyberforum.ru/cpp-beginners/thread839552.html
Создать тип данных Многоразрядное число C++
Создать тип данных Многоразрядное число. Разработать следующие функции: • Equal() – сравнение двух многоразрядных чисел (возвращает 0, если числа равны, 1 – если первое число больше, -1 – если второе число больше); • LongModShort() – возвращает остаток от деления многоразрядного числа на короткое число типа int; • LongDivShort() – возвращает результат целочисленного деления...
C++ Производный класс не видит перегруженную операцию базового класса
Подскажите пожалуйста, почему производный класс, а именно его объект не видит перегруженную операцию, в данном случае это префиксные операции (++,--). Без них программа запускается. В начале базовый класс, за ним производный,а у производного есть свой производный. Вот код: #include <iostream> using namespace std; //////////////////////////////////////////////////////////////// class Counter...
C++ Ошибка при выполнении программы http://www.cyberforum.ru/cpp-beginners/thread839515.html
//set.h #pragma once typedef unsigned short WORD; class Set { private: int minElem; int maxElem;
C++ Дерево поиска Всем добрый полдень:) Помогите пож-та решить вот такую вот задачку: В текстовом файле задан алфавит(на англ(a-z), нужно построить бинарное дерево поиска:)Плиииииз( буду очееееееень благодарна..... Добавлено через 1 час 47 минут ????????????????????????????????? подробнее

Показать сообщение отдельно
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.04.2013, 17:30     Создание бинарного дерева поиска
Могу дать только свою реализацию структуры бинарного дерева поиска. Ввод информации сама сможешь реализовать?
Файл cmap.h
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
#ifndef CMAP_H
#define CMAP_H
 
/*
   Модуль структуры вида "словарь" на языке Си.
   Для использования данного модуля НЕОБХОДИМО в файле определения(cmap.c)
   ОБЯЗАТЕЛЬНО задать функцию, сравнивающую ключи и значение(инициализировать
   указатели keyCompareFunc и valueComapareFunc).
   При этом пользовательская функция должна возвращать отрицательное значение,
   если первый аргумент меньше второго, положительное значение, если первый аргумент
   больше второго и должна возвращать 0 в случае равенства двух аргументов
 */
 
#include <stdio.h>
 
struct Map; // опережающее объявление
 
typedef int TKey;   // тип ключа
typedef const char * TValue; // тип значения
 
typedef int (*keyCompareFuncPointer)(TKey, TKey); // указатель на функцию сравнения ключей
//typedef int (*valueComapareFuncPointer) (TValue, TValue); // // указатель на функцию сравнения значения
typedef void (*outNodeFuncPointer) (struct Map *);
 
struct Map
{
   TKey key;
   TValue value;
};
 
struct Node
{
   struct Map map;
   struct Node *left;  // левое поддерево (для меньших значений)
   struct Node *right; // правое поддерево (для бОльших значений)
};
 
/* cmap_has_key() проверяет имеется ли в словаре ключ key
   в случае отсутствия такового возвращает NULL,
   иначе структуру Map, содержащий искомый ключ */
struct Map * cmap_has_key(struct Node *rootNode, TKey key);
TValue cmap_get_value(TKey key);                 // возвращает значение по ключу
/* cmap_insert() вставляет в словарь новую запись.
   В случае, если ключ key уже имеется в словаре, то просто обновляется его value */
int cmap_insert(struct Node **rootNode, TKey key, TValue value);
int cmap_clear(struct Node ** const rootNode);            // очищает словарь
int cmap_empty(const struct Node * const rootNode);             // проверяет на пустоту словарь
/* удаляет элемент словаря по ключу. Возвращает 0 в случае успеха, или
   CMAP_KEY_NOT_FOUND в случае неудачи */
int cmap_delete(struct Node ** const rootNode, TKey key);
void cmap_out(struct Node *rootNode, outNodeFuncPointer outFunc);
 
enum CMAP_ERROR{
   CMAP_NULL_POINTER = 1, // если передан неверный указатель
   CMAP_KEY_NOT_FOUND,     // указанный ключ не найден
   CMAP_MEMORY_ALLOCATE_ERROR // ошибка выделения памяти
};
 
#endif // CMAP_H
Файл cmap.c
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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
#include "cmap.h"
 
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
int cmpInt(int a, int b)
{
   return a - b;
}
 
static
keyCompareFuncPointer keyCompareFunc = &cmpInt;
 
/*
static
valueComapareFuncPointer valueComapareFunc = &strcmp;
*/
 
// ------------------------------------------------------------
int cmap_insert(struct Node **rootNode, TKey key, TValue value)
{
   /* cmap_insert() вставляет в словарь новую запись.
   В случае, если ключ key уже имеется в словаре, то просто обновляется его value */
   if (!rootNode)
      return CMAP_NULL_POINTER;
 
   if (*rootNode == 0)
   {
      struct Node *newNode = malloc(sizeof (*newNode));
 
      newNode->map.key = key;
      newNode->map.value = value;
      newNode->left = NULL;
      newNode->right = NULL;
      // пустое дерево, новый элемент есть новый корень
      *rootNode = newNode;
   }
   else
   {
      struct Node *curNode = *rootNode; // текущий узел
      int iCmp; // хранит значение функции сравнения ключа текущего узла и ключа вставки
 
      while (1)
      {
         iCmp = keyCompareFunc(curNode->map.key, key);
 
         if (iCmp < 0)
         {
            // ключ вставки меньше ключа текущего узла
            if (curNode->left != NULL)
               curNode = curNode->left;
            else
            {
               struct Node *newNode = malloc(sizeof (*newNode));
 
               if (!newNode)
                  return CMAP_MEMORY_ALLOCATE_ERROR;
 
               newNode->map.key = key;
               newNode->map.value = value;
               newNode->left = NULL;
               newNode->right = NULL;
 
               curNode->left = newNode;
               break;
            }
         }
         else if (iCmp > 0)
         {
            // ключ вставки больше ключа текущего узла
            if (curNode->right != NULL)
               curNode = curNode->right;
            else
            {
               struct Node *newNode = malloc(sizeof (*newNode));
 
               if (!newNode)
                  return CMAP_MEMORY_ALLOCATE_ERROR;
 
               newNode->map.key = key;
               newNode->map.value = value;
               newNode->left = NULL;
               newNode->right = NULL;
 
               curNode->right = newNode;
               break;
            }
         }
         else
         {
            // ключ вставки равен ключу текущего узла. В таком случае просто обновляем значение узла
            curNode->map.value = value;
            break;
         }
      }
   }
 
   return 0;
}
// ------------------------------------------------------------
struct Map * cmap_has_key(struct Node *rootNode, TKey key)
{
   /* cmap_has_key() проверяет имеется ли в словаре ключ key
   в случае отсутствия такового возвращает NULL,
   иначе структуру Map, содержащий искомый ключ */
 
   if (!rootNode) // если словарь пуст, то мы ничего не нашли
      return NULL;
 
   struct Node *curNode = rootNode; // текущий узел
   int iCmp; // хранит результат сравнения ключа текущего узла и искомого
 
 
   while (1)
   {
      iCmp = keyCompareFunc(curNode->map.key, key);
 
      if (iCmp < 0)
      {
         if (curNode->left == NULL)
            return NULL; // ключ не найден
         else
            curNode = curNode->left;
      }
      else if (iCmp > 0)
      {
         if (curNode->right == NULL)
            return NULL; // ключ не найден
         else
            curNode = curNode->right;
      }
      else
      {
         // если мы здесь, то ключ найден
         return &curNode->map;
      }
   }
}
// ------------------------------------------------------------
int cmap_delete(struct Node ** const rootNode, TKey key)
{
   if (!(*rootNode))
      return CMAP_KEY_NOT_FOUND;
 
   struct Node *parentNode = NULL;
   struct Node *curNode = *rootNode;
   int iCmp;
 
   while (1)
   {
      iCmp = keyCompareFunc(curNode->map.key, key);
 
      if (iCmp < 0)
      {
         if (curNode->left == NULL)
            return CMAP_KEY_NOT_FOUND; // ключ не найден
         else
         {
            parentNode = curNode;
            curNode = curNode->left;
         }
      }
      else if (iCmp > 0)
      {
         if (curNode->right == NULL)
            return CMAP_KEY_NOT_FOUND; // ключ не найден
         else
         {
            parentNode = curNode;
            curNode = curNode->right;
         }
      }
      else
      {
         // если мы здесь, то ключ найден. Выходим из цикла
         break;
      }
   } // end while (1)
 
   if (!curNode->left && !curNode->right) // удаляем узел без потомков
   {
      if (!parentNode) // удаляем весь словарь
         *rootNode = NULL;
      else
      {
         if (parentNode->left == curNode)
            parentNode->left = NULL;
         else
            parentNode->right = NULL;
      }
 
      free(curNode);
   }
   else if (curNode->left && curNode->right) // если удаляемый узел содежит два потомка
   {
      struct Node *leaf = curNode->left; // для нахождения листка
      struct Node *leafParent = curNode;
      // цикл поиска листка у дерева удаляемого элемента
      while (leaf->left || leaf->right) // пока у текущего узла есть дети
      {
         leafParent = leaf;
 
         if (leaf->left)
            leaf = leaf->left;
         else
            leaf = leaf->right;
      }
 
      if (leafParent->left == leaf) // удаляем информацию о листочке у его родителя
         leafParent->left = NULL;
      else
         leafParent->right = NULL;
 
      leaf->left = curNode->left;
      leaf->right = curNode->right;
 
      if (parentNode) // если удаляем не самый корень дерева
      {
         // заменяем удаляемый элемент листком из его поддерева
         if (parentNode->left == curNode)
            parentNode->left = leaf;
         else
            parentNode->right = leaf;
      }
      else // усли удаляем самый корень дерева
      {
         *rootNode = leaf;
      }
 
      free(curNode);
   }
   else // если у удаляемого узла только один потомок
   {
      if (parentNode)
      {
         if (parentNode->left == curNode)
            parentNode->left = curNode->left ? curNode->left : curNode->right;
         else
            parentNode->right = curNode->left ? curNode->left : curNode->right;
      }
      else // удаляем самый корень дерева
      {
         *rootNode = parentNode->left = curNode->left ? curNode->left : curNode->right;
      }
 
      free(curNode);
   }
 
   return 0;
}
// ------------------------------------------------------------
int cmap_empty(const struct Node * const rootNode)
{
   return rootNode == NULL;
}
// ------------------------------------------------------------
int cmap_clear(struct Node ** const rootNode)
{
   /* Функция очистки диски. УЖАСНЕЙШАЯ реализация, как будет время надо переделать!!!!!
    */
 
   if (!rootNode)
      return CMAP_NULL_POINTER;
   while (!cmap_empty(*rootNode))
      cmap_delete(rootNode, (**rootNode).map.key);
 
   return 0;
}
// -----------------------------------------------------------
void cmap_out(struct Node *rootNode, outNodeFuncPointer outFunc)
{
   // ужаснейщая реализация. Необходимо задействовать структуру типа стэка
   // вместо рекурсии
   if (!rootNode)
      return;
 
   if (rootNode->left)
      cmap_out(rootNode->left, outFunc);
 
   outFunc(&rootNode->map);
   printf("\n");
 
   if (rootNode->right)
      cmap_out(rootNode->right, outFunc);
}
// -----------------------------------------------------------
 
Текущее время: 18:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru