Классы памяти. Глобальные и локальные среды.

Определение переменной вызывает выделение памяти для хранения ее значения. Класс выделяемой памяти определяется спецификатором класса памяти, и определяет время жизни и область видимости переменной, связанные с понятием блока программы.

В языке СИ блоком считается последовательность объявлений, определений и операторов, заключенная в фигурные скобки. Существуют два вида блоков - составной оператор и определение функции, состоящее из составного оператора, являющегося телом функции, и предшествующего телу заголовка функции (в который входят имя функции, типы возвращаемого значения и формальных параметров). Блоки могут включать в себя составные операторы, но не определения функций. Внутренний блок называется вложенным, а внешний блок - объемлющим.

Время жизни - это интервал времени выполнения программы, в течение которого программный объект (переменная или функция) существует. Время жизни переменной может быть локальным или глобальным. Переменная с глобальным временем жизни имеет распределенную для нее память и определенное значение на протяжении всего времени выполнения программы, начиная с момента выполнения объявления этой переменной. Переменная с локальным временем жизни имеет распределенную для него память и определенное значение только во время выполнения блока, в котором эта переменная определена или объявлена. При каждом входе в блок для локальной переменной распределяется новая память, которая освобождается при выходе из блока.

Все функции в СИ имеют глобальное время жизни и существуют в течение всего времени выполнения программы.

Область видимости - это часть текста программы, в которой может быть использован данный объект.

Спецификатор класса памяти в объявлении переменной может быть auto, register, static или extern. Если класс памяти не указан, то он определяется по умолчанию из контекста объявления.

Объекты классов auto и register имеют локальное время жизни. Спецификаторы static и extern определяют объекты с глобальным временем жизни.

При объявлении переменной на внутреннем уровне может быть использован любой из четырех спецификаторов класса памяти, а если он не указан, то подразумевается класс памяти auto.

Ссылочные типы данных.

Указатель - это адрес памяти, распределяемой для размещения идентификатора (в качестве идентификатора может выступать имя переменной, массива, структуры, строкового литерала). В том случае, если переменная объявлена как указатель, то она содержит адрес памяти, по которому может находиться скалярная величина любого типа. При объявлении переменной типа указатель, необходимо определить тип объекта данных, адрес которых будет содержать переменная, и имя указателя с предшествующей звездочкой (или группой звездочек). Формат объявления указателя:

спецификатор-типа [ модификатор ] * описатель.

Спецификатор-типа задает тип объекта и может быть любого основного типа, типа структуры, смеси (об этом будет сказано ниже). Задавая вместо спецификатора-типа ключевое слово void, можно своеобразным образом отсрочить спецификацию типа, на который ссылается указатель. Переменная, объявляемая как указатель на тип void, может быть использована для ссылки на объект любого типа. Однако для того, чтобы можно было выполнить арифметические и логические операции над указателями или над объектами, на которые они указывают, необходимо при выполнении каждой операции явно определить тип объектов. Такие определения типов может быть выполнено с помощью операции приведения типов.

Размер переменной объявленной как указатель, зависит от архитектуры компьютера и от используемой модели памяти, для которой будет компилироваться программа. Указатели на различные типы данных не обязательно должны иметь одинаковую длину.

Структурирование данных.

Cтруктуры - это составной объект, в который входят элементы любых типов, за исключением функций. В отличие от массива, который является однородным объектом, структура может быть неоднородной. Тип структуры определяется записью вида:

struct { список определений }

В структуре обязательно должен быть указан хотя бы один компонент. Определение структур имеет следующий вид:

тип-данных описатель;

где тип-данных указывает тип структуры для объектов, определяемых в описателях. В простейшей форме описатели представляют собой идентификаторы или массивы.

 

Объединение подобно структуре, однако в каждый момент времени может использоваться (или другими словами быть ответным) только один из элементов объединения. Тип объединения может задаваться в следующем виде:

union { описание элемента 1;... описание элемента n; };

 

