алгоритмы и структуры данных. СанктПетербургский государственный университет телекоммуникаций им проф. М. А

• Название: СанктПетербургский государственный университет телекоммуникаций им проф. М. А
• Анкор: алгоритмы и структуры данных
• Дата: 27.11.2022
• Размер: 0.88 Mb.
• Имя файла: Prezent._lekc.ASD_3.pdf
• Тип: Лекция; #815031

Санкт-Петербургский
государственный университет
телекоммуникаций им. проф. М. А.
Бонч-Бруевича
Кафедра Безопасности информационных
систем
Алгоритмы и структуры данных
Лекция 3. Линейные структуры данных.
©Кривцов Александр Николаевич
[e-mail]
© Моисеев Игорь Анатольевич
mig1256@
mail.ru

Лекция 3. Линейные структуры данных.
Линейные списки. Линейный однонаправленный список.
Часто используемые на практике структуры данных представляют собой не прос- то объект, содержащий объекты других типов, но объект, связанный с внешними объектами или ресурсами посредством ссылок или указателей. Массивы являются удобной формой хранения данных в том случае, когда объем данных в процессе обработки заранее известен и не подвержен изменениям. Иногда структура данных в связи с моделируемой пред- метной областью такова, что заранее нельзя предсказать их объем, а также часто возникает необходимость в операциях удаления и добавления элементов. Для структуры данных типа
«массив» - это «неудобные» операции, так как требуют дополнительных усилий по преобразованию массивов. Если нам в основном нужен последовательный перебор эле- ментов, их можно организовать в виде связного списка (linked list) – базовой структуры данных, в которой каждый элемент содержит информацию, необходимую для получения следующего элемента. Основное преимущество связных списков перед массивами заклю- чается в возможности эффективного изменения расположения элементов. Эта гибкость достигается за счет скорости доступа к произвольному элементу списка, поскольку един- ственный способ получения элемента состоит в проходе по ссылкам от начала списка.
Таким образом, связный список – это базовая структура данных, в которой каждый элемент содержит информацию, необходимую для получения следующего элемента. Наиболее простой динамической структурой является однонаправленный (односвязный) список,
элементами которого служат объекты структурного типа. В классическом варианте, связный список состоит их элементов, называемых узлами. Каждый узел включает в себя в клас- сическом варианте два поля:


информационное поле (поле данных), в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой – вектором, массивом, объектом класса, другой струк- турой и т.д.;

адресное поле (поля связок), в котором содержатся один или несколько указателей,
связывающий данный элемент с другими элементами структуры;
Связный список, содержащий только один указатель на следующий элемент), называется односвязным (однонаправленным).
Каждый узел односвязного линейного списка содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL). В
списках существует понятие корневого (первого) узла списка, который задается указателем этого первого элемента списка (Head). Это означает, что для создания всего списка элементов, вначале нужно инициализировать создание в памяти первого его элемента.

Основными операциями для работы с однонаправленными списками, являются:

создание (инициализация) списка;

вставка (добавление) узла в список;

удаление узла из списка;

удаление (корня) списка;

проверка пустоты (существование) списка;

поиск элемента в списке;

взаимообмен двух узлов в списке;

вывод (просмотр) узлов списка.
Часто, для представления узлов списка используют две структуры:
Структуру для представления данных, например,
struct Data
{
Int a;
};
Здесь в качестве примера данных используется только одно целочисленное поле. Следует заметить, что данные узлов могут быть различными и представлены не только одним полем.

Структура для представления узла
(Node) списка, может быть следующей struct Node
{
Data d;
// поле для данных типа Data
Node *next; // поле указателя next на следующий элемент такого же узла
};
Объявленная переменная
d будет считываться (откуда-либо) и передаваться в элемент списка. Элемент списка будет, как бы, «прицепляется» к уже существующему списку.
Переменная
d является информационным полем каждого отдельного элемента из списка.
Далее рассмотрим как производится инициализация списка.
Инициализация списка.
Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение. Для эффективного исполь- зования связных списков ключевое значение имеет выделение памяти. Выше описана единственная структура (struct
Node), но она может существовать во множестве экземпляров - по одному для каждого узла, который придется использовать. Как только понадобится новый узел, для него нужно выделить память. При объявлении переменной типа
Node для нее резервируется память во время компиляции. Однако часто приходится организовывать вычисления, связанные с резервированием памяти во время выполнения - с помощью вызовов системных операций управления памятью. Например, в строке кода
Node x = new Node; содержится операция new, которая резервирует для узла достаточный объем памяти и возвращает указатель на него в переменной
x.

Способ программной инициализации может быть различным, например, с помощью функции, конструктора или метода класса. В примерах ниже будем рассматривать функциональные, варианты.
Функция инициализации корневого узла списка.
List * Init_List(int h)
{
Node *x; //объявляем указатель типа List
x = new Node; // выделение под него памяти списка
x->d.a = h; // записываем значение
x->next = NULL; // определяем ссылку на следующий узел return(x);
}
В качестве аргумента функция
Init_List () получает значение данных (целое число). Функция инициализирует узел адресом в памяти (операция
new), помещает данные по этому адресу
(
x->d.a) и устанавливает указатель данного узла на следующий узел в NULL.
Итак, список создан, теперь добавим в него новый узел.

