Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19
Download 1.98 Mb.
|
Lekcii AiSD 2015
|
3.8 Алгоритмы обработки статических линейных структур
Алгоритмы обработки статических линейных структур чаще всего также носят линейный характер и представляют собой цик- лы, подобные циклам создания и удаления двумерного динами- ческого массива. Наряду с операциями, используемыми для про- стых структур данных — просмотр, модификация, ввод и вывод, к массивам и другим линейным структурам (не только статиче- ским) применяются более сложные операции, например, поиск, реверсирование (обращение). Алгоритмы поиска, в том числе, в линейных структурах, бу- дут рассмотрены ниже. Операция реверсирование представляет собой перестановку элементов структуры данных, например, массива, в обратном по- рядке. Реверсирование может оказаться полезным в случае, когда массив упорядочен, например, по убыванию, и требуется пере- ПО]ЭЯДОЧИТЬ EГO ПО ВОЗ]Э tCT tНИЮ. const int N = 10; // Размер массива float mas[N] = {9., 8., 7., 6., 5., 4., 3., 2., 1., 0. }; float buf; void main() for(int а = 0; а< N/2; а++) buf = mas[a]; mas[a] = mas[N — a]; mas[N — a] = buf; 53 Часто требуется скопировать содержимое одного массива в другой. Наиболее просто такая операция выполняется, если мас- сив-приёмник по размерам не превосходит массив-источник. Удобно оформить эту операцию в виде отдельной процедуры. float mas1[N]; void MasCopy(float* а, float* b, int п) for(int х = 0; х<п; х++) b[х] = а[х]; Алгоритмы характеризуются своей трудоёмкостью, т.е. ко- личеством операций, необходимых для завершения алгоритма, а также требованиями к объёму памяти, необходимой для хранения исходных данных и промежуточных результатов. Кроме того, ко- личество операций фактически означает время выполнения алго- ритма. Для обозначения обеих характеристик — времени выпол- нения и требуемого объёма памяти, используется одна и та же система обозначений, получившая название «О большое» верх- няя асимптотическая оценка трудоёмкости алгоритма. В этой системе обозначений время обработки структуры данных разме- ром N с помощью рассмотренных выше линейных алгоритмов (кроме поиска) характеризуется как fi(Щ. Вопросы и задания для самоконтроля К какой группе структур данных относятся автоматиче- ские массивы? К какой группе структур данных относятся статические массивы? К какой группе структур данных относятся динамиче- ские массивы? По каким признакам можно классифицировать двумер- ный динамический массив? Можно ли изменить размер динамического массива в процессе его использования? 54 Можно ли использовать один и тот же указатель для создания в разные моменты времени динамических массивов разного размера? В чем заключается связь между указателями и массива- мИ? Какие операции обязательны при работе с динамиче- скими массивами? Перечислите основные свойства динамических масси- В чем заключается отличие между автоматическими и статическими массивами? Какое требование нужно соблюдать при присваивании адреса массива указателю? Какие ограничения накладываются на определение многомерных динамических массивов? В чем заключается отличие между именем массива и указателем? Что представляют собой строки? Какие существуют способы организации строк? 55
Ссылки. Временные структуры данных В языках Си и Си++ возможны ситуации появления времен- ных структур данных — как переменных стандартных типов, так и более сложных: экземпляров записей (структурных типов) и объ- ектов классов. Такими ситуациями являются, в частности, несов- падение типов операндов в арифметических операциях и несов- падение типов в формальных и фактических аргументах функ- Ссылки в языке Си++ представляют собой второе имя ( няп псевдоним) объекта; объявляются при помощи символа &, npн объявленнн обязательно допжн ы бьiть нннцналнзнрован ы именами тех объектов, псевдонимами которых они будут являть- сЯ. double agent = .028; double &bond = agent; bond /= 4.0 // agent - .007 В общем случае в качестве инициализирующего выражения должно выступать имеющее значение L-выражение (имя объекта, реально существующего в памяти). Значением ссылкн после оп- ределения с инициализацией становится адрес этого объекта. Пo- вторное присвоение значения ссылке не допускается, т.е. невоз- можно сделать так, чтобы некоторая конкретная ссылка ссыла- лась на другой объект. В определении ссылки символ & не является частью типа, т.е. имя bond имеет тип doulэ 1е. Могут существовать ссылки на любые используемые в про- грамме типы, как стандартные, так и созданные программистом (записи, классы и т.п.), кроме перечисленных ниже. Функционально ссылка ведет себя подобно обычной пере- менной того же типа, а фактически является другой формой ука- зателя. Ссылки повышают эффективность программ при передаче больших объектов в функции, поскольку не требуют копирования объекта в стек; предоставляют функциям механизм изменения значения 56
используются, главным образом, при определении компо- нентных функций классов; — не являются самостоятельными объектами и существуют только после инициализации; какие-либо операции выполняются не над ссылками, а над объектами, на которые они ссылаются; int i; int &іг = i; ir = 3; // i = 3 int ј; ј = i * ir; // ј = 9 ip = &іг; // ip получает адрес i — не могут ссылаться на другую ссылку или на битовое по- ле. Не может быть ни массивов ссылок, ни указателей на ссылки (т.к. ссылка — это не самостоятельный объект), но может быть объявлена ссылка на указатель (поскольку указатель — са- мостоятельный объект). int *&rpi; // Ссылка на указатель Ссылка не может иметь тип vo id, для ссылки нельзя выде- лить участок памяти операцией new. Значение ссылки не может изменяться. Но любой объект может быть адресован любым ко- личеством ссылок (также как и указателей). Можно определить ссылку на константу, используя моди- фикатор const. Ссылка на константу не позволяет изменить зна- чение того объекта, с которым она связана. double agent = .028: const double &Bond = agent; agent 0.035; // правильно Bond .008; // ошибка Если тип инициализированной ссылки не совпадает с типом объекта, то создается временный анонимный объект, для кото- рого ссылка является псевдонимом, инициализирующее значение преобразуется к типу ссылки и используется для установки зна- чения анонимного объекта. 57 double d; in L а ir = d; // несовпадение типов => анонимный объект iг = Й « г ние d не изменилось, анонимный объект получил значение 3 Такая ситуация справедлива как для локальных или глобальных переменных, так и для аргументов функций, являющихся ссыл- ками. При передаче в функцию некоторой структуры данных (любого типа) по ссылке, в случае несовпадения типа и возмож- ности его преобразования (например, целый тип в действитель- ный тип или производный класс в базовый класс) внутри функ- ции создаётся временная безымянная структура данных требуе- мого типа, с которой и выполняются все предписанные програм- мой действия. Затем временная структура автоматически разру- шается при выходе из функции и её содержимое теряется. Со- стояние объекта, передававшегося в функции (фактического ар- гумента) остаётся неизменным. 58
Составные типы данных Download 1.98 Mb. Do'stlaringiz bilan baham: 
|