СИ. Программирование на языке CC Часть Структурное программирование
 Скачать 1.65 Mb.
|
|
int * p1 = new int ; для создания динамической переменной типа Здесь совмещено описание переменной-указателя и выделение памяти; эти два действия можно разделить — 91 Можно использовать инициализатор в круглых скобках, например: double * p2 = new double (3.5); В результате выполнения операции new в динамической памяти резервируется область нужного размера (в зависимости от указанного типа) и адрес начала этой области помещается в указатель. Если используется инициализатор, то заданное в скобках значение помещается в зарезервированную область памяти и может быть прочитано при разыменовании указателя. Пример выделения динамической памяти с помощью функции malloc : i n t * p3 ; p3 = ( i n t *) malloc ( s i z e o f ( i n t )); double * p4 ; p4 = ( double *) malloc ( s i z e o В качестве параметра указывается размер области памяти. Поскольку функция возвращает значение типа указатель без типа), требуется явное приведение типов. Если при попытке выделения динамической области памяти выясняется, что свободная память отсутствует, тов старых версиях компиляторов языка указатель принимает нулевое значение и память не выделяется, а в новых версиях генерируется так называемое исключение, которое может быть обработано в программе (работа исключениями рассматривается во второй части настоящего пособия). Когда динамическая переменная становится ненужной, занимаемую ею память надо освободить. Переменные, созданные с помощью операции уничтожаются операцией delete . Если использовалась функция то для уничтожения динамической переменной применяют функцию free() : delete p1 ; delete p2 ; free ( p3 ); free ( p4 ); — 92 Если указатель нулевой (никуда не указывает, то операция delete и функция free ничего не делают. После освобождения памяти указатель по-прежнему хранит старый адрес, поэтому иногда рекомендуют обнулить указатель, чтобы случайно не обратиться к участку памяти, который уже не должен использоваться 0; p2 = 0; p3 = 0; p4 = Если программист забыл освободить динамическую память, то происходит, так называемая, утечка памяти — занятая область динамической памяти больше не используется программой, ноне может быть выделена для других динамических переменных (в том числе, при работе других программ), пока данная программа (в которой происходит утечка) не будет завершена. При завершении программы все созданные в ней динамические переменные уничтожаются автоматически и память освобождается. Одномерные динамические массивы. Обычно в динамической памяти хранят не одиночные переменные, а структуры данных большого размера, в том числе, массивы. Пример создания одномерного динамического массива из элементов типа Здесь описана переменная-указатель на массив вещественных чисел в динамической памяти зарезервирована область для хранения элементов массива адрес начала этой области помещён в переменную-указатель. То же самое, нос использованием функции malloc() : double * p2 ; p2 = ( double *) malloc ( n * s i z e o Инициализатор в фигурных скобках при определении динамического массива использовать нельзя. Кроме того, в отличие от статических массивов, элементы которых автоматически инициализируются нулевыми значениями, элементы динамических массивов имеют произвольные начальные значения — 93 При освобождении памяти, отведённой под массив, в операции delete требуется указывать квадратные скобки: delete [] p1 ; Если программист забудет указать квадратные скобки, то освободится область динамической памяти, занятая только нулевым элементом массива а место, занимаемое остальными элементами, будет недоступно для всех программ, пока наша программа не завершится (утечка памяти). Функция free работает с указателями на массив, как и с любыми други- ми: free ( p2 ); Варианты обращения к 𝑖-му элементу одномерного динамического массива, на начало которого указывает переменная-указатель p , ничем не отличаются от использования указателей со статическими массивами: p[i] или *(p+i) Перепишем программу из листинга, используя динамические массивы (листинг 3.3 ). Листинг 3.3: Вычисление суммы элементов динамического массива i n c l u d e 2 # i n c l u d e 3 using namespace std ; 4 5 i n t main (){ 6 // Ограничение на число элементов unsigned long i n t m = 100000000; 8 9 double x ; // среднее значение long i n t n ; // число элементов 13 do { 14 cout << "Введите␣число␣элементов␣" — 94 — 15 "(не␣больше␣" << m << ")␣=␣"; 16 cin >> n ; 17 } while ( n > m ); // пока не будет введено правильное значение 19 double * a = new double [ n ]; // создали динамический массив 0.0; // здесь будем накапливать сумму элементов o r ( unsigned long i n t i =0; i < n ; i ++) { 22 cout << "␣␣введите␣элемент␣[" << i << "]␣=␣"; 23 cin >> a [ i ]; // вводим й элемент сумма элементов "Сумма␣введённых␣элементов␣=␣" << sum << endl ; 27 x = sum / n ; // среднее арифметическое "Среднее␣значение␣=␣" << x << endl ; 29 d e l e t Как видим, текст программы практически не изменился мы исправили только описание массива (добавили операцию new ), переместив её в то место программы, где уже известно число элементов также добавилась операция освобождения памяти. В результате мы используем память экономно (вот- личие от варианта со статическим массивом, где место для него резервировалось с запасом кроме того, теперь мы можем работать с массивами очень большой длины (в пределах возможностей динамической памяти). Модификация массивов. При использовании массивов программист имеет возможность непосредственно обращаться для чтения или записи к любому элементу. Но если, например, требуется вставить новый элемент в начало или середину массива, сохранив все уже имеющиеся, или нужно удалить некоторый элемент изначала или середины массива, то приходится сдвигать — 95 все элементы, которые следуют после вставляемого или удаляемого элемента, соответственно, вправо или влево. Пример 3.4. Вставка нового элемента в позицию массива и сдвиг всех оставшихся элементов вправо (последний элемент теряется o r ( unsigned long i = n -2; i > k ; i --) a [ i +1] = a [ i ]; a [ k ] Пример 3.5. Удаление го элемента массива и сдвиг всех оставшихся элементов влево (последний элемент инициализируется нулём): f o r ( unsigned long i = k ; i < n -1; i ++) a [ i ] = a [ i +1]; a [ n -1] = 0; 3.3. Сортировка элементов массива Алгоритм сортировки — это алгоритм упорядочения элементов водно- мерном массиве (векторе, списке). Перестановка элементов. В приведённых ниже алгоритмах сортировки используется операция перестановки элементов массива. В простейшем случае значения двух элементов и можно поменять местами с помощью служебной переменной = a [ j ]; a [ j ] Если элементы массива имеют целый тип, то можно обойтись и без дополнительных переменных, например, с помощью поразрядной операции исключающее или = a [ i ] ^ a [ j ]; a [ j ] = a [ i ] ^ a [ j ]; a [ i ] = a [ i ] ^ a [ j ]; — 96 Если операция перестановки используется в алгоритме часто, то можно определить функцию (см. разделили макрос d e f i n e SWAP(A, B) { A = A ^ B; B = A ^ B; A = A ^ B; Чтобы переставить вещественные числа, вместо поразрядных операций придётся использовать арифметические d e f i n e SWAP(A, B) { A = A + B; B = A - B; A = A - B; Чтобы избежать ошибок округления (особенно заметных, если перестав- ляемые значения отличаются на несколько порядков, лучше всё-таки использовать временную переменную d e f i n e SWAP(A, B) { double T = A; A = B; B = T; } Гномья сортировка. Данный алгоритм предложен в 2000 году и состоит (в отличие от других) всего из одного цикла. Это метод, которым садовый гном сортирует линию цветочных горшков. Он смотрит на два соседних горшка если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия если нет предыдущего горшка — гном шагает вперёд; если нет следующего горшка — сортировка завершена. Фрагмент программы для сортировки по возрастанию массива из элементов методом гнома (нумерация элементов начинается с n t i = 0; while ( i < n ){ i f ( i == 0 || a [ i -1] <= a [ i ]) { i ++; } e l s e { double t = a [ i ]; a [ i ] = a [ i -1]; a [-- i ] = t ; } } — 97 Подумайте, как изменить текст программы, чтобы сортировка происходила по убыванию. Сортировка пузырьком. Сортировка простыми обменами пузырьком также один из самых простых, ноне эффективных алгоритмов часто упоминается в учебной литературе, ноне рекомендуется профессиональным программистам o r ( i = n - 1; i > 0; i --) { f o r ( j = 0; j < i ; j ++) { i f ( a [ j ] > a [ j + Сортировка перемешиванием (шейкерная сортировка) представляет собой улучшенный вариант пузырьковой сортировки n t last = n -1, left = 1, right = n -1; do { f o r ( j = right ; j >= left ; j --) { i f ( a [ j -1] > a [ j ]) { SWAP ( a [ j -1], a [ j ]) last = j ; } } left = last + 1; f o r ( j = left ; j <= right ; j ++) { i f ( a [ j -1] > a [ j ]) { SWAP ( a [ j -1], a [ j ]) last = j ; } } right = last -1; } while ( left < right ); — 98 Сортировка вставками. На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан o r ( i = 1; i < n ; i ++) { t = a [ i ]; f o r ( j = i - 1; j >= 0; j --) { i f ( a [ j ] < t ) { break ; } a [ j +1] = a [ j ]; } a [ j +1] Сортировка выбором. Находим минимальное значение в текущем списке производим обмен этого значения со значением на первой неотсорти- рованной позиции сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы o r ( i n t i =0; i < n -1; ++ i ){ i n t min = i ; f o r ( i n t j = i +1; j < n ; ++ j ){ i f ( a [ j ]< a [ min ]) min = j ; } i f ( min != i ) SWAP ( a [ i ], a [ min ]); } — 99 — 3.4. Двумерные массивы Статические двумерные массивы. При описании статических двумерных массивов (матриц) в квадратных скобках указываются количество строки столбцов, например матрица из 5 строки столбцов Согласно стандарту C90 обе размерности должны быть константами или константными выражениями, известными на момент компиляции. Стандарт допускает использование переменных, если переменная-массив является ло- кальной. Аналогично описывается массив любой другой размерности, например, трёхмерный массив: double a [2][5][3]; В памяти элементы массива располагаются построчно (при переходе к следующему элементу изменяется последний индекс). Определение массива может сопровождаться его инициализацией при этом каждую строку можно либо заключать в отдельные фигурные скобки (при этом можно не указывать самую первую размерность, либо задавать единый список всех элементов в том порядке, в каком они должны размещаться в памяти компьютера n t a [][3] = {{1, 5, 3}, {-5, 4, 1}}; i n t a [2][3] = {1, 5, 3, -5, 4, Если значения последних элементов не указаны, то они будут инициализированы нулями. Доступ к элементу двумерного массива осуществляется по двум индексам варианты обращения к элементу, находящемуся в й строке им столбце Во втором случае мы сначала обращаемся к адресу начала й строки, а от него переходим к j -му элементу. В третьем случае мы берём адрес начала массива, затем переходим к началу й строки, после чего переходим к j -му элементу. Динамические двумерные массивы. Для создании двумерного массива в динамической памяти при использованием операции new необходимо указать обе его размерности, причём переменной может быть только первая размерность. Данное ограничение связано стем, что компилятору необходимо знать все размерности многомерного массива, кроме первой, чтобы генерировать код для доступа к нужным элементам. Ниже указаны фрагмент кода, иллюстрирующий работу с динамическим двумерным массивом n t n ; const i n t m = 10; cout << "Введите␣количество␣строк␣матрицы:␣"; cin >> n ; double (* p )[ m ] = new double [ n ][ m ]; f o r ( i n t i =0; i < n ; i ++){ f o r ( i n t j =0; j < m ; j ++){ cout << "arr[" << i << "][" << j << "Здесь мы определили указатель на массив из элементов типа если не поставить скобки, то получится массив указателей) и выделили динамическую память под элементов типа массив из элементов типа После этого в цикле организовали ввод элементов массива с клавиатуры. Напомним, что элементы динамических массивов не инициализируются компилятором. Для освобождения динамической памяти, занятой массивами с любым количеством измерений, используется операция delete [] p ; — 101 Чтобы иметь возможность работать с динамическими массивами, имеющими произвольное количество строки столбцов, обычно организуют в динамической памяти иерархическую структуру, состоящую только из одномерных массивов (рис n t n , m ; cout << "Введите␣количество␣строк␣и␣столбцов:␣"; cin >> n >> m ; double ** p = new double *[ n ]; ¬ f o r ( i n t i = 0; i < n ; i ++) p [ i ] = new double [ m ]; ® ¬ — описываем указатель на указатель на элемент массива типа double и выделяем в динамической памяти место для хранения одномерного массива указателей на строки матрицы — цикл по строкам матрицы — выделяем в динамической памяти место для хранения элементов й строки и присваиваем i -му элементу массива указателей адрес начала данного участка памяти. Рис. 3.2. Двумерный массив в динамической памяти Освобождение памяти в этом случае выглядит следующим образом o r ( i n t i = 0; i < n ; i ++){ d e l e t e [] p [ i ]; } d e l e t e [] p ; — 102 те. сначала в цикле освобождается память, занятая каждой строкой матрицы, а затем уничтожается массив указателей на (уже уничтоженные) строки. Контрольные вопросы. Пояснить смысл следующий понятий, привести примеры а) массив; б) указатель в) ссылка г) динамическая память д) утечка памяти. Можно ли хранить в массиве элементы различных типов. Доступ к отдельным элементам массива осуществляется по имени или по номеру. Какой индекс имеет самый первый элемент одномерного массива вязы- ке C/C++? 5. Как располагаются в памяти элементы одномерного массива. Когда при описании массива допускается не указывать его размер. Зачем используется функция sizeof() ? Какие она имеет входные параметры Какой результат и какого типа возвращает. В программе требуется обратиться с 50-му элементу массива. Можно ли это сделать непосредственно, или придётся по очереди перебрать все предыдущие 49 элементов. Какими способами можно создать динамическую переменную типа double ? 10. Как создать одномерный динамический массив из элементов типа long int ? 11. Какой смысл имеют следующие строки в программе: а) int * p = new int (5); б) int * p = new int [5]; 12. Программист создал в динамической памяти массив из 100 элементов. Входе выполнения программы потребовалось добавить к этому массиву ещё 50 элементов. Как это сделать. Описан массив из 𝑀 элементов. Уже используются (имеют нужные значения) первые 𝑁 элементов. Входе выполнения программы потребовалось между мим элементом массива вставить новый элемент, сохранив значения всех уже имеющихся элементов. Как это сделать? Изменится ли ответ, если 𝑀 = 𝑁 ? 14. Зачем нужно освобождать динамическую память после использования. В программе описан статический массив из 10 элементов. В некоторой строке программы происходит обращение к 11-му элементу. К чему это может привести Возникнут ли ошибки вовремя компиляции и/и- ли выполнения программы Изменится ли ответ, если массив будет не статическим, а динамическим. Перечислите преимущества и недостатки динамических массивов по сравнению со статическими. Какими значениями инициализируются элементы статических массивов А динамических. В программе объявлены массив и указатель n t a [10], Как присвоить указателю адрес самого первого элемента массива. В программе создан динамический массив n t * a = new |