Архив категории ‘Динамические структуры данных на языке программирования Pascal’

Поиск звена в двунаправленном списке

    На этом шаге мы рассмотрим как найти звено в двунаправленном списке.     Поиск в двунаправленном списке может проводиться в двух направлениях:     1). Поиск в прямом направлении: от начала двунаправленного списка к его хвосту.     Приведем функцию, в которой следующие параметры:     pBegin - указатель на список (ссылка на заглавное звено);     Key - […]

Очистка двунаправленного списка

    На этом шаге мы рассмотрим процедуры очистки двунаправленного списка. Приведем не рекурсивную процедуру "очистки" двунаправленного списка. Рrocedure Free (pBegin : PtrRec; var pEnd: PtrRec); Begin While pEnd <> pBegin do Begin pEnd := pEnd^.pPrev; Disрose (pEnd^.pNext); pEnd^.pNext := Nil; End; End;     Приведем рекурсивную процедуру "очистки" двунаправленного списка. Рrocedure Free_Rec (var pRing: PtrRec); Begin […]

Проход по двунаправленному списку от его конца

    На этом шаге мы рассмотрим проход по двунаправленному списку от его конца.     Пусть значением переменной pAux является адрес некоторого элемента списка целых чисел. Тогда после присваивания pAux := pAux^.pPrev, ее значением будет или ссылка на предыдущий элемент этого списка (если такой элемент имеется) или Nil. Пользуясь таким способом перехода от одного элемента к […]

Проход по двунаправленному списку от его начала

    На этом шаге мы рассмотрим проход по двунаправленному списку от его начала.     Пусть значением переменной pAux является адрес некоторого элемента списка, тогда после присваивания pAux := pAux^.pNext, ее значением будет или ссылка на следующий элемент этого списка (если такой элемент имеется) или Nil. Пользуясь таким способом перехода от одного элемента к другому, можно […]

Двунаправленные списки с заглавным звеном

    На этом шаге мы рассмотрим формирование двунаправленного списка с заглавным звеном..     Для начала заметим, что существует несколько алгоритмов построения двунаправленных списков.     Рассмотрим первый алгоритм формирования двунаправленного списка при помощи схем "до и после" Кнута: {Создание заглавного звена} New (pBegin); Рис.1. Сформируем заглавное звено двунаправленного списка pBegin^.pNext := Nil; pBegin^.pPrev := Nil; Рис.2. […]

Двунаправленные списки

    На этом шаге мы рассмотрим двунаправленные списки..     В зависимости от количества связей между соседними элементами различают односвязные и двусвязные списки.     Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка.     Двунаправленный список отличается двумя основными преимуществами.     Во-первых, список может просматриваться в […]

Удаление звена кольцевого списка с удаленным заглавным звеном

    На этом шаге мы рассмотрим удаление звена однонаправленного кольцевого списка с удаленным заглавным звеном..     Удаление звена, на которое указывает pCKey, осуществляется процедурой: Procedure Del_Elem1 (pCKey: PtrRec); Var q, pAux: PtrRec; Begin If pCKey^.pNext=pCKey Then Begin pBegin^.pNext := Nil; Writeln ('Кольцо пусто!') End Else Begin q := pBegin; pAux := pBegin^.pNext; While pAux <> […]

Добавление звена в кольцевой список с удаленным заглавным звеном

    На этом шаге мы рассмотрим добавление звена в однонаправленный кольцевой список с удаленным заглавным звеном..     Добавление звена с информационным полем R после звена, на которое указывает pCKey, осуществляется процедурой: Procedure Add_Elem1 (pCKey: PtrRec; R: TypeElement); Var pAux: PtrRec; Begin New (pAux); pAux^.Element := R; pAux^.pNext := pCKey^.pNext; pCKey^.pNext := pAux; End;     Добавление […]

Поиск звена в списке с удаленным заглавным звеном

    На этом шаге мы рассмотрим поиск звена в однонаправленном кольцевом списке с удаленным заглавным звеном..     Поиск компоненты с заданным ключом необходим для процедур чтения и вставки компоненты в кольцевой список. Пусть требуется найти компоненту списка с ключом Key. Приведем функцию поиска: Function Find (pBegin: PtrRec; Key: TypeElement; var pCKey: PtrRec) : Boolean; Var […]

Просмотр кольцевого однонаправленного списка с удаленным заглавным звеном

    На этом шаге мы рассмотрим просмотр однонаправленного кольцевого списка с удаленным заглавным звеном..     Приведем процедуру просмотра кольцевого однонаправленного списка: Procedure Print_Ring (pBegin: PtrRec); Var pAux: PtrRec; Begin pAux := pBegin^.pNext; If pBegin^.pNext<>Nil Then Begin While pAux^.pNext <> pBegin^.pNext do Begin Write (pAux^.Element,' '); pAux := pAux^.pNext End; Writeln (pAux^.Element); End Else Writeln ('Список […]