1.2. Операции обработки списка

Основными операциями обработки списка являются:

1. включение ( вставка ) в список нового элемента перед или после заданного элемента ( в том числе перед первым элементом или после последнего ); включению, как правило, предшествует поиск элемента после и/или перед которым происходит включение; при включении элемента перед первым в список без заглавного звена меняется заголовок списка; при включении после некоторого элемента меняется ссылочное поле у элемента, после которого происходит включение, поэтому надо определять ссылку на элемент после которого происходит включение;

2. исключение ( удаление ) заданного элемента из списка ( в том числе удаление первого элемента или последнего ); исключению, как правило, предшествует поиск, исключаемого элемента; результатом поиска должна быть ссылка на элемент предшествующий исключаемому, так как при удалении элемента из списка меняется ссылочное поле у элемента, предшествующего удаляемому; при удалении первого элемента в списке без заглавного звена меняется заголовок списка;

3. поиск заданного элемента по его значению или порядковому номеру; операция заканчивается, когда элемент найден или просмотрен весь список (если элемента нет); результат операции должен определять, есть ли элемент в списке или нет и, если есть, то возможно его адрес или значение;

4. определение числа звеньев списка;

5) упорядочение элементов списка по значению информационного поля.

Чтобы описать набор операций абстрактного типа данных список на языке C++, требуется определить класс, который будет интерфейсом взаимодействия со списками и в котором эти операции будут объявлены как методы класса.

Все операции по работе со списком сосредоточены внутри описания класса, так что при программировании задач обработки списков можно будет пользоваться этим классом.

1.3. Создание класса для работы со списком

Листинг 1: Определение класса IntList

файл intlist.h

class IntList {

/* Класс ListItem представляет элемент списка, связанный со следующим с помощью указателя, содержащегося в поле next */

struct ListItem

{

int item; // значение элемента списка

Listltem *next; // указатель на следующий элемент списка

// Конструктор для создания нового элемента

ListItem(int i, Listltem *n = NULL) { item = i; next = n; }

};

int count; // счетчик числа элементов

ListItem *first; // первый элемент списка

ListItem *last; // последний элемент списка

public :

// Конструктор по умолчанию - создание пустого списка

IntLis() { count = 0; first = last = NULL; }

// Конструктор копирования - создание копии имеющегося списка

IntList(const IntList & src);

// Деструктор списка

~IntLis() ;

// Доступ к первому элементу списка

int head() const { return first->item; }

int & head() { return first->item; }

// Доступ к последнему элементу списка

int tail() const { return last->item; }

int & tail() { return last->item; }

// Добавить один элемент в начало списка

void addFirst(int item);

// Добавить один элемент в конец списка

void addLast(int item);

// Добавить элементы другого списка в конец этого

void addLast(const IntList & src) ;

// Удалить первый элемент

int removeFirst();

// количество элементов списка

int getCount() { return count; }

}; // Конец определения класса IntList