9. Ввод, сортировка и двоичный поиск в массиве структур

Алиас: словарь.

Цель работы

При выполнении лабораторной работы изучить следующие вопросы:

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

Задание

Англо-русский словарь построен в виде массива структур Dictionary. Структура содержит английское слово и соответствующее ему русское слово. Для хранения записей словаря необходимо использовать динамический массив.

Разработать программу, которая:

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

предупреждение

Для реализации поиска по словарю запрещено использовать функции из стандартной библиотеки string.h.

Программа должна обеспечивать диалог с помощью меню.

Программа должна иметь два режима запуска: демонстрационный и интерактивный:

В демонстрационном режиме необходимо продемонстрировать в консоли все доступные функции работы со словарем с комментариями к отображаемым данным. В данном режиме не должно быть никакого пользовательского ввода. Исполнитель задания самостоятельно определяет какие параметры передаются в качестве аргументов в функции работы со словарем. Конечный вид данного режима определяет исполнитель задания.
В интерактивном режиме обеспечить интерактивное взаимодействие с пользователем для управления словарем.

Режим запуска определять по переданным аргументам командной строки. По умолчанию программу запускать в демонстрационном режиме.

Начальное число слов в словаре равно 10.

Для исключения проблем, связанных с вводом кириллицы, вводите русские слова латинскими буквами, например:

kot - cat;
sobaka - dog.

Весь функционал, обеспечивающий работу с Dictionary, необходимо выделить в самостоятельный модуль, состоящий из заголовочного файла mdict.h и файла реализации mdict.c или mdict.cpp в зависимости от используемого языка программирования. Структуру Dictionary необходимо объявить в mdict.h.

к сведению

Для того, чтобы понять как создать модуль для Dictionary, рекомендуется обратить внимание на CMakeLists.txt, mprinter.c и mprinter.h из лабораторной работы №8.

Указания по выполнению работы

Шаги разработки программы

I. Определение состава и способа представления исходных данных, результатов и промежуточных данных

Обратите внимание, что размер словаря неограничен. Вам необходимо использовать динамический массив для хранения записей словаря. Также на длину слова не устанавливается ограничений. Поэтому для хранения записей словаря в оперативной памяти (ОП) можно использовать структуру Dictionary:

struct Dictionary {
    char *engl;    // слово по-английски
    char *rus;     // слово по-русски
};

Словарь хранится в текстовом файле. Элементы массива структур Dictionary будем записывать в файл последовательно, начиная с нулевого. При этом поля структуры записываются в виде отдельных строк, т.е. каждое слово должно заканчиваться символом \0.

II. Разработка алгоритма решения задачи

При программировании этой задачи уделим дополнительное внимание разбиению на функции и спецификации их интерфейсов. Например, логично оформить в виде функции каждую операцию со словарем (формирование, поиск, добавление и удаление элемента), поскольку они представляют собой законченные действия.

Интерфейс пользователя организуем в виде простейшего меню, которое будет выводиться на экран после каждого действия. В стандарты С/C++ не входят функции позиционирования курсора на экране, управления цветом и работы с экраном в графическом режиме, поскольку они зависят от операционной системы. Поэтому меню представим в виде пронумерованного перечня возможных действий пользователя, красиво размещенного на экране, а выбор действия будем выполнять путем ввода его номера в перечне. В функции menu() желательно предусмотреть реакцию на ввод пользователем непредусмотренных алгоритмом данных, например, слова вместо номера (так называемая "защита от дурака").

Будем исходить из того, что все функции должны быть независимы, чтобы изменения в одной функции не могли влиять на поведение другой. Для этого всё, что функциям необходимо получать извне, будем передавать им через параметры.

Прежде всего определим интерфейс нашей программы. В соответствии с заданием, кажется логичным предоставить пользователю следующие возможности:

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

Каждый пункт этого меню, кроме последнего, оформим в виде отдельной функции. Определим прототипы предложенных функций. Меню. Эта функция (в качестве подсказки) выводит пронумерованный перечень возможных действий пользователя и выполняет ввод номера выбранного действия. Это число она должна вернуть в вызвавшую функцию:

int menu();

Добавление слов в словарь. Чтобы добавить элемент Dictionary в словарь, надо задать пару слов и определить место, куда вставлять элемент, чтобы массив оставался отсортированным. Поиск места вставки и ввод добавляемого элемента выполним внутри функции, а в функцию передадим указатель на начало словаря и его размерность. Назовем ее add_w.

