Что такое статические и полустатические структуры данных
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета
Поиск
Введите ваш запрос для начала поиска.
Об авторах
Курс разработан на кафедре Компьютерных технологий и систем Кубанского государственного аграрного унивеситета. Авторами являются заведующий кафедрой, доктор технических наук, профессор Лойко Валерий Иванович и доцент кафедры, кандидат физико-математических наук Лаптев Сергей Владимирович.
Основные цели сайта
Сайт предназанчен для максимально эффективного и быстрого доступа ко всем материалам курса «Алгоритмы и структуры данных», имеющимся на кафедре компьютерных технологий и систем КубГАУ. Основной задачей его создания является повышения эффективности освоения дисциплины студентами и всеми желающими.
Полустатические структуры данных
К полустатическим структурам данных относят стеки, деки и очереди. Прежде, чем начать подробное изучение данных структур, рассмотрим одну более общую структуру, называемую списком.
Списки
Количество элементов списка может меняться в процессе выполнения программы. Различают 2 вида списков:
В несвязных списках связь между элементами данных выражена неявно. В связных списках в элемент данных заносится указатель связи с последующим или предыдущим элементом списка.
Стеки
В силу указанной дисциплины обслуживания, в стеке доступна единственая его позиция, которая называется вершиной стека- это позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх прежней вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).
Графически стек можно представить следующим образом:
Операции, производимые над стеками:
1. Занесение элемента в стек.
2. Выборка элемента из стека.
3. Определение пустоты стека.
4. Прочтение элемента без его выборки из стека.
5. Определение переполнения стека (для полустатических структур)
Алгоритмы основных операций со стеком
Заметим, что при выборки элемента из стека для обеспечения корректности выполняемой операции необходимо проверять стек на пустоту, поэтому абсолютно правильный алгоритм для функции Pop ( S ) будет следующим
if i = 0 then “пусто”
Алгоритм проверки стека на пустоту можно записать несколько по другому, если использовать логический тип данных
if i = 0 then empty = true
Затем можно изменить алгоритм функции Pop ( S )
Понятно, что maxS здесь максимальное число элементов массива.
Очередь
Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание.
На рисунке ниже приведена очередь, содержащая четыре элемента — А, В, С и D. Элемент А расположен в начале очереди, а элемент D — в ее конце. Элементы могут удаляться только из начала очереди, то есть первый помещаемый в очередь элемент удаляется первым. По этой причине очередь часто называют списком, организованным по принципу «первый размещенный первым удаляется» в противоположность принципу стековой организации — «последний размещенный первым удаляется».
Реальная очередь создается в памяти ЭВМ в виде одномерного массива с конечным числом элементов, при этом необходимо указать тип элементов очереди, а также необходима переменная в работе с очередью.
Физически такая очередь занимает сплошную область памяти и элементы следуют друг за другом, как в последовательном списке.
Дек можно рассматривать как два стека, соединенных нижними границами.
Лекция 11. Структуры данных и их классификация. Основные статические и полустатические структуры данных
ЛЕКЦИЯ 11. СТРУКТУРЫ ДАННЫХ И ИХ КЛАССИФИКАЦИЯ. ОСНОВНЫЕ СТАТИЧЕСКИЕ И ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.
СТРУКТУРЫ ДАННЫХ И ИХ КЛАССИФИКАЦИЯ
Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов (битов), а их значениями являются соответствующие двоичные числа.
Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество элементов данных и множество связей между ними.
ФИЗИЧЕСКОЙ структурой данных называется способ физического представления данных в памяти машины. Он называется еще структурой хранения, внутренней структурой или структурой памяти.
ЛОГИЧЕСКОЙ структурой данных называется описание данных без учёта их представления устройствами-носителями информации.
Конкретное логическое и физическое представление данных зависит от задачи, в которой они используются, так как любой класс абстрактных объектов может иметь несколько возможных представлений и выбор наилучшего из них зависит от того, каким образом эти объекты используются. В связи с этим в современном программировании имеет место общепринятая классификация структур данных, направления которой соответствуют различным типичным задачам. Дадим общую классификацию структур данных по нескольким признакам.
1. В зависимости от характера взаимного расположения элементов в памяти структуры данных можно разделить на структуры со СМЕЖНЫМ (или последовательным) распределением элементов в памяти и структуры со СВЯЗНЫМ распределением элементов в памяти.
2. По признаку изменчивости количества элементов и связей между ними различают структуры СТАТИЧЕСКИЕ (векторы, массивы, записи) ПОЛУСТАТИЧЕСКИЕ (стеки, очереди, строки) и ДИНАМИЧЕСКИЕ (списки, деревья, графы).
Над любыми структурами данных могут выполняться четыре общие операции: СОЗДАНИЕ, УНИЧТОЖЕНИЕ, ДОСТУП, ОБНОВЛЕНИЕ.
Операция СОЗДАНИЯ заключается в общем случае в выделении памяти для структуры данных. Память может выделяться как на этапе компиляции, так и на этапе выполнения программы.
Операция УНИЧТОЖЕНИЯ структур данных противоположна по своему действию операции создания; она помогает эффективно использовать память.
Наличие вышеуказанных четырёх операции обязательно для всех структур данных. Помимо этих общих операций для каждой структуры данных могут быть определены операции специфические, работающие только с данной структурой. Некоторые специфические операции будут рассмотрены при изучении конкретных типов структур данных.
ОСНОВНЫЕ СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Векторы
Логически вектор (одномерный массив) представляет собой структуру данных с фиксированным числом элементов одного и того же типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.
Рассмотрим физическое представление векторов в памяти машины. Как правило в языках программирования векторы являются структурами со смежным размещением. Элементы вектора размещаются в ячейках памяти, расположенных подряд. Под элемент вектора выделяется количество байт памяти, определяемое типом элемента этого вектора. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом. Размер памяти для хранения вектора определяется произведением размера слота на число элементов.
В языках программирования вектор представляется одномерным массивом с синтаксисом описания вида (PASCAL):
где n-номер первого элемента, k-номер последнего элемента. Представление в памяти вектора будет такое, как показано на рисунке.
 |  |
