Одномерные массивы с векторами (7 видео)

Одномерные массивы (векторы)

Лабораторная работа №6. Массивы

Цель и порядок работы

Цель работы – получение практических навыков алгоритмизации и программирования вычислительных процессов с использованием массивов.

Порядок выполнения работы:

— ознакомиться с описанием лабораторной работы;

— получить задание у преподавателя, согласно своему варианту;

— написать программу и отладить ее на ЭВМ;

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

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

Вся совокупность компонент определяется одним именем. Для обозначения отдельных компонент используется конструкция, называемая переменной с индексом или с индексами. Переменная с индексом представляет собой имя массива, вслед за которым в квадратных скобках записывается индекс (или индексы).

Описание массива выглядит следующим образом:

базовый_тип имя_массива [размерность];

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

//одномерный массив целочисленного типа из 5 элементов

//одномерный массив вещественного типа из N элементов (N — константа. )

const int N = 20;

//одномерный массив беззнакового целочисленного типа из 2*M элементов

unsigned int b[2*M];

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

базовый_тип имя_массива [размерность] = ;

Если инициализирующих значений меньше, чем элементов в массиве, остаток массива обнуляется, если больше – лишние значения не используются.

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

int a[3] = ; //a[0] = 1, a[1] = 2, a[2] = 3

// недостающие значения инициализации заполняются нулями

int b[5] = ; //b[0] = 1, b[1] = 2, b[2] = 3, b[3] = 0, b[4] = 0

// лишние значения (4 и 5) не используются

int с[3] = ; //c[0] = 1, c[1] = 2, c[2] = 3

//индекс может быть опущен и размер вычисляется

// по количеству элементов инициализации

int d[] = ; //c[0] = 0, c[1] = 2, c[2] = 4 (размер 3)

//строка так же является массивом символов,

//оканчивающимся нуль-символом (управляющей последовательностью )

char s[] = Hi!; //s[0]=’H’, s[1]=’i’, s[2]=’!’, s[3]=’′ (размер 4)

Для доступа к элементу массива после его имени указывается номер элемента (индекс), в квадратных скобках:

Элемент массива считается переменной: он может получать значения (например, в операторе присваивания), а также участвовать в выражениях.

Например, для объявленных выше массивов обращения и использование будет выглядеть следующим образом:

//обращения к элементам массива

Рассмотрим пример нахождения суммы элементов массива.

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

using namespace std;

Результат работы программы:

Задача: найти сумму элементов массива, ее и сам массив на экран. Элементы массива ввести с клавиатуры.

using namespace std;

//определим размер массива

const int N = 10;

//введем элементы массива с клавиатуры

for (int i = 0; iN; i++)

//объявим переменную для хранения суммы элементов

//просуммируем элементы массива

for (int i = 0; iN; i++)

//выведем на экран элементы массива и их сумму

for (int i = 0; iN; i++)

Часто возникает ситуация, когда количество элементов массива может варьироваться на этапе компиляции. При этом пересчет количества элементов вручную приводит к потере времени. C++ позволяет избежать данной проблемы. Для определения размера массива используется следующая конструкция:

Здесь array – имя массива, N – полученный размер массива, sizeof(array) возвращает размер всего массива в батах, а sizeof(array[0]) – размер первого элемента в байтах (естественно совпадающий с размером остальных элементов). Таким образом, поделив размер всего массива на размер одного элемента, мы получим количество элементов, т.е. искомый размер массива.

Рассмотрим следующий пример: найти максимальный элемент в массиве.

using namespace std;

//определим размер массива

int n = sizeof(b)/sizeof(b[0]);

//объявим переменную для хранения максимального элемента

//присвоим начальное значение, равное нулевому элементу

//просмотрим все элементы начиная с 1-ого элемента

for (int i = 1; in; i++)

//если i-й элемент будет больше

//текущего максимального значения,

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

//на значение i-го элемента

//выведем на экран элементы массива

for (int i = 0; in; i++)

//и максимальный элемент

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

Для доступа к элементу многомерного массива указываются все его индексы.

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

//одномерный массив (вектор) размерностью 10

//двумерный массив (матрица) размерностью 3×3

//двумерный массив размерностью 6 строк на 8 столбцов

