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

Тема 1. Указатели
© К.Ю. Поляков, 2008
Динамические структуры данных
(язык Си)

Статические данные
переменная (массив) имеет имя, по которому к ней можно обращаться
размер заранее известен (задается при написании программы)
память выделяется при объявлении
размер нельзя увеличить во время работы программы
int x, y = 20;
float z, A[10];
char str[80];

Динамические данные
размер заранее неизвестен, определяется во время работы программы
память выделяется во время работы программы
нет имени?
Проблема:
как обращаться к данным, если нет имени?
Решение:
использовать адрес в памяти
Следующая проблема:
в каких переменных могут храниться адреса?
как работать с адресами?

Указатели
Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти).
Объявление:
Как записать адрес:
char *pC; // адрес символа
// (или элемента массива)
int *pI; // адрес целой переменной
float *pF; // адрес вещественной переменной
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 = &m;
printf ("m = %d", * pI); // вывод значения
n = 4*(7 - *pI); // n = 4*(7 - 4) = 12
*pI = 4*(n – m); // m = 4*(12 – 4) = 32
printf("&m = %p", 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
«вытащить» значение по адресу

Что надо знать об указателях
указатель – это переменная, в которой можно хранить адрес другой переменной;
при объявлении указателя надо указать тип переменных, на которых он будет указывать, а перед именем поставить знак *;
знак & перед именем переменной обозначает ее адрес;
знак * перед указателем в рабочей части программы (не в объявлении) обозначает значение ячейки, на которую указывает указатель;
для обозначения недействительного указателя используется константа NULL (нулевой указатель);
при изменении значения указателя на n он в самом деле сдвигается к n-ому следующему числу данного типа, то есть для указателей на целые числа на n*sizeof(integer) байт;
указатели печатаются по формату %p.

Тема 2. Динамические массивы
© К.Ю. Поляков, 2008
Динамические структуры данных
(язык Си)

Где нужны динамические массивы?
Задача. Ввести размер массива, затем – элементы массива. Отсортировать массив и вывести на экран.
Проблема:
размер массива заранее неизвестен.
Пути решения:
выделить память «с запасом»;
выделять память тогда, когда размер стал известен.
Алгоритм:
ввести размер массива;
выделить память ;
ввести элементы массива;
отсортировать и вывести на экран;
удалить массив.
выделить память
удалить массив

Программа
#include
void main()
{
int *A, N;
printf ("Введите размер массива > ");
scanf ("%d", &N);
A = new int [N];
if ( A == NULL ) {
printf("Не удалось выделить память");
return;
}
for (i = 0; i < N; i ++ ) {
printf ("\nA[%d] = ", i+1);
scanf ("%d", &A[i]);
}
...
delete pI;
}
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;
}
проверка

Динамические массивы
для выделения памяти в языке Си используются функции malloc и calloc;
в языке C++ удобнее использовать оператор new;
указатель = new тип [размер];
результат работы оператора new – адрес выделенного блока памяти, который нужно сохранить в указателе;
если оператор new вернул нулевой указатель (NULL), память выделить не удалось;
с динамическим массивом можно работать так же, как и с обычным (статическим);
для освобождения блока памяти нужно применить оператор delete:
delete указатель;

Ошибки при работе с памятью
Запись в «чужую» область памяти:
память не была выделена, а массив используется.
Что делать: проверять указатель на NULL.
Выход за границы массива:
обращение к элементу массива с неправильным номером, при
записи портятся данные в «чужой» памяти.
Что делать: если позволяет транслятор, включать проверку выхода за границы массива.
Указатель удален второй раз:
структура памяти нарушена, может быть все, что угодно.
Что делать: в удаленный указатель лучше записывать NULL, ошибка выявится быстрее.
Утечка памяти:
ненужная память не освобождается.
Что делать: убирайте «мусор».

Динамические матрицы
Задача. Ввести размеры матрицы и выделить для нее место в памяти во время работы программы.
Проблема:
размеры матрицы заранее неизвестны.
Пути решения:
выделять отдельный блок памяти для каждой строки;
выделить память сразу на всю матрицу.

