Алгоритмы и структуры данных

1.2.7. Циклические списки

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

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными.

1.2.7.1. Циклический однонаправленный список

Циклический однонаправленный список похож на линейный однонаправленный список, но его последний элемент содержит указатель, связывающий его с первым элементом (рис. 4).

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие «первого» элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как «первый» путем установки на него специального указателя. Это требуется, например, для предотвращения «зацикливания» при просмотре списка.

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

• вставка элемента;
• просмотр
• поиск;
• удаление элемента.

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

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

procedure Ins CicleSingleList(DataElem: TypeData;

var ptrHead, ptrCurrent: PElement); {Вставка элемента в циклический однонаправленный список} {справа от элемента, на который указывает ptrCurrent}

var

ptrAddition: PElement;      {вспомогательный указатель} begin

New(ptrAddition);

ptrAdditionA.Data := DataElem; if ptrHead = nil then begin      {список пуст} {создаем первый элемент списка}

ptrAdditionA.Next := ptrAddition;    {цикл из 1 элемента}

ptrHead := ptrAddition; end else begin      {список не пуст}

{вставляем элемент списка справа от элемента,}

{на который указывает ptrCurrent}

ptrAdditionA.Next := ptrCurrentA.Next;

ptrCurrentA.Next := ptrAddition; end;

ptrCurrent := ptrAddition; end;

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

Операция просмотра списка заключается в последовательном просмотре всех элементов списка. В отличие от линейного однонаправленного списка здесь признаком окончания просмотра списка будет возврат к элементу, выделенным как «первый»:

procedure Scan CicleSingleList(ptrHead:  PElement);

{Просмотр циклического однонаправленного списка} var

ptrAddition:  PElement;      {вспомогательный указатель} begin

if ptrHead <> nil do begin      {список не пуст} ptrAddition := ptrHead; repeat

writeln(ptrAdditionA.Data);    {Вывод значения элемента} ptrAddition := ptrAdditionA.Next; until ptrAddition = ptrHead; end; end;

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

function Find CicleSingleList(DataElem: TypeData;

var ptrHead,

ptrCurrent: PElement): boolean; {Поиск в циклическом однонаправленном списке} var

ptrAddition: PElement;      {вспомогательный указатель} begin

if ptrHead <> nil do begin     {список не пуст} ptrAddition := ptrHead; repeat

ptrAddition := ptrAdditionA.Next; 
until  (ptrAddition = ptrHead) or {прошли весь список}

(ptrAdditionA.Data = DataElem)       {элемент найден} if ptrAdditionA.Data = DataElem then begin Find CicleSingleList := true; ptrCurrent := ptrAddition; end else begin

Find CicleSingleList := false; end; end else begin

Find CicleSingleList := false; end; end;

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

procedure Del CicleSingleList(var ptrHead, ptrCurrent: PElement);

{Удаление элемента из циклического однонаправленного списка}

var

ptrAddition: PElement;    {дополнительный указатель} begin

if ptrCurrent <> nil then begin     {входной параметр корректен} if ptrHeadA.Next <> ptrHead then begin {Если удаляемый элемент не единственный в списке} {устанавливаем вспомогательный указатель на элемент, предшествующий удаляемому} ptrAddition := ptrHead;

while ptrAdditionA.Next <> ptrCurrent do

ptrAddition := ptrAdditionA.Next; {непосредственное удаление элемента} ptrAdditionA.Next := ptrCurrentA.Next; if ptrHead = ptrCurrent then        {удаляем первый}

ptrHead := ptrCurrentA.Next; dispose(ptrCurrent); ptrCurrent := ptrAdditionA.Next; end else begin ptrHead:=nil; dispose(ptrCurrent); ptrCurrent:=nil; end; end; end;

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

Для ускорения доступа к элементам списка путем применения переходов между элементами в обоих направлениях в циклических списках применяют тот же подход, что и в линейных списках: циклический двунаправленный список.

1.2.7.2. Циклический двунаправленный список

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

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

