6. Вектор. Функциональная спецификация. Логическое описание и физическое представление.

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

Размер вектора очень важен, поэтому вектор должен состоять из 2х множеств: доступные индексы(мощность этого множества есть размер вектора) и множество компонент вектора. Для доступа к компоненте вектора необходимо прибавить к адресу блока размер одной компоненты, умноженной на ее индекс. Таким образом проведение операции изменение размера при уменьшении размера вектора с m на n компоненты вектора с индексами от 0 до n-1 не должны изменяться. При увеличении размера вектора с m на p компоненты с индексами 0 … m-1 должны сохранить свое значение, а компоненты с индексами m … p-1 могут быть неопределены либо проинициализированы значениями по умолчанию.

Поскольку ОС не всегда в состоянии выделить память непосредственно за последним блоком вектора, то операция изменения размера требует копирования оставшихся элементов в новый участок памяти, в котором есть достаточное количество памяти для размещения всех компонент вектора с новым размером. Эта операция неэффективна и требует O(N) времени выполнения, но такова цена операции доступа к компонентам, которая в таком случае выполняется за постоянное время.

Операции над вектором:

1. Создать empty -> V(T,In)

2. Пусто V(T,In) ->bool

3. Длина V(T,In) -> N

4. Загрузить V(T,In) * In -> T // вывести значение компоненты из вектора по ее индексу

5. Сохранить V(T,In) * In * T -> V(T,In)

6. Изменить длину V(T,In) * N -> V(T,Im)

7. Равны V(T,In) * V(T,In) -> bool

8. Уничтожить V(T,In) -> empty

Структура вектора в СИ:

Typedef struct {

T* data; //массив компонент типа Т

Int size; //размер вектора

} Vecctor;

В функции передается ссылка на вектор, выделение памяти под создаваемый вектор осуществляется при помощи функции malloc, перемещение вектора в другой участок памяти функцией realloc.

7. Очередь. Функциональная спецификация.

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

1. Постановка в очередь нового элемента

2. Проверка пустоты очереди

3. Просмотр первого элемента (если есть)

4. Извлечение из очереди первого элемента, если она не пуста.

Очереди применяются к 2м классам задач:

1. Для моделирования реальных очередей. (порядок обработки входящих сообщений, заход самолетов на посадку и тп.)

2. Для решения собственных задач информатики(алгоритм BFS – поиск в ширину для обхода графов, в ОС однотипные запросы к разным компонентам системы должны выполняться в процессе их поступления).

Очередь – упорядоченный одномерный, динамически изменяемый массив компонент в котором добавление компонент производится на одном конце набора, а считывание и удаление – на другом конце. Количество компонент называется длиной очереди. Длина может быть вычислена вручную перебором всех компонент очереди (извлечение и запись в другую очередь) , однако это дорогостоящая операция, требующая O(n) временной и пространственной сложности из за последовательного доступа к компонентам очереди.

Тип очередь характеризуется следующими операциями:

1. Создать empty -> Q(T)

2. Пусто Q(T) -> bool

3. Из_очереди Q(T) -> Q(T)

4. В_очередь Q(T) * T -> Q(T)

5. Первый Q(T) -> T

6. Длина Q(T) -> N

7. Уничтожить Q(T) -> empty

Привести набор тестов.

Пусто(Создать) = истина

Первый(В_очередь(Создать,t)) = t и тп.

8. Очередь. Логическое описание и физическое представление (файл).

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

Для реализации очереди на файле в паскале необходимо создать переменную типа очередь, базирующуюся на внешнем файле.

Процедура создать.

Функция пусто.

Пустой очереди должен соответствовать пустой файл.

Функция В_очередь.

Для добавление элемента в файл необходимо добраться до его конца.

Функция Из_очереди.

Выталкивает элемент из очереди. Для получения значения элемента используется функция Первый.

Функция Первый.

9. Очередь. Логическое описание и физическое представление(массив).

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

Есть 3 стратегии отображения очереди на массив:

1. Голова очереди фиксируется на первом элементе массива. Хвост очереди подвижен, поэтому время добавление элемента в очередь постоянно и невелико О(1). Однако при извлечении элемента из очереди все элементы кроме первого сдвигаются к началу массива. Цена этой операции высока и пропорциональна ее длине O(N).

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

3. Стратегия с кольцевым буфером. Перемещение очереди нет. Начало и конец очереди склеивают при помощи операции mod. При использовании кольцевого буфера как только одна из переменных-индексов достигает конца массива ее скачкообразно переставляют в начало массива на освобожденное ушедшими из очереди элементами место. Таким образом и сама очередь и свободная память образуют сплошные куски буферного массива (по модулю), между началом и концом которых добавляются и извлекаются элементы. Вставка и извлечение элементов производится за небольшое время O(1).

