Типы данных делятся на две группы: простые и составные, состоящие из элементов простых типов. Простые типы данных Целые (целочисленные). Набор целых чисел. В памяти для переменной этого типа обычно выделяется 2 байта. Принимают значения из промежутка от до Вещественные. Набор чисел состоящих из целой и дробной части, разделённых десятичной точкой. В памяти выделяется 4 или 6 байт, количество цифр после запятой до Принимают значения из промежутка (по модулю) от 2.9E-39 до 1.7E+38. Символьные. Набор символов алфавита ЯП. В качестве своего значения могут иметь один символ. В памяти для переменной этого типа выделяется 1 байт. Логические. Флаг или переключатель. В памяти для переменной этого типа выделяется 1 байт. Принимают только два значения: True (Истинно) и False (Ложно). Составные типы данных называют структурами данных – это некоторым образом организованная совокупность данных, состоящая из данных простых типов или других структур данных. Структуры данных это: Массивы – фиксированный набор элементов одного и того же типа, Строки – линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом, Записи – набор элементов (полей данных), характеризующихся различными типами данных, Файлы – набор записей на внешнем носителе данных. Подробнее составные типы данных рассматриваются позже, при рассмотрении типовых алгоритмов работы с ними. 1 Данные в программах и алгоритмах ТОИ-ИМ

Основные типы данных Некоторые простые типы Integer Integer - Целые принимают значения из промежутка от до В памяти для переменной этого типа выделяется 2 байта Real Real - Вещественные принимают значения из промежутка (по модулю) от 2.9E-39 до 1.7E+38. В памяти выделяется 6 байт, количество цифр после запятой до Boolean Boolean - Логические принимают только два значения: True (истина) и False (ложь. Char Char – Литерные (символьные) в качестве своего значения могут иметь один символ. В памяти для переменной этого типа выделяется 1 байт Некоторые стандартные типы данных int int – целые в памяти занимает 2 байта (на 16- и 32- битовых ЭВМ) short short - короткие целые в памяти 2 байта, диапазон значений от до long long - длинные целые 4 байта, диапазон от до float float - вещественные 4 байта, диапазон приблизительно от 3.4E-38 до 3.4E+38. double double – вещественные с удвоенной точностью 8 байт, диапазон приблизительно от 1.7Е-308 до 1.7Е+308. char char - символьные 1 байт, от -128 до 127 PascalC 2 ТОИ-ИМ

Элементы ЯПВУ Pascal Пользовательские типы данных (определяемые программистом) Pascal – строго типизированный язык, все переменные в программах должны иметь явно объявленный тип данных. Для типов данных, вводимых пользователем в Pascal используется ключевое слово Type объявляющее раздел описания типов данных. Этот раздел размещается до начала программы Pascal вместе с разделами Const и Var. Синтаксис объявления типа данных: Type = ; … Var : ; Примеры: Type Group = (Ivanov, Fedorov, Petrov); Var pie99, kl : group; fas : group; Можно задавать тип данных непосредственно при описании переменной, но при этом тип не будет иметь имени Var : ; Примеры: Var pie99, kl : (Ivanov, Fedorov, Petrov); 3 ТОИ-ИМ

Элементы ЯПВУ Типы данных, определяемые программистом Перечисляемые типы данных Перечисляемый тип данных – ограниченная упорядоченная последовательность (список) скалярных констант. Значение каждой константы задаётся её именем. Перечисляемый тип задаётся в блоке TYPE: Type = (список_имён_констант); Пример: Type Raduga = (красный, оранжевый, жёлтый, зелёный, голубой, синий, фиолетовый); Direction = (North, South, West, East); Перечисляемый тип относится к порядковым типам данных, это означает, что каждая константа в списке имеет порядковый номер и к ним могут применяться функции получения номера предыдущего и последующего значения и аналогичные. В операциях ввода-вывода использовать перечисляемый тип – нельзя. Имена констант в пределах области их видимости (подпрограмма, программа) должны быть уникальными, т.е. в одной подпрограмме два перечисляемых типа не могут иметь одинаковые константы. 4 Pascal ТОИ-ИМ

Элементы ЯПВУ Типы данных, определяемые программистом Перечисляемые типы данных Пример: просуммировать зарплату за год Program interval; var s, k : real; m : (jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec); Begin s:=0; for m:=jan to dec do begin writeln ('Введите зарплату за ', ord(m)+1:3, '-й месяц'); readln (k); S := s + k; end; write )'s = ', s:6:1; End. 5 Pascal ТОИ-ИМ

