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

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

int x, y = 20;
float z, A[10];
char str[80];

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

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





Как записать адрес:
char *pC;

int m = 5, *pI;
int A[2] = { 3, 4 };
pI = & m; // адрес переменной m
pI = & A[1]; // адрес элемента массива A[1]
pI = NULL; // нулевой адрес

&

scanf("%d", &m);

Как работать с массивами?
int m = 4, n, *pI;
pI

int *pI, i, A[] = {1, 2, 3, 4, 5, 999};
pI = A; // адрес A[0] записывается как A
while ( *pI != 999 ) { // while( A[i] != 999 )
*pI += 2; // A[i] += 2;
pI++; // i++ (переход к следующему)
}

*

%p

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

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

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

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

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

printf ("Введите размер массива > ");
scanf ("%d", &N);
A

delete A;

A = new int [N];

выделить память (С++)

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

for (i = 0; i < N; i ++ ) {
printf ("\nA[%d] = ", i+1);
scanf ("%d", &A[i]);
}

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

if ( A == NULL ) {
printf("Не удалось выделить память");
return;
}

проверка

и calloc;
в языке C++ удобнее использовать оператор new;

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

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

массив строк
адрес матрицы = адрес массива, где хранятся адреса строк
адрес

int **A;

typedef int *pInt;
pInt *A;

или через объявление нового типа данных
pInt = указатель на int

Объявление динамической матрицы:

A[M][0] ... A[M][N]

A[0][0] ... A[0][N]

int M, N, i;
pInt *A;
...
A =

A = new pInt[M];

for ( i = 0; i < M; i ++ )
A[i] = new int[N];

for ( i = 0; i < M; i ++ )
delete A[i];

delete A;

// ввод M и N

// работаем с матрицей A, как обычно

выделяем массив указателей

выделяем массив под каждую строку

освобождаем память для строк

освобождаем массив адресов строк

... A[M]
A[0][0] … A[1][0] … A[2][0]

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

A = new pInt[M];
A[0] = new int [M*N];

delete A[0];
delete A;

Расстановка указателей:

for ( i = 1; i < N; i ++ ) A[i] = A[i-1] + N;