Добавление (вставка) нового узла
Общая схема вставки нового узла в список включает следующие шаги:

создание узла и заполнение его полей;

переустановка указателя предшествующего узла на добавляемый узел;

установка (настройка) указателя добавляемого узла на следующий узел.

Следует заметить, эта операция возможна тогда, когда список уже существует. Простейшая операция вставки – добавление нового элемента в конец списка.
void Insert_End(Node *x, int n)
{ Node *t = x; //узел t такой же как x – начало списка.
for (int i=1;i<=n;i++)
{
t->next=new Node; //выделяем память под новый следующий элемент
t=t->next;
// текущий указатель перенаправляем на следующий элемент
cin>>t->d.a;
//вводим данные в новый узел
t->next=NULL;
// инициализируем нулем указатель на последний элемент
}
}
Если список был создан, то другие операции вставки – в начало или в середину – требуют обязательного определения места вставки. Это место определяется «ключом», в качестве которого можно использовать, значение элемента или номер узла, или его адрес в памяти.
Если использовать значение, то следует упорядочить список по какому-либо критерию. И
тогда вставка нового узла будет производиться слева (справа) от узла с искомым значением.
Если – это номер узла, то реализуется предыдущая схема, но для этого нужно ввести еще одну переменную для хранения индекса (номера) узла. Второй случай предпочтительней,
так как не требует операций поиска по значению, а доступ к элементу будет осуществляется непосредственно по этому индексу. В третьем случае вставка осуществляется непос- редственно в указанное место, например, до или после адреса существующего узла. Тогда необходимо определить этот адрес. Особенностью операции вставки является то, что при

ее выполнении нужно «отслеживать» случай, когда вставка нового узла осуществляется на место корневого узла. Для однонаправленных линейных списков операции вставки проще осуществляются после найденного элемента (если это вставка не по номеру узла), так как операция вставки «до» требует дополнительной операции перенастройки указателей узлов, например, так, как это показано на рисунке ниже.
Функция добавления (вставки) узла по номеру в списке
Insert_Number() получает в качестве аргументов указатель на корневой узел, значение места (индекса) вставки в список и значение данных для этого нового узла. Функция инициализирует новый узел и его данные; проверяет список на «пустоту» и создает его следующим образом:

вставляет новый узел в указанное место, а если это место является местом корневого узла,
то переназначает корневой узел, сдвигая, тем самым, все элементы вправо. Результатом работы функции является указатель на корневой узел нового списка.
Node *Insert_Number (Node *u, int n, int h)
{
// инициализируем новый узел
Node *t = new Node;
t->d.a=h;
t->next=NULL;
// проверка списка на «пустоту»
if (u == NULL)
// если список пуст
u = t;
//создаем первый элемент списка
else
{
// если список не пуст
Node *p=u;
// устанавливаем указатель на начало
// если индексы элементов меньше заданного индекса и эти узлы не конечные
for ( int i=1; inext!=NULL; i++)
p=p->next;
// перенаправляем указатель, оставляя порядок узлов неизменным
if(n==1) // если место вставки – место корневого узла, то переопределяем корень
{ t->next=u; // корневой узел становится следующим узлом
u=t;
// новый узел становится корневым (первым в списке)
}
else // если место вставки – не место корневого узла
{ t->next=p->next; // вставка по схеме, рассмотренной ранее

p->next=t;
}
}
return u;
// возвращаем указатель на корневой узел нового списка
}
Функция добавления узла (вставки) по значению данных («до») принимает два аргумента:
ссылку на корневой узел и данные для нового узла. Для определения места вставки нового узла новые (искомые) данные сравниваются со значениями данных в существующих узлах.
И, как только будет найден узел, данные которого не больше искомых, происходит вставка нового узла перед найденным узлом. Для передачи параметра с новыми данными их нужно задать перед вызовом этой функции, например, следующим образом
Data D;
cin>>D.a;
Так же, как и для примера, рассмотренного выше, здесь требуется проверка списка на «пус- тоту»; проверка условия при котором данные корневого узла окажутся не больше искомых данных; проверка условия вставки в заданное место и проверка случая, когда данные будут помещены в конец списка.
Node *Insert_Data(Node *u, Data &x)
{ // определяем новый узел и его значение
Node *p=new Node;
p->d.a = x.a;
// проверка на «пустоту» списка

if(u== NULL)
{
// если список пуст, то корневым узлом становится новый узел
p->next= NULL;
u=p;
return u; // завершаем работу функции и возвращаем указатель на новый список
}
// если список не пуст, то
Node *t = u;
//устанавливаем указатель на его начало
// проверка искомых данных с данными корневого узла
if(p->d.a <= t->d.a) // если данные совпали или меньше,
{
// меняем местами корневой узел с новым
p->next = t;
u = p;
// корневым узлом стал новый узел
return u; // завершаем работу функции и возвращаем указатель на новый список
}
// «треугольник» поиска места вставки нового узла, рисунок ниже
Node *t1=t->next;
// устанавливаем указатель на следующий элемент списка
while(t1)
// пока список существует (t1->next != NULL)
{ if( p->d.a <= t1->d.a) // если выполняется критерий поиска, то

{ p->next=t1;
// текущий проверяемый узел становится следующим,
t->next=p;
// на его место становится новый узел и
return u; // выходим из функции, возвращая указатель на новый список
}
// если критерий поиска и вставки не выполняется, то
t=t1;
// переходим к следующему узлу и
t1=t1->next;
// возобновляем цикл проверки
}
// если в цикле проверке критерий вставки не найден, узел считается новым
t->next = p;
// добавляем его в конец существующего списка
p->next = NULL;
return u; // завершаем работу функции и возвращаем указатель на новый список
}