Главной особенностью объединения является то, что для каждого из объявленных элементов выделяется одна и та же область памяти, т.е. они перекрываются. Хотя доступ к этой области памяти возможен с использованием любого из элементов, элемент для этой цели должен выбираться так, чтобы полученный результат не был бессмысленным.

 

Элементом структуры может быть битовое поле, обеспечивающее доступ к отдельным битам памяти. Вне структур битовые поля объявлять нельзя. Нельзя также организовывать массивы битовых полей и нельзя применять к полям операцию определения адреса. В общем случае тип структуры с битовым полем задается в следующем виде:

struct { unsigned идентификатор 1: длина-поля 1; unsigned идентификатор 2: длина-поля 2; }

 

Длина поля задается целым выражением или константой. Эта константа определяет число битов, отведенное соответствующему полю. Поле нулевой длины обозначает выравнивание на границу следующего слова.

 

Билет №17

Общий подход к абстрагированию и структурированию данных. Понятие объекта и объектно-ориентированные технологии. Последовательности и однопроходные алгоритмы. Моделирование динамических структур данных с последовательным доступом на примере стека и очереди.

Объектно – ориентированное программирование.

 

Объектно - ориентированное программирование — парадигма программирования, в которой основной концепцией является понятие объекта, отождествляя его с объектом предметной области.

 

Первым языком программирования, в котором были предложены принципы объектной ориентированности, была Симула. В момент своего появления (в 1967 году), этот язык программирования предложил поистине революционные идеи: объекты, классы, виртуальные методы и др., однако это всё не было воспринято современниками как нечто грандиозное. Тем не менее, большинство концепций были развиты Аланом Кэйем и Дэном Ингаллсом в языке Smalltalk. Именно он позже стал считаться первым объектно-ориентированным языком программирования.

 

Главные понятия и разновидности

 

Структура данных «класс», представляющая собой объектный тип данных, внешне похожа на типы данных процедурно-ориентированных языков, такие как структура в языке С, в которой поля могут сами быть не только данными, но и методами (то есть процедурами или функциями). Таким образом, в простейшем случае объектно-ориентированное программирование получается добавлением к процедурно-ориентированному процедурного типа данных, то есть, переменных, способных принимать значение функций и процедур. Вдобавок класс поддерживает такие свойства как наследование, полиморфизм и отчасти — инкапсуляцию. Объектное программирование противопоставляется процедурному программированию, где данные и подпрограммы (процедуры, функции) их обработки формально не связаны. Кроме того, в объектно-ориентированном программировании часто большое значение имеет понятие события.

 

Основные понятия

Абстракция данных

Объекты представляют собою неполную информацию о реальных сущностях предметной области. Их модели адекватны решаемой задаче, работать с ними намного удобнее, чем с низкоуровневым описанием всех возможных свойств и реакций объекта. Абстракция данных — подход к обработке данных по принципу чёрного ящика. Данные обрабатываются функцией высокого уровня с помощью вызова функций низкого уровня. Обычно такой подход используется в объектно-ориентированном программировании, что позволяет работать с объектами, не вдаваясь в особенности их реализации.

Инкапсуляция

Инкапсуляция — это принцип, согласно которому любой класс должен рассматриваться как чёрный ящик — пользователь класса должен видеть и использовать только интерфейс (т. е. список декларируемых свойств и методов) класса и не вникать в его внутреннюю реализацию. Этот принцип (теоретически) позволяет минимизировать число связей между классами и, соответственно, упростить независимую реализацию и модификацию классов.

Наследование

Наследованием называется возможность порождать один класс от другого с сохранением всех свойств и методов класса-предка (иногда его называют суперклассом) и добавляя, при необходимости, новые свойства и методы. Наследование призвано отобразить такое свойство реального мира, как иерархичность.

Полиморфизм

Полиморфизмом называют явление, при котором классы-потомки могут изменять реализацию метода класса-предка, сохраняя его сигнатуру (таким образом, сохраняя неизменным интерфейс класса-предка). Это позволяет обрабатывать объекты классов-потомков как однотипные объекты, не смотря на то, что реализация методов у них может различаться.

 

Основные концепции

· Система состоит из объектов