//трехмерный массив размерностью 6x3x2

//шестимерный массив размерностью 6x3x2x5x8x4

//объявление массива с инициализацией

//крайняя левая размерность отсутствует

//объявление массива с инициализацией

//для удобства чтения каждая строка массива находится в отдельной строчке

//объявление массива с инициализацией

//внутренние фигурные скобки могут отсутствовать

int mass3 [3][2] = (1, 1, 0, 2, 3, 0):

//объявление массива с инициализацией

//для удобства чтения каждая строка массива находится на отдельной строчке

Пример: в целочисленной матрице 3×4 определить номера строки и столбца элемента, который равен нулю. Массив задать случайными числами.

using namespace std;

const int N = 3, M = 4;

//заполним массив случайными числами от 0 до 9

//внешний цикл для перемещения по строкам

for (int i = 0; iN; i++)

//внутренний цикл для перемещения по столбцам

for (int j = 0; jM; j++)

//остаток от деления на 10 позволяет

//получить требуемый диапазон значений

//выведем массив на экран

for (int i = 0; iN; i++)

for (int j = 0; jM; j++)

//перейдем на новую строчку

//найдем элементы равные 0 и выведем их индексы на экран

for (int i = 0; iN; i++)

for (int j = 0; jM; j++)

1. Как определить массив?

2. Как проинициализировать массив?

3. Какие варианты объявления с инициализацией вы знаете?

4. Как обратиться к элементу массива?

5. Как объявить многомерный массив?

6. Как проинициализировать многомерный массив?

7. Как определить размер одномерного массива, зная его имя?

1. Написать программу в соответствии с вариантом задания из пункта 5.1.

2. Отладить и протестировать программу.

3. Написать программу в соответствии с вариантом задания из пункта 5.2.

4. Отладить и протестировать программу.

5. Оформить отчёт.

Одномерные массивы (векторы)

1. Дан одномерный массив, состоящий из N целочисленных элементов.

1.1. Ввести массив с клавиатуры.

1.2. Найти максимальный элемент.

1.3. Вычислить среднеарифметическое элементов массива.

1.4. Вывести массив на экран в обратном порядке.

2. Дан одномерный массив, состоящий из N целочисленных элементов.

2.1. Заполнить массив случайными числами.

2.2. Найти минимальный элемент.

2.3. Вычислить сумму элементов массива.

2.4. Вывести положительные элементы на экран.

3. Дан одномерный массив, состоящий из N вещественных элементов.

3.1. Ввести массив с клавиатуры.

3.2. Найти максимальный элемент.

3.3. Вычислить среднеарифметическое положительных элементов массива.

3.4. Вывести отрицательные элементы на экран в обратном порядке.

4. Дан одномерный массив, состоящий из N вещественных элементов.

4.1. Заполнить массив случайными числами.

4.2. Найти минимальный положительный элемент.

4.3. Вычислить произведение не нулевых элементов массива.

4.4. Вывести ненулевые элементы на экран в обратном порядке.

5. Дан одномерный массив, состоящий из N целочисленных элементов.

5.1. Ввести массив с клавиатуры.

5.2. Найти максимальный отрицательный элемент.

5.3. Вычислить сумму отрицательных элементов массива.

5.4. Вывести положительные элементы на экран.

6. Дан одномерный массив, состоящий из N целочисленных элементов.

6.1. Заполнить массив случайными числами.

6.2. Найти максимальный положительный элемент.

6.3. Вычислить сумму элементов массива.

6.4. Вывести ненулевые элементы на экран в обратном порядке.

7. Дан одномерный массив, состоящий из N вещественных элементов.

7.1. Ввести массив с клавиатуры.

7.2. Найти максимальный элемент.

7.3. Вычислить среднеарифметическое отрицательных элементов массива.

7.4. Вывести массив на экран в обратном порядке.

8. Дан одномерный массив, состоящий из N вещественных элементов.

8.1. Заполнить массив случайными числами.

8.2. Найти минимальный элемент.

8.3. Вычислить произведение не нулевых элементов массива.

8.4. Вывести положительные элементы на экран в обратном порядке.

9. Дан одномерный массив, состоящий из N целочисленных элементов.

9.1. Ввести массив с клавиатуры.