В заключение рассмотрим функция добавления (вставки) узла по адресу («после»).
void Insert_Node (Node *x, int h)
{
struct Node *t;
t = new Node;
// выделяем память для вставляемого узла
t->next = x->next;
// сохранение указателя на следующий узел
t->d.a=h;
// сохранение поля данных добавляемого узла
x->next=t;
// предыдущий узел указывает на следующий элемент
}
Функция добавления узла в существующий список принимает два аргумента: указатель на узел (адрес) после которого происходит добавление нового узла и значение поля данных для этого узла. Код функции составлен в соответствии со схемой рассмотренной выше.
Теперь рассмотрим задачу вывода (печати) информации содержащейся в созданном пос- редством рассмотренных выше функций списке. Функция
Print_Node() реализует вывод элементов списка на экран. В качестве аргумента в функцию вывода элементов передается указатель на корень списка. Функция осуществляет последовательный обход всех узлов с выводом их значений.
void Print_Node(Node *u)
{ Node *p = u;
// указатель на начало
while(p)
// пока узел существует
p!=NULL
{ cout << p->d.a; // вывод его содержимого

p = p->next;
// переадресация на следующий узел
}
}
Определение адреса узла равнозначно операции поиска элемента по его ключу.
В линейном списке, так же, как и в массиве, последовательный поиск происходит за один проход и в худшем случае имеет порядок О(n). Рассмотрим пример, в котором функция
Find_Node() находит его адрес по значению поля данных. Функция поиска узла в существу- ющем списке принимает два аргумента: указатель на начало списка и адрес поля данных.
Данные связаны с узлами. Поэтому для вычисления и передачи адреса искомых данных в узле нужно их задать перед вызовом этой функции, например, следующим образом
Data D;
cin>>D.a;
А затем вызвать эту функцию командой:
Node *v=Find_Node(u,D); Функция поиска адреса узла по значению поля данных приводится ниже.
Node * Find_Node(Node *u, Data &D)
{
Node *p = u;
int i=1; //переменная-счетчик узлов
while(p) //пока список существует
{
if(p->d.a == D.a) // условие для поиска
{
return p; // возвращаем адрес найденного узла с таким полем данных
}

p = p->next;
i++;
} // счетчик примет значение номера найденного узла
}
В результате, будет найдено первое вхождение искомого элемента в списке, адрес его узла и, если нужно, номер узла в списке. Если после этого вызвать функцию с такими, например,
аргументами командой
Insert_Node(v,25), то новый узел с числом 25 вставиться после узла с числом
D.a.
Приведенные выше примеры вставки и поиска, ключами для которых являются значения индекса узла или его данных, позволяют реализовывать различные операции ообмена данными, меняя местами элементы списков. В частности, так же, как и массивы,
линейные списки можно упорядочивать по какому-либо критерию. Рассмотрим функцию сортировки
Sort_Node(), которая упорядочивает узлы списка по убыванию значений их данных.
void Sort_Node(Node *u)
{
Node *t=new Node; // список для перестановки узлов
Node *p = u; // устанавливаем указатель на начало
while(p)
// пока список существует,
{ t=p->next;
// устанавливаем указатель на его следующий элемент и,
while(t)
// пока не найден конец списка,

{
// проверяем значения двух соседних элементов
if (p->d.a < t->d.a) // если значение левого меньше значения правого,
swap(p->d.a, t->d.a);
// меняем только значения данных этих узлов,
t=t->next;
// переходим к следующему элементу внутреннего цикла
} // больший по значению элемент найден,
p = p->next; // сдвигаемся на позицию вправо во внешнем цикле
}
}
В данной функции реализован классический алгоритм сортировки прямым обменом
(«пузырек). «Треугольник» обмена сортировки выполняет встроенная функция swap()
стандартной библиотеки STL С++. Над линейными списками допустимы такие же методы сортировки данных, как и для массивов, если ключом являются данные. Заметим, что адреса узлов списка при этом не изменяются.
Так же, как и для операции вставки, операция удаления связана с изменением значений адресных полей в списке. Удаляется тот узел, на который установлен указатель. И
так же, как при вставке, нужно анализировать, является ли удаляемый узел корневым или нет. Переадресация указателей для первого или последующих отличаются друг от друга:
если удаляется корневой узел, то корневым становится узел, следующий за ним в случае,
когда нужно сохранить список. Если не делать такой переадресации, то при удалении корневого узла считается, что «удаляется» весь список. В случае, когда удаляется не корневой узел переадресация указателей осуществляется так, что все последующие узлы сдвигаются влево. При удалении узлов следует помнить об операции освобождения динамической памяти
delete.