C / С++ Элементы ЯПВУ Перечисления Перечисления (enum) – это набор именованных констант. enum [ ] { } [ ]; где – имя_типа – идентификатор типа объединения (тег),тег – enum – ключевое слово описания перечисления, – список_констант – список целочисленных констант. При отсутствии инициализатора значение первой константы = 0, остальных +1. Формат объявления переменных: enum ; Примеры: enum coin {penni, nickel, dime, quarter, half_dollar, dollar}; enum coin money; а значить можно выполнить: money = dime; if (money == quarter) printf("Денег – четверть доллара"); Оператор printf ("%d %D", penny, dime); выведет на экран 0 и 2. Инициализация: enum coin {penny=2, nickel, dime, quarter=100, half_dollar, dollar}; Значения элементов будут: penny 2 nickel3 dime4 quarter100 half_dollar101 dollar102 Имена перечисляемых констант должны быть уникальными, а значения могут совпадать. При выполнении арифметических операций перечисления преобразуются в целые числа. 6 C / С++ Типы данных, определяемые программистом ТОИ-ИМ

Элементы ЯПВУ Типы данных, определяемые программистом Интервальные типы данных Интервальный тип данных – это отрезок любого стандартного или перечисляемого типа данных, кроме вещественного. Отрезок задаётся диапазоном от минимального до максимального значения констант. Скалярный тип данных, на котором строится отрезок, называется базовым типом. Константы должны быть одного и того же порядкового типа. Type = константа_1.. константа_2; - константа_1 – нижняя граница отрезка должна быть меньше, чем константа_2 – верхняя граница отрезка или равна ей. Примеры: Type m=5..40; year= ; let='a'..'h'; Var p, s, к : m; y : year; L : let; Над переменными интервального типа могут выполняться все операции и к ним применимы все стандартные функции, допустимые для базового типа данных. В Pascal есть две функции для интервальных переменных: High (x) – возвращает верхнюю границу отрезка (интервала), Low (x) – возвращает нижнюю границу интервала данной переменной x. 7 Pascal ТОИ-ИМ

СТРУКТУРЫ ДАННЫХ Структуры данных – составные типы данных – это некоторым образом организованная совокупность данных, состоящая из данных простых типов или других структур данных. Напомним, что данные – это информационные объекты, над которыми выполняются действия (операции) алгоритмов для получения требующего результата. Тип данных определяет объём памяти для хранения данных, диапазон значений данных и допустимые операции (действия) над данными. Структуры данных – это сложные (составные) типы данных. К сложным структурам данных относят статические, полустатические, динамические и файловые структуры данных. Основой для построения Сложных структур данных служат Базовые структуры данных (примитивные, простые структуры). В языках программирования простые структуры описываются простыми (базовыми) типами. К основным базовым типам данных относятся: числовые, логические, символьные. Числовые данные – с помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т.е. счетное число объектов); значение вещественных чисел определяется лишь с некоторой конечной точностью, зависящей от внутримашинного формата вещественного числа и от разрядности процессора ЭВМ. Логические – данные в виде одной из констант false (ложь) или true (истина). Символьные – символы из некоторого предопределенного множества. В большинстве современных ПЭВМ этим множеством является ASCII (American Standard Code for Information Interchange – американский стандартный код для обмена информацией). 8 Основные понятия ТОИ-ИМ