несколько полей – элементов разных типов (в том числе и

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

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

struct Book {
char author[40]; // автор, символьная строка
char title[80]; // название, символьная строка
int year; // год издания, целое число
int pages; // количество страниц, целое число
};

Как ввести новый тип данных-структур?

структура

название

поля

= { "А.С. Пушкин",

Заполнение полей:

strcpy ( b.author, "А.С. Пушкин" );
strcpy ( b.title, "Полтава" );
b.year = 1998;
b.pages = 223;

Ввод полей с клавиатуры:

printf ( "Автор " );
gets ( b.author );
printf ( "Название книги " );
gets ( b.title );
printf ( "Год издания, кол-во страниц " );
scanf ( "%d%d", &b.year, &b.pages );

b1
strcpy ( b2.author, b1.author );
strcpy ( b2.title, b1.title );
b2.year =

Задача: скопировать структуру b1 в b2.

Копирование «бит в бит»:

#include
...

memcpy ( &b2, &b1, sizeof(Book) );

или просто так:

b2 = b1;

куда

откуда

сколько байт

i < 10; i ++ )
B[i].year = 2008;

B[0] ... B[9]

Запись в двоичный файл:

Чтение из двоичного файла:

FILE *f;
f = fopen("input.dat", "wb" );


fwrite ( B, sizeof(Book), 10, f );

f = fopen("input.dat", "rb" );
n = fread ( B, sizeof(Book), 10, f );
printf ( "Прочитано %d структур", n );

адрес массива

размер блока

сколько блоков

указатель на файл

Book

write binary

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

#include
struct Book { … };
void main()
{
Book B[100];
int i, n;
FILE *f;
f = fopen ( "books.dat", "rb" );
n = fread ( B, sizeof(Book), 100, f );
fclose(f);
for ( i = 0; i < n; i ++ ) B[i].year = 2008;
fp = fopen("books.dat", "wb" );
fwrite ( B, sizeof(Book), n, f );
fclose ( f );
}

struct Book { … };

f = fopen ( "books.dat", "rb" );
n = fread ( B, sizeof(Book), 100, f );
fclose ( f );

fp = fopen("books.dat", "wb" );
fwrite ( B, sizeof(Book), n, f );
fclose ( f );

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

чтение массива (≤ 100 структур), размер записывается в переменную n

запись массива (n структур)

" );
gets ( p->author );
printf ( "Название книги "

p = new Book;

выделить память под структуру, записать ее адрес в переменную p

p->author

delete p;

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

у вас книг? " );
scanf ( "%d", &n );

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

B = new Book[n];

Book *B;

delete B;

в этот указатель будет записан адрес массива

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

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

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

p[0]

p[1]

p[2]

p[3]

p[4]

p[4]

p[0]

p[2]

p[1]

p[3]

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

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

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

for ( i = 0; i < 5; i ++ )
printf("%d %s", p[i]->year, p[i]->title);

p[i]

p[i]

j;
... // здесь заполняем структуры
for ( i = 0; i

Book *p[N], *temp;

for ( i = 0; i < N; i++ )
p[i] = &B[i];

for ( i = 0; i < n-1; i++ )
for ( j = n-2; j >= i; j-- )
if ( p[j+1]->year < p[j]->year ) {
temp = p[j];
p[j] = p[j+1];
p[j+1] = temp;
}

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

начальная расстановка указателей

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

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

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

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

struct Node {
char word[40]; // слово
int count; // счетчик повторений
Node *next; // ссылка на следующий элемент
};

typedef Node *PNode;

Указатель на эту структуру:

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

PNode Head = NULL;

списка;
в конец списка;
после заданного узла;
до заданного узла.
Искать нужный узел в

new Node;
strcpy(NewNode->word, NewWord);
NewNode->count = 1;
NewNode->next = NULL;

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

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

новое слово

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

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

void AddFirst (PNode & Head, PNode NewNode)
{
NewNode->next = Head;
Head = NewNode;
}

&

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

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

p->next = NewNode;

void AddAfter (PNode p, PNode NewNode)
{
NewNode->next = p->next;
p->next = NewNode;
}

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

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

...
PNode q = Head; // начали с головы
while ( q != NULL ) { // пока не дошли до конца
... // делаем что-то хорошее с q
q = q->next; // переходим к следующему узлу
}
...

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

void AddLast ( PNode &Head, PNode NewNode )
{
PNode q = Head;
if ( Head == NULL ) {
AddFirst( Head, NewNode );
return;
}
while ( q->next ) q = q->next;
AddAfter ( q, NewNode );
}

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

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

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

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

void AddBefore ( PNode & Head, PNode p, PNode NewNode )
{
PNode q = Head;
if ( Head == p ) {
AddFirst ( Head, NewNode );
return;
}
while ( q && q->next != p ) q = q->next;
if ( q ) AddAfter(q, NewNode);
}

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

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

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

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




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

void AddBefore2 ( PNode p, PNode NewNode )
{
Node temp;
temp = *p; *p = *NewNode;
*NewNode = temp;
p->next = NewNode;
}

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

PNode Find ( PNode Head, char NewWord[] )
{
PNode q = Head;
while (q && strcmp(q->word, NewWord))
q = q->next;
return q;
}

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

результат – адрес узла

while ( q && strcmp ( q->word, NewWord) )
q = q->next;

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

заданное слово, так чтобы в списке сохранился алфавитный порядок слов.

PNode FindPlace ( PNode Head, char NewWord[] )
{
PNode q = Head;
while ( q && strcmp(NewWord, q->word) > 0 )
q = q->next;
return q;
}

> 0

слово NewWord стоит по алфавиту до q->word

= Head;
if ( Head == p )
Head

while ( q && q->next != p )
q = q->next;

if ( Head == p )
Head = p->next;

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

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

ищем предыдущий узел, такой что q->next == p

delete p;

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

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

char word[80];
...
n = fscanf ( in, "%s", word );

FILE *in;
in = fopen ( "input.dat", "r" );

read, чтение

вводится только одно слово (до пробела)!

count; // счетчик повторений
Node *next;

typedef Node *PNode;

Указатель на эту структуру:

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

PNode Head = NULL;
PNode Tail = NULL;

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

Си)

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

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

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

[ ( ( ) ) ] { }

data[MAXSIZE]; // стек на 100 символов
int size;

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

int Push ( Stack &S, char x )
{
if ( S.size == MAXSIZE ) return 0;
S.data[S.size] = x;
S.size ++;
return 1;
}

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

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

нет ошибки

== 0 ) return char(255);
S.size --;
return S.data[S.size];
}
Снятие элемента с вершины:
Пусто й