Функция удаления узла по значению поля данных.
Node *Del_Node_Dat(Node *u, Data &x)
{
if (u == NULL) // список пуст - удалять нечего!
{ return u; }
Node *t = u;
if( t->d.a == x.a) // если список не пуст и удаляется начало
{ u = t->next;
// корневым узлом становится следующий элемент
delete t;
// освобождаем память от удаляемого узла («старого» корня)
return u;
// возвращаем значение нового списка
}
Node *t1 = t->next;// устанавливаем указатель на следующий элемент после корня
while (t1)
// если удаляемый элемент не корень, то
{
// просматриваем все остальные узлы и,
if (t1->d.a == x.a)
// если искомый ключ найден в текущем узле, то
{
// перенастраиваем предыдущий указатель («до»)
t->next = t1->next;
// на следующий («за»),
delete t1;
// и удаляем текущий узел из памяти

return u;
// возвращаем значение нового списка
}
// если искомый ключ в текущем узле, не найден то
t = t1;
// сдвигаемся вправо на следующий узел
t1 = t1->next;
}
}
}
Операция удаления корневого узла и освобождения памяти от него лишь имитируют удаление всего списка. Другие элементы продолжают «жить» в памяти, пока данная программа не будет завершена. Сказанное можно сравнить с реалиями, при которых, например, случайно удаленная папка с файлами на компьютере не означает, что файлы потеряны навсегда. В частности, признаком наличия объектов линейного списка является объект-корневой узел. Чтобы освободить память от всего списка, увеличив, тем самым, ее свободное пространство, нужно удалить все элементы списка. Проще всего это сделать с помощью рекурсивной функции. В рассмотренной функции
Del_Node_List() нужно переставлять указатель на следующий элемент списка до тех пор, пока указатель не станет равен NULL, то есть не будет достигнут конец списка. После чего – удалить корневой узел.
Это нерационально, поэтому ниже приводится рекурсивная функция удаления всего списка.
Node *Del_Node_List(Node *x)
{ if(x==NULL)
// если список пуст и удалять нечего, то
return x; // выходим из рекурсии, возвращая NULL
if (x != NULL)
// если список не пуст

{
Del_Node_List(x->next);
delete x;
// рекурсивно удаляем все узлы
}
}
В однонаправленном линейном списке обход узлов происходит в одном направ- лении – по одной ссылке (указателю) на следующий узел. Многие операции над списком могут быть ускорены и упрощены, если просмотр (обход) узлов организовать в обоих направлениях. Такую возможность представляют двусвязные списки. Двухсвязный (ли- нейный) список – это структура данных, в которой каждый элемент имеет поля с данными и два указателя: один указатель хранит адрес предшествующего элемента списка, второй —
адрес последующего элемента. В первом и последнем узле соответствующие указатели принимают значение
NULL.
Основные операции, выполняемые над двунаправленным списком, те же, что и для однонаправленного списка:


Инициализация списка

Добавление узла в список

Удаление узла из списка

Удаление корня списка

Вывод элементов списка в прямом порядке

Вывод элементов списка в обратном порядке

Взаимный обмен двух узлов списка
Так как двунаправленный список более гибкий, чем однонаправленный, то при вставке эле- мента в список, нужно использовать указатель как на элемент, за которым происходит вставка, так и указатель на элемент, перед которым происходит вставка. При удалении эле- мента из списка нужно использовать как указатель на сам удаляемый элемент, так и ука- затели на предшествующий или следующий за удаляемым элементы. Но так как элемент двунаправленного списка имеет два указателя, то при выполнении операций встав- ки/удаления элемента надо изменять больше связей, чем в однонаправленном списке.
В отличие от однонаправленного списка в двусвязном списке нет необходимости обеспе- чивать позиционирование какого-либо указателя именно на первый элемент списка, так как благодаря двум указателям в элементах можно получить доступ к любому элементу списка из любого другого элемента, осуществляя переходы в прямом или обратном направлении.
Однако по правилам хорошего тона программирования указатель желательно ставить на заголовок списка. Так же, как и в односвязном списке, для представления узлов списка обычно используют две структуры:

Структуру для представления данных, например,
struct Data
{ int a;
};
В примере, в качестве данных, используется только одно поле целого типа. Напомним, что данные узлов могут быть различными и представлены не только одним полем.
Структуру для представления узла
Node списка, отличающуюся от односвязного списка на- личием еще одного указателя, например,
struct Node
{
Data d;
// поле для данных типа Data
Node *prev;
// поле указателя prev на предыдущий узел
Node *next;
// поле указателя next на следующий узел
};
Дальше рассмотрим особенности основных операций над двусвязным списком.
Перед вызовом функции инициализации из основной программы объявляются (и задаются)
соответствующие элементы
int main()
{
Node *u;
// определение корневого узла
int a;
// определение данных
cin>> a;
// ввод данных для корневого узла

u=Init_List2(D);
// вызов функции инициализации корневого узла
return 0;
}
Функция инициализации корневого узла
Node * Init_List2(int h)
// h- значение первого узла
{
Node *lst;
lst = new Node;
// выделение памяти под корневой узел
lst->d.a = h;
// сохранение данных в узле
lst->next = NULL;
// указатель на следующий узел
lst->prev = NULL;
// указатель на предыдущий узел
return (ist);
}
Если начальный узел списка уже создан, то добавление новых элементов возможно после- довательно слева или последовательно справа от этого корневого элемента, в зависимости от настройки указателей. Рассмотрим схему, при которой добавление новых узлов (
new)
будет происходит справа от существующих . Добавление узла включает следующие этапы:

