Методичка С++ (Массивы)

Посмотреть архив целиком

9



  1. Массивы

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

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

  1. Однотипная обработка массивов

А) Поэлементная обработка .

Б) Выборочная обработка элементов массива

  1. Переформирование массива

А) Без изменения исходных размеров массива

Б) С изменением размеров исходного массива.

  1. Одновременная обработка нескольких массивов или подмассивов.

А) С синхронным изменением индексов.

Б) С произвольным изменением индексов

  1. Поисковые задачи.

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

    1. Основные приемы программирования обработки одномерных массивов.

Одномерными называются массивы, имеющие один тип индексов. Описание массива может быть выполнено в разделе описания переменных в разделе VAR:

VAR A,B:array [1..10] of real; {массив из 10 вещественных чисел}

C:array[BOOLEAN] of char; {массив символов из двух значений}

d:array [char] of integer; {массив целых чисел на 256 значений}

или с предварительным описанием типа в разделе TYPE:

TYPE Bmas=array[BOOLEAN] of char; { тип - массив символов из двух значений}

Cmas= array [char] of integer; {тип - массив целых чисел на 256 значений}

Rmas= array [1..10] of real; { тип - массив из 10 вещественных чисел}

VAR A,B:Rmas;

C:Bmas;

d:Cmas;

Рассмотрим наиболее распространенные приемы программирования обработки одномерных массивов.

      1. Первый класс задач

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

Рассмотрим некоторые типовые алгоритмы задач первого типа.

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



Рис. 4.1


Рис. 4.2


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

Пример 3. Пусть необходимо найти среднее арифметическое значение положительных элементов целочисленного массива, кратных трем. Для решения этой задачи необходимо двум вспомогательным переменным Sum и Kol, которые будут использоваться для накопления суммы требуемых элементов и их количества, присвоить нулевые значения. После этого осуществляется перебор всех элементов и, если очередной удовлетворяет условию, его значение добавляется к содержимому переменной Sum, а значение переменной Kol увеличивается на единицу. В конце просмотра всего массива среднее арифметическое может быть определено путем деления накопленной суммы на количество найденных элементов. Алгоритм решения задачи представлен на рис. 4.3.


Рис.4.3





      1. Второй класс задач.

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

Пример1. Пусть необходимо заменить все отрицательные элементы массива на нулевые

Пример 2. Переформировать массив таким образом, чтобы сначала шли все положительные элементы, затем отрицательные и в конце - нулевые.

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

        1. Сортировка массивов

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

Сортировка с помощью выбора

Сортировка с помощью выбора представляет собой один из самых простых методов сортировки. Он основан на следующих принципах:

  1. Выбирается наименьший элемент из всего массива.

  2. Найденный наименьший элемент меняется местами с первым элементом.


  1. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент массива.

Пример алгоритма с помощью выбора приведен на рисунке 5.1


Рис. 5.1



Сортировка с помощью обмена

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

Пусть, например, массив состоит из элементов (2, 5, 12, 1, 8, 4). Если сортировать массив по возрастанию, то после первого «прохода» по массиву мы получим следующий массив (2, 5, 1, 8, 4, 12). После второго «прохода» - (2, 1, 5, 4, 8, 12), после третьего – (1, 2, 4, 5, 8,12).

В своем простейшем виде алгоритм сортировки с помощью обмена представлен на рисунке 5.2.

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

Сортировка методом вставки

Алгоритм сортировки с помощью вставки можно описать следующим образом. При каждом шаге, начиная с i=2, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность на нужное место. В реальном процессе поиска подходящего места удобно сначала сравнивать извлеченный элемент с очередным элементом aj, а затем либо aj сдвигается вправо, либо ai вставляется на освободившееся место. Процесс поиска может закончиться при выполнении одного из двух следующих условий: либо найден элемент aj меньший, чем ai, либо достигнут левый конец массива.

Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться хорошо известным приемом «барьера». Для этого необходимо расширить диапазон индекса в описании массива от 0 до n. Алгоритм сортировки приводится на рисунке 5.3.

Рис.5.2


Рис. 5.3




Метод Шелла

Метод состоит в том, что упорядочиваемый массив разделяется на группы таким образом, что в каждой группе находятся элементы, отстоящие друг от друга на расстоянии d. Каждая группа сортируется методом вставки, затем массив делится на новые группы с шагом d-1 и т.д. пока количество групп не станет равным единице. Обычно d выбирается таким образом, чтобы в каждой группе находилось два элемента, т.е. d=[n/2].

      1. Третий класс задач.

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

Пример 1. Определить максимальный элемент, среди элементов целочисленного массива, стоящих на четных местах.

