Поиск нужного слова в словаре, в котором слова расположены в лексикографическом порядке - 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
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д