С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 38
Текст из файла (страница 38)
Одним из способов может бытьиспользование функции find() – нахождение элемента с определенным значением:pointer_to_3 = mylist.find( 3 );find() принимает в качестве параметра значение из списка. Если элемент с такимзначением найден, то возвращается его адрес, иначе find() возвращает 0.Может быть два специальных случая вставки элемента: в начало и в конец списка. Дляinsert_front( value );этого требуется только задание значения:1nsert_end( value );Предусмотрим следующие операции удаления элемента с заданным значением, первогоremove( value );remove_front();элемента и всех элементов списка:remove_all();218С++ для начинающихФункция 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. Это обеспечиваетсяконструктором по умолчанию:219С++ для начинающих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;};Теперь мы можем определять объекты типа ilist, например:ilist mylist;но пока ничего больше.
Добавим возможность запрашивать размер списка. Включимобъявление функции size() в открытый интерфейс списка и определим эту функциютак:inline int ilist::size() { return _size; }Теперь мы можем использовать:int size = mylist.size();Пока не будем позволять присваивать один список другому и инициализировать одинсписок другим (впоследствии мы реализуем и это, причем такие изменения не потребуютмодификации пользовательских программ). Объявим копирующий конструктор икопирующий оператор присваивания в закрытой части определения списка без ихclass ilist {public:// определения не показаныilist();int size();// ...private:// запрещаем инициализацию// и присваивание одного списка другомуilist( const ilist& );ilist& operator=( const ilist& );// данные-члены без измененияреализации.
Теперь определение класса ilist выглядит таким образом:};Обе строки следующей программы вызовут ошибки компиляции, потому что функцияmain() не может обращаться к закрытым членам класса ilist:220С++ для начинающихint main(){ilist yourlist( mylist ); // ошибкаmylist = mylist;// ошибка}Следующий шаг – вставка элемента, для представления которого мы выбрали отдельныйclass ilist_item {public:// ...private:int_value;ilist_item *_next;класс:};Член _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.)221С++ для начинающихclass ilist_item {public:ilist_item( int value, ilist_-item *item_to_link_to = 0 );// ...};inlineilist_item::ilist_item( int value, ilist_item *item ): _value( value ){if ( item )_next = 0;else {_next = item->_next;item->_next = this;}Операция insert() в общем случае работает с двумя параметрами – значением иадресом элемента, после которого производится вставка.
Наш первый вариантinline voidilist::insert( ilist_item *ptr, int value ){new ilist_item( value, ptr );++_size;реализации имеет два недочета. Сможете ли вы их найти?}Одна из проблем заключается в том, что указатель не проверяется на нулевое значение.Мы обязаны распознать и обработать такую ситуацию, иначе это приведет к крахупрограммы во время исполнения. Как реагировать на нулевой указатель? Можноаварийно закончить выполнение, вызвав стандартную функцию abort(), объявленную в#include <cstdlib>// ...if ( ! ptr )заголовочном файле cstdlib:abort();Кроме того, можно использовать макрос assert(). Это также приведет к аварийному#include <cassert>// ...завершению, но с выводом диагностического сообщения:assert( ptr != 0 );Третья возможность – возбудить исключение:222С++ для начинающих223if ( ! ptr )throw "Panic: ilist::insert(): ptr == O";В общем случае желательно избегать аварийного завершения программы: в такойситуации мы заставляем пользователя беспомощно сидеть и ждать, пока службаподдержки обнаружит и исправит ошибку.Если мы не можем продолжать выполнение там, где обнаружена ошибка, лучшимрешением будет возбуждение исключения: оно передает управление вызвавшейпрограмме в надежде, что та сумеет выйти из положения.Мы же поступим совсем другим способом: рассмотрим передачу нулевого указателя какif ( ! ptr )запрос на вставку элемента перед первым в списке:insert_front( value );Второй изъян в нашей версии можно назвать философским.
Мы реализовали size() и_size как пробный вариант, который может впоследствии измениться. Если мыпреобразуем функции size() таким образом, что она будет просто пересчитыватьэлементы списка, член _size перестанет быть нужным. Написав:++_size;мы тесно связали реализацию insert() с текущей конструкцией алгоритма пересчетаэлементов списка. Если мы изменим алгоритм, нам придется переписывать эту функцию,как и insert_front(), insert_end() и все операции удаления из списка. Вместо тогочтобы распространять детали текущей реализации на разные функции класса, лучшеinline void ilist::bump_up_size(){ ++_size; }инкапсулировать их в паре:inline void ilist::bump_down_size() { --_size; }Поскольку мы объявили эти функции встроенными, эффективность не пострадала.
Вотinline voidilist::insert( ilist_item *ptr, int value )if (!ptr )insert_front( value );else{bump_up_size();new ilist_item( value, ptr );}окончательный вариант insert():}С++ для начинающихРеализация функций insert_front() и insert_end() достаточно очевидна. В каждойinline voidilist::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 voidilist::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();из них мы должны предусмотреть случай, когда список пуст.}find()ищет значение в списке.
Если элемент с указанным значением найден,ilist_item*ilist::find( int value ){ilist_item *ptr = _at_front;while ( ptr ){if ( ptr->value() == value )break;ptr = ptr->next();}return ptr;возвращается его адрес, иначе find() возвращает 0. Реализация find()выглядит так:}ilist_item *ptr = mylist.find( 8 );Функцию find() можно использовать следующим образом:mylist.insert( ptr, some_value );или в более компактной записи:224С++ для начинающихmylist.insert( mylist.find( 8 ), some_value );Перед тем как тестировать операции вставки элементов, нам нужно написать функциюdisplay(), которая поможет нам при отладке.
Алгоритм display() достаточно прост:печатаем все элементы, с первого до последнего. Можете ли вы сказать, где в данной// не работает правильно!for ( ilist_item *iter = _at_front; // начнем с первогоiter != _at_end;// пока не последний++iter )// возьмем следующийcout << iter->value() << ' ';// теперь напечатаем последнийреализации ошибка?cout << iter->value();Список – это не массив, его элементы не занимают непрерывную область памяти.Инкремент итератора++iter;вовсе не сдвигает его на следующий элемент списка. Вместо этого он указывает на местов памяти, непосредственно следующее за данным элементом, а там может быть все чтоугодно. Для изменения значения итератора нужно воспользоваться членом _next объектаilist_item:iter = iter->_next;Мы инкапсулировали доступ к членам ilist_item набором встраиваемых функций.class ilist_item {public:ilist_item( int value, ilist_item *item_to_link_to = 0 );intvalue() { 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;Определение класса ilist_item теперь выглядит так:};Вот определение функции display(), использующее последнюю реализацию классаilist_item:225С++ для начинающих226#include <iostream>class ilist {public:void display( ostream &os = cout );// ...};void ilist::display( ostream &os ){os << "\n( " << _size << " )(";ilist_item *ptr = _at_front;while ( ptr ) {os << ptr->value() << " ";ptr = ptr->next();}os << ")\n";}Тестовую программу для нашего класса ilist в его текущей реализации можнопредставить таким образом:С++ для начинающих#include <iostream>#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();}Результат работы программы: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 )( )227С++ для начинающихПомимо вставки элементов, необходима возможность их удаления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