создание узла добавляемого элемента и заполнение его поля данных;

переустановка указателя «следующий» узла, предшествующего добавляемому, на до- бавляемый узел (
next_1 -> new);

переустановка указателя «предыдущий» узла, следующего за добавляемым, на добав- ляемый узел (
prev_2->new);


установка указателя «следующий» добавляемого узла на следующий узел (тот, на кото- рый указывал предшествующий узел) (
next_new->2);

установка указателя «предыдущий» добавляемого узла на узел, предшествующий до- бавляемому (
prev_new->1).
Схема добавления узла в двусвязный список «справа»
Функция добавления нового узла после текущего приведена ниже. В качестве аргументов функция
Insert_List2() принимает указатель на текущий узел и значение для данных нового узла и возвращает указатель на новый (вставленный) узел. В процессе работы используется
«вспомогательный» узел для организации «треугольника» перестановки.

Node * Insert_List2(Node *x, int h)
{ Node *new_node, *p; //определение указателей на новый и вспомогательный узлы
p = x->next;
// сохранение указателя узла (1) на следующий узел (2)
new_node = new Node;
new_node->d.a = h;
// сохранение поля данных добавляемого узла
x->next = new_node;
// предыдущий узел (1) указывает на новый
new_node->next = p;
// созданный узел указывает на следующий узел (2)
new_node->prev = x;
// созданный узел указывает на предыдущий узел (1)
if (p != NULL)
p->prev = new_node;
// предыдущий узел (2) указывает на новый
return(new_node);
// возвращение указателя созданного узла
}
Теперь рассмотрим реализацию обхода узлов для подобного списка. В отличие от одно- связного списка, за счет наличия второго указателя, над двусвязным списком возможна операция обхода узлов в прямом (по ссылкам
next) и обратном (по ссылкам prev) направ- лениям, если известно начало (
Begin) конец (End) списка узлов обхода. Функция обхода (и вывода) узлов в прямом порядке
Print_List2_Begin() аналогична функции Print_Node() для односвязного списка. В качестве аргумента на вход подается значение корня узла (
Begin).
Обход и вывод узлов происходит по ссылкам
next.
void Print_List2_Begin(Node *x)
{ Node *p = x;
// p=Begin
do {
cout<
d.a<<" "; // вывод значения данных текущего узла
p = p->next;
// переход к следующему узлу

} while (p != NULL);
// условие окончания обхода
}
Если на вход функции подать адрес узла (
Begin), с которого нужно начать обход, то будут выведены все узлы справа от него, включая узел
Begin. Адрес узла можно вычислить так же,
как это сделано в примере для поиска адреса узла в односвязном списке.
Функция обхода (и вывода) узлов в обратном порядке Print_List2_End() работает по ука- зателями
prev, то есть «справа» на «лево». Поэтому требует на вход либо непос- редственный адрес последнего узла, либо перенастройку адреса входящего узла
(Begin) на адрес конца выводимого списка (
End), чтобы вывести (обойти) все узлы, начиная с End до
Begin включительно. Вариант реализации функции может быть таким:
void Print_List2_End(Node *x)
{ Node *p=x;
// p=Begin
while (p->next != NULL)
p = p->next;
// переход к концу списка (p=End)
do
{
cout<< p->d.a<<" "; // вывод значения данных текущего узла
p = p->prev;
// переход к предыдущему узлу
} while (p != NULL);
// условие окончания обхода
}

Удаление узлов происходит по схеме, обратной схеме для вставки узлов и по аналогии с примерами удаления узлов односвязного вписка. Чтобы удалить весь список вместе с кор- нем, можно применить рекурсивную функцию
Del_List2(), аналогичную функции
Del_Node_List() .
Следующую рекурсивную функцию можно использовать для удаления всего двусвязного списка.
Node *Del_List2 (Node *x)
{ if(x==NULL)
// если список пуст и удалять нечего, то
return x;
// выходим из рекурсии, возвращая NULL
if (x != NULL)
// если список не пуст
{
Del_Node_List(x->next);
delete x;
// рекурсивно удаляем все узлы
}
}
Для удаления конкретного узла, можно воспользоваться функцией
Del_Node_List2(),
которая вначале перенастроит указатели предыдущего и следующего узлов, а затем удалит этот узел. На вход этой функции нужно подать «ключ»: либо номер узла, либо его адрес,
либо значения данных.
Рассмотрим функцию удаления узлов двусвязного списка. Пусть на вход функции подается номер узла удаления (h), тогда:

