Совет по повышению эффективности 15.4

Использование вместо массивов динамического распределения памяти для структур данных, которые могут увеличиваться или уменьшаться во время счета, способствует экономному использованию ресурсов памяти. Однако имейте ввиду, что указатели занимают некоторое место в памяти и что динамическое распределение приводит к нерациональному использованию памяти при обращениях к функциям.

Программа, приведенная на рис. 15.3 (выходные данные, полученные в результате выполнения этой программы, показаны на рис. 15.4), использует шаблон класса List (см. главу 12 Шаблоны ) для манипуляций со списком данных целого типа и списком данных с плавающей запятой. Программа драйвер (driver.cpp) дает возможность использовать 5 режимов работы: 1) вставка значения в начало списка (функция insertAtFront); 2) вставка значения в конец списка (insertAtBack); 3) удаление значения из начала списка (функция removeFromFront); 4) удаление значения из конца списка (функция removeFromBack); 5) завершение обработки списка. Детальное обсуждение этой программы будет дано ниже. В упражнении 15.20 предлагается реализовать рекурсивную функцию, которая печатает связный список в обратной последовательности; а в упражнении 15.21 предлагается реализовать рекурсивную функцию поиска указанного элемента данных в связном списке.

Программа, приведенная на рис. 15.3, состоит из двух шаблонов класса: ListNode и List. Каждый объект, инкапсулированный в шаблон класса List, является связным списком объектов класса ListNode. Шаблон класса List-Node состоит из закрытых элементов data и nextPtr. Элемент data класса ListNode хранит значение типа NODETYPE, этот тип параметра передается шаблону класса. Элемент указатель nextPtr класса ListNode хранит указатель на следующий объект класса ListNode в связном списке.

Шаблон класса List состоит из закрытых элементов firstPtr (указатель на первый объект списка класса ListNode) и lastPtr (указатель на последний объект списка класса ListNode). Конструктор по умолчанию задает обоим указателям начальные значения О. Деструктор обеспечивает уничтожение всех объектов класса ListNode, входящих в объект класса List, при уничтожении самого этого объекта класса List. Основными функциями-э.пемен-тами шаблона класса List являются insert AtFront, insertAtBack, removeFromFront и removeFromBack. Функция isEmpty называется предикатной функцией или предикатом - она, во всех случаях не изменяет список, а только устанавливает, не является ли он пустым (т.е. не является ли указатель на первый узел списка нулевым). Если список пуст, то возвращается 1; в противном случае, возвращается О. Функция print выводит на экран содержимое списка.

firstPtr

lastPtr

LISTND.H: iifndef LISTND H #define LISTND H

Определение шаблона ListNode

template<class NODETYPE> class ListNode {

friend class List<NODETYPE>;

public:

ListNode(const NODETYPE &); NODETYPE getData0 const; private:

NODETYPE data; ListNode *nextPtr;

объявление List

дружественной функцией

конструктор

возвращает данные в узле

данные

следующий узел в списке

Конструктор template<class NODETYPE>

ListNode<NODETYPE>::ListNode(const NODETYPE &info) (

data = info; nextPtr = 0;

Возвращает копию данных в узле

template<class NODETYPE>

NODETYPE ListNode<NODETYPE>::getDatai

#endif

const { return data;}

LIST.H: #ifndef LIST H #define LIST H #include <iostream.h> #include <assert.h> #include timel.h

Определение щаблона класса List

template<class NODETYPE>

class List {

public:

ListO у конструктор

-LiatO; деструктор

void insertAtFront(const NODETYPE i) void insertAtBack(const NODETYPE &); int removePromFront(NODETYPE &); int removeFromBack(NODETYPE &); int isEmptyO const; void print 0 const; private:

ListNode<NODETYPE> *firstPtrg

ListNode<NODETYPE> *lastPtr;

указатель

на первый узел

указатель на последний

узел

ListNode<NODETYPE> *getNewNode(const NODETYPE &);

утилита

cout << Bee узлы удалены << endl << endl;

Вставка узла в начало списка template<class NODETYPE>

void List<NODETYPE>:linsertAtFront(const NODETYPE Svalue) {

ListNode<NODETYPE> *newPtr = getNewNode(value);

if (isEmpty0) Список пустой

firstPtr = lastPtr = newPtr; else { Список не пустой

newPtr->nextPtr = firstPtr;

firstPtr = newPtr;

Вставка узла в конец списка ternplate<cla88 NODETYPE>

void List<NODETYPE>::insertAtBack(const NODETYPE Evalue) {

ListNode<NODETYPE> *newPtr = getNewNode(value);

if (isEmptyO) Список пустой

firstPtr = lastPtr = newPtr; else { Список не пустой

lastPtr->nextPtr = newPtr;

lastPtr = newPtr;

Конструктор с умолчанием template<class NODETYPE>

List<NODETYPE>::ListО { firstPtr = lastPtr = 0; }

. Деструктор

nplate<class NODETYPE> List<NODETYPE>: :-List ()

if (! isEmpty0 ) { Список не пустой

cout << Удаление узлов ... << endl;

ListNode<NODETYPE> *currentPtr = firstPtr, *tempPtr;

while (currentPtr != 0) { удаление

оставшихся узлов

tempPtr = currentPtr; cout tempPtr->data endl; currentPtr = currentPtr->nextPtr; delete tempPtr;