Язык программирования C++. Вводный курс. С для начинающих
 Скачать 5.41 Mb.
|
|
219 Функция display() распечатывает размер списка и все его элементы. Пустой список можно представить в виде: (0)( ) а список из семи элементов как: (7) ( 0 1 1 2 3 5 8 ) reverse() меняет порядок элементов на противоположный. После вызова mylist.reverse(); предыдущий список выглядит таким образом: (7) ( 8 5 3 2 1 1 0 ) Конкатенация добавляет элементы второго списка в конец первого. Например, для двух списков: (4)( 0 1 1 2 ) // listl (4)( 2 3 5 8 ) // list2 операция listl.concat( list2 ); превращает list1 в (8) ( 0 1 1 2 2 3 5 8 ) Чтобы сделать из этого списка последовательность чисел Фибоначчи, мы можем воспользоваться функцией remove(): listl.remove( 2 ); Мы определили поведение нашего списка, теперь можно приступать к реализации. Пусть список (list) и элемент списка (list_item) будут представлены двумя разными классами. (Ограничимся теми элементами, которые способны хранить только целые значения. Отсюда названия наших классов – ilist и ilist_item.) Наш список содержит следующие члены: _at_front – адрес первого элемента, _at_end – адрес последнего элемента и _size – количество элементов. При определении объекта типа ilist все три члена должны быть инициализированы 0. Это обеспечивается конструктором по умолчанию: С++ для начинающих 220 }; Теперь мы можем определять объекты типа ilist, например: ilist mylist; но пока ничего больше. Добавим возможность запрашивать размер списка. Включим объявление функции size() в открытый интерфейс списка и определим эту функцию так: inline int ilist::size() { return _size; } Теперь мы можем использовать: int size = mylist.size(); Пока не будем позволять присваивать один список другому и инициализировать один список другим (впоследствии мы реализуем и это, причем такие изменения не потребуют модификации пользовательских программ). Объявим копирующий конструктор и копирующий оператор присваивания в закрытой части определения списка без их реализации. Теперь определение класса ilist выглядит таким образом: }; Обе строки следующей программы вызовут ошибки компиляции, потому что функция main() не может обращаться к закрытым членам класса ilist: class ilist_item; class ilist { public: // конструктор по умолчанию ilist() : _at_front( 0 ), _at_end( 0 ), _size( 0 ) {} // ... private: ilist_item *_at_front; ilist_item *_at_end; int _size; class ilist { public: // определения не показаны ilist(); int size(); // ... private: // запрещаем инициализацию // и присваивание одного списка другому ilist( const ilist& ); ilist& operator=( const ilist& ); // данные-члены без изменения С++ для начинающих 221 } Следующий шаг – вставка элемента, для представления которого мы выбрали отдельный класс: }; Член _value хранит значение, а _next – адрес следующего элемента или 0. Конструктор ilist_item требует задания значения и необязательного параметра – адреса существующего объекта ilist_item. Если этот адрес задан, то создаваемый объект ilist_item будет помещен в список после указанного. Например, для списка 0 1 1 2 5 вызов конструктора ilist_item ( 3, pointer_to_2 ); модифицирует последовательность так: 0 1 1 2 3 5 Вот реализация ilist_item. (Напомним, что второй параметр конструктора является необязательным. Если пользователь не задал второй аргумент при вызове конструктора, по умолчанию употребляется 0. Значение по умолчанию указывается в объявлении функции, а не в ее определении; это поясняется в главе 7.) int main() { ilist yourlist( mylist ); // ошибка mylist = mylist; // ошибка class ilist_item { public: // ... private: int _value; ilist_item *_next; С++ для начинающих 222 } Операция insert() в общем случае работает с двумя параметрами – значением и адресом элемента, после которого производится вставка. Наш первый вариант реализации имеет два недочета. Сможете ли вы их найти? } Одна из проблем заключается в том, что указатель не проверяется на нулевое значение. Мы обязаны распознать и обработать такую ситуацию, иначе это приведет к краху программы во время исполнения. Как реагировать на нулевой указатель? Можно аварийно закончить выполнение, вызвав стандартную функцию abort(), объявленную в заголовочном файле cstdlib: abort(); Кроме того, можно использовать макрос assert(). Это также приведет к аварийному завершению, но с выводом диагностического сообщения: assert( ptr != 0 ); Третья возможность – возбудить исключение: class ilist_item { public: ilist_item( int value, ilist_-item *item_to_link_to = 0 ); // ... }; inline ilist_item:: ilist_item( int value, ilist_item *item ) : _value( value ) { if ( item ) _next = 0; else { _next = item->_next; item->_next = this; inline void ilist:: insert( ilist_item *ptr, int value ) { new ilist_item( value, ptr ); ++_size; #include // ... if ( ! ptr ) #include // ... С++ для начинающих 223 throw "Panic: ilist::insert(): ptr == O"; В общем случае желательно избегать аварийного завершения программы: в такой ситуации мы заставляем пользователя беспомощно сидеть и ждать, пока служба поддержки обнаружит и исправит ошибку. Если мы не можем продолжать выполнение там, где обнаружена ошибка, лучшим решением будет возбуждение исключения: оно передает управление вызвавшей программе в надежде, что та сумеет выйти из положения. Мы же поступим совсем другим способом: рассмотрим передачу нулевого указателя как запрос на вставку элемента перед первым в списке: insert_front( value ); Второй изъян в нашей версии можно назвать философским. Мы реализовали size() и _size как пробный вариант, который может впоследствии измениться. Если мы преобразуем функции size() таким образом, что она будет просто пересчитывать элементы списка, член _size перестанет быть нужным. Написав: ++_size; мы тесно связали реализацию insert() с текущей конструкцией алгоритма пересчета элементов списка. Если мы изменим алгоритм, нам придется переписывать эту функцию, как и insert_front(), insert_end() и все операции удаления из списка. Вместо того чтобы распространять детали текущей реализации на разные функции класса, лучше инкапсулировать их в паре: inline void ilist::bump_down_size() { --_size; } Поскольку мы объявили эти функции встроенными, эффективность не пострадала. Вот окончательный вариант insert(): } if ( ! ptr ) if ( ! ptr ) inline void ilist::bump_up_size() { ++_size; } inline void ilist:: insert( ilist_item *ptr, int value ) if ( !ptr ) insert_front( value ); else { bump_up_size(); new ilist_item( value, ptr ); } С++ для начинающих 224 Реализация функций insert_front() и insert_end() достаточно очевидна. В каждой из них мы должны предусмотреть случай, когда список пуст. } find() ищет значение в списке. Если элемент с указанным значением найден, возвращается его адрес, иначе find() возвращает 0. Реализация find()выглядит так: } Функцию find() можно использовать следующим образом: mylist.insert( ptr, some_value ); или в более компактной записи: inline void ilist:: insert_front( int value ) { ilist_item *ptr = new ilist_item( value ); if ( !_at_front ) _at_front = _at_end = ptr; else { ptr->next( _at_front ); _at_front = ptr; } bump_up_size(); } inl-ine void ilist:: insert_end( int value ) { if ( !_at_end ) _at_end = _at_front = new ilist_item( value ); else _at_end = new ilist_item( value, _at_end ); bump_up_s-ize(); ilist_item* ilist:: find( int value ) { ilist_item *ptr = _at_front; while ( ptr ) { if ( ptr->value() == value ) break; ptr = ptr->next(); } return ptr; ilist_item *ptr = mylist.find( 8 ); С++ для начинающих 225 mylist.insert( mylist.find( 8 ), some_value ); Перед тем как тестировать операции вставки элементов, нам нужно написать функцию display() , которая поможет нам при отладке. Алгоритм display() достаточно прост: печатаем все элементы, с первого до последнего. Можете ли вы сказать, где в данной реализации ошибка? cout << iter->value(); Список – это не массив, его элементы не занимают непрерывную область памяти. Инкремент итератора ++iter; вовсе не сдвигает его на следующий элемент списка. Вместо этого он указывает на место в памяти, непосредственно следующее за данным элементом, а там может быть все что угодно. Для изменения значения итератора нужно воспользоваться членом _next объекта ilist_item : iter = iter->_next; Мы инкапсулировали доступ к членам ilist_item набором встраиваемых функций. Определение класса ilist_item теперь выглядит так: }; Вот определение функции display(), использующее последнюю реализацию класса ilist_item : // не работает правильно! for ( ilist_item *iter = _at_front; // начнем с первого iter != _at_end; // пока не последний ++iter ) // возьмем следующий cout << iter->value() << ' '; // теперь напечатаем последний class ilist_item { public: ilist_item( int value, ilist_item *item_to_link_to = 0 ); int value() { return _value; } iilst_item* next() { return _next; } void next( ilist_item *link ) { _next = link; } void value( int new_value ) { _value = new_value; } private: int _value; ilist_item *_next; С++ для начинающих 226 } Тестовую программу для нашего класса ilist в его текущей реализации можно представить таким образом: #include // ... }; void ilist:: display( ostream &os ) { os << "\n( " << _size << " )( "; ilist_item *ptr = _at_front; while ( ptr ) { os << ptr->value() << " "; ptr = ptr->next(); } os << ")\n"; С++ для начинающих 227 } Результат работы программы: Ok: после insert_front() и insert_end() (20)( 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 ) Ищем значение 8: нашли? да! Вставка элемента 1024 после 8 ( 21 )( 9 8 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 ) Удалено 2 элемент(ов) со значением 8 ( 19 )( 9 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 ) Удален первый элемент ( 18 )( 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 ) Удалены все элементы ( 0 )( ) #include #include "ilist.h" int main() { ilist mylist; for ( int ix = 0; ix < 10; ++ix ) { mylist.insert_front( ix ); mylist.insert_end( ix ); } cout << "Ok: после insert_front() и insert_end()\n"; mylist.display(); ilist_item *it = mylist.find( 8 ); cout << "\n" << " Ищем значение 8: нашли?" << ( it ? " да!\n" : " нет!\n" ); mylist.insert( it, 1024 ); cout << "\n" << " Вставка элемента 1024 после 8\n"; mylist.display(); int elem_cnt = mylist.remove( 8 ); cout << "\n" << " Удалено " << elem_cnt << " элемент(ов) со значением 8\n"; mylist.display(); cout << "\n" << " Удален первый элемент\n"; mylist.remove_front(); mylist.display(); cout << "\n" << " Удалены все элементы\n"; mylist.remove_all(); mylist.display(); С++ для начинающих 228 Помимо вставки элементов, необходима возможность их удаления. Мы реализуем три таких операции: int remove( int value ); Вот как выглядит реализация remove_front(): } remove_all() вызывает remove_front() до тех пор, пока все элементы не будут удалены: } Общая функция remove() также использует remove_front() для обработки специального случая, когда удаляемый элемент (элементы) находится в начале списка. Для удаления из середины списка используется итерация. У элемента, предшествующего удаляемому, необходимо модифицировать указатель _next. Вот реализация функции: void remove_front(); void remove_all (); inline void i1ist:: remove_front() { if ( _at_front ) { ilist_item *ptr = _at_front; _at_front = _at_front->next(); bump_down_size() ; delete ptr; } void ilist:: remove_all() { while ( _at_front ) remove_front(); _size = 0; _at_front = _at_end = 0; С++ для начинающих 229 } Следующая программа проверяет работу операций в четырех случаях: когда удаляемые элементы расположены в конце списка, удаляются все элементы, таких элементов нет или они находятся и в начале, и в конце списка. 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; С++ для начинающих 230 #include #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"; С++ для начинающих 231 } Результат работы программы: ----------------------------------------------- тест #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() содержит ошибку. Сможете ли вы ее найти? } Проблема состоит в том, что теперь два объекта ilist содержат последовательность одних и тех же элементов. Изменение одного из списков, например вызов операций insert() и remove(), отражается на другом, приводя его в рассогласованное состояние. Простейший способ обойти эту проблему – скопировать каждый элемент второго списка. Сделаем это при помощи функции insert_end(): 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; С++ для начинающих 232 } Вот реализация функции reverse(): } Тестовая программа для проверки этих операций выглядит так: void ilist:: concat( const ilist &i1 ) { i1ist_item *ptr = i1._at_front; while ( ptr ) { insert_end( ptr->value() ); ptr = ptr->next(); } 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 ); С++ для начинающих 233 } Результат работы программы: ( 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 ) С одной стороны, задачу можно считать выполненной: мы не только реализовали все запланированные функции, но и проверили их работоспособность. С другой стороны, мы не обеспечили всех операций, которые необходимы для практического использования списка. Одним из главных недостатков является то, что у пользователя нет способа перебирать элементы списка и он не может обойти это ограничение, поскольку реализация от него скрыта. Другим недостатком является отсутствие поддержки операций инициализации одного списка другим и присваивания одного списка другому. Мы сознательно не стали их реализовывать в первой версии, но теперь начнем улучшать наш класс. Для реализации первой операции инициализации необходимо определить копирующий конструктор. Поведение такого конструктора, построенного компилятором по умолчанию, совершенно неправильно для нашего класса (как, собственно, и для любого класса, содержащего указатель в качестве члена), именно поэтому мы с самого начала #include #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(); |