 |
Доступ к заданному элементу списка
|
|
|
|
Функция ListItem возвращает адрес элемента списка с индексом Index (индексация элементов в списке начинается с 0). Если элемент с заданным индексом в списке отсутствует, функция возвращает нулевой адрес. Параметр Beg задает адрес первого элемента списка (адрес начала списка). Третий параметр функции ErrMsg определяет надо ли выводить сообщение об ошибке при неправильно заданном индексе.
t_Item *ListItem(t_Item *Beg, unsigned Index, bool ErrMsg = true)
{
// Цикл заканчивается, когда
while (Beg && (Index --))
Beg = Beg->Adr;
if (ErrMsg &&!Beg)
cout << "Элемент списка отсутствует \ n";
return Beg;
}
Добавление нового элемента к списку
t_Item *InsItem(t_Item * &Beg, unsigned Index)
{
t_Item * Item = new t_Item;
if (!Index ||!Beg)
{
Item->Adr = Beg;
Beg = Item;
return Item;
}
t_Item * PredItem = Beg;
-- Index;
while (PredItem->Adr && (Index --))
PredItem = PredItem->Adr;
Item->Adr = PredItem->Adr;
PredItem->Adr = Item;
return Item;
}
Определение количества элементов в списке
unsigned LengthList (t_ Item * Beg)
{
unsigned Length = 0; // Счетчик элементов списка
// Начинаем с начала списка
while (Beg)
{
// Увеличиваем счетчик элементов списка на единицу
++ Length;
// Перемещаемся на следующий элемент списка
Beg = Beg->Adr;
}
return Length;
}
Удаление элемента из списка
void DelItem(t_Item * &Beg, unsigned Index)
{
if (Index >= LengthList (Beg))
return;
t_Item * Item;
if (!Index)
{
Item = Beg->Adr;
delete Beg;
Beg = Item;
return;
}
Item = ListItem (Beg, Index - 1, 0);
t_Item * DItem = Item->Adr;
Item->Adr = DItem->Adr;
delete DItem;
}
Одномерные двунаправленные списки
Каждый элемент списка содержит два адресных поля Pred и Next. Поле Pred содержит адрес предыдущего элемента списка (в первом элементе это поле равно 0). Поле Next содержит адрес следующего элемента списка (в последнем элементе это поле равно 0). Такая организация списка позволяет перемещаться по его элементам в двух направлениях.
|
|
|
Тип данных для элементов такого списка можно определить так:
Struct t_Item
{
double Inf;
t_ Item * Pred,
* Next;
};
Здесь предполагается, что информационное поле имеет тип double.
Для создания такого списка можно использовать следующую функцию:
t_Item *CreateList (unsigned Length)
{
t_ Item * Curr = 0, // Адрес очередного элемента списка
* Next = 0; // Адрес следующего за очередным элемента списка
// Начинаем создавать список с последнего элемента
for (unsigned i = 1; i <= Length; ++ i)
{
// Создаем очередной элемент списка
Curr = new t_ Item;
// В адресную часть записываем адрес следующего
// за очередным элемента списка
Curr-> Next = Next;
if (Next) // Следующий элемент существует (Next не равен 0)
// Очередной элемент с адресом Curr является предыдущим
// элементом для элемента с адресом Next
Next-> Pred = Curr;
// Запоминаем адрес очередного элемента в качестве
// следующего элемента для следующего шага цикла
Next = Curr;
}
// Для первого элемента списка адрес предыдущего элемента
// должен быть равен 0
Curr-> Pred = 0;
// Возвращаем адрес последнего созданного элемента,
// как адрес первого элемента списка
return Curr;
}
Функции удаления списка DeleteList,доступа кэлементам списка ListItem,определения длины списка LengthList и перемещения элемента MoveItem остаются такими же, как и для однонаправленного списка (необходимо только заменить идентификатор поля Adr на Next). Остальные функции требуют небольшой коррекции, связанной с дополнительной обработкой адресного поля Pred:
t_Item *InsItem(t_Item * &Beg, unsigned Index)
|
|
|
{
t_Item * Item = new t_Item;
if (!Index ||!Beg)
{
Beg->Pred = Item;
Item->Pred = 0;
Item->Next = Beg;
Beg = Item;
return Item;
}
t_Item * PredItem = Beg;
-- Index;
while (PredItem->Next && (Index --))
PredItem = PredItem->Next;
Item->Pred = PredItem;
Item->Next->Pred = Item;
Item->Next = PredItem->Next;
PredItem->Next = Item;
return Item;
}
void DelItem(t_Item * &Beg, unsigned Index)
{
if (Index >= LengthList (Beg))
return;
t_Item * Item;
if (!Index)
{
Item = Beg->Next;
delete Beg;
Beg = Item;
Beg->Pred = 0;
return;
}
Item = ListItem (Beg, Index - 1, 0);
t_Item * DItem = Item->Next;
Item->Next = DItem->Next;
Item->Next->Pred = Item;
delete DItem;
}
Многомерные списки
Стек
Знакомство с классами
Понятие класса
Инкапсуляция - механизм, позволяющий объединять в едином объекте множество его характеристик (данные, характеризующие объект) и действий над ними (средства обработки этих данных).
Сокрытие представляет собой принцип разграничения доступа различных частей программы к различным элементам данных и действий над ними.
В языке С++ классы соединяют в себе оба эти понятия, позволяя в одном объекте объединять различные его характеристики (переменные) и средства их обработки (функции), а также обладают средствами разграничения доступа к различным частям объектов из разных частей программы.
Класс – это тип данных, определяемый пользователем. Класс может содержать определение только данных или только некоторых действий, но чаще всего он содержит и то, и другое.
Данные (переменные), характеризующие класс, называются членами данных, а действия над ними (функции) – функциями-членами класса.
Для работы с некоторым классом создаются переменные этого типа, называемые экземплярами класса.
Определение класса осуществляется с помощью инструкции class:
class < идентификатор класса >
{
// Закрытые члены класса
public:
// Открытые члены класса
} < список экземпляров класса >;
Например:
typedef double t_ Inf; // Тип данных элементов массива
const t_ Inf DefVal = 0; // Значение элемента массива по умолчанию
char Err [] = "\ n***В массиве нет элемента с индексом "; // Сообщение об ошибке
class t_ DinArr {
// Закрытые члены-данные класса
t_ Inf * Arr; // Указатель на динамический массив
|
|
|
unsigned ItemCount; // Количество элементов в массиве
public:
// Открытые члены-функции класса
void Init (unsigned N = 0); // Инициализация массива из N элементов
void Clear(); // Очистка массива
void Set (unsigned Ind, t_Inf Val); // Запись значения Val в элемент с индексом Ind
t_ Inf Get (unsigned Ind); // Возвращает значение элемента с индексом Ind
void Add (t_ Inf Val); // Добавляет в конец массива элемент со значением Val
unsigned Count (); // Возвращает количество элементов массива
void Free (); // Удаление массива из динамической памяти
};
В этом примере начато создание класса для работы с одномерными динамическими массивами. Элементами этого массива являются данные типа t_ Inf (в этом примере – эквивалент типа double). Константа DefVal = 0 определяет значение элементов массива по умолчанию.
Идентификатор класса t_ DinArr определяет новый пользовательский тип данных, включающий в себя два члена-данных: Arr (указатель на массив элементов типа t_ Inf) и ItemCount (переменная, определяющая текущее количество элементов массива). И Arr и ItemCount являются закрытыми членами класса (все члены класса, расположенные до слова public, являются закрытыми). После слова public перечисляются открытые члены класса. В нашем примере это пять членов-функций. Функция Init создает динамический массив на N элементов и инициализирует его элементы значениями DefVal. Функция Set присваивает элементу массива с индексом Ind значение Val. Функция Get возвращает значение элемента массива с индексом Ind. Функция Count возвращаетколичество элементов массива. Функция Free удаляет массив из динамической памяти. Члены-функции определяются с помощью прототипов. Реализация этих функций приведена ниже. Таким образом, класс инкапсулирует два члена-данных и пять функций членов.
Различие между закрытыми и открытыми членами класса состоит в следующем. К закрытым членам класса могут обращаться только другие члены класса (открытые и закрытые). Открытые члены класса доступны везде (и в других членах класса, и в программе). Иными словами, при использовании некоторого класса программист в программе может пользоваться только открытыми членами класса. Закрытые члены класса могут использоваться только внутри реализации класса. Определяя Arr и ItemCount закрытыми, мы осуществляем сокрытие этих данных от прямого доступа к ним. При использовании этого класса в программе программист не может напрямую изменять эти данные, что предотвращает возможность возникновения ошибок при работе с массивом. Например, если сделать Arr открытым членом класса, то в программе можно будет напрямую изменить значение указателя на первый элемент массива, присвоив ему, например, значение 0. В этом случае уже имеющийся в динамической области памяти массив будет «потерян» - произойдет утечка памяти. Этого допускать нельзя. То же самое касается и члена класса ItemCount – произвольные изменения его значения могут привести к неправильной работе программы.
|
|
|
Перейдем к реализации членов функций.
Член функцию Init можно реализовать так:
void t_ DinArr:: Init (unsigned N) // Инициализация массива из N элементов
{
if (N) // Если N больше 0
// Выделяем память в динамической области для N элементов массива
Arr = (t_ Inf *) malloc (sizeof(t_ Inf) * N);
else
// При N = 0 указатель на массив равен 0 – массива нет
Arr = 0;
// Устанавливаем значение количества элементов в массиве
ItemCount = N;
// Очищаем массив значениями DefVal
Clear();
}
В чем особенности определения:
1. Для того, чтобы показать, что функция Init является членом класса t_ DinArr, перед ее именем необходимо указать префикс t_ DinArr::.
2. Обращение и к открытым, и к закрытым членам класса внутри тела функции осуществляется напрямую
Аналогичным образом реализуются и остальные функции члены класса:
void t_ DinArr:: Clear () // Очистка массива значениями DefVal
{
for (unsigned i = 0; i < ItemCount; ++ i)
Arr [i] = DefVal;
}
// Запись значения Val в элемент с индексом Ind
|
|
|