Node *Del_List2_Node(Node *x, int h)
{
Node *p=x;
if(h==1) // если номер совпал с номером корневого узла
{ p->prev=NULL; // устанавливаем prev следующего узла в NULL
x=p->next;
// делаем следующий узел корневым
delete p;
// удаляем прежний корень
return x;
// возвращаем новый список
}
int n=2;
// устанавливаем индекс номера на второй элемент
Node *p1=p->next;// устанавливаем указатель на второй элемент
while(p1)
{ if(n==h)
// если номер найден
{p->next=p1->next;
// указатель next предыдущего узла=next->next
p1->prev=p;
// указатель prev текущего узла указывает на предыдущий узел
delete p1;
// удаляем найденный узел
return x;
// возвращаем новый список
}
// в случае, если искомый номер не совпал с номером узла, повторяем
// цикл поиска
p=p1;
p1=p1->next;
n++;
}
}

Такие операции над двусвязными линейными списками как поиск, упорядочивание, взаим- ный обмен узлов местами организуются по тем же правилам, что и в линейном одно- связном списке, но с учетом перенастройки и второго указателя. Односвязные и двусвязные списки данных легли в основу других абстрактных (пользовательских) типов данных линей- ной структуры. Рассмотрим некоторые из них.
Циклический (кольцевой) список.
На практике нередко возникают задачи, при которых требуется последовательный про- смотр данных по «кругу», когда последний элемент замкнут на первый или наоборот, пер- вый – на последний. Например, операция поиска и замены элементов текста в текстовых файлах современных редакторах. Такие операции реализуются с помощью специальных линейных структур, называемых кольцевыми (циклическими) списками. Кольцевой список
— это список, у которого последний элемент связан с первым. Кольцевой список можно сделать как односвязным, так и двухсвязным.

Ясно, что эти типы данных являются абстракциями линейного односвязного и двусвязного списков. Отличие состоит лишь в том, что при инициализации кольцевых списков – в одно- связном линейном списке указатель
next последнего элемента устанавливается не в NULL, а замыкается на первый элемент; в двусвязном списке – еще и указатель
prev первого элемента устанавливается на последний элемент. При выполнении операций обхода нужно
«отслеживать» признаки первого или последнего элемента. Рассмотрим эти особенности на примере линейного односвязного кольцевого списка. Для представления его узлов используют те же две структуры.
Для представления данных
struct Data
{
int a;
};
Для представления узлов
(Node) списка
struct Node
{
Data d;
// поле для данных типа Data
Node *next; // поле указателя next на следующий элемент такого же узла
};
При инициализации в функции
Init_Circle_1() корневого узла, его указатель next «замы- кается» сам на себя.

Node * Init_Circle_1(int h) // h- значение первого узла
{
Node *p;
p = new Node;
// выделение памяти под корень списка
p->d.a = h;
// сохранение данных
p->next = p;
// указатель на корневой узел
return(p);
}
Ввод узлов циклического списка реализуется функцией
Insert_Circle_1() в которой у каждого нового узла (
new_node), его указатель next устанавливается на корневой узел.
Node * Insert_Circle_1(Node *x, int h)
{
Node *new_node, *p;
p = x->next;
// сохранение указателя узла на следующий узел
new_node = new Node;
new_node->d.a = h;
// сохранение поля данных добавляемого узла
x->next = new_node;
// предыдущий узел указывает на новый
new_node->next = p;
// созданный узел указывает на корневой узел
return(new_node);
}
В функции
Print_Circle_1() единственным отличием от функции печати односвязного списка,
или от функции обхода двусвязного списка в прямом порядке является условие окончания цикла
p!=x (пока не найден корень) – вместо p!=NULL (пока не найден признак конца списка).

void Print_Circle_1(Node *x)
{ Node *p = x;
do
{
cout<
d.a<<" "; // вывод значения элемента узла p
p = p->next;
// переход к следующему узлу
} while (p != x);
// условие окончания обхода
}
Так же, как и в обычном односвязном списке, удаление узлов циклического списка возможно по значению данных, номеру узла или его адреса. В циклическом списке указатель
next замкнут на корень. Поэтому особенностью операции удаления узла циклического списка является то, что все другие узлы, начиная со следующего после удаленного, сдвигаются «влево», и сам следующий узел становится корнем списка.
Например, если начальный список u0 = {1, 2, 3, 4, 5, 6, 7, 8, 9}, то после удаления элемента с номером, например, 5, новым списком будет список u1 = {6, 7, 8, 9, 1, 2, 3, 4}. Функция
Del_Node_Circle_1() на вход получает указатель на корень списка и номер узла, который нужно удалить. Если номер узла не совпал с искомым, то узел пропускается и поиск начи- нается со следующего узла (
цикл for()). При нахождении узла p с искомым номером,
указатель
next узла предшественника (ptr->next) устанавливается на следующий за p узел
(
ptr->next=p->next), после чего узел p удаляется (delete(p)). Функция возвращает в точку вызова указатель на новый список (
return x).

