Освой самостоятельно С++ за 21 день.

Рис. 12.8. Вид связанного списка после того, как был добавлен второй промежуточный узел

В результате новый узел вновь будет вставлен в правильную позицию.

Если вы переписали эту программу И запустили на своем компьютере, то с помощью средства отладки можно посмотреть, как будет происходить ввод других данных программой. Каждый раз будет проводиться сравнение данных и новые узлы будут добавляться в список строго в порядке возрастания значений.

Что мы узнали в этой главе

В программах, рассмотренных выше, не осталось ничего от привычных нам процедурных программ. При процедурном программировании контрольный метод сравнивает данные и вызывает функцию. При объектно-ориентированном программировании каждый отдельный объект служит для выполнения ограниченного набора четко определенных задач. Так, связанный список отвечает за поддержание головного узла: Головной узел немедленно передает данные по адресу своего указателя, не анализируя ни передаваемые данные, ни адресуемый объект.

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

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

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

Кто же стоит над всем этим? В хорошо сконструированной объектно-ориентированной программе нет необходимости создавать какой-либо всеохватывающий объект контроля. Каждый объект выполняет свою маленькую партию, и результаты работы всех объектов сливаются в стройный хор.

Классы массивов

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

Можно разработать механизм сортировки или какого-либо другого упорядочения элементов массива либо использовать множество других эффективных вариантов массивов, наиболее популярны среди которых следующие:

• отсортированные коллекции: каждый член массива автоматически занимает свое определенное место;

• наборы: ни один из членов не повторяется в массиве дважды;

• словари: связанные пары элементов массива, где один член выполняет роль ключа для возвращения второго члена;

• разреженные массивы: допускается использование произвольных значений индексов, но в массив будут добавляться только реально существующие элементы. Так, можно ввести и использовать элемент с индексом SprseArray[5] или SpcseArray[2Q0], HO 3TO не значит, что в массиве реально существуют все элементы с меньшими индексами;

• мультимножества: неупорядоченные коллекции, члены которых добавляются и возвращаются в произвольном порядке.

Перегрузив оператор индексирования ([]), можно превратить связанный список в отсортированную коллекцию. Если добавить функцию отслеживания одинаковых членов, то отсортированная коллекция превратится в набор. Если все объекты списка связать попарно, то связанный список превратится в словарь или в разреженный массив.

Резюме

Сегодня вы узнали, как создавать массивы в C++. Массив представляет собой коллекцию объектов одинакового типа с фиксированным числом элементов.

Массивы никак не контролируют свой размер. Поэтому вполне возможно в программе заносить данные за пределы массива, что часто является причиной ошибок. Отсчет индексов массива начинается с 0. Часто допускаемой ошибкой является указание индекса n для массива с размером n.

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

Объекты массивов или все массивы целиком можно сохранять как в стековой области памяти, так и в области динамического обмена. Если удаляется объект из области динамической памяти, не забудьте установить квадратные скобки после ключевого слова delete[].

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

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

Строки представляют собой массивы символов. В C++ существуют дополнительные средства манипулирования текстовыми строками, включая возможность ввода в массив строки, взятой в двойные кавычки.

Вопросы и ответы

Что произойдет, если в массив из 24-х членов вписать значение для 25-го элемента?

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

Что представляют собой элементы неинициализированного массива?

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

Можно ли создавать комбинации массивов?

Да. Массив может содержать указатель на другой, более крупный массив. В случае работы со строками можно использовать некоторые стандартные функции, такие как strcat, чтобы создавать комбинации массивов символов.

Чем связанные списки лучше массивов?

Массивы всегда имеют фиксированный размер, тогда как размер связанного списка может изменяться динамически во время выполнения программы.

Всегда ли нужно в классе строк использовать указатель char * для сохранения содержимого строки?

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

Коллоквиум

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