• вставка элемента;
• просмотр;
• поиск;
• удаление элемента.

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

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

procedure Ins CicleDubleList(DataElem: TypeData;

var ptrHead, ptrCurrent: PElement); {Вставка элемента в циклический двунаправленный список справа от элемента, на который указывает ptrCurrent}

var

ptrAddition: PElement;      {вспомогательный указатель} begin

New(ptrAddition); ptrAdditionA.Data := DataElem; if ptrHead = nil then begin      {список пуст} {создаем первый элемент списка}

ptrAdditionA.Next := ptrAddition;    {петля из 1 элемента} ptrAdditionA.Last := ptrAddition;

ptrHead := ptrAddition; end else begin      {список не пуст}

{вставляем элемент списка справа от элемента,}

{на который указывает ptrCurrent}

ptrAdditionA.Next := ptrCurrentA.Next;

ptrCurrentA.Next := ptrAddition;

ptrAdditionA.Last := ptrCurrent;

ptrAdditionA.NextA.Last := ptrAddition; end;

ptrCurrent := ptrAddition; end;

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

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

Операция удаления элемента также осуществляется во многом аналогично удалению из циклического однонаправленного списка:

procedure Del CicleDubleList(var ptrHead, ptrCurrent: PElement);

{Удаление элемента из циклического двунаправленного списка} var

ptrAddition: PElement;    {дополнительный указатель} begin

if ptrCurrent <> nil then begin     {входной параметр корректен} if ptrHeadA.Next <> ptrHead then begin {Если удаляемый элемент, не единственный в списке}

ptrAddition := ptrCurrentA.Next;

ptrCurrentA.LastA.Next := ptrCurrentA.Next;

ptrCurrentA.NextA.Last := ptrCurrentA.Last;

if ptrHead = ptrCurrent then {удаляем первый}

ptrHead := ptrCurrentA.Next;

dispose(ptrCurrent);

ptrCurrent := ptrAddition; end else begin

ptrHead:=nil;

dispose(ptrCurrent); ptrCurrent:=nil; end; end; end;

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

1.2.8. Разреженные матрицы

Разреженная матрица - двухмерный массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений, отличных от основного (фонового) значения остальных элементов.

Различают два типа разреженных матриц:

1) матрицы, в которых местоположения элементов со значениями, 
отличными от фонового, могут быть математически описаны;

2) матрицы со случайным расположением элементов.

В случае работы с разреженными матрицами вопросы размещения их в памяти реализуются с учетом их типа.

1.2.8.1. Матрицы с математическим описанием местоположения элементов

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

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

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

На практике для работы с разреженной матрицей разрабатываются функции:

1) для преобразования индексов матрицы в индекс вектора;

2. для получения значения элемента матрицы из ее упакованного представления по двум индексам (строка, столбец);
3. для записи значения элемента матрицы в ее упакованное представление по двум индексам.

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

¹ = ((y - I)-X_n + x)/2,

где 1 - индекс в линейном представлении; x, y - индексы соответственно строки и столбца в двумерном представлении; X_m - количество элементов в строке исходной матрицы.

1.2.8.2. Матрицы со случайным расположением элементов

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

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

Пусть есть матрица A размерности 5x7, в которой из 35 элементов только 10 отличны от нуля:

дексами строки и столбца матрицы (рис. 6). Такой способ хранения называется последовательным представлением разреженных матриц.

Доступ к элементу матрицы A с индексами i и j выполняется выборкой индекса i из поля Row, индекса j из поля Colum и значения элемента из поля Value. Следует отметить, что элементы матрицы обязательно запоминаются в порядке возрастания номеров строк для ускорения поиска.

Такое представление матрицы A сокращает используемый объем памяти. Для больших матриц экономия памяти является очень актуальной проблемой.

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

Метод связанных структур переводит статическую структуру матрицы в динамическую. Эта динамическая структура реализована в виде циклических списков.

Для такого представления разреженных матриц требуется следующая структура элемента списка:

type