Общие сведения о списках
Г л а в а 5
СПИСКИ
Список представляет собой последовательность элементов, каждый из которых имеет тип структуры, состоящей из двух частей: информационной и адресной. Например, простейший однонаправленный список целых чисел объявляется следующим образом. Как для структуры, сначала объявляем тип, например,
struct tsp
{ int num;
tsp * next;
};
Затем объявляем один или несколько указателей на структуру:
tsp *P, *Q, *T;
Как и для структур, допускается совместное объявление типа и указателя на структуру. Во всех приведенных далее алгоритмах P — это адрес начала списка, то есть адрес его первого, на рисунке (Рис.1) ”левого”, элемента. Переменную-указатель Q будем использовать в алгоритмах создания и обработки списка для организации цикла, с её помощью будем “перемещаться” по списку. Переменная T является дополнительной, и будет использоваться для вставки, удаления элементов и для некоторых других целей.
Пусть список создан. Алгоритм его создания будет рассмотрен во втором параграфе. Следуя большинству литературных источников, список будем обозначать для наглядности в виде следующей последовательности или цепочки (рис. 1):
|
Рис. 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) алгоритм вставки элемента в начало списка отличается от алгоритма его вставки в любое другое место списка. Благодаря наличию фиктивного элемента достаточно будет написать один алгоритм для вставки элемента в середину списка. Перед таким элементом никогда ничего вставлять не будем. Реальная вставка в начало списка благодаря наличию фиктивного элемента реально будет выглядеть как вставка в середину списка.
Из всего сказанного следует, что такой фиктивный элемент в списке не является обязательным. Вместо него мы можем просто предусматривать по два алгоритма для удаления и вставки. Читателю предлагается выбор: добавить вспомогательный элемент и ограничиться одним алгоритмом вставки или удаления или забыть о таком элементе и предусмотреть два разных алгоритма.
В связи с этим заметим, что подобных проблем с удалением последнего (“правого”) элемента и вставкой элемента в конец (то есть “справа”) не существует.
§2. Создание списка
Список можно создать двумя способами:
а) в прямом направлении “слева направо”, когда новый элемент добавляется в конец списка “справа”;
б) в обратном направлении, когда новый элемент вставляется слева, то есть в начало (вершину) списка. Так создаётся список, который называется стек.
2.1. Первый способ (+)
// Создаём фиктивный элемент (см. §1).
T=new tsp;
/* Зарезервировали память для фиктивного элемента списка и его адрес поместили в T */
T->num=0;
/* Определили его информационную часть.Это можно не делать, так как в просмотре этот элемент участвовать не будет. */
P=T;
/* В переменной P — адрес начала списка. При наличии фиктивного элемента его менять не будем, даже после вставки в начало списка, так как перед фиктивным элементом вставлять ничего никогда не будем. */
int n; cin>>n;
// n — количество реальных элементов списка без учёта фиктивного.
for (int i=1; i<=n;i++)
// Цикл для добавления n реальных элементов списка
{
/* Резервируем память для одного элемента списка и его адрес помещаем в Q */
Q=new tsp;
// Определяем информационную часть нового элемента .
cin>>Q->num;
/* “Cоединяем” его с предыдущим элементом. Другими словами, адрес нового подготовленного элемента, который находится в Q, помещаем в адресное поле структуры, адрес которой в T, то есть в T->next. */
T->next=Q;
/* Чтобы на следующем шаге это (T->next=Q;) можно было бы повторить, адрес только что созданного и присоединённого к списку элемента (Q) помещаем в T. */
T=Q;
/* Тогда после этого присваивания этот элемент Q, а точнее T, будет играть роль предшествующего, а новый элемент Q создадим. */
} // Конец цикла
/*Последний элемент должен содержать адрес NULL. Это означает, что после него в цепочке нет больше элементов списка. Элемент, в адресной части которого значение NULL, похож на “тупик”. */
Q->next=NULL;
Кроме ввода с экрана (cin>>Q->num;) при подготовке информационной части одного нового элемента списка возможны следующие варианты:
получение информационных полей с помощью датчика случайных чисел;
вычисление их или части полей по некоторому алгоритму, который реализуется, как правило, в функции. Вместо cin>>Q->num; тогда вызываем эту функцию;
все или некоторые информационные поля элемента списка можно прочитать из предварительно созданного файла (см. главу “Файлы”).
2.2. Второй способ (создание стека). (+)
Создание списка в обратном направлении рассмотрим на примере списка, в информационной части элемента которого не одно число, как в предыдущем примере, а одномерный статический массив фиксированной размерности m. Соответствующая структура для такого списка объявляется следующим образом:
const m=5;
struct tsp2 { float a[m]; tsp2 *next} *P2, *Q2, *T2;
Заметим, что при такой организации данных будет иметь место ещё один способ работы с “матрицей”. Информационная часть каждого элемента — это одна строка “матрицы”. При этом количество строк, то есть количество элементов списка, не обязательно фиксируется в виде константы. Его мы можем объявить как переменную и каким-нибудь способом определить, например, ввести, как это сделали в предыдуще примере. В предложенном ниже варианте количество элементов списка определяется в процессе создания списка
Вместо записанного в первом варианте цикла for, в котором используется заданное количество элементов списка, то есть количество одномерных массивов, можно использовать так называемый вечный цикл
while (1) { }
Выход из него выполним с помощью break, если введём, например, массив, в котором будет хотя бы одно число 1000 в любом месте. Для ввода и анализа массива составим логическую функцию, которая возвращает true или false в зависимости от того, есть ли это число 1000 в одномерном массиве:
bool fun1 (float *x, unsigned size)
{ for( int j=0; j<size; j++)
{ cin>>x[j];
if (x[j] ==1000) return true;
}
return false;
}
Фиктивный элемент в этом способе создавать не будем, хотя никто не мешает это сделать. Так как первым готовим последний “правый” элемент списка, то надо не забыть в него занести тупиковый адрес NULL. В отличие от рассмотренного выше варианта это надо сделать не после цикла (см. 2.1), а в начале алгоритма. Поэтому начинаем алгоритм так:
P2=NULL;
unsigned n=0; // Счётчик для количества элементов списка
while (1)
{ /* Резервируем память для одного элемента списка и его адрес помещаем в Q2 */
Q2=new tsp2;
/* Определяем информационную часть нового элемента, то есть один одномерный массив, и проверяем условие выхода из цикла с помощью функции fun1. Как и в первом варианте, кроме ввода с экрана, возможны другие способы определения массива (см. 2.1) */
if (fun1(Q2->a, m)) break;
n++;
/* Присоединяем этот подготовленный элемент “справа”, а не “слева”, как в первом варианте. В адресную часть этого нового только что созданного элемента списка помещаем адрес последнего присоединённого к этому моменту элемента. Для первого элемента списка в его адресную часть занесём NULL. */
Q2->next=P2;
/* Чтобы на следующем шаге иметь возможность в адресное поле нового элемента занести адрес последнего сформированного перед этим элемента, необходимо выполнить следующее присваивание: */
P2=Q2;
} // Конец цикла while
Этот способ используется для создания одного из видов списка, который называется стек .
§3. Просмотр и анализ списка