Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

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(Щ.


Вопросы и задания для самоконтроля

1. 
   К какой группе структур данных относятся автоматиче-
   

ские массивы?

2. 
   К какой группе структур данных относятся статические массивы?
   
3. 
   К какой группе структур данных относятся динамиче-
   

ские массивы?

4. 
   По каким признакам можно классифицировать двумер- ный динамический массив?
   
5. 
   Можно ли изменить размер динамического массива в процессе его использования?
   

54

6. 
   Можно ли использовать один и тот же указатель для создания в разные моменты времени динамических массивов разного размера?
   
7. 
   В чем заключается связь между указателями и массива-
   

мИ?

8. 
   Какие операции обязательны при работе с динамиче-
   

скими массивами?

9. 
   Перечислите основные свойства динамических масси-
   

10. 
    В чем заключается отличие между автоматическими и статическими массивами?
    
11. 
    Какое требование нужно соблюдать при присваивании адреса массива указателю?
    
12. 
    Какие ограничения накладываются на определение многомерных динамических массивов?
    
13. 
    В чем заключается отличие между именем массива и указателем?
    
14. 
    Что представляют собой строки?
    
15. 
    Какие существуют способы организации строк?
    

55

4. 
   Ссылки. Временные структуры данных
   

В языках Си и Си++ возможны ситуации появления времен- ных структур данных — как переменных стандартных типов, так и более сложных: экземпляров записей (структурных типов) и объ- ектов классов. Такими ситуациями являются, в частности, несов- падение типов операндов в арифметических операциях и несов- падение типов в формальных и фактических аргументах функ-

Ссылки в языке Си++ представляют собой второе имя ( няп псевдоним) объекта; объявляются при помощи символа &, 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

4. 
   Составные типы данных
   

1.