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

• Название: 2лекция Статические структуры данных
• Анкор: Статистические структуры данных
• Дата: 13.12.2021
• Размер: 0.79 Mb.
• Имя файла: 002-SDA.ppt
• Тип: Лекция; #302251

2-лекция: Статические структуры данных

План:
Основные понятия о статических структурах данных и их виды
Фундаментальные(базовые) ССД и операции над ними
Сложные (структурированные) ССД и операции над ними


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

Базовые структуры данных

К стандартным относят 6 типов:
пустой (VOID)
Числовые типы
а) целый (INT);
б) вещественный (FLOAT) ;
Логический (BOOL);
Символьный (CHAR);
Указательный (POINTER).
 К пользовательским относят 4 типа:
перечисляемый (ENUM); диапазонный(битовый) (INTERVAL)
приведенный (TYPEDEF) препроцессоры (DEFINE)
Структурированные типы в языках программирования являются теми средствами интеграции, которые позволяют строить структуры данных сколь угодно большой сложности. К таким типам относятся: множества (этот тип реализован не во всех языках), массивы, записи (в некоторых языках - структуры) и таблицы.

Числовые типы

Числовые типы в языках программирования используются в следующих формах:
Целые типы
Вещественные типы
Целый тип включает некоторое подмножество целых, размер которого варьируется от машины к машине. Если для представления целых чисел в машине используется n разрядов, причем используется дополнительный код, то допустимые числа должны удовлетворять условию
-2 n-1<= x< 2 n-1.
Числа делятся на знаковые и беззнаковые. Для каждого из них имеется свой диапазон значений:
a)(0..2n-1) для беззнаковых чисел
b) (-2N-1.. 2N-1-1) для знаковых.

Числовые типы

С помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т.е. счетное число объектов).
Синтаксис объявления переменных целого типа:
[signed | unsigned] short | long | int ;
Специфические операции над числовыми типами - хорошо известные всем арифметические операции: сложение(+), вычитание(-), умножение(*), деление нацело(/), остаток от деления(%), инкремент(++), декремент(--), операция возведения в степень(pow), округление (ceil), отброс дробной части(floor).
Еще одна группа операций над числовыми типами - операции сравнения: "равно“(==), "не равно“(!=), "больше“(>), "меньше“(<) и т.п.
x=y=5;
z = ++x + y++; //x-? y-? z-?

Числовые типы

Вещественные типы
Вещественные типы образуют ряд подмножеств вещественных чисел, которые представлены в машинных форматах с плавающей точкой. Числа в формате с плавающей точкой характеризуются целочисленными значениями мантиссы и порядка, которые определяют диапазон изменения и количество верных знаков в представлении чисел вещественного типа.
X = +/- M * q(+/-P) - полулогарифмическая форма представления числа
937,56 = 93756 * 10-2 = 0,93756 * 103

Числовые типы

Синтаксис объявления переменных вещественного типа:
float | [long ] double ;
Специфические операции над вещественными числами - арифметические операции: сложение(+), вычитание(-), умножение(*), деление(/), нахождение корня(sqrt), логарифмы чисел(log);
тригонометрические операции: синус, косинус, тангенс; операции сравнения: "больше“(>), "меньше“(<) и т.п.
X=12,54;
Y=floor(X);
Z=ceil(X);
//y-? z-?

Символьный тип

Значением символьного типа являются символы из некоторого предопределенного множества. В большинстве современных персональных компьютерах этим множеством является ASCII (American Standard Code for Information Intechange - американский стандартный код для обмена информацией). Значение символьного типа занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы. ASCII, однако, не является единственно возможным множеством. Другим достаточно широко используемым множеством является код EBCDIC (Extended Binary Coded Decimal Interchange Code - расширенный двоично-кодированный десятичный код обмена), применяемый в системах IBM средней и большой мощности.

Символьный тип

Синтаксис объявления переменных символьного типа:
char | wchar_t ;
Символьные данные задаются в одинарных кавычках (апострофах) ‘ ’ или целым числом (кодом символа)
Специфические операции над символьными типами - только операции сравнения. При сравнении коды символов рассматриваются как целые числа без знака. Кодовые таблицы строятся так, что результаты сравнения подчиняются лексикографическим правилам: символы, занимающие в алфавите места с меньшими номерами, имеют меньшие коды, чем символы, занимающие места с большими номерами.

Логический тип

Значениями логического типа может быть одна из предварительно объявленных констант false (ложь) или true (истина).
Данные логического типа занимают один байт памяти. При этом значению false соответствует нулевое значение байта, а значению true соответствует любое ненулевое значение байта.
Над логическими типами возможны операции булевой алгебры - НЕ (not), ИЛИ (or), И (and).

Битовый тип

