Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Полу статические структуры данных
Свойства полустатических структур данных: • они имеют переменную длину и простые способы ее изменения; • изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения. С логической точки зрения полустатическая структура представляет собой последовательность данных, связанную отношениями линейного списка (см. разд. 3.3.5). Доступ к элементу может осуществляться по его порядковому номеру. Физически полустатические структуры представляются либо в виде вектора, т. е. располагаются в непрерывной области памяти, либо в виде однонаправленного связного списка, где каждый следующий элемент адресуется указателем, находящимся в текущем элементе. К полустатическим структурам относятся стеки, очереди, деки, строки.
Динамические структуры данных Динамические структуры не имеют постоянного размера, поэтому память под отдельные элементы таких структур выделяется в момент, когда они создаются в процессе выполнения программы, а не во время трансляции. Когда в элементе структуры больше нет необходимости, занимаемая им память освобождается (элемент «разрушается»). Поскольку элементы динамической структуры располагаются в памяти не по порядку и даже не в одной области, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Связь между элементами динамической структуры устанавливается через указатели, содержащие адреса элементов в памяти. Такое представление данных в памяти называется связным. Таким образом, кроме информационных полей, ради которых создается структура и которые являются видимыми для конечного пользователя ПО, динамические структуры содержат поля для связи с другими элементами, видимые только для программиста — разработчика ПО. С помощью связного представления данных обеспечивается высокая изменчивость структуры. Достоинства динамических структур: • размер структуры ограничивается только объемом памяти компьютера; • при изменении логической последовательности элементов структуры (удалении, добавлении элемента, изменении порядка следования элементов) требуется только коррекция указателей. С другой стороны, такие структуры обладают рядом недостатков:
• работа с указателями требует высокой квалификации программиста; • на указатели расходуется дополнительная память; • дополнительный расход времени на доступ к элементам связной структуры.
Связные линейные списки Линейные связные списки являются простейшими динамическими структурами данных. Они являются упорядоченными множествами, содержащими переменное число элементов, на которые не накладываются ограничения по длине. На рис. 3.10 приведена структура односвязного списка. Здесь поле INF информационное поле, содержащее данные, NEXT — указатель на следующий элемент списка. Голова списка — указатель на начало списка. Указатель на следующий элемент последнего элемента списка содержит значение nil, это является признаком последнего элемента.
Рис. 3.10. Структура односвязного списка Двусвязные списки Обработка односвязного списка не всегда удобна, так как невозможно двигаться в противоположную сторону. Такую возможность обеспечивает двусвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы. Структура линейного двусвязного списка приведена на рис. 3.11, где поле NEXT — указатель на следующий элемент, поле PREV — указатель на предыдущий элемент. Первый и последний элементы такого списка содержат nil в указателе на предыдущий и последующий элементы соответственно. Рис. 3.11. Структура двусвязного списка
|
|||||
Последнее изменение этой страницы: 2016-12-29; просмотров: 418; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.22.181.81 (0.006 с.) |