9.2. Найти минимальный положительный элемент.

9.3. Вычислить сумму положительных элементов массива, кратных 3.

9.4. Вывести не нулевые элементы на экран.

10. Дан одномерный массив, состоящий из N целочисленных элементов.

10.1. Заполнить массив случайными числами.

10.2. Найти максимальный положительный элемент.

10.3. Вычислить произведение элементов массива.

10.4. Вывести положительные элементы на экран.

11. Дан одномерный массив, состоящий из N вещественных элементов.

11.1. Ввести массив с клавиатуры.

11.2. Найти максимальный элемент.

11.3. Вычислить сумму четных элементов массива.

11.4. Вывести отрицательные элементы на экран в обратном порядке.

12. Дан одномерный массив, состоящий из N вещественных элементов.

12.1. Заполнить массив случайными числами.

12.2. Найти минимальный отрицательный элемент.

12.3. Вычислить среднеарифметическое положительных элементов массива.

12.4. Вывести положительные элементы на экран.

13. Дан одномерный массив, состоящий из N целочисленных элементов.

13.1. Ввести массив с клавиатуры.

13.2. Найти максимальный отрицательный элемент.

13.3. Вычислить произведение отрицательных элементов массива.

13.4. Вывести ненулевые элементы на экран в обратном порядке.

14. Дан одномерный массив, состоящий из N целочисленных элементов.

14.1. Заполнить массив случайными числами.

14.2. Найти максимальный элемент.

14.3. Вычислить среднеарифметическое нечетных элементов массива.

14.4. Вывести отрицательные элементы на экран.

15. Дан одномерный массив, состоящий из N вещественных элементов.

15.1. Ввести массив с клавиатуры.

15.2. Найти минимальный положительный элемент.

15.3. Вычислить сумму четных элементов массива.

15.4. Вывести массив на экран в обратном порядке.

16. Дан одномерный массив, состоящий из N вещественных элементов.

16.1. Заполнить массив случайными числами.

16.2. Найти минимальный отрицательный элемент.

16.3. Вычислить произведение ненулевых элементов массива, кратных 3.

16.4. Вывести отрицательные элементы на экран в обратном порядке.

17. Дан одномерный массив, состоящий из N целочисленных элементов.

17.1. Ввести массив с клавиатуры.

17.2. Найти максимальный отрицательный элемент.

17.3. Вычислить среднеарифметическое четных элементов массива.

17.4. Вывести ненулевые элементы на экран в обратном порядке.

18. Дан одномерный массив, состоящий из N целочисленных элементов.

18.1. Заполнить массив случайными числами.

18.2. Найти минимальный элемент.

18.3. Вычислить сумму положительных нечетных элементов массива.

18.4. Вывести положительные элементы на экран.

19. Дан одномерный массив, состоящий из N вещественных элементов.

19.1. Ввести массив с клавиатуры.

19.2. Найти минимальный положительный элемент.

19.3. Вычислить произведение нечетных элементов массива.

19.4. Вывести отрицательные элементы на экран.

20. Дан одномерный массив, состоящий из N вещественных элементов.

20.1. Заполнить массив случайными числами.

20.2. Найти максимальный элемент.

20.3. Вычислить среднеарифметическое отрицательных элементов массива.

20.4. Вывести положительные элементы на экран в обратном порядке.

21. Дан одномерный массив, состоящий из N целочисленных элементов.

21.1. Ввести массив с клавиатуры.

21.2. Найти максимальный положительный элемент.

21.3. Вычислить сумму положительных четных элементов массива.

21.4. Вывести отрицательные элементы на экран в обратном порядке.

22. Дан одномерный массив, состоящий из N целочисленных элементов.

22.1. Заполнить массив случайными числами.

22.2. Найти минимальный элемент.

22.3. Вычислить произведение ненулевых нечетных элементов массива.

22.4. Вывести массив на экран в обратном порядке.

23. Дан одномерный массив, состоящий из N вещественных элементов.

23.1. Ввести массив с клавиатуры.

23.2. Найти минимальный положительный элемент.

23.3. Вычислить среднеарифметическое положительных элементов массива.

23.4. Вывести ненулевые элементы на экран в обратном порядке.

24. Дан одномерный массив, состоящий из N вещественных элементов.

