В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
k обозначает номер прохода. Подчеркнуты числа, которые подвергаются обмену на текущем проходе. Элементы, которые не участвуют в текущем проходе, выделены вертикальными линиями. k=0; k Imax = i Imax = 0 buf = A[N-k-1] A[N-k-1]= A[Imax] A[Imax] = buf Рис. 4.19. Сортировка методом линейного поиска 130 0 4 5 9 1 7 6 0 4 5 6 1 7 9 k=0 0 4 5 6 1 7 |9| k=1 0 4 5 1 6 |7| |9| k=2 0 4 1 5 |6| |7| |9| k=3 0 1 4 |5| |6| |7| |9| k=4 0 1 |4| |5| |6| |7| |9| k=5 Программная реализация алгоритма: for (int k=0; k } Еще одним достаточно простым методом сортировки является сортировка пузырьковым методом. Он называется так потому, что на каждом проходе, при движении вдоль массива, берем самый большой встретившийся элемент и далее двигаем его к концу массива, пока не встретим элемент еще больше. Затем продолжаем движение уже с этим элементом. И так до тех пор, пока весь массив не будет пройден. Этот наибольший элемент можно представить пузырьком в стакане воды, который медленно поднимается на поверхность. 0 4 5 9 1 7 6 i=0 k=6 0 4 5 9 1 7 6 i=1 k=6 0 4 5 9 1 7 6 i=2 k=6 0 4 5 1 9 7 6 i=3 k=6 0 4 5 1 7 9 6 i=4 k=6 0 4 5 1 7 6 9 i=5 k=6 0 4 5 1 7 6 |9| i=0 k=5 0 4 5 1 7 6 |9| i=1 k=5 0 4 1 5 7 6 |9| i=2 k=5 131 0 4 1 5 7 6 |9| i=3 k=5 0 4 1 5 6 7 |9| i=4 k=5 0 4 1 5 6 |7| |9| i=0 k=4 0 1 4 5 6 |7| |9| i=1 k=4 0 1 4 5 6 |7| |9| i=2 k=4 0 1 4 5 6 |7| |9| i=3 k=4 0 1 4 5 |6| |7| |9| i=0 k=3 0 1 4 5 |6| |7| |9| i=1 k=3 0 1 4 5 |6| |7| |9| i=2 k=3 0 1 4 |5| |6| |7| |9| i=0 k=2 0 1 4 |5| |6| |7| |9| i=1 k=2 0 1 |4| |5| |6| |7| |9| i=0 k=1 k=n-1; k>0; k-- i=0; i buf = A[i] A[i] = A[i+1] A[i+1] = buf Рис. 4.20. Сортировка пузырьковым методом 132 На каждом проходе анализируем соседние элементы. Если для них выясняется, что они не на своем месте, то меняем их местами. После проверки всех соседних паросочетаний переходим к следующему проходу. Но последний элемент уже не участвует в сортировке, поскольку он на своем месте. И так продолжаем до тех пор, пока не достигнем начала массива. Иллюстрация описанного алгоритма представлена ниже. Подчеркнуты те ячейки массива, которые подвергаются анализу в текущий момент: k – количество проходов до окончания сортировки; i – номер анализируемой пары элементов. Данный алгоритм представлен на рис. 4.20. for (int k=n-1; k>0; k--) { for (int i=0; i { buf = a[i]; a[i] = a[i+1]; a[i+1] = buf; } } Как видно из примера разобранного для пузырькового метода, массив оказывается отсортированным значительно раньше, чем закончатся все проходы. Уже на третьем проходе весь массив упорядочен. Оставшиеся три прохода идут впустую. Даже если массив будет изначально упорядочен, число проходов не изменится. Чтобы учесть высказанные замечания, можно модифицировать пузырьковый метод. Для этого внешний цикл сделаем циклом с постусловием, а внутрь него поместим логическую переменную sort, которая будет принимать при каждой внешней итерации ложное значение. Однако, если массив не отсортирован на данной итерации, то она примет истинное значение. Как только условие упорядоченности соседних элементов выполнится для всех ячеек массива, сортировка прекратится. Иллюстрация этого процесса представлена ниже. 133 0 4 5 9 1 7 6 i=0 k=6 0 4 5 9 1 7 6 i=1 k=6 0 4 5 9 1 7 6 i=2 k=6 0 4 5 1 9 7 6 i=3 k=6 0 4 5 1 7 9 6 i=4 k=6 0 4 5 1 7 6 9 i=5 k=6 sort = false 0 4 5 1 7 6 |9| i=0 k=5 0 4 5 1 7 6 |9| i=1 k=5 0 4 1 5 7 6 |9| i=2 k=5 0 4 1 5 7 6 |9| i=3 k=5 0 4 1 5 6 7 |9| i=4 k=5 sort = false 0 4 1 5 6 |7| |9| i=0 k=4 0 1 4 5 6 |7| |9| i=1 k=4 0 1 4 5 6 |7| |9| i=2 k=4 0 1 4 5 6 |7| |9| i=3 k=4 sort = false 0 1 4 5 |6| |7| |9| i=0 k=3 0 1 4 5 |6| |7| |9| i=1 k=3 0 1 4 5 |6| |7| |9| i=2 k=3 sort = true Программная реализация алгоритма: int k=n; do { bool sort=false; k--; for (int i=0; i { int buf = a[i]; a[i] = a[i+1]; a[i+1] = buf; sort = true; } } while (sort); Описанный алгоритм записывается таким образом (рис. 4.21): 134 Итак, для каждого из описанных методов требуется два цикла для осуществления сортировки. Число проверок условий в этих алгоритмах равно 1 1 1 2 3 ... ( 2) ( 1) N k W i N N Это сумма арифметической прогрессии, она равна k -- k = n + sort = false i=0; i buf = A[i] A[i] = A[i+1] A[i+1] = buf sort = true sort - Рис. 4.211. Улучшение алгоритма сортировки 135 2 2 1 2 2 N N N N W N По данной формуле видно, что зависимость времени исполнения сортировки от размера массива квадратичная. Для этого была введена функция 2 N . Очевидно, что чем длиннее массив, тем больше времени требуется на его упорядочивание, причем время возрастает нелинейно и достаточно быстро. Про такие алгоритмы принято говорить, что время их исполнения порядка 2 N . Вообще доказано, что для сортировки одномерного массива максимально быстрые алгоритмы не могут быть быстрее чем log N N . Однако эти алгоритмы в данной главе рассматриваться не будут, поскольку они достаточно сложны для неподготовленного читателя. Следует отметить, что сложность log N N гораздо более приемлемая, чем 2 N , поскольку, например, если длина массива возрастает в 100 раз, то время простой сортировки увеличится в 10 000 раз. А для быстрой сортировки увеличение времени произойдет примерно в 2 100 log 100 664 раза. Еще одной интересной задачей для одномерных массивов является задача поиска одинаковых элементов. Одинаковые элементы можно найти если каждый элемент сравнить с каждым. То есть первый элемент сравниваем со вторым, потом с третьим и так до конца массива. Далее сравниваем второй элемент с третьим, четвертым, пятым и т. д. Алгоритм продолжаем до тех пор, пока все пары не будут рассмотрены. Эта задача решается в два цикла (рис. 4.22): for (int k=0; k 136 Сложность алгоритма полиномиальная, квадратичная. Всего потребуется, как и для сортировки массива, 2 / 2 N N проверок условия. 4.6. Динамические массивы Ранее в разделе 3.6. были приведены основные сведения об указателях и динамической памяти. Имя массива является указателем на область памяти, в которой расположены элементы массива, таким образом запись a[0] эквивалентна записи *a. А запись a[5] соответствует записи *(a+5). Чтобы пользоваться динамическими массивами, т.е. массивами, под которые объем памяти выделяется в процессе работы (предложенные нами методы не будут работать в MVS и некоторых других компиляторах) можно использовать динамическое выделение памяти. Динамическое выделение памяти необходимо для эффективного использования памяти компьютера. Например, мы написали какую-то программку, которая обрабатывает массив. При написании данной программы необходимо было объявить массив, то есть задать ему k=0; k Вывод A[ i ] Рис. 4.222. Алгоритм поиска одинаковых элементов массива 137 фиксированный размер (к примеру, от 0 до 100 элементов). Тогда данная программа будет не универсальной, ведь может обрабатывать массив размером не более 100 элементов. А если нам понадобятся всего 20 элементов, но в памяти выделится место под 100 элементов, ведь объявление массива было статическим, а такое использование памяти крайне не эффективно. Напомним, что в С++ операции new и delete предназначены для динамического распределения памяти компьютера. Операция new выделяет память из области свободной памяти, а операция delete высвобождает выделенную память. Выделяемая память, после её использования должна высвобождаться, поэтому операции new и delete используются парами. Даже если не высвобождать память явно, то она освободится ресурсами ОС по завершению работы программы. Однако, если такое выделение памяти происходит многократно в процессе работы программы, это может привести к заполнению всей свободной оперативной памяти, поэтому необходимо очищать не используемую память. ПРИМЕР Создать динамический массив из n элементов. int n; cout<<”\nInput count of array’s elements”; cin>>n; float *mas = new int [n]; for (int i=0; i } delete []mas; // освобождение памяти 138 5. ДВУМЕРНЫЕ МАССИВЫ 5.1. Понятие и объявление двумерного массива Довольно часто при обработке больших объемов информации мы имеем дело с упорядочиванием данных по нескольким признакам. Если в структуре данных есть возможность выделения содержимого по этим признакам, то имеет смысл организовывать так называемый многомерный массив. Самым простым примером многомерного массива является двумерный. Двумерный массив – это одномерный массив, каждым элементом которого является свой одномерный массив. Получается так называемый «массив массивов». Можно сказать и так: двумерный массив – это такой тип данных, элементы которого однотипны и каждый из них характеризуется уникальной парой чисел: индексом строки и индексом столбца. Естественным отображением двумерного массива является таблица. Таблица есть двумерная структура, у которой вдоль горизонтального направления перечень одних свойств, а вдоль вертикального – других. -4,5 0 3,0 1 -12,1 2 3,1 3 0 1 2 A= B= 2,2 7,1 5,0 -5,2 0,1 -3,0 -12,1 6,0 0 1 2 i ↓ j → ‘привет!!!’ ’12 23 3' ‘2 часа’ ‘*** ***’ ’vstu.ru' ‘2 $’ ‘- %%№’ ’Массив' ‘### 1’ 0 1 2 i ↓ j → N A M A M B N B Рис. 5.1 Примеры двумерных массивов 139 Пересечение столбца и строки дает нужный элемент, одновременно обладающий обоими свойствами. Для двумерного массива этими свойствами являются числа – индексы строк и столбцов. Примеры двумерных массивов изображены на рис. 5.1. На иллюстрации массив A – это массив, элементами которого являются дробные числа (тип float). Объявление массива A следующее: float a[10][10]; Массив A объявлен с запасом по размерности. На рисунке размерность массива 3×4, а при объявлении выделяем память под 10×10=100 ячеек типа float, т.е. размер будет 100×8 байт = 800 байт. Используемый размер 3×4×8 байт 96 байт. Видно, как сильно зависит расход памяти от размерности массива. Потому следует следить за размерностью и, по возможности, не объявлять слишком больших массивов. Условимся далее для обозначения числа строк использовать переменную N, а для столбцов M. То есть для массива A N A =3, M A =4; для массива B N B =3, M B =3. B – массив состоящий из наборов символов. Объявление массива B такое: string b[3][3]; Для непосредственного обращения к элементу нужно указать его адрес. Адрес в двумерном массиве – пара чисел. Сначала идет номер элемента во внешнем одномерном массиве, а потом во внутреннем. Поскольку двумерные массивы представляем в виде таблиц, то условимся первым числом обозначать номер строки, а вторым – индекс столбца. Вообще, строки и столбцы можно поменять местами, поскольку организовывать порядок их задания можно произвольно. Но далее всегда будем обозначать сначала строку, а затем – столбец. Причем в С++ каждый индекс пишется в собственных квадратных скобках. Для примеров на рис. 5.1 это выглядит следующим образом: 140 A[0][0]=–4,5 A[0][1]= 3,0 A[0][2]=–12,1 A[0][3]= 3,1 A[1][0]= 2,2 A[1][1]= 7,1 A[1][2]= 5,0 A[1][3]=–5,2 A[2][0]= 0,1 A[2][1]=–3,0 A[2][2]=–12,1 A[2][3]= 6,0 И, соответственно, массив B: B[0][0]= “привет” B[0][1]=”12 23 3” B[0][2]=”2 часа” B[1][0]=”*** ***” B[1][1]=”vstu.ru” B[1][2]=”2 $” B[2][0]= “- %%№” B[2][1]=”Массив” B[2][2]=”### 1” Порядок обращения к элементам двумерного массива сходен с порядком обращения к элементам одномерного, т. е. нельзя подвергать изменению целиком весь массив сразу. Для обращения, как это видно выше, в квадратных скобках через запятую указываются координаты элемента по вертикали и горизонтали. В некоторых языках программирования счет индексам начинается не с 0, например, в Pascal можно задавать диапазон изменения индексов в любых границах (даже отрицательных). В языке С++ номера всегда начинаются с 0, так как с именем массива связан адрес памяти, в которой содержатся элементы массива. Еще следует отметить, что наиболее естественными объектами, которые принято хранить в двумерных массивах, являются числа. Такие массивы будем называть матрицами, так же, как и в математике. И именно на их примере рассмотрим основные алгоритмы обработки этих структур. 5.2. Поэлементная обработка двумерных массивов Прямая безусловная поэлементная обработка двумерного массива предполагает такую обработку, при которой все его элементы безусловно просматриваются в порядке возрастания индексов. Индексы можно увеличивать, рассматривая массив по строкам или по столбцам. 141 Блок-схема этого процесса (построчная реализация) представлена на рис. 5.2, а. Самые простые алгоритмы поэлементной обработки массива – это алгоритмы ввода и вывода. Алгоритм ввода, или инициализация пользователем, представлен на рис. 5.2, б. Здесь, поскольку массивы мы объявляем с запасом размерности, следует сначала указать число строк N и количество столбцов M. Массив рассматриваем, согласно соглашению, построчно, т. е. во внешнем цикле меняется индекс строки, а во внутрен- нем – индекс столбца. int n,m,a[10][15]; cout<<”\nInput count of rows”; cin< } i=0; i i=0; i Ввод A[i][j] Ввод N а) б) Рис. 5.2. Поэлементная обработка двумерного массива (а) и ввод массива (б) 142 Вывод массива аналогичен вводу; только если будем выводить все элементы подряд, разные строки сольются между собой. Невозможно будет определить, где кончается одна строка и начинается следующая. Для этого нужно после вывода каждой строки принудительно переводить курсор на следующую. Делается это очень просто, методом вставки во внешний цикл алгоритма операции cout<<”\n”;: for (int i=0; i На блок-схеме (рис. 5.3) показана операция принудительного перевода курсора на следующую строку. В дальнейшем при оформлении блок-схем ее показывать не будем, негласно предполагая ее наличие. Вообще, такая обработка называется обработкой по строкам или столбцам и более детально будет рассмотрена ниже. Здесь же вывод массива приведен для того, чтобы не терять логическую связь со вводом. В качестве примеров прямой обработки всех элементов массива можно привести алгоритм подсчета сумы, произведения, а также изменение всех элементов. Скажем, рассмотрим увеличение всех элементов двумерного массива на некоторую константу x: for (int i=0; i Перевод строки Рис. 5.3. Вывод двумерного массива 143 В теле внутреннего цикла помещено условие, в случае выполнения которого происходит действие над элементом A[i][j]. Вот типичная задача на обработку всего двумерного массива с анализом элементов. i=0; i Действия над A[i][j] Рис. 5.4. Алгоритм анализа элементов массива i=0; i A[i][j] = A[i][j] 2 Рис. 5.5. Возведение в квадрат нечетных элементов 144 ПРИМЕР Возвести в квадрат все нечетные элементы двумерного массива A. Решение приведено на рисунке 5.5. for (int i=0; i Рассмотрим полностью задачу, которая в предыдущей главе решалась для одномерных массивов. ПРИМЕР Найти среднее арифметическое четных элементов массива. Для начала составим тестовый пример: вход: 2 1 2 8 4 5 ; выход: SrA=4. Сам алгоритм практически такой же, как и в задаче для одномерных массивов; отличие здесь в том, что дополнительно добавляется цикл по столбцам (по |