Лекция №

Вид материала

Лекция

Содержание Приложение А

Подобный материал:

• «Социальная стратификация и социальная мобильность», 46.19kb.
• Первая лекция. Введение 6 Вторая лекция, 30.95kb.
• Лекция Сионизм в оценке Торы Лекция Государство Израиль испытание на прочность, 2876.59kb.
• Текст лекций н. О. Воскресенская Оглавление Лекция 1: Введение в дисциплину. Предмет, 1185.25kb.
• Собрание 8-511 13. 20 Лекция 2ч режимы работы эл оборудования Пушков ап 8-511 (ррэо), 73.36kb.
• Концепция тренажера уровня установки. Требования к тренажеру (лекция 3, стр. 2-5), 34.9kb.
• Лекция по физической культуре (15. 02.; 22. 02; 01. 03), Лекция по современным технологиям, 31.38kb.
• Тема Лекция, 34.13kb.
• Лекция посвящена определению термина «транскриптом», 219.05kb.
• А. И. Мицкевич Догматика Оглавление Введение Лекция, 2083.65kb.

Приложение А

(рекомендуемое)

Листинг модуля Algo.h


#ifndef AlgoH

#define AlgoH

//---------------------------------------------------------------------------

// Заголовочный файл "iostream.h" содержит описание потоков ввода (класс istream)

// и вывода (класс ostream).

// Вывод (в поток вывода) осуществляется перегруженной операцией <<.

// Ввод (из потока ввода) осуществляется перегруженной операцией >>.

// Также объявляются стандартные поток ввода cin типа istream и

// поток вывода cout типа ostream.

#include

//---------------------------------------------------------------------------

/*

Шаблон функции: нахождение максимума из двух значений одного типа.

Аргументы:

константная ссылка x на первое значение,

константная ссылка y на второе значение.

Результат: константная ссылка на максимальное значение.

Требование к типу T:

- должна быть определена операция <

bool operator < (const T &x, const T &y) { ... }

*/

template

inline const T& Max(const T &x, const T &y)

{

return x < y ? y : x;

}

//---------------------------------------------------------------------------

/*

Шаблон функции: нахождение минимума из двух значений одного типа.

Аргументы:

константная ссылка x на первое значение,

константная ссылка y на второе значение.

Результат: константная ссылка на минимальное значение.

Требование к типу T: аналогично Max

*/

template

inline const T& Min(const T &x, const T &y)

{

return x < y ? x : y;

}

//---------------------------------------------------------------------------

/*

Шаблон функции: копирование массивов равного размера из элементов одинакового типа.

Аргументы:

указатель x на первый элемент результирующего массива,

указатель y на константный объект - адрес первого элемента исходного массива,

count - число элементов в массивах.

Результат: -

Требование к типу T:

- операция присваивания должна быть корректно определена

*/

template

void Copy(T *x, const T *y, unsigned count)

{

while (count--)

*x++ = *y++;

}

//---------------------------------------------------------------------------

/*

Шаблон функции: сравнение массивов равного размера из элементов одинакового типа.

Аргументы:

указатель x на константный объект - адрес первого элемента одного массива,

указатель y на константный объект - адрес первого элемента второго массива,

count - число элементов в массивах.

Результат: true, если массивы равны; false - иначе.

Требование к типу T:

- должна быть определена операция !=

bool operator != (const T &x, const T &y) { ... }

*/

template

bool Compare(const T *x, const T *y, unsigned count)

{

while (count--)

if (*x++ != *y++) return false;

return true;

}

//---------------------------------------------------------------------------

/*

Шаблон функции: ввод массива из потока.

Аргументы:

указатель x на первый элемент массива,

count - число элементов в массиве,

ссылка на поток ввода stream (по умолчанию стандартный поток ввода cin).

Результат: -

Требование к типу T:

- должна быть определена операция ввода из потока >>

istream& operator >> (istream &stream, T &x) { ... }

*/

template

void Read(T *x, unsigned count, istream &stream = cin)

{

while (count--)

stream >> *x++;

}

//---------------------------------------------------------------------------

/*

Шаблон функции: вывод массива в поток.

Аргументы:

указатель x на константый объект - адрес первого элемента массива,

count - число элементов в массиве,

ссылка поток вывода stream (по умолчанию стандартный поток вывода cout),

указатель delim на константую строку,

которая выводится после каждого элемента массива (по умолчанию " ").

Результат: -

Требование к типу T:

- должна быть определена операция вывода в поток <<

ostream& operator << (ostream &stream, const T &x) { ... }

*/

static const char *WriteDefDelim = " ";


template

void Write(const T *x, unsigned count, ostream &stream = cout, const char *delim = WriteDefDelim)

{

while (count--)

stream << *x++ << delim;

}

//---------------------------------------------------------------------------

#endif


Приложение Б

(рекомендуемое)

Листинг модуля Array.h


#ifndef ArrayH

#define ArrayH

//---------------------------------------------------------------------------

#include

#include "Algo.h"

//---------------------------------------------------------------------------

/*

Шаблон класса: одномерный динамический массив из элементов типа T.

*/

template

class Array {


private:

unsigned FCount; // число элементов

T* FData; // указатель на первый элемент массива (если FCount > 0)


public:

// Создание массива из count элементов, по умолчанию 0.

Array(unsigned count = 0)

: FCount(0) // инициализируем элемент FCount конструктором копии

{ // (вместо конструктора по умолчанию)

Resize(count, false);

}


// Создание массива из count элементов, которые инициализируются

// count элементами, на которые указывает data.

Array(unsigned count, const T *data)

: FCount(0)

{

Assign(count, data);

}


// Конструктор копии.

Array(const Array& array)

: FCount(0)

{

Assign(array.FCount, array.FData);

}


// Деструктор (освобождает память).

~Array()

{

Clear();

}


// Возвращает размер массива.

unsigned Count() const { return FCount; }

// Задает размер массива.

void Count(unsigned count) { Resize(count); }


// Устанавливает размер массива в count и копирует в него count элементов

// data[0], data[1], ..., data[count - 1].

void Assign(unsigned count, const T *data);


// Устанавливает размер массива. Старые элементы (сколько влезут в новый размер)

// по умолчанию остаются (параметр store = true), либо теряются (store = false).

void Resize(unsigned count, bool store = true);


// Удаление всех элементов.

void Clear()

{

Count(0);

}


// Операция присваивания. Устанавливается такой же размер и копируются данные из array.

Array& operator =(const Array& array)

{

// Если не имеет место самоприсваивание (Array a; a = a;), то

if (this != &array)

// выполняем присваивание.

Assign(array.FCount, array.FData);

// Возвращаем ссылку на левый аргумент операции присваивания, чтобы позволить, например,

// дальнейшее присваивание (Array a, b, c; a = b = c;).

return *this;

}


// Операция индексации (для константного массива).

const T& operator [](unsigned index) const

{

assert(index < FCount); // проверка корректности индекса

return FData[index]; // и возврат константной ссылки на элемент

}


// Операция индексации (для неконстантного массива).

T& operator [](unsigned index)

{

assert(index < FCount); // проверка корректности индекса

return FData[index]; // и возврат ссылки на элемент

}


// Операция вывода в поток.

friend ostream& operator <<(ostream &stream, const Array& array)

{

// Вывод в поток и

Write(array.FData, array.FCount, stream);

// возврат ссылки на поток, чтобы позволить последующий вывод (нап: cout << a << b).

return stream;

}


// Операция ввода из потока.

friend istream& operator >>(istream &stream, Array& array)

{

// Ввод из потока и

Read(array.FData, array.FCount, stream);

// возврат ссылки на поток, чтобы позволить последующий ввод (нап: cin >> a >> b).

return stream;

}


// Операция равенства.

friend bool operator ==(const Array& x, const Array& y)

{

// Если массивы являются различными объектами, то выполняем сравнение.

if (&x != &y)

// Если число элементов одинаково,

if (x.FCount == y.FCount)

// то выполняем поэлементное сравнение.

return Compare(x.FData, y.FData, FCount);

// Иначе, массивы не равны.

else

return false;

// Иначе возвращаем истину (т. к. любой массив сам себе равен).

return true;

}


// Операция неравенства.

friend bool operator !=(const Array& x, const Array& y)

{

return !(x == y);

}


};

//---------------------------------------------------------------------------

// Определение не встраиваемых функций-элементов

//---------------------------------------------------------------------------

template

void Array::Assign(unsigned count, const T *data)

{

Resize(count, false); // устанавливаем размер, без сохранения элементов

Copy(FData, data, FCount); // и копируем данные

}

//---------------------------------------------------------------------------

template

void Array::Resize(unsigned count, bool store)

{

// Если число элементов изменяется.

if (FCount != count) {

// Если новое число элементов не нулевое, то распределяем память;

if (count) {

// Создаем динамический массив из count элементов,

T *p = new T[count];

// и копируем туда старые элементы (сколько влезет), если требуется.

if (store)

Copy(p, FData, Min(FCount, count));

// Уничтожаем старый массив, если он не пуст.

if (FCount) delete[] FData;

// Сохраняем в классе адрес первого элемента нового массива.

FData = p;

}

// иначе освобождаем память.

else

delete[] FData;

// Сохраняем новое число элементов в классе.

FCount = count;

}

}

//---------------------------------------------------------------------------

#endif

Приложение В

(рекомендуемое)

Листинг модуля List.h


//---------------------------------------------------------------------------

#ifndef ListH

#define ListH


// Определяем макрос, кот-й используется как условие того,

// что компилируется "List.h".

#define ListInterior

//---------------------------------------------------------------------------

#include

//---------------------------------------------------------------------------

/*

Шаблон класса: связный список из элементов типа T.

*/

template

class List {


private:


// Включаем определение структуры "узел списка".

#include "ListNode.h"


Node *FFirst, // первый узел списка

*FLast; // последний узел


// Делаем конструктор копии и операцию присваивания закрытыми.

List(const List&) { }

void operator =(const List&) { }


public:


// Включаем определение класса "итератор списка".

#include "ListIterator.h"


// Конструктор пустого списка

List()

: FFirst(NULL), FLast(NULL)

{

}


// Деструктор (освобождает память).

~List()

{

Clear();

}


// Возвращает константный итератор на первый элемент (для константного списка).

const Iterator First() const

{

return Iterator(FFirst);

}


// Возвращает итератор на первый элемент (для не константного списка).

Iterator First()

{

return Iterator(FFirst);

}


// Возвращает константный итератор на последний элемент (для константного списка).

const Iterator Last() const

{

return Iterator(FLast);

}


// Возвращает итератор на последний элемент (для не константного списка).

Iterator Last()

{

return Iterator(FLast);

}


// Возвращает константный итератор на "конец" (для константного списка).

const Iterator End() const

{

return Iterator();

}


// Возвращает итератор на "конец" (для не константного списка).

Iterator End()

{

return Iterator();

}


// Проверка пустоты списка.

bool Empty() const

{

return !FFirst;

}


// Вставляет элемент в список перед элементом, на который указывает итератор iter.

// Если iter указывает на "конец", то эл-т добавляется в конец списка.

void Insert(const Iterator& iter, const T& data);


// Удаляет эл-т, на который указывает итератор iter.

void Delete(const Iterator& iter);


// Удаляет все эл-ты из списка.

void Clear();


// Добавление эл-та в начало списка.

void PushFront(const T& data) { Insert(First(), data); }


// Добавление эл-та в конец списка.

void PushBack(const T& data) { Insert(End(), data); }


// Удаление первого эл-та.

void PopFront() { Delete(First()); }


// Удаление последнего эл-та.

void PopBack() { Delete(Last()); }


};

//---------------------------------------------------------------------------

// Определение не встраиваемых функций-элементов

//---------------------------------------------------------------------------

template

void List::Insert(const Iterator& iter, const T& data)

{

Iterator i;

Node *t,

*n = new Node(data); // создаем отдельный узел

// Если iter указывает на "конец", то добавляем эл-т в конец списка.

if (iter == End()) {

// Если список не пуст, то

if (FFirst)

// связываем последний узел с новым;

FLast->Next = n;

else

// иначе новый последний узел является и первым.

FFirst = n;

// Связываем новый узел с последним,

n->Prev = FLast;

// и делаем новый последним.

FLast = n;

}

else

// Иначе, если iter указывает на первый, то добавляем эл-т в начало списка.

if (iter == First()) {

// Если список не пуст, то

if (FFirst)

// связываем первый узел с новым;

FFirst->Prev = n;

else

// иначе новый первый узел является и последним.

FLast = n;

// Связываем новый узел с первым,

n->Next = FFirst;

// и делаем его первым.

FFirst = n;

}

// Иначе вставляем эл-т в "середину" списка.

else {

// Ищем узел X, перед которым нужно вставить.

for (i = First(); i != End(); i++)

if (i == iter) break;

// Если не найден, то iter не корректен: ошибка.

assert(i != End());

t = i.P->Prev;

t->Next = n; // связываем предшествующий X с новым

n->Prev = t; // связываем новый с предшествующим X

n->Next = i.P; // связываем новый с X

i.P->Prev = n; // связываем X с новым

}

}

//---------------------------------------------------------------------------

template

void List::Delete(const Iterator& iter)

{

Node *t;

Iterator i;

// Ищем узел X, содержащий удаляемый эл-т.

for (i = First(); i != End(); i++)

if (i == iter) break;

// Если не найден, то iter не корректен: ошибка.

assert(i != End());

t = i.P;

// Если X первый.

if (i == First()) {

// Смещаем первый узел на следующий за ним.

FFirst = t->Next;

// Если он отсутсвует, то список состоит из одного эл-та и

// нужно сбросить указатель на последний.

if (!FFirst) FLast = NULL;

}

else

// Иначе, если X последний.

if (i == Last()) {

// Смещаем последний узел на ему предшествующий.

FLast = t->Prev;

// Если он отсутсвует, то список состоит из одного эл-та и

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

if (!FLast) FFirst = NULL;

}

else {

// Иначе X средний.

t->Prev->Next = t->Next; // связываем предыдущий X со следующим за X,

t->Next->Prev = t->Prev; // отделяя X от списка

}

// Удаляем X (уничтожаем и освобождаем память).

delete t;

}

//---------------------------------------------------------------------------

template

void List::Clear()

{

// Если список не пуст.

if (!Empty()) {

Node *n;

Iterator i;

// Удаляем все узлы.

for (i = First(); i != End(); ) {

n = i.P; // сохраняем адрес узла

i++; // переходим к следующему

delete n; // и удаляем текущий

}

// Сбрасываем указатели на первый и последний.

FFirst = FLast = NULL;

}

}

//---------------------------------------------------------------------------

// Убираем макрос ListInterior, т. к. "List.h" закончился.

#undef ListInterior


#endif


Листинг модуля ListIterator.h


// Если "ListIterator.h" включен вне "List.h",

#ifndef ListInterior

// то выдать ошибку компиляции.

#error "ListIterator.h" is internal for "List.h". Do not include directly.

#endif


//template

//class List {

//...


// Итератор списка.

class Iterator {

// Класс список объявляется дружественным для доступа к указателю на узел.

friend List;


Node* P; // ук-ль на узел списка, содержащий значение эл-та, на кот-й указывает итератор


public:

// Создает итератор, указывающий на эл-т списка, хранящийся в узле по адресу p.

// По умолчанию ни на что не указывает. Т. к. Node - закрытый тип класса List,

// то итератор на эл-т может быть создан только функциями-элементами List.

Iterator(Node* p = NULL)

: P(p)

{

}


// Операция разыменовывания для константного итератора.

// Возвращает константую ссылку на значение эл-та.

const T& operator *() const

{

return P->Data;

}


// Операция разыменовывания для не константного итератора.

// Возвращает не константного ссылку на значение эл-та, по которой

// оно может быть изменено.

T& operator *()

{

return P->Data;

}


// Префиксная операция инкремента. Перемещает итератор к следующему эл-ту списка.

Iterator operator ++()

{

P = P->Next; // переходим к следующему эл-ту

return *this; // возвращаем "увеличенный" итератор

}


// Постфиксная операция инкремента. Перемещает итератор к следующему эл-ту списка.

// Аргумент типа int указывает компилятору, что данная функция-операция operator ++