СТРУКТУРЫ ДАННЫХ Статические структуры представляют собой структурированное множество базовых структур; они отличаются отсутствием изменчивости. Массивы – структура данных, которая характеризуется: фиксированным набором элементов одного и того же типа; каждый элемент имеет уникальный набор значений индексов; количество индексов определяют мерность массива, например, три индекса - трехмерный массив, один индекс - одномерный массив или вектор; обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента. Иначе: массив – это вектор, каждый элемент которого скаляр или вектор. Записи – конечное упорядоченное множество полей, характеризующихся различным типом данных (базовыми, статическими и др.). Полустатические структуры данных характеризуются следующими признаками: (1) они имеют переменную длину и простые процедуры ее изменения; (2) изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения. Доступ к элементу может осуществляться по его порядковому номеру, но с некоторыми ограничениями. Строки – это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Их важные свойства: длина, как правило, переменна, хотя алфавит фиксирован; обычно обращение к символам строки идет с какого-нибудь одного конца последовательности, т.е. важна упорядоченность этой последовательности, а не ее индексация; в связи с этим свойством строки часто называют также цепочками; чаще всего целью доступа к строке является не отдельный ее элемент (хотя это тоже не исключается), а некоторая цепочка символов в строке. 9 Основные понятия ТОИ-ИМ

МАССИВЫ МАССИВ – это структура данных, представляющая собой конечную совокупность элементов одного типа, которая определяется одним именем, например Mas. Массив – это внутренняя структура данных алгоритма, т.е. массивы используются только во время выполнения алгоритма, в котором они определены. Во внешнем представлении задачи массивы могут быть (см. рисунки): - Линейной последовательностью значений однотипных элементов -- вектором или одномерной матрицей, - Совокупностью двух векторов – таблицей или двумерной матрицей, - Совокупностью трёх векторов – трёхмерной матрицей, и т.д. 10 Принципы обработки и типовые алгоритмы Количество векторов в массиве называется измерением массива, количество элементов в измерении называется размерностью данного измерения. Измерение и размерность массива данных фиксируется при создании массива и остаются неизменными при выполнении различных операций над массивами данных. Размерность массива определяет количество элементов массива и вычисляется как произведение размерностей всех измерений массива. Размерность измерения массива задаётся или через именованную константу, или напрямую – числом. ТОИ-ИМ

МАССИВЫ 11 Принципы обработки и типовые алгоритмы Элементы массива располагаются в последовательных ячейках памяти и обозначаются именем массива и индексом. Элементы массива нумеруются от 1 до N (например, в Pascal) или от 0 до N-1 (в С/С++), номер элемента массива называется индексом. Для обозначения отдельных элементов массива используются переменные представленные именем массива с индексом(-ами): М[3], FR[3,6], S[K+1]. Пример: одномерный массив M из пяти элементов, содержащий пять нечётных чисел (ряд арифметической прогрессии с шагом 2): Именование элементов массива через индекс M[1]M[2]M[3]M[4]M[5] Значения элементов массива При обращении к элементам массива необходимо контролировать выход индекса элемента за объявленные границы (размерность) массива и избегать такой ситуации, так это обычно приводит к ошибкам при выполнении алгоритма. ТОИ-ИМ

МАССИВЫ 12 Принципы обработки и типовые алгоритмы Структура данных Массив позволят выполнять операции как со всем массивом в целом, так и с отдельным элементом массива. С отдельными элементами массива можно работать как в режиме последовательного доступа, переходя от элемента с индексом i к элементу с индексом i+1 (или i-1), так и в режиме прямого доступа, обращаясь прямо к элементу с нужным индексом. Последовательная обработка массивов реализуется в цикле (ДЛЯ, ПОКА, ПОВТОРЯТЬ-ПОКА). Элементам массива присваиваются некоторые значения, при этом в общем случае количество элементов массива, которым заданы какие-либо значения, может быть меньше размерности массива. ТОИ-ИМ

