заполнить новые элементы массива данными.

Вот как можно решить эту задачу в стиле C++:

int N1 = 10, // Начальный размер массива

N2 = 20; // Новый размер массива

int *Arr = new int [N1]; // Создаем исходный массива из N1 элемента

for (int i = 0; i < N1; ++ i) // Заполняем исходный массив числами от 0 до 9

Arr[i] = i;

for (int i = 0; i < N1; ++ i) // Выводим исходный массив на экран

cout << Arr[i] << " ";

cout << endl;

int *Rez = new int [N2]; // Создаем промежуточный массив из N2 элементов

for (int i = 0; i < N1; ++ i) // Копируем данные из исходного массива

Rez[i] = Arr[i]; // в промежуточный

delete [ ] Arr; // Освобождаем память от исходного массива. Если этого не

// сделать, произойдет утечка памяти

Arr = Rez; // Изменяем переменную исходного массива

for (int i = N1; i < N2; ++ i) // Дополняем исходный массив числами от 10 до 19

Arr[i] = i;

for (int i = 0; i < N2; ++ i) // Снова выводим исходный массив на экран

cout << Arr[i] << " ";

cout << endl;

delete [ ] Arr; // Окончательно освобождаем память от исходного массива.

В результате работы этого фрагмента программы на экран будут выведены значения массива до его расширения и после расширения:

0 1 2 3 4 5 6 7 8 9

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Если удалить из этого фрагмента строки, не имеющие непосредственного отношения к решаемой задаче (это ввод данных в массивы, вывод данных на экран), то “скелет” алгоритма будет таким:

int N1 = 10, // Начальный размер массива

N2 = 20; // Новый размер массива

int *Arr = new int [N1]; // Создаем исходный массива из N1 элемента

……. // Работаем с массивом старой длины

int *Rez = new int [N2]; // Создаем промежуточный массив из N2 элементов

for (int i = 0; i < N1; ++ i) // Копируем данные из исходного массива

Rez[i] = Arr[i]; // в промежуточный

delete [ ] Arr; // Освобождаем память от исходного массива. Если этого не

// сделать, произойдет утечка памяти

Arr = Rez; // Изменяем переменную исходного массива

……. // Работаем с массивом новой длины

delete [ ] Arr; // Окончательно освобождаем память от исходного массива.

А вот как решается эта же задача при использовании стиля языка C:

int N1 = 10, // Начальный размер массива

N2 = 20; // Новый размер массива

int *Arr = (int *) malloc( N1 * sizeof ( int ) ); // Создаем массив из N1 элемента

for (int i = 0; i < N1; ++ i) // Заполняем массив числами от 0 до 9

Arr[i] = i;

for (int i = 0; i < N1; ++ i) // Выводим массив на экран

cout << Arr[i] << " ";

cout << endl;

Arr = (int *) realloc( Arr, N2 * sizeof ( int ) ); // Изменяем размер массива

for (int i = N1; i < N2; ++ i) // Дополняем массив числами от 10 до 19

Arr[i] = i;

for (int i = 0; i < N2; ++ i) // Снова выводим массив на экран

cout << Arr[i] << " ";

cout << endl;

delete [ ] Arr; // Окончательно освобождаем память от исходного массива.

А вот, что представляет “скелет” алгоритма, в этом случае:

int N1 = 10, // Начальный размер массива

N2 = 20; // Новый размер массива

int *Arr = (int *) malloc( N1 * sizeof ( int ) ); // Создаем массив из N1 элемента

……. // Работаем с массивом старой длины

Arr = (int *) realloc( Arr, N2 * sizeof ( int ) ); // Изменяем размер массива

……. // Работаем с массивом новой длины

delete [ ] Arr; // Окончательно освобождаем память от исходного массива.

Не правда ли, существенно короче и понятнее.

Перейдем к рассмотрению двумерных массивов. С ними дело обстоит несколько сложнее, чем с одномерными динамическими массивами.

В стиле C++ двумерный массив целых чисел можно создать и удалить следующим образом:

int ( * Arr ) [ 10 ] = new int [ dim ] [ 10 ];

delete [ ] Arr;

В этом примере создается двумерный массив из dim строк и 10 столбцов. Элементами массива являются целые числа типа int. При таком способе создания двумерных массивов изменять в процессе выполнения программы можно только самую левую размерность массива (dim). Вторая размерность должна задаваться константным значением (в нашем случае 10). Таким образом, динамически изменяемым в таких массивах является только количество строк, а количество столбцов остается постоянным. Пример использования этого метода:

cin >> dim; // Вводим с клавиатуры количество строк массива

int ( * Arr ) [ 10 ] = new int [ dim ] [ 10 ]; // Выделяем память в динамической области

// Заполняем массив Arr значениями равными сумме индексов элементов массива

