246071-Либерти-Освой-самостоятельно-С-за-21-день (852741), страница 61
Текст из файла (страница 61)
Они также поддерживают метод Show(), отображающий значениеобъектаклассаData.Чтобы лучше разобраться в работе связанного списка, проанализируем шаг за шагомвыполнение программы, показанной выше. В строке 201 объявляется выполняемый блокпрограммы, в строке 203 — указатель на класс Data, а в строке 205 определяется связанныйсписок.Для создания связанного списка в строке 189 вызывается конструктор. Единственное, чтоон делает, — выделяет области памяти для объекта HeadNode и присваивает адрес объектауказателю,поддерживаемомусвязаннымспискомиобъявленномувстроке182.ПрисозданииобъектаHeadNodeвызываетсяещеодинконструктор,объявленныйвстроках160—163,который,всвоюочередь,создаетобъектTailNodeиприсваиваетегоадресуказателюmyNext, содержащемуся в объекте HeadNode. При создании объекта TailNode вызываетсяконструкторTailNode,объявленныйвстроке128.Телоконструкторасодержитсявтойжестрокепрограммы,ионнесоздаетникакихновыхобъектов.Такимобразом,созданиесвязанногоспискавызываетпоследовательностьвзаимосвязанныхпроцессов, в результате которых для него выделяется область стековой памяти, создаютсяголовной и хвостовой узлы и устанавливаются взаимосвязи между ними, как показано на рис.12.6.Встроке209начинаетсябесконечныйцикл.Появляетсяпредложениепользователюввестизначение,котороебудетдобавленовсвязанныйсписок.Вводновыхзначенийможнопродолжатьдо бесконечности.
Ввод значения 0 завершает цикл. Введенное значение проверяется в строке213.Есливведенноезначениеотличаетсяот0,товстроке215создаетсяновыйобъекттипаData,австроке216онвводитсявсвязанныйсписок.Предположим,чтопользовательввелчисло15,послечеговстроке195будетвызванметодInsert.Рис.12.6.СвязанныйсписоксразупослесозданияСвязанный лист немедленно передаст ответственность за ввод объекта головному узлу,вызваввстроке167методInsert.Головнойузелнемедленноделегируетответственностьлюбомудругомуузлу(вызываетвстроке139методInsert),адрескоторогохранитсявуказателеmyNext.Сначала в этом указателе представлен адрес хвостового узла (вспомните, что при созданииголовногоузлаавтоматическисоздаетсяхвостовойузелиссылкананегодобавляетсявголовнойузел).Хвостовому узлу TailNode известно, что любой объект, переданный обращениемTailNode::Insert, нужно добавить в список непосредственно перед собой.
Так, в строке 141создается объект InternalNode, который добавляется в список перед хвостовым узлом ипринимает введенные данные и указатель на хвостовой узел. Эта процедура выполняется спомощьюобъявленноговстроке87конструктораобъектаInternalNode.Конструктор объекта InternalNode просто инициализирует указатель класса Data адресомпереданногообъектаэтогокласса,атакжеприсваиваетуказателюmyNextэтогообъекта адрес того узла, из которого он был передан. В случае создания первогопромежуточногоузлаэтомууказателюбудетприсвоенадресхвостовогоузла,поскольку,каквыпомните,именнохвостовойузелпередалсвойуказательthis.Теперь, после того как был создан узел InternalNode, адрес этого узла присваиваетсяуказателю dataNode в строке 141, и именно этот адрес возвращается теперь методомTailNode::Insert().ТакмывозвращаемсякметодуHeadNode::Insert(),гдеадресузлаInternalNodeприсваивается указателю myNext узла HeadNode (строка 169).
И наконец, адрес узла HeadNodeвозвращаетсявсвязанныйсписок—туда,гдевстроке197онбылсброшен(ничегострашногоприэтомнепроизошло,таккаксвязанномуспискуужебылизвестенадресголовногоузла).Зачембылобеспокоитьсяовозвращенииадреса,еслионнеиспользуется?МетодInsertбылобъявленвбазовомклассеNode.Длявыполненияметоданеобходимозадатьзначениевозврата.Если изменить значение возврата функции HeadNode::Insert(), то компилятор покажетсообщение об ошибке. Это все равно что возвратить узел HeadNode и позволить связанномуспискувыброситьегоадрес.Так что же все-таки произошло? Данные были введены в список. Список передал этиданные головному узлу.
Головной узел передал их дальше по тому адресу, что хранится в егоуказателе. В первом цикле в этом указателе хранился адрес хвостового узла. Хвостовой узелнемедленно создает новый промежуточный узел, указателю которого присваивается адресхвостового узла. Затем хвостовой узел возвращает адрес промежуточного узла в головной узел,где он присваивается указателю myNext головного узла. Итак, свершилось то, что требовалось:данныерасположилисьвспискеправильнымобразом(рис.12.7).После ввода первого промежуточного узла программа переходит к строке 211 и выводитпредложение пользователю ввести новое значение.
Предположим, что в этот раз было введенозначение3.Врезультатевстроке215создаетсяновыйобъектклассаDataивводитсявсписоквстроке216.Рис.12.7.Видсвязанногоспискапослетого,какбылдобавленпервыйпромежуточныйузелИ вновь в строке 197 список передает новое значение в головной узел HeadNode. МетодHeadNode: :Insert(), в свою очередь, передает эти данные по адресу, хранящемуся в указателеmyNext. Как вы помните, теперь он указывает на узел, содержащий объект типа Data созначением15.Врезультатевстроке96вызываетсяметодInternalNode::Insert().Встроке100 указатель myData узла InternalNode сообщает объекту этого узла (значение которогосейчасравно15)онеобходимостивызватьметодCompare(),принимающийвкачествеаргумеи'тановыйобъектDataсозначением3.МетодCompare()объявленвстроке41.Происходит сравнение значений двух объектов, и, поскольку значение myValueсоответствует 15, а theOtherData.myValue равно 3, метод возвращает константу kIsLarget.
Bсоответствии со значением возвращенной константы программа переходит к выполнениюстроки109.СоздаетсяновыйузелInternalNodeдляновогообъектаданных.Новыйузелбудетуказыватьна текущий объект узла InternalNode, и адрес нового узла InternalNode возвращается методомInternalNode:;Insert() в головной узел HeadNode. Таким образом, новый узел, значение которогоменьше значения текущего объекта, добавляется в связанный список, после чего связанныйсписоквыглядиттак,какпоказанонарис,12.8.Натретьем цикле пользователь ввел значение 8. Оно больше чем 3, но меньше чем 15,поэтому программа должна ввести новый объект данных между двумя существующимипромежуточными узлами.
Последует та же серия операций, что и в предыдущем цикле, за темисключением,чтопривызовеметодаCompare()дляобъектатипаData,значениекото-рогоравно3, будет вОзвращена константа kIsSmaller, а не kIsLarger, как в предыдущем случае (посколькузначениетекущегообъекта3меньшезначенияновогообъекта8).В результате метод InternalNode::Insert() переведет выполнение программы на строку 116.Вместосозданияивводавсписокновогоузла,новыеданныебудутпереданывметодInsertтогообъекта, на который ссылается указатель myNext текущего объекта. В данном случае будетвызванметодInsertNodeдляпромежуточногоузла,значениеобъектакоторогоравняется15.Вновьбудетпроведеносравнениеданных,котороевэтотраззавершитсясозданиемновогопромежуточного узла.
Этот новый узел будет ссылаться на тот промежуточный узел, значениекоторого15,аадресновогоузлабудетприсвоенуказателюузласозначением3,какпоказановстроке116.Рис.12.8.Видсвязанногоспискапослетого,какбылдобавленвторойпромежуточныйузелВрезультатеновыйузелвновьбудетвставленвправильнуюпозицию.Если вы переписали эту программу И запустили на своем компьютере, то с помощьюсредства отладки можно посмотреть, как будет происходить ввод других данных программой.Каждый раз будет проводиться сравнение данных и новые узлы будут добавляться в списокстроговпорядкевозрастаниязначений.ЧтомыузналивэтойглавеВ программах, рассмотренных выше, не осталось ничего от привычных нам процедурныхпрограмм. При процедурном программировании контрольный метод сравнивает данные ивызывает функцию.
При объектно-ориентированном программировании каждый отдельныйобъектслужитдлявыполненияограниченногонаборачеткоопределенныхзадач.Так,связанныйсписокотвечаетзаподдержаниеголовногоузла:Головнойузелнемедленнопередаетданныепоадресусвоегоуказателя,неанализируянипередаваемыеданные,ниадресуемыйобъект.Хвостовой узел создает новые узлы и добавляет их в список, если они содержат данные.Хвостовомуузлуизвестно,чтоеслиновыеобъектысодержаткакие-тоданные,тоонидолжнырасполагатьсявспискедонего.Промежуточные узлы выполняют более сложные функции.
Они обращаются к своимтекущимобъектамисравниваютихзначениясозначенияминовыхобъектов.Взависимостиотрезультатасравнения,онилибовставляютобъектыпередсобой,либопередаютихдругомуузлу.Обратите внимание, что промежуточные узлы сами по себе не имеют никакогопредставленияоданныхобъектовиотом,какихсравнивать.Сравнениевыполняетсяметодами,вызываемымиобъектами.Все,зачтоотвечаетпромежуточныйузел,—этообращениексвоемуобъекту с требованием вызвать метод сравнения текущего значения с новым переданнымзначением. В зависимости от того, какую константу возвратит метод сравнения, узел либодобавляетобъектыпередсобой,либопередаетихдругомуузлу,небеспокоясьотом,чтобудетсэтимобъектомдальше.Кто же стоит над всем этим? В хорошо сконструированной объектно-ориентированнойпрограмменетнеобходимостисоздаватькакой-либовсеохватывающийобъектконтроля.Каждыйобъект выполняет свою маленькую партию, и результаты работы всех объектов сливаются встройныйхор.КлассымассивовПо сравнению с использованием встроенных массивов написание собственного классамассивовдаетрядпреимуществ.Так,можноразработатьсистемуконтролязавводомданныхвмассив для предупреждения ошибок или создать класс массива, динамически изменяющийразмер.Присозданиимассивможетсодержатьтолькоодинэлемент,постепенноприрастаяпомеревыполненияпрограммы.Можноразработатьмеханизмсортировкииликакого-либодругогоупорядоченияэлементовмассива либо использовать множество других эффективных вариантов массивов, наиболеепопулярнысредикоторыхследующие:• отсортированные коллекции: каждый член массива автоматически занимает своеопределенноеместо;•наборы:ниодинизчленовнеповторяетсявмассиведважды;• словари: связанные пары элементов массива, где один член выполняет роль ключа длявозвращениявторогочлена;•разреженныемассивы:допускаетсяиспользованиепроизвольныхзначенийиндексов,новмассив будут добавляться только реально существующие элементы.
Так, можно ввести ииспользовать элемент с индексом SprseArray[5] или SpcseArray[2Q0], HO 3TO не значит, что вмассивереальносуществуютвсеэлементысменьшимииндексами;• мультимножества: неупорядоченные коллекции, члены которых добавляются ивозвращаютсявпроизвольномпорядке.Перегрузив оператор индексирования ([]), можно превратить связанный список вотсортированную коллекцию. Если добавить функцию отслеживания одинаковых членов, тоотсортированная коллекция превратится в набор. Если все объекты списка связать попарно, тосвязанныйсписокпревратитсявсловарьиливразреженныймассив.РезюмеСегодня вы узнали, как создавать массивы в C++.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