Логически массив представляет собой структуру данных, которая характеризуется фиксированным числом элементов одного типа, каждый из которых имеет уникальный набор значений индексов. Количество индексов у каждого элемента массива определяет его размерность. Обращение к элементу массива осуществляется по имени массива и значениям индексов для данного элемента.
Существует и другой способ размещения в памяти многомерных структур – с помощью векторов Айлиффа, который состоит в следующем. Для массива любой мерности формируется набор дескрипторов: основного и несколько уровней вспомогательных дескрипторов, называемых векторами Айлиффа. Каждый вектор Айлиффа определённого уровня содержит указатель на первые элементы векторов Айлиффа следующего, более низкого уровня, а векторы Айлиффа самого нижнего уровня содержат указатели групп элементов отображаемого массива. Основной дескриптор массива хранит указатель вектора Айлиффа первого уровня. При такой организации к произвольному элементу В(j1,j2. jn) многомерного массива можно обратиться пройдя по цепочке от основного дескриптора через соответствующие компоненты векторов Айлиффа (см. рис).
 |
На рисунке приведена физическая структура двухмерного массива В[0..2,0..2], представленная по методу Айлиффа. Из этого рисунка видно, что метод Айлиффа, увеличивая скорость доступа к элементам массива, приводит в то же время к увеличению суммарного объёма памяти, требуемого для представления массива. В этом заключается основной недостаток представления массивов с помощью векторов Айлиффа.
Физически запись может быть размещена в памяти двумя способами. В первом случае, подобно вектору, она представляет собой последовательность полей, размещённых смежно, последовательно одно за другим и занимающих непрерывную область памяти. При такой организации для выполнения операции доступа к полю записи достаточно иметь указатель на начало записи, и смещение поля относительно начала (указатель на начало записи хранится при этом в дескрипторе самой записи, а значения смещений сохраняются при этом в дескрипторе, описывающем соответствующий тип данных). Это дает экономию памяти, но лишнюю трату времени на вычисление адресов полей записи. При другом способе в дескрипторе записи, хранятся, наряду с указателем на начало записи, указатели на значения полей записи (аналогично организации массивов с помощью векторов Айлиффа). При такой организации имеет место быстрое обращение к элементам, но очень неэкономичный расход памяти для хранения.
ОСНОВНЫЕ ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Особенности полустатических структур
Полустатические структуры данных характеризуются следующими признаками:
1. Они имеют переменное число элементов;
2. Изменение длины структуры происходит, как правило, в определённых пределах, не превышая какого-то максимального числа элементов;
3. Логически полустатические структуры представляют собой последовательность данных, связанных отношениями линейного списка.
Рассмотрим основные типы полустатических структур – их логическое и физическое представление.
Стеки
Логически стек представляет собой последовательность элементов с переменной длиной; включение и исключение элементов из последовательности происходит при этом только с одной стороны, называемой вершиной стека. Другие названия стека – магазин и очередь LIFO (last in first out). Основные операции над стеком это:
— определение текущего числа элементов в стеке;
Для наглядности рассмотрим небольшой пример, демонстрирующий принцип включения элементов в стек и исключения элементов из стека. На рисунке изображены состояния стека:
 |  |  |  |