for ( int i = 0; i < dim; ++ i )

for ( int j = 0; j < 10; ++ j )

Arr [ i ] [ j ] = i + j;

// Выводим на экран элементы массива Arr в виде таблицы, содержащей dim строк и

// 10 столбцов

for (int i = 0; i < dim; ++ i)

{

for (int j = 0; j < 10; ++ j)

cout << setw(4) << Arr[i][j];

cout << endl;

}

delete [ ] Arr; // Освобождаем память от массива Arr

Недостаток этого метода очевиден – мы можем управлять только одной размерностью такого массива.

Для того чтобы избавиться от этого недостатка представим двумерный массив как одномерный массив, элементами которого являются одномерные массивы элементов базового типа массива.

Пусть базовым типом элементов нашего двумерного массива, как и в предыдущем примере, будут целые числа типа int. Этот двумерный массив можно представить как набор из RowCount строк, то есть как одномерный массив строк. Этому массиву на приведенном ниже рисунке соответствует вертикальный массив, элементами которого являются указатели на тип int (каждый элемент этого массива будет содержать адрес первого элемента соответствующей строки int*). Каждая строка представляет собой одномерный массив из ColCount элементов типа int. Элементы массивов-строк служат для хранения данных, для которых и предназначен двумерный массив.

Таким образом, для того чтобы получить двумерный массив, нам необходимо:

Создать одномерный динамический массив из RowCount указателей на базовый тип элементов массива (в нашем случае указателей на тип int);

2. в цикле создать RowCount одномерных динамических массивов, каждый из которых содержит ColCount элементов базового типа (в нашем случае указателей на тип int) и адреса их первых элементов записать в соответствующие элементы “вертикального” массива.

Остается неясным вопрос: как определить массив указателей (“вертикальный” массив)? Обычный одномерный массив определяется как указатель на базовый тип данных элементов этого массива. Базовым типом элементов этого массива являются указатели int*. Для того чтобы определить указатель на указатель достаточно использовать следующую конструкцию: (int*)* или проще int**.

Таким образом, для того чтобы создать динамический массив Arr из указателей, можно поступить так:

int ** Arr = new int * [ RowCount ]

Создание массива-строки p еще проще:

int * p = new int [ ColCount ]

Тогда для создания всего двумерного динамического массива необходимо выполнить следующие действия:

int ** Arr = new int * [ RowCount ]; // Создаем “вертикальный” массив

for ( int i = 0; i < RowCount; ++ i )

Arr [ i ] = new int [ ColCount ]; // Создаем i-ый массив-строку

Для освобождения памяти необходимо:

Сначала в цикле удалить RowCount массивов-строк;

2. затем удалить “вертикальный” массив.

for ( int i = 0; i < RowCount; ++ i )

delete [ ] Arr [ i ]; // Удаляем i-ый массив-строку

delete [ ] Arr; // Удаляем “вертикальный” массив

Следующий рабочий фрагмент программы обеспечивает: создание такого двумерного массива размерности n на m (вводятся с клавиатуры), заполнение его некоторыми данными; вывод значений элементов массива на экран в виде таблицы; освобождение памяти:

int **CreateArr ( unsigned RowCount, unsigned ColCount )

// Создает двумерный динамический массив целых чисел из RowCount строк

// и ColCount столбцов. Возвращает адрес массива.

{

int **Arr = new int* [RowCount];

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

Arr[i] = new int[ColCount];

return Arr;

}

void FreeArr( int **Arr, unsigned RowCount )

// Удаляет двумерный динамический массив целых чисел Arr из RowCount строк

{

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

delete [ ] Arr [ i ];

delete [ ] Arr;

}

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

{

int N1 = 10,

N2 = 20;

cin >> N1 >> N2; // Вводим размерности массива

int ** Arr = CreateArr ( N1, N2 ); // Создаем массив

// Начинаем работу с массивом

for ( int i = 0; i < N1; ++ i ) // Заполняем массив данными

for ( int j = 0; j < N2; ++ j )

Arr [ i ][ j ] = i + j;

for ( int i = 0; i < N1; ++ i ) // Выводим массив на экран

{

for ( int j = 0; j < N2; ++ j )

cout << setw(4) << Arr [ i ][ j ];

cout << endl;

}

// Заканчиваем работу с массивом

FreeArr ( Arr, N1 ); // Освобождаем память

system ( "pause" );

return 0;

}

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

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

По аналогии с двумерными динамическими массивами можно создавать и массивы большей мерности.

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

Одномерный однонаправленный список представляет собой совокупность отдельных элементов, каждый из которых содержит две части – информационную (Inf) и адресную (Adr). Информационная часть предназначена для хранения “полезных” данных и может иметь практически любой тип. Адресная часть каждого элемента содержит адрес следующего элемента списка. Схематическое изображение такого списка представлено на следующем рисунке.

