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

Считывание из файла (Организация таблиц идентификаторов) - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Тип bool http://www.cyberforum.ru/cpp-beginners/thread121934.html
Может кто-нибудь поможет на простейшем но понятном примере объяснить как работает тип bool. Знаю что это тип может быть ложный или истинный но что-то никак его работу не могу понять.... для чего он нужен...
C++ Функция которая меняет переданные ей переменные? Как ее сделать http://www.cyberforum.ru/cpp-beginners/thread121933.html
описание двумерного массива C++
Здравствуйте программисты! есть тип typedef char tBoard; Неполучается сделать чтото типо того typedef tBoard * pBoard; оно то делается только tBoard B = { {...},{...},...}; pBoard pb = &B
C++ Как описывать методы в классах?
Отдельно как функцию, или обязательно внутри объявления класса??
C++ Умножить каждый элемент столбца матрицы A(n, m) на первый элемент данного столбца. http://www.cyberforum.ru/cpp-beginners/thread121918.html
Помогите, пожалуйста, написать программу: Умножить каждый элемент столбца матрицы A(n, m) на первый элемент данного столбца. Она кажется не сложной, однако, я не очень хорошо в этом разбираюсь Допоможіть, будь-ласка, скласти програму: Помножити кожний елемент стовпця матриці А(n,m) на перший елемент даного стовця. Вона здаеться не тяжкою, однак, я не дуже розуміюся на цьому.
C++ Текстовое окно или ТекстБокс Ребят, есть проблема. Надо напиасть текст программы с правой стороны экрана. В Борланде есть для этого функция window из библиотеки conio.h. А я работаю не в борланде , а в Dev-C++ и эта библиотека не содержит данной функции. Вопрос какои функцией писать текст на правой стороне экрана? Как создать текстовое окно или тест бокс? Табуляцию, и писать в Борланде не предлагать! Заранее спасибо! подробнее

Показать сообщение отдельно
Artemka89
0 / 0 / 0
Регистрация: 26.04.2010
Сообщений: 4
26.04.2010, 03:08     Считывание из файла (Организация таблиц идентификаторов)
Всем доброй ночи, помогите пожалуйста доделать задачу:

Требуется написать программу, которая получает на выходе набор идентификаторов, организует таблицы идентификаторов с помощью заданных методов (простой список и рехэширование с использованием псевдослучайных чисел), позволяет осуществить многократный поиск произвольного идентификатора в таблицах и сравнить эффективность методов организации таблиц. Список идентификаторов считать заданным в виде текстового файла. Длина идентификаторов ограничена 32 символами.


