Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.97/31: Рейтинг темы: голосов - 31, средняя оценка - 4.97
HIMen
4265 / 1432 / 101
Регистрация: 12.04.2009
Сообщений: 2,346
1

Бинарный поиск в текстовом файле

29.05.2009, 15:51. Просмотров 5798. Ответов 10
Метки нет (Все метки)

Есть текстовый файл с 10000 словами в алфавитном порядке.
Функция проверяет, есть ли введенное слово в этом файле.
Помогите реализовать бинарный поиск по первой букве
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool slovo_true(char *slovo, FILE *stream) 
{
   char read_str[20], *result;
   fseek(stream,0,SEEK_SET);
   while (!feof(stream))  
   {
      result=fgets(read_str,20, stream);
      if (!strcmp(read_str, slovo)) 
      {
         return true;
      }
   }    
   return false;
};
Как менять позицию fseek(stream,0,SEEK_SET) на определенную строчку?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2009, 15:51
Ответы с готовыми решениями:

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

Бинарный поиск в бинарном файле
Здравствуйте, помогите решить проблему. Написал программу для нахождения числа...

Поиск в текстовом файле
Есть тестовый файл такого типа: Имя: Плотник Трудоемкость: 32 Время: 22...

Поиск в текстовом файле
Добрый вечер еще разок. Никак не могу сообразить, как реализовать следующий...

Поиск в текстовом файле
Здравствуйте, нужно осуществить поиск нужной строки в файле .txt. Как быть?

10
CheshireCat
Эксперт С++
2913 / 1262 / 114
Регистрация: 27.05.2008
Сообщений: 3,464
29.05.2009, 15:57 2
На определенную строчку - никак.
0
Haster
инженер-системотехник
111 / 110 / 5
Регистрация: 10.03.2009
Сообщений: 533
29.05.2009, 16:01 3
Можно предложить, например, такой алгоритм:
считываешь первую букву - если не подходит то читаешь до символа перевод строки..
Затем опять проверяешь и т.д.
(будет работать в случае, если каждое слово на новой строке)
0
MrAndrey_ka
79 / 79 / 20
Регистрация: 13.05.2009
Сообщений: 537
Записей в блоге: 1
29.05.2009, 16:02 4
что имеется ввиду
бинарный поиск по первой букве
, по коду буквы или как?
0
Gravity
569 / 563 / 64
Регистрация: 29.01.2009
Сообщений: 1,274
29.05.2009, 16:03 5
Если заранее известно кол-во слов в файле, то нужно читать из файла в массив и уже работать с массивом.
0
HIMen
4265 / 1432 / 101
Регистрация: 12.04.2009
Сообщений: 2,346
29.05.2009, 16:08  [ТС] 6
Цитата Сообщение от MrAndrey_ka Посмотреть сообщение
что имеется ввиду , по коду буквы или как?
да.

Количество слов точно не известно, т.к. файл пополняется словами
0
Gravity
569 / 563 / 64
Регистрация: 29.01.2009
Сообщений: 1,274
29.05.2009, 16:15 7
Тогда так:
- создаем массив через динамическую память и заводим счетчик считанных слов
- читаем слова из файла в массив
- если счетчик слов превышает размер массива, выделяем еще памяти под массив
И так пока не прочитаешь весь файл, затем делай бинарный поиск по массиву.
1
Evg
Эксперт CАвтор FAQ
19339 / 7193 / 537
Регистрация: 30.03.2009
Сообщений: 20,132
Записей в блоге: 30
29.05.2009, 16:20 8
Можно тупо считать из файла все 10 тыщ слов (займут в памяти немного места).

Либо сделать первый проход и запомнить 10 тыщ элементов с позициями начала слова. Потом в массиве из 10 тыщ позиций методом бинарного поиска проверять слово. Идиотизм такого метода почти очевиден

Либо вот так. Делаемм SEEK на середину файла (середину в байтах), далее читаем до энтера - таким образом нашли начало слова, которое приблизительно в середине файла находится. И так даелее, делаем SEEK в терминах абсолютного байтового смещения, ищем начало слова и проверяем. Правда возникнет геморой ближе к концу. Типа если у нас диапазон сузился до 10 байт, при этом в этом диапазоне слово 3 байта и 7 байт. По такому алгоритму мы доначала слова не доберёмся, а потому тут что-то думать надо

Идей, как тут применить бинарный поиск больше нет
1
HIMen
4265 / 1432 / 101
Регистрация: 12.04.2009
Сообщений: 2,346
29.05.2009, 16:22  [ТС] 9
Цитата Сообщение от Gravity Посмотреть сообщение
Тогда так:
- создаем массив через динамическую память и заводим счетчик считанных слов
- читаем слова из файла в массив
- если счетчик слов превышает размер массива, выделяем еще памяти под массив
И так пока не прочитаешь весь файл, затем делай бинарный поиск по массиву.
На поиск обычным способом уходит 0.2-0.3 секунды.
Это будет быстрее?
0
Evg
Эксперт CАвтор FAQ
19339 / 7193 / 537
Регистрация: 30.03.2009
Сообщений: 20,132
Записей в блоге: 30
29.05.2009, 16:25 10
Цитата Сообщение от HIMen Посмотреть сообщение
На поиск обычным способом уходит 0.2-0.3 секунды.
Это будет быстрее?
В твоём варианте на каждое слово читается файл. В предложенном варианте файл читается только один раз идальше вся информация лежит в памяти. Для однократного исполнения разницы по времени скорее всего не будет. Для многократного исполнения твой вариант медленнее
0
salvafion
10 / 10 / 1
Регистрация: 16.06.2009
Сообщений: 194
01.04.2010, 17:29 11
держи а начале файла количество слоа в файле а потом как в школе делим колличство пополам и ставим указатели. и смотрим в какую сторону смещаться
0
01.04.2010, 17:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.04.2010, 17:29

Поиск в текстовом файле
Всем привет! Нужно на С++ написать программу,в поиске похожего не нашёл. Вот...

Не работает поиск в текстовом файле
Я хочу чтобы данные которые я ввожу , записывались в файл с пробелами и...

Поиск слова в текстовом файле
Программа ищет заданное слово в файле с текстом, в результате нужно вывести на...


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

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

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