Обрабатываемые объекты: цепочки символов, списки, деревья

Сегодня на уроке мы вспомним:

· что такое абстрактная структура данных;

· что такое цепочка символов, списки, деревья;

· чем отличается стек от очереди;

· рассмотрим несколько заданий, которые могут быть на ОГЭ по информатике.

Чтобы представить информацию в такой форме, в которой её было бы удобно обрабатывать компьютеру, каждый объект представляют как некоторую абстрактную структуру данных.

Абстрактная структура данных описывает свойства и характеристики объекта, взаимосвязи его элементов и операции, которые могут быть произведены над классами таких объектов. Такие структуры данных предназначены для удобного хранения и доступа к информации. Они предоставляют удобный интерфейс для типичных операций с хранимыми объектами, скрывая детали реализации от пользователя.

К базовым абстрактным структурам данных, которыми пользуются в информатике, относятся:

· целые и вещественные числа;

· символы;

· логические значения.

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

Можно создать более сложные структуры из базовых типов. Есть много разных способов объединения простых типов в составные, которые по-разному указывают правила построения структуры данных:

· каким образом эта структура организована, а именно – какие более элементарные объекты в ней содержатся и какие операции можно над ними выполнять – это относится к логической организации структуры;

· и список операций, которые можно выполнять в целом над структурой.

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

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

С помощью основных методов конструирования составных структур можно создать статические объекты: таблицы, векторы, строки и последовательности. Для таких объектов обычно в большинстве языков программирования есть соответствующие типы данных, такие как одномерные и двумерные массивы, строки, файлы, записи и множества. Статические структуры отличаются отсутствием изменчивости, память для них выделяется один раз, и её объем остаётся неизменным до уничтожения структуры.

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

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

Цепочка символов (или строка) – это произвольная последовательность символов, записанных один за другим. В цепочки символов могут входить любые допустимые символы. Важен состав и количество символов в цепочке. Один и тот же символ может произвольное число раз входить в цепочку. Но цепочки «о» и «оо», а также «оа» и «ао» являются разными цепочками символов. Цепочки символов α = β (или совпадают), если у них один и тот же состав символов, одно и то же их количество и расположение символов в цепочке так же одинаковое.

Длина цепочки – это количество символов, из которых она состоит.

Выделяют следующие операции над цепочками символов:

Конкатенация – это объединение или сложение цепочек, то есть дописывание второй цепочки в конец первой.

Обращение цепочки – это запись символов цепочки в обратном порядке.

И повторение цепочки некоторое количество раз – это конкатенация цепочки самой с собой n раз.

Существует пустая цепочка символов – это цепочка, которая не содержит ни одного символа.

Список – это упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции добавления элементов в произвольное место списка и удаления любого элемента. Список задаётся указателем на начало списка. Обычно элементы списка называют узлами. Список, отражающий отношения соседства между элементами, называется линейным. Длина списка – это количество элементов, которые содержатся в списке. Список нулевой длины называется пустым списком.

Для каждого узла, кроме первого, существует предыдущий узел; для каждого узла, кроме последнего, есть следующий узел. Чтобы обойти все элементы списка, нужно двигаться последовательно от текущего элемента к следующему начиная с первого. Так как доступ к произвольному элементу невозможен и отсутствует возможность движения в противоположную сторону – от конца списка к началу, то обработка такого односвязного списка не всегда удобна.

Есть несколько видов списков, для которых существуют определённые дополнительные правила работы с начальным и конечным элементами.

Кольцевой список, или кольцо – это список, у которого имеется дополнительная связь между последним и первым элементами (получается первый узел является следующим для последнего).

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

Стек – это вид списка, в котором все добавления и удаления узлов (и чаще всего всякий доступ) осуществляются только на одном его конце – вершине стека. Иногда стек называют списком LIFO (Last In – First Out), что значит последним вошёл, первым вышел).

Очередь – это вид списка, в котором все добавления элементов производятся на одном его конце, а удаление узлов (и обычно всякий доступ) – на другом. Эти узлы называются началом и концом очереди. Иногда очередь называют списком FIFO (First In – First Out – первым вошёл, первым вышел).

Основными операциями над стеком и очередью являются включение, исключение, определение размера, очистка, неразрушающее чтение.

Дерево – это множество элементов, среди которых выделен один узел, называемый корнем, а остальные элементы разбиты на группы так, что они также образуют деревья. При этом:

· корни поддеревьев являются потомками корня всего дерева;

· множества элементов поддеревьев не пересекаются друг с другом;

· листьями называются узлы, не имеющие ни одного потомка.

Каждый узел дерева является корнем некоторого поддерева, которое содержится в дереве, или листом. Таким образом получается иерархическая структура узлов: все элементы связаны между собой отношениями вида «предок» – «потомок».

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

Типовыми операциями над элементами дерева являются:

