АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Биологически важные гетероциклические соединения
  2. В водных растворах (глюкоза и фруктоза) существуют в трех взаимопревращающихся формах, две из которых циклические, что объясняется таутомерией моносахаридов в растворах.
  3. Линейные списки
  4. Линейные списки
  5. Маркированные списки
  6. Мультисписки
  7. Рациональное управленческое решение. Способы принятия рационального решения. Списки. Дерево решений. Причинно-следственные диаграммы.
  8. Списки избирателей, порядок их составления и значение
  9. Списки литературы
  10. Списки пользователя
  11. ЦИКЛИЧЕСКИЕ КОДЫ
  12. Циклические процессы. КПД цикла. Цикл Карно. КПД цикла Карно.

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

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

Рис.1.3. Однонаправленный циклический список

 

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

В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка.

current

Рис.1.4. Двунаправленный циклический список

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

· добавление (справа и слева от текущего);

· удаление (справа и слева от текущего);

· поиск;

· вывод списка.

program;

type element = record

data:string;

last, next: pointer;

end;

var

i,n: integer;

point: pointer;

current, pnt, pnt2: ^element;

s:string;

begin

new(current);

current^.data:= ' first ';

current^.next:=current

current^.last:=current;

repeat

writeln(' 1 – сделать текущим ');

writeln(' 2 – список элементов ');

writeln(' 3 – добавить справа ');

writeln(' 4 – добавить слева ');

writeln(' 5 – удалить текущий ');

writeln(' 6 – удалить справа от текущего ');

writeln(' 7 – удалить слева от текущего ');

writeln(' 0 – выход ');

writeln(' текущий элемент: ▒, current^.data);

readln(n);

if n=1 then

{Выбор нового текущего элемента}

begin

writeln(''); readln(s);

pnt:=current; point:=current;

repeat

if pnt^.data=s then current:=pnt;



pnt:=pnt^.next;

until pnt=point;

end;

if n=2 then

{Вывод всех элементов}

begin

pnt:=curent; i:=1

repeat

writeln(i, ' – ', pnt^.data);

pnt:=pnt^.next; i:=i+1;

until pnt=current;

end;

if n=3 then

{Добавление нового элемента справа от текущего}

begin

writeln(' элемент '); readln(s);

new(pnt);

pnt^.data:=s;

pnt^.last:=current;

pnt^.next:=current^.next;

pnt2:=current^.next;

pnt2^.last:=pnt;

current^.next:=pnt;

end;

if n=4 then

{Добавление нового элемента слева от текущего}

begin

writeln(' элемент '); readln(s);

new(pnt);

pnt^.data:=s;

pnt^.last:=current^.last;

pnt^.next:=current;

pnt2:=current^.last;

pnt2^.next:=pnt;

end;

if n=5 and not(current^.next=current) then

begin

{Удаление текущего элемента}

pnt:=current^.last;

pnt2^.next:=current^next;

pnt2^.last:=current^.last;

pnt2:=current^next;

dispose(current);

current:=pnt2;

end;

if n=6 and not(current^.next=current) then

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

begin

pnt:=current^.next;

current^.next:=pnt^next;

pnt2:=pnt^.next;

pnt2^.last:=current;

dispose(pnt);

end;

if n=7 and not(current^.next=current)then

{Удаление элемента слева от текущего}

begin

pnt:=current^.last;

current^.last:=pnt^.last;

pnt2:=pnt^.last;

pnt2^.next:=current;

dispose(pnt);

end;

until n=0;

end.

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |


При использовании материала, поставите ссылку на Студалл.Орг (0.009 сек.)