Одномерные двунаправленные списки

Каждый элемент списка содержит два адресных поля 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

void t_DinArr:: Set(unsigned Ind, t_Inf Val)

{

if (Ind >= ItemCount) // Индекс выходит за границу массива

   cout << Err << Ind << '!\ n'; // Выводим сообщение об ошибке

else // Индекс правильный

Arr [ Ind] = Val; // Элементу массива с индексом Ind присваиваем значение Val

}

// Возвращает значение элемента с индексом Ind

t_Inf t_DinArr:: Get(unsigned Ind)

{

if (Ind >= ItemCount) // Индекс выходит за границу массива

{

cout << Err << Ind << "!\ n"; // Выводим сообщение об ошибке

return DefVal; // Возвращаем из функции значение DefVal

}

else // Индекс правильный

return Arr [ Ind ]; // Возвращаем из функции значение элемента с индексом Ind

}

 

// Добавляет в конец массива элемент со значением Val

void t_DinArr:: Add(t_Inf Val)

{

++ ItemCount; // Количество элементов в массиве увеличиваем на 1

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

Arr = (t_Inf *) realloc (Arr, sizeof(t_Inf) * ItemCount);

// В новый (последний) элемент массива записываем значение Val

Arr [ ItemCount – 1 ] = Val;

}

unsigned t_ DinArr:: Count () // Возвращает количество элементов массива

{

return ItemCount;

}

void t_ DinArr:: Free () // Удаление массива из динамической памяти

{

if (Arr) // Указатель на массив не равен 0 – массив есть

{

      free(Arr); // Освобождаем динамическую память

      Arr = 0; // Делаем указатель на массив равным 0 – массива нет

ItemCount = 0; // Присваиваем количеству элементов в массиве значение 0

}

}

 

Первый вариант класса t_ DinArr готов. Его использование иллюстрируется следующим примером:

 

Int main ()

{

setlocale (0, "");

// Описываем экземпляр класса (статическая переменная DA типа t_ DinArr):

t_ DinArr DA;

// Вводим с клавиатуры необходимый размер массива:

unsigned N;

cout  <<  “Количество элементов в массиве: ”;

cin >> N;

// Инициализируем экземпляр класса (при этом в динамической области

// памяти будет создан массив на заданное количество элементов

// и этот массив будет «обнулён» значениями DefVal):

DA. Init (N);

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

// равными индексам элементов массива:

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

   DA. Set (i,  i);

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

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

   cout << DA. Get (i)  << ‘ ‘; // на экране видим числа: 0 1 2 … N-1

cout << endl;

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

// которых заполняются значениями, от N до N + 4

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

            DA.Add (N + i);

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

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

   cout << DA. Get (i)  << ‘ ‘; // на экране видим числа: 0 1 2 … N + 4

cout << endl;

// Заканчиваем работу с массивом (освобождаем динамическую память):

DA. Free ();

system (" pause");

return 0;

}

 

Обсудим использование класса в этом примере.

1. Обращение к членам экземпляра класса осуществляется точно так же, как и к полям обычных структур, с помощью оператора «точка», например: DA. Init (N).
2. В функции main обращаться можно только к открытым членам класса. Доступ к закрытым членам класса (Arr и ItemCount) осуществляется опосредованно через функции члены класса, что защищает программу от случайных возможно ошибочных изменений этих данных.
3. Для работы с массивом необходимо перед началом работы объявить экземпляр класса (t_ DinArr DA;) и инициализировать его (DA. Init (N);).
4. При окончании работы с экземпляром класса необходимо освободить динамическую память (DA. Free ();).

Рабочая программа этого примера приведена в Приложении 1.