246071-Либерти-Освой-самостоятельно-С-за-21-день (852741), страница 60
Текст из файла (страница 60)
Оператор += манипулирует суже существующими строками, как в случае string1 += string2. В этом примере оператор +=действует так же, как оператор суммирования, но значение временной строки tempприсваиваетсяненовой,атекущейстроке(*this=temp),каквстроке142.Функция main() (строки 145—175) выполняется для проверки результатов работы данногокласса.Встроке147создаетсяобъектStringспомощьюконструктора,задающегострокивстилеязыка С с концевым нулевым символом.
Строка 148 выводит содержимое этого объекта спомощью функции доступа GetString(). В строке 150 создается еще одна строка текста в стилеязыкаС.Встроке151тестируетсяперегруженныйоператорприсваивания,астрока152выводитрезультат.Встроке154создаетсятретьястрокасконцевымнулевымсимволом—tempTwo.Встроке155 с помощью функции strcpy() происходит заполнение буфера строкой символов nice to behere!. В строке 156 с помощью перегруженного оператора += осуществляется конкатенациястрокиtempTwoксуществующейстрокеs1.Результатвыводитсянаэкранвстроке158.Встроке160возвращаетсяивыводитсянаэкранпятыйсимволстроки—s1.Затемвстроке161этотсимволзамещаетсядругимспомощьюнеконстантногооператораиндексирования([]).Результатвыводитсястрокой162,чтобыпоказать,чтосимволстрокидействительноизменился.В строке 164 делается попытка получить доступ к символу за пределами массива.Возвращаетсяивыводитсянапечатьпоследнийсимволстроки,какибылопредусмотреноприперегрузкеоператораиндексирования.В строках 166 и 167 создаются два дополнительных объекта String, и в строке 168используетсяперегруженныйоператорсуммирования.Результатвыводитсястрокой169.В строке 171 создается еще один объект класса String — s4.
В строке 172 используетсяоператор присваивания, а строка 173 выводит результат. Оператор присваивания перегружентакимобразом,чтобыиспользоватьконстантнуюссылкуклассаString,объявленнуювстроке21,но в данном случае в функцию передается строка с концевым нулевым символом. Разве этодопустимо?Хотякомпилятор,ожидаяполучитьобъектString,вместоэтогополучаетмассивсимволов,он автоматически проверяет возможность преобразования полученного значения в ожидаемуюстроку.
В строке 12 объявляется конструктор, который создает объект String из массивасимволов. Компилятор создает временный объект String из полученного массива символов ипередает его в функцию оператора присваивания. Такой процесс называется неявнымпреобразованием. Если бы в программе не был объявлен соответствующий конструктор,преобразующий массивы символов, то для этой строки компилятор показал бы сообщение обошибке.СвязанныеспискиидругиеструктурыМассивы являются отличными контейнерами для данных самых разных типов.Единственныйихнедостатоксостоитвтом,чтоприсозданиимассиванеобходимоза-датьегофиксированный размер. Если на всякий случай создать слишком большой массив, то попустубудет потрачено много памяти компьютера.
Если сэкономить память, то возможностипрограммыпооперированиюданнымиокажутсяограниченными.Один из способов решения этой проблемы состоит в использовании связанных списков.Связанный список представляет собой структуру данных, состоящую из взаимосвязанныхблоков,каждыйизкоторыхможетподдерживатьструктурнуюединицуданных. Идея состоит в том, чтобы создать класс, поддерживающий объекты данныхопределенного типа, такого как CAT или Rectangle, которые, помимо данных, содержали бытакже указатели, связанные с другими объектами этого класса.
Таким образом, получаетсякласс,содержащийвзаимосвязанныеобъекты,образующиепроизвольнуюструктуру-список.Такие объекты называют узлами. Первый узел в списке образует голову, а последний —хвост.Существует три основных типа связанных списков. Ниже они перечислены в порядкеусложнения.•Однонаправленныесписки.•Двунаправленныесписки.•Деревья.Воднонаправленныхсвязанныхспискахкаждыйузелуказываетнаследующийузелтольководном направлении. Движение по узлам в обратном направлении невозможно. Чтобы найтинужныйузел,следуетначатьспервогоузлаидвигатьсяотузлакузлу,подобнокладоискателю,действующемусогласноуказаниямкартыпоискасокровищ:"...отбольшогокамняидикстаромудубу, сделай три шага на восток и начинай копать..." Двунаправленные списки позволяютосуществлять движение в обоих направлениях по цепи.
Деревья представляют собой болеесложные структуры, в которых один узел может содержать ссылки на два или три следующихузла.Всетритипасвязанныхсписковсхематичнопоказанынарис.12.5.ОбщиепредставленияосвязанныхспискахВданномразделеобсуждаютсяосновныемоментысозданиясложныхструктури,чтоещеболее важно, возможности использования в больших проектах наследования, полиморфизма иинкапсуляции.ДелегированиеответственностиОсновная идея объектно-ориентированного программирования состоит в том, что каждыйобъект специализируется в выполнении определенных задач и передает другим объектамответственность за выполнение тех задач, которые не соответствуют их основномупредназначению.Примеромреализацииэтойидеивтехникеможетбытьавтомобиль.Назначениедвигателя— вырабатывать свободную энергию. Распределение энергии уже не входит в круг задачдвигателя.
За это ответственна трансмиссия. И в конце концов, движение автомобиля за счетотталкивания от дороги осуществляется с помощью колес, а двигатель и трансмиссияпринимаютвэтомделесущественное,нокосвенноеучастие.Хорошо сконструированная машина состоит из множества деталей с четкимраспределением функций и структурным взаимодействием между ними, обеспечивающимрешениесложныхзадач.Такжедолжнавыглядетьхорошонаписаннаяпрограмма:каждыйклассвплетаетсвоюнить,аврезультатеполучаетсяшикарныйперсидскийковер.Рис.12.5.СвязанныеспискиКомпонентысвязанныхсписковСвязанный список состоит из узлов.
Узлы представляют собой абстрактные классы. Внашемпримередляпостроениясвязанногоспискаиспользуютсятриподтипаданных.Одинузелбудет представлять голову связанного списка и отвечать за его инициализацию. Попробуйтедогадаться сами, за что отвечает хвостовой узел. Между ними могут быть представлены (либомогутотсутствовать)одинилинесколькопромежуточныхузлов,которыеотвечаютзаобработкуданных,переданныхвсписок.Обратитевнимание,чтоданныеспискаисамсписок—этонеодноитоже.Вспискемогутбыть представлены данные любого типа, но связываются друг с другом не данные, а узлы,которыесодержатданные.Выполняемой части программы ничего не известно об узлах, она работает со связаннымсписком как с единым целым. В то же время функциональная нагрузка на список как таковойвесьма ограничена — он просто распределяет ответственность за выполнение задач междуузлами.В листинге 12.13 рассматривается пример программы со связанным списком, а затемдетальноанализируетсяееработа.Листинг12.13.Связанныйсписок0://**********************************************1://Листинг12.13.2://3://ЦЕЛЬ:Показатьиспользованиесвязанногосписка4://ПРИМЕЧАНИЯ:5://6://Авторскоеправо:Copyright(С)1998LibertyAssociates,Inc.7://Всеправазащищены8://9://Показанодинизподходовобьектно-ориентированного10://программированияпосозданиюсвязанныхсписков.11://Списокраспределяетзадачимеждуузлами,12://представляющимисобойабстрактныетипыданных.13://Списоксостоитизтрехузлов:головного,14://хвостовогоипромежуточного.Данныесодержит15://толькопромежуточныйузел.16://Всеобъекты,используемыевсписке,относятся17://кклассуData.18://**********************************************19:20:21:#include<iostream.h>22:23:enum{kIsSmaller,kIsLarger,kIsSame};24:25://СвязанныйсписокосновываетсянаобьектахклассаData26://Любойклассвсвязанномспискедолженподдерживатьдваметода:27://Show(отображениезначения)иCompare(возвращениеотносительнойпозицииузла)28:classData29:{30:public:31:Data(intval):myValue(val){}32:~Data(){}33:intCompare(constData&);34:voidShow(){cout<<myValue<<endl;}35:private:36:intmyValue;37:};38:39://Сравнениеиспользуетсядляопределения40://позициивспискедляновогоузла.41:intData::Compare(constData&theOtherData)42:{43:if(myValue<theOtherData.myValue)44:returnkIsSmaller;45:if(myValue>theOtherData.myValue)46:returnkIsLarger;47:else48:returnkIsSame;49:}50:51://Объявления52:classNode;53:classHeadNode;54:classTailNode;55:classInternalNode;56:57://ADT-представлениеузловыхобъектовсписка.58://ВкаждомпроизводномкласседолжныбытьзамещеныфункцииInsertиShow59:classNode60:{61:public:62:Node(){}63:virtual~Node(){}64:virtualNode*Insert(Data*theData)=0;65:virtualvoidShow()=0;66:private:67:};68:69://Этотузелподдерживаетреальныеобъекты.70://ВданномслучаеобъектимееттипData71://0другом,болееобщемметодерешенияэтой72://задачимыузнаемприрассмотрениишаблонов.73:classInternalNode:publicNode74:{75:public:76:InternalNode(Data*theData,Node*next);77:~InternalNode(){deletemyNext;deletemyData;}78:virtualNode*Insert(Data*theData);79:virtualvoidShow(){myData->Show();myNext->Show();}//Делегирование!80:81:private:82:Data*myData;//данныесписка83:Node*myNext;//указательнаследующийузелвсвязанномсписке84:};85:86://Инициализация,выполняемаякаждымконструктором87:InternalNode::InternalNode(Data*theData,Node*next):88:myData(theData),myNext(next)89:{90:}91:92://Сущностьсписка.93://Когдавсписокпередаетсяновыйобъект,94://программаопределяетпозициювсписке95://дляновогоузла96:Node*InternalNode::Insert(Data*theData)97:{98:99://Этотновенькийбольшеилименьшечемя?100:intresult=myData->Compare(*theData);101:102:103:switch(result)104:{105://Посоглашению,еслионтакойжекакя,тоонидетпервым106:casekIsSame://условиевыполняется107:casekIsLarger://новыеданныевводятсяпередмоими108:{109:InternalNode*dataNode=newInternalNode(theData,this);110:returndataNode;111:}112:113://Онбольшечемя,поэтомупередаетсяв114://следующийузел,ипустьтотделаетсэтимиданнымивсе,чтозахочет.115:casekIsSmaller:116:myNext=myNext->Insert(theData);117:returnthis;118:}119:returnthis;//появляетсяMSC120:}121:122:123://Хвостовойузелвыполняетрольчасового124:125:classTailNode:publicNode126:{127:public:128:TailNode(){}129:~TailNode(){}130:virtualNode*Insert(Data*theData);131:virtualvoidShow(){}132:133:private:134:135:};136:137://Еслиданныеподходятдляменя,тоонидолжныбытьвставленыпередомной,138://таккакяхвостиНИЧЕГОнеможетбытьпослеменя139:Node*TailNode::Insert(Data*theData)140:{141:InternalNode*dataNode=ewInternalNode(theData,this);142:returndataNode;143:}144:145://Головнойузелнесодержитданных,онтолько146://указываетнаначалосписка147:classHeadNode:publicNode148:{149:public:150:HeadNode();151:~HeadNode(){deletemyNext;}152:virtualNode*Insert(Data*theData);153:virtualvoidShow(){myNext->Show();}154:private:155:Node*myNext;156:};157:158://Кактолькосоздаетсяголовнойузел,159://онсоздаетхвост160:HeadNode::HeadNode()161:{162:myNext=newTailNode;163:}164:165://Ничегонеможетбытьпередголовой,поэтому166://любыеданныепередаютсявследующийузел167:Node*HeadNode::Insert(Data*theData)168:{169:myNext=myNext->Insert(theData);170:returnthis;171:}172:173://Ятолькораспределяюзадачимеждуузлами174:classLinkedList175:{176:public:177:LinkedList();178:~LinkedList(){deletemyHead;}179:voidInsert(Data*theData);180:voidShowAll(){myHead->Show();}181:private:182:HeadNode*myHead;183:};184:185://Списокпоявляетсяссозданиемголовногоузла,186://которыйсразусоздаетхвостовойузел.187://Такимобразом,пустойсписоксодержитуказательнаголовнойузел,188://указывающий,всвоюочередь,нахвостовойузел,междукоторымипоканичегонет.189:LinkedList::LinkedList()190:{191:myHead=newHeadNode;192:}193:194://Делегирование,делегирование,делегирование195:voidLinkedList::Insert(Data*pData)196:{197:myHead->Insert(pData);198:}199:200://выполняемаятестоваяпрограмма201:intmain()202:{203:Data*pData;204:intval;205:LinkedList11;206:207://Предлагаетпользователюввестизначение,208://котороепередаетсявсписок209:for(;;)210:{211:cout<<"Whatvalue?(0tostop):";212:cin>>val;213:if(!val)214:break;215:pData=newData(val);216:ll.Insert(pData);217:}218:219://теперьпройдемсяпоспискуипосмотримзначения220:ll.ShowAll();221:return0;//11выходитзаустановленныерамкиипоэтомуудалено!222:}Результат:Whatvalue?(0tostop)5Whatvalue?(0tostop)8Whatvalue?(0tostop)3Whatvalue?(0tostop)9Whatvalue?(0tostop)2Whatvalue?(0tostop)10Whatvalue?(0tostop)02358910Анализ: Первое, на что следует обратить внимание, — это константное перечисление, вкоторомпредставленыконстантыkIsSmaller,kIsLargerиkIsSame.Любойобъект,представленныйвсписке,долженподдерживатьметодCompare(').Константы,показанныевыше,возвращаютсяврезультатевыполненияэтогометода.Встроках28—37объявляетсяклассData,австроках39—49выполняетсяметодCompare().Объекты класса Data содержат данные и могут использоваться для сравнения с другимиобъектами класса Data.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
