Структуры и алгоритмы обработки данных, часть 4

9.  Какие характеристики стека вам известны?

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

push

Добавить (положить) в конец стека новый элемент

pop

Извлечь из стека последний элемент

back

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в стеке

clear

Очистить стек (удалить из него все элементы)

10.  Какие характеристики дека вам известны?

Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

push_front

Добавить (положить) в начало дека новый элемент

push_back

Добавить (положить) в конец дека новый элемент

pop_front

Извлечь из дека первый элемент

pop_back

Извлечь из дека последний элемент

front

Узнать значение первого элемента (не удаляя его)

back

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в деке

clear

Очистить дек (удалить из него все элементы)

11.  Какие характеристики очереди вам известны?

Очередью (aнгл. queue) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.

Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет "ползти" дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.

Структуры и алгоритмы обработки данных, часть 3

7.  Расскажите о представлении линейных структур данных в ЭВМ

   Наиболее простой формой хранения данных в памяти ЭВМ является одномерный линейный список. Линейный список-это множество n>=0 объектов (узлов) Х(1), Х(2), Х(3)... Х(n) структурные свойства которого связаны только с линейным (одномерным) относительным расположением узлов. Если n>0, то X(1) является первым узлом; для 1<i<n узел X(i-1) предшествует узлу X(i), а узел X(i+1) следует за ним, X(n) является последним узлом, т. е. линейный список реализует структуру, которую можно определить как линейное упорядочение элементов данных.

  Линейный список X рассматривают как последовательность Х(1), Х(2), Х(3)... Х(n) компоненты которой идентифициро­ваны порядковым номером, указывающим их относительное расположение в X.

   Одномерный линейный список, используемый для хранения данных в памяти машины, называют еще вектором данных или физической структурой хранения данных. Использование линейного списка в качестве физической структуры хранения данных определяется свойствами памяти вычислительной машины. Так, оперативная память ЕС ЭВМ представляет вектор, в котором байты упорядочены по возрастанию их адресов от О до наивысшего, т. е. проидентифицированы адресом.

   Проблема представления логических структур данных в памяти ЭВМ заключается в нахождении эффективных методов отображения логической структуры данных на физическую структуру хранения. Такое отображение называют адресной функцией.

    При реализации адресной функции используют два основных метода: последовательное распределение памяти; связанное распределение памяти.

8. Расскажите о представлении нелинейных структур данных в ЭВМ

    Отношения между объектами реального мира часто носят нелинейный характер. Это могут быть отношения, определяемые логическими условиями, отношениями типа "один-ко-многим" или отношениями типа "многие-ко-многим". Отношения "один-ко-многим" носят иерархический характер и отображаются древовидными структурами. В виде иерархии может быть представлена например, структура учебных подразделений ВУЗа.

  Отношения "многие-ко-многим" носят более универсальный характер и отображается структурами графов. Пример такого отношения. Каждый ВУЗ распределяет своих выпускников на различные предприятия. В то же время предприятие поучает специалистов из различных ВУЗов.

     Граф общего вида состоит из ряда вершин (узлов) и ребер, связывающих пары вершин. Если в понятия "ребро" и "вершина" вложить определенную смысловую нагрузку, то графы можно использовать для представления данных. Так вершинам графа можно сопоставить определенные объекты, тогда ребра будут соответствовать отношениям между объектами. В литературе по структурам баз данных модель данных, имеющую вид ориентированного графа, называют сетью.

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

Структуры и алгоритмы обработки данных, часть 2

5. Охарактеризуйте линейные структуры данных

Линейные структуры данных – это структуры данных, в которых переход от одного элемента данных к другому не зависит от каких-либо логических условий, т.е. в линейных структурах используются лишь безусловные связи элементов.

 К линейным структурам относятся стеки, очереди и деки.

Очереди и стеки — это динамически изменяемые упорядоченные наборы элементов. Новые элементы в очередях и стеках всегда добавляются к одному и тому же концу набора — «входному концу».

Стек функционирует по принципу «последним пришел — первым ушел» , при этом удаление элементов производится с входного конца. При добавлении в стек нового элемента данных все ранее загруженные элементы сдвигаются на одну позицию в глубину стека, а при удалении элемента данных сдвиг производится на одну позицию ко входу в стек. По такому принципу используется, например, стопка бумаги (листы добавляются и удаляются сверху) или магазин автомата (верхний патрон выстреливается первым), поэтому иногда стек называют магазином.

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

6. Охарактеризуйте нелинейные структуры данных

Линейные - алгоритм в пошаговом исполнении от начала до конца.

Нелинейные - алгоритм с переходами по условию.

Структуры и алгоритмы обработки данных, часть 1

1.   Какие сигналы несут новую информацию?

Цифровые.

2. Укажите причины появления искажений при взаимном преобразовании цифрового и аналогового сигнала

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

3.  Кратко охарактеризуйте известные вам типы данных

Типы float, double и long double предназначены для чисел с плавающей точкой и различаются точностью представления (количеством значащих разрядов) и диапазоном. Обычно float (одинарная точность) занимает одно машинное слово, double (двойная точность) – два, а long double (расширенная точность) – три.

Символьная переменная — это переменная типа char, занимающая в памяти 1 байт;

short, int и long вместе составляют целые типы, которые, в свою очередь, могут быть знаковыми (signed) и беззнаковыми (unsigned). В знаковых типах самый левый бит служит для хранения знака (0 – плюс, 1 – минус), а оставшиеся биты содержат значение. В беззнаковых типах все биты используются для значения. 8-битовый тип signed char может представлять значения от -128 до 127, а unsigned char – от 0 до 255.

4.  Кратко охарактеризуйте известные вам структуры данных

Строка – конечная линейная упорядоченная последовательность простых данных символьного типа, которое рассматривается как единое целое. Логическая структура строки представляет собой вектор или одномерный массив. Максимальная длина 255.

Линейный список – упорядоченная последовательность элементов данных.

Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним.

Очередью (aнгл. queue)) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.

Структура – иерархически упорядоченная коллекция данных.

Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь.

Множество – произвольный набор однотипных элементов, понимаемое как единое целое.