|
Нелинейные коллекции
Иерархическая коллекция – набор элементов, разделенных на уровни. Элементны на текущем уровне могут иметь несколько связанных элементов на нижнем уровне. Особой иерархической коллекцией является дерево, в которой на верхнем уровне имеется один эелемент – корень. Элементы в дереве называют узлами, каждый из которых указывает на нисходящие узлы, называемыми потомками. Каждый элемент, за исключением корня имеет одного потомка. Дерево является идеальной структурой для описания файловой системы с каталогами и подкаталогами.
Группа – представляет те коллекции, которые содержат элементы без упорядочивания. Набор переменных в программе – яркий пример группы.
39
Сюда можно отнести граф – структуру, задающую набор вершин и набор связей, соединяющих вершины. Графы широко используются в планировании, транспортных задачах и в задачах проектирования. Сеть – особая форма графа, которая приписывает вес каждой связи. Вес указывает стоимость использования связи при прохождения графа. Так в задаче коммивояжера используется сеть для представления городов и стоимостей проезда из города в город.
Тема «Создание класса для работы со строками»
Существует много способов определения строк . Основные из них : использование строковых констант, использование массивов типа char, использование указателей типа char.
Строковая константа - любая последовательность символов, заключенная в двойные кавычки. Заключенные в кавычки символы и автоматически добавляемый к ним компилятором завершающий символ \0 сохраняется в памяти в качестве символьной строки. Например:
#define STR " Строковая константа" Массивы символьных строк и инициализация.
При определении массива символьных строк компилятору необходимо сообщить, сколько места требуется для его хранения. Один из способов этого
инициализация массива с помощью строковой константы. Следующее объявление инициализирует внешний массив m1 символами указанной строки:
char m1[ ] = " Инициализация массива "
Это сокращенная форма стандартной формы инициализации массива :
char m1[ ] = { ‘И’, ’н’, ‘и’, ‘ц’, ‘и’, ‘а’, ‘л’, ‘и’, ‘з’, ‘а’, ‘ц’, ‘и’, ‘я’, ‘ ‘, ‘м’, ‘а’, ‘с’, ‘с’, ‘и’, ‘в’, ‘а’, ‘\0’ };
Обратите внимание на завершающий символ нуля. Без него мы получили бы массив символов, а не строку. При использовании любой формы ( но лучше первую) компилятор подсчитывает количество символов и в соответствии с этим определяет размер массива.
Например, можно использовать следующее объявление:
char
char
*m3 = " Использование указателя"; m3[ ] = " Использование массива";
40
Оба объявления говорят, что m3 - указатель на данную строку. В обоих случаях сама эта строка определяет объем памяти, который должен быть выделен для строки. Тем не менее, эти две формы не идентичны.
Сравнение представлений в форме массива и указателя.
Так в чем же состоит различие между представлениями в форме
массива и указателя?Формамассива
|
( m3[ ]) приводит к созданию
|
массива, состоящего из 24 элементов( по
|
одному для каждого символа
|
плюс один элемент для завершающего символа ‘\0 ’ ), в статической памяти. Каждый элемент инициализируется соответствующим символом. Отсюда следует, что компилятор будет распознавать имя m3 в качестве синонима адреса элемента массива, &m3[0]. Важно отметить, что в представлении в форме массива m3 - адресная константа. m3 нельзя изменять, поскольку это бы означало изменение ячеек памяти, в которых хранится массив. Для
идентификации следующего элемента массива
|
можно использовать
|
операции типа m3 + 1.
|
|
Представление в форме указателя (*m3) также приводит к резервированию в статической памяти места для 24 элементов строки. Кроме
того, еще одна ячейка резервируется для переменной указателя
|
m3.
|
Первоначально эта переменная указывает на первый символ строки,
|
но
|
значение может быть изменено. Следовательно, можно использовать операцию приращения.
И
|
н
|
и
|
ц
|
и
|
а
|
л
|
и
|
з
|
а
|
ц
|
и
|
я
|
|
м
|
а
|
с
|
с
|
и
|
в
|
а
|
\0
|
\0
|
\0
|
Рис 8 представление строки в ячейках памяти
языке С большинство операций со строками в действительности работают с указателями. Рассмотрим несколько строк кода:
char *mesg = " Don’t be a fool";
char *copy;
copy = mesg;
Сама строка никуда не копировалась. Оператор copy = mesg; всего лишь создает второй указатель, который указывает на ту же строку.
co
|
|
D
|
|
o
|
|
n
|
|
‘
|
|
t
|
|
|
|
b
|
|
e
|
|
|
|
a
|
|
|
|
f
|
|
o
|
|
o
|
|
l
|
|
\0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
py
mesg
Рис 9 Создание второго указателя.
Почему бы просто не скопировать всю строку? Что эффективнее : скопировать один адрес, или скажем 50 отдельных элементов? Часто для выполнения задачи достаточно получить только адрес.
41
Создадим шаблон класса «строка». Он содержит одно поле - указатель на строку ( *s). В классе выполняются методы: определение длины строки, копирование части строки, печать строки, поиск указанного символа.
Методы:
Do'stlaringiz bilan baham: |
