Упорядоченные списки

 

Класс SeqList создаёт список, элементы которого добавляются в хвост. В результате получается неупорядоченный список. Однако во многих приложениях требуется списковая структура с таким условием включения, при котором элементы запоминаются в некотором порядке. В этом случае приложение сможет эффективно определять наличие того или иного элемента в списке, а также выводить элементы в виде отсортированных последовательностей.

Чтобы создать упорядоченный список, мы используем класс SeqList в качестве базового и образуем на его основе класс OrderedList, который вставляет элементы в возрастающем порядке с помощью оператора “<”. Это пример наследования в действии. Мы предопределяем только метод Insert, поскольку все другие операции не влияют на упорядочение и могут быть наследованы от базового класса.

 

Спецификация класса OrderedList.

 

объявление

#include “seqlist2.h”

 

template <class T>

class OrderedList: public SeqList<T>

{

public:

//конструктор

OrderedList (void);

 

//подменить метод Insert для формирования упорядоченного списка

virtual void Insert (const t& item);

};

описание

 

Все операции за исключением Insert, взяты из SeqList, так как они не влияют на упорядочение. Поэтому должен быть объявлен только метод Insert, чтобы подменить одноимённый метод из SeqList. Эта функция сканирует список и включает в него элементы, сохраняя порядок.

Класс OrderedList находится в файле ordlist.h.

 

 

Реализация класса OrderedList

 

В классе OrderedList определяется конструктор, который просто вызывает конструктор класса SeqList. Тем самым инициализируется этот базовый класс, а он в свою очередь инициализирует свой базовый класс List. Мы имеем пример трёх-классовой иерархической цепи.

//конструктор. инициализировать базовый класс

template <class T>

OrderedList:: OrderedList (void): SeqList<T>()

{}

В этом классе определяется новая функция Insert, которая включает элементы в подходящее место списка. Новый метод Insert использует встроенный в класс LinkedList механизм поиска первого элемента, большего, чем включаемый элемент. Метод InsertAt используется для включения в связанный список нового узла в текущем месте. Если новое значение больше, чем все имеющиеся, оно дописывается в хвост списка. Метод Insert отвечает за обновление переменной size, определённой в базовом классе List.

//вставить элемент в список в возрастающем порядке

template <class T>

void OrderedList:: Insert (const T& item)

{

//использовать механизм прохождения связанных списков

//для обнаружения места вставки

for (llist.Reset();!llist.EndOfList(); llist/Next() }

if (item<llist.Data())

break;

//вставить item в текущем месте

llist.InsertAt (item);

size++;

}

 

Приложение: длинные последовательности. Обсудим методику фильтрации (предварительной обработки) данных для получения более длинных последовательностей.

Предположим, что большой блок данных храниться в случайном порядке в массиве или на диске. Тогда эти данные можно представить в виде ряда коротких последовательностей. Например, следующее множество их 15-и символов состоит из восьми последовательностей.

CharArray: [a k] [g] [c m t] [e n] [l] [c r s] [c b f]

Попытка использовать сортировку слиянием для упорядочения этих данных была бы тщетной ввиду значительного числа коротких последовательностей, подлежащих объединению. В нашем примере четыре слияния дают следующие последовательности.

[a g k] [c e m t] [c l r s] [b c f]

Сортировка слиянием предписывает объединить на следующем проходе эти четыре последовательности в две и затем создать полностью отсортированный список. Алгоритм работал бы лучше, если бы изначально последовательности имели разумную длину. Этого можно достичь путём сканирования элементов и объединения их в отсортированные подсписки. Алгоритм внешней сортировки должен противостоять относительно медленному времени доступа к диску и включает в себя фильтр для предварительной обработки данных. Мы должны постараться, чтобы время, затраченное на фильтрацию данных, повышало бы общую эффективность алгоритма.

Упорядоченный список является примером простого фильтра. Предположим, что исходный массив или файл содержит N элементов. Мы вставляем каждую группу из k элементов в некоторый упорядоченный список, а затем копируем этот список обратно в массив. Этот фильтр гарантирует, что последовательности будут иметь длину, по крайней мере, k. Например, пусть k=5, и мы обрабатываем данные массива CharArray. Тогда результат будет таким:

[a c q k m] [c e l n t] [b c f r a]