Рекурсивные структуры данных Списки, двоичные деревья.

Презентация:



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

Массивы в Паскале. Создание массива: var a:array [1..5] of integer; i:integer; begin for i:=1 to 5 do begin write ('a[',i,']='); readln(a[i]); end; end.
9.Задана целочисленная матрица. Вывести N чисел - максимальные значения элементов для каждой строки, где N - количество строк матрицы
5.Дана матрица А и вектор Х соответствующих размерностей. Нечетные строки матрицы заменить элементами вектора Х. Результаты работы: n=4 m=
Одномерные массивы Введение. I.Описание Массив – это фиксированное кол - во элементов одного и того же типа, объединенных одним именем, каждый элемент.
PROGRAM example1; const m=100; var a : ARRAY [1.. m] of INTEGER; i,k,n,q : INTEGER; BEGIN readln (n); randomize; WRITELN('Полученный массив:' ); FOR i.
Поиск максимального и минимального элемента линейного массива на языке Turbo Pascal. Program poisk; Const n=10; Type mass=array[1..n] of integer; Var a:mass;
Program Summa; {Суммирование элементов в 1м массиве} Uses Crt; Type Massiv = Array [1..100] of Real; Var A : Massiv; i, N : Integer; S : Real; Begin Write('Введите.
PROGRAM example1; {сдвинуть циклически элементы массива вправо} const m=10; var a : ARRAY [1.. m] of INTEGER; i,k,n: INTEGER; BEGIN randomize; n:=m; WRITELN('Полученный.
1 Списки в языке Haskell. Кубенский А.А. Функциональное программирование. Глава 1. Элементы функционального программирования. [] -- пустой список [1, 2,
Решение задач с использованием массивов
Дан массив. Найти максимальный и минимальный элементы массива и поменять их местами. Выполнение программы Выполнение программы.
Тема: Нахождение минимального и максимального элемента в массиве.
Оператор присваивания := Ввода Read(x1,x2,…) Readln(x1,x2,…) Вывода Writex(x1,x2,…) Writeln(x1,x2,…) Составной оператор begin …. End;
29. Дан массив целых чисел. Найти индексы элементов, значения которых больше значения предыдущего элемента (на­чиная со второго). Program a29; Var i,n:integer;
Алгоритмы на графах Представление графов Построение остовного дерева Нахождение компонент смежности Перебор в глубину и в ширину.
3. Дана прямоугольная матрица, элементами которой являются целые числа. Поменять местами ее строки следующим образом: первую строку с последней, вторую.
Одномерный массив Turbo Pascal 9 класс. Объясните каждый шаг в программе. Что делает программа? Сколько раз срабатывает цикл? Var A : array [1..10] of.
Способы ввода значений в массив на Паскале 1) Заполнение массива с клавиатуры а) program massiv_1; const n=5; vari: integer; a: array[1..n] of integer;
Решение олимпиадных задач Учитель информатики МБОУ«СОШ 23 с углубленным изучением отдельных предметов» Энгельсского муниципального района Саратовской области.
Транксрипт:

Рекурсивные структуры данных Списки, двоичные деревья

Список Списком является пустой список (nil) Если l – список элементов типа a, e – элемент типа a, то cons(e,l) – список элементов типа a

Работа со списками program testlist; type plist = ^list; list = record el : integer; next : plist; end; function addEl(l : plist; el : integer) : plist; var pl : plist; begin New(pl); pl^.el := el; pl^.next := l; addEl := pl; end; var l : plist; i : integer; begin l := nil; for i := 1 to 10 do l := addEl(l,i); end. type plist = ^list; list = object el : integer; next : plist; end;

Работа со списками procedure writelist(l : plist); begin while l nil do begin write(l^.el,' '); l := l^.next; end; procedure writelistrec(l : plist); begin if l nil then begin write(l^.el,' '); writelistrec(l^.next); end;

Двоичное дерево Деревом является пустое дерево Если l 1, l 2– деревья элементов типа a, e – элемент типа a, то tree(el,l1,l2) – дерево элементов типа a

Работа с деревьями program testtree; type ptree = ^tree; tree = record el : integer; left, right : ptree; end; function addEl(l,r : ptree; el : integer) : ptree; var pl : ptree; begin New(pl); pl^.el := el; pl^.left := l; pl^.right := r; addEl := pl; end; function copyTree(t : ptree) : ptree; var pt : ptree; begin if t = nil then copyTree := nil else begin New(pt); pt^.el := t^.el; pt^.left := copyTree(t^.left); pt^.right := copyTree(t^.right); copyTree := pt; end; prevt := nil; t := addEl(nil,nil,i); for i := 1 to 6 do begin r := copyTree(prevt); prevt := t; t := addEl(t,r,i); end;

Работа с деревьями procedure writetree(t : ptree; level : integer); var i : integer; begin if t nil then begin writetree(t^.left,level+1); for i := 1 to level do write(' '); writeln(t^.el); writetree(t^.right,level+1); end;

Поиск в дереве function search(t : ptree; el : integer) : boolean; begin if t = nil then search := false else if el = t^.el then search := true else if el < t^.el then search :=search(t^.left,el) else search := search(t^.right,el) end;

Сортировка с помощью двоичного дерева procedure insert(var t : ptree; el : integer); begin if t = nil then begin New(t); t^.el := el; t^.left := nil; t^.right := nil; end else if el < t^.el then insert(t^.left,el) else insert(t^.right,el) end;