Г л а в а 4

Списки §1. Общие сведения о списках

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

struct tsp

{ int num;

tsp * next;

};

Затем объявляем один или несколько указателей на структуру:

tsp *P, *Q, *T;

Как и для структур, допускается совместное объявление типа и указателя на структуру. Во всех приведенных далее алгоритмах P — это адрес начала списка, то есть адрес его первого, на рисунке (Рис.1) ”левого”, элемента. Переменную-указатель Q будем использовать в алгоритмах создания и обработки списка для организации цикла, с её помощью будем “перемещаться” по списку. Переменная T является дополнительной, и будет использоваться для вставки, удаления элементов и для некоторых других целей.

Пусть список создан. Алгоритм его создания будет рассмотрен во втором параграфе. Следуя большинству литературных источников, список будем обозначать для наглядности в виде следующей последовательности или цепочки (рис. 1):

NULLLLL

Рис. 1.

Здесь каждый элемент содержит две “клеточки”. В первой из них, “левой”, находится целое число, то есть информационная часть, а в правой — адрес следующего элемента, на что указывает нарисованная “стрелка”. Из последнего “правого” элемента стрелка не проведена. Это означает, что в его адресной части находится пустой адрес, который в программе обозначается как NULL, то есть это “тупик”, означающий, что список закончился. Пусть адрес “левого” элемента находится в переменной P. Тогда, как и по общим правилам использования структур, с помощью P->num осуществляется доступ к информационному полю элемента списка, а P ->next идентифицирует его адресное поле.

В информационной части структуры, то есть элемента списка содержатся подлежащие обработке данные. В нашей структуре это одно целое число num, и тогда получается числовой список. Если полем является одномерный статический массив, то имеет место список массивов, то есть мы имеем возможность работать не с одним, а с несколькими одномерными массивами (см. 2.2). Это ещё один способ представления “матрицы” и работы с ней. Если в информационной части элемента находится строка, то получается список строк. Как и в любой структуре, в информационной части может быть несколько полей разных типов, например, фамилия студента, массив из 5 оценок и размер стипендии. Эти данные могут размещаться напрямую в структуре или с помощью вложенных структур.

В адресной части каждого элемента списка может содержаться один или несколько адресов, то есть одно или несколько полей типа указатель на такую же структуру. В нашем примере это переменная-указатель next, в которой будет находиться адрес следующего элемента списка. При такой структуре данных рядом с информационными полями (в нашем примере рядом с каждым числом) будет находиться один адрес, и тогда такой список называют однонаправленным. Таких адресных полей может быть два. Например, можно хранить адрес следующего и адрес предыдущего элементов списка. В таком случае говорят о двунаправленном списке. Деревья, как разновидность списков, также организованы с помощью двух адресных полей в каждом элементе.

Для того, чтобы быстрее понять идеи и правила работы со списками, чтобы не усложнять алгоритмы деталями, не относящимися к новой для нас структуре данных, будем работать с объявленным выше списом, в информационной части элемента которого находится только одно число. Забегая вперёд (см. §6), отметим, что такой список с точки зрения памяти малоэффективен. Дело в том, что по сравнению с обычным одномерным массивом требуется в два раза больше памяти, так как рядом с каждым числом находится адрес следующего элемента.

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

Первая особенность связана с несколько непривычным, не традиционным объявлением структуры. По общим правилам сначала надо объявить какой-нибудь нестандартный не встроенный тип, а затем его можно использовать. Например, при рассмотрении вложенных структур мы сначала объявляли одну из них, а затем использовали её при объявлении другой структуры или указателя на неё. Что мы видим в случае со списком? В этом правиле здесь сделано исключение. Не закончив объявление структуры tsp, мы в ней же, в этой же структуре используем указатель на ещё не объявленную структуру.

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

(P->next, Q->next, Q->next->next, T->next),

так и просто в переменной-указателе (P, Q, T). Поэтому допустимы, например, следующие присваивания:

T=Q; T->next=Q; Q=T->next; Q= Q ->next->next;

Доступ к информационному полю можно выполнить как с помощью, например, Q ->inf, так и с помощью Q ->next-> inf.

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

Зачем такой фиктивный элемент? Как увидим в дальнейшем (§3), удаление самого первого элемента списка выполняется не так, как удаление любого элемента с его середины. Поэтому фиктивный элемент используется, чтобы для удаления элементов не предусматривать два разных алгоритма. Из списка он никогда не удаляется. Аналогично (§4) алгоритм вставки элемента в начало списка отличается от алгоритма его вставки в любое другое место списка. Благодаря наличию фиктивного элемента достаточно будет написать один алгоритм для вставки элемента в середину списка. Перед таким элементом никогда ничего вставлять не будем. Реальная вставка в начало списка благодаря наличию фиктивного элемента реально будет выглядеть как вставка в середину списка.

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

В связи с этим заметим, что подобных проблем с удалением последнего (“правого”) элемента и вставкой элемента в конец (то есть “справа”) не существует.