Поиск нужного слова в словаре, в котором слова расположены в лексикографическом порядке - C (СИ)
Формулировка задачи:
[C]
Напишите задачу поиска нужного слова в словаре, в котором слова расположены в лексикографическом порядке(бинарный поиск).
решить надо с помощью рекурсии=((
помогите пожалуйста..а то я сама ваще не знаю как((
Решение задачи: «Поиск нужного слова в словаре, в котором слова расположены в лексикографическом порядке»
textual
Листинг программы
#include <stdio.h>
#include <string.h>
int binsearch(const char **v, int i, int j, char *s)
{
int mid, cond;
if (i > j)
return -1;
mid = (j + i) / 2;
if ((cond = strcmp(s, v[mid])) < 0)
return binsearch(v, i, mid - 1, s);
else if (cond > 0)
return binsearch(v, mid + 1, j, s);
else
return mid;
}
int main()
{
const char *words[4] = {
"internet",
"protect",
"seashepherd",
"the"
};
int i;
if ((i = binsearch(words, 0, 3, "seashepherd")) != -1)
printf("the index of element"
"you are looking for is %d\n", i);
else
printf("not found!\n");
return 0;
}
Объяснение кода листинга программы
- Включаем необходимые заголовочные файлы
- Определяем функцию binsearch, которая выполняет бинарный поиск в массиве слов
- Если массив пуст, то возвращаем -1
- Находим средний индекс массива
- Сравниваем искомое слово с словом в среднем элементе массива
- Если искомое слово меньше, то рекурсивно вызываем функцию binsearch для левой половины массива
- Если искомое слово больше, то рекурсивно вызываем функцию binsearch для правой половины массива
- Если слова равны, то возвращаем индекс среднего элемента массива
- В функции main создаем массив слов
- Используем функцию binsearch для поиска слова
seashepherdв массиве слов - Если слово найдено, то выводим его индекс
- Если слово не найдено, то выводим сообщение
not found