int isEmpty ( Stack &S )
{
if ( S.size == 0 )
return 1;
else return 0;
}

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

int isEmpty ( Stack &S )
{
return (S.size == 0);
}

char br2[3] = { ')', ']', '}' };
char s[80],

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

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

то, что сняли со стека

признак ошибки

strlen(s); i++ )
{
for ( k = 0;

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

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

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

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

Node *next;
};
typedef Node *PNode;
void Push (PNode &Head,

char x;
PNode q = Head;
if ( Head

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

Stack S;
S.size = 0;
...
if ( ! error && (S.size == 0) )
printf("\nВыpажение пpавильное\n");
else printf("\nВыpажение непpавильное \n");

PNode S = NULL;

(S == NULL)

стек пуст

/
Как вычислять автоматически:
Инфиксная запись
(знак операции между операндами)
(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

int data[MAXSIZE];
int head, tail;
};
Структура данных:
Добавление в

int PushTail ( Queue &Q, int x )
{
if ( Q.head == (Q.tail+2) % MAXSIZE ) return 0;
Q.tail = (Q.tail + 1) % MAXSIZE;
Q.data[Q.tail] = x;
return 1;
}

замкнуть в кольцо

% MAXSIZE

очередь полна, не добавить

удачно добавили

)
{
int temp;
if ( Q.head == (Q.tail

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

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

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

*next;
};
typedef Node *PNode;
struct Queue {
PNode Head,

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

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

PNode NewNode;
NewNode = new Node;
NewNode->data

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

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

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

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

top = Q.Head;
int x;
if ( top

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

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

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

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

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

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

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

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

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

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

корень

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

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

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

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

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

// полезные данные
Node *left, *right; // ссылки на

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

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

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

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

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

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

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

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

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

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

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

дереву
// Вход: Tree - адрес корня,
//

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

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

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

порядке.
Обход ЛКП («левый – корень – правый»):
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, если не операция
//--------------------------------------------
int Priority ( char

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

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

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

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

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

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

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

};
typedef Node *PNode;
Создание узла для числа (без потомков)
PNode NumberNode (

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

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

первого и последнего // символов рассматриваемой части
// Выход:

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

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

Вход: адрес дерева
// Выход: значение выражения
//--------------------------------------------
int CalcTree (PNode Tree)
{
int

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

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

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

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

дерева
//--------------------------------------------
void main()
{
char s[80];
PNode Tree;
printf ( "Введите выражение

первой из которых 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][0]=1 и M[0][j]=1

или

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

или

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

строка i

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

столбец j

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

M =

или

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

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

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

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

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

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

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

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

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

2

1

3

4

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

3

// номера вершин
};
const N = 5;
void main()
{
int W[N][N], Color[N],

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

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

цвета вершин

k ++ ) {
min = 30000; // большое число

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

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

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

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

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

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

k ++ ) {
...
for ( i =

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

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

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

int W[N][N], Color[N];
rebro Reb[N-1];

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 = 0; k < N; k ++ )
for ( i = 0; i < N; i ++ )
for ( j = 0; j < N; j ++ )
if ( W[i][j] > W[i][k] + W[k][j] )
W[i][j] = W[i][k] + W[k][j];

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

< N; i ++ )
for ( j = 0;

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). Надо разместить