Паскаль_ДинСтруктурыДанных.ppt

Тема 1. Указатели

Динамические структуры данных(язык Паскаль)

Статические данные

var x, y: integer;
z: real;
A: array[1..10] of real;
str: string;

Динамические данные

Указатели

var pC: ^char; // адрес символа
pI: ^integer; // адрес целой переменной
pR: ^real; // адрес вещ. переменной

var m: integer; // целая переменная
pI: ^integer; // указатель
A: array[1..2] of integer; // массив
...
pI:= @ m; // адрес переменной m
pI:= @ A[1]; // адрес элемента массива A[1]
pI:= nil; // нулевой адрес

@

^

nil

Обращение к данным через указатель

program qq;
var m, n: integer;
pI: ^integer;
begin
m := 4;
pI := @m;
writeln('Адрес m = ', pI); // вывод адреса
writeln('m = ', pI^); // вывод значения
n := 4*(7 - pI^); // n = 4*(7 - 4) = 12
pI^ := 4*(n - m); // m = 4*(12 – 4) = 32
end.

^

Обращение к данным (массивы)

program qq;
var i: integer;
A: array[1..4] of integer;
pI: ^integer;
begin
for i:=1 to 4 do A[i] := i;
pI := @A[1]; // адрес A[1]
while ( pI^ <= 4 ) // while( A[i] <= 4 )
do begin
pI^ := pI^ * 2; // A[i] := A[i]*2;
pI := pI + 1; // к следующему элементу
end;
end.

Что надо знать об указателях

Тема 2. Динамические массивы

Динамические структуры данных(язык Паскаль)

Где нужны динамические массивы?

выделить память

удалить массив

Использование указателей (Delphi)

program qq;
type intArray = array[1..1] of integer;
var A: ^intArray;
i, N: integer;
begin
writeln('Размер массива>');
readln(N);
GetMem(pointer(A), N*sizeof(integer));
for i := 1 to N do
readln(A[i]);
... { сортировка }
for i := 1 to N do
writeln(A[i]);
FreeMem(pointer(A));
end.

Использование указателей

Ошибки при работе с памятью

Динамические массивы(Delphi)

program qq;
var A: array of integer;
i, N: integer;
begin
writeln('Размер массива>');
readln(N);
SetLength ( A, N );
for i := 0 to N-1 do
readln(A[i]);
... { сортировка }
for i := 0 to N-1 do
writeln(A[i]);
SetLength( A, 0 );
end.

Динамические массивы (Delphi)

Динамические матрицы (Delphi)

var A: array of array of integer;
N, M: integer;
begin
writeln('Число строк и столбцов>');
readln(N, M);
SetLength ( A, N, M );
... // работаем, как с обычной матрицей
SetLength( A, 0, 0 );
end.

Тема 3. Структуры (записи)

Динамические структуры данных(язык Паскаль)

Структуры (в Паскале – записи)

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

Задача: объединить эти данные в единое целое

Размещение в памяти

Одна запись

readln(Book.author); // ввод
readln(Book.title);
Book.year := 1998; // присваивание
if Book.pages > 200 then // сравнение
writeln(Book.author, '.', Book.title); // вывод

Объявление (выделение памяти):

var Book: record
author: string[40]; // автор, строка
title: string[80]; // название, строка
year: integer; // год издания, целое
pages: integer; // кол-во страниц, целое
end;

Обращение к полям:

Массив записей

Объявление (выделение памяти):

const N = 10;
var aBooks: array[1..N] of record
author: string[40];
title: string[80];
year: integer;
pages: integer;
end;

Books[1] ... Books[10]

Массив записей

for i:=1 to N do begin
readln(aBooks[i].author);
readln(aBooks[i].title);
...
end;
for i:=1 to N do
if aBooks[i].pages > 200 then
writeln(aBooks[i].author, '.',
aBooks[i].title);

Обращение к полям:

Новый тип данных – запись

const N = 10;
var Book: TBook; // одна запись
aBooks: array[1..N] of TBook; // массив

Объявление типа:

type TBook = record
author: string[40]; // автор, строка
title: string[80]; // название, строка
year: integer; // год издания, целое
pages : integer; // кол-во страниц, целое
end;

Объявление переменных и массивов:

Записи в процедурах и функциях

Book.author := 'А.С. Пушкин';
ShowAuthor ( Book );
Book.year := 1800;
writeln( IsOld(Book) );

Процедура:

procedure ShowAuthor ( b: TBook );
begin
writeln ( b.author );
end;

Основная программа:

function IsOld( b: TBook ): boolean;
begin
IsOld := b.year < 1900;
end;

Функция:

Файлы записей

Объявление указателя на файл:

var F: file of TBook;

Assign(F, 'books.dat'); { связать с указателем }
Rewrite(F); { открыть файл для запись }
writeln(F, Book); { запись }
for i:=1 to 5 do
writeln(aBook[i]); { запись }
Close(F); { закрыть файл }

Запись в файл:

Чтение из файла

Известное число записей:

Assign(F, 'books.dat'); { связать с указателем }
Reset(F); { открыть для чтения }
Read(F, Book); { чтение }
for i:=1 to 5 do
Read(F, aBook[i]); { чтение }
Close(F); { закрыть файл }

«Пока не кончатся»:

count := 0;
while not eof(F) do begin
count := count + 1; { счетчик }
Read(F, aBook[count]); { чтение }
end;

Пример программы

Задача: в файле books.dat записаны данные о книгах в виде массива структур типа TBook (не более 100). Установить для всех 2008 год издания и записать обратно в тот же файл.

type Tbook … ;
const MAX = 100;
var aBooks: array[1..MAX] of TBook;
i, N: integer;
F: file of TBook;
begin
{ прочитать записи из файла, N - количество }
for i:=1 to N do
aBooks[i].year := 2008;
{ сохранить в файле }
end.

type TBook … ;

Пример программы

Чтение «пока не кончатся»:

Assign(f, 'books.dat');
Reset(f);
N := 0;
while not eof(F) and (N < MAX) do begin
N := N + 1;
read(F, aBooks[N]);
end;
Сlose(f);

Assign(f, 'books.dat'); { можно без этого }
Rewrite(f);
for i:=1 to N do write(F, aBooks[i]);
Close(f);

Сохранение:

Выделение памяти под запись

var pB: ^TBook;
begin
New(pB);
pB^.author := 'А.С. Пушкин';
pB^.title := 'Полтава';
pB^.year := 1990;
pB^.pages := 129;
Dispose(pB);
end.

New(pB);

pB^

Dispose(pB);

pB: ^TBook;

Сортировка массива записей

Ключ (ключевое поле) – это поле записи (или комбинация полей), по которому выполняется сортировка.

const N = 100;
var aBooks: array[1..N] of TBook;
i, j, N: integer;
temp: TBook; { для обмена }
begin
{ заполнить массив aBooks }
{ отсортировать = переставить }
for i:=1 to N do
writeln(aBooks[i].title,
aBooks[i].year:5);
end.

Сортировка массива записей

for i:=1 to N-1 do
for j:=N-1 downto i do
if aBooks[j].year > aBooks[j+1].year
then begin
temp := aBooks[j];
aBooks[j] := aBooks[j+1];
aBooks[j+1] := temp;
end;

Сортировка массива записей

Проблема: как избежать копирования записи при сортировке?
Решение: использовать вспомогательный массив указателей, при сортировке переставлять указатели.

До
сортировки:

После
сортировки:

Вывод результата:

for i:=1 to N do
writeln(p[i]^.title, p[i]^.year:5);

p[i]^

p[i]^

Реализация в программе

type PBook = ^TBook; { новый тип данных }
var p: array[1..N] of PBook;
begin
{ заполнение массива записей}
for i:=1 to N do
p[i] := @aBooks[i];








for i:=1 to N do
writeln(p[i]^.title, p[i]^.year:5);
end.

for i:=1 to N-1 do
for j:=N-1 downto i do
if p[j]^.year > p[j+1]^.year then begin
temp := p[j];
p[j] := p[j+1];
p[j+1] := temp;
end;

Тема 4. Списки

Динамические структуры данных(язык Паскаль)

Динамические структуры данных

Строение: набор узлов, объединенных с помощью ссылок.
Как устроен узел:

Типы структур:

списки

деревья

графы

односвязный

двунаправленный (двусвязный)

циклические списки (кольца)

Когда нужны списки?

Задача (алфавитно-частотный словарь). В файле записан текст.  Нужно записать в другой файл в столбик все слова,  встречающиеся в тексте, в алфавитном порядке, и количество  повторений для каждого слова.
Проблемы:
количество слов заранее неизвестно (статический массив);
количество слов определяется только в конце работы (динамический массив).
Решение – список.
Алгоритм:
создать список;
если слова в файле закончились, то стоп.
прочитать слово и искать его в списке;
если слово найдено – увеличить счетчик повторений, иначе добавить слово в список;
перейти к шагу 2.

Что такое список:
пустая структура – это список;
список – это начальный узел (голова) и связанный с ним список.

Списки: новые типы данных

type PNode = ^Node; { указатель на узел }
Node = record { структура узла }
word: string[40]; { слово }
count: integer; { счетчик повторений }
next: PNode; { ссылка на следующий }
end;

Новые типы данных:

Адрес начала списка:

var Head: PNode;
...
Head := nil;

Что нужно уметь делать со списком?

Создать новый узел.
Добавить узел:
а) в начало списка;
б) в конец списка;
в) после заданного узла;
г) до заданного узла.
Искать нужный узел в списке.
Удалить узел.

Создание узла

function CreateNode(NewWord: string): PNode;
var NewNode: PNode;
begin
New(NewNode);
NewNode^.word := NewWord;
NewNode^.count := 1;
NewNode^.next := nil;
Result := NewNode;
end;

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

1) Установить ссылку нового узла на голову списка:

NewNode^.next := Head;

2) Установить новый узел как голову списка:

Head := NewNode;

procedure AddFirst ( var Head: PNode; NewNode: PNode );
begin
NewNode^.next := Head;
Head := NewNode;
end;

var

Добавление узла после заданного

1) Установить ссылку нового узла на узел, следующий за p:

NewNode^.next = p^.next;

2) Установить ссылку узла p на новый узел:

p^.next = NewNode;

procedure AddAfter ( p, NewNode: PNode );
begin
NewNode^.next := p^.next;
p^.next := NewNode;
end;

Проход по списку

var q: PNode;
...
q := Head; // начали с головы
while q <> nil do begin // пока не дошли до конца
... // делаем что-то хорошее с q
q := q^.next; // переходим к следующему
end;

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

procedure AddLast ( var Head: PNode; NewNode: PNode );
var q: PNode;
begin
if Head = nil then
AddFirst ( Head, NewNode )
else begin
q := Head;
while q^.next <> nil do
q := q^.next;
AddAfter ( q, NewNode );
end;
end;

Добавление узла перед заданным

procedure AddBefore(var Head: PNode; p, NewNode: PNode);
var q: PNode;
begin
q := Head;
if p = Head then
AddFirst ( Head, NewNode )
else begin
while (q <> nil) and (q^.next <> p) do
q := q^.next;
if q <> nil then AddAfter ( q, NewNode );
end;
end;

Добавление узла перед заданным (II)

procedure AddBefore2 ( p, NewNode: PNode );
var temp: Node;
begin
temp := p^; p^ := NewNode^;
NewNode^ := temp;
p^.next := NewNode;
end;

Поиск слова в списке

function Find(Head: PNode; NewWord: string): PNode;
var q: PNode;
begin
q := Head;
while (q <> nil) and (NewWord <> q^.word) do
q := q^.next;
Result := q;
end;

while (q <> nil) and (NewWord <> q^.word) do
q := q^.next;

Куда вставить новое слово?

function FindPlace(Head: PNode; NewWord: string): PNode;
var q: PNode;
begin
q := Head;
while (q <> nil) and (NewWord > q^.word) do
q := q^.next;
Result := q;
end;

>

Удаление узла

procedure DeleteNode ( var Head: PNode; p: PNode );
var q: PNode;
begin
if Head = p then
Head := p^.next
else begin
q := Head;
while (q <> nil) and (q^.next <> p) do
q := q^.next;
if q <> nil then q^.next := p^.next;
end;
Dispose(p);
end;

while (q <> nil) and (q^.next <> p) do
q := q^.next;

if Head = p then
Head := p^.next

Dispose(p);

Алфавитно-частотный словарь

var F: Text;
...
Assign(F, 'input.dat');
Reset ( F );

Close ( F );

Как прочитать одно слово из файла?

function GetWord ( F: Text ) : string;
var c: char;
begin
Result := ''; { пустая строка }
c := ' '; { пробел – чтобы войти в цикл }
{ пропускаем спецсимволы и пробелы }
while not eof(f) and (c <= ' ') do
read(F, c);
{ читаем слово }
while not eof(f) and (c > ' ') do begin
Result := Result + c;
read(F, c);
end;
end;

Полная программа

type PNode = ^Node;
Node = record ... end; { новые типы данных }
var Head: PNode; { адрес головы списка }
NewNode, q: PNode; { вспомогательные указатели }
w: string; { слово из файла }
F: text; { файловая переменная }
count: integer; { счетчик разных слов }
{ процедуры и функции }
begin
Head := nil;
Assign ( F, 'input.txt' );
Reset ( F );
{ читаем слова из файла, строим список }
Close ( F );
{ выводим список в другой файл }
end.

Полная программа (II)

{ читаем слова из файла, строим список }
while True do begin { бесконечный цикл }
w := GetWord ( F ); { читаем слово }
if w = '' then break; { слова закончились, выход }
q := Find ( Head, w ); { ищем слово в списке }
if q <> nil then { нашли, увеличить счетчик }
q^.count := q^.count + 1
else begin { не нашли, добавить в список }
NewNode := CreateNode ( w );
q := FindPlace ( Head, w );
AddBefore ( Head, q, NewNode );
end;
end;

Полная программа (III)

{ выводим список в другой файл }
q := Head; { проход с начала списка }
count := 0; { обнулили счетчик слов }
Assign(F, 'output.txt');
Rewrite(F);
while q <> nil do begin { пока не конец списка }
count := count + 1; { еще одно слово }
writeln ( F, q^.word, ': ', q^.count );
q := q^.next; { перейти к следующему }
end;
writeln ( F, 'Найдено ',
count, ' разных слов.' );
Close(F);

type PNode = ^Node; { указатель на узел }
Node = record { структура узла }
word: string[40]; { слово }
count: integer; { счетчик повторений }
next: PNode; { ссылка на следующий }
prev: PNode; { ссылка на предыдущий }
end;

Двусвязные списки

Структура узла:

Адреса «головы» и «хвоста»:

var Head, Tail: PNode;
...
Head := nil; Tail := nil;

Задания

«4»: «Собрать» из этих функций программу для построения алфавитно-частотного словаря. В конце файла вывести общее количество разных слов (количество элементов списка).
«5»: То же самое, но использовать двусвязные списки.
«6»: То же самое, что и на «5», но вывести список слов в порядке убывания частоты, то есть, сначала те слова, которые встречаются чаще всего.

Тема 5. Стеки, очереди, деки

Динамические структуры данных(язык Паскаль)

Стек

Пример задачи

Решение задачи со скобками

[ ( ( ) ) ] { }

Реализация стека (массив)

Структура-стек:

const MAXSIZE = 100;
type Stack = record { стек на 100 символов }
data: array[1..MAXSIZE] of char;
size: integer; { число элементов }
end;

Добавление элемента:

procedure Push( var S: Stack; x: char);
begin
if S.size = MAXSIZE then Exit;
S.size := S.size + 1;
S.data[S.size] := x;
end;

Реализация стека (массив)

function Pop ( var S:Stack ): char;
begin
if S.size = 0 then begin
Result := char(255);
Exit;
end;
Result := S.data[S.size];
S.size := S.size - 1;
end;

Снятие элемента с вершины:

Пустой или нет?

function isEmpty ( S: Stack ): Boolean;
begin
Result := (S.size = 0);
end;

Программа

var br1, br2, expr: string;
i, k: integer;
upper: char; { то, что сняли со стека }
error: Boolean; { признак ошибки }
S: Stack;
begin
br1 := '([{'; br2 := ')]}';
S.size := 0;
error := False;
writeln('Введите выражение со скобками');
readln(expr);
... { здесь будет основной цикл обработки }
if not error and isEmpty(S) then
writeln('Выражение правильное.')
else writeln('Выражение неправильное.')
end.

Обработка строки (основной цикл)

for i:=1 to length(expr)
do begin
for k:=1 to 3 do begin
if expr[i] = br1[k] then begin { откр. скобка }
Push(S, expr[i]); { втолкнуть в стек}
break;
end;
if expr[i] = br2[k] then begin { закр. скобка }
upper := Pop(S); { снять символ со стека }
error := upper <> br1[k];
break;
end;
end;
if error then break;
end;

Реализация стека (список)

Добавление элемента:

Структура узла:

type PNode = ^Node; { указатель на узел }
Node = record
data: char; { данные }
next: PNode; { указатель на след. элемент }
end;

procedure Push( var Head: PNode; x: char);
var NewNode: PNode;
begin
New(NewNode); { выделить память }
NewNode^.data := x; { записать символ }
NewNode^.next := Head; { сделать первым узлом }
Head := NewNode;
end;

Реализация стека (список)

Снятие элемента с вершины:

function Pop ( var Head: PNode ): char;
var q: PNode;
begin
if Head = nil then begin { стек пуст }
Result := char(255); { неиспользуемый символ }
Exit;
end;
Result := Head^.data; { взять верхний символ }
q := Head; { запомнить вершину }
Head := Head^.next; { удалить вершину из стека }
Dispose(q); { удалить из памяти }
end;

q := Head;
Head := Head^.next;
Dispose(q);

Реализация стека (список)

Изменения в основной программе:

var S: Stack;
...
S.size := 0;

var S: PNode;

S := nil;

Пустой или нет?

function isEmpty ( S: Stack ): Boolean;
begin
Result := (S = nil);
end;

Вычисление арифметических выражений

a b + c d + 1 - /

Как вычислять автоматически:

(a + b) / (c + d – 1)

/ + a b - + c d 1

a + b

a + b

c + d

c + d

c + d - 1

c + d - 1

Запишите в постфиксной форме

(32*6-5)*(2*3+4)/(3+7*2)

(2*4+3*5)*(2*3+18/3*2)*(12-3)

(4-2*3)*(3-12/3/4)*(24-3*12)

Вычисление выражений

Постфиксная форма:

a b + c d + 1 - /

X =

Системный стек (Windows – 1 Мб)

Очередь

Реализация очереди (массив)

Реализация очереди (кольцевой массив)

Реализация очереди (кольцевой массив)

В очереди 1 элемент:

Очередь пуста:

Очередь полна:

Head = Tail + 1

Head = Tail + 2

Head = Tail

Реализация очереди (кольцевой массив)

type Queue = record
data: array[1..MAXSIZE] of integer;
head, tail: integer;
end;

Структура данных:

Добавление в очередь:

procedure PushTail( var Q: Queue; x: integer);
begin
if Q.head = (Q.tail+1) mod MAXSIZE + 1  then Exit; { очередь полна, не добавить }
Q.tail := Q.tail mod MAXSIZE + 1;
Q.data[Q.tail] := x;
end;

mod MAXSIZE

Реализация очереди (кольцевой массив)

Выборка из очереди:

function Pop ( var S: Queue ): integer;
begin
if Q.head = Q.tail mod MAXSIZE + 1 then begin
Result := MaxInt;
Exit;
end;
Result := Q.data[Q.head];
Q.head := Q.head mod MAXSIZE + 1;
end;

Реализация очереди (списки)

type PNode = ^Node;
Node = record
data: integer;
next: PNode;
end;

type Queue = record
head, tail: PNode;
end;

Структура узла:

Тип данных «очередь»:

Реализация очереди (списки)

procedure PushTail( var Q: Queue; x: integer );
var NewNode: PNode;
begin
New(NewNode);
NewNode^.data := x;
NewNode^.next := nil;
if Q.tail <> nil then
Q.tail^.next := NewNode;
Q.tail := NewNode; { новый узел – в конец}
if Q.head = nil then Q.head := Q.tail;
end;

Добавление элемента:

Реализация очереди (списки)

function Pop ( var S: Queue ): integer;
var top: PNode;
begin
if Q.head = nil then begin
Result := MaxInt;
Exit;
end;
top := Q.head;
Result := top^.data;
Q.head := top^.next;
if Q.head = nil then Q.tail := nil;
Dispose(top);
end;

Выборка элемента:

Дек

Задания

«4»: В файле input.dat находится список чисел (или слов). Переписать его в файл output.dat в обратном порядке.
«5»: Составить программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме, с помощью стека. Выражение правильное, допускаются только однозначные числа и знаки +, -, *, /.
«6»: То же самое, что и на «5», но допускаются многозначные числа.

Тема 6. Деревья

Динамические структуры данных(язык Паскаль)

Деревья

Деревья

Какие структуры – не деревья?

Деревья

Дерево – рекурсивная структура данных

Двоичные деревья

Структура узла:

type PNode = ^Node; { указатель на узел }
Node = record
data: integer; { полезные данные }
left, right: PNode; { ссылки на левого и  правого сыновей }
end;

Двоичные деревья поиска

Двоичные деревья поиска

Поиск в массиве (N элементов):

Поиск по дереву (N элементов):

Реализация алгоритма поиска

{ Функция Search – поиск по дереву
Вход: Tree - адрес корня,
x - что ищем
Выход: адрес узла или nil (не нашли) }
function Search(Tree: PNode; x: integer): PNode;
begin
if Tree = nil then begin
Result := nil;
Exit;
end;
if x = Tree^.data then
Result := Tree
else
if x < Tree^.data then
Result := Search(Tree^.left, x)
else Result := Search(Tree^.right, x);
end;

Как построить дерево поиска?

{ Процедура AddToTree – добавить элемент
Вход: Tree - адрес корня,
x - что добавляем }
procedure AddToTree( var Tree: PNode; x: integer );
begin
if Tree = nil then begin
New(Tree);
Tree^.data := x;
Tree^.left := nil;
Tree^.right := nil;
Exit;
end;
if x < Tree^.data then
AddToTree(Tree^.left, x)
else AddToTree(Tree^.right, x);
end;

Обход дерева

Обход ЛКП («левый – корень – правый»):

125

98

76

45

59

30

16

Обход ПКЛ («правый – корень – левый»):

Обход КЛП («корень – левый – правый»):

Обход ЛПК («левый – правый – корень»):

Обход дерева – реализация

{ Процедура LKP – обход дерева в порядке ЛКП
(левый – корень – правый)
Вход: Tree - адрес корня }
procedure LKP(Tree: PNode);
begin
if Tree = nil then Exit;
LKP(Tree^.left);
write(' ', Tree^.data);
LKP(Tree^.right);
end;

Разбор арифметических выражений

a b + c d + 1 - /

Как вычислять автоматически:

(a + b) / (c + d – 1)

a + b / c + d – 1

/ + a b - + c d 1

Вычисление выражений

Постфиксная форма:

a b + c d + 1 - /

X =

Вычисление выражений

Построение дерева

first

last

k

k+1

k-1

Как найти последнюю операцию?

Приоритет операции

{ Функция Priority – приоритет операции
Вход: символ операции
Выход: приоритет или 100, если не операция }
function Priority ( c: char ): integer;
begin
case ( c ) of
'+', '-': Result := 1;
'*', '/': Result := 2;
else Result := 100;
end;
end;

Номер последней операции

{ Функция LastOperation – номер последней операции
Вход: строка, номера первого и последнего символов рассматриваемой части
Выход: номер символа - последней операции }
function LastOperation ( Expr: string;
first, last: integer): integer;
var MinPrt, i, k, prt: integer;
begin
MinPrt := 100;
for i:=first to last do begin
prt := Priority ( Expr[i] );
if prt <= MinPrt then begin
MinPrt := prt;
k := i;
end;
end;
Result := k;
end;

Построение дерева

Структура узла

type PNode = ^Node;
Node = record
data: char;
left, right: PNode;
end;

Создание узла для числа (без потомков)

function NumberNode(c: char): PNode;
begin
New(Result);
Result^.data := c;
Result^.left := nil;
Result^.right := nil;
end;

Построение дерева

{ Функция MakeTree – построение дерева
Вход: строка, номера первого и последнего символов рассматриваемой части
Выход: адрес построенного дерева }
function MakeTree ( Expr: string;
first, last: integer): PNode;
var k: integer;
begin
if first = last then begin
Result := NumberNode ( Expr[first] );
Exit;
end;
k := LastOperation ( Expr, first, last );
New(Result);
Result^.data := Expr[k];
Result^.left := MakeTree ( Expr, first, k-1 );
Result^.right := MakeTree ( Expr, k+1, last );
end;

Вычисление выражения по дереву

{ Функция CalcTree – вычисление по дереву
Вход: адрес дерева
Выход: значение выражения }
function CalcTree(Tree: PNode): integer;
var num1, num2: integer;
begin
if Tree^.left = nil then begin
Result := Ord(Tree^.data) - Ord('0');
Exit;
end;
num1 := CalcTree(Tree^.left);
num2 := CalcTree(Tree^.right);
case Tree^.data of
'+': Result := num1+num2;
'-': Result := num1-num2;
'*': Result := num1*num2;
'/': Result := num1 div num2;
else Result := MaxInt;
end;
end;

Основная программа

{ Ввод и вычисление выражения с помощью дерева }
program qq;
var Tree: PNode;
Expr: string;
{ процедуры и функции }
begin
write('Введите выражение > ');
readln( Expr );
Tree := MakeTree( Expr, 1, Length(Expr) );
writeln(' = ', CalcTree(Tree) );
end.

Дерево игры

Дерево игры

3, 2

игрок 1

3, 6

27, 2

3, 18

3, 3

4, 2

12, 2

4, 6

5, 2

4, 3

9, 3

4, 3

36, 2

4, 18

15, 2

27, 3

игрок 1

игрок 2

игрок 2

9, 2

4, 3

4, 3

Задания

«4»: «Собрать» программу для вычисления правильного арифметического выражения, включающего только однозначные числа и знаки операций +, -, * , /.
«5»: То же самое, но допускаются также многозначные числа и скобки.
«6»: То же самое, что и на «5», но с обработкой ошибок (должно выводиться сообщение).

Тема 7. Графы

Динамические структуры данных(язык Паскаль)

Определения

Определения

Описание графа

Список смежности

Матрица и список смежности

Построения графа по матрице смежности

Как обнаружить цепи и циклы?

M =

Как обнаружить цепи и циклы?

M2 = M  M

Логическое умножение матрицы на себя:

M2 =



=

M2[3][1] = 0·0 + 1·1 + 0·0 + 1·1 = 1

Как обнаружить цепи и циклы?

M3 = M2  M

Матрица путей длины 3:

M3 =



=

M4 =



=

Весовая матрица

Задача Прима-Краскала

Жадный алгоритм

Реализация алгоритма Прима-Краскала

3

2

4

5

4

Реализация алгоритма Прима-Краскала

Структура «ребро»:

type rebro = record
i, j: integer; { номера вершин }
end;

const N = 5;
var W: array[1..N,1..N] of integer;
Color: array[1..N] of integer;
i, j, k, min, col_i, col_j: integer;
Reb: array[1..N-1] of rebro;
begin
... { здесь надо ввести матрицу W }
for i:=1 to N do { раскрасить в разные цвета }
Color[i] := i;
... { основной алгоритм – заполнение массива Reb }
... { вывести найденные ребра (массив Reb)}
end.

Основная программа:

Реализация алгоритма Прима-Краскала

for k:=1 to N-1 do begin
min := MaxInt;
for i:=1 to N do
for j:=i+1 to N do
if (Color[i] <> Color[j]) and
(W[i,j] < min) then begin
min := W[i,j];
Reb[k].i := i;
Reb[k].j := j;
col_i := Color[i];
col_j := Color[j];
end;
for i:=1 to N do
if Color[i] = col_j then
Color[i] := col_i;
end;

Основной алгоритм:

Сложность алгоритма

Основной цикл:

O(N3)

for k:=1 to N-1 do begin
...
for i:=1 to N do
for j:=i+1 to N do
...
end;

Требуемая память:

var W: array[1..N,1..N] of integer;
Color: array[1..N] of integer;
Reb: array[1..N-1] of rebro;

O(N2)

Количество операций:

Кратчайшие пути (алгоритм Дейкстры)

Алгоритм Дейкстры (E.W. Dijkstra, 1959)

Алгоритм Дейкстры

Реализация алгоритма Дейкстры

Реализация алгоритма Дейкстры

Шаг 1:

Реализация алгоритма Дейкстры

Шаг 2:

Шаг 3:

Как вывести маршрут?

Результат работа алгоритма Дейкстры:

Маршрут из вершины 0 в вершину 4:

4

5

2

0

Сложность алгоритма Дейкстры:

O(N2)

Алгоритм Флойда-Уоршелла

for k: =1 to N
for i: = 1 to N
for j: = 1 to N
if W[i,j] > W[i,k] + W[k,j] then
W[i,j] := W[i,k] + W[k,j];

Алгоритм Флойда-Уоршелла

Версия с запоминанием маршрута:

for i:= 1 to N
for j := 1 to N
c[i,j] := i;
...
for k: =1 to N
for i: = 1 to N
for j: = 1 to N
if W[i,j] > W[i,k] + W[k,j] then begin
W[i,j] := W[i,k] + W[k,j];
c[i,j] := c[k,j];
end;

c[i,j] := c[k,j];

O(N3)

Задача коммивояжера

O(N!)

Другие классические задачи