Хороший стиль программирования

15.1. Используя операцию new проверьте, не вернула ли она нулевой указатель. Выполните соответствующую обработку ошибки, если операция new не выделила область памяти.

15.2. Когда память, которая динамически выделена операцией new, более не требуется, используйте операцию delete для немедленного освобождения памяти.

15.3. Присваивайте нулевое значение (0) указателю элементу нового узла. Указатели должны быть инициализированы перед тем, как они используются.

Советы по повышению эффективности

15.1. Можно объявить размер массива таким, чтобы он мог вместить большее число элементов, чем ожидается. Но это может привести к избыточному расходу памяти. Связные списки могут обеспечивать более рациональное использование памяти. Связные списки позволяют программе настраиваться во время счета.

15.2. Операции вставки и удаления в отсортированном массиве могут быть продолжительными по времени, так как все элементы, следующие за вставляемым или удаляемым, должны быть соответствующим образом сдвинуты.

15.3. Элементы массива хранятся в памяти непрерывно (по соседству друг с другом). Это предоставляет возможность мгновенного доступа к любому элементу массива, поскольку адрес любого элемента может быть вычислен непосредственно путем определения его позиции по отношению к началу массива. Связные списки не предоставляют возможности д-пя такого мгновенного доступа к своим элементам.

15.4. Использование вместо массивов динамического распределения памяти для структур данных, которые могут увеличиваться или уменьшаться во время счета, способствует экономному использованию ресурсов памяти. Однако имейте ввиду, что указатели занимают некоторое место в памяти и что динамическое распределение приводит к нерациональному использованию памяти при обращениях к функциям.

Замечания по мобильности

15.1. Размер объектов класса не обязательно равен сумме своих данных-элементов. Это происходит из-за различных машинно-зависимых требований по выравниванию границ областей памяти (см. главу 16) и по другим причинам.

Упражнения для самопроверки

15.1. Заполнить пробелы в следующих утверждениях:

e) Очередь относится к структуре данных типа .

f) Указатель на следующий узел в связном списке называется

g) Для освобождения динамически выделенной памяти используется операция .

h) является частным случаем связного списка, в котором

узлы могут быть помещены только в конец списка, а удалены только из его начала.

i) является нелинейной двумерной структурой данных, в

которой узлы имеют по два или более указателей связи.

j) Стек относится к структурам данных типа , поскольку последний помещенный в него узел удаляется первым.

к) Узлы дерева включают два элемента связи.

1) Первый узел дерева называется узлом.

т) Каждая связи в дереве указывает на или

данного узла.

п) Узел дерева, который не имеет узлов-потомков, называется или узлом.

о) Четыре алгоритма обхода дерева двоичного поиска, которые были

упомянуты в главе, называются соответственно , ,

и .

15.2. Какие существуют различия между связным списком и стеком?

15.3. Какие существуют различия между стеком и очередью?

15.4. Возможно наиболее подходящим названием для этой главы было бы Повторно используемые структуры данных . Поясните, каким образом каждый из нижеперечисленных объектов и понятий способствуют повторному использованию структур данных:

a) классы

b) шаблоны классов

c) наследование

d) скрытое наследование

e) композиция.

a) Класс с используется для создания динамических

структур данных, которые могут увеличиваться или уменьшаться во время выполнения программы.

b) Операция используется для динамического выделения

памяти. Эта операция возвраш;ает указатель на выделенную память.

с) является частным случаем связного списка, в котором

узлы могут вставляться и удаляться только из его вершины. Эта структура данных возвращает значения в узлах по принципу последним вошел - первым вышел (LIFO).

d) Функция, которая не меняет связный список, а просто его просматривает и определяет, не является ли он пустым, называется

11 19 32 44 69 72 92 99

Рис. 15.19. Дерево двоичного поиска с 12-тью узлами

Ответы на упражнения для самопроверки

15.1. а) с самоадресацией; Ь) new; с) стек; d) предикат, предикатная функция; е) первым вошел - первым вышел (FIFO); f) указателем связи; g) delete; h) очередь; i) дерево; j) последним вошел - первым вышел (LIFO); к) бинарного; 1) корневым; т) узел-потомок, поддерево; п) листом дерева, концевым; о) последовательный (симметричный) обход, обход в ширину (прямой обход), обратный обход, послойный обход.

15.2. В связном списке можно помещать узел в любое место списка и удалять узлы из любого места списка. Узлы в стеке могут быть помещены только в его вершину, а удалены только из вершины стека.

15.3. Очередь имеет указатели на головной элемент и на хвост очереди, так что узлы могут быть помещены только в конец (хвост) очереди, а удалены только из ее начала (головы). Стек имеет единственный указатель на вершину стека и только в ней выполняются операция вставки и удаления узла.

15.4. а) Классы позволяют нам создавать столько объектов структур данных определенного типа (т.е. классов), сколько нам необходимо.

b) Шаблоны класса позволяют нам создавать связные классы, каждый из которых базируется на различных типах параметров, и мы можем создавать столько объектов каждого шаблона класса, сколько нам необходимо.

c) Наследование позволяет нам повторно использовать код базового класса для производного класса, причем структуры данных производного класса также являются структурами данных базового класса (с открытым интерфейсом).

d) Скрытое наследование позволяет повторно использовать часть кода базового класса для создания структуры данных производного класса; поскольку это наследование является скрытым, то открытые функции-элементы базового класса становятся закрытыми в производном класса. Это, в свою очередь, препятствует произвольному доступу объектов производного класса к таким функциям-элементам базового класса, которые в производном классе не применяются.

15.5. Осуществите вручную последовательный обход, обход в ширину и обратный обход дерева двоичного поиска, приведенного на рис. 15.19.