· добавление элемента в дерево,

· удаление элемента из дерева,

· обход дерева,

· поиск элемента в дереве.

Рассмотрим несколько заданий, которые могут быть на ОГЭ по информатике.

Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она чётная, то в середину цепочки символов добавляется символ А, а если нечётная, то в конец цепочки добавляется символ Я. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А – на Б, Б – на В и так далее, а Я – на А). Получившаяся таким образом цепочка является результатом работы алгоритма.

Дана цепочка символов АРБА. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (то есть применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм).

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

Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.

Сначала вычислим длину исходной цепочки символов. Она равно 4. Длина чётная, значит, необходимо добавить символ А в середину цепочки – АРАБА. Теперь заменим каждую букву на следующей за ней в русском алфавите – БСБВБ.

Применим алгоритм ещё раз, но уже к получившемуся результату.

Длина цепочки символов БСБВБ равна 5. Так как длина нечётная, то в конец цепочки добавляем символ Я – БСБВБЯ. 

Теперь заменим каждую букву на следующей за ней в русском алфавите.

В ответе записываем следующую цепочку символов: ВТВГВА.

В таблице приведены протяжённости дорог между населёнными пунктами (отсутствие числа означает, что между соответствующими пунктами нет прямого сообщения). Определите длину кратчайшего пути из пункта Г в пункт Д (при условии, что можно передвигаться только по имеющимся дорогам).

Построим дерево решения задачи. В качестве корня дерева примем стартовый пункт маршрута – Г. Из него идёт только один путь – в пункт Б. Его длина равна 1. Добавим в дерево узел и подпишем его. Соединим оба узла линией (ребром) и припишем расстояние от Г до Б.

К узлу Б добавим поддерево, содержащее узлы всех доступных из Б населённых пунктов – А, В и Ж. Соединим эти узлы с Б. Посчитаем суммарное расстояние от пункта Г до пунктов А, В и Ж и припишем каждому ребру эти расстояния.

Для каждого из полученных листов дерева рассмотрим возможные маршруты.

Из пункта А идут два пути – к пункту Ж и пункту Д. Соединим эти узлы. Посчитаем расстояние от пункта А до этих пунктов и припишем каждому ребру получившиеся значения.

Из пункта В идёт только один путь – к пункту Д. Добавляем узел Д в дерево, соединяем узлы и считаем расстояние от пункта В к Д.

Из пункта Ж тоже идёт только один путь – к пункту А. Добавляем этот узел в дерево, соединяем узлы и считаем расстояние от пункта Ж к А.

В результате видим, что самый короткий путь от пункта Г до Д равен 14 – это путь ГБВД.

У исполнителя Калькулятор в системе команд имеются команды:

1. прибавить 2

2. умножить на 6

Выполняя первую команду, исполнитель прибавляет 2 к имеющемуся числу. В результате второй команды исполнитель умножает на 6 имеющееся у него число. Таким образом, последовательность команд 1121, применённая исполнителем к числу 5, приведёт к результату 56:

прибавить 2;

прибавить 2;

умножить на 6;

прибавить 2

(5 + 2 = 7; 7 + 2 = 9; 9 х 6 = 54; 54 + 2 = 56).

Требуется записать последовательность номеров команд, чтобы получить результат 72 из числа 1 не более чем за 5 шагов.

Итак, чтобы выполнить задание, построим дерево поиска решений для обратной задачи – получения числа один из числа 72 с помощью двух обратных команд: разделить на 6 и вычесть 2.

Корнем дерева будем считать узел с исходным числом 72. Из корневого узла будет исходить 2 ребра, так как к нему можно применить одну из двух возможных операций. Так как не все числа делятся на 6, то некоторые узлы дерева будут иметь только одно ребро – для операции вычитания.

Узлы, полученные вычитанием, расположим в левой ветви; узлы, полученные делением, – в правой. Каждому ребру припишем соответствующую операцию.

Поскольку по условию можно использовать для преобразований не более 5 шагов, то после 6 уровня прекратим добавление узлов к дереву.

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

Выпишем команды, приведшие к решению обратной задачи:

делить на 6;

вычесть 2;

вычесть 2;

вычесть 2;

делить на 6.

Для решения прямой задачи следует выписать исходные команды в противоположном порядке:

умножить на 6;

прибавить 2;

прибавить 2;

прибавить 2;

умножить на 6;

В ответе записываем номера этих команд: 21112.

В конце урока попробуйте ответить на следующие вопросы:

Что такое абстрактная структура данных?

Как называется вид списка, в котором все добавления и удаления узлов (и чаще всего, всякий доступ) осуществляются только на одном его конце – вершине стека?

Что такое длина цепочки символов?

Можно ли в списке удалить элемент?

Внимательно посмотрев урок, вам не составит труда ответить на вопросы.