- •Вопрос 1) Основные структуры данных.
- •Вопрос 2) Массивы и их свойства.
- •Вопрос 3) Записи
- •Вопрос 4) Множества
- •Операции над множествами
- •Операции отношения.
- •Вопрос 5) Динамические структуры данных;
- •Вопрос 6) Линейные списки.
- •Вопрос 7) Циклические списки
- •Вопрос 8) Стек и его организация
- •Вопрос 9) Очереди и их организация
- •Вопрос 10) Задачи поиска в структурах данных.
- •Вопрос 11) Алгоритм линейного поиска.
- •Вопрос 12) Алгоритм бинарного поиска.
- •Вопрос 13) Алгоритм Кнута, Мориса- Пратта
- •Вопрос 14) Хэширование данных
- •Вопрос 15) сортировка данных
- •15. Сортировка данных
- •1) Сортировка включением
- •2) Сортировка Шелла
- •3) Обменная сортировка
- •4) Сортировка перемешиванием (Шейкерная сортировка)
- •5) Сортировка со слиянием
- •1) Прямое слияние
- •2) Естественное слияние
- •Вопрос 16) Пузырьковая сортировка.
- •17 Вопрос
- •Вопрос 18) Представление графов и деревьев
- •Вопрос 19) Представление бинарных деревьев.
- •Вопрос 20) Представление графов Способы представления графа в информатике Матрица смежности
- •Матрица инцидентности
- •Список рёбер
- •Вопрос 21) Алгоритмы на графах
- •Алгоритм Дейкстры нахождения кратчайшего пути
Вопрос 7) Циклические списки
Один из недостатков линейных списков заключается в том, что если какой-либо элемент списка уже пройден, то он становится недоступным. В результате мы не имеем доступа к элементам, предшествующим заданному. Для повторного обращения к пройденному элементу списка необходимо снова начать поиск с его головы.
Сделаем в структуре линейного списка некоторые изменения. Пусть последний элемент списка содержит не пустой указатель, а указатель на первый его элемент. Такой список называется циклическим или кольцевым.
Циклические списки можно использовать не только для представления структур, которым свойственна цикличность, но также для представления линейных структур; циклический список с одним указателем на голову списка, по существу, эквивалентен простому линейному списку с двумя указателями на начало и конец.
Циклический список отличается тем, что из любого его элемента можно достичь любой другой его элемент.
Однако у циклического списка имеется и недостаток. Если при использовании таких списков не применять соответствующих мер предосторожности, то можно попасть в бесконечный цикл. Поэтому при работе с циклическими списками важно уметь обнаруживать конец списка.
Один из вариантов решения этой задачи – поместить в список специальный узел, который легко может быть распознан. Такой узел может содержать, например, пустое поле данных.
Другой вариант – сравнение адреса очередного узла с адресом головного элемента списка.
Третий способ – запомнить адрес элемента, с которого начинаем поиск. Проблема решается так: если мы выполняем некоторые операции, двигаясь по списку от одного узла к следующему, то мы должны остановиться, когда мы вернулись к исходному месту. При этом предполагается, что исходное место все еще присутствует в списке.
Циклический список позволяет программе снова и снова просматривать список по кругу до тех пор, пока в этом есть необходимость.
В качестве примера использования циклического списка рассмотрим задачу выбора из N претендентов на приз одного. Для решения этой задачи выстраиваем всех претендентов в круг и убираем каждого М-го человека, постепенно сужая круг. Надо найти человека, который останется последним (и получит приз, если организаторы к тому времени не передумают), или, по-другому, найти порядок отсеивания претендентов. На основе циклического списка нетрудно составить программу, которая читает значения N и M, и затем распечатывает порядок отсеивания.
Сначала создается список с ключами от 1 до N. Затем программа проходит по этому циклическому списку, пропуская M–1 элементом и уничтожая следующий после них узел до тех пор, пока в списке не останется один единственный элемент.
В delphi будет выгледеть примерно так:
Record = link
Inf:integer;
Next:^link;
End;
В программе
Var
Beg,elem link;
I:integer;
Begin
New(beg); // создание списка из 10 элементов
Beg^.next:=nil;
Beg^.inf:=1;
Elem:=beg;
For i:=2 to 10 do
Begin
New(elem^.next);
Elem:=elem^.next;
Elem^.next:=beg;
Elem^.inf:=I;
End;
Elem:=beg; // вывод списка
Writeln(elem^.inf);
Elem:=elem^.next;
While(elem <> beg) do
Begin
Writeln(elem^.inf);
Elem:=elem^.next;
End;
End;
В СИ ++
Struct list{
Int inf;
Struct List *next;
};
void main()
{
List *beg,*elem;
Beg=NULL;
Elem=NULL;
Beg = new list; // создание списка из 10 элементов
Beg->inf=1;
Beg->next=NULL;
Elem=beg;
Fore(int i=2;i<=10;i++)
{
Elem->next = new list;
Elem=elem->next;
Elem->next=beg;
Elem->inf=I;
}
Elem=beg;
Cout<<elem->inf<<endl;
Elem=elem->next;
While(elem != beg)
{
Cout<<elem->inf<<endl;
Elem=elem->next;
}
}