Описать функции добавления, извлечения, создания, проверки на пустоту, возврата размера, просмотра первого элемента в очереди на кольцевом буфере.

Struct queue{

T data[POOLSIZE];

Int first;

Int size;

};

Добавление в очередь производится следующим образом: q->data[(q->first+q->size)%POOLSIZE] = t , где дата – массив очереди, first – индекс головы, size – размер очереди, POOLSIZE – размер массива. Извлечение: q->first++; q->first %= POOLSIZE; q->size--;. Уничтожение очереди на статическом массиве не требуется, однако для унификации можно просто обнулить значение size в очереди.

10. Очередь. Логическое описание и физическое представление (динамические объекты).

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

Структура:

Struct queue{

Int size;

Item* first;

Item* last;

}

Функция Создать выделяет из кучи указатель на первый и последний элемент, а также устанавливает сайз размером 0.

Функция В_очередь выдает запрос системе на выделение памяти под элемент очереди. Значение нового элемента присваивается терминатору, также терминатору приписывается указатель на вновь созданный элемент. Таким образом вновь созданный элемент становится терминатором. Переменная размера очереди инкрементируется.

Функция Из_очереди запоминает указатель на первый элемент во временную переменную и переставляет ссылку q->first на q->first->next, затем освобождает память по указателю на первый элемент и уменьшает размер очереди на 1.

Функция Первый вытаскивает значение из указателя на первый элемент очереди q->first->data

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

11. Стек. Функциональная спецификация.

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

1. Пополнение стека новыми данными

2. Проверка стека на пустоту

3. Просмотр верхнего(самого нового) элемента

4. Уничтожение последнего добавленного элемента

Стеки полезны при решении различных задач информатики:

1. Выполнение рекурсивной процедуры организуется при помощи стека.

2. В стеке удобно отводить память под локальные переменные программных единиц блочной структуры

Тип стека характеризуется операциями:

1. Создать empty -> S(T)

2. Пусто S(T) -> bool

3. В_стек S(T) * T -> S(T)

4. Из_стека S(T) -> S(T)

5. Глубина S(T) -> N

6. Верх S(T) -> T

7. Уничтожить S(T) -> empty

Заносящиеся во вновь созданный стек элементы т1 и т2 при извлечении их инвертируют их порядок. Это свойство может быть распространено по индукции на любую последовательность элементов.

Тесты для стека

Пусто(Создать) = истина

Верх(В_стек(s,t)) = t и тп.

12. Стек. Логическое описание.

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

13. Стек. Физическое представление(массив).

Для реализации стека на массиве ограничим максимальную глубину стека величиной POOLSIZE, все элементы стека размещаются в массиве data величины POOLSIZE. Переменная size является как длиной стека, так и уменьшенная на 1 индексом его вершины.

Структура стека:

Struct stack{

Int size;

T* data;

};

Функция создания обнуляет размер стека

Функция проверки на пустоту возвращает результат сравнения размера стека с нулем

Функция Размер возвращает размер стека

Функция В_стек добавляет элемент на место size и увеличивает размер стека на единицу.

Функция Из_стека декрементирует размер стека

Функция Верх возвращает элемент стека с индексом size-1

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

14. Стек. Реализация на динамических структурах.

Для реализации стека на динамических структурах понадобится тип «Элемент стека» содержащий значение элемента и ссылку на предыдущий элемент стека.

Само описание стека заключается в описании двух переменных: указателя на верхушку стека и переменной отвечающей за глубину стека.

Структура стека:

Struct stack{

Int size;

Item* Top;

};

Функция создания обнуляет размер стека, а указателю на верхушку присваивает значение NULL.

Функция Пусто возвращает результат сравнения размера стека с 0

Функция В_стек создает новый элемент стека, куда записывается добавляемое значение, ссылкой на следующий элемент становится ссылка на текущую верхушку стека, а верхушкой стека становится созданный элемент. После выполняется Инкрементирование размера стека.

Функция Из_стека Копирует указатель на верхушку стека в созданную временную переменную. Верхушке стека присваивается значение следующего элемента, а память изначальной верхушки стека освобождается.

Функия Верх возвращает значение верхушки стека.

Функция уничтожить покомпонентно очищает память стека сохраняя указатель на текущую верхушку во временной переменной и, передвигая указатель на следующий элемент, очищает память предыдущего значения верхушки стека. После очищения памяти стека размеру присваивается значение 0, а верхушке NULL.