Алгоритм - непрерывные и связанные списки

Зачем нужны списки?

В повседневной жизни часто встречаются такие списки, как:

Люди в зале ожидания.
Студенты, обучающиеся по специальности.
Машины ждут красного света.
и т.д.

Цель состоит в том, чтобы представить эти примеры из реальной жизни и обработать их в информатике.

Каковы характеристики списка?

Они обрабатываются последовательно.
Разграничен с обоих концов < голова> и < очередь>.
Есть возможность добавлять или удалять элементы.
Динамическая структура (размер варьируется).

Representation

1 - Непрерывное представление

Мы видели, что мы можем представить список с массивом T[1..max], но его структура статична (его размер фиксирован в то время, когда мы определяем его в объявлении).

тип списка: Article
{
T: array[1..lmax] элемента
length: 0..lmax
}

Наиболее важные операции

Le parcours

Путь к процедуре(L:list)
Start
для i от 1 до L.length
faire
process(L.T[i])
finfaire
Конец

Удаление ( см.: s удаление элемента из непрерывного списка).

Вставка (см.: Вставка элемента в список contiguous).

Преимущества

Прямой доступ.
Удаление и вставка в конец списка.
Простая реализация.

Cons

Вы должны знать, как изменить длину.
Удаления и вставки включают смещения.

2- Представительство В цепочке

Он состоит из последовательности ссылок (блоков) и каждая ссылка состоит из двух полей:

Элемент field.
Адресное поле, указывающее на следующее.

L: указатель на первую ссылку.

Пустой связанный список представлен L=null.

ptr type: link pointer

тип ссылки: article

{

долина; element

link: ptr

}

chainlisted< type: link/span>

var L: chainlisted

<>Наиболее важные операции

Course.

Путь к процедуре(L:list)
Наверх
pp := L.link // Глава de L
до тех пор, пока pp != null
faire
treat(L.T[i])
pp := *pp.link
finfaire
Fin

Подавление(см: Вставка и удаление элемента в связанном списке.).

Insertion(см.: Вставка и удаление элемента в связанном списке.).

Преимущества

Последовательный путь.
Удалена ссылка.
Вставка link.

Cons

Косвенный доступ к элементу, вы должны пройти через ссылки i-1, чтобы добраться до него i^-й maillon.
Потеря места в памяти для links.