Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
1. Как освободить память от удаленного из списка элемента?
- p=getnode;
- ptr(p)=nil;
- freenode(p);
- p=lst.
2. Как создать новый элемент списка с информационным полем D?
- p=getnode;
- p=getnode; info(p)=D;
- p=getnode; ptr(D)=lst.
3. Как создать пустой элемент с указателем p?
- p=getnode;
- info(p);
- freenode(p);
- ptr(p)=lst.
4. Сколько указателей используется в односвязных списках?
- 1;
- 2;
- сколько угодно.
5. В чём отличительная особенность динамических объектов?
- порождаются непосредственно перед выполнением программы;
- возникают уже в процессе выполнения программы;
- задаются в процессе выполнения программы.
Кольцевые структуры данных.
6. При удалении элемента из кольцевого списка
- список разрывается;
- в списке образуется дыра;
- список становится короче на один элемент.
7. Для чего используется указатель в кольцевых списках?
- для ссылки на следующий элемент;
- для запоминания номера сегмента расположения элемента;
- для ссылки на предыдущий элемент;
- для расположения элемента в списке памяти.
8. Чем отличается кольцевой список от линейного списка?
- в кольцевом списке последний элемент является одновременно и первым;
- в кольцевом списке указатель последнего элемента пустой;
- в кольцевых списках последнего элемента нет;
- в кольцевом списке указатель последнего элемента не пустой.
9. Сколько указателей используется в односвязном кольцевом списке?
- 1;
- 2;
- сколько угодно.
10. В каких направлениях можно перемещаться в кольцевом двунаправленном списке?
- в обоих;
- влево;
- вправо.
Примеры алгоритмов конкретных задач
Рассмотрим, как реализуются возможные с односвязными списками операции на языке программирования С++ с помощью функций.
Элемент списка можно определить как структуру, внутри которой содержится указатель на следующий элемент такой же структуры. В простейшем случае, если информационным полем элемента односвязного списка являются целые числа, элемент списка можно описать так:
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;
p 1-> Next = NULL ;
cout<<"Последний элемент списка добавлен"<<endl;
cout<<"Нажмите любую клавишу для продолжения"<<endl;
getch();
}
}
Здесь также предусмотрена проверка на пустоту, а также корректное занесение самого первого элемента.
Для удаления элемента из очереди можно использовать ту же функцию, что и для стека.
Задания
Дата: 2019-12-10, просмотров: 583.