СПИСКИ. СТЕК. ОЧЕРЕДЬ Варианты списков 1.Однонаправленные списки 1.1. Списки без заглавного звена... a n nil L a1a1 a2a2 Удаление 1 звена L a1a1 a 2... - презентация

1 СПИСКИ. СТЕК. ОЧЕРЕДЬ Варианты списков 1. Однонаправленные списки 1.1. Списки без заглавного звена... a n nil L a1a1 a2a2 Удаление 1 звена L a1a1 a 2... Удаление произвольного не 1-го звена L a1a1 a2a2 a3a3...

2 1.2 Список с заглавным звеном a n nil L a1a1 a3a3... заглавное звено 1.3 Циклические списки anan L a1a1 a2a Двунаправленные списки L... nil a 1 a 2 a n-1 a n nil

3 Стек (stack) Стеком (другое название – магазин) называется последовательность однотипных элементов, по отношению к которой применяются следующие две операции: 1) новые элементы всегда добавляются в конец последовательности, 2) элементы всегда удаляются из конца последовательности. стек : Векторное представление стека … N Mabcd k4 const N =...; {размер массива M} type ТЭС =...; {тип элементов стека} стек = record M: array[1..N] of TЭС; k: 0..N end;

4 1) Начальная установка стека: procedure Нач УстСтека(var S: стек); {сделать стек пустым} begin S.k:=0 end; 2) Проверка на пустой стек: function Пустой Стек(var S: стек): boolean; {стек пуст?} begin Пустой Стек:=S.k=0 end; 3) Запись элемента в стек: procedure ВСтек(x: TЭС; var S: стек); {x --> стек} begin with S do begin if k=N then ошибка(1); {переполнение стека} k:=k+1; M[k]:=x end end; 4) Считывание элемента из стека: procedure Из Стека(var S: стек; var x: TЭС); {стек --> x} begin if Пустой Стек(S) then ошибка(2); {пустой стек} with S do begin x:=M[k]; k:=k-1 end end;

5 function Соотв Скобок(ОС, ЗС: char): boolean; begin Соотв Скобок:=(ОС='(') and (ЗС=')') or (ОС='[') and (ЗС=']') or (ОС='{') and (ЗС='}') end; function скобки: boolean; var S: стек; {любое представление, ТЭС=char} c, d: char; begin Нач УстСтека(S); Скобки:=false; read(c); while (c<>.) and not Ош do begin if (c='(') or (c='[') or (c='{') then ВСтек(c,S) else if (c=')') or (c=']') or (c='}') then begin if Пустой Стек(S) then break; Из Стека(S,d); if not Соотв Скобок(d,c) then break end; end; {of while} if Пустой Стек(S) then скобки:= true; end;

6 Очередь Очередь - это последовательность однотипных элементов, по отношению к которой применяются следующие две операции: 1) новый элемент добавляется в конец очереди, 2) первым всегда удаляется элемент из начала очереди. очередь: Списковое представление очереди c nil нач ab кон type ТЭО =...; {тип элементов очереди (любой)} адрес = звено; звено = record элем: ТЭО; след: адрес end; очередь = record нач, кон: адрес end;

7 1) Начальная установка очереди procedure Нач УстОчереди(var Q: очередь); {сделать очередь пустой} begin Q.нач:=nil; Q.кон:=nil end; 2) Проверка на пустую очередь function Пустая Очередь(var Q: очередь): boolean; {очередь пуста?} begin Пустая Очередь:= Q.нач=nil end; 3) Запись элемента в очередь procedure ВОчередь(x: T; var Q: очередь); {x --> очередь} var p: адрес; begin new(p); p.элем:=x; p.след:=nil; with Q do begin if нач=nil then нач:=p else кон.след:=p; кон:=p end end;

8 4) Считывание элемента из очереди procedure Из Очереди(var Q: очередь; var x: ТЭО); {очередь --> x} var p: адрес; begin if Пустая Очередь(Q) then ошибка(3); with Q do begin p:=нач; x:=p.элем; нач:=p.след; if нач=nil then кон:=nil; dispose(p) end end;

9 3.3 Пример на использование очереди Пусть для ввода дана последовательность ненулевых целых чисел, за которой следует ноль (это признак конца последовательности). Требуется вывести на экран эти же ненулевые числа в следующем порядке: сначала - все положительные числа, а затем – все отрицательные числа, причем должен сохраняться исходный взаимный порядок следования в каждой из этих двух групп. Например: 2 8 –4 5 –2 4 0 ==> –4 -2 Идея решения: вводим числа по одному; если очередное число положительно, то сразу выводим его, а если это число отрицательно, то ставим его в очередь: очередь –4 5 – вывод

10 procedure Вывод Чисел; var Отр: очередь; {любое представление, ТЭО=integer} r: integer; begin Нач УстОчереди(Отр); read(k); while k<>0 do begin if k>0 then write(k, ' ') else Вочередь(k,Отр); read(k); end; while not Пустая Очередь(Отр) do {вывод < 0} begin Из Очереди(Отр,k); write(k, ' ') end; writeln end;