Существуют динамические и статические объекты. У обычные переменные сразу после её описания резервируется область памяти, и эта область закрепляется за переменной на все время работы программы. Такого рода переменные называют статическими переменными.
Часто бывает так, что какая-то переменная нужна не на всё время выполнение программы, а только на какую-то часть этого времени. Такие временные программные объекты могут занимать значительный объем памяти и одновременное существование всех таких объектов может потребовать столь большого объема машинной памяти, что соответствующая программа просто не сможет разместиться в ограниченной оперативной памяти машины.
Переменные которые могут резервировать область памяти, а затем снова освобождать во время выполнения программы стали называтьдинамическими. Динамические объекты будут возникать в процессе выполнения программы, а действия над ними необходимо задавать уже до выполнения. В Паскале для работы с динамическими объектами предусматривается специальный тип переменных, так называемый ссылочный тип. Каждому динамическому объекту в программе сопоставляется статическая переменная ссылочного типа. В терминах этих ссылочных переменных обосновываются действия над соответствующими динамическими объектами. Динамические объекты и ссылки: = ^ , где ^ — называемая «крышка», признак ссылочного типа, — это имя либо статического, либо ранее описанного типа значения.Рассмотрим листинг программы написанный на языке Паскаль:
СТРУКТУРЫ — ТВОЯ ГЛАВНАЯ ОШИБКА
masiv = array[1..10] of Integer;
: array [1..15] of RefReal;
Значение переменнойр может быть ссылкой на динамический объект целого типа. Значение переменнойq — ссылка на динамический объект литерного типа. Значение переменной RabMas — ссылка на динамический объект значение, которого является массив из 10 целых чисел.
Значения статических ссылочных переменных указывают место в памяти соответствующего динамического объекта. поэтому переменные ссылочного типа часто называют указателями. Динамическому объекту в отличие от статических не дается имен в обычном понимание этого слова.
Для ссылки на динамический объект в Паскале имеется такое понятие как переменная с указателем: = ^, где — это имя той статической переменой ссылочного типа, которая в программе поставлена в соответствие данному динамическому типу. «Крышка» после ссылочной переменной свидетельствует о том, что здесь речь идет не о значении ссылочной переменной, а о значении того программного объекта на которой указывает эта ссылочная переменная. Отличия использования динамических переменных от статических переменных: вместо описания самих динамических переменных в программе даются описания указателей(статических переменных ссылочного типа) поставленных в соответствие динамическим переменным; в подходящем месте программы должно быть представлено порождение каждой из динамической переменной (в Паскале процедура New); для ссылки на динамическую переменную используется переменная с указателем.
Что такое динамическая память. Утечка памяти. Стек и куча. Статическая память. Обзорный урок #45
Если в процессе выполнения программы некоторая динамический объект созданный ранее становиться не нужным, то его можно уничтожить, что позволит освободить оперативную память, которую он занимал. Для статической структуры данных выделяется фиксированная область памяти, которая определяется перед выполнением программы.
Использование статической структуры позволяет более эффективно использовать резерв времени выполнения программы, но к уменьшению размера свободной оперативной памяти. К статическим структурам данных относятся массивы и структуры. В Массивы объединяются элементы одного и того же типа.
Массив может состоять из одного элемента, а может запомнить столько, сколько позволяет оперативная память. Элементы массива запоминаются в памяти последовательно, каждый элемент хранит одно значение типа с которым был объявлен массив. Массивы могут обладать одним, двумя и более измерениями. Структуры для объединения данных различного типа в одну группу.
Они формируют оболочку вокруг одного или нескольких значений одного или нескольких типов данных. Элементы структуры хранятся в памяти вместе. Область памяти для динамической структуры данных определяется после начала выполнения программы и может меняться в процессе ее выполнения. Обычно их элементы используют указатели для ссылок на элементы, подобные им самим.
Применение динамических структур данных позволяет экономичнее использовать память, но снижает скорость выполнения программы. К динамическим структурам данных относятся списки, стеки и деревья. В Списокобъединяются элементы, содержащие указатель на следующий элемент своего типа.
Стек — это структура данных, работающая по принципу «последним пришел- первым вышел». Стек напоминает груду книг. Верхнюю книгу взять легко, но чтобы достать нижние книги, нужно убрать те, которые находятся сверху. Стек обычно используется для хранения адресов возврата из функций и локальных переменных, но его можно применять для хранения различных видов информации.
Деревья. Если добавить второй указатель в элемент списка, то он (элемент) сможет указывать сразу на 2 элемента своего собственного типа.
Еще работы по информатике
Реферат по информатике
Статические и динамические Web-страницы. Особенности скриптовых программ. Анализ языков управления сценариями (JavaScript, VBScript, PHP, Perl).
Источник: ronl.org
Классификация структур данных
На этапе создания спецификаций и требований, необходимых для разработки качественного ПО, важно определить структуру и формат данных, используемых в программном приложении. Каким же образом классифицируются структуры данных? Какие форматы представления данных используются? Чем различаются статические, динамические и полустатические структуры? Об этом — наша статья.
Вне зависимости от сложности и содержания любые данные представлены в памяти электронно-вычислительных устройств (ЭВМ) в виде последовательности битов (двоичных разрядов), причем их значения — это соответствующие двоичные числа. Однако сами по себе битовые последовательности структурированы недостаточно, поэтому они не очень удобны для практического использования. Именно поэтому на практике применяют структуры данных, которые организованы более сложно. Понятие структуры тесно связано с понятием типа данных.
Классификация
Структуры данных бывают физические и логические. В отличие от последних, физические отражают, по сути, способ представления данных в памяти ЭВМ, поэтому их называют еще и внутренними.
По своему составу структуры данных классифицируют на следующие типы:
— простые. Их нельзя разделить на составные части, которые больше, чем биты, то есть мы говорим о неделимых единицах. Для простого типа ясно определен размер и способ размещения структуры в памяти ПК;
— сложные, они же интегрированные. Состоят из других структур данных, которые бывают как простые, так и, в свою очередь, тоже сложные.
По наличию связей структуры бывают:
— несвязные: массивы, векторы, строки, стеки (Last In, First Out), очереди (First In, First Out);
— связные (к примеру, связные списки).
Также существует понятие изменчивости — это изменение количества элементов либо связей между ними. По признаку изменчивости структуры бывают:
— статические;
— полустатические;
— динамические.
Классификацию можно посмотреть на картинке ниже:
Здесь отдельного упоминания заслуживают файлы как структуры данных. Файлами называют, к примеру, совокупность записей, структурированных одинаково. Файлы бывают:
— прямого или комбинированного доступа;
Следующий критерий — характеристика упорядоченности элементов. По признаку упорядоченности структуры бывают:
— нелинейные: деревья, графы, многосвязные списки;
— линейные. По характеру распределения компонентов в памяти ЭВМ они могут иметь последовательное распределение (строки, векторы, массивы, стеки, очереди) и произвольное связное распределение (односвязные и двусвязные списки).
Когда мы указываем тип данных, мы четко определяем:
— размер памяти, который отводится под конкретную структуру;
— способ размещения структуры в памяти;
— значения, которые допустимы для этого типа данных;
— операции, которые поддерживаются.
Простые структуры данных
Как уже было сказано выше, это основа для создания более сложных структур. Также простые структуры называют примитивными либо базовыми (типами данных). Какие структуры сюда относят:
Для примера — структура простых типов для языка программирования Pascal:
Далее — формат представления беззнаковых чисел:
И формат представления чисел со знаком:
Статические структуры
Это не что иное, как структурированное множество простых структур. К примеру, тот же вектор можно представить упорядоченным множеством чисел. Для статических структур изменчивость несвойственна, ведь размер памяти ЭВМ, который отводится для этих данных, является постоянным, выделяясь на этапе компиляции либо выполнения программы.
Вектор
Вектором также называют и одномерный массив. Это структура данных, где число элементов фиксировано, причем речь идет об однотипных компонентах. У каждого компонента — свой индекс (уникальный номер). С физической точки зрения векторные компоненты размещаются в памяти в ячейках, расположенных подряд.
Двумерный массив
Двумерный массив (он же матрица) представляет собой вектор, причем каждый его элемент — тоже вектор. Если учесть внешние сходства, тогда то, что является справедливым для вектора, является справедливым и для матрицы.
Множество
Это набор неповторяющихся данных одного типа. Множество способно принимать все значения базового типа, а так как он не должен превышать 256 значений, то типом элементов множеств могут быть char, byte и их производные.
В памяти множество хранится в виде массива битов, причем каждый бит показывает, принадлежит ли элемент объявленному множеству. Таким образом, максимальное число элементов множества равно 256, а множество может занимать не больше 32 байт.
Записи
Комбинированный тип данных, в котором значения представляют собой нетривиальную структуру. Записи формируются из нескольких полей разного типа, причем внешний доступ к этим полям происходит по именам полей. Из этого можно сделать простейшее заключение: записи — это средство представления программных моделей реальных объектов, ведь реальный объект имеет несколько внешних свойств, описываемых разнотипными данными.
К примеру, с помощью записи можно описать преподавателя университета. В этом случае объект «преподаватель» будет иметь следующие характеристики:
- табельный номер, представленный целым положительным числом;
- фамилия-имя-отчество, представленные строкой символов;
- пол («М», «Ж») — это символ;
- наличие ученой степени — строка символов;
- зарплата — вещественное число;
- и так далее.
В памяти компьютера это можно представить:
— в виде последовательности полей, которые занимают произвольную непрерывную область памяти:
— в виде связного списка, имеющего указатели на значения полей записи:
Полустатические структуры
— поддержка простых способов изменения этой длины;
— изменение длины возможно не в произвольных, а в определенных пределах, которые не будут превышать максимально-допустимые (предельные) значения.
С точки зрения логики полустатическая структура — это последовательность данных, связанная отношениями линейного списка. Доступ к элементу возможен по порядковому номеру.
С физической точки зрения полустатические структуры представлены в виде вектора, располагаясь в непрерывной области памяти ПК. Также их можно представить в качестве однонаправленного связного списка, где каждый последующий компонент адресуется указателем, который находится в текущем компоненте.
Примеры: стеки, строки, очереди, деки.
Динамические структуры
Не обладают постоянным размером, в результате чего память выделяется в момент создания элементов либо в процессе выполнения программы. Когда необходимость в элементе отпадает, занимаемая им память освобождается.
Так как компонент находится в памяти не по порядку и не в одной области, его адрес нельзя вычислить из адреса начального либо предыдущего компонента. Именно поэтому компонентная связь формируется через указатели, которые содержат соответствующие адреса в памяти. Это не что иное, как связное представление данных в памяти. Вывод напрашивается сам собой: такое представление обеспечивает высокую изменчивость структуры.
• размер структуры ограничивается лишь объемом памяти ЭВМ;
• во время изменения логической последовательности элементов (выполнении основных операций по удалению, добавлению, изменению порядка следования) нужна лишь коррекция указателей.
• работа с указателями требует от разработчика высокой квалификации;
• на указатели тратится дополнительная память;
• на доступ тратится дополнительное время.
Связные линейные списки
Это простейшие динамические структуры. Они представляют собой упорядоченные множества, которые содержат переменное число компонентов, причем отсутствуют ограничения по длине.
Ниже изображен односвязный список:
— INF — информационное поле, которое содержит данные;
— NEXT — указатель на последующий компонент списка;
— «Голова списка» — указатель на начало;
— nil — указатель на последний элемент.
На практике использовать и обрабатывать односвязный список не всегда удобно, ведь нельзя перемещаться в противоположную сторону, что ставит под вопрос оперативное выполнение некоторых операций. Однако такая возможность существует у двухсвязного списка, ведь в нем каждый элемент обеспечивает хранение двух указателей: на последующий и на предыдущий компоненты. Также для удобства обработки он имеет особый элемент — указатель конца списка. Но за повышенное удобство и оперативное выполнение операций надо платить — в случае с двухсвязным списком наличие 2-х указателей в каждом компоненте повышает сложность и становится причиной дополнительных затрат памяти.
Заключение
В качестве заключения скажем, что структуризация данных осуществляется сегодня множеством различных способов. Понимание особенностей структур данных, их строения, функций и основных характеристик позволит вам повысить качество создаваемого программного обеспечения, не говоря уже о более оперативной разработке. Также при определении формата данных нужно всегда учитывать специфику поставленных задач, делая это еще на этапе создания спецификаций и требований.
Источник: otus.ru
2. Статические и полустатические структуры данных
Привет, сегодня поговорим про статические структуры данных, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое статические структуры данных, полустатические структуры данных , настоятельно рекомендую прочитать все из категории Структуры данных. Структуры данных — это совокупность элементов данных и отношений между ними. При этом под элементами данных может подразумеваться как простое данное так и структура данных. Под отношениями между данными понимают функциональные связи между ними и указатели на то, где находятся эти данные.
Графическое представление элемента структуры данных.
Элемент отношений — это совокупность всех связей элемента с другими элементами данных, рассматриваемой структуры.
Где S — структура данных, D — данные и R — отношения.
Как бы сложна ни была структура данных, в конечном итоге она состоит из простых данных (см. рис. 2.2, 2.3).
2.1 Уровни представления данных
Внутренний мир ЭВМ далеко не так прост, как мы думаем. Память машины состоит из миллионов триггеров, которые обрабатывают поступающую информацию