Вариант 1. Свой блок – каждой строке
Адрес матрицы:
матрица = массив строк
адрес матрицы = адрес массива, где хранятся адреса строк
адрес строки = указатель
адрес матрицы = адрес массива указателей
int **A;
typedef int *pInt;
pInt *A;
или через объявление нового типа данных
pInt = указатель на int
Объявление динамической матрицы:
A[M][0] ... A[M][N]
A[0][0] ... A[0][N]

Вариант 1. Свой блок – каждой строке
typedef int *pInt;
void main()
{
int M, N, i;
pInt *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;
}
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, как обычно
выделяем массив указателей
выделяем массив под каждую строку
освобождаем память для строк
освобождаем массив адресов строк

Вариант 2. Один блок на матрицу
A
Выделение памяти:
A[0] ... A[M]
A[0][0] … A[1][0] … A[2][0] ... A[M][N]
Освобождение памяти:
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;

Тема 3. Структуры
© К.Ю. Поляков, 2008
Динамические структуры данных
(язык Си)

Структуры
Структура – это тип данных, который может включать в себя несколько полей – элементов разных типов (в том числе и другие структуры).
Свойства:
автор (строка)
название (строка)
год издания (целое число)
количество страниц (целое число)
Задача: объединить эти данные в единое целое
struct Book {
char author[40]; // автор, символьная строка
char title[80]; // название, символьная строка
int year; // год издания, целое число
int pages; // количество страниц, целое число
};
Как ввести новый тип данных-структур?
структура
название
поля

Как работать со структурами?
Объявление:
Book b; // здесь выделяется память!
Book b1 = { "А.С. Пушкин",
"Полтава", 1998, 223 };
Заполнение полей:
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 );

Копирование структур
По элементам:
Book b1, b2;
... // здесь вводим b1
strcpy ( b2.author, b1.author );
strcpy ( b2.title, b1.title );
b2.year = b1.year;
b2.pages = b1.pages;
Задача: скопировать структуру b1 в b2.
Копирование «бит в бит»:
#include
...
memcpy ( &b2, &b1, sizeof(Book) );
или просто так:
b2 = b1;
куда
откуда
сколько байт

Массивы структур
Объявление:
Book B[10];
Обращение к полям:
for ( i = 0; 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

Пример программы
Задача: в файле books.dat записаны данные о книгах в виде массива структур типа Book (не более 100). Установить для всех 2008 год издания и записать обратно в тот же файл.
#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 структур)

Выделение памяти под структуру
Book *p;
p = new Book;
printf ( "Автор " );
gets ( p->author );
printf ( "Название книги " );
gets ( p->title );
printf ( "Количество страниц " );
scanf ( "%d", &p->pages );
p->year = 2008;
...
delete p;
p = new Book;
выделить память под структуру, записать ее адрес в переменную p
p->author
delete p;
освободить память

Динамические массивы структур
Book *B;
int n;
printf ( "Сколько у вас книг? " );
scanf ( "%d", &n );
B = new Book[n];
... // здесь заполняем массив B
for ( i = 0; i < n; i++ )
printf ( "%s. %s. %d.\n",
B[i].author, B[i].title,
B[i].year);
delete B;
Задача: выделить память под массив структур во время выполнения программы.
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]

Реализация в программе
const N = 10;
Book B[N];
Book *p[N], *temp;
int i, j;
... // здесь заполняем структуры
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;
}
for ( i = 0; i < 5; i ++ )
printf("%d %s", p[i]->year, p[i]->title);
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;
}
вспомогательные указатели
начальная расстановка указателей
сортировка методом пузырька, меняем только указатели, сами структуры остаются на местах

Тема 4. Списки
© К.Ю. Поляков, 2008
Динамические структуры данных
(язык Си)

Динамические структуры данных
Строение: набор узлов, объединенных с помощью ссылок.
Как устроен узел:
Типы структур:
списки
деревья
графы
односвязный
двунаправленный (двусвязный)
циклические списки (кольца)

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

