Лекции по информатике (984119), страница 2
Текст из файла (страница 2)
Итак, приступим к программированинл итераторов. Сначала, опишем тип элементов двунаправленного списка, указываемых итераторами; Итератор, как было отмечено выше, всего лишь указывает па некоторый элемент. Упакуем ссылку на, элемент в запись, чтобы предотвратить исгюльзование таких (определенных по умолчанию) операций ссылочного типа, как проверка на равенство, разыменование и, особенно для С,'С вЂ” , '+, инкремент и декремент. Дело в том, что оператор инкремента (орегаСог++~ в Си определен для любого указателя, и он возвращает указатель с адресом, на в1хеоГ( л ) большим исходного.
Суре 1Сегасог гесогс1 пос1е: Р1Сеш; епс1; Сурес1еГ вСгпсС 1Сепи пос1е: 1 1Сегасог; Такое решение уже применялось вьппе при обходе массива, но ясно. что просто так увеличивать адрес и таким образом получить следующий элемспт стлта нельзя, поскольку эти элементы совершенно необязательно хранятся в памяти последовательно.
Более того, в случае дош ой и интенсивной работы программы со списком адреса вновь создаваемых компонент могут быть мелльиле уже существующих и не могут быть получены путем обычной инкрементации. "1'еперь, следуя функциональной спецификации, опишем функции сравнения двух итераторов на равенство и неравенство. Два итератора считан)тс1я равными тогда и только тогда, когда указывают на один и тот же элемент: Ьоо! Ес1па1(сопвС 1Сегагог~ 1Ьа, сопвС 1Сегасогэ гЬе) геСпгп 1Ьа —.:-Ьос1е ---- гЬэ — >пос1е; и неравными во всех остальных случаях: 1эоо1 ХоСЕс1па1(сопвС 11ега1ог, 1Ьгч сопвС 11егагог~ гЬэ) КппсС1оп ХоСЕс1па1(айаг 1Ьа, гЬв: 1Сегагог : Ьоо1еап; 246 Суре Р11с гп 1Сеп1 11сггг гесогс1 рта: Р1гегп; пехС: Р1Сепц <1аСа: Т; епс1; ГппсС1оп Ес1па!(наг 1Ье, гЬе: 1гегаСог) Ьоо1еап: Ьеп1п Ес1па1:- - 1Ьа.
гюс1е гЬэ.пос1е; епс1; вСгпсС 1Сеш вСгпсС Иепл* ргет', вСгпсС 1Сеш* пехг; '1' с1аса; Ь Ьеиш ЪМЕс1па!: -- поС Ес1па1(11!я, г1гя); епс1; геСпгп ! К<1па1(Ъя, г1гя); Введение УоЖс1иа1О может показаться избыточным, но оно не только проясняет условия ветвлений и циклов,. особенно в Си, но и упрощает эти условия, удаляя из них один унарный опера,тор. Функция ЖегвСО продвигает итсратор к следующему элементу списка. Чтобы не загроможчать эту функцию защитным кодом. ,проверок легитимности предпринимаемой операции не осуществляется. '1ем не менее, правильная организация списка (например, кольцевание) позволит предотвратить обращение по неопределенному адресу. Целостность списка и навигация по нему не нарушатся. СппсС1оп ХехС1уаг 1: 1СегаСог) 1СегаСог; Ьеи1п 1 . пос1е: — 1. пос1е" .пехС; ХехС:— еш1; 1Сегагог г'1ехС(11егаСогя 1) 1 — >пос1е -- ! — >пос1е — >пехС; геСпгп 1; Функция Ргев() является зеркальным отражением функции ЖсхС(): СппсС1оп Ргеу(уаг 1: 1СегаСог) 1СегаСог; Ьеиш 1.пос1с: — 1.пос1с .ргсу; Ргсу: — 1: епс1; 1СегаСог Ргеу(1Сегасога 1) ( 1 — >пос1е -- 1 — >пос1е — >ргеу; геСпгп 1; СппсС1оп Гесс1г!уаг 1: 1Сегагог): Т; Ьеи1п Гегс1г: — 1.
пос1е".с1ага; епс1; Т ГеСс1г(сопяС 1Сегагог~ 1) ( геСпгп ! — >пос1е — >с1ага: Противоположная для ГеСс1г() функция .5Соге() позволяет записать данные в элемент списка. ргосес1ше ВСоге(уаг1: 1СегаСог; С: Т); Ьеиш уоЫ 8!осе(сопяС 1СегаСог~ 1, сопяС Т С) 247 Функция ГеСссг() нужна для чтения элемента списка, на который указывает итсратор. Хотя итератор может указывать на терминатор, никакой проверки этого факта функция не осуществляет. Защитные действия загромождая)т код, снижают производительность и не являются абсолютно надежными, и поэтому все проверки должен осуществлять пользователь.
Впрочем, это нетрудно, т. к. терминатор используется лишь с одной целью указывать на конец списка. 1.пос1е".с1аСа г 1; епс1; > — >г>ос!с> — >с1а!а 5.6.3.2 Реализация на динамических структурах Подобно тому, .как это было сделано в реализации очереди, соединим начало и конец списка. Поскольку список двунаправленный., каждый его элемент содержит ровно по две ссылки: на предыдущий и на последующий элементы списка. Воспользуемся этим, создав фиктивный элемент списка терминатор. Его указате.сь иехС будет ссылаться на ггервый элемент списка (если он есть, в противном случае на терминатор), а ргег — на последний значащий элемент списка (опять-таки, если он есть).
Такой подход позволит сократить количсство указателей, организун>щих список, до минимально возможного -- всего 1. Посредством этой единственной ссылки и осуществляс тся лн>бой доступ к списку. Сначала обращаемся к терминатору, через него, в свою очередь, к первому и последнему элементам списка, а через них строго последовательно и к остальным. Еще одно достоинство подхода заключается в том, что при ошибочном применении операции АгехСО к итератору, указывающему на терминатор, с последующей записью значения в несуществующий элемент, оно будет занесено в очередной элемент закольцованного списка, не испортив какую-либо другую область памяти, в частности, не нарушив саму списковую структуру.
Итак. описание структуры типа список содержит всего две переменные: указатель на фиктивный элемент — голову-хвост списка и его дл>шу: Суре !лэ1,: — гесогс1 1>еас1: Р11еш; а1ие: шСеиег; епс1; Сурес1еГ вСгпсС ( !Сепи 1>еас1; шС а1ие; 1,>вс; Функция Сгеаге() выделяет г>вмять под терминатор, создает пустой кольцевой список путем присваивания компонентам ргее и иехС значения указателя на терминатор и устанавливает равной О длину списка. ргосес1пге Сгеаге(>гаг 1: !.1эС): С>еи1п пеж (1. 1>еас1): 1. 1>сас!".рген: — 1.аеас!; !,Ьас!".>>ехС: - !.аеас!; 1. а!хе: — О; епс1; >со!с! Г ~гсаге(! 1аС* 1) 1 — > 1>еас! — п>а!!ос(в1кеоГ(вСгпсС 1Сеп>) 1 — >1>еас! — >пех1 =- 1 — >1>еас! — >рте> 1 — >1>еас1; 1 —..
э17е О; 248 Изменяя функциональность итераторов путем запрещения функций Гс1с6() или огоге() можно полу"сить списки пюяъко с>ля ч>пения или только для, записи подобно тому, как это сдела,но при помснци свойств 1ргорегСгсз) в средс Ве1р1>1. Аналогично описанным п1>ясиьсм итераторам, можно дополнительно определить обрагг>нъсе итераторы, которые позволят пройти список с последнего элемента, до первого, полностью сохраняя семантику и идиомы прямых итераторов.
Функция Еггв?() создает итератор из ссыло шой компоненты псх1 терминатора списка. Мы определили итератор как запись, и функция Гггв?() получилась нескалярной, что ограничивает сферу ее использования расширенными версиями языка Паскаль. Впрочем, существует стандартный рецепт скаляризации функции структурного типа, когда возвращается не объект, а ссылка на него. Функция Лаз?() создает итератор из указателя на терминатор списка. 11ега1ог; По построению списка он пуст, если итераторы начала и конца совпадают. Функция Я?се() вссто лишь возвращает хранимый размер списка.
В качестве альтернативы функция могла бы вычислять длину путем перебора элементов списка с начала и до встречи с терминатором. ?п1 В!хе(сопв1 Ь!в1~ 1) ге1пгп 1 — >в!хе; Функция 1ивег1() согласно спецификации вставляет элемент в список перед заданным. Сначала функция запрашивает память и в случае неуспеха этой операции возвращает итератор, указывающий на терминатор. В случае успеха результатом функции является 249 Гппс1юп Еггв1(чаг 1: 1.Ь1); 11егагог чаг гев: 11ега1ог; Ьеи?п гев.пос1е: - 1.?геас?".ггех1; Г!гв1: - гев; епс1; Гппс1юп Ьав1(чаг 1: Ь1в1) чаг гев: 11ега1ог; Ьеиш гев .
пос1е: - — 1. ?геас?; 1ав1: - гев; епс1; Гпггс1юп Етр1,у(чаг 1: ?йв1): Ьоо1еап: чаг ?в1, !в1: 11ега?ог: Ьеиш Ь1;-- Епв1(1): 1в1: — Ьав1 (! ); Егпр1у: Ес!па1(Ь1, ! в1): епс1; Гппс1?оп %хе(чаг 1: Ь!в1 ): ?п1еиег; Ьеиш о!хе г- 1. в!хе; епс1; 11ега1ог Е!гв1 (сопв1 1йв1* 1) 11ега1ог гев -- ( 1 — >?геас! — >пех1 ); ге1игп гев; 11егасог Ьав1(сопв1 Ь1в1~ 1) 11,ега1ог гев -- ( 1 — >Ьеас1 ): ге1пгп гсв: Ьоо! Ешр1у(сопв1 1йв1* Ц ( 1!егагог Ь1 Г1гв1(!); 11ега!ог 1в1 — !,аэ1(!); ге1пгп Ес?па!(1с?в1, ьс1в1); итс ратор, указывающий на, добавленный элемент.
Приведем графическуло иллюстрацию процесса вставки элемента Щ: У этой функции есть потенциальный недостаток, связанный с отсутствием проверки принадлежности указуеъюго итератором э:лемента списку, поэтому программист должен быть более анима,тельным, передавая аргументы этой функции. Впрочем, вставка нс по своему итс,ратору не приведет к катастрофе, но вот значсние,члины станет неактуальным. Вычисление длины перебором списка вместо получения ее текуп!его значения, ассоциированного со списком, устраняет проблему.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