б) после последовательного включения в него элементов A, B, C;
в) после исключения из него двух элементов;
г) после включения в него элемента D.
Простейшая наглядная интерпретация такой структуры как стек – стопка книг.
При ВКЛЮЧЕНИИ элемента в стек на место, определяемое указателем стека, производится запись элемента, а затем указатель стека модифицируется. Модификация указателя состоит в прибавлении к нему или в вычитании из него размера слота (в зависимости от того, в сторону возрастания или убывания адресов растёт стек).
Операция ИСКЛЮЧЕНИЯ элемента состоит в модификации указателя стека (в направлении, обратном модификации при включении) и последующем чтении значения, на которое указывает указатель стека. После чтения слот, в котором размещался исключённый элемент, считается свободным.
ОПРЕДЕЛЕНИЕ РАЗМЕРА стека сводится к вычислению разности указателей: указателя стека и адреса начала области памяти.
Следующий пример поясняет реализацию операций создания, включения, исключения и определения размера стека на языке С.
int n=10; //Максимальное число элементов в стеке
int* pmem; //Указатель на область памяти, занимаемой стеком
int* pstack; //Указатель вершины стека
pmem=new int[n]; // Выделяем память под стек максимальным размером n
pstack=pmem; // Присваиваем начальное значение указателю стека
*pstack=1; pstack=pstack+1; // Помещаем в стек число 1
*pstack=2; pstack=pstack+1; // Помещаем в стек число 2
pstack=pstack-1; i=*pstack; // Читаем из стека число (в данном случае 2)
m=pstack-pmem; // Определяем текущий размер стека
Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вызовов функций с параметрами и локальными переменными. В микропроцессорах семейства Intel, как и в большинстве современных процессорных архитектур, реализована аппаратная поддержка стека.
 | | | |
 |  | |
б) после последовательного включения в очередь элементов A, B, C;
в) после исключения из очереди двух элементов;
г) после включения в очередь элемента D.
Физически очередь представляется в памяти машины аналогично стеку, т. е. в виде вектора, размер которого определяет максимальный размер очереди. Дескриптор очереди при этом в дополнение к обычным для дескриптора вектора параметрам должен содержать два указателя: на начало очереди (на первый элемент в очереди) и на ее конец (первый свободный элемент в очереди). При ВКЛЮЧЕНИИ элемента в очередь элемент записывается по адресу, определяемому указателем на конец, после чего этот указатель модифицируется (увеличивается на размер слота). При ИСКЛЮЧЕНИИ элемента из очереди читается элемент, адресуемый указателем на начало, после чего этот указатель также модифицируется (уменьшается на размер слота).
В исходном состоянии указатели на начало и на конец указывают на начало области памяти, выделенной под очередь. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди. Для кольцевой очереди ситуация несколько сложнее: если в процессе работы с кольцевой очередью число операций включения превышает число операций исключения, то может возникнуть момент, когда указатель конца «догонит» указатель начала. Это ситуация заполненной очереди, но если в этот момент указатели сравняются, эта ситуация будет неотличима от ситуации пустой очереди. Для различения этих двух ситуаций к кольцевой очереди предъявляется требование, чтобы между указателем конца и указателем начала оставался «зазор» из свободных элементов. Когда этот «зазор» сокращается до одного элемента, очередь считается заполненной и дальнейшие попытки записи в нее блокируются. Очистка очереди сводится к записи одного и того же (не обязательно начального) значения в оба указателя. Определение размера состоит в вычислении разности указателей с учетом кольцевой природы очереди.
Следующий пример поясняет простейшую реализацию операций создания, включения, исключения и определения размера очереди на языке С.
int n=10; //Максимальное число элементов в очереди
int* pmem; //Указатель на область памяти, занимаемой очередью
int* pout; //Указатель начала очереди
int* pin; //Указатель на конец очереди
pmem=new int[n]; // Выделяем память под очередь размером n
pout=pmem; pin=pmem; // Присваиваем начальные значения указателям очереди
*pin=1; pin=pin+1; // Помещаем в очередь число 1
*pin=2; pin=pin+1; // Помещаем в очередь число 2
i=*pout; pout=pout+1;// Читаем из очереди число (в данном случае 1)
m=pin-pout; // Определяем текущий размер очереди
Строкой называется линейная упорядоченная последовательность символов, принадлежащих некоторому множеству (алфавиту). Основным свойство строк является их переменная длина. Основными операциями над строками являются:
— определение длины строки;
— конкатенация (сцепление) строк;
— поиск вхождения символа в строку.
Физическое представление строк в памяти и особенности выполнения операций над ними зависит от того, насколько изменчивыми являются строки в каждой конкретной задаче.
Векторное представление строк
Представление строки в виде вектора постоянной длины является самым простым способом. В этом случае в памяти отводится фиксированное количество байт, в которые записываются символы строки (как в одномерный массив). Если строка меньше отводимого под нее вектора, то лишние места заполняются пробелами, а если строка выходит за пределы вектора, то лишние символы должны быть отброшены (на рисунке показан пример размещения в памяти строки “ABC”):
Представление строк вектором переменной длины с признаком конца
 |
