С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 39

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 39)

Мы реализуем триvoid remove_front();void remove_all ();таких операции:int remove( int value );inline voidi1ist::remove_front(){if ( _at_front ) {ilist_item *ptr = _at_front;_at_front = _at_front->next();bump_down_size() ;delete ptr;}Вот как выглядит реализация remove_front():}remove_all() вызывает remove_front() до тех пор, пока все элементы не будутvoid ilist::remove_all(){while ( _at_front )remove_front();_size = 0;_at_front = _at_end = 0;удалены:}Общая функция remove() также использует remove_front() для обработкиспециального случая, когда удаляемый элемент (элементы) находится в начале списка.Для удаления из середины списка используется итерация. У элемента, предшествующегоудаляемому, необходимо модифицировать указатель _next. Вот реализация функции:228С++ для начинающихint ilist::remove( int value ){ilist_item *plist = _at_front;int elem_cnt = 0;while ( plist && plist->value() == value ){plist = plist->next();remove_front();++elem_cnt;}if ( ! plist )return elem_cnt;ilist_item *prev = plist;plist = plist->next();while ( plist ) {if ( plist->value() == value ) {prev->next( plist->next() );delete plist;++elem_cnt;bump_down_size();plist = prev->next();if ( ! plist ) {_at_end = prev;return elem_cnt;}}else {prev = plist;plist = plist->next();}return elem_cnt;}Следующая программа проверяет работу операций в четырех случаях: когда удаляемыеэлементы расположены в конце списка, удаляются все элементы, таких элементов нетили они находятся и в начале, и в конце списка.229#include <iostream>#include "ilist.h"int main()С++{ для начинающихilist mylist;cout << "\n-----------------------------------------------\n"<< "тест #1: - элементы в конце\n"<< "-----------------------------------------------\n";mylist.insert_front( 1 ); mylist.insert_front( 1 );mylist.insert_front( 1 );my1ist.insert_front( 2 ); mylist.insert_front( 3 );my1ist.insert_front( 4 );mylist.display();int elem_cnt = mylist.remove( 1 );cout << "\n" << "Удалено " << elem_cnt<< " элемент(ов) со значением 1\n";mylist.display();mylist.remove_all();cout << "\n-----------------------------------------------\n"<< "тест #2: - элементы в начале\n"<< "-----------------------------------------------\n";mylist.insert_front( 1 ); mylist.insert_front( 1 );mylist.insert_front( 1 );mylist.display();elem_cnt = mylist.remove( 1 );cout << "\n" << "Удалено " << elem_cnt<< " элемент(ов) со значением 1\n";mylist.display();mylist.remove_all () ;cout << "\n-----------------------------------------------\n"<< "тест #3: - элементов нет в списке\n"<< "-----------------------------------------------\n";mylist.insert_front( 0 ); mylist.insert_front( 2 );mylist.insert_front( 4 );mylist.display();elem_cnt = mylist.remove( 1 );cout << "\n" << "Удалено " << elem_cnt<< " элемент(ов) со значением 1\n";mylist.display();mylist.remove_all () ;cout << "\n-----------------------------------------------\n"<< "тест #4: - элементы в конце и в начале\n"<< "-----------------------------------------------\n";my1ist.insert_front( 1 ); mylist.insert_front( 1 );my1ist.insert_front( 1 );my1ist.insert_front( 0 ); mylist.insert_front( 2 );my1ist.insert_front( 4 );mylist.insert_front( 1 ); my1ist.insert_front( 1 );mylist.insert_front( 1 );mylist.display() ;elem_cnt = mylist.remove( 1 );cout << "\n" << "Удалено " << elem_cnt<< " элемент(ов) со значением 1\n";230С++ для начинающих}Результат работы программы:----------------------------------------------тест #1: - элементы в конце----------------------------------------------( 6 )( 4 3 2 1 1 1 )Удалено 3 элемент(ов) со значением 1( 3 )( 4 3 2 )----------------------------------------------тест #2: - элементы в начале----------------------------------------------( 3 )( 1 1 1 )Удалено 3 элемент(ов) со значением 1( 0 )( )----------------------------------------------тест #3: - элементов нет в списке----------------------------------------------( 3 )( 4 2 0 )Удалено 0 элемент(ов) со значением 1( 3 )( 4 2 0 )----------------------------------------------тест #4: - элементы в конце и в начале----------------------------------------------(9 )( 1 1 1 4 2 0 1 1 1 )Удалено 6 элемент(ов) со значением 1( 3 )( 4 2 0 )Последние две операции, которые мы хотим реализовать, – конкатенация двух списков(добавление одного списка в конец другого) и инверсия (изменение порядка элементов напротивоположный).

Первый вариант concat() содержит ошибку. Сможете ли вы ееvoid ilist::concat( const ilist &i1 ) {if ( ! _at_end )_at_front = i1._at_front;else _at_end->next( i1._at_front );_at_end = i1._at_end;найти?}Проблема состоит в том, что теперь два объекта ilist содержат последовательностьодних и тех же элементов. Изменение одного из списков, например вызов операцийinsert() и remove(), отражается на другом, приводя его в рассогласованное состояние.Простейший способ обойти эту проблему – скопировать каждый элемент второго списка.Сделаем это при помощи функции insert_end():231С++ для начинающихvoid ilist::concat( const ilist &i1 ){i1ist_item *ptr = i1._at_front;while ( ptr ) {insert_end( ptr->value() );ptr = ptr->next();}}voidilist::reverse(){ilist_item *ptr = _at_front;ilist_item *prev = 0;_at_front = _at_end;_at_end = ptr;while ( ptr != _at_front ){ilist_item *tmp = ptr->next();ptr->next( prev );prev = ptr;ptr = tmp;}_at_front->next( prev );Вот реализация функции reverse():}Тестовая программа для проверки этих операций выглядит так:232С++ для начинающих#include <iostream>#include "ilist.h"int main(){ilist mylist;for ( int ix = 0; ix < 10; ++ix ){ mylist.insert_front( ix ); }mylist.display();cout << "\n" << "инвертирование списка\n";mylist.reverse(); mylist.display();ilist mylist_too;mylist_too.insert_end(0); mylist_too.insert_end(1);mylist_too.insert_end(1); mylist_too.insert_end(2);mylist_too.insert_end(3); mylist_too.insert_end(5);cout << "\n" << "mylist_too:\n";mylist_too.display();mylist.concat( mylist_too );cout << "\n"<< "mylist после concat с mylist_too:\n";mylist.disp1ay();}Результат работы программы:( 10 ) ( 9 8 7 6 5 4 3 2 1 0 )инвертирование списка( 10 ) ( 0 1 2 3 4 5 6 7 8 9 )mylist_too:( 6 )( 0 1 1 2 3 5 )mylist после concat с mylist_too:( 16 ) ( 0 1 2 3 4 5 6 7 8 9 0 1 1 2 3 5 )С одной стороны, задачу можно считать выполненной: мы не только реализовали всезапланированные функции, но и проверили их работоспособность.

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

Лучше уж полностью лишить пользователя какой-либооперации, чем допустить возможные ошибки. (В разделе 14.5 объясняется, почемудействия копирующего конструктора по умолчанию в подобных случаях неверны.) Вотilist::ilist( const ilist &rhs ){ilist_item *pt = rhs._at_front;while ( pt ) {insert_end( pt->value() );pt = pt->next();}реализация конструктора, использующая функцию insert_end():}Оператор присваивания должен сначала вызвать remove_all(), а затем с помощьюinsert_end() вставить все элементы второго списка. Поскольку эта операцияvoid ilist::insert_all ( const ilist &rhs ){ilist_item *pt = rhs._at_front;while ( pt ) {insert_end( pt->value() );pt = pt->next();}повторяется в обеих функциях, вынесем ее в отдельную функцию insert_all():}inline ilist::ilist( const ilist &rhs ): _at_front( 0 ), _at_end( 0 ){ insert_all ( rhs ); }inline ilist&ilist::operator=( const ilist &rhs ) {remove_all();insert_all( rhs );return *this;после чего копирующий конструктор и оператор присваивания можно реализовать так:}Теперь осталось обеспечить пользователя возможностью путешествовать по списку,например с помощью доступа к члену _at_front:ilist_item *ilist::front() { return _at_front(); }После этого можно применить ilist_item::next(), как мы делали в функциях-членах:234С++ для начинающихilist_item *pt = mylist.front();while ( pt ) {do_something( pt->value() );pt = pt->next();}Хотя это решает проблему, лучше поступить иначе: реализовать общую концепциюпрохода по элементам контейнера.

Характеристики

Список файлов книги