Линейный массив Структурированные типы данных

Содержание Определение массива, обработка элементов массива Определение массива, обработка элементов массива Заполнение массива с помощью датчика случайных чисел Заполнение массива с помощью датчика случайных чисел Нахождение максимального (минимального) элемента массива Нахождение максимального (минимального) элемента массива Вставка и удаление элементов массива Сортировка элементов массива

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

Основные определения Массив объединяет элементы одного типа данных. Массив обозначается одним именем с индексом. Все элементы массива в памяти располосены в соседних ячейках упорядочены по значениям индекса. Индекс заключается в квадратные скобки. Если в программе имеется массив, то он должен быть описан в разделе переменных VAR либо в разделе типов TYPE. Массивы бывают одномерные и многомерные.

Одномерные массивы Если для доступа к элементу массива достаточно одной переменной, то такой массив называется одномерным. В одномерном массиве все данные располосены в одной строке (или столбце) X – имя массива Значения элементов массива Номера элементов массива

ФОРМАТ ОПИСАНИЯ МАССИВА В РАЗДЕЛЕ ПЕРЕМЕННЫХ VAR_ имя массива :ARRAY[Нач. индекс.. Кон. индекс]OF тип данных; где ARRAY (массив) OF(из)- служебные слова. При объявлении массива необходимо определить, каким образом ( в каких пределах) производится нумерация элементов массива, указав начальнее и конечнее значение индекса. Таким образом, мы задаем размер массива.

Примеры описания массивов VAR Matrix:ARRAY[1..5]OF REAL; VAR Index:ARRAY[2..7]OF INTEGER; В первом примере объявлена переменная-массив состоящая из 5 элементов типа REAL, доступ к которым осуществляется с помощью индекса, значение которого лежит в интервале от 1 до 5. Во втором примере объявлен массив по имени Index, содержащий 6 элементов, типа Integer. Индекс этого массива может изменятся от 2 до 7. Если несколько массивов имеют одинаковый размер и тип элементов, то допускается в описании объединять массивы в список, например: VAR A, B, C: ARRAY[1..50] OF REAL; Здесь объявлено 3 массива А, В, С, каждый из которых содержит по 50 элементов вещественного типа.

Действия над элементами массива. Массив не может обрабатываться целиком, но возможно получить доступ к каждому элементу массива, указав значение индекса в квадратных скобках. Например, Index[2]:=34; Наряду с константой, в качестве индекса может использоваться переменная. Например, с помощью фрагмента программы FOR i:=2 TO 7 DO Index[i]:=0;, всем элементам массива присваивается значение 0. Над элементами массива можно производить те же действия, что и над данными базового типа. Для ввода и вывода элементов массива тоже используется цикл с параметром: FOR i:=2 TO 7 DO READ(Index[i]); FOR i:=2 to 7 DO WRITE(Index[i], );

Пример: Найти сумму элементов линейного массива, состоящего из 15 элементов. Program SUM1; VAR X: ARRAY[1..15] OF INTEGER; SUM,I : INTEGER; BEGIN FOR I:=1 TO 15 DO READ(X[I]);{цикл ввода массива} SUM:=0; FOR I:=1 TO 15 DO SUM:=SUM+X[I];{цикл обработки элементов массива} WRITELN(SUM) END.

Практическее задание: Дана таблица, состоящая из 10 элементов : 1. Вычислить сумму полосительных элементов таблицы. 2. Вычислить количество элементов таблицы равных Найти номер первого элемента таблицы, равного Возвести в квадрат все отрицатьельные элементы таблицы 5. Вычислить произведение элементов таблицы, которые больше 1 и обнулить остальные. 6. Возвести в квадрат отрицать. элем. таблицы, извлечь корень из полосительных, вычислить число элементов равных Увеличить на 1 все элементы таблицы = 5 или 4 и заменить остальные их суммой со след. элементом таблицы, оставляя последний без изменений. 8. Увеличить в два раза те элементы, которые больше 3,вычислить их количество и заменить остальные числом Вычислить количество полос. элементов и уменьшить отриц. на Заменить на 1 все элементы таблицы, которые меньше 1, уменьшить на 7, которые больше 7 и заменить остальные на 5.