Что такое список:
пустая структура – это список;
список – это начальный узел (голова) и связанный с ним список.
Списки: новые типы данных
Структура узла:
struct Node {
char word[40]; // слово
int count; // счетчик повторений
Node *next; // ссылка на следующий элемент
};
typedef Node *PNode;
Указатель на эту структуру:
Адрес начала списка:
PNode Head = NULL;

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

Создание узла
PNode CreateNode ( char NewWord[] )
{
PNode NewNode = new Node; strcpy(NewNode->word, NewWord);
NewNode->count = 1;
NewNode->next = NULL;
return NewNode;
}
Функция CreateNode (создать узел):
вход: новое слово, прочитанное из файла;
выход: адрес нового узла, созданного в памяти.
возвращает адрес созданного узла
новое слово

Добавление узла в начало списка
1) Установить ссылку нового узла на голову списка:
NewNode->next = Head;
2) Установить новый узел как голову списка:
Head = NewNode;
void AddFirst (PNode & Head, PNode NewNode)
{
NewNode->next = Head;
Head = NewNode;
}
&
адрес головы меняется

Добавление узла после заданного
1) Установить ссылку нового узла на узел, следующий за 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 (дошли до конца списка), то стоп;
выполнить действие над узлом с адресом q ;
перейти к следующему узлу, q->next.
Проход по списку
...
PNode q = Head; // начали с головы
while ( q != NULL ) { // пока не дошли до конца
... // делаем что-то хорошее с q
q = q->next; // переходим к следующему узлу
}
...

Добавление узла в конец списка
Задача: добавить новый узел в конец списка.
Алгоритм:
найти последний узел q, такой что q->next равен NULL;
добавить узел после узла с адресом q (процедура AddAfter).
Особый случай: добавление в пустой список.
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

Добавление узла перед заданным (II)
Задача: вставить узел перед заданным без поиска предыдущего.
Алгоритм:
поменять местами данные нового узла и узла p;
установить ссылку узла p на NewNode.
void AddBefore2 ( PNode p, PNode NewNode )
{
Node temp;
temp = *p; *p = *NewNode;
*NewNode = temp;
p->next = NewNode;
}

Поиск слова в списке
Задача:
найти в списке заданное слово или определить, что его нет.
Функция Find:
вход: слово (символьная строка);
выход: адрес узла, содержащего это слово или NULL.
Алгоритм: проход по списку.
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;
пока не дошли до конца списка и слово не равно заданному

Куда вставить новое слово?
Задача:
найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов.
Функция FindPlace:
вход: слово (символьная строка);
выход: адрес узла, перед которым нужно вставить это слово или
NULL, если слово нужно вставить в конец списка.
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

Удаление узла
void DeleteNode ( PNode &Head, PNode p )
{
PNode q = Head;
if ( Head == p )
Head = p->next;
else {
while ( q && q->next != p )
q = q->next;
if ( q == NULL ) return;
q->next = p->next;
}
delete p;
}
while ( q && q->next != p )
q = q->next;
if ( Head == p )
Head = p->next;
Проблема: нужно знать адрес предыдущего узла q.
особый случай: удаляем первый узел
ищем предыдущий узел, такой что
q->next == p
delete p;
освобождение памяти

Алфавитно-частотный словарь
Алгоритм:
открыть файл на чтение;
прочитать слово:
если файл закончился (n!=1), то перейти к шагу 7;
если слово найдено, увеличить счетчик (поле count);
если слова нет в списке, то
создать новый узел, заполнить поля (CreateNode);
найти узел, перед которым нужно вставить слово (FindPlace);
добавить узел (AddBefore);
перейти к шагу 2;
вывести список слов, используя проход по списку.
char word[80];
...
n = fscanf ( in, "%s", word );
FILE *in;
in = fopen ( "input.dat", "r" );
read, чтение
вводится только одно слово (до пробела)!

Двусвязные списки
Структура узла:
struct Node {
char word[40]; // слово
int count; // счетчик повторений
Node *next; // ссылка на следующий элемент
Node *prev; // ссылка на предыдущий элемент
};
typedef Node *PNode;
Указатель на эту структуру:
Адреса «головы» и «хвоста»:
PNode Head = NULL;
PNode Tail = NULL;

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

