- •2.Классификация структур данных
- •3. Связные и несвязные структуры данных.
- •5.Тип «указатель» и ситуации его применения.
- •7. Статические структуры данных.
- •8. Назначение хеширования данных.
- •11. Понятие динамических структур данных. Возможности, предоставляемые использованием динамических структур данных.
- •13.Абстрактный тип данных «очередь». Реализация очереди с помощью указателей. Привести рисунок и определить абстрактный тип «очередь».
- •14. Абстрактный тип данных «стек». Реализация стека с помощью указателей. Привести пример.
- •16. Особенности и определение рекурсивного вычислительного процесса. Привести пример использования рекурсии и стека.
- •17.Постфиксная, префиксная, инфиксная записи представления выражений и их особенности
- •18. Правило вычисления выражения в обратной польской записи.
Типы данных. Абстрактные типы данных
Тип данных – мн-во значений, которые может принимать переменная.Тип может присваиваться компил-ром. или
задаваться явно.Значение меняется, а тип-нет.Паскаль под-
держивает защиту типов. Абстрактный тип-мат. модель+
различные операторы,определ. в рамках модели.Алгоритм
разрабат. в терминах абстр. типов, а потом реализ. на кон-
кретном ЯП.Для представления абстр. типа использ. структ.
данных, представл. переменные разл. типов данных, объед.
особым образом.Выбор структуры данных влияет на произ-
водительность.
2.Классификация структур данных
Физ. структура данных отобр. способ физическ. представл.
данных в памяти машины.Существ. логическ. структура.
Между ними должно быть соотв., отображ. одну в другую.
Различ. простые и интегрир. структуры.Простые не могут
разделяться на части >1 бит.Интегр.-структ.,сост. части
которых другие структ. или данные.
Различ. несвязные(массивы,строки) и связные(связанные
списки.
3. Связные и несвязные структуры данных.
Статические, полустатические и динамические структуры
Изменчивость-изменение числа эл-тов. и/или связей между
ними.По изменчивости:статические, полустатические, дина-
мические.
Структуры опер. памяти-оперативные.Файловые структ. –
внешние.
По упоряд. – линейные и нелинейные.
Простые:Числов.,символьн.,логическ.
Статич:Массивы, записи, таблицы.
Полустатич.:Строки, стеки, деки,очереди.
Динамическ.:Деревья,Графы,Связ. списки.
Файлов:Послед. доступ.,прям. доступа, комбин. доступа.
4.Связь между структурой и типом данных.
Информация, определяемая типом данных.
В ЯП прост. структ. представл. базовыми типами:числовыми
битовыми,логическими, символьн.,интервальн.,указателями.
Целые типы представл. объекты, дискретн. по своей природе.
В памяти они хранятся в виде знака и значения.
Для получения большей отчности применяют запись с плав.
точкой.Это эффективно для больших и маленьк. чисел, при
условии, что ограничено число значащ. цифр и не всё число
может быть представлено в памяти.
Значениями лог. типа могут быть константы истина(1)/ложь(0).
Данные занимают одно маш. слово. Поддерживают операции
Булев. алгебры.Результаты лог. типа получаются при сравнении
любых других.
Значениями симв. типа. явл. символы из набора ASCII.
Занимает 1 байт. Операция – только сравнение.Сравниваются
коды как числа без знака.
5.Тип «указатель» и ситуации его применения.
Физическая структура указателя.
Память-важный ресурс любой системы. Одна из главных задач-
управление памятью.При стат. способе не тратится время на
управление памятью.Стат. – вов время трансляции.
Динам. способ – во время выполнения.Память не резервируется
заранее, а по мере необходимости.
Для организ. динам. способа использ. указатели,указыв поло-
жжение другой переем.Типизир.Содержат адрес перемен. опред.
типа.Адрес задаётся 2-мя 16-разрядн. словами – сегментом и
смещением.Сегмент – участок в 64 кб. Смещение указ кол-во
байт от начала сегмента до нужн. адреса. Абс. адрес=сегм.*16+
+смещение.
6.Представление указателей в языке Паскаль.
Операции над указателями.
var p1,p2:^integer; {указ. на целый}
begin
p1:=nil;
p2:=nil;{Не ссылается ни на какой участок}
new(p1){Создание нового указ., адр- в р1}
new(p2)
p1^:=2;
p1^:=p2^;
p2:=p1;
Осн. опер. – присваив., взятие адреса, выборка.
Присваив.-двухместн. опер. Оба эл-та – указ.
Копирует значение одного указ. в другой. В результ. оба
ссылаются на один и тот же адрес в памяти.
Получение адреса – одноместн. Результат – адрес объекта
операнда.
Выборка – одноместн. Операнд – указ. Результат – данные,
выбранные по адресу операнда.
Набор опер. достаточен для приклад. прогр. Этим и
ограничивается.