Node* Del_Node_Circle_1(Node* x, int N)
{
if (x != NULL)
{ Node *p = x;
if (x->next != x)
// если узел не последний
{ for (int i = 1; i < N; i++)
// поиска узла p->next с искомым номером
p = p->next;
Node *ptr = x;
while (ptr->next != p)
// указатели всех узлов перенастраиваем на узел p
ptr = ptr->next;
// удаление узла p
ptr->next = p->next;
if (x = p)
x = p->next;
delete(p);
}
return x;
}
Операция удаления кольцевого списка хорошо иллюстрируется на классическом примере решения задачи Иосифа («выбор лидера»). Цель ее решения такова. В круг становится k человек на позицию с соответствующим номером. На каждом шаге просмотра круга из него удаляется человек, позиция которого при просмотре равна n. Круг смыкается и поиск следующего человека с номером позиции n в новом круге продолжается. Определить, кто
(человек с первоначальным номером позиции) останется не удаленным.

Ниже представлена схема шагов решения задачи для
k=9 и n=5 (удаление каждого пятого).
Далее представлен результат работы программы решения задачи. Этот результат можно получить, доработав интерфейс вызова функции
Del_Node_Circle_1() в точке ее вызова. На- пример, через цикл вызова, условием окончания которого является признак того, что в списке остался единственный узел:
while(u->next!=u)
{
u= Del_Node_Circle_1(u, n);
Print_Circle_1(u);
}
Схема решения задачи Иосифа

Конечный результат циклического вызова функции
Del_Node_Circle_1().

Стек
Еще одной структурой, организованной на основе односвязного списка, является динами- ческая структура, называемая стеком. Следует различать понятия программного и аппарат- ного стека. Аппаратный стек используется для хранения адресов возврата из функций и их аргументов. Программный стек – это пользовательская модель (структура) данных.
Стек — динамическая структура данных, для которой выполняется дисциплина обслу- живания элементов
LIFO: последним пришёл — первым ушёл (LIFO – Last Input First
Output).
Таким образом, и дополнение новых данных, и извлечение их из стека всегда происходит с одной стороны: через вершину стека. Новые данные добавляются в вершину и удаляются из вершины.

Ясно, что, в общем случае, стек — это односвязный список, для которого определены толь- ко две операции: добавление и удаление из начала списка.
Возможные операции:

инициализация стека;

помещение элемента в стек;

удаление элемента из стека;

получение верхнего элемента стека без его удаления;

получение количества элементов стека;

определение, пуст ли стек;

вывод (печать) элементов;
Рассмотрим реализацию стека с помощью односвязного линейного списка и особенности некоторых из этих операций. Следует обратить внимание на то, что для списка типа стек нет операций вставки новых узлов в конец всего списка или между существующими узлами.
Поэтому односвязный линейный список – наиболее эффективный способ представления стека. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует, и указатель принимает значение
NULL. Если структура данных и структура узлов стека объявлены, то операция инициализации стека сводится к одной команде
Node *Stk=NULL.
Функция
Push_Stack(Node *x, int h) «вталкивает» очередное значение h в стек, на который указывает указатель
x. Новое значение размещается в голове стека, остальные данные смещаются вправо, при этом, каждый указатель
next нового узла настраивается на предыдущий узел, а значение указателя вершины – на новый узел.

Node *Push_Stack(Node *x, int h)
{ Node *t = new Node;
//память для узла
t->d.a = h;
// сохраняем значение данных узла
t->next=x;
// указатель следующего узла – предыдущий узел
x=t;
// вершина – новый узел
return x;
// возвращение нового стека
}
Вызов функции в цикле, например, так:
for (int i=1; i<=N; i++)
{ cin>>h;
Stk=Push_Stack(Stk,h);
}
позволит создать стек из
N узлов (элементов), в которых данными будут вводимые значения
h.
Вывод (печать) элементов стека производится точно также, как и вывод элементов списка
(«в прямом» порядке) по ссылкам на
next. Основываясь на тех же принципах, что при печа- ти содержимого стека, можно вычислить количество, входящих в него элементов, чтобы понять его «глубину». Функция
Count_Stack() получает указатель на вершину стека, а воз- вращает количество узлов.

int Count_Stack(Node *stk)
{ int x=0;
while(stk)
{ stk=stk->next;
x++;
}
return x;
}
Если значение «верхнего» элемента равно
NULL, то стек пуст. Быструю проверку можно осуществить с помощью, например, такой функции:
int Empty_Stack(Node *stk)
{ if(stk->next == NULL)
return 1;
// стек пуст
else
return 0;
// стек существует
}
Еще одна «полезная» операция – знание содержимого вершины без ее извлечения из стека.

int Top_Stack(Node *stk)
{
if((stk->next)!=NULL)
return stk->d.a;
// возвращаем значение стека
else
return Empty_Stack(stk);
// возвращаем 0 (через функцию), если стек пуст
}
Так как операция извлечения узлов происходит с вершины стека по одному, то, например,
зная сколько их в стеке, можно последовательно извлечь нужное количество, или извлечь все, освободив память. Функция извлечения всех узлов стека Del_Stack() и освобождения памяти может быть реализована следующим образом:
Node *Del_Stack(Node *stk)
{ int k=Count_Stack(stk);
// вычисляем количество узлов
for ( int i=0; i<=k; i++)
{
if(stk == NULL)
// проверка стека на пустоту
{ cout << " Стек пуст" << endl;
return 0;
}

Node *t = stk;
// если стек не пуст cout<< " Удаляемый узел -> "<< t->d.a <next;
// Перенастройка вершины
delete t;
// Удаление текущего узла вершины
}
return stk;
// возвращение нового стека
}
Для извлечения только одной вершины, или нескольких узлов, достаточно в данной функ- ции убрать строку с циклом
for ( int i=0; i<=k; i++), или изменить правую границу k в его па- раметрах.
Очередь
Еще одной структурой, относящейся к абстрактным типам данных, является очередь. В
очереди реализуется дисциплина
FIFO (First Input, First Output) – «первый пришел» -
«первый вышел». Очередь — это линейная динамическая структура данных, для которой выполняется правило: добавление новых данных возможно только в конец этой структуры,
а удаление (извлечение) — только с начала. Всем понятна очередь в повседневной жизни
(магазин, касса,…). Аналогичный принцип реализации очереди применяется и в програм- мировании, тогда, когда нужно совершить какие-то действия в порядке их поступления,
выполняя их последовательно. Например, запуская очередное приложение, нужно подож- дать, когда процессор освободится от выполнения предыдущего задания; посылая на пе- чать документ, он будет распечатан после печати предыдущего. нужно подождать, когда процессор освободится от выполнения предыдущего задания; посылая на печать документ,
он будет распечатан после печати предыдущего.

Очевидно, что для реализации этого правила подойдет двусвязный список – список с двумя указателями
next (следующий узел) и prev (предыдущий узел), через которые будут фик- сироваться начало (
Begin) и конец (End) очереди.
В силу определения очереди, основными операциями являются вставка (помещение) но- вого узла только в конец, а извлечение узла – только с начала этого списка.
Для инициализации двусвязного очереди при ее объявлении используются такие же структуры, что и для двусвязного списка: структура для данных узлов, например,
struct Data
{ int a; };
и структура для описания узла, например,
struct Node_Q
{
Data d;
// поле для данных типа Data
Node_Q *prev;
// поле указателя prev на предыдущий узел
Node_Q *next;
// поле указателя next на следующий узел
};

Первый шаг – объявление (инициализация) узлов:
Node_Q *Begin=NULL;
// указатель на начальный узел очереди
Node_Q *End=NULL; // указатель на конечный узел очереди
Функция добавления новых узлов в конец очереди
Add_Queue() :
Node_Q *Add_Queue (Node_Q **Begin, Node_Q **End, Data &x)
{ Node_Q *t = new Node_Q;
// Память под новый элемент
t->d.a = x.a;
// Запоминание значения данных
if(*Begin == NULL || *End == NULL)
{ // Если очередь была пуста
t->prev = NULL;
t->next = NULL;
*Begin = *End = t; // адреса начального и конечного узлов настраиваем на текущий
return t;
}
else
// В очереди был хотя бы один элемент
{ t->prev = *End; // указатель его предыдущего элемента настраиваем на адрес конца
(*End)->next = t; // переадресуем указатель next того узла, который был конечным на
// создаваемый узел
t->next = NULL; // указатель следующего узла для него = NULL (инициализация узла)
*End = t;
// адрес конца текущей очереди настраиваем на создаваемый узел
return t;
// возвращаем указатель на новую очереди

}
}
Обратиться к функции из программы можно, например, так:
q = Add(&Begin, &End, x);
где
q – объект типа Node_Q (узел); Begin и End – адреса начала и конца очереди; x —
объект типа
Data (значение данных). В процессе работы функция проверяет очередь на пустоту, создает заголовочный узел, если это так и добавляет в конец очереди новый узел,
перенастраивая адреса «головы» и «хвоста». Функция возвращает в точку ее вызова новую очередь.
Если при вызове функции обращение к ней организовать в виде цикла, например,
for(int i=1; i<=N; i++)
{ cin>>D.a;
q=Add_Queue(&Begin,&End,D);
}
cout<d.a<<" "<d.a<
то будет создана очередь из
N элементов, и, по завершению ее создания, будут получены значения данных начального и конечного узлов.
Как и для двусвязного списка очередь можно просмотреть и в прямом (с головы), и в обрат- ном (с хвоста) порядке. Для этого нужно в качестве начальных аргументов в точку вызова функции посылать указатели на «голову» или «хвост», а при выводе использовать указатели либо
next, либо prev. Например, функция Print_Queue() реализует оба таких просмотра.

void Ptint_Queue(Node_Q *Begin, Node_Q *End)
{ Node_Q *p = Begin; // вывод в прямом порядке (с головы)
while(p)
{ cout << p->d.a << " ";
p = p->next;
}
p=End; // вывод в обратном порядке (с хвоста)
while(p)
{ cout << p->d.a << " ";
p = p->prev;
}
}
Операция удаления узлов, как и операция вставки осуществляется с одного конца. Удаление происходит только с «хвоста» очереди. Чтобы удалить один узел очереди, можно вос- пользоваться функцией
Del_Queue(); для удаления всех элементов – обратиться к этой функции через цикл. Операцию подсчета количества N элементов очереди для цикла (если это не известно) можно организовать аналогично тому, как это сделано в функции для стека
Count_Stack() . Удаление узла очереди можно реализовать с помощью следующей функции.

int Del_Que(Node_Q **Begin, Node_Q **End)
{
Node_Q *t = *End;
cout<<" Извлекаем хвост "<d.a<
*End = t->next;
if (*End == NULL) // Удаляется единственный элемент очереди
*Begin = NULL;
delete t;
return 1;
}