· Объекты некоторым образом взаимодействуют между собой

· Каждый объект характеризуется своим состоянием и поведением

 

Традиционный подход

 

Данный подход реализован в огромном количестве языков программирования; основоположником является язык C++. Очень часто под объектно-ориентированным подходом понимается именно модель, реализованная в этом языке и клонированная в других. Дополнительные концепции этого подхода таковы:

· Инкапсуляция

· Наследование

· Полиморфизм

 

Обмен сообщениями

Прототипное программирование

Реализационный подход

Концептуальный подход

//их 4 штуки нетрадиционных, о них лучше не заикаться, потому что деталей там – заебёсси

 

Стек (англ. stack — стопка) –смотри в 5ом билете. Там выделено.

 

Список — упорядоченная последовательность элементов данных, воспринимаемая как особая контейнерная структура данных. В качестве элементов списка могут выступать любые другие элементы данных, в том числе и сами списки. У определённой таким образом структуры данных имеются некоторые свойства:

Размер списка — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком.

· Тип элементов — тот самый тип A, над которым строится список; все элементы в списке должны быть этого типа.

· Отсортированность — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).

· Возможности доступа — некоторые списки в зависимости от реализации могут обеспечивать программиста селекторами для доступа непосредственно к заданному по номеру элементу.

· Сравниваемость — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.

 

Как должно быть понятно из названия рассматриваемой структуры данных, списки используются для хранения наборов однотипных элементов. Такие элементы могут быть отсортированы для использования в функциях поиска или функциях для быстрой вставки новых элементов в список.

 

Очередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть dequeue, при этом выбранный элемент из очереди удаляется).

 

Применение очередей

Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.

 

Последовательность – это упорядоченная структура данных, в которой в каждый момент времени мы имеем доступ только к одному элементу данных, и только обработав его, можем перейти к следующему. Что вновь попасть на тот же элемент последовательности, надо вновь обработать её сначала до искомого элемента. Действия в последовательности (собственно, пример однопроходного алгоритма):

· Открыть последовательность

· Прочитать очередной элемент

· Пропустить очередной элемент

· Добавить элемент в конец последовательности

· Встать в начало последовательности

· Проверка на конец последовательности

 

Билет 18

Ссылочные реализации динамических структур данных. Организация списков, операции добавления и исключения элементов. Представление деревьев и графов. Алгоритмы обхода дерева. Деревья поиска. Примеры реализации.

Списки

6.1 Ссылочный подход

1. элементы данных образуют линейную цепочку, т.е. для каждого элемента существует "следующий" и "предыдущий" (естественно, кроме концевых элементов, для которых существует только один такой соседний элемент);

2. в каждый момент времени в этой линейной цепочке определена некоторая текущая позиция и нам разрешен доступ к элементу в этой текущей позиции (или к его непосредственным "соседям").

3. положение текущей позиции можно изменять и тем самым получать доступ к значению любого элемента данной структуры не извлекая из нее элементов;

4. добавление и удаление элементов может происходить в окрестности текущей позиции, причем эти операции не должны приводить к массовым пересылкам данных в памяти;

Структуры данных, обладающие указанными свойствами обычно называют списками. Наглядным примером списочной организации данных может служить работа с текстом в боль­шинстве текстовых редакторов. Редактирование текста можно выполнять в окрестности текущей позиции, которая опреде­ляется положением курсора. Можно удалить текущую строку или вставить новую строку непосредственно перед текущей. Можно перемещаться по строкам по направлению к началу или концу текста. Таким образом, весь текст можно рассматривать как список строк. Точно так же каждую отдельную строку можно рассматривать как список символов, по которому можно перемещать текущую позицию редактирования к началу или концу строки и добавлять или удалять символы в окрестности текущей позиции.

Обсудим теперь идеи реализации подобных структур. Для того, чтобы обеспечить выполнение условия 4, нам придется отказаться от непрерывности размещения элементов. Новый добавляемый элемент списка будет размещаться в памяти там, где в данный момент для него найдется место. Таким образом, добавление нового элемента никак не повлияет на размещение уже существующих данных.

 

