mylist.insert (pointer_to_3, 5);
изменит наш список так:
1 1 2 3 5 8
Чтобы обеспечить подобную возможность, нам необходимо дать пользователю способ получения адреса определенного элемента. Одним из способов может быть использование функции find() – нахождение элемента с определенным значением:
pointer_to_3 = mylist.find( 3 );
find() принимает в качестве параметра значение из списка. Если элемент с таким значением найден, то возвращается его адрес, иначе find() возвращает 0.
Может быть два специальных случая вставки элемента: в начало и в конец списка. Для этого требуется только задание значения:
insert_front( value );
insert_end( value );
Предусмотрим следующие операции удаления элемента с заданным значением, первого элемента и всех элементов списка:
remove( value );
remove_front();
remove_all();
Функция 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. Это обеспечивается конструктором по умолчанию:
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();
Пока не будем позволять присваивать один список другому и инициализировать один список другим (впоследствии мы реализуем и это, причем такие изменения не потребуют модификации пользовательских программ). Объявим копирующий конструктор и копирующий оператор присваивания в закрытой части определения списка без их реализации. Теперь определение класса ilist выглядит таким образом:
class ilist {
public:
// определения не показаны
ilist();
int size();
// ...
private:
// запрещаем инициализацию
// и присваивание одного списка другому
ilist( const ilist );
ilist operator=( const ilist );
// данные-члены без изменения
};
Обе строки следующей программы вызовут ошибки компиляции, потому что функция main() не может обращаться к закрытым членам класса ilist:
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
