Основные определения. Список – это совокупность объектов или элементов, в котором каждый объект содержит информацию о местоположении связанного с ним другого объектаСписок – это совокупность объектов или элементов, в котором каждый объект содержит информацию о местоположении связанного с ним другого объекта. Если список располагается в оперативной памяти, то, как правило, информация для поиска следующего объекта – это указатель, адрес памяти. Если связный список хранится на диске в файле, то информация о следующем элементе может включать смещение элемента от начала файла к положению указателя записи или считывания файла, ключ записи и любую другую информацию, позволяющую однозначно отыскать следующий элемент списка. В списке элементы связаны друг с другом логически. Логический порядок следования элементов списка определяется с помощью указателей. Подчеркнем, что логический порядок следования элементов списка может не совпадать с физическим порядком их расположения в памяти ПЭВМ. Списки бывают линейными и кольцевыми, односвязными и двусвязными. Как правило, элемент списка представляет собой структурную переменную, содержащую указатель или указатели на следующий элемент и любое число других полей, называемых информационными. Если движение от элемента к элементу списка возможно только в одном направлении и список имеет начальную точку такого движения, говорят об односвязном списке. Элемент односвязного списка включает только указатель на следующий элемент. Сам список характеризуется указателем на начало списка (рис. 12.1). Двусвязный список позволяет выполнять «движение» от элемента к элементу в обоих направлениях. В этом случае элемент включает два указателя: на предыдущий и последующий элементы списка. А так как список имеет и начало, и конец, описываются еще два указателя – начала и конца списка (рис. 12.2).
Рис. 12.1. Модель односвязного линейного списка
Список, в котором последний элемент не связан с первым, называется линейным. Соответственно кольцевым называется список, у которого последний элемент указывает на первый. В последнем элементе односвязного и двусвязного линейного списка указатель на следующий элемент и в первом элементе двусвязного списка указатель на предыдущий элемент равны нулю.
Рис. 12.2. Модель двусвязного линейного списка
|
