Struct List

{ // -- поля данных --

char name[20]; // имя

Int age; // возраст

// -- поля связи ---

List *next; // указатель на следующий

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

List *start; // start - специальный глобальный

// указатель для входа в список

// для пустого списка должен

// быть равен нулю

Для этого списка определены три операции:

- добавление нового элемента списка Add();

- удаление элемента из списка Del();

- переход к следующему элементу списка Next().

Рассмотрим их.

Исследование операций с элементами связанных списков

1. Добавление нового элемента списка Add().

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

List* Add(List *cur) // cur - текущий эл-т

{

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

List *p=(List*)malloc(sizeof(List)); // p - новый эл-т if(!p) // если выделить память не удалось

{

cout<<" Error!";

return 0;

}

if(!start) // если список пуст

{

start=p; // то новый элемент будет первым

p->next=NULL; // и последним в списке

return p;

}

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

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

// последующим

p->next=cur->next;

cur->next=p; // связываем текущий элемент с новым

Return p; // возвращаем указатель на новый элемент

}

Динамическое создание новых элементов списка производится с использованием стандартной функции работы с памятью malloc():

List *p=(List*)malloc(sizeof(List));

Рассмотрим подробнее этот оператор. Функция sizeof(List) определяет размер структуры List в байтах. Функция malloc() выделяет блок памяти этого размера. Результат выполнения этой функции преобразуется к типу указатель на структуру List - (List*), то есть возвращает указателю p типа структуры List адрес первого байта выделенной памяти.

2. Удаление элемента из списка Del().

// функция удаления элемента списка

void Del(List *cur) // cur - указатель удаляемый элемент

{

// создаем указатель для перемещения и

// устанавливаем на начало

List *p=start;

if (cur==start) // если удаляем первый эл-т списка

{

Free(start); // освобождаем память

start=start->next;// второй делаем первым

return;

}

// выполняем, пока не достигли конца списка

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

while (p && p->next!=cur)

p=Next(p); // переходим к следующему

if(!p) // дошли до конца не найдя предшествующего

{

cout << "Не найден элемент";

return;

}

// связываем предыдущий с последующим

p->next=cur->next;

// освобождаем память текущего

free(cur);

return;

}

3. Переход к следующему элементу списка Next().

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

List* Next(List *cur)

{

// возвращаем указатель на следующий элемент списка

return (cur->next);

}