Проблема состоит в том что не получается считывать идентификаторы из текстового файла.(((

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
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
#include <iostream>
#include <exception>
#include <fstream>
 
#define MAX_VALUE 255
 
//tree------------------------------------------------------
class Node
{
private:
char *m_value;
 
Node *m_right;
Node *m_left;
 
public:
 
Node( char *value )
{ 
m_value = new char[strlen(value) + 1];
strcpy(m_value, value);
 
m_left = NULL;
m_right = NULL;
};
~Node()
{
if( m_right != NULL )
{
delete m_right;
}
if( m_left != NULL )
{
delete m_left;
}
if(m_value != NULL)
{
delete m_value;
}
}
 
 
//создать правого потомка
Node* CreateRightChild(char *value)
{
if(m_right != NULL)
{
delete m_right;
}
 
m_right = new Node(value);
 
return m_right;
}
 
//создать левого потомка
Node* CreateLeftChild(char *value)
{
if(m_left != NULL)
{
delete m_left;
}
 
m_left = new Node(value);
 
return m_left;
}
 
//получить правого потомка
Node* GetRightChild()
{
return m_right;
}
//получить левого потомка
Node* GetLeftChild()
{
return m_left;
}
//Получить значение у вершины
char* GetValue()
{
return m_value;
}
 
//Добавляет лексему в дерево.
//возвращает указатель на созданную вершину и количество сравнений при добавлении
std::pair <Node*, int> AddLexem(char *lexem)
{
Node *current_node = this;
//тут хранится количество сравнений
int compares_count = 0;
 
while(1)
{
//а вот и сравнение (; регистрируем
int result = strcmp(lexem, current_node->GetValue());
compares_count++;
 
if(result > 0)
{
//если полученная строка меньше текущей, пытаемся добавить в левое поддерево
if(current_node->GetLeftChild() == NULL)
{
//если пустое - создаём вершину
current_node = current_node->CreateLeftChild(lexem);
break;
}
//если нет -- делаем левую вершину текущей и возвращаемся в начало цикла
current_node = current_node->GetLeftChild();
continue;
}
else if (result < 0)
{
//если строка больше текущей, пытаемся добавить в правое поддерево
if(current_node->GetRightChild() == NULL)
{
current_node = current_node->CreateRightChild(lexem);
break;
}
current_node = current_node->GetRightChild();
continue;
}
else
{
break;
}
}
//возвращаем пару значений - созданную вершину и количество сравнений
 
return std::make_pair<Node*, int>( current_node, compares_count );
}
 
std::pair <Node*, int> FindLexem( char *lexem )
{
//бинарный поиск по дереву
Node* current_node = this;
//количество сравнений
int compares_count = 0;
 
do
{ 
//сравнение
int result = strcmp( lexem, current_node->m_value );
compares_count++;
//если полученная строка меньше - ищем в левом поддереве
if( result > 0 )
{
current_node = current_node->m_left;
}
else if( result < 0 )
{
//иначе -- в правом
current_node = current_node->m_right;
}
else
{
// если нашли, возвращаем найденную вершину и количество сравнений
return std::make_pair<Node*, int>( current_node, compares_count );
}
 
} while ( current_node != NULL );
 
return std::make_pair<Node*, int>( current_node, compares_count );
}
};
 
//two-way linked list
class Item
{
private:
 
char* m_value;
 
Item* m_previous;
Item* m_next;
 
public:
Item( char *value )
{ 
m_value = new char[strlen(value) + 1];
strcpy(m_value, value);
m_previous = NULL;
m_next = NULL;
};
~Item()
{
m_previous->m_next = m_next;
m_next->m_previous = m_previous;
delete m_value;
}
 
//добавить элемент ПЕРЕД текущим
Item* InsertBefore( char *value )
{
Item* temp = m_previous;
m_previous = new Item( value );
m_previous->m_previous = temp;
m_previous->m_next = this;
return m_previous;
}
 
//Добавить элемент ПОСЛЕ текущего
Item* InsertAfter( char *value )
{ 
Item* temp = m_next;
m_next = new Item( value );
m_next->m_previous = this;
m_next->m_next = temp;
return m_next;
}
 
//Добавляем лексему. Список -- отсортированный
std::pair<Item*, int> AddLexem( char *lexem)
{
Item* current_item = this;
int compares_count = 0;
 
//если строка больше текущей и есть следующий элемент
while( current_item->m_next != NULL && strcmp( current_item->m_value, lexem ) < 0 )
//делаем следующий элемент текущим
{
current_item = current_item->m_next;
compares_count++;
}
//если следующего элемента нет, добавляем лексему после текущего
if(current_item->m_next == NULL)
{
return std::make_pair<Item*, int> ( current_item->InsertAfter( lexem ), compares_count );
}
else
{
//если же есть, значит текущее значение >= лексеме, добавляем её перед текущим элементом
return std::make_pair<Item*, int> ( current_item->InsertBefore( lexem ), compares_count );
}
}
 
//поиск лексемы в списке (последовательный)
std::pair<Item*, int> FindLexem ( char *lexem )
{
Item* current_item = this;
int compares_count = 1;
//если не нашли лексему в текущем элементе списка - переходим к следующему 
while( current_item != NULL && strcmp( current_item->m_value, lexem ) )
{
compares_count++;
current_item = current_item->m_next;
}
//количество сравнений и найденный элемент -- возвращаем.
return std::make_pair<Item*, int> ( current_item, compares_count );
}
};
 
///hash function -- среднее арифметическое символов лексемы
int GetHashIndex( char *lexem )
{
double result = 0;
 
int length = strlen( lexem ); 
 
for (int i = 0; i < length; i++ )
{
result += static_cast<int>( lexem[i] );
}
result /= length;
 
return static_cast<int>(result);
}
 
 
int main(int argc, char **argv)
{
if(argc != 2 )
{
std::cout << "No file specified" << std::endl;
return 1;
}
 
//сколько всего лексем мы обработали
int tokens_count = 0;
//сколько раз искали лексемы
int search_tries = 0;
 
//Tree hash - массив, дополняемый деревьями
Node* tree_hash_array[MAX_VALUE]; 
//сколько всего раз проводилось сравнение при добавлении в дерево
int tree_add_compares = 0;
// ----- при поиске в дереве
int tree_search_compares = 0;
 
//List hash -- массив, дополняемый списками
Item* list_hash_array[MAX_VALUE];
//сколько раз сравнивалось при добавлении в список
int list_add_compares = 0;
//----- при поиске в списке
int list_search_compares = 0;
 
 
for( int i = 0; i < MAX_VALUE; i++ )
{
tree_hash_array[i] = NULL;
list_hash_array[i] = NULL;
}
 
std::ifstream input_file;
 
input_file.open(argv[1]);
 
char token[80];
 
while( !input_file.eof() )
{
//читаем по слову
input_file >> token;
 
tokens_count++;
 
//пытаемся получить для слова индекс через хэш
int index = GetHashIndex( token );
 
//занято
if( tree_hash_array[index] != NULL )
{
//добавляем в дерево, считаем сравнения
tree_add_compares += tree_hash_array[index]->AddLexem( token ).second;
}
else
{
//свободно?! создаём новое дерево
tree_hash_array[index] = new Node( token ); 
}
 
//по аналогии, только со списком
if( list_hash_array[index] != NULL )
{
list_add_compares += list_hash_array[index]->AddLexem( token ).second;
}
else
{
list_hash_array[index] = new Item( token );
}
}
 
while( 1 )
{
//просим ввести лексему для поиска
char answer[80];
std::cout << "Enter token to search or \":q\" to exit >> ";
std::cin >> answer;
if( !strcmp( ":q", answer ) )
{
return 0;
} 
 
//считаем индекс через хэш
int index = GetHashIndex( answer );
 
//пусто, нет таких. -- ничего не выводим, заново спрашиваем лексему
if( tree_hash_array[index] == NULL )
{
continue;
}
 
//есть дерево -- ищем в этом дереве
std::pair<Node*, int> tree_seach_results = tree_hash_array[index]->FindLexem( answer );
 
if( tree_seach_results.first == NULL )
{
continue;
}
 
search_tries++;
//считаем сравнения
tree_search_compares += tree_seach_results.second;
//и в списке тоже ищем, считаем сравнения
list_search_compares += list_hash_array[index]->FindLexem( answer ).second;
//выводим общее количество сравнений при добавлении и среднее при поиске
//для списка
std::cout << "List add: " << list_add_compares << "\tsearch: " << list_search_compares/search_tries << std::endl;
//для дерева
std::cout << "Tree add: " << tree_add_compares << "\tsearch: " << tree_search_compares/search_tries << std::endl;
 
}
 
return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 09:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru