Class List

Struct t_Item

Пример создания класса

Понятие класса

Знакомство с классами

Стек

Многомерные списки

///////////////////////////////////////////////////////////////////////////////////////////

// Пример реализации класса для работы с одномерными //

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

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

// начиная с 0. //

///////////////////////////////////////////////////////////////////////////////////////////

#include "stdafx.h"

#include <iostream>

using namespace std;

///////////////////////////////////////////////////////

// Начало определения класса List //

///////////////////////////////////////////////////////

// Тип данных t_Inf определяет тип данных информационных частей

// элементов динамического списка. В этом примере в качестве

// информации, хранящейся в элементах списка, используется тип данных double.

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

// необходимо заменить тип double,

// на нужный тип данных. При этом необходимо скорректировать

// значение определенной ниже константы DefVal.

// Также, возможно, потребуется незначительная коррекция функций-членов

// класса, связанная с операциями с информационными частями элементов списка

typedef double t_Inf;

// Значение информационной части элементов списка, используемое по умолчанию

const t_Inf DefVal = 0;

// Структура t_Item определяет тип данных элемента списка

{

t_Inf Inf; //Информационная часть - хранит полезную информацию

t_Item *Adr; // Адресное поле - хранит адрес следующего элемента списка

};

{

// Закрытые члены-данные класса

t_Item *Items, // Адрес первого элемента

*End; // Адрес последнего элемента

// Закрытые члены-функции класса

bool ItemExists(unsigned Index); // Проверка наличия элемента по его индексу

t_Item *Item(unsigned Index); // Получение адреса элемента по его индексу

t_Item *ExtractItem(unsigned Index); // Выделение элемента из списка по его

// индексу

public:

// Открытые члены-данные класса

unsigned Count; // Количество элементов в списке

// Открытые члены-функции класса

List(unsigned N = 0); // Коструктор класса. N - количество элементов списка

~List(void); // Деструктор класса

void Create(unsigned N = 0); // Создание нового списка из N элементов

void Clear(); // Удаление элементов списка

t_Inf GetItem(unsigned Index); // Получение информационной части элемента

// по его индексу

void PutItem(unsigned Index, t_Inf Val); // Присвоение значения Val элементу

// с индексом Index

void AddItem(t_Inf Val = DefVal); // Добавление элемента в конец списка

// (Val - значение информационной части)

void DelItem(unsigned Index); // Удаление из списка элемента с индексом Index

void InsItem(unsigned Index, t_Inf Val = DefVal); // Вставка нового элемента

// в позицию Index

void MoveItem(unsigned OldIndex, unsigned NewIndex); // Перестановка элемента

// с индексом OldIndex

// на позицию NewIndex

};

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

List::List (unsigned N)

// Конструктор класса DinArr. N - количество элементов в списке.

// Автоматически вызывается при создании объекта

{

// Вначале список пустой:

Count = 0;

Items = 0;

End = 0;

// Создает в динамической области список из N элементов:

Create (N);

}

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

List::~List ()

// Деструктор класса DinArr. Автоматически вызывается при уничтожении объекта

{

// При уничтожении объекта освобождает динамическую память от списка

Clear ();

}

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

void List::Create (unsigned N)

// Удаляет существующий список и создает новый список из N элементов

{

if (Count) // Если в списке есть элементы, то удаляем их

Clear ();

for (unsigned i = 1; i <= N; ++ i) // Добавляем к пустому списку N элементов

AddItem (); // Добавляем в конец списка новый элемент

}

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

void List::Clear ()

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

{

unsigned N = Count;

for (unsigned i = 1; i <= N; ++ i) // N раз удаляем из списка первый

// элемент (элемент с индексом 0)

DelItem (0);

}

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

bool List::ItemExists (unsigned Index)

// Проверка наличия элемента с индексом Index (значения индекса от 0 до Count - 1)

{

if (Index >= Count) // Если значение индекса некорректное

{

// Выводим сообщение об ошибке

cout << "Элемент с индексом " << Index << " отсутствует!\n";

return 0; // Возвращаем значение false

}

return 1; // Элемент с заданным индексом существует. Возвращаем значение true

}

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

t_Item *List::Item (unsigned Index)

// Функция возвращает адрес элемента с индексом Index (значения индекса

// от 0 до Count - 1). Если такого элемента нет, выводится сообщение об

// ошибке и функция возвращает нулевой адрес

{

if (!ItemExists (Index)) // Если элемент с заданным индексом

// отсутствует, выводим сообщение об ошибке,

return 0; // возвращаем нулевой адрес

if (Index == Count – 1) // Если нужен последний элемент списка,

return End; // возвращаем адрес последнего элемента

// Начиная с начала списка перемещаемся по списку до элемента

// с заданным индексом

t_Item *Curr = Items; // Делаем адрес очередного элемента равным

// адресу первого элемента

while (Index --) // Цикл продолжается Index раз

Curr = Curr->Adr; // Делаем адрес очередного элемента

// равным адресу следующего элемента

return Curr; // Возвращаем адрес элемента с заданным индексом

}

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

t_Inf List::GetItem (unsigned Index)

// Функция возвращает информационную часть элемента с индексом Index,

// если такой элемент имеется. Если такого элемента нет, выводится

// сообщение об ошибке, и функция возвращает значение

// информационной части равное DefVal

{

t_Item *Curr = Item (Index); // Получаем адрес элемента с заданным индексом

if (!Curr) // Если адрес нулевой

return DefVal; // Возвращаем значение по умолчанию

return Curr->Inf; // Возвращаем значение информационной части

}

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

void List::PutItem (unsigned Index, t_Inf Val)

// Функция устанавливает значение информационной части элемента

// с индексом Index, если такой элемент имеется, в значение Val.

// Если такого элемента нет, выводится сообщение об ошибке,

// а информационная часть элемента остается без изменения

{

t_Item *Curr = Item (Index); // Получаем адрес элемента с заданным индексом

if (!Curr) // Если адрес нулевой

return; // Выходим из функции

Curr->Inf = Val; / / Информационной части найденного элемента

// присваиваем значение Val

}

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

void List::AddItem (t_Inf Val)

// Функция добавляет новый элемент в конец списка и

// делает значение информационной части этого элемента равной Val

{

t_Item *NewItem = new t_Item; // NewItem - адрес нового созданного

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

NewItem->Inf = Val; / / Присваиваем информационной части этого

// элемента значение Val

NewItem->Adr = 0; // Поскольку элемент добавляется в конец списка,

// в его адресную часть заносим 0

if (Count) // Если в списке уже были эементы (Count > 0),

End->Adr = NewItem; // адресной части последнего элемента

// присаиваем адрес нового элемента

else // Иначе (Count = 0 - список был пуст)

Items = NewItem; // делаем адрес первого элемента списка

// равным адресу нового элемента

End = NewItem; // Теперь адрес последнего элемента списка

// делаем равным адресу добавленного элемента

++ Count; // Увеличиваем количество элементов списка на 1

}

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

t_Item *List::ExtractItem (unsigned Index)

// Функция выделяет элемент списка с индексом Index, исключая его из списка,

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

// выделенного элемента, если такой элемент есть. Если такого элемента нет –

// выводит сообщение об ошибке и возвращает нулевой адрес

{

if (!ItemExists (Index)) // Если элемент с заданным индексом отсутствует,

// выводим сообщение об ошибке,

return 0; // возвращаем нулевой адрес

t_Item *DItem, // Переменная для адреса выделяемого элемента

*Pred = 0; / / Переменная для адреса элемента

// предшествующего выделяемому

if (Index == 0) // Если выделяется первый элемент списка,

{

DItem = Items; // адрес выделяемого элемента делаем равным адресу

// первого элемента списка,

Items = Items->Adr; // изменяем адрес первого элемента равным адресу

// следующего элемента

}

else // Иначе (выделяется не первый элемент списка)

{

Pred = Item (Index – 1); // находим адрес элемента, который расположен

// перед удаляемым,

DItem = Pred->Adr; // делаем адрес выделяемого элемента равным

// адресной части предыдущего,

Pred->Adr = DItem->Adr; // и в адресную часть предыдущего элемента

// записывем адрес элемента, следующего

// за выделяемым (тем самым исключаем

// выделяемый элемент из списка).

}

if (DItem == End) // Если выделяемый элемент является

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

End = Pred; // корректируем адрес последнего элемента, делая его

// равным адресу предыдущего

-- Count; // Уменьшаем количество элементов в списке на 1

return DItem; // Возвращаем адрес выделенного элемента

}

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

void List::DelItem (unsigned Index)

// Функция удаляет элемент с индексом Index из списка и освобождает

// от него динамическую память. Если такого элемента нет, то выводится

// сообщение об ошибке, а список остается без изменений

{

t_Item *DItem = ExtractItem (Index); // Выделяем заданный элемент из списка

if (DItem) // Если адрес выделенного элемента не равен 0,

delete DItem; // освобождаем от него динамическую память

}

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

void List::InsItem (unsigned Index, t_Inf Val)

// Функция создает и вставляет новый элемент в список в позицию с индексом Index.

// Val - значение информационной части этого элемента. Если Index указывает

// позицию, выходящую за пределы списка, то новый элемент добавляется

// в конец списка

{

if (Index > Count) // Если указан слишком большой индекс,

// корректируем его так,

Index = Count; // чтобы новый элемент был вставлен в конец

// списка

t_Item *NewItem = new t_Item; // Создаем новый элемент (его адрес - NewItem)

NewItem->Inf = Val; // Формируем информационную часть

// вставляемого элемента

if (Index == 0) // Если элемент вставляется в начало списка,

{

NewItem->Adr = Items; // присоединяем новый элемент к началу

// списка и

Items = NewItem; // изменяем адрес первого элемента списка

}

else // Иначе (элемент должен быть не первым)

{

t_Item *Pred = Item (Index – 1); // находим адрес элемента, после

// которого должен быть вставлен

// новый элемент,

NewItem->Adr = Pred->Adr; // в адресную часть нового элемента

// заносим адрес следующего элемента,

Pred->Adr = NewItem; // в адресную часть предыдущего

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

// элемента

}

if (Index == Count) // Если новый элемент был вставлен в конец списка,

End = NewItem; // корректируем адрес последнего элемента, делая

// его равным адресу нового элемента

++ Count; // Увеличиваем количество элементов списка на 1

}

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

void List::MoveItem (unsigned OldIndex, unsigned NewIndex)

// Функция перемещает элемент с индексом OldIndex на позицию с индексом

// NewIndex. Если элемента с индексом OldIndex не существует, выводится ошибка

// и список не меняется. Если неверно указан новый индекс (NewIndex > Count),

// то элемент переставляется в конец списка

{

t_Item *MItem = ExtractItem (OldIndex); // Выделяем перемещаемый элемент из

// списка

if (MItem) // Если перемещаемый элемент найден,

{

InsItem(NewIndex, MItem->Inf); // вставляем новый элемент в позицию

// NewIndex, а информационную часть

// для него берем из перемещаемого

// элемента, и

delete MItem; // удаляем выделенный элемент из

// динамической памяти

}

}

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

/////////////////////////////////////////////////////

// Конец определения класса List //

/////////////////////////////////////////////////////

// Остальной код не имеет отношения к определению класса,

// а служит для иллюстрации использования созданного класса

void WriteArr (List &A)

// Функция выводит на экран значения информационных полей элементов списка А

{

for (unsigned i = 0; i < A.Count; ++ i)

cout << A.GetItem (i) << ' '; // Выводим на экран значение

// информационной части элемента

// с индексом i списка А

cout << endl;

}

int _tmain (int argc, _TCHAR* argv [ ])

{

setlocale (0, "");

List Arr (10); // Создаем список на 10 элементов

// В цикле заполняем информационные части всех элементов списка

// значениями, равными индексам этих элементов

for (unsigned i = 0; i < Arr.Count; ++ i)

Arr.PutItem (i, i);

WriteArr (Arr); // На экране видим: 0 1 2 3 4 5 6 7 8 9

// В цикле добавляем в конец списока еще 5 элементов, информационные части

// которых заполняются значениями, от 10 до 14 - Arr.AddItem (i + 10)

for (unsigned i = 0; i < 5; ++ i)

Arr.AddItem (i + 10);

WriteArr (Arr); // На экране видим: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Arr.MoveItem (10, 2); // Перемещаем элемент с индексом 10 в позицию

// с индексом 2

WriteArr (Arr); // На экране видим: 0 1 10 2 3 4 5 6 7 8 9 11 12 13 14

system ("pause");

return 0;

}