7.1. Несвязанные списки

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

Каждый список состоит в общем случае из множества более мелких  информационных структур, называемых записями. Записи, входящие в список, содержат «родственную» информацию. Примером списка является список, содержащий сведения о служащих организации. Одна запись такого списка содержит сведения об одном сотруднике организации.

В свою очередь, запись состоит из одного или нескольких полей (рис.16). Содержанием поля может быть, например, число или набор символов. Для приведенного выше примера поля записи могут содержать фамилию, имя, отчество, год рождения и так далее. Будем считать, что все записи, входящие в один и тот же список, имеют одинаковую (фиксированную) длину. Кроме того, будем считать для удобства, что все записи списка имеют одинаковую структуру, т.е. одинаковый состав и порядок полей.

Рис. 16. Cтруктура записи

В списке записи расположены, не как попало, а в определенном логическом порядке. В зависимости от этого порядка все списки делятся на линейные и нелинейные. Линейным списком называется список, логическое расположение записей в котором наглядно описывается прямой линией (рис.17). Пример списка, который не является линейным, приведен на рис.18.

Рис. 17. Линейный список

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

Рис. 18. Пример нелинейного списка

Логический и физический порядки размещения записей совпадают для линейных списков, называемых несвязанными. Для несвязанного списка характерно то, что, зная адрес памяти, которую занимает данная запись, мы без труда можем найти в памяти логически соседние к ней записи. Допустим пока, что мы  имеем дело с несвязанными линейными списками. В зависимости от состава допустимых операций над списком будем различать следующие типы линейных списков: 1) линейный список общего вида; 2) стек; 3) очередь.

Линейный список общего вида допускает наибольшее число операций:

1) получение доступа к k-й записи списка, чтобы проанализировать или изменить содержимое ее полей;

2) включение новой записи непосредственно перед записью k;

3) исключение записи k из списка;

4) объединение двух или более линейных списков в один;

5) определение числа записей в списке;

6) поиск записи в списке с заданным значением некоторого поля записи;

7) сортировка записей списка в порядке возрастания или убывания значения некоторого поля записи.

Для удобства выполнения перечисленных операций над линейным списком общего вида вводятся две вспомогательные переменные (переменная – небольшая область в ОП или в ВП, или это – регистр):

S – содержит адрес в памяти, где расположена первая запись списка;

F – содержит адрес в памяти последней записи списка.

Переменные S и F часто называют указателями, соответственно, на начало и конец списка. Пользуясь этими переменными, нетрудно входить в список, как с начала, так и с конца (рис.19).

Рис. 19.  S  и F – указатели на начало и конец линейного списка

Стек – линейный список, над которым допустимы только две операции:

1) включение новой записи в начало списка;

2) исключение записи, стоящей первой от начала списка.

При работе со стеком выполняется правило “последним пришел, первым ушел". Это аналогично стопке подносов в столовой: поднос, который был положен на стопку последним, первым будет с нее снят. Т.к. включения и исключения из стека производятся только в его начале, то нужна  только одна переменная S. На рис. 20 и 21 приведены примеры включения и исключения записи.

Рис. 20. Включение записи  k  в стек

Рис. 21. Исключение записи из стека

   Очередь – линейный список, над которым допустимы только две операции:

1) включение новой записи в конец очереди;

исключение записи, стоящей в начале очереди.

На рис. 22 и 23 приведены примеры включения и исключения записи.

Рис. 22. Включение записи  k  в несвязанную очередь

Рис. 23. Исключение записи из несвязанной очереди