Потопахин Виталий Валерьевич 3 Задачи прикладного характера по информатике 3 миф-2, №2, 2000 8 Потопахин Виталий Валерьевич 8 решение

Вид материала

Решение

Содержание Богоутдинов Дмитрий Гилманович Структуры данных Конец АТД Узел Задание по теории игр

Подобный материал:

• Алексей Валерьевич Антошин. Форма отчет, 169.69kb.
• Платов Антон Валерьевич в поисках святого грааля король Артур и мистерии древних кельтов, 1046.94kb.
• Сейфуллина Виталий Петров, в результате долгого и упорного труда сумевший опередить, 26.72kb.
• Виталий Валентинович Бианки (1894 1959). Аесли говорить о природоведческой книге для, 161.76kb.
• Евгений Валерьевич Куршинский, 18.63kb.
• Максимов Юрий Валерьевич лекции, 1534kb.
• Алексеев Владимир Валерьевич, к ист, 113.16kb.
• Илья Валерьевич Мельников, 2470.8kb.
• У системы начинается ломка виталий найшуль: «Если лозунгом революции 1991 года была, 63.74kb.
• Агафонов Максим Валерьевич реферат Гребенюк Светлана Александровна реферат, 12.91kb.

^

Богоутдинов Дмитрий Гилманович

Структуры данных

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

Рассмотрим наиболее простой пример. Пусть вам необходимо вспомнить формулу Герона. Как легче всего это сделать? Поиск можно производить в разных источниках в словарях, справочниках по математике и т.п. Но в некоторых книгах материал может располагаться так, что необходимая формула будет находиться в середине параграфа «Площадь треугольника» и тогда нужно знать для чего используется искомая формула, а в других книгах эта формула может оказаться в указателе формул. Таким образом, мы видим, что при определенных условиях поиск сильно упрощается. С появлением ЭВМ такие задачи приобрели новое звучание. Программисты поняли, что эффективность поиска зависит не только от алгоритма, то есть от порядка действий, но и от того, как представлены исходные данные. Способы представления данных, а точнее – структуры данных, мы и будем рассматривать.

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

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

• Набор операций для манипуляции над специфическими типами абстрактных объектов.
  
• Структура памяти, в которой хранятся абстрактные объекты.
  
• Реализация каждой из операций в терминах структуры памяти.
  

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

Для описания абстрактных типов данных используют формат, который включает заголовок с именем, описание типа данных и список операций. Для каждой операции определяются входные значения, предусловия, применяемые к данным до того, как операция может быть выполнена, и процесс, который выполняется операцией. После выполнения операции определяются выходные значения и постусловия, указывающие на любые изменения данных. Большинство АТД имеют инициализирующую операцию, которая присваивает данным начальные значения. В некоторых языках программирования такой инициализатор называется конструктором. Данный термин мы и будем использовать.

Приведем общую схему АТД-формата.

АТД имя_АТД

Данные

Описание структуры данных.

Операции

Конструктор

Начальные значения: Данные, используемые для инициализации

объекта.

Процесс: Инициализация объекта.

Операция₁

Вход: Данные от пользователя.

Предусловия: Необходимое состояние системы перед

выполнением операции.

Процесс: Действия, выполняемые с данными.

Выход: Данные, возвращаемые клиенту.

Постусловия: Состояние системы после выполнения операций.

Операция₂ . . . . . . . . . . . . . . . . . . . .

Операция_n . . . . . . . . . . . . . . . . . . . .

Конец АТД

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

Рассмотрим пример.

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

АТД Dice (игральные кости)

Данные (выпишем всё, что нам известно из условий задачи)

Число костей в каждом бросании – целое, большее либо равное 1. Целое значение, содержащее сумму очков всех костей в последнем бросании. Если N – число бросаемых костей, то число очков находится в диапазоне от N до 6N. Список, содержащий число очков каждой кости в бросании. Значение любого элемента списка находится в диапазоне от 1 до 6.

Операции

Конструктор

Начальные значения: Число бросаемых костей.

Процесс: Инициализировать данные, определяющие число

костей в каждом бросании

Toss (описываем бросок игральных костей)

Вход: Нет.

Предусловия: Нет.

Процесс: Бросание костей и вычисление общей суммы

очков.

Выход: Нет.

Постусловия: Общая сумма содержит сумму очков в бросании, а

в списке находятся очки каждой кости.

DieTotal

Вход: Нет.

Предусловия: Нет.

Процесс: Находит значение элемента, определяемого как

сумма очков в последнем бросании.

Выход: Возвращает сумму очков в последнем бросании.

Постусловия: Нет.

DisplayToss

Вход: Нет.

Предусловия: Нет.

Процесс: Печатает список очков каждой кости в последнем

бросании.

Выход: Нет.

Постусловия: Нет.

Конец АТД Dice.

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

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

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

Связанные списки

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

П
ри обработке списков связанные списки имеют два преимущества перед массивами. Во-первых, изменение порядка элементов выполняется очень просто и быстро, а во-вторых, связанные списки динамичны – они могут сжиматься и расти, в течение их «жизни». При работе со связанными списками можно не следить за переполнением отведенного участка памяти, что очень важно при работе с массивами.

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

А
налогичный процесс описывает операцию УдалСлед, которая удаляет узел, следующий за текущим.

Структура узлов с операциями вставки и удаления описывает абстрактный тип данных. Для каждого узла эти операции относятся непосредственно к его последующему узлу. Опишем ADT Узел.

АТД Узел

Данные

Поле данных используется для хранения данных. Кроме инициализации, значение не используется ни в какой другой операции. Поле Next является указателем на следующий узел. Если Next – это Nil, то следующего узла нет.

Операции.

Конструктор

Начальные значения: Значение данных и указатель на следующий узел.

Процесс: Инициализация двух полей.

СледУзел

Вход: Нет

Предусловия: Нет

Процесс: Выборка значений поля Next

Выход: Возвращение значения поля Next.

Постусловия: Нет.

ВставПосле

Вход: Указатель на новый узел.

Предусловия: Нет.

Процесс: Переустановка значения Next для указания на

новый узел и установка значения Next в новом

узле для ссылки на узел, следующий за текущим.

Выход: Нет.

Постусловия: Узел теперь указывает на новый узел.

УдалСлед

Вход: Нет.

Предусловия: Нет.

Процесс: Отсоединение текущего узла и присваивание

значения Next для ссылки на узел, который

следует за следующим узлом.

Выход: Указатель на удаленный узел.

Постусловия: Узел имеет новое значение Next.

^ Конец АТД Узел

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

Р
ассмотрим на конкретном примере ранее описанные преимущества связанных списков.

Пример.

Пусть нам дан лексикографически упорядоченный массив, в котором хранятся сведения о студентах курса, посещающих дополнительные курсы по информатике (назовем этот массив St) (рис. 1). Если студенты Петров и Градов перестают посещать курсы, а студент Сидоров добавляется, то нам хотелось бы получить новый список, посещающих курсы (рис. 2). По сравнению с массивом, связанный список требует дополнительной памяти, но позволяет легко вносить нужные нам изменения (хотя сам список мы будем пока представлять также в виде массива).

Рис.1. Массив St.