Данные и их обработка. Структуры данных. Неструктурированные типы данных.

Данные — это результат фиксации, отображения информации на каком-либо материальном носителе, то есть зарегистрированное на носителе представление сведений независимо от того, дошли ли эти сведения до какого-нибудь приёмника и интересуют ли они его

• сбор данных — накопление информации с целью обеспечения достаточной полноты для принятия решений;

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

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

• сортировка данных — упорядочение данных по заданному признаку с целью удобства использования; повышает доступность информации;

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

• защита данных — комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных;

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

• преобразование данных — перевод данных из одной формы в другую или из одной структуры в другую.

Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество элементов данных и множество связей между ними.

Понятие ФИЗИЧЕСКОЙ структуры данных отражает способ физического представления данных в памяти машины. Рассмотрение же структуры данных без учета ее представления в машинной памяти называется абстрактной или ЛОГИЧЕСКОЙ структурой.

ПРОСТЫМИ (базовыми, примитивными) структурами (типами) данных называются такие, которые не могут быть расчленены на составные части, большие, чем биты. ИНТЕГРИРОВАННЫМИ (структурированными, композитными, сложными) называются такие структуры данных, составными частями которых являются другие структуры - простые или в свою очередь интегрированные.

В зависимости от отсутствия или наличия явно заданных связей между элементами данных принято различать НЕСВЯЗНЫЕ и СВЯЗНЫЕ структуры.

 

Абстракция данных. Понятия класса и объекта. Методы класса. Указатели на объекты.

Класс — это тип, описывающий устройство объектов, их поведение и способ представления.

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

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

Описание класса начинается со служебного слова class, вслед за которым указывается имя класса. Затем в блоке следует описание класса и после закрывающей скобки блока ставится точка с запятой.

Описание класса состоит из полей и методов.

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

К полям внутри класса можно обращаться непосредственно по именам полей.

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

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

Методы и поля входящие в состав класса называются членами класса. При этом методы часто называют функциями-членами класса.

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

Абстракция данных — это выделение существенных характеристик объекта, которые отличают его от прочих объектов, четко определяя его границы.

Абстракция данных в ООП предусматривает выделение характеристик, существенных в рамках решаемой задачи и рассматриваемой предметной области.

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

Вес, размер и положение — это поля будущего объекта-контейнера.

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

 

26. Линейные структуры данных: стек и очередь как примеры абстрактных типов данных.

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

Программная реализация стека

Программно стек можно реализовать двумя основными способами:

1) на базе массива. При этом способе количество элементов ограничено размером массива. Дно стека соответствует элементу массива с индексом 0, а вершина стека – значению массива с индексом равному <количество элементов в стеке – 1>.

2) на базе связного списка. Количество элементов ограничено размером свободной оперативной памяти. Каждый элемент связного списка содержит два поля – информационное (содержит значение элемента) и адресное (содержит адрес следующего элемента стека). Поле адреса последнего элемента стека содержит значение NULL.

Очередью FIFO (FirstIn - FirstOut – «первым пришел - первым исключается») называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (называемой концом или хвостом очереди), а исключение - с другой стороны (начало или голова очереди). Очереди к прилавкам и к кассам являются типичным бытовым примером очереди FIFO.

Программная реализация очереди

Программно очередь можно реализовать тремя основными способами:

1) на базе массива. При этом способе количество элементов ограничено размером массива. Начало очереди соответствует элементу массива с индексом 0, а конец очереди – значению массива с индексом равному <количество элементов в очереди – 1>.

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

3) на базе связного списка. Способ аналогичен представлению стека на базе связного списка. Начало очереди соответствует первому элементу связного списка, конец очереди – последнему элементу списка (возможно и представление наоборот: конец очереди соответствует началу списка, а начало очереди – концу списка).