Список может содержать произвольное количество элементов. Адресная часть последнего элемента списка содержит нулевой адрес, свидетельствующий об окончании списка.

Для работы со списком достаточно знать только адрес первого элемента списка (Beg). Зная адрес первого элемента списка можно последовательно получить доступ к любому другому его элементу.

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

Типовыми операциями при работе со списками являются:

· создание списка;

· освобождение памяти от списка (удаление списка);

· доступ к заданному элементу списка для манипуляций с его информационной частью;

· добавление нового элемента к списку;

· удаление элемента из списка;

· перестановка элемента списка на новую позицию внутри списка.

Рассмотрим эти операции на примере списка, в котором информационные части представляют собой, например, вещественные числа типа double. Все эти операции оформим в виде отдельных функций.

Прежде всего, определим необходимые типы данных для работы со списком.

Поскольку каждый элемент списка должен иметь две части, логичнее всего представить его в виде следующей структуры:

struct t_Item

{

double Inf;

t_Item * Adr;

};

Для того чтобы хранить в списке другие данные (не double), достаточно заменить тип double поля Inf на другой необходимый тип данных.

Тип адресного поля этой структуры определен как указатель на тип данных элемента списка (t_Item * Adr).

Создание списка

Представленная ниже функция CreateList обеспечивает создание динамического однонаправленного списка на Length элементов и возвращает адрес первого элемента созданного списка.

t_Item *CreateList ( unsigned Length )

{

t_Item *Curr = 0, // Адрес очередного элемента списка

*Next = 0; // Адрес следующего за очередным элемента списка

// Начинаем создавать список с последнего элемента

for ( unsigned i = 1; i <= Length; ++ i )

{

// Создаем очередной элемент списка

Curr = new t_Item;

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

// за очередным элемента списка

Curr->Adr = Next;

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

// следующего элемента для следующего шага цикла

Next = Curr;

}

// Возвращаем адрес последнего созданного элемента,

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

return Curr;

}

Для создания списка используется цикл на Length итераций. На каждом шаге этого цикла в динамической области памяти создается очередной элемент списка с адресом Curr и в его адресную часть Curr->Adr записывается адрес следующего за ним элемента Next. Наиболее простой алгоритм работы этой функции получается в том случае, когда список начинает создаваться не с первого элемента, а с последнего.

Использовать эту функцию для создания списка можно, например, так:

t_Item *List = CreateList ( 5 );

Переменная List будет содержать адрес первого элемента динамического списка, содержащего 5 элементов. Информационные части элементов этого списка в функции CreateList не инициализируются и будут иметь после выхода из функции непредсказуемые значения.

Заполнить информационные части элементов этого списка конкретными данными, например, с клавиатуры можно так:

// Чтобы не потерять адрес начала списка (он нам понадобится для дальнейшей

// работы со списком) вводим дополнительную переменную-указатель Curr – адрес

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

t_Item * Curr = List;

// Выполняем цикл пока адрес очередного элемента списка не равен 0

while ( Curr )

{

// Вводим данные в информационную часть очередного элемента с клавиатуры

cin >> Curr->Inf;

// Делаем очередным следующий элемент списка. Для этого переменной

// Curr присваиваем адрес следующего элемента списка. Последний элемент

// списка содержит в адресной части 0, поэтому кода мы обработаем последний

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

Curr = Curr->Adr;

}

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

Curr = List;

while ( Curr )

{

// Выводим информационную часть очередного элемента на экран

cout << Curr->Inf << “ “;

Curr = Curr->Adr;

}

cout << endl;

Удаление списка

После окончания работы со списком необходимо освободить от него динамическую память. Для этого можно использовать следующую функцию, имеющую единственный параметр-ссылку Beg – адрес начала списка:

void DeleteList ( t_Item * &Beg )

{

t_Item *Next; // Указатель на следующий элемент списка

// Начинаем с начала списка

while ( Beg )

{

// Запоминаем адрес следующего элемента списка. Если этого не сделать,

// то после удаления элемента по адресу Beg негде будет взять адрес

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

Next = Beg->Adr;

// Удаляем первый элемент списка

delete Beg;

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

// следующего после удаленного (мы его запомнили чуть выше)

Beg = Next;

}

}

После окончания работы эта функция возвращает через свой параметр-ссылку Beg адрес 0 – список отсутствует (он перестал существовать).

Использование этой функции:

DeleteList ( List );

Если проверить значение указателя List после вызова этой функции, то оно действительно будет равно 0, что будет свидетельствовать о том, что список не существует.

Доступ к заданному элементу списка

Функция 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;

}

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

Стек

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

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

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

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

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

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

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

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

struct t_Item

{

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

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

};

class List

{

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

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;

}