IPB
ЛогинПароль:

> Внимание! Действует предмодерация

Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.

> Все о динамических структурах данных.
сообщение
Сообщение #1


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Содержание:
Есть материал по теме? высылайте! ваша информация будет размещена здесь!


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Гость






Кольцевые (циклические) двухсвязные списки

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

Для описания элемента списка будем пользоваться следующей структурой:
type
myType = integer;
Ring = ^TRing;
TRing = record
info: myType;
next: Ring;
prev: Ring;
end;


Добавление элемента

Добавляться новые элементы будут перед элементом, помеченным как first (то есть, перед "головой" списка) по следующему алгоритму:
  1. Поскольку выделение памяти под новый элемент должно производиться независимо от того, пуст список или в нем уже есть элементы, то сделаем это в самом начале процедуры добавления, еще перед проверкой на пустоту списка.
  2. В зависимости от того, пуст наш кольцевой список или уже частично заполнен, дальнейшее выполнение процедуры пойдет по одному из двух путей:

    2а) список пуст - устанавливаем указатели prev и next на новый элемент и "помечаем" его как первый (First)

    2б) список не пуст - действовать нужно по-другому:
    • поскольку добавляем в "конец" списка (перед элементом first), то поле next нового элемента указывает на "голову" списка, а поле prev - туда, куда раньше указывал prev "головы";
    • не забываем про "бывший последним" элемент (элемент на который раньше указывал first^.prev). Поле next этого элемента должно указывать на добавляемый элемент, поскольку новый добавляется после "последнего" (перед "первым");
    • ну, и наконец, "голова" списка должна теперь указывать prev-ом на новый элемент, он ведь находится в списке ПЕРЕД "головой"...
    .
procedure Append(var First: Ring; value: myType);
var p: Ring;
begin
{ 1 }
new(p);
p^.info := value;

if first = nil then begin
{ 2а }
p^.next := p;
p^.prev := p;
first := p;
end
else begin
{ 2б }
p^.next := first;
p^.prev := first^.prev;
first^.prev^.next := p;
first^.prev := p;
end;
end;


Удаление элемента

При удалении элемента из кольцевого списка также рассматриваем два случая:
  1. Список содержит один элемент: проверяем, нужно ли удалять этот элемент, и если нужно - просто удаляем его, и обнуляем First, нет элементов - нет "головы" списка.
  2. Список содержит несколько элементов: переназначаем указатели prev^.next и next^.prev удаляемого элемента так, чтобы ни предыдущий ни последующий элементы больше на P не указывали. После этого проверяем, не удаляется ли "головной" элемент (First), и в случае положительного ответа "продвигаем" First на один элемент вперед (если этого не сделать, то после удаления элемента P указатель на "голову" станет невалидным и его использование приведет к получению неправильных результатов). И только после того, как все вышесказанное выполнено, можно удалять элемент списка, на который указывает P...
{ Удалить из списка, начинающегося с First, элемент, на который указывает P }
procedure RemoveItem(var First: Ring; p: Ring);
begin
if (first^.next = first) and (p = first) then
begin
dispose(first);
first := nil; exit;
end;

p^.prev^.next := p^.next;
p^.next^.prev := p^.prev;
if p = first then first := p^.next;
dispose(p); p := nil;
end;


Продолжение следует...
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 20:39
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name