Тема 5. Стеки, очереди, деки
© К.Ю. Поляков, 2008
Динамические структуры данных
(язык Си)

Стек
Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца (вершины стека). Stack = кипа, куча, стопка (англ.)
LIFO = Last In – First Out
«Кто последним вошел, тот первым вышел».
Операции со стеком:
добавить элемент на вершину
(Push = втолкнуть);
снять элемент с вершины
(Pop = вылететь со звуком).

Пример задачи
Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры:
[()]{} ][ [({)]}
Упрощенная задача: то же самое, но с одним видом скобок.
Решение: счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным.

Решение задачи со скобками
Алгоритм:
в начале стек пуст;
в цикле просматриваем все символы строки по порядку;
если очередной символ – открывающая скобка, заносим ее на вершину стека;
если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка);
если в конце стек не пуст, выражение неправильное.
[ ( ( ) ) ] { }

Реализация стека (массив)
Структура-стек:
const MAXSIZE = 100;
struct Stack {
char 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;
}
ошибка: переполнение стека
добавить элемент
нет ошибки

Реализация стека (массив)
char Pop ( Stack &S )
{
if ( S.size == 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);
}

Программа
void main()
{
char br1[3] = { '(', '[', '{' };
char br2[3] = { ')', ']', '}' };
char s[80], upper;
int i, k, error = 0;
Stack S;
S.size = 0;
printf("Введите выражение со скобками > ");
gets ( s );
... // здесь будет основной цикл обработки
if ( ! error && (S.size == 0) )
printf("\nВыpажение пpавильное\n");
else printf("\nВыpажение непpавильное\n");
}
открывающие скобки
закрывающие скобки
то, что сняли со стека
признак ошибки

Обработка строки (основной цикл)
for ( i = 0; i < strlen(s); i++ )
{
for ( k = 0; k < 3; k++ )
{
if ( s[i] == br1[k] ) // если открывающая скобка
{
Push ( S, s[i] ); // втолкнуть в стек
break;
}
if ( s[i] == br2[k] ) // если закрывающая скобка
{
upper = Pop ( S ); // снять верхний элемент
if ( upper != br1[k] ) error = 1;
break;
}
}
if ( error ) break;
}
цикл по всем символам строки s
цикл по всем видам скобок
ошибка: стек пуст или не та скобка
была ошибка: дальше нет смысла проверять

Реализация стека (список)
Добавление элемента:
Структура узла:
struct Node {
char data;
Node *next;
};
typedef Node *PNode;
void Push (PNode &Head, char x)
{
PNode NewNode = new Node;
NewNode->data = x;
NewNode->next = Head;
Head = NewNode;
}

Реализация стека (список)
Снятие элемента с вершины:
char Pop (PNode &Head) {
char x;
PNode q = Head;
if ( Head == NULL ) return char(255);
x = Head->data;
Head = Head->next;
delete q;
return x;
}
Изменения в основной программе:
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 + c d + 1 - /
Как вычислять автоматически:
Инфиксная запись
(знак операции между операндами)
(a + b) / (c + d – 1)
необходимы скобки!
Постфиксная запись (знак операции после операндов)
польская нотация,
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