Представление строк вектором переменной длины со счётчиком
 |  |
Представление строк вектором с управляемой длиной
 |
Очевидно, что программная реализация операций со строками зависит от конкретного способа представления строк в памяти.
ЗАДАНИЕ К ЛЕКЦИИ 11
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета
Поиск
Введите ваш запрос для начала поиска.
Об авторах
Курс разработан на кафедре Компьютерных технологий и систем Кубанского государственного аграрного унивеситета. Авторами являются заведующий кафедрой, доктор технических наук, профессор Лойко Валерий Иванович и доцент кафедры, кандидат физико-математических наук Лаптев Сергей Владимирович.
Основные цели сайта
Сайт предназанчен для максимально эффективного и быстрого доступа ко всем материалам курса «Алгоритмы и структуры данных», имеющимся на кафедре компьютерных технологий и систем КубГАУ. Основной задачей его создания является повышения эффективности освоения дисциплины студентами и всеми желающими.
Статические и полустатические структуры данных
Записи
Запись представляет из себя структуру данных последовательного типа, где элементы структуры расположены один за другим как в логическом, так и в физическом представлении. Запись предполагает множество элементов разного типа. Элементы данных в записи часто называют полями записи.
Логическая структура записи может быть представлена как в графическом виде, так и в табличном.
Элемент записи может включать в себя записи. В этом случае возникает сложная иерархическая структура данных.
Пример:
Ниже приведены два логических представления структуры этой записи.
Получена четырехуровневая иерархическая структура данных. Информация содержится в листьях, остальные узлы служат для указания пути к листьям.
1-ый уровень Студент = запись
2-ой уровень Имя = запись
3-ий уровень Фамилия
3-ий уровень Отчество
2-ой уровень Анкетные данные = запись
3-ий уровень Место рождения
3-ий уровень Год рождения
3-ий уровень Родители = запись
2-ой уровень Факультет
2-ой уровень Группа
2-ой уровень Оценки = запись
3-ий уровень Английский
3-ий уровень Физика
Эта структура называется вложенной записью.
Операции над записями:
1. Прочтение содержимого поля записи.
2. Занесение информации в поле записи.
3. Все операции, которые разрешаются над полем записи, соответствующего типа.
Таблицы
При задании таблицы указывается количество содержащихся в ней записей.
Table: Array [1..19] of St;
Операции с таблицами:
1. Поиск записи по заданному ключу.
2. Занесение новой записи в таблицу.
Полустатические структуры данных
К полустатическим структурам данных относят стеки, деки и очереди. Прежде, чем начать подробное изучение данных структур, рассмотрим одну более общую структуру, называемую списком.
Списки
Количество элементов списка может меняться в процессе выполнения программы. Различают 2 вида списков:
В несвязных списках связь между элементами данных выражена неявно. В связных списках в элемент данных заносится указатель связи с последующим или предыдущим элементом списка.
Стеки
В силу указанной дисциплины обслуживания, в стеке доступна единственая его позиция, которая называется вершиной стека- это позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх прежней вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).
Графически стек можно представить следующим образом:
Операции, производимые над стеками:
1. Занесение элемента в стек.
2. Выборка элемента из стека.
3. Определение пустоты стека.
4. Прочтение элемента без его выборки из стека.
5. Определение переполнения стека (для полустатических структур)
Алгоритмы основных операций со стеком