Пример 2. Заменить каждый третий элемент массива значением 0- если он четен и остатком от деления элемента на два, если он нечетен.


      1. Четвертый класс задач.

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

Пример 1. Пусть необходимо вычеркнуть из массива целых чисел все те числа, которые кратны 5. Для решения задачи необходимо, обходя весь массив найти очередной удаляемый элемент, а затем путем циклического сдвига перенести все элементы, расположенные после него. Полученный массив окажется на 1 элемент меньше. Изменив размер массива следует продолжить перебор элементов.

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

      1. Пятый класс задач.

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

      1. Шестой класс задач.

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

Рассмотрим следующие примеры.

Пример1. Задан целочисленный массив из n элементов. Присвоить переменной k значение true, если в массиве существуют два одинаковых элемента, стоящих рядом, и false в противном случае.

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





Пример 2. Пусть необходимо отыскать в массиве отсортированном по убыванию элемент равный введенному.

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

    1. Приемы программирования обработки матриц.

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

в разделе описания переменных VAR двумя способами:

  1. как одномерный массив одномерных массивов

VAR

M: array[1..8] of array[char] of integer; {массив из 8 массивов на 256 целых чисел}

A,B: array[boolean] of array[byte] of real; {массив из 2-х массивов на 256 вещественных чисел}

C: array[1..5] of array[1..10] of char; {массив из 5 массивов на 10 символов}

  1. как двумерный массив

VAR

MATR: array[1..8,char] of real; {матрица 8х256 вещественных чисел}

CMATR: array[1..5,1..10] of char; {символьная матрица 5х10 символов}

BMATR: array[byte,’A’..’Z’] of boolean; {матрица логических переменных 256х26 значений}

в разделе описания типов TYPE двумя способами:

  1. как одномерный массив одномерных массивов

TYPE

MAS =array[char] of integer; {тип - массив на 256 целых чисел}

MASA = array[byte] of real; {тип - массив на 256 вещественных чисел}

MASC = rray[1..10] of char; {тип массив на 20 символов}

VAR

M:array[1..8] of MAS; {массив из 8 элементов типа MAS }

A,B: array[boolean] of MASA; {массив из двух элементов типа MASA }

C: array[1..5] of MASC; {массив из 5 элементов типа MASC }

  1. как двумерный массив

TYPE

TMATR = array[1..8,char] of real; { тип -матрица 8х256 вещественных чисел}

TCMATR= array[1..5,1..6] of char; { тип - символьная матрица 5х10 символов}

TBMATR = array[byte,’A’..’Z’] of boolean; { тип - матрица логических переменных 256х26 значений}

VAR

MATR:T:TMATR; {переменная типа TMATR}

CMATR: TCMATR; {переменная типа TCMATR}

BMATR: TBMATR; {переменная типа TBMATR}

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

      1. Первый класс задач.

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

Рассмотрим некоторые типовые алгоритмы задач первого класса.

Пример 1. Задана квадратная целочисленная матрица размера nn. Найти наибольший элемент матрицы и количество таких элементов.

Для решения этой задачи нужно организовать цикл для перебора всех элементов матрицы. Так как матрица является двумерным массивом, то потребуется два цикла (один для перебора строк, второй - столбцов). В остальном, алгоритм решения этой задачи (см. рис. 6.1) схож с алгоритмом нахождения максимального элемента одномерного массива.

Пример 2. Задана целочисленная матрица A(m, n). Вычислить сумму каждой стоки и результат записать в массив b(n).

Для вычисления суммы элементов некоторой строки с номером i необходимо организовать цикл для перебора всех элементов данной строки. Поэтому параметром этого цикла следует выбрать номер столбца j. Перед циклом с параметром j необходимо задать начальное значение суммы S=0. После окончания цикла результат присваивается соответствующему элементу массива b. Для обеспечения обхода всех строк матрицы параметром внешнего цикла следует выбрать номер строки i.


Рис. 6.2




Рис 6.1



      1. Второй класс задач.

В качестве примеров задач второго класса для матриц можно


Пример.1.. Дана действительная квадратная матрица порядка 2n. Получить новую матрицу, переставляя ее блоки размера nn в соответствии с рисунком.

Для решения этой задачи нужно определить правило, по которому будут преобразовываться индексы матрицы. Будем считать, что после преобразования получается новая квадратная матрица размерности 2n. Тогда внимательно изучив соответствие между элементами матрицы A и матрицы B, получаем следующий закон преобразования:

Алгоритм решения смотри на рисунке 6.3.


Рис. 6.3






Случайные файлы

Файл
177919.rtf
my.doc
55529.rtf
104086.rtf
1.doc