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

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

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

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

Стек
Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца (вершины стека). 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;
}
Выборка элемента:
если список пуст, …
запомнили первый элемент
если в списке ничего не осталось, …
освободить память