Добавление звена в начало списка — КиберПедия 

История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Добавление звена в начало списка

2020-06-02 121
Добавление звена в начало списка 0.00 из 5.00 0 оценок
Заказать работу

  {Процедура добавления звена в начало списка; в x содержится добавляемая информация}   Procedure V_Nachalo(Var First: U; X: BT);   Var Vsp: U;   Begin           New(Vsp);           Vsp^.Inf:= X;           Vsp^.Next:= First; {То звено, что было заглавным, становится вторым по счёту}           First:= Vsp; {Новое звено становится заглавным}   End;

Удаление звена из начала списка

  {Процедура удаления звена из начала списка;    в x содержится информация из удалённого звена}   Procedure Iz_Nachala(Var First: U; Var X: BT);   Var Vsp: U;   Begin           Vsp:= First; {Забираем ссылку на текущее заглавное звено}           First:= First^.Next; {То звено, что было вторым по счёту, становится заглавным}           X:= Vsp^.Inf; {Забираем информацию из удаляемого звена}           Dispose(Vsp); {Уничтожаем звено}   End;

Добавление звена в произвольное место списка, отличное от начала (после звена, указатель на которое задан)

  {Процедура добавления звена в список после звена,    на которое ссылается указатель Pred;    в x содержится информация для добавления}   Procedure V_Spisok(Pred: U; X: BT);   Var Vsp: U;   Begin       New(Vsp); {Создаем пустое звено}       Vsp^.Inf:= X; {Заносим информацию}       Vsp^.Next:= Pred^.Next; {Теперь это звено ссылается на то,                                 что было следом за звеном Pred}       Pred^.Next:= Vsp; {Теперь новое звено встало вслед за звеном Pred}   End;

Удаление звена из произвольного места списка, отличного от начала (после звена, указатель на которое задан)

  {Процедура удаления звена из списка после звена,    на которое ссылается указатель Pred;    в x содержится информация из удалённого звена}   Procedure Iz_Spiska(Pred: U; Var X: BT);   Var Vsp: U;   Begin        Vsp:= Pred^.Next; {Забираем ссылку на удаляемое звено}        {Удаляем звено из списка, перенаправив ссылку на следующее           за ним звено}        Pred^.Next:= Pred^.Next^.Next;        X:= Vsp^.Inf; {Забираем информацию из удаляемого звена}        Dispose(Vsp); {Уничтожаем звено}   End;

 

Лекция 16. Динамические переменные: другие виды списков, стек и очередь.

Другие виды списков

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

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

2. Замкнутость списка. Поле next в последнем элементе указывает на первый элемент. Иначе такие списки называются кольцевыми. Этот вид позволяет упростить процедуру удаления элемента списка и другие операции.

С учётом этих свойств возможны четыре различных типа списков.

 

 

Для примера рассмотрим описание и реализацию кольцевого двунаправленного списка:

type tItemPtr = ^tItem

tItem = record

  data: tData;

  next,prev: tItemPtr;

end;

var List: tItemPtr; { список - указатель на один из элементов }

........

{ Удалить после указанного:}

procedure DelAfter(p: tItemPtr);

var q: tItemPtr;

Begin

if (p<> nil) and (p^.next<>p) then begin

q:=p^.next^.next;

dispose(p^.next);

p^.next:=q;

q^.prev:=p;

end;

end;

{Вставить перед указанным:}

procedure InsertBefore(p: tItemPtr; d: tData);

var q: tItemPtr;

Begin

if p<> nil then begin

new(q);

q^.data:=d;

q^.next:=p;

q^.prev:=p^.prev;

p^.prev:=q;

q^.prev^.next:=q;

end;

end;

 

 

Стек и очередь

Стек -список, для которого операции выбора, вставки и удаления компонента ограничены началом списка.Т.е. стек - это список, сформированный по принципу LIFOLast Input – First Output («Последним пришел - Первым вышел», т.е. обслуживание в порядке, обратном поступлению).

 

Очередь - список, у которого операции удаления и выборки компонента выполняются с одного конца, а операция вставки – с другого.Т.е. очередь - это список, сформированный по принципу FIFOFirst Input – First Output («Первым пришел - Первым вышел», т.е. обслуживание в порядке поступления).

Стеком называется такой способ хранения данных, при котором элемент, записанный в хранилище данных, последним всегда извлекается первым (дисциплина LIFO – «last in - first out»). При извлечении элемента происходит его удаление со стека.

Рассмотрим простейший пример использования стека. Предположим, что имеется строка, состоящая из одних лишь открывающих и закрывающих скобок. Требуется определить, является ли она правильным скобочным выражением (то есть для каждой открывающей скобки должна найтись закрывающая). Заведём массив и переменную для хранения номера последнего значимого элемента в массиве (то есть вершины стека), в который при проходе по строке будем складывать все открывающиеся скобки (с увеличением номера вершины на 1), а при встрече с закрывающей будем удалять соответствующую открывающую (попросту уменьшать номер вершины стека). Если окажется, что «пришла» закрывающая скобка, а стек пуст (то есть номер вершины равен 0), то выражение ошибочно. Это же можно сказать и в случае, когда строка закончилась, а стек не пуст.

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

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

Любая реализация стека должна содержать следующие процедуры и функции:

procedure InitStack – инициализация стека;

procedure Push(d: tData) – положить элемент в стек;

procedure Pop(var d: tData) – извлечь элемент с вершины стека;

function NotEmpty: boolean – проверка стека на пустоту;

 

Очередь отличается от стека тем, что последний пришедший в неё элемент будет извлечён последним, а первый – первым («FIFO»). С помощью списков её можно организовать следующим образом: будем хранить не только указатель на «голову» списка, но и на «хвост»; добавлять будем в «хвост», а извлекать – из «головы».

Любая реализация очереди (не обязательно с помощью списков) должна «уметь» выполнять такие действия:

procedure InitQueue – инициализация очереди;

procedure AddQueue(d: tData) – поставить элемент в очередь;

procedure SubQueue(var d: tData) – извлечь элемент из очереди;

function NotEmpty: boolean – проверка очереди на пустоту;

 


Поделиться с друзьями:

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...

Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.015 с.