Си_ДинСтруктурыДанных.ppt

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

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

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

переменная (массив) имеет имя, по которому к ней можно обращаться
размер заранее известен (задается при написании программы)
память выделяется при объявлении
размер нельзя увеличить во время работы программы

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

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

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

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

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

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

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

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

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

Программа

#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;
}

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

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

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

Вариант 1. Свой блок – каждой строке

int **A;

typedef int *pInt;
pInt *A;

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

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. Структуры

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

Структуры

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

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

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

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

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

Задача: в файле 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. Списки

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

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

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

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

списки

деревья

графы

односвязный

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

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

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

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

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

новое слово

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

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

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

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

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

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

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

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)

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

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

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

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

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->next == p

delete p;

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

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

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. Стеки, очереди, деки

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

Стек

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

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

[ ( ( ) ) ] { }

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

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

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)

/ + a b - + c d 1

a + b

a + b

c + d

c + d

c + d - 1

c + d - 1

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

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

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

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

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

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

a b + c d + 1 - /

X =

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

Очередь

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

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

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

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

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

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

Head == Tail + 1

размер массива

Head == Tail + 2

Head == Tail

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

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

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

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

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

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

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

Дек

Задания

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

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

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

Деревья

Деревья

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

Деревья

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

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

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

struct Node {
int data; // полезные данные
Node *left, *right; // ссылки на левого  // и правого сыновей
};
typedef Node *PNode;

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

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

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

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

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

//---------------------------------------
// Функция 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

/ + a b - + c d 1

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

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

a b + c d + 1 - /

X =

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

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

first

last

k

k+1

k-1

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

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

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

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

//--------------------------------------------
// Функция 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

игрок 1

3, 6

27, 2

3, 18

3, 3

4, 2

12, 2

4, 6

5, 2

4, 3

9, 3

4, 3

36, 2

4, 18

15, 2

27, 3

игрок 1

игрок 2

игрок 2

9, 2

4, 3

4, 3

Задания

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

Тема 7. Графы

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

Определения

Определения

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

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

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

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

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

M =

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

M2 = M  M

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

M2 =



=

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

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

M3 = M2  M

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

M3 =



=

M4 =



=

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

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

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

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

2

1

3

4

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

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

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

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

O(N3)

for ( k = 0; k < N-1; k ++ ) {
...
for ( i = 0; i < N-1; i ++ )
for ( j = i+1; j < N; j ++ )
...
}

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

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

O(N2)

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

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

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

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

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

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

Шаг 1:

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

Шаг 2:

Шаг 3:

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

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

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

4

5

2

0

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

O(N2)

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

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

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

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

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

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

O(N3)

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

O(N!)

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