Линейный список –совокупность однотипных элементов, расположенных последовательно друг за другом, количество элементов в списке не фиксируется
Лекция 6.
4. Линейный список –совокупность однотипных элементов, расположенных последовательно друг за другом, количество элементов в списке не фиксируется.
В списке присутствует указатель, он может перемещаться по списку, отмечает текущий элемент при просмотре списка.
в начале текущий в конце
списка элемент списка
Указатель может перемещаться по списку от начала к концу, в этом случае список называется однонаправленный.Еслиуказателю разрешено перемещаться от начала к концу и от конца к началу списка, список называется двунаправленный.
Операции для однонаправленного списка:
1. Сделать список пустым.
2. Установить указатель в начало списка.
3. Передвинуть указатель на одну позицию к концу.
4. Добавить элемент за указателем.
5. Удалить элемент за указателем, если такой есть.
6. Проверить, стоит ли указатель в конце списка.
7. Проверить список на пустоту.
8. Выбрать элемент за указателем без удаления.
Список можно реализовать также на основе массива, но в этой реализации такие операции, как добавление и удаление элементов, будут требовать много времени, т.к. придется сдвигать часть массива.
Самим придумать операции для двунаправленного списка.
Связанный список.
Можно описать массив указателей и для каждого создать динамическую переменную: . . . . . . … Xn-1 X2 X1 …Организация связанного списка.
Определить тип элемента связанного списка.
Обозначим tip – тип информационной части элемента списка. Например,
typedef int tip;
Структура элемента связанного списка:
Struct tel
tel *next; //указатель на следующий элемент }; 2. Описать указатель на связанный список (иногда удобно описать два указателя: на начало и на конец), рабочие…Поиск места вставки x
t = beg; p = NULL;
bool b = true;
while (t && b)
if (t -> inf < x) {p=t; t = t->next;}
Else b=false; // найдено место вставки
Создание нового элемента
q= new tel; q->inf = x;
If (p == NULL) // вставка в начало или в пустой список
{q ->next = beg; beg = q;}
Else //вставка после элемента, на который указывает p
{q-> next = p->next;
P-> next =q; } //это может быть вставка в конец,если
P->next=0), либо в середину
Динамические структуры можно создавать на основе связанного списка. В этом случае элементы динамической структуры составляют информационные части… Рассмотрим реализацию стека на основе связанного списка (в виде 3-х файлов). … // stack3f.hШаблон связанного списка
· чтобы объявление операций и реализация этих операций находились в одном файле (3-х файловая программа не работает). · template <class tip> помешают перед каждой функцией и структурой tel… //shablon.hRez.txt
33 9 7 5 32 6 8 21 65
6 4
4 2
2 3
1 2.5
3 1
5 9
7 5