Запишите в постфиксной форме
(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 - /
Алгоритм:
взять очередной элемент;
если это не знак операции, добавить его в стек;
если это знак операции, то
взять из стека два операнда;
выполнить операцию и записать результат в стек;
перейти к шагу 1.
X =

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

Очередь
Очередь – это линейная структура данных, в которой
добавление элементов возможно только с одного конца
(конца очереди), а удаление элементов – только с другого конца (начала очереди).
FIFO = First In – First Out
«Кто первым вошел, тот первым вышел».
Операции с очередью:
добавить элемент в конец очереди (PushTail = втолкнуть
в конец);
удалить элемент с начала очереди (Pop).

Реализация очереди (массив)
самый простой способ
нужно заранее выделить массив;
при выборке из очереди нужно сдвигать все элементы.

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

Реализация очереди (кольцевой массив)
В очереди 1 элемент:
Очередь пуста:
Очередь полна:
Head == Tail + 1
размер массива
Head == Tail + 2
Head == Tail

Реализация очереди (кольцевой массив)
const MAXSIZE = 100;
struct Queue {
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 Pop ( Queue &Q )
{
int temp;
if ( Q.head == (Q.tail + 1) % MAXSIZE )
return 32767;
temp = Q.data[Q.head];
Q.head = (Q.head + 1) % MAXSIZE;
return temp;
}
очередь пуста
взять первый элемент
удалить его из очереди

Реализация очереди (списки)
struct Node {
int data;
Node *next;
};
typedef Node *PNode;
struct Queue {
PNode Head, Tail;
};
Структура узла:
Тип данных «очередь»:

Реализация очереди (списки)
void PushTail ( Queue &Q, int x )
{
PNode NewNode; NewNode = new Node;
NewNode->data = x;
NewNode->next = NULL;
if ( Q.Tail )
Q.Tail->next = NewNode;
Q.Tail = NewNode;
if ( Q.Head == NULL ) Q.Head = Q.Tail;
}
Добавление элемента:
создаем новый узел
если в списке уже что-то было, добавляем в конец
если в списке ничего не было, …

Реализация очереди (списки)
int Pop ( Queue &Q )
{
PNode top = Q.Head; int x;
if ( top == NULL )
return 32767;
x = top->data;
Q.Head = top->next;
if ( Q.Head == NULL )
Q.Tail = NULL;
delete top;
return x;
}
Выборка элемента:
если список пуст, …
запомнили первый элемент
если в списке ничего не осталось, …
освободить память

Дек
Дек (deque = double ended queue, очередь с двумя концами) – это линейная структура данных, в которой добавление и удаление элементов возможно с обоих концов.
Операции с деком:
добавление элемента в начало (Push);
удаление элемента с начала (Pop);
добавление элемента в конец (PushTail);
удаление элемента с конца (PopTail).
Реализация:
кольцевой массив;
двусвязный список.

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

Тема 6. Деревья
© К.Ю. Поляков, 2008
Динамические структуры данных
(язык Си)

Деревья

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

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

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

Двоичные деревья
Структура узла:
struct Node {
int data; // полезные данные
Node *left, *right; // ссылки на левого // и правого сыновей
};
typedef Node *PNode;
Применение:
поиск данных в специально построенных деревьях
(базы данных);
сортировка данных;
вычисление арифметических выражений;
кодирование (метод Хаффмана).

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

Двоичные деревья поиска
Поиск в массиве (N элементов):
При каждом сравнении отбрасывается 1 элемент.
Число сравнений – N.
Поиск по дереву (N элементов):
При каждом сравнении отбрасывается половина оставшихся элементов.
Число сравнений ~ log2N.
быстрый поиск
нужно заранее построить дерево;
желательно, чтобы дерево было минимальной высоты.

Реализация алгоритма поиска
//---------------------------------------
// Функция Search – поиск по дереву
// Вход: Tree - адрес корня,
// x - что ищем
// Выход: адрес узла или NULL (не нашли)
//---------------------------------------
PNode Search (PNode Tree, int x)
{
if ( ! Tree ) return NULL;
if ( x == Tree->data )
return Tree;
if ( x < Tree->data )
return Search(Tree->left, x);
else
return Search(Tree->right, x);
}
дерево пустое: ключ не нашли…
нашли, возвращаем адрес корня
искать в левом поддереве
искать в правом поддереве

Как построить дерево поиска?
//---------------------------------------------
// Функция AddToTree – добавить элемент к дереву
// Вход: Tree - адрес корня,
// x - что добавляем
//----------------------------------------------
void AddToTree (PNode &Tree, int x)
{
if ( ! Tree ) {
Tree = new Node;
Tree->data = x;
Tree->left = NULL;
Tree->right = NULL;
return;
}
if ( x < Tree->data )
AddToTree ( Tree->left, x );
else AddToTree ( Tree->right, x );
}
дерево пустое: создаем новый узел (корень)
адрес корня может измениться
добавляем к левому или правому поддереву

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

Обход дерева – реализация
//---------------------------------------------
// Функция LKP – обход дерева в порядке ЛКП
// (левый – корень – правый)
// Вход: Tree - адрес корня
//----------------------------------------------
void LKP( PNode Tree )
{
if ( ! Tree ) return;
LKP ( Tree->left );
printf ( "%d ", Tree->data );
LKP ( Tree->right );
}
обход этой ветки закончен
обход левого поддерева
вывод данных корня
обход правого поддерева

Разбор арифметических выражений
a b + c d + 1 - /
Как вычислять автоматически:
Инфиксная запись, обход ЛКП
(знак операции между операндами)
(a + b) / (c + d – 1)
необходимы скобки!
Постфиксная запись, ЛПК (знак операции после операндов)
a + b / c + d – 1
польская нотация,
Jan Łukasiewicz (1920)
скобки не нужны, можно однозначно вычислить!
Префиксная запись, КЛП (знак операции до операндов)
/ + a b - + c d 1
обратная польская нотация,
F. L. BauerF. L. Bauer and E. W. Dijkstra

Вычисление выражений
Постфиксная форма:
a b + c d + 1 - /
Алгоритм:
взять очередной элемент;
если это не знак операции, добавить его в стек;
если это знак операции, то
взять из стека два операнда;
выполнить операцию и записать результат в стек;
перейти к шагу 1.
X =

Вычисление выражений
Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа и знаки операций +-*\. Вычислить это выражение.
Алгоритм:
ввести строку;
построить дерево;
вычислить выражение по дереву.
Ограничения:
ошибки не обрабатываем;
многозначные числа не разрешены;
дробные числа не разрешены;
скобки не разрешены.

Построение дерева
Алгоритм:
если first=last (остался один символ – число), то создать новый узел и записать в него этот элемент; иначе...
среди элементов от first до last включительно найти последнюю операцию (элемент с номером k);
создать новый узел (корень) и записать в него знак операции;
рекурсивно применить этот алгоритм два раза:
построить левое поддерево, разобрав выражение из элементов массива с номерами от first до k-1;
построить правое поддерево, разобрав выражение из элементов массива с номерами от k+1 до last.
first
last
k
k+1
k-1

Как найти последнюю операцию?
Порядок выполнения операций
умножение и деление;
сложение и вычитание.
Приоритет (старшинство) – число, определяющее последовательность выполнения операций: раньше выполняются операции с большим приоритетом:
умножение и деление (приоритет 2);
сложение и вычитание (приоритет 1).

Приоритет операции
//--------------------------------------------
// Функция Priority – приоритет операции
// Вход: символ операции
// Выход: приоритет или 100, если не операция
//--------------------------------------------
int Priority ( char c )
{
switch ( c ) {
case '+': case '-': return 1;
case '*': case '/': return 2;
}
return 100;
}
сложение и вычитание: приоритет 1
умножение и деление: приоритет 2
это вообще не операция

Номер последней операции
//--------------------------------------------
// Функция LastOperation – номер последней операции
// Вход: строка, номера первого и последнего
// символов рассматриваемой части
// Выход: номер символа - последней операции
//--------------------------------------------
int LastOperation ( char Expr[], int first, int last )
{
int MinPrt, i, k, prt;
MinPrt = 100;
for( i = first; i <= last; i++ ) {
prt = Priority ( Expr[i] );
if ( prt <= MinPrt ) {
MinPrt = prt;
k = i;
}
}
return k;
}
проверяем все символы
вернуть номер символа
нашли операцию с минимальным приоритетом

Построение дерева
Структура узла
struct Node {
char data;
Node *left, *right;
};
typedef Node *PNode;
Создание узла для числа (без потомков)
PNode NumberNode ( char c )
{
PNode Tree = new Node;
Tree->data = c;
Tree->left = NULL;
Tree->right = NULL;
return Tree;
}
возвращает адрес созданного узла
один символ, число

Построение дерева
//--------------------------------------------
// Функция MakeTree – построение дерева
// Вход: строка, номера первого и последнего
// символов рассматриваемой части
// Выход: адрес построенного дерева
//--------------------------------------------
PNode MakeTree ( char Expr[], int first, int last )
{
PNode Tree;
int k;
if ( first == last )
return NumberNode ( Expr[first] );
k = LastOperation ( Expr, first, last );
Tree = new Node;
Tree->data = Expr[k];
Tree->left = MakeTree ( Expr, first, k-1 );
Tree->right = MakeTree ( Expr, k+1, last );
return Tree;
}
осталось только число
новый узел: операция

Вычисление выражения по дереву
//--------------------------------------------
// Функция CalcTree – вычисление по дереву
// Вход: адрес дерева
// Выход: значение выражения
//--------------------------------------------
int CalcTree (PNode Tree)
{
int num1, num2;
if ( ! Tree->left ) return Tree->data - '0';
num1 = CalcTree( Tree->left);
num2 = CalcTree(Tree->right);
switch ( Tree->data ) {
case '+': return num1+num2;
case '-': return num1-num2;
case '*': return num1*num2;
case '/': return num1/num2;
}
return 32767;
}
вернуть число, если это лист
вычисляем операнды (поддеревья)
выполняем операцию
некорректная операция

Основная программа
//--------------------------------------------
// Основная программа: ввод и вычисление
// выражения с помощью дерева
//--------------------------------------------
void main()
{ char s[80];
PNode Tree;
printf ( "Введите выражение > " );
gets(s);
Tree = MakeTree ( s, 0, strlen(s)-1 );
printf ( "= %d \n", CalcTree ( Tree ) );
getch();
}

Дерево игры
Задача.
Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней.
Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу.
Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16.
Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?

Дерево игры
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
ключевой ход
выиграл игрок 1

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

Тема 7. Графы
© К.Ю. Поляков, 2008
Динамические структуры данных
(язык Си)

Определения
Граф – это набор вершин (узлов) и соединяющих их ребер (дуг).
Направленный граф (ориентированный, орграф) – это граф, в котором все дуги имеют направления.
Цепь – это последовательность ребер, соединяющих две вершины (в орграфе – путь).
Цикл – это цепь из какой-то вершины в нее саму.
Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина).
Да, без циклов!

Определения
Связный граф – это граф, в котором существует цепь между каждой парой вершин.
k-cвязный граф – это граф, который можно разбить на k связных частей.
Полный граф – это граф, в котором проведены все возможные ребра (n вершин → n(n-1)/2 ребер).

Описание графа
Матрица смежности – это матрица, элемент M[i][j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет.
Список смежности

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

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

Как обнаружить цепи и циклы?
Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i в нее саму).
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

Как обнаружить цепи и циклы?
M2 = M ⊗ M
Логическое умножение матрицы на себя:
матрица путей длины 2
M2 =
⊗
=
M2[2][0] = 0·0 + 1·1 + 0·0 + 1·1 = 1
маршрут 2-1-0
маршрут 2-3-0

Как обнаружить цепи и циклы?
M3 = M2 ⊗ M
Матрица путей длины 3:
M3 =
⊗
=
на главной диагонали – циклы!
M4 =
⊗
=

Весовая матрица
Весовая матрица – это матрица, элемент W[i][j] которой равен весу ребра из вершины i в вершину j (если оно есть), или равен ∞, если такого ребра нет.

Задача Прима-Краскала
Задача: соединить N городов телефонной сетью так, чтобы длина телефонных линий была минимальная.
Та же задача: дан связный граф с N вершинами, веса ребер заданы весовой матрицей W. Нужно найти набор ребер, соединяющий все вершины графа (остовное дерево) и имеющий наименьший вес.

Жадный алгоритм
Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент.
Шаг в задаче Прима-Краскала – это выбор еще невыбранного ребра и добавление его к решению.

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

Реализация алгоритма Прима-Краскала
Структура «ребро»:
struct rebro {
int i, j; // номера вершин
};
const N = 5;
void main()
{
int W[N][N], Color[N], i, j,
k, min, col_i, col_j;
rebro Reb[N-1];
... // здесь надо ввести матрицу W
for ( i = 0; i < N; i ++ ) // раскрасить вершины
Color[i] = i;
... // основной алгоритм – заполнение массива Reb
... // вывести найденные ребра (массив Reb)
}
Основная программа:
весовая матрица
цвета вершин

Реализация алгоритма Прима-Краскала
for ( k = 0; k < N-1; k ++ ) {
min = 30000; // большое число
for ( i = 0; i < N-1; i ++ )
for ( j = i+1; j < N; j ++ )
if ( Color[i] != Color[j] && W[i][j] < min ) {
min = W[i][j];
Reb[k].i = i;
Reb[k].j = j;
col_i = Color[i];
col_j = Color[j];
}
for ( i = 0; i < N; i ++ )
if ( Color[i] == col_j ) Color[i] = col_i;
}
Основной алгоритм:
нужно выбрать N-1 ребро
цикл по всем парам вершин
учитываем только пары с разным цветом вершин
запоминаем ребро и цвета вершин
перекрашиваем вершины цвета col_j

Сложность алгоритма
Основной цикл:
O(N3)
for ( k = 0; k < N-1; k ++ ) {
...
for ( i = 0; i < N-1; i ++ )
for ( j = i+1; j < N; j ++ )
...
}
три вложенных цикла, в каждом число шагов <=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, такой что a[i]=1, если вершина уже рассмотрена, и a[i]=0, если нет.
массив b, такой что b[i] – длина текущего кратчайшего пути из заданной вершины x в вершину i;
массив c, такой что c[i] – номер вершины, из которой нужно идти в вершину i в текущем кратчайшем пути.
Инициализация:
заполнить массив a нулями (вершины не обработаны);
записать в b[i] значение W[x][i];
заполнить массив c значением x;
записать a[x]=1.

Реализация алгоритма Дейкстры
Основной цикл:
если все вершины рассмотрены, то стоп.
среди всех нерассмотренных вершин (a[i]=0) найти вершину j, для которой b[i] – минимальное;
записать a[j]=1;
для всех вершин k: если путь в вершину k через вершину j короче, чем найденный ранее кратчайший путь, запомнить его: записать b[k]=b[j]+W[j][k] и c[k]=j.
Шаг 1:

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

Как вывести маршрут?
Результат работа алгоритма Дейкстры:
длины путей
Маршрут из вершины 0 в вершину 4:
4
5
2
0
Сложность алгоритма Дейкстры:
O(N2)
два вложенных цикла по N шагов
Вывод маршрута в вершину i (использование массива c):
установить z=i;
пока c[i]!=x присвоить z=c[z] и вывести z.

Алгоритм Флойда-Уоршелла
Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов.
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!

Алгоритм Флойда-Уоршелла
Версия с запоминанием маршрута:
for ( i = 0; i < N; i ++ )
for ( j = 0; j < N; j ++ )
c[i][j] = i;
...
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];
c[i][j] = c[k][j];
}
i–ая строка строится так же, как массив c в алгоритме Дейкстры
в конце цикла c[i][j] – предпоследняя вершина в кратчайшем маршруте из вершины i в вершину j
c[i][j] = c[k][j];
O(N3)

Задача коммивояжера
Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,...N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Точные методы:
простой перебор;
метод ветвей и границ;
метод Литтла;
…
Приближенные методы:
метод случайных перестановок (Matlab);
генетические алгоритмы;
метод муравьиных колоний;
…
большое время счета для больших N
O(N!)
не гарантируется оптимальное решение

Другие классические задачи
Задача на минимум суммы. Имеется N населенных пунктов, в каждом из которых живет pi школьников (i=1,...,N). Надо разместить школу в одном из них так, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным.
Задача о наибольшем потоке. Есть система труб, которые имеют соединения в N узлах. Один узел S является источником, еще один – стоком T. Известны пропускные способности каждой трубы. Надо найти наибольший поток от источника к стоку.
Задача о наибольшем паросочетании. Есть M мужчин и N женщин. Каждый мужчина указывает несколько (от 0 до N) женщин, на которых он согласен жениться. Каждая женщина указывает несколько мужчин (от 0 до M), за которых она согласна выйти замуж. Требуется заключить наибольшее количество моногамных браков.