24.1. Заполнить массив случайными числами.

24.2. Найти максимальный отрицательный элемент.

24.3. Вычислить среднеарифметическое нечетных элементов массива.

24.4. Вывести отрицательные элементы на экран.

25. Дан одномерный массив, состоящий из N целочисленных элементов.

25.1. Ввести массив с клавиатуры.

25.2. Найти минимальный отрицательный элемент.

25.3. Вычислить сумму несчетных отрицательных элементов массива.

25.4. Вывести положительные элементы на экран.

Содержание

Статьи к прочтению:
04 Работа с массивами и матрицами в MATLAB
Похожие статьи:
Одномерные массивы. Вектора
Одномерные массивы с векторами
2.5.1 Векторы
2.5.2 Строки
2.5.3 Битовые векторы
📸 Видео

Статьи к прочтению:

04 Работа с массивами и матрицами в MATLAB

Одномерные массивы. Вектора

Если в описании массива типом элемента является простой тип данных, то такой массив называется вектором. Поскольку в таком массиве для идентификации величины используется только один индекс, то он называется одномерным. Такие одномерные массивы представляют собой простейшие структурированные данные. Обращение к элементам одномерного массива осуществляется с помощью индексированных переменных, например X[i]. Здесь X – имя массива, a i — константа, переменная или выражение того же типа, что и тип индекса в объявлении массива.

Определить частоту появления латинских прописных букв в тексте, вводимом с клавиатуры. Ввод данных завершить символом ‘*’.

Здесь, в качестве индекса удобно использовать ограниченный литерный тип ‘А’ .. ‘Z’, что обеспечивает с одной стороны — мнемонический смысл индекса, соответствующего счетчику частоты появления литеры в тексте, а с другой стороны – легкость перебора значений индекса.

В Паскале нет средств ввода, вывода массива целиком, поэтому эти действия приходится выполнять как циклические процессы над отдельными элементами массива, используя (в частности, в нашем примере) оператор FOR. В этом примере при выводе результатов с помощью форматного вывода реализован перевод целочисленного выражения COUNTER [СН] * 100 / N в вещественную форму числа с фиксированной десятичной точкой.

VAR COUNTER: ARRAY [‘A’.. ‘Z’] OF INTEGER;

FOR СН := ‘А’ ТО ‘Z’ DO COUNTER[CH] := 0;