Будем называть указателем списка переменную (или переменные), хранящие указатель на доступный в данный момент элемент (или два соседних элемента) списка. Изменяя значение этого указателя ("передвигая" указатель списка), мы можем добраться до любой позиции в списке, т.е. обеспечить выполнение условия 3.

 

6.2 Одно- и двунаправленные списки

Сначала мы рассмотрим реализацию двунаправленного списка, в котором каждый элемент (кроме первого и последнего) ссылается на два соседних с ним элемента. Примем следующие соглашения по поводу задания структуры этого списка:

 

• каждый элемент списка представляет собой составной объ­ект, хранящий в себе содержательную информацию данного элемента и два указателя — на следующий и предыдущий элементы;

• в каждый момент времени разрешен доступ только к двум соседним элементам списка (будем называть их элемент до указателя и элемент за указателем), пару указателей на позиции этих двух элементов будем называть указателем текущей позиции;

• удалять можно только те элементы, на которые показывает указатель текущей позиции (т.е. элементы до или за указа­телем), при этом соответствующая ссылка указателя списка перемещается на предыдущий (соответственно, следующий) элемент;

• новые элементы добавляются в окрестности указателя те­кущей позиции, т.е. добавленный элемент может стать либо элементом до указателя, либо элементом за указателем.

 

В этих соглашениях не отражен только один пункт — как работать с концевыми элементами списка, т.е. как отличать их от внутренних, как устанавливать указатель текущей позиции в начало или конец списка и т.д. Обычно применяется одно из двух решений: первое — указатель на предыдущий для первого элемента и. указатель на следующий для последнего элемента полагаются равными нулю, второе — вводится дополнительный служебный элемент списка, который замыкает весь список в коль­цо.

 

7 Деревья

7.1 Определения и обходы

Понятие списка, которое мы рассмотрели в предыдущем разделе, естественным образом обобщается на структуры с множествен­ными связями между отдельными элементами. Одной из таких структур является дерево. В математике дерево определяется как связный граф, не содержащий циклов. Если в этом графе выделена одна вершина, то говорят, что дерево имеет корень. Мы будем рассматривать именно такие деревья. Наличие корня в дереве сразу определяет некоторое отношение подчиненности вершин. Для большей четкости изложения введем несколько определений.

Определение 1. Расстоянием (или длиной пути) между двумя вершинами А и В дерева назовем количество ребер графа, содержащихся в связной цепочке ребер, соединяющих А и В. (Поскольку дерево — это граф без циклов, расстояние между двумя вершинами определяется однозначно.)

Определение 2. Вершина В называется потомком вершины А, если расстояние между А и В равно 1 и расстояние от А до корня меньше, чем расстояние от В до корня дерева. Вершину А будем также называть родителем вершины В.

Определение 3. Будем говорить, что вершина А принадле­жит k-му уровню дерева, если расстояние от А до корня дерева равно к.

Очевидно, что уровень 0 дерева содержит только корень, а уровень к дерева образован потомками всех вершин уровня к — 1.

Определение 4. Ветвью дерева назовем связную последо­вательность вершин, начинающуюся в корне и оканчивающуюся

на вершине, не имеющей потомков. Длиной ветви назовем число вершин в этой ветви.

Определение 5. Дерево, в котором каждая вершина имеет не более двух потомков, называется бинарным, в противном случае будем дерево называть произвольным.

 

Чтобы реализовать хранение и работу с данными, содержа­щимися в вершинах дерева, нам необходимо каким-то образом представить существующие связи между между отдельными вершинами. Так как каждая вершина связана ребрами не более, чем с тремя другими вершинами, то мы можем естественным образом обобщить списочный подход и для представления вершины ввести следующий класс¹:

class TreeNode

{ public:

Type value;

TreeNode *prev,*left,«right;

};

где указатели left и right показывают на потомков, a prev — на родителя. При этом, если вершина не имеет соседей в каком-нибудь направлении, то соответствующий указатель имеет нулевое значение.

Такой способ представления каждой отдельной вершины является исчерпывающим для бинарного дерева.