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

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

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

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

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

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

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

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).

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

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