В ряде задач может потребоваться работа с отдельными двоичными разрядами данных. Данные такого типа представляются в виде набора битов, упакованных в байты или слова, и не связанных друг с другом. Операции над такими данными обеспечивают доступ к выбранному биту данного. Над этими типами помимо операций, характерных для числовых типов, допускаются и побитовые операции.
Над битовыми типами возможны три группы специфических операций: разрядные операции, операции сдвигов, операции сравнения.
Разрядные операции. К разрядным операциям относятся |(дизъюнкция), & (конъюнкция), ^(XOR, исключающая ИЛИ), !(отрицание). Например 5 в двоичной системе равен 101 а 6 равен 110:
6&5= 4=100; 6|5= 7= 111; 6^5=3=011; 6=4=010.
Сдвиг влево <<. Например: 5<<2=20 или 101<<2=10100.
Сдвиг вправо >>. Например 5>>2=1 или 101>>2=001=1.

Перечислимый тип

Перечислимый тип представляет собой упорядоченный тип данных, определяемый программистом, т.е. программист перечисляет все значения, которые может принимать. В памяти перечислимый тип представляется целочисленным типом.
Синтаксис объявления типа:
enum T (c1, c2, c3, …, cn)
Например
enum VrGoda (“зима”, “весна”, “лето”, “осень”);
VrGoda A;

Указатели

Указатель это переменная, хранящая уникальный номер ячейки памяти. Указатель определяет некоторое место в оперативной памяти, в котором может находиться какая либо переменная.
Указатель обычно является типизированным и объявляется следующим способом:
<имя типа> * <имя указателя> = <начальное значение>;
Основными специфическими операциями, в которых участвуют указатели, являются получение адреса(&), операции адресной арифметики(+,-,++,--) и выборка([]), new , delete.
int a = 5;
int * p = &a;

Директивы препроцессора

Директивы препроцессора - управляют преобразованием текста программы до ее компиляции.
Новый тип. Спецификатор Typedef позволяет вводить новые типы.
пример:
Typedef unsigned char COD;
COD simbol;
Замена. Спецификатор #define - указывает правила замены в тексте.
#define PI 3.14

Структурированные ССД. Множества и операции над множествами

Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений.
Множество в памяти хранится как массив битов, в котором каждый бит указывает, является ли элемент принадлежащим объявленному множеству или нет.
Допустим у нас множество A состоит из интервала от 1 до 10. И в нем находится {2;4;7}. В памяти оно будет выглядеть следующим обраазом:

0

1

0

1

0

0

1

0

0

0

Над множествами определены следующие специфические операции.
1) Объединение множеств: S2+S3. Результатом является множество, содержащее элементы обоих исходных множеств.
2) Пересечение множеств: S2*S3. Результатом является множество, содержащее общие элементы обоих исходных множеств.
3) Проверка на вхождение элемента в множество: a in S1. Результатом этой операции является значение логического типа - true, если элемент a входит в множество S1, false - в противном случае.

Массивы и их обработка

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

Массивы и их обработка

Синтаксис описания массивов в языке С++
<Тип элемента> <Имя> [<Размер>]
Пример: int a[]={2, 3, 4, 5} или int a[4]
Важнейшая операция физического уровня над массивом - доступ к заданному элементу. Как только реализован доступ к элементу, над ним может быть выполнена любая операция, имеющая смысл для того типа данных, которому соответствует элемент. Преобразование логической структуры в физическую, в ходе которого многомерная логическая структура массива преобразуется в одномерную физическую структуру, называется процессом линеаризации.

Записи (структуры)

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

Синтаксис объявления структуры в С++

struct BirthDay
{
int day;
int month;
long year;
} a,b;
Полем записи может быть в свою очередь интегрированная структура данных - вектор, массив или другая запись. Полем записи может быть другая запись, но ни в коем случае не такая же.
Важнейшей операцией для записи является операция доступа к выбранному полю записи - операция квалификации. Практически во всех языках программирования обозначение этой операции имеет вид:
<имя переменной-записи>.<имя поля>


Операции над записями:
Прочтение содержимого поля записи.
Занесение информации в поле записи.
Все операции, которые разрешаются над полем записи, соответствующего типа.
Над выбранным полем записи возможны любые операции, допустимые для типа этого поля. Большинство языков программирования поддерживает некоторые операции, работающие с записью, как с единым целым, а не с отдельными ее полями. Это операции присваивания одной записи значения другой однотипной записи и сравнения двух однотипных записей на равенство/неравенство. В тех же случаях, когда такие операции не поддерживаются языком явно, они могут выполняться над отдельными полями записей или же записи могут копироваться и сравниваться как неструктурированные области памяти.

Таблицы и операции над ними

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

Таблицы и операции над ними

При задании таблицы указывается количество содержащихся в ней записей
Struct Book
{ char Author[25];
char Name[25];
int pages;
int year;
char Izd[15];
};
Book LibraryA[250];

Author	Name	pages	year	Izd

Таблицы и операции над ними

Элементом данных таблицы является запись. Поэтому операции, которые производятся с таблицей - это операции, производимые с записью.
Операции с таблицами:
1. Поиск записи по заданному ключу.
2. Занесение новой записи в таблицу.
Ключ - это идентификатор записи. Для хранения этого идентификатора отводится специальное поле.
Составной ключ - ключ, содержащий более двух полей.