AlgStr / Библиотека / ЛЕКЦИИ / PZ01 / Структуры данных и их классификация
Cтруктуры данных предназначены для удобного хранения и доступа к информации. Они предоставляют удобный интерфейс для типичных операций с хранимыми объектами, скрывая детали реализации от пользователя. Это позволяет добиться большей модульности программы. Абстрактные структуры данных иногда делят на две части: интерфейс, набор операций над объектами, который называют АТД(абстрактный тип данных) и реализацию
Языки программирования высокого уровня(Паскаль, Си..) предоставляют удобный интерфейс для чисел: операции +, *, = .. и т.п, но при этом скрывают саму реализацию этих операций, машинные команды.
Структуры данных разделяют на два типа: статические и динамические.
- Статические структуры относятся к разряду непримитивных структур, которые, фактически, представляют собой структурированное множество примитивных, базовых, структур. Например, вектор может быть представлен упорядоченным множеством чисел. Поскольку по определению статические структуры отличаются отсутствием изменчивости, память для них выделяется один раз и ее объем остается неизменным до уничтожения структуры.
- Динамические структуры по определению характеризуются отсутствием физической смежности элементов структуры в памяти непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки.
- информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой — вектором, массивом, другой динамической структурой и т.п.;
- поле связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры;
- размер структуры ограничивается только доступным объемом машинной памяти;
- при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей;
- большая гибкость структуры.
- на поля связок расходуется дополнительная память;
- доступ к элементам связной структуры может быть менее эффективным по времени.
Cписки
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в списке, список нулевой длины называется пустым списком. Линейные связные списки являются простейшими динамическими структурами данных. На рис. 1 приведена структура односвязного списка. На нем поле INF — информационное поле, данные, NEXT — указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка. 
Рис. 1: Представление односвязного списка в памяти Двусвязный список характеризуется наличием пары указателей в каждом элементе: на предыдущий элемент и на следующий: 
Рис. 2: Представление двусвязного списка в памяти Очевидный плюс тут в том, что от данного элемента структуры мы можем пойти в обе стороны. Таким образом упрощаются многие операции. Однако на указатели тратится дополнительная память. Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются, как показано на рис.3. При работе с такими списками несколько упрощаются некоторые процедуры. Однако, при просмотре такого списка следует принять некоторых мер предосторожности, чтобы не попасть в бесконечный цикл. 
Рис. 3: Структура кольцевого двухсвязного списка
Таблицы
Под таблицей следует понимать динамическую структуру данных, которая в каждый момент выполнения вычислений состоит из конечного набора элементов (записей); записи таблицы могут подразделяться на несколько полей; при этом количество и тип полей является одинаковыми для всех записей таблицы. Первое поле всех записей таблицы обычно называют ключом, поля записи без ключевого поля образуют тело записи. Например, задавая соответствие между идентификаторами переменных (именами) и их адресами в памяти ЭВМ, мы можем построить простейшую таблицу вида Пример таблицы для организации доступа по имени в которой каждая строка-запись состоит из двух полей: поля ключа (имени) и поля тела записи (адреса). Основные операции, выполняемые над таблицами, определяются следующим набором операций:
- поиск записи (по одному или нескольким ключам);
- вставки записи (с контролем возможных повторений);
- удаления записи.
Операции вставки и удаления записей служат для формирования требуемого набора записей; операция поиска записи по ключу обеспечивает доступ по имени (ключу) к записям таблицы.
Деревья
Элемент такой структуры (узел дерева) определяется как запись, содержащая несколько полей ссылок. Например: Type Point = ^ Item; Item = Record Data: Integer; Right, Left: Point End; Type Link = ^ TreeVert; TreeVert = Record Data: Real; Key : Integer; Left, Middle, Right : Link End; Количество ссылочных полей узла дерева называется степенью ветвления (арностью) узла. Таким образом, дерево может быть либо вырожденным (Nil), либо составлено из узла дерева, все указатели которого выставлены на деревья. В этом случае узел называют корнем дерева, а деревья, на которые выставлены указатели — поддеревьями. Если поддерево состоит из одного узла, все указатели которого установлены на Nil, его называют листом. Остальные узлы дерева называют промежуточными. Совокупность ссылочных полей может быть оформлена как запись либо как несколько полей записи (как в наших примерах). Часто совокупность ссылочных полей определяется в виде массива ссылок, либо организуется в виде списка ссылок. В этих случаях говорят об упорядоченных деревьях, т.к. поддеревья одного корня оказываются упорядоченными либо индексами массива, либо по порядку доступа. Если все узлы дерева имеют одну и ту же степень ветвления, можно говорить о степени ветвления дерева. Деревья, степень ветвления которых равна двум, называют бинарными. Бинарные деревья — одна из наиболее распространенных ветвящихся структур, применяемых в программировании.
Сети
Сеть — орграф, в котором допускаются и петли, и кратные дуги и который используется как модель системы, процесса и пр. Обычно в сети выделяются некоторые вершины — полюсы сети, играющие роль входов и выходов сети. В теории программирования сеть используется для описания статической топологии моделируемого процесса или системы и имеет вид двудольного орграфа (в общем случае бесконечного) с двумя типами вершин: места и переходы. На основе понятия сети вводятся динамические сетевые структуры, в которых местам приписываются специальные разметки, моделирующие выполнение условий, и с сетью связывается понятие ее функционирования, изменяющего эти разметки (условия) в результате так называемых срабатываний переходов. К таким динамическим сетям относятся сети Петри, их различные варианты, обобщения и частные случаи. 7
Источник
Урок информатики по теме «Структуры данных: деревья, сети, графы, таблицы». 10-й класс 
Назад Вперёд
Назад Вперёд
Тип урока: с применением современных информационных технологий
- Образовательные:
- ввести классификацию структур информационных моделей;
- сформировать понятия «граф», «деревья», «таблицы»;
- ознакомить обучающихся с граф-моделями и табличными моделями систем, сформировать умение строить такие модели, использовать их для решения практических задач.
- развивать умение оценивать свою учебную деятельность и деятельность своего партнера;
- развивать умения выделять главное, сравнивать, анализировать, обобщать.
- стимулировать интерес обучающихся к информационным технологиям;
- пробудить интерес к самостоятельному решению задач.
- Знать:
- понятия «граф», «дерево», «сеть», «таблица»;
- структуры информационных моделей;
- структуру и типы таблиц.
- ориентироваться в граф-моделях;
- строить граф-модели (деревья, сети, таблицы) по вербальному описанию системы;
- строить различные по типу таблицы.
Формируемые умения: самоанализ вопросов теста, слушать, работать по учебнику, по карточкам.
Цели использования ИКТ: проверить теоретические знания с помощью теста, созданного в программе MyTestXPro, объяснить новый материал с использованием презентации MS PowerPoint, закрепить знания с помощью кроссворда, созданного в презентации MS PowerPoint, работа по карточкам в текстовом редакторе MS Word.
Этап урока, на котором использовались ИКТ: актуализация знаний, тестовый контроль, изучение нового материала.
Формы организации работы детей: индивидуальная, групповая, практическая.
Формы организации работы учителя: контроль, объяснение, консультирование.
Технологические особенности: личностно–ориентированная, дифференцированная, объяснительно– иллюстративное обучение, технология учебной дискуссии.
Технические условия
Используемое оборудование: компьютерный класс с установленным ПО (MS Power Point, MS Word, MyTestXPro), проектор, экран.
Разработанные цифровые образовательные ресурсы: подготовка теста в MyTestXPro, презентации нового материала урока, кроссворда.
Литература: И.Г Семакина «Информатика 10 класс», § 14
Технологическая карта урока
Методическая часть
Элемент ИКТ Программа для тестирования MyTestXPro в режиме обучения Презентация MS PowerPoint
Презентация 2 (кроссворд)Презентация MS PowerPoint Презентация1.pps (слайд №19 –31) Текстовый редактор MS Word Как (приемы и методы) используется этот элемент в уроке личностно-ориентированная технология личностно-ориентированная технология объяснительно-иллюстративное обучение, технология учебной дискуссии практическая работа Какие цели преследуются применением конкретно этого элемента на уроке проверить знания изученного материала, выявить пробелы, проанализировать ошибки проверить знания изученного материала, выявить пробелы, проанализировать ошибки – ввести понятия «структура данных», «граф», «сеть», «дерево» «таблица»;
– сформировать навыки построения графов, деревьев, по вербальному описанию системы;
– строить различные по типу таблицы.закрепить навыки и умения работы по созданию информационных моделей: «граф», «сеть», «дерево» «таблица». Каким образом этот элемент усиливает эффективность достижения названных целей индивидуальность работы, получение результата и анализ всех ошибок индивидуальность работы, получение результата и анализ всех ошибок иллюстративно-наглядное объяснение с обращением в форме вопросов к учащимся и комментарием учителя самостоятельная работа учащихся за компьютером Источник