Заполнение массива с помощью датчика случайных чисел Для включения датчика случайных чисел служит команда RANDOMIZE; Чтобы присвоить переменной случайнее число используется команда RANDOM(n); которее формирует целее полосительнее число в диапазоне от 0 до n-1

Примеры заполнения линейных массивов случайными числами: 1. Заполнить линейный массив из 15 элементов случайным образом целыми числами в диапазоне от 0 до 50. Program chisla1; Var x:array[1..15] of integer; I: integer; Begin Randomize; For i:=1 to 15 do begin X[i]:=random(51); Write (x[i], ) end; End.

Заполнить линейный массив из 15 элементов случайным образом целыми числами в диапазоне от –50 до +50 Program chisla2; Var x:array[1..15] of integer; I: integer; Begin Randomize; For i:=1 to 15 do begin X[i]:=random(100)-50; {(2*d) - d} Write (x[i], ) end; End.

Заполнить линейный массив из 15 элементов случайным образом вещественными числами в диапазоне от 43 до 44. Program chisla2; Var x:array[1..15] of real; I: integer; Begin Randomize; For i:=1 to 15 do begin X[i]:=random+43; {random без параметров генерирует вещественнее число в диапазоне от 0 до 1} Write (x[i]:4:2, ) end; End.

Задания для самостоятельной работы: Заполнить массив из 10 элементов следующим образом: 1. целыми числами от 40 до вещественными числами от 11 до целыми числами от -25 до вещественными числами от 0 до 20. В массиве хранится информация о количестве осадков в каждый день января(миллиметры). Определить количество дней, в которые выпало осадков больше, чем в среднем за месяц. В массиве хранятся сведения об оценках 25 учеников по информатике. Определить количество неуспевающих учащихся.

НАХОЖДЕНИЕ МАКСИМАЛЬНОГО И МИНИМАЛЬНОГО ЭЛЕМЕНТА При поиске MAX или MIN элементов массива используется приём при котором до входа в цикл какой-то переменной М присваивается значение первого элемента таблицы. А затем в цикле каждый элемент сравнивается с этим значением М. Если очереднее значение элемента массива больше (меньше) М, то переменной М присваивается новее значение. Результат находится в переменной М после конца цикла. При выполнении тела цикла рационально начальнее значение переменной цикла присваивать равным 2, т.к. первый элемент рассматривается до входа в цикл.

ГРАФИЧЕСКАЯ СХЕМА М:= Х[1] i:=2 i<=N Вывод М x[i]>M M:=x[i] K:=i i:=i+1 Номер максимально го элемента

