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

обращаться
размер заранее известен (задается при написании программы)
память выделяется при

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

во время работы программы
нет имени?
Проблема:
как обращаться

переменной (или блока памяти).
Объявление:



Как записать адрес:
var pC:

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

@

^

nil

указатель

адрес ячейки

pI: ^integer;
begin
m := 4;
pI := @m;
writeln('Адрес m

^

«вытащить» значение по адресу

of integer;
pI: ^integer;
begin
for i:=1 to 4 do

переместиться к следующему элементу = изменить адрес на sizeof(integer)

можно хранить адрес другой переменной;
при объявлении указателя надо указать тип

массива. Отсортировать массив и вывести на экран.
Проблема:
размер массива заранее

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

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

^intArray;
i, N: integer;
begin
writeln('Размер массива>');
readln(N);
GetMem(pointer(A), N*sizeof(integer));

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

освободить память

работаем так же, как с обычным массивом!

какой-то массив целых чисел

размер в байтах );
указатель должен быть приведен к типу pointer

была выделена, а массив используется.
Что делать: так не делать.
Выход за

integer;
begin
writeln('Размер массива>');
readln(N);
SetLength ( A, N );
for

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

освободить память

какой-то массив целых чисел

нумерация с НУЛЯ!

не выделяется:
var A: array of integer;
для выделения памяти

место в памяти во время работы программы.
Проблема:
размеры матрицы заранее

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

который может включать в себя несколько полей – элементов разных

Свойства:
автор (строка)
название (строка)
год издания (целое число)
количество страниц (целое число)

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

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

присваивание
if Book.pages > 200 then // сравнение
writeln(Book.author,

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

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

название

запись

поля

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

record
author: string[40];
title: string[80];

Books[1] ... Books[10]

...
end;
for i:=1 to N do
if aBooks[i].pages > 200

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

// одна запись
aBooks: array[1..N] of TBook; // массив
Объявление

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

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

TBook – Type Book («тип книга») – удобно!

);
Book.year := 1800;
writeln( IsOld(Book) );
Процедура:
procedure ShowAuthor ( b: TBook );
begin

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

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

Функция:

{ связать с указателем }
Rewrite(F); { открыть

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

}
Reset(F); { открыть для чтения }
Read(F, Book);

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

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

пока не дошли до конца файла F
EOF = end of file

виде массива структур типа TBook (не более 100). Установить для

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 … ;

полное описание структуры

0;
while not eof(F) and (N < MAX) do begin

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

Сохранение:

чтобы не выйти за пределы массива

Пушкин';
pB^.title := 'Полтава';
pB^.year := 1990;
pB^.pages := 129;

New(pB);

выделить память под запись, записать адрес в pB

pB^

Dispose(pB);

освободить память

pB: ^TBook;

переменная-указатель на TBook

комбинация полей), по которому выполняется сортировка.
const N = 100;
var aBooks:

downto i do
if aBooks[j].year > aBooks[j+1].year

вспомогательный массив указателей, при сортировке переставлять указатели.
До
сортировки:
После
сортировки:
Вывод результата:
for i:=1

p[i]^

p[i]^

}
var p: array[1..N] of PBook;
begin
{ заполнение массива

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;

вспомогательные указатели

меняем только указатели, записи остаются на местах

начальная расстановка

узел:
Типы структур:
списки
деревья
графы
односвязный
двунаправленный (двусвязный)
циклические списки (кольца)

Нужно записать в другой файл в столбик все

узел (голова) и связанный с ним список.
Списки: новые типы данных
type

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

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

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

начало списка;
б) в конец списка;
в) после заданного узла;
г) до заданного

NewWord;
NewNode^.count := 1;
NewNode^.next := nil;
Result := NewNode;
end;
Функция

возвращает адрес созданного узла

новое слово

голову списка:
NewNode^.next := Head;

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

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

var

адрес головы меняется

следующий за p:
NewNode^.next = p^.next;
2) Установить ссылку узла p на

