Теоретические сведения

Лабораторная работа №1

Структура данных «список».

Теоретические сведения.

1. Основные определения.

Список – это совокупность объектов или элементов, в котором каждый объект содержит информацию о местоположении связанного с ним объекта.

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

В списке элементы связаны друг с другом логически. Логический порядок следования элементов списка опре­деляется с помощью указателей. Подчеркнем, что логи­ческий порядок следования элементов списка может не совпадать с физическим порядком их расположения в памяти ЭВМ.

Списки бывают линейными и кольцевыми, односвязными и двусвязными.

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

Если движение от элемента к элементу списка возможно только в одном направлении и список имеет начальную точку такого движения, говорят об односвязном списке. Элемент односвязного списка включает только указатель на следующий элемент. Сам список характеризуется указателем на начало списка (см. рис.12.1).

Двусвязный список позволяет выполнять «движение» от элемента к элементу в обоих направлениях. В этом случае элемент включает два указателя: на предыдущий и последующий элементы списка. А так как список имеет и начало, и конец, описываются еще два указателя – начала и конца списка (см. рис. 12.2).

	Указатель на начало списка
	Указатель на второй элемент _____________ данные				NULL _____________ данные

Рис. 12.1 Модель односвязного линейного списка

Рис. 12.2 Модель двусвязного линейного списка

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

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