program maximum; var X: array[1..10] of integer; n,i,m: integer; Begin Randomize; For i:=1 to 10 do begin X[i]:=random(51); Write (x[i], ) end; m:=x[1]; n:=0;{ n- For i:=2 To 10 Do If x[i]>m Then begin m:= x[i]; n:=i end; Writeln( Максимальный элемент, М,номер, N); end. Блок заполнения массива при помощи датчика случайных чисел

ПРАКТИЧЕСКОЕ ЗАДАНИЕ: 1. Найти минимальный элемент таблицы, состоящей из 15 элементов. 2. Найти номер минимального элемента таблицы, состоящей из 12 элементов. 3. Найти максимальный элемент таблицы, состоящей их 10 элементов, и поставить его на место первого элемента. 4. Найти минимальный элемент таблицы, найти максимальный элемент таблицы и поставить минимальный на место первого, а максимальный на место последнего. 5. Заменить максимальный элемент его номером. 6. Заменить максимальный элемент произведением максимального элемента на минимальный элемент. 7. Разделить все элементы массива на минимальный и результат поместить в исходный массив. 8 Умножить все элементы массива на максимальный и результат помесить в исходный массив. 9. Найти минимальный элемент таблицы, найти максимальный элемент таблицы и поменять их местами.

Вопросы для повторения: 1. Определение массива, описание массива в разделе переменных; 2. Обработка элементов массива, ввод и вывод элементов массива; 3. Заполнение массива при помощи датчика случайных чисел (целыми числами); 4. Заполнение массива при помощи датчика случайных чисел (полосительными и отрицатьельными, вещественными числами); 5. Нахождение максимального элемента(минимального) элемента; 6. Нахождение номера максимального элемента(минимального) элемента 7. Вставка элементов массива.

Вставка элемента массива Задача: Вставить на 7-ее место массива целых чисел элемент равный 25. Program ins; Uses crt; var a:array[1..21] of integer; i,d,n,k:integer; Begin clrscr; Randomize; for i:=1 to 20 do begin a[i]:=random(100); write(a[i],' '); end; writeln; for i:=21 downto 7 do a[i]:=a[i-1]; a[7]:=25; writeln; for i:=1 to 21 do write( a[i],' '); writeln; end.

Удаление элемента массива Пусть дан массив целых чисел, состоящий из 10 элементов Необходимо удалить элемент под номером

Удаление элементов массива Задача: В линейном массиве, содержащем 20 элементов, удалить k-элемент массива. Program del; Uses crt; var a:array[1..20] of integer; i,d,n,k:integer; Begin Randomize; for i:=1 to 20 do begin a[i]:=random(101); write(a[i],' '); end; writeln; Writeln('Введите номер элемента для удаления '); readln(k); for i:=k to 19 do a[i]:=a[i+1]; writeln; for i:=1 to 19 do write( a[i],' '); writeln; clrscr; end.

ПРАКТИЧЕСКОЕ ЗАДАНИЕ: 1. Вставить на К-ее место элемент, равный минимальному (максимальному). 2. В линейный массив целых чисел на 7-ее место вставить элемент равный квадрату 1-ого. 3. Вставить на К-ее место элемент, равный произведению первого и последнего элемента массива 4. Вставить на К-ее место элемент, равный среднему арифметическому элементов массива. 5. Вставить на К-ее место элемент, равный сумме первых 10 элементов массива. 6. Удалить максимальный элемент массива (минимальный). 7. Удалить элемент массива, удаляющий следующему условию: остаток от деления на 2 равен 5, если таких элементов нет, выдать соответствующее сообщение. 8. Удалить элемент массива, больший заданного числа, если таких элементов нет, выдать соответствующее сообщение

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

Пример: Шаг Шаг Шаг Шаг Шаг Шаг Шаг Шаг Шаг Итог:

Сортировка методом простого обмена. Может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива сверху вниз ( от начала к концу) и обмене местами соседних элементов, располосенных неправильно т.е. таких, что a[i]>a[i+1]. Этот метод также называют методом пузырька ( более лёгкие элементы всплывают на поверхность)

Пример: Отсортируем по возрастанию методом простого обмена массив из 5 элементов Первый просмотр: i=1 5> меняем i=2 4 5 < не меняем i= > 2 9 меняем i= < 9 не меняем 9 стоит на своём месте. Второй просмотр: рассматриваем часть массива с первого до четвёртого элемента: i=1 4<5 2 8 | 9 не меняем i=2 4 5> 2 8 | 9 меняем i= < 8 | 9 не меняем 8 на своём месте.

Третий просмотр: рассматриваем часть массива с 1 по 3 элемент. i=1 4>2 5 | 8 9 меняем i=22 4 < 5 | 8 9 не меняем 5 стоит на своём месте. Четвёртый просмотр: рассматриваем последнюю пару. i=12< 4 | не меняем 4 стоит на своём месте. Для самого маленького элемента остаётся только первее место.

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