Для С:

void add_w(struct Dictionary **dict, int *n);

Для C++:

void add_w(Dictionary **dict, int *n);

По аналогии определите прототипы остальных функций самостоятельно.

III. Кодирование и тестовые примеры

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

Сначала начнем с определения того, в каком режиме запускать программу.

Выбор режима запуска

Для того, чтобы запускать программу в интерактивном режиме, мы будем передавать в качестве аргумента символом i. Тогда запуск программы в интерактивном режиме будет выглядеть в оболочке Bash:

lab9 i

Подпрограмму, отвечающую за интерактивный режим, выделим в функцию interactive(), а для демонстрационного режима - demo(). Тогда прототип программы, определяющий режим запуска, будет выглядеть так, как показано ниже.

Для программ на C:

#include <string.h>
#include <stdbool.h>

int interactive();

int demo();

int main(int argc, char *argv[]) {
    bool isInteractive = false;    // по умолчанию демо-режим.

    // Если i передается в качестве аргумента, то программу
    // необходимо запустить в интерактивном режиме
    if ((argc == 2) && strcmp(argv[1], "i") == 0) {
        isInteractive = true;
    }

    if (isInteractive) {
        return interactive();

    } else {
        return demo();
    }
}

Для программ на C++:

#include <iostream>
#include <string.h>

int interactive();

int demo();

int main(int argc, char *argv[]) {
    bool isInteractive = false;    // по умолчанию демо-режим.

    // Если i передается в качестве аргумента, то программу
    // необходимо запустить в интерактивном режиме
    if ((argc == 2) && strcmp(argv[1], "i") == 0) {
        isInteractive = true;
    }

    if (isInteractive) {
        return interactive();

    } else {
        return demo();
    }
}

Реализация интерактивного режима

При реализации подпрограммы, отвечающую за интерактивный режим, первой добавляемой функцией должна быть функция menu().

При использовании меню функция interactive() сильно упрощается: она периодически вызывает меню, анализирует запрошенный код операции и вызывает функцию, которая выполняет эту операцию. При выборе операции с номером 7 выполнение программы завершается.

Для программ на C:

int menu();

void add_w(struct Dictionary **dict, int *n);

void print_dict(struct Dictionary *dict, int n);

int interactive() {
    struct Dictionary* dict;        // динамический массив структур для
                                    // хранения словаря в оперативной памяти
    int num_w = 0;                  // фактическое число записей в словаре

    while (true) {
        switch (menu()) {
            case 1:
                add_w(&dict, &num_w);
                break;
            case 2:
            case 3:
            case 4:
                break;
            case 5:
                print_dict(dict, num_w);
                break;
            case 6:
                break;
            case 7:
                return 0;
            default:
                printf("Надо вводить число от 1 до 7");
                break;
        }
    }
}

Для программ на C++:

int menu();

void add_w(Dictionary **dict, int *n);

void print_dict(Dictionary *dict, int n);

int interactive() {
    Dictionary* dict;               // динамический массив структур для
                                    // хранения словаря в оперативной памяти
    int num_w = 0;                  // фактическое число записей в словаре

    while (true) {
        switch (menu()) {
            case 1:
                add_w(&dict, &num_w);
                break;
            case 2:
            case 3:
            case 4:
                break;
            case 5:
                print_dict(dict, num_w);
                break;
            case 6:
                break;
            case 7:
                return 0;
            default:
                std::cout << " Надо вводить число от 1 до 7" << std::endl;
                break;
        }
    }
}

После отладки menu(), запрограммируйте и отладьте функции add_w() и print_dict().

add_w() добавляет записи в массив структур, а print_dict() распечатывает массив из оперативной памяти.

Проверка задания

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

Методический материал

Требования к отчету
Полезная информация:
1. Структуры C++
Контрольные вопросы:
1. Для потока на С
2. Для потока на С++

Цель работы​

Задание​

Указания по выполнению работы​

Шаги разработки программы​

I. Определение состава и способа представления исходных данных, результатов и промежуточных данных​

II. Разработка алгоритма решения задачи​

III. Кодирование и тестовые примеры​

Выбор режима запуска​

Реализация интерактивного режима​

Проверка задания​

Методический материал​