IF (СН >= ‘A’) AND (СН

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

CONST A: ARRAY [1..10] OF REAL = (0.1, -15.3, 7, 0, -11.89, 4, -78,11.2, 1,0.01);

При таком объявлении массива в разделе констант вы заносите в одномерный массив А по порядку А[1] = 0.1, А[2] = -15.3. А[10] = 0.01 вещественные числа, перечисленные в круглых скобках. При этом массив является массивом переменных, то есть в процессе работы программы можно менять содержимое любого разряда одномерного массива. Этот способ, конечно, является нарушением по стандарту Паскаля, однако очень часто используется на практике.

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

A: ARRAY[M .. N] OF REAL;

где M – нижняя, a N верхняя границы индексов. Первый способ ввода будет иметь инструкцию:

WRITELN(‘Введите массив А, из 15 вещественных чисел’);

FOR I := М ТО N DO READ(A[I]);

При таком способе оператор может ввести все 15 чисел через пробел в одну строку и только затем нажать на клавишу Enter. Если он считает нужным, то он может вводить группы чисел (например, по 3 числа, чтобы не ошибиться) через пробелы и нажимать Enter. А можно вводить на каждой строке только по одному числу.

Второй способ ввода имеет вид:

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

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

FOR I := М ТО N DO А[I] := 0;

Пример 29.

В результате измерения случайного параметра сформирован массив из N вещественных чисел.

Вычислить эмпирическую среднюю и среднее квадратическое отклонение

Обозначим М = и S = σ, тогда алгоритм программы будет иметь вид.

Как мы только что обсуждали, ввод массива — это инструкция, содержащая несколько операторов, в том числе оператор цикла FOR. Но здесь и во всех последующих примерах мы не будем уточнять способ ввода одномерного массива, оставляя выбор за программистом.

X: ARRAY [1.. N] OF REAL;

WRITELN(‘Введите массив X, из’, N:2,’ вещественных чисел’);

FOR I := 1 TO N DO READ(X[I]);

FOR I := 1 TO N DO M := M + X[I];

FOR I := 1 TO N DO S := S + (X[I] — M) * (X[I] — M);

WRITELN(‘M — ‘, M :10:6,’, S = ‘, S :9:6);

Отображение на экране значений одномерного массива

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

VAR A: ARRAY [M .. N] OF REAL;

Тогда первый способ вывода элементов массива в строку будет иметь инструкцию:

WRITELN(‘Элементы массива А имеют значения:’);

FOR I := М ТО N DO WRITE(A[I]: С: D,»);

В этой инструкции первый оператор WRITELN сообщает оператору, какую информацию он увидит на экране. Второй оператор сформирует цепочку вещественных чисел, разделенных пробелами в формате: С: D. Третий оператор WRITELN переведет курсор на новую строку.

Второй способ обеспечивает вывод значений элементов массива в столбец, причем каждый из элементов будет идентифицирован:

FOR I := М ТО N DO WRITELN(‘A[‘, I:2,’] — ‘, А[I]: С: D);

Работа с индексами одномерного массива

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

Пример 30.

Для программирования необходимо линейную формулу U преобразовать к следующему виду:

Нетрудно заметить, что задача сведена к двойному арифметическому циклу.

Для накопления суммы по I используется переменная U, исходное состояние которой равно 0. Для накопления произведения используется рабочая переменная Р, которая рассчитывается шесть раз для значений индекса I=1,2,…,6. Для накопления произведения начальное значение J принимается равным 1.

X: ARRAY [1.. 24] OF REAL;

WRITELN(‘Введите массив X, из 24 вещественных чисел’);

FOR I := 1 ТО 24 DO READ(X[I]);

Нахождение минимального и максимального элементов массива

Одной из наиболее распространенных задач обработки массивов является поиск минимального (максимального) элемента.

В массиве X из 20 вещественных чисел поменять местами наибольшие и наименьшие элементы.

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

Идентификатор	Содержательный смысл	Тип
Х[I]	Элемент с индексом I массива X	REAL
MIN	Значение наименьшего элемента из X	REAL
МАХ	Значение наибольшего элемента из X	REAL

Эту задачу нужно решать с помощью двух последовательных просмотров массива X. Целью первого просмотра является вычисление наибольшего МАХ и наименьшего МIN значений элементов массива X. В начале просмотра значение первого элемента Х[1] считается одновременно наибольшим и наименьшим, что справедливо в том случае, если в массиве всего один элемент. Далее со второго элемента Х[2] и до последнего Х[20] сравниваются значение текущего элемента с MIN. Если значение текущего элемента меньше, то оно с этого момента считается минимальным. По окончании цикла в рабочей ячейке MIN окажется число, равное значению
наименьшего элемента. Аналогично поступаем для нахождения МАХ.

Далее нужно сравнить между собой MIN и МАХ. Если эти величины равны между собой, то массив состоит из 20 равнозначных элементов. Следовательно, переставлять их местами нет необходимости. Если MIN≠МАХ, то нужно наименьшим элементам присвоить значение МАХ, а наибольшим элементам присвоить значение MIN. Эти действия являются основой для второго просмотра массива X.

X: ARRAY [ 1.. 20] OF REAL;

WRITELN(‘Введите массив X, из 20 вещественных чисел’);

FOR I := 1 ТО 20 DO READ(X[I]);

THEN FOR I := 1 TO 20

ELSE IF MIN = X[I]

WRITELN(‘Элементы массива X имеют значения:’);

FOR I := 1 TO 20 DO WRITE(X[I]: 4:1,’ ‘);

3.3. Сортировка одномерного массива

Сортировка — перестановка местами объектов в определенном порядке. Известно несколько сотен алгоритмов сортировки и их модификаций.

Пусть дана последовательность элементов – A₁, А₂, …, А_n. Сортировка означает перестановку этих элементов в новом порядке А_k₁ , А_k₂, …, A_kn. Этот порядок соответствует значениям некоторой функции F, такой, что справедливо отношение F(A_k₁) 2 . Следует отметить, что показатели С и М существенно зависят от первоначальной упорядоченности сортируемого массива. Наиболее тяжелым (Мах) считается случай, когда массив упорядочен в обратном порядке. Ниже мы рассмотрим три наиболее известных способа сортировки одномерного массива. Сравнительные временные характеристики этих способов приведены в следующей таблице:

Способ	Min	Средний	Max
Метод Пузырька	C = (N 2 -N)/2, М = 0	C = (N 2 -N)/2, M = 0.75·(N 2 -N)	C = (N 2 -N)/2, M = 1.5· (N 2 -N)
Простой выбор	C = (N 2 -N)/2, M = 3· (N-1)	C = (N 2 -N)/2, M = N· (Ln(N) + 0.57)	C = (N 2 -N)/2, M = N 2 /4 + 3· (N-l)
Простое включение	C = N-1, M = 2· (N-1)	C = (N 2 +N-2)/4, M = (N 2 -9N-10)/4	C = (N 2 -N)/2-l, M = (N 2 +3N-4)/2

Сортировка простым обменом. Метод пузырька

Методом пузырька упорядочить (отсортировать) в порядке возрастания массив из 8 целых чисел (44, 55, 12, 42, 94, 18, 06, 67).

Концептуальную модель сортировки рассмотрим на примере восьми целых чисел, которые расположим в первом вертикальном столбце. Вертикальное расположение сортируемого массива наглядно иллюстрирует «всплывание легких элементов (чисел) вверх к поверхности» по мере сортировки массива.

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

Индекс элемента массива	Номер прохода сортировки (I)
J=1	44

Элементы всплывают вверх к поверхности в соответствии с их весами, пока не встретят элемент с более малым весом. С каждым проходом наиболее легкий элемент из оставшихся поднимается на свое место, показанное жирными цифрами. Таким образом, нет необходимости на каждом проходе проверять элементы, стоящие выше выделенных, поскольку они уже отсортированы ранее. Начиная с 6 прохода, состояние массива не изменяется, что объясняется начальной упорядоченностью элементов в исходном массиве.

Эта программа предназначена для изучения сортировки методом пузырька, поэтому взят массив из восьми целых чисел. Массив заранее известен, следовательно, инициализировать Х[1. 8] проще всего в разделе констант. Ввод данных с клавиатуры в этой программе не требуется. Алгоритм программы представляет собой двойной вложенный цикл. Индекс I внешнего арифметического цикла соответствует номеру прохода сортировки. Индекс J это номер элемента в массиве. Для перестановки двух соседних элементов X[J-1] и X[J] местами используется промежуточная рабочая ячейка с идентификатором L.

X: ARRAY [1.. 8] OF INTEGER = (44, 55,12,42,94,18,06, 67);

Видео:Что такое массив. Примеры. Теория. Array. Одномерный массив. Синтаксис. C++. Урок #25.Скачать

Одномерные массивы с векторами

Массив (array) является объектом с элементами расположенными в соответствие с декартовой системой координат.

Количество измерений массива называется ранг (это терминология взята из APL). Ранг является неотрицательных целым. Также каждое измерение само по себе является неотрицательным целым. Общее количество элементов в массиве является произведением размеров всех измерений.

Реализация Common Lisp’а может налагать ограничение на ранг массива, но данное ограничение не может быть менее 7. Таким образом, любая Common Lisp программа может использовать массивы с семью и менее измерениями. (Программа может получить текущее ограничение для ранга для используемой системы с помощью константы array-rank-limit.)

Допускается существование нулевого ранга. В этом случае, массив не содержит элементов, и любой доступ к элементам является ошибкой. При этом другие свойства массива использоваться могут. Если ранг равен нулю, тогда массив не имеет измерений, и их произведение приравнивается к 1 (FIXME). Таким образом массив с нулевым рангом содержит один элемент.

Элемент массива задаётся последовательностью индексов. Длина данной последовательности должна равняется рангу массива. Каждый индекс должен быть неотрицательным целым строго меньшим размеру соответствующего измерения. Также индексация массива начинается с нуля, а не с единицы, как в по умолчанию Fortran’е.

В качестве примера, предположим, что переменная foo обозначает двумерный массив с размерами измерений 3 и 5. Первый индекс может быть 0, 1 или 2, и второй индекс может быть 0, 1, 2, 3 или 4. Обращение к элементам массива может быть осуществлено с помощью функции aref, например, (aref foo 2 1) ссылается на элемент массива (2, 1). Следует отметить, что aref принимает переменное число аргументов: массив, и столько индексов, сколько измерений у массива. Массив с нулевым рангом не имеет измерений, и в таком случае aref принимает только один параметр – массив, и не принимает индексы, и возвращает одиночный элемент массива.

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

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

Массив, что не указывает на другой массив, не имеет указателя заполнения и не имеет динамически расширяемого размера после создания называется простым массивом. Пользователи могут декларировать то, что конкретный массив будет простым. Некоторые реализации могут обрабатывать простые массивы более эффективным способом, например, простые массивы могут храниться более компактно, чем непростые.

Когда вызывается make-array, если один или более из :adjustable, :ﬁll-pointer и :displaced-to аргументов равен истине, тогда является ли результат простым массивом не определено. Однако если все три аргумента равны лжи, тогда результат гарантированно будет простым массивом.

2.5.1 Векторы

В Common Lisp’е одномерные массивы называется векторами, и составляют тип vector (который в свою очередь является подтипом array). Вектора и списки вместе являются последовательностями. Они отличаются тем, что любой элемент одномерного массива может быть получен за константное время, тогда как среднее время доступа к компоненту для списка линейно зависит от длины списка, с другой стороны, добавление нового элемента в начала списка занимает константное время, тогда как эта же операция для массива занимает время линейно зависящее от длины массива.

Обычный вектор (одномерный массив, который может содержать любой тип объектов, но не имеющий дополнительных атрибутов) может быть записан с помощью перечисления элементов разделённых пробелом и окружённых #( и ). Например:

Следует отметить, что когда функция read парсит данный синтаксис, она всегда создаёт простой массив. __________________________________________

Обоснование: Многие люди рекомендовали использовать квадратные скобки для задания векторов так: [a b c] вместо #(a b c). Данная запись короче, возможно более читаема, и безусловно совпадает с культурными традициями в других областях компьютерных наук и математики. Однако, для достижения предельной полезности от пользовательских макросимволов, что расширяют возможности функции read, необходимо было оставить некоторые строковые символы для этих пользовательских целей. Опыт использования MacLisp’а показывает, что пользователи, особенно разработчики языков для использования в исследованиях искусственного интеллекта, часто хотят определять специальные значения для квадратных скобок. Таким образом Common Lisp не использует квадратных и фигурных скобок в своём синтаксисе.

Реализации могут содержать специализированные представления массивов для достижения эффективности в случаях, когда все элементы принадлежат одному определённому типу (например, числовому). Все реализации содержат специальные массивы в случаях, когда все элементы являются строковыми символами (или специализированное подмножество строковых символов). Такие одномерные массивы называются строки. Все реализации также должны содержать специализированные битовые массивы, которые принадлежат типу (array bit). Такие одномерные массивы называются битовые векторы.

2.5.2 Строки

Реализация может поддерживать другие типы строк. Все функции Common Lisp’а взаимодействуют со строками одинаково. Однако следует отметить, вставка extended character в base string является ошибкой.

Строковый (string) тип является подтипом векторного (vector) типа.

Строка может быть записана как последовательность символов, с предшествующим и последующим символом двойной кавычки «. Любой символ « или в данной последовательности должен иметь предшествующий символ .

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

Строковые символы обрамленные двойными кавычками, считываются слева направо. Индекс символа больше индекса предыдущего символа на 1. Самый левый символ строки имеет индекс 0, следующий 1, следующий 2, и т.д.

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

2.5.3 Битовые векторы

Битовый вектор может быть записан в виде последовательности битов заключённых в строку с предшествующей #*; любой разделитель, например, как пробел завершает синтаксис битового вектора. Например:

Биты записанные после #*, читаются слева направо. Индекс каждого бита больше индекса предыдущего бита на 1. Индекс самого левого бита 0, следующего 1 и т.д.

Функция prin1 выводит любой битовый вектор (не только простой) в этом синтаксисе, однако функция read при разборе этого синтаксиса будет всегда создавать простой битовый вектор.