Рассмотрим, как реализуются возможные с односвязными списками операции на языке программирования С++ с помощью функций.
Элемент списка можно определить как структуру, внутри которой содержится указатель на следующий элемент такой же структуры. В простейшем случае, если информационным полем элемента односвязного списка являются целые числа, элемент списка можно описать так:
struct TNode;
typedef TNode* PNode;
struct TNode
{
int Data;
PNode Next;
};
Здесь с помощью typedef мы определяем PNode как указатель на элемент данной структуры.
Функцию вставки элемента в начало односвязного списка можно описать следующим образом:
void InsertFirst(PNode& First, int Data)
{
PNode p = new TNode;
p->Data=Data;
p->Next=First;
First=p;
}
Происходит генерация динамического элемента структуры с рабочим указателем p, после чего указателю на следующий элемент списка присваивается значение First (p->Next=First; First уже не указывает на начало списка), затем указателю начала списка присваивается значение рабочего указателя p (First=p).
Функцию удаления элемента из начала односвязного списка опишем следующим образом:
void DeleteFirst(PNode& First)
{
PNode p=First;
if(p==0) cout<<" Ошибка: В списке нет элементов"<<endl;
else
{First=First->Next;
Delete p;}
}
В случае, когда вставка всегда осуществляется в начало односвязного списка, с его помощью реализуется чисто динамический стек, причем функция AddFirst(PNode& First, int Data) реализует операцию занесения в стек нового элемента, а функция DelFirst(PNode& First) – считывания элемента из стека. Проверка на пустоту осуществляется по значению рабочего указателя p (if(p==0) “Список пуст и стек соответственно тоже”). Переполнение стека может возникнуть в данном случае только в случае реального переполнения оперативной памяти машины, поэтому при такой реализации стека нет необходимости вводить в функцию занесения нового элемента условие проверки на переполнение.
Для удаления элемента из начала односвязного списка и из стека, реализованного на односвязном списке, можно использовать следующую функцию.
void DeleteFirst(PNode& First)
{
PNode p=First;
if (p==NULL)
{
cout<<"Ошибка! В списке нет элементов!"<<endl;
cout<<"Нажмите любую клавишу для продолжения"<<endl;
getch();
}
else
{
First=First->Next;
delete p;
cout<<"Первый элемент списка удален"<<endl;
cout<<"Нажмите любую клавишу для продолжения"<<endl;
getch();
}
}
В данной функции предусмотрена проверка списка (стека) на пустоту.
Структура данных типа односвязный список, помимо указателя начала списка, предусматривает наличие нескольких рабочих указателей, что значительно расширяет ее практическое применение. В частности, можно реализовать функции его последовательного просмотра, вставки элемента в любое место списка, перестановки элементов путем несложных манипуляций с указателями. Если вставку осуществлять не в начало, а в конец списка, то с помощью односвязного списка реализуется очередь. Функция вставки элемента в очередь в этом случае будет выглядеть следующим образом:
void InsertLast(PNode& First, int Data)
{
PNode p1, p2=First;
if (First==0)
{PNode p1=new TNode;
p1->Data=Data;
p1->Next=First;
First=p1;
cout<<"Список был пустым"<<endl;
cout<<"Последний элемент списка добавлен и является одновременно первым"<<endl;
cout<<"Нажмите любую клавишу для продолжения"<<endl;
getch();
}
else
{
while (p2->Next!=NULL)
p2=p2->Next;
p1=new TNode;
p1->Data=Data;
p2->Next=p1;
p1->Next=NULL;
cout<<"Последний элемент списка добавлен"<<endl;
cout<<"Нажмите любую клавишу для продолжения"<<endl;
getch();
}
}
Здесь также предусмотрена проверка на пустоту, а также корректное занесение самого первого элемента.
Для удаления элемента из очереди можно использовать ту же функцию, что и для стека.