МАССИВЫ 13 Инициализация элементов массива Прежде чем выполнять какие либо действия с массивом, необходимо занести начальные данные в элементы массива – такая операция называется инициализацией элементов массива. Начальные значения элементов могут быть заданы как константы или считаны извне (с клавиатуры и из файла). Инициализация массива константами Такая инициализация обычно выполняется в том случае, когда данные массива не планируется изменять. Пример: Массив, хранящий названия месяцев Это двумерный массив символьных элементов – month-mas, его размерностью 12 х 8, 12 – количество месяцев, 8 – максимальное количество символов в названии месяца (сентябрь). Инициализация таблицы месяцев: month-mas[1,1] = 'я' month-mas[1,2] = 'н' month-mas[1,3] = 'в' month-mas[1,4] = 'а' month-mas[1,5] = 'р' month-mas[1,6] = 'ь' month-mas[1,7] = ' ' month-mas[1,8] = ' ' month-mas[2,1] = 'ф' month-mas[2,2] = 'е' month-mas[2,3] = 'в' month-mas[2,4] = 'р' month-mas[2,5] = 'а' month-mas[2,6] = 'л' month-mas[2,7] = 'ь' month-mas[2,8] = ' ' …………………….. month-mas[12,1] = 'д' month-mas[12,2] = 'е' month-mas[12,3] = 'к' month-mas[12,4] = 'а' month-mas[12,5] = 'б' month-mas[12,6] = 'р' month-mas[12,7] = 'ь' month-mas[12,8] = ' ' конец ТОИ-ИМ

МАССИВЫ 14 Инициализация элементов массива Загрузка в массив начальных значений извне Если значения элементов массива в ходе выполнения алгоритма изменяются, то инициализировать их константами нельзя. Начальные значения элементов массива необходимо получить извне – ввести с клавиатуры или прочитать из файла. Стандартный способ ввода начальных значений элементов массива – организовать цикл ПОКА (ПОВТОРЯТЬ-ПОКА) или ДЛЯ, в каждой итерации цикла получить очередное значение и записать его в очередной элемент массива. Инициализируем одномерный массив. Используем переменные: - M – имя массива, - i – индекс массива, - Max – размерность массива. ТОИ-ИМ

МАССИВЫ 15 Алгоритм заполнения массива с клавиатуры: Приращение счётчика итераций цикла – индекса массива (на 1) ИНАЧЕ ТО Конец Вывести "Превышен размер массива" ЕСЛИ i > Max И M[i] ЕСЛИ ВСЁ ЕСЛИ индекс превысил размерность массива и есть допустимое входное значение, ТО выводится сообщение о выходе за границу массива 1 Читать значения элементов в массив Получить M[1] И Л Начало Получить M[i] Установить Max = n i = 1 Задать размерность массива – n и значение индекса i. Вычислить i = i + 1 Цикл выполняется ПОКА есть входные значения И индекс массива не превысил размерность массива M[i] – значение i-того элемента массива M ПОКА ВСЁ 1 ПОКА M[i]И i<=Max ТОИ-ИМ

МАССИВЫ 16 Инициализация элементов массива Загрузка начальных значений в массив непостоянного размера Если требуется массив непостоянного размера (динамический), в котором количество элементов меняется в ходе выполнения алгоритма, то задаётся массив заведомо большего размера, а для маркировки последнего элемента массива используется сигнальная метка (например, 9999). Во время начального ввода элементов массива сигнальная метка укажет конец входных записей (завершение ввода), а во время последующей обработки массива будет указывать последний элемент массива. Если массив содержит символьные элементы, то и сигнальная метка должна быть символьная (например, точка). Если сигнальную метку записывать в последний элемент массива, то по ней можно определять завершение содержательной части массива. Если надо записать в массив заранее известное количество элементов (и оно меньше размера массива), то рационально использовать цикл с параметром ДЛЯ. При заполнении элементов массива данными из файла не требуется использовать сигнальную метку – специальное значение, обозначающее окончание вводимых данных (в приведенном алгоритме – это 9999). Работая с файлом, можно проверять специальный символ окончания файла – eof (end of file). ТОИ-ИМ

МАССИВЫ 17 Алгоритм заполнения массива непостоянного размера: ИНАЧЕ ТО Вывести "Превышен размер массива" ЕСЛИ i <= Max Вычислить M[i] = Конец ЕСЛИ ВСЁ ЕСЛИ индекс не вышел на границу массива, ТО в массив записывается 9999, иначе выводится сообщение о выходе за границу массива Читать значения элементов в массив Получить M[1] И Л Начало Получить M[i] Установить Max = n i = 1 Задать размерность массива – n и значение индекса i. Вычислить i = i + 1 Приращение счётчика итераций цикла – индекса массива (на 1) Цикл выполняется ПОКА входное значение не равно 9999 ИЛИ индекс массива не превысил размерность массива M[i] – значение i-того элемента массива M ПОКА ВСЁ 1 Ввод первого элемента массива М ПОКА M[i] <> 9999 ИЛИ i<=Max ТОИ-ИМ

