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

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