Включение элемента в голову списка

Алгоритм включения элемен­та X в начало списка может быть следующим.

Процедура Включить_В_Начало (X)

1. ВП(Work).

2. Work–>Data = X (сформировать поле информации).

3. Work–>Next = Start (сформировать поле указателя).

4. Start = Work.

Легко убедиться в том, что алгоритм работает правильно даже в том случае, если список изначально пуст, т.е. Start = 0.

Формирование списка путем добавления нового элемента в начало

Операция включения элемента в голову списка является основой для алгоритма формирования списка. Форми­руется пустой список, и последовательно добавляются элементы в его начало.

Запишем алгоритм формирования списка из n элементов путем до­бавления элементов в его начало.

Процедура Создание_Списка

1. Start = 0 (сформировать пустой список)

2. ВП(Work).

3. Work–>Data = n (сформировать поле информации).

4. Work–>Next = Start (сформировать поле указателя).

5. Start = Work.

6. n = n – 1.

7. Если n = 0, закончить. Иначе на шаг 2.

(Работу алгоритма показать на примере при n=5).

Это самый простой алгоритм формирования списка, однако порядок элементов в этом случае обратен порядку их включения, что не всегда желательно.

Включение элемента в список после заданного

Необходимо включить элемент, заданный ссылкой Work1, после элемента списка, за­данного ссылкой Work2.

Алгоритм состоит из следующих шагов.

Процедура Включить_В_Список (X, Work2)

1. ВП(Work1).

2. Work1–>Data = X.

3. Work1–>Next = Work2–>Next.

4. Work2–>Next = Work1.

Включение элемента в конец списка

Зная алгоритм включения элемента после заданного, поставленную задачу можно решить следу­ющим образом. Просмотрев весь список найти последний его элемент и вставить новый элемент за последним.

Однако такой метод допустим только для списков с небольшим ко­личеством элементов. Если же количество элементов в списке вели­ко, то такой алгоритм по очевидным причинам неэффективен. Лучшее решение – ввод второй ссылки, указывающей на последний элемент списка.

Недостаток этого метода создания списка в том, что первый из включаемых эле­ментов нужно обрабатывать иначе, чем остальные.

Включение элемента в список перед заданным элементом

Пусть требуется включить элемент X, заданный ссылкой Work1, перед эле­ментом списка, заданным ссылкой Work2. Алгоритм решения этой за­дачи не очевиден, хотя и прост.

Трудность заключается в том, что в односвязном списке нет воз­можности вернуться к элементу, предшествующему данному. Однако, как вы увидите из алгоритма, это и не требуется. Достаточно вклю­чить новый элемент после текущего, а потом поменять местами зна­чения информационных полей.

1. Work1–>Data = Work2–>Data.

2. Work1–>Next = Work2–>Next.

3. Work2–>Next = Work1.

4. Work2–>Data = X.

Удаление элемента из списка

Удаление элемента, следующего за заданным

Сначала рассмотрим алгоритм исключения элемента, следующего за элементом, на который указывает Work1.

Процедура Исключить (Work1)

1. Work2 = Work1–>Next (получить адрес исключаемого элемента).

2. Work1–>Next = Work2–>Next.

3. ОП(Work2).

Удаление текущего элемента

Труднее исключить элемент, на который указывает указатель. Та же проблема, что и при включении. Однако и решение этой проблемы аналогично. Исключается следующий элемент, но перед этим значение его информационного поля передвигается вперед.

1. Work2 = Work1–>Next.

2. Work1–>Data = Work2–>Data.

3. Work1–>Next = Work2–>Next.

4. ОП(Work2).

Следует иметь в виду, что рассмотренные выше алгоритмы можно применять только в случае, если за удаляемым элементом есть последующий элемент, т.е. он не является последним в списке.

 

Просмотр списка

Просмотр списка выполняется с целью обработки его элементов. При последовательном просмотре списка обработка может состоять в:

- печати содержимого информационной части или отдельных ее полей;

- модификации полей информационной части;

- сравнении полей информационной части с образцом при поиске по ключу;

- подсчете количества элементов в списке;

- очистке списка и т.п.

 

Рассмотрим операцию печати элементов списка.

Процедура Печать_Списка (Start)

1. Work1 = Start.

2. Пока Work1 <> 0

3. Печать Work1–>Data.

4. Work1 = Work1–>Next.

5. Конец Пока.

В алгоритме поиска некоторого значения в списке на втором шаге добавляется еще одна проверка информационного поля на равенство искомому значению.