10.09.2008Рекурсивная обработка списков1 Структуры и алгоритмы обработки данных, 1 Лекция 3 Рекурсивная обработка списков 1.Представление и реализация. - презентация

1 Рекурсивная обработка списков1 Структуры и алгоритмы обработки данных, 1 Лекция 3 Рекурсивная обработка списков 1.Представление и реализация линейных списков 2.Иерархические (нелинейные) списки

2 Рекурсивная обработка списков2 Реализация линейных списков {Ссылочное представление в динамической памяти } type {El базовый тип элементов списка (описан в Global)} Link = ^ Node;{ссылка на звено в цепи} Node = record{звено цепи ( списка ): } Info: El;{ - содержимое (элемент списка) } Next: Link ;{ - ссылка на следующее звено } end {Node}; L_list = Link; {Л-список}

3 Рекурсивная обработка списков3 {1} function Null (x: L_list): Boolean; {список пуст} {2}function Head (x: L_list): El; {селектор «голова» списка; отказ, если x – пустой список} {3} function Tail (x: L_list): L_list; {селектор «хвост» списка; отказ, если x – пустой список} {4} function Cons (x: El; y: L_list): L_list; {конструктор; отказ, если исчерпана память} Реализация линейных списков

4 Рекурсивная обработка списков4 {1} function Null (x: L_list): Boolean; begin Null:= (x = nil); end {Null}; {2} function Head (x: L_list): El; begin if Null(x) then begin WriteLn; WriteLn(' ! Head(Nil) '); Halt; end else Head := x ^. Info; end {Head}; Реализация линейных списков

5 Рекурсивная обработка списков5 {3} function Tail (x: L_list): L_list; begin if Null(x) then begin WriteLn; WriteLn(' ! Tail(Nil) '); Halt; end else Tail := x ^. Next ; end {Tail}; Реализация линейных списков

6 Рекурсивная обработка списков6 {4} function Cons (x: El; y: L_list): L_list; var p : L_list; begin if MaxAvail >= SizeOf (Node) then begin New(p); p ^. Info := x; p ^. Next := y; Cons := p; end else begin WriteLn; WriteLn(' ! Исчерпана память '); Halt; end; end {Cons};

7 Рекурсивная обработка списков7 Замечание к реализации Cons Остается доступ к части нового списка через ссылку y. Ср. y := Cons (x, y); и z := Cons (x, y); x:x: y:y: p:p: Cons: г л аз г

8 Рекурсивная обработка списков8 Выполняются ли аксиомы для базовых функций при такой реализации? A3) Head(Cons(x, y)) = x; x:x: б Cons: б y:y: ро

9 Рекурсивная обработка списков9 A4) Tail(Cons(x, y)) = y; x:x: б Cons: б y:y: ро Tail: Пусть z := Tail(Cons(x, y)). Значения z и y совпадают.

10 Рекурсивная обработка списков10 A5) Cons(Head(z), Tail(z)) = z. Значения z и Cons не совпадают ! Списки z и Cons идентичны. Cons: б z:z: ро Tail: б б

11 Рекурсивная обработка списков11 Особенности реализации Concat(y, z) = if Null(y) then z else Cons(Head(y), Concat(Tail(y), z)). Пример Concat((a b), (c d)) = Cons(a, Concat((b), (c d))). Concat((b), (c d)) = Cons(b, Concat(Nil, (c d))). Concat(Nil, (c d)) = (c d). Concat((b), (c d)) = Cons(b, (c d)) = (b c d). Concat((a b), (c d)) = Cons(a, (b c d)) = (a b c d). Замечания: 1. Список y разбирается и затем собирается даже если список z пуст. 2. Функция Cons вызывается Size(y) раз.

12 Рекурсивная обработка списков12 Функция Concat на языке Паскаль function Concat (y, z: L_list): L_list; begin if Null (y) then Concat := z else Concat := Cons (Head (y), Concat (Tail (y), z)); end

13 Рекурсивная обработка списков13 Пример Concat((a b), (c d)) y:y: Concat: z:z: cd b a a b Concat с Copy a b Concat2: c d

14 Рекурсивная обработка списков14 Copy (x) if Null (x) then Nil else Cons (Head (x), Copy (Tail(x))); function Copy (x: L_list): L_list; begin if Null (x) then Copy := nil else Copy := Cons (Head (x), Copy (Tail(x))); end {Copy};

15 Рекурсивная обработка списков15 function Concat (y, z: L_list): L_list; begin if Null (y) then Concat := Copy (z) else Concat := Cons (Head (y), Concat (Tail (y), z)); end Функция Concat c Copy на языке Паскаль

16 Рекурсивная обработка списков16 Процедура Conc – аналог операции x := x y procedure Conc (var x : L_list; y: L_list); begin if Null (x) then x := y else Conc(x.Next, y); end Итерация if x = nil then x := y else begin q := x; while q.Next nil do q := q.Next ; q.Next := y end

17 Рекурсивная обработка списков17 Иерархические списки См. 1.7 в учебном пособии Рекурсивное определение типа данных S_expr (El), использующее данное ранее определение линейного списка (типа L_list): ::= |, ::=.

18 Рекурсивная обработка списков18 Примеры Полная записьСокращенная запись a Nil (a. (b. (c. Nil))) (a. ((b. (c. Nil)). (d. (e. Nil)))) a ( ) (a b c) (a (b c) d e) (a (b c) ( (d e (f) ) g) h)(a (b c) ( (d e (f) ) g) h)

19 Рекурсивная обработка списков19 Размеченное объединение множеств A = {1, 3, 5}; B = {2, 3, 4, 5}; A U B = {1, 2, 3, 4, 5}; A B = {1 A, 2 B, 3 A, 3 B, 4 B, 5 A, 5 B }; A B = {(1, A), (2, B), (3, A), (3, B), (4, B), (5, A), (5, B)}; (e, t) A B (e A) or (e B), t {a, b} t – tag (тэг, ярлык, этикетка) Если (e A),то t = a Если (e B), то t = b A B = (A {a}) U (B {b} ) ::=

20 Рекурсивная обработка списков20 Особенности реализации ::= |, ::=. ::= | ::= Nil ::= ::= (. ) ::= Сначала анализ: атом – список Затем: пустой список?

21 Рекурсивная обработка списков21 Представление type { El – базовый тип для атомов (описан в Global)} Ref_S_expr = ^ S_expr; {ссылка на S-выражение} S_expr = record { S-выражение:} case Tag: (Atomic, Pair) of Atomic: (Atm: El); {атомарное} Pair: (Hd, Tl: Ref_S_expr){пара} end {S_expr}; H_list = Ref_S_expr;{иерархический список} Итак, H_list это ссылка на S_expr. Пустой список – ссылка nil. Если H_list nil, тогда анализировать «атом – не атом».

22 Рекурсивная обработка списков22 Замечание к графическому изображению списка Более точным было бы изображение элемента списка с явным указанием поля тэга. : или Atomic Pair Atm: El Tl : Ref_S_expr Hd : Ref_S_expr Tag A A

23 Рекурсивная обработка списков23 aed cb Замечание к графическому изображению списка

24 Рекурсивная обработка списков24 Copy (x) if Null (x) then Nil else if Atom (x) then x else Cons (Copy ( Head (x)), Copy (Tail(x)) ); {8} function Copy (x: H_list): H_list; begin if Null (x) then Copy := nil else if Atom (x) then Copy := Make_Atom (x ^.Atm) else Copy := Cons (Copy (Head (x)), Copy (Tail(x))); end {Copy};

25 Рекурсивная обработка списков25 Процедура вывода списка с обрамляющими его скобками {4} procedure Write_H_list (S: H_list); begin {пустой список выводится как () } if Null (x) then Write(' ( ) ') else if Atom (x) then Write (' ', x ^. Atm) else {непустой список} begin Write (' ( '); Write_List (x); Write (' ) ') end; end {Write_H_list};

26 Рекурсивная обработка списков26 Процедура вывода списка без обрамляющих скобок {5} procedure Write_List (x: Ref_S_expr); begin if not Null (x) then begin Write_H_list (Head (x)); Write_List (Tail (x)) end; end {Write_List}

27 Рекурсивная обработка списков27 КОНЕЦ ЛЕКЦИИ