Элементы ЯПВУ C Массивы ( определяемый программистом составной тип данных ) Pascal МАССИВ – это структура данных, представляющая собой совокупность элементов одного типа, которая определяется одним именем, например M. Для обозначения отдельных элементов массива используются пременные с индексом(-ами) типа М[3], FR[3,6] – в Pascal и FR[3][6] – в С, S[K+1 ]. Объявление массива Type NameM : array [F 1 _Ind..L 1 _Ind [,…F n _Ind..L n _Ind]] of TypeM; где - NameM – имя типа массива, -TypeM – тип элементов массива, - F x _Ind..L x _Ind – начальный и конечный индексы измерения массива ( интервальный тип данных ). Var ID1, ID2 : NameM; где – ID1 и ID2 – идентификаторы объявляемых массивов. TypeM NameM [E1] [[E2]…] = {Init_1}[, {Init_2},…]; где - TypeM – тип элементов массива, - NameM – имя массива, - En – к-во элементов по измерению массива – размерность массива, - Init_n – инициализаторы (нач.значен.) каждого элемента массива. Если инициализаторов меньше, чем элементов, то начальное значение остальных элементов равно Элементы массива нумеруются от 1 до N в Pascal и от 0 до N-1 в С; номер элемента массива называется индексом. ТОИ-ИМ

Элементы ЯПВУ C Массивы Pascal Примеры int d[3] = {3,5}; // d[0]=3, d[1]=5, d[2]=0 float mask[12][5]; int mass[3][2]={{1,1},{0,2},{1,0}}; или int mass[3][2]={1,1,0,2,1,0}; Type MS = array[1..100] of Real; Var t1, Z, De : MS; Можно описывать массивы прямо в разделе Var: Var t1, Z, De : array[1..100] of Real; Описание двумерного массива: n: array [1..12, 1..14] of Integer; или Type а = array [1..6] of integer; b = array [1..12] of a; Var m : b; Размерность массива разумно задавать в виде именованных констант: const int n = 12; int mark[n] = {3,3,4,5,4,4}; Или через директиву препроцессора define: #define SIZE 5 // размерность массива При обращении к элементам массива автоматический контроль выхода индекса за границу массива не производится это может привести к ошибкам. 19 ТОИ-ИМ

ЗАДАНИЕ. Нарисовать блок-схему алгоритма: ввести с клавиатуры одномерный массив из 5 элементов и вывести количество ненулевых элементов в этом массиве. 20 Вывести " Введите 5 элементов массива, после ввода каждого целого числа нажать Enter" Начало Установить SIZE = 5 n = 0 Задать размерность массива SIZE=5 и ко- личество ненулевых элементов n=0. ДЛЯ i=1 ДО i<=SIZE ДЛЯ ВСЁ Л Вывести "a[%i]=",i Получить a[i] a[i] – значение i-того элемента массива a Цикл от первого до последнего элемента массива И ИНАЧЕ Вычислить n = n + 1 ЕСЛИ ВСЁ Если введённый a[i] не равен 0, то увеличиваем счётчик на 1 ТО ЕСЛИ a[i] <> 0 Вывести " В массива n ненулевых элементов" Конец МАССИВЫ ТОИ-ИМ

Элементы ЯПВУ C Массивы Pascal ЗАДАНИЕ: ввести с клавиатуры одномерный массив из 5 элементов и вывести количество ненулевых элементов в этом массиве. Program MASSIV; Const SIZE = 5; (* Размер массива *) Var a:arry[1..Size] of integer; n: integer; i: integer; Begin WriteLn(' Введите 5 элементов массива '); Write(' После ввода числа '); WriteLn(' нажимайте Enter '); n:=0; For i:=1 To SIZE do Begin Write('a[',i,'] -> '); ReadLn(a[i]); If a[i] <> 0 Then n:=n+1; End; WriteLn(' В массиве ',n,' ненулевых элемента. '); ReadLn; End. #include #define SIZE 5 // размер массива void main () { int a[SIZE]; // массив int n = 0, i; // ненулевые элементы, индекс printf("\n Введите элементы массива \n"); Printf (" После ввода числа – Enter \n"); for (i=0; i<SIZE; i++) { printf("a[i] ->", i); scanf("%i",&a[i]); if (a[i] != 0) n++; } printf(" В массиве %i ненулевых элемента \n", n); } 21 ТОИ-ИМ

МАССИВЫ 22 Двумерные массивы Когда для решения задач не хватает вектора – одномерного массива, тогда возникает необходимость увеличить количество измерений массива. Рассмотрим некоторые особенности работы с двумерными массивами. Двухмерный массив – это фактически массив одномерных массивов. Объявление двухмерного массива d, состоящего из 10 строк и 20 столбцов: int d[10][20]; – в ЯП С/С++ и d: array [1..10, 1..20] of Integer; – в ЯП Pascal. Осторожно! В Pascal размерности векторов массива отделяются запятыми, в C/C++ размерность каждого вектора массива заключена в квадратные скобки. Двумерный массив хранится в виде матрицы, в которой первый индекс задает номер строки, а второй – номер столбца. Принято, что при обходе элементов в порядке их размещения в памяти правый (второй) индекс изменяется быстрее, чем левый. Графическая схема размещения двухмерного массива int Mas[4][3] в памяти: Правый (второй) индекс нумерует столбцы Левый (первый) индекс нумерует строки Mas [0] [0]Mas [0] [1]Mas [0] [2] Mas [1] [0]Mas [1] [1]Mas [1] [2] Mas [2] [0]Mas [2] [1]Mas [2] [2] Mas [3] [0]Mas [3] [1]Mas [3] [2] ТОИ-ИМ

МАССИВЫ 23 Алгоритм заполнения двумерного массива с клавиатуры: Загрузка начальных значений в массив с клавиатуры реализуется обычно с использованием циклов (ДЛЯ, ПОКА, ПОВТОРЯТЬ-ПОКА) начиная с первого элемента до конца массива. Первый индекс (i) определяет номер строки, второй индекс (j) – номер столбца. Max_i – количество строк массива, Max_j – количество столбцов. Для смещения по каждому индексу массива выделяется отдельный цикл. Циклы вложены один в другой. Внешний цикл (по индексу - i) смещается по строкам (выбирает строку) и передает управление внутреннему циклу. Внутренний цикл (по индексу - j) смещается по столбцам – выбира- ет в текущей строке ячейку, соответствующую столбцу массива (таблицы). Затем управление возвращается внешнему циклу, происходит переход к следующей строке массива. И так пока не заполниться весь массив. Цикл выполняется от начала до конца столбца массива Цикл выполняется от начала до конца строки массива Читать значения элементов в двумерный массив Начало Получить M[i][j] Установить Max_i = n Max_j = m Задать размерность двумерного массива – n строк и m столбцов. M[i][j] – значение элемента массива M ДЛЯ ВСЁ Конец И Л И Л ДЛЯ ВСЁ ДЛЯ i=1 ДО i<= Max_i ДЛЯ j = 1 ДО Max_j ТОИ-ИМ

24 Двумерные массивы. Загрузка содержимого массива с клавиатуры и вывод его на экран // Заполнение двумерного массива #include // Количество строк массива #define SIZE_i 5 // Количество столбцов массива #define SIZE_j 5 void main () { int a[SIZE_i][SIZE_j]; // Двумерный массив int i, j; // индексы массива printf("\n Введите элементы массива\n"); см. продолжение Продолжение // Ввод элементов массива с клавиатуры printf("После ввода числа - Enter\n"); for (i=0; i<SIZE_i; i++) for (j=0; j<SIZE_j; j++) { printf ("a[%d][%i] = ",i,j); scanf ("%i",&a[i][j]); } // Вывод массива на экран for (i=0; i<SIZE_i; i++) // { for (j=0; j<SIZE_j; j++) printf("%4d \n",a[i][j]); // } } Элементы ЯПВУ C / С++ Массивы ТОИ-ИМ