C++ для начинающих

-----------------------------------------------

тест #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():

void ilist::

concat( const ilist i1 )

{

i1ist_item *ptr = i1._at_front;

while ( ptr ) {

insert_end( ptr-value() );

ptr = ptr-next();

}

}

Вот реализация функции reverse():

void

ilist::

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 );

}

Тестовая программа для проверки этих операций выглядит так:

#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 )

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

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

Для реализации первой операции инициализации необходимо определить копирующий конструктор. Поведение такого конструктора, построенного компилятором по умолчанию, совершенно неправильно для нашего класса (как, собственно, и для любого класса, содержащего указатель в качестве члена), именно поэтому мы с самого начала запретили его использование. Лучше уж полностью лишить пользователя какой-либо операции, чем допустить возможные ошибки. (В разделе 14.5 объясняется, почему действия копирующего конструктора по умолчанию в подобных случаях неверны.) Вот реализация конструктора, использующая функцию insert_end():

ilist::ilist( const ilist rhs )

{

ilist_item *pt = rhs._at_front;

while ( pt ) {

insert_end( pt-value() );

pt = pt-next();

}

}

Оператор присваивания должен сначала вызвать remove_all(), а затем с помощью insert_end() вставить все элементы второго списка. Поскольку эта операция повторяется в обеих функциях, вынесем ее в отдельную функцию insert_all():