p^.next = NewNode;

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

указатель q на голову списка;
если указатель q равен nil (дошли

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

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

списка.
Алгоритм:
найти последний узел q, такой что q^.next равен nil;
добавить

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;

особый случай – добавление в пустой список

ищем последний узел

добавить узел после узла q

назад нельзя!
Решение: найти предыдущий узел q (проход с начала списка).
Добавление

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;

в начало списка

ищем узел, следующий за которым – узел p

добавить узел после узла q

поиска предыдущего.
Алгоритм:
поменять местами данные нового узла и узла p;




установить ссылку

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

определить, что его нет.
Функция Find:
вход: слово (символьная строка);
выход: адрес

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;

ищем это слово

результат – адрес узла или nil (нет такого)

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;

>

слово NewWord стоит по алфавиту перед q^.word

q: PNode;
begin
if Head = p then
Head :=

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

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

Проблема: нужно знать адрес предыдущего узла q.

особый случай: удаляем первый узел

ищем узел, такой что q^.next = p

Dispose(p);

освобождение памяти

то перейти к шагу 7;
если слово найдено, увеличить счетчик (поле

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

Close ( F );

) : string;
var c: char;
begin
Result := ''; { пустая

Алгоритм:
пропускаем все спецсимволы и пробелы (с кодами <= 32)
читаем все символы до первого пробела или спецсимвола

... end; { новые типы данных }
var Head: PNode;

True do begin { бесконечный цикл }
w

Head; { проход с начала списка }
count

Node = record { структура

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

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

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

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

В конце файла вывести общее количество разных слов (количество элементов

Паскаль)

удаление элементов возможно только с одного конца (вершины стека). Stack

скобками трех типов: [], {} и (). Определить, верно ли

символы строки по порядку;
если очередной символ – открывающая скобка, заносим

[ ( ( ) ) ] { }

стек на 100 символов }
data: array[1..MAXSIZE] of

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

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;

ошибка: переполнение стека

добавить элемент

S.size = 0 then begin
Result := char(255);

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

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

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

ошибка: стек пуст

upper: char; { то, что сняли со стека }

открывающие скобки

закрывающие скобки

begin
for k:=1 to 3 do begin

цикл по всем символам строки expr

цикл по всем видам скобок

ошибка: стек пуст или не та скобка

была ошибка: дальше нет смысла проверять

на узел }
Node = record

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

PNode ): char;
var q: PNode;
begin
if Head = nil then

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

S: PNode;

S := nil;

Пустой или нет?
function isEmpty ( S: Stack

/
Как вычислять автоматически:
Инфиксная запись
(знак операции между операндами)
(a + b) /

необходимы скобки!

Постфиксная запись (знак операции после операндов)

польская нотация,
Jan Łukasiewicz (1920)

скобки не нужны, можно однозначно вычислить!

Префиксная запись (знак операции до операндов)

/ + a b - + c d 1

обратная польская нотация,
F. L. BauerF. L. Bauer and E. W. Dijkstra

a + b

a + b

c + d

c + d

c + d - 1

c + d - 1

1 - /
Алгоритм:
взять очередной элемент;
если это

X =

адресов возврата (по которым переходит программа после выполнения функции или

Переполнение стека (stack overflow):
слишком много локальных переменных (выход – использовать динамические массивы);
очень много рекурсивных вызовов функций и процедур (выход – переделать алгоритм так, чтобы уменьшить глубину рекурсии или отказаться от нее вообще).

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

очереди нужно сдвигать все элементы.

Tail + 1


размер массива
Head = Tail + 2
Head = Tail

data: array[1..MAXSIZE] of integer;
head, tail: integer;

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

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

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

Queue ): integer;
begin
if Q.head = Q.tail mod MAXSIZE +

очередь пуста

взять первый элемент

удалить его из очереди

максимальное целое число

record
data: integer;
next:

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

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

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

NewNode: PNode;
begin
New(NewNode);
NewNode^.data := x;
NewNode^.next := nil;
if

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

создаем новый узел

если в списке уже что-то было, добавляем в конец

если в списке ничего не было, …

top: PNode;
begin
if Q.head = nil then begin
Result

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

если список пуст, …

запомнили первый элемент

если в списке ничего не осталось, …

освободить память

– это линейная структура данных, в которой добавление и удаление

Операции с деком:
добавление элемента в начало (Push);
удаление элемента с начала (Pop);
добавление элемента в конец (PushTail);
удаление элемента с конца (PopTail).

Реализация:
кольцевой массив;
двусвязный список.

его в файл output.dat в обратном порядке.
«5»: Составить программу, которая

их направленных ребер (дуг), причем в каждый узел (кроме корневого)

корень

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

по стрелкам в узел x.
Потомок узла x – это узел,

Сын узла x – это узел, в который существует дуга непосредственно из узла x.
Брат узла x (sibling) – это узел, у которого тот же родитель, что и у узла x.
Высота дерева – это наибольшее расстояние от корня до листа (количество дуг).

– это корень и несколько связанных с ним деревьев.
Двоичное (бинарное)

Пустая структура – это двоичное дерево.
Двоичное дерево – это корень и два связанных с ним двоичных дерева (левое и правое поддеревья).

указатель на узел }
Node = record

