Обработка динамических структур данных

Задуманный вами объект это лошадь?

Ответ:1;

Где «объект» это содержание листьевой вершины. Если пользователь ответил «да», то программа выводит сообщение

Я угадала!

Если же пользователь ответит нет, то программа последовательно предлагает ввести ему название задуманного им объекта и текст вопроса, ответ на который позволит ей отличить этот объект от объекта, который был «вычислен» программой в процессе движения по дереву. Предложение ввести определение нового объекта выглядит так:

Ответ:0

Какой объект вы задумали?

Ответ: зебра

Предложение ввести вопрос выглядит таким образом:

Введите вопрос отличающий «лошадь» от «зебра»

Ответ: Животное полосатое?

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

Играем еще?

Если пользователь отвечает «нет» программа завершает свою работу.

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

Имеет две ноги?

38

Животное полосатое?

Кенгуру

38

Лошадь

Зебра

38

Любой ответ пользователя (кроме ответов на вопросы об определении нового объекта и на предложение ввести вопрос соответствующий новому объекту) отличающийся от «0» и «1» является ошибкой. Каждая обнаруженная ошибка вызывает появление на экране диагностического сообщения:

Ошибка ввода! Ведите «0» или «1»

После этого повторяется последний вопрос.

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

Работа программы основана на использовании двоичного дерева, структура которого изображена на рисунке 9.

Рисунок 9

Из рисунка 9 видно, что каждый элемент дерева хранит указатели на левое и правое поддеревья, а также информационное поле, содержащее слово.

              При необходимости программа выполняет следующие операции над двоичным деревом:

1) заполнение двоичного дерева из текстового файла;

2) вывод на экран вершин дерева, которые соответствуют выбору пользователя.

3) добавление вершин содержащих новое слово и вопрос.

4) запись дерева в файл.

Подробные алгоритмы перечисленных процедур рассмотрены в пункте 3.3. Алгоритмизация задачи

3.3 Алгоритмизация задачи

Разрабатываемая  программа обеспечивает преобразование данных, сохраненных изначально в текстовом файле, в вид дерева двоичного поиска. Программа совершает движение по дереву, согласно инструкциям пользователя. Если программа находит загаданный пользователем объект, то выводит соответствующее сообщение. Если же объект отсутствует в дереве, то программа начинает обучаться: предлагает пользователю ввести задуманный объект и вопрос, отличающий его от «отгаданного» программой. Программа проверяет вводимые значения, и в случае некорректного ввода данных выводит на экран сообщение об ошибке. Стоит учесть, что если последовательность вопросов, которые задает программа, не создают логическою цепочку, то это не является ошибкой, так как «обучение» программы (т.е. заполнение дерева вопросами и ответами)  возложено на пользователя.

3.3.1 Основной алгоритм

Шаг 1 Очистить экран: cls

Шаг 2 Вывести на экран информационное сообщение:

writeln(‘Загадайте животное. «Да»-1, «Нет»-0’)

Шаг 3 Связать файловую переменную f с текстовым файлом data.txt: assign(f,’data.txt’)

Шаг 4 Если файл data.txt есть то

Шаг 4.1.1 Открыть файл для чтения: reset(f)

Шаг 4.1.2 Сформировать дерево root из файла: root:=LoadFromFile             

Шаг 4.1.3 Закрыть файл: close(f)

Шаг 4.2 Иначе сформировать новое дерево: InitRoot

Шаг 5 Дереву р присвоить сформированное дерево root: p:=root

Шаг 6 Пока левое поддерево не равно nil (p^.left<>nil) делать

Шаг 6.1 Вывести на экран вопрос: write(p^.s+’?’)

Шаг 6.2 Ввести с клавиатуры ответа на вопрос: readln(x)

Шаг 6.3 Если ответ введен не корректно(x<>1 and x<>0) то

Шаг 6.3.1 Вывести сообщение об ошибке: writeln(‘Ошибка. Введите 0 или 1’)

Шаг 6.3.2 Иначе если ответ положительный (х=1) то

Шаг 6.3.2.1 Дереву р присвоить левое поддерево: p:=p^.left

Шаг 6.3.2.2 Иначе дереву р присвоить правое поддерево: p:=p^.right

Шаг 7 Вывести на экран «угаданного» программой объекта: write(‘Это ’+p^.s+’?’)

Шаг 8 Ввести с клавиатуры ответ на вопрос: readln(x)

Шаг 9.1 Если ответ введен не корректно(x<>1 and x<>0) то

Шаг 9.1.1 Вывести сообщение об ошибке: writeln(‘Ошибка. Введите 0 или 1’)

Шаг 9.1.2 Иначе если ответ положительный (х=1) то

Шаг 9.1.2.1 Вывести на экран сообщение: writeln(‘Я угадала’)

Шаг 9.1.2.2 Иначе вывести на экран сообщения: writeln(‘Я проиграла. Что это за

животное?’)

Шаг 9.1.2.3 Ввести с клавиатуры загаданный объект: readln(s)

Шаг 9.1.2.4 Вывести сообщение на экран: writeln(‘Введите вопрос, отличающий это

животное от ’+p^.s+’: ’)

Шаг 9.1.2.5 Ввести с клавиатуры новый вопрос: readln(q)

Шаг 9.1.2.6 Выделить память для динамических переменных и присвоить указателям р1 и

р2 адреса выделенных областей: New(р1) New(p2)

Шаг 9.1.2.7 Заполнить поля вершины дерева р1:

Шаг 9.1.2.7.1 Левый потомок пуст: р1^.left:=Nil

Шаг 9.1.2.7.2 Правый потомок пуст: р1^.right:=Nil

Шаг 9.1.2.7.3 Запись строку s в вершину дерева: р1^.s:=s

Шаг 9.1.2.8 Заполнить поля вершины дерева р2:

Шаг 9.1.2.8.1 Левый потомок пуст: р1^.left:=Nil

Шаг 9.1.2.8.2 Правый потомок пуст: р1^.right:=Nil

Шаг 9.1.2.8.3 Запись строку s в вершину дерева: р1^.s:=s

Шаг 9.1.2.8 Добавить новые вершины в дерево р:

Шаг 9.1.2.8.1 Левый потомок: р^.left:=р1

Шаг 9.1.2.8.2 Правый потомок: р^.right:=р2

Шаг 9.1.2.8.3 Запись вопрос q в вершину дерева: р^.s:=q

Шаг 10 Открыть файл для перезаписи: rewrite(f)

Шаг 11 Записать дерево в файл: SaveToFile(root)

Шаг 12 Закрыть файл: close(f)

3.3.2 Создание корня дерева

Алгоритм реализован в виде процедуры InitRoot.

Шаг 1 Выделить память для динамической переменной и присвоить указателю root адрес выделенной области: New(root)

Шаг 2 Заполнить поля корня дерева:

Шаг 2.1 Левый потомок пуст: root^.left:=Nil

Шаг 2.2 Правый потомок пуст: root^.right:=Nil

Шаг 2.3 Слово: root^.s:=’Собака’

Шаг 5 Конец алгоритма

3.3.3 Формирование дерева из текстового файла

Алгоритм реализован в виде процедуры LoadFromFile.

Шаг 1 Считать строки из файла: readln(f,s).

Шаг 2 Если файл пуст (s=’’) то

Шаг 2.1 Присвоить функции LoadFromFile значение nil: Result:=nil

Шаг 2.2 Выход из процедуры: Exit

Шаг 3 Выделить память для динамической переменной и присвоить указателю p адрес выделенной области: New(p)

Шаг 4 Заполнить поля вершины дерева:

Шаг 4.1 Добавление строки в левое поддерево: p^.left:= LoadFromFile

Шаг 4.2 Добавление строки в правое поддерево: p^.right:= LoadFromFile

Шаг 4.3 Запись строки s в вершину дерева: p^.s:=s

Щаг 5 Присвоить функции LoadFromFile значение p: Result:=p

Шаг 6 Конец алгоритма

3.3.4 Запись дерева в текстовый файл

Алгоритм реализован в виде процедуры SaveToFile.

Шаг 1 Если дерево пусто (p=nil) то

Шаг 1.1 Запись в файл пустой строки: writeln(f,’’)

Шаг 1.2 Выход из процедуры: Exit

Шаг 2 Запись в файл дерева

Шаг 2.1 Запись в файл вершины дерева: writeln(f,p^.s)

Шаг 2.2 Запись в файл левого поддерева: SaveToFile(p^.left)

Шаг 2.3 Запись в файл правого поддерева: SaveToFile(p^.right)

Шаг 2 Конец алгоритма

Блок-схемы алгоритмов представлены в Приложении Б. Пояснение идентификаторов, используемых в программе, приведено в таблице Д.1
3.4. Тестирование программы

Тестирование программы осуществлялось в нормальных условиях, на «нулевых» примерах и в экстремальных условиях (на которые программа не рассчитана). Все результаты представлены в таблице 1.

Таблица 1.1 Результаты тестирования программы в нормальных условиях

Таблица 1.2 Результаты тестирования программы на «нулевых» примерах