Применение:
поиск данных в специально построенных деревьях (базы данных);
сортировка данных;
вычисление арифметических выражений;
кодирование (метод Хаффмана).

ключами, а справа – с бóльшими.
Ключ – это характеристика узла,

Как искать ключ, равный x:
если дерево пустое, ключ не найден;
если ключ узла равен x, то стоп.
если ключ узла меньше x, то искать x в левом поддереве;
если ключ узла больше x, то искать x в правом поддереве.

1 элемент.
Число сравнений – N.
Поиск по дереву (N элементов):
При каждом

быстрый поиск

нужно заранее построить дерево;
желательно, чтобы дерево было минимальной высоты.

Tree - адрес корня,

дерево пустое: ключ не нашли…

нашли, возвращаем адрес корня

искать в левом поддереве

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

Tree - адрес корня,
x

дерево пустое: создаем новый узел (корень)

адрес корня может измениться

добавляем к левому или правому поддереву

порядке.
Обход ЛКП («левый – корень – правый»):
125
98
76
45
59
30
16
Обход ПКЛ («правый –

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

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

порядке ЛКП
(левый

обход этой ветки закончен

обход левого поддерева

вывод данных корня

обход правого поддерева

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

Инфиксная запись, обход ЛКП
(знак операции между операндами)
(a +

необходимы скобки!

Постфиксная запись, ЛПК (знак операции после операндов)

a + b / c + d – 1

польская нотация,
Jan Łukasiewicz (1920)

скобки не нужны, можно однозначно вычислить!

Префиксная запись, КЛП (знак операции до операндов)

/ + a b - + c d 1

обратная польская нотация,
F. L. BauerF. L. Bauer and E. W. Dijkstra

1 - /
Алгоритм:
взять очередной элемент;
если это

X =

может содержать только однозначные числа и знаки операций +-*\. Вычислить

Алгоритм:
ввести строку;
построить дерево;
вычислить выражение по дереву.

Ограничения:
ошибки не обрабатываем;
многозначные числа не разрешены;
дробные числа не разрешены;
скобки не разрешены.

новый узел и записать в него этот элемент; иначе...
среди элементов

first

last

k

k+1

k-1

(старшинство) – число, определяющее последовательность выполнения операций: раньше выполняются операции

Выход: приоритет или 100, если не операция }
function Priority (

сложение и вычитание: приоритет 1

умножение и деление: приоритет 2

это вообще не операция

строка, номера первого и последнего символов

проверяем все символы

вернуть номер символа

нашли операцию с минимальным приоритетом

record
data: char;
left,

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

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

возвращает адрес созданного узла

один символ, число

первого и последнего символов рассматриваемой части

осталось только число

новый узел: операция

Вход: адрес дерева
Выход: значение выражения

вернуть число, если это лист

вычисляем операнды (поддеревья)

выполняем операцию

некорректная операция

qq;
var Tree: PNode;
Expr: string;
{ процедуры и функции }
begin

первой из которых 3, а во второй – 2 камня.

6
5, 2
4, 3
9, 3
4, 3
36, 2
4, 18
15, 2

27, 3
игрок 1
игрок

игрок 2

9, 2

4, 3

4, 3

ключевой ход

выиграл игрок 1

однозначные числа и знаки операций +, -, * , /.
«5»:

(дуг).





Направленный граф (ориентированный, орграф) – это граф, в котором

Да, без циклов!

каждой парой вершин.
k-cвязный граф – это граф, который можно разбить

1, если существует ребро из вершины i в вершину j,

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

k из вершины i в вершину j (или цикл длиной

M2[i][j]=1, если M[i][1]=1 и M[1][j]=1

или

M[i][2]=1 и M[2][j]=1

или

M[i][3]=1 и M[3][j]=1

строка i

логическое умножение

столбец j

логическое сложение

M =

или

M[i][4]=1 и M[4][j]=1

матрицы на себя:
матрица путей длины 2
M2 =
⊗
=
M2[3][1] = 0·0 +

маршрут 3-2-1

маршрут 3-4-1

длины 3:
M3 =
⊗
=
на главной диагонали – циклы!
M4 =
⊗
=

весу ребра из вершины i в вершину j (если оно

телефонных линий была минимальная.
Та же задача: дан связный граф

каждом шаге принимается решение, лучшее в данный момент.
Шаг в

и 2) ребро не образует цикла с выбранными ребрами.
Решение:

3

2

4

5

Алгоритм:
покрасить все вершины в разные цвета;
сделать N-1 раз в цикле:
выбрать ребро (i,j) минимальной длины из всех ребер, соединяющих вершины разного цвета;
перекрасить все вершины, имеющие цвет j, в цвет i.
вывести найденные ребра.

4

i, j: integer; { номера вершин }

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.

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

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

цвета вершин

MaxInt;
for i:=1 to N do
for j:=i+1 to

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

нужно выбрать всего N-1 ребер

цикл по всем парам вершин

учитываем только пары с разным цветом вершин

запоминаем ребро и цвета вершин

перекрашиваем вершины цвета col_j

for i:=1 to N do
for j:=i+1 to N

три вложенных цикла, в каждом число шагов <=N

растет не быстрее, чем N3

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

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

O(N2)

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

которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного

Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.

присвоить всем вершинам метку ∞;
среди нерассмотренных вершин найти вершину j с наименьшей меткой;
для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние;
если остались необработанны вершины, перейти к шагу 2;
метка = минимальное расстояние.

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

рассмотрена, и a[i]=0, если нет.
массив b, такой что b[i] –

нерассмотренных вершин (a[i]=0) найти вершину j, для которой b[i] –

Шаг 1:

в вершину 4:
4


5
2
0



Сложность алгоритма Дейкстры:
O(N2)
два вложенных цикла по N шагов
Вывод

иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города

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];

Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k!

j := 1 to N
c[i,j] := i;
...
for

i–ая строка строится так же, как массив c в алгоритме Дейкстры

в конце цикла c[i,j] – предпоследняя вершина в кратчайшем маршруте из вершины i в вершину j

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

O(N3)

города и, посетив по разу в неизвестном порядке города 2,3,...N,

Точные методы:
простой перебор;
метод ветвей и границ;
метод Литтла;
…
Приближенные методы:
метод случайных перестановок (Matlab);
генетические алгоритмы;
метод муравьиных колоний;
…

большое время счета для больших N

O(N!)

не гарантируется оптимальное решение

в каждом из которых живет pi школьников (i=1,...,N). Надо разместить