programming
informaticsSimilar presentations:
Алгоритмизация и программирование. Язык C. Целочисленные алгоритмы (§ 38 - § 45)
1. Алгоритмизация и программирование. Язык C
1Алгоритмизация и
программирование.
Язык C
§ 38. Целочисленные алгоритмы
§ 39. Структуры
§ 40. Динамические массивы
§ 41. Списки
§ 42. Стек, очередь, дек
§ 43. Деревья
§ 44. Графы
§ 45. Динамическое программирование
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
2. Алгоритмизация и программирование. Язык C
2Алгоритмизация и
программирование.
Язык C
§ 38. Целочисленные
алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
3. Решето Эратосфена
3Алгоритмизация и программирование. Язык C, 11 класс
Решето Эратосфена
3 4 5 6 7 8 9 10 11 12 13 14 15 16
22 3
Алгоритм:
1) начать с k = 2
Эратосфен Киренский
2) «выколоть» все числа через k, начиная с 2k···kk
(Eratosthenes, Ερατοσθδνη)
3) перейти к следующему «невыколотому» k
(ок. 275-194 до н.э.)
<=N N , то перейти к шагу 2
4) если kk··k<=
5) напечатать все числа, оставшиеся «невыколотыми»
Новая версия – решето Аткина.
?
Как улучшить?
высокая скорость, количество операций
O((N·log N)·log log N )
нужно хранить в памяти все числа от 1 до N
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
4. Решето Эратосфена
4Алгоритмизация и программирование. Язык C, 11 класс
Решето Эратосфена
Задача. Вывести все простые числа от 2 до N.
Объявление переменных:
const int N = 100;
bool A[N+1];
выделяем на 1
int i, k;
элемент больше,
чтобы начать с
A[1]
Сначала все невычеркнуты:
for ( i = 2; i <= N; i++ )
A[i] = true;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
5. Решето Эратосфена
5Алгоритмизация и программирование. Язык C, 11 класс
Решето Эратосфена
Вычёркивание непростых:
k = 2;
while ( k*k <= N ) {
if ( A[k] ) {
i = k*k;
while ( i <= N )
{
A[i] = false;
i += k;
}
}
k ++;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
6. Решето Эратосфена
6Алгоритмизация и программирование. Язык C, 11 класс
Решето Эратосфена
Вывод результата:
for ( i = 2; i <= N; i++ )
if ( A[i] )
printf ( "%d ", i );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
7. «Длинные» числа
7Алгоритмизация и программирование. Язык C, 11 класс
«Длинные» числа
Ключи для шифрования: 256 битов.
Целочисленные типы данных: 64 битов.
?
Как хранить?
Длинное число – это число, которое не помещается в
переменную одного из стандартных типов данных
языка программирования.
«Длинная арифметика» – алгоритмы для работы с
длинными числами.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
8. «Длинные» числа
8Алгоритмизация и программирование. Язык C, 11 класс
«Длинные» числа
A = 12345678
A
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
0
0
?
Что плохо?
нужно хранить длину числа
неудобно вычислять (с младшего разряда!)
неэкономное расходование памяти
Обратный порядок элементов:
A
9
8
7
6
5
4
3
2
1
0
0
0
1
2
3
4
5
6
7
8
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
9. «Длинные» числа
9Алгоритмизация и программирование. Язык C, 11 класс
«Длинные» числа
Упаковка элементов:
A
A = 12345678
9
8
7
6
5
4
3
0
0
0
0
0
0
0
2
1
0
12 345 678
12345678 = 12·10002 + 345·10001 + 678·10000
?
На что похоже?
система счисления
с основанием 1000!
long int:
от –231 = – 2 147 483 648 до 231 – 1 = 2 147 483 647.
?
Какие основания можно использовать?
должны помещаться все
промежуточные результаты!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
10. Вычисление факториала
10Алгоритмизация и программирование. Язык C, 11 класс
Вычисление факториала
Задача 1. Вычислить точно значение факториала
100! = 1·2·3·…·99·100
?
Как оценить количество цифр?
201 цифра
1·2·3·…·99·100 < 100100
основание
6 цифр в ячейке 34 ячейки
1000000
const int N = 33;
long int A[N+1];
Основной алгоритм:
длинное
число
[A] = 1;
for ( k = 2; k <= 100; k ++ )
[A] = [A] * k;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
11. Вычисление факториала
11Алгоритмизация и программирование. Язык C, 11 класс
Вычисление факториала
основание d = 1 000 000
[A] = 12345678901734567
A
3
2
1
0
0
12345
678901
734567
734 567·3 = 2 203 701
r = перенос в A[1]
?
*3
остаётся в
A[0]
Как найти перенос?
s = A[0]*k;
A[0] = s % d;
r = s / d;
?
Что изменится для A[1]?
К.Ю. Поляков, Е.А. Ерёмин, 2014
s:= A[1]*k +
r;
http://kpolyakov.spb.ru
12. Вычисление факториала
12Алгоритмизация и программирование. Язык C, 11 класс
Вычисление факториала
Умножение «длинного» числа на k:
r = 0;
for ( i = 0; i <= N; i++ ) {
s = A[i] * k + r;
A[i] = s % d;
r = s / d;
}
все разряды
Вычисление 100!:
for ( k = 2; k <= 100; k++ )
{
...
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
13. Вывод длинного числа
13Алгоритмизация и программирование. Язык C, 11 класс
Вывод длинного числа
A
3
2
1
0
0
1
2
3
?
Какое число?
[A] = 1000002000003
• найти старший ненулевой разряд
i = N;
while ( ! A[i] )
i --;
• вывести этот разряд
printf ( "%ld", A[i] );
• вывести все следующие разряды, добавляя
лидирующие нули до 6 цифр
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
14. Вывод длинного числа
14Алгоритмизация и программирование. Язык C, 11 класс
Вывод длинного числа
Вывод остальных разрядов:
for ( k = i-1; k >= 0; k-- )
Write6 ( A[k] );
Write6:
x = 12345
x /
100000
012345
x %
100000
К.Ю. Поляков, Е.А. Ерёмин, 2014
со старшего
x
M
x / M
12345
100000
0
12345
10000
1
2345
1000
2
345
100
3
45
10
4
5
1
5
http://kpolyakov.spb.ru
15. Вывод длинного числа
Алгоритмизация и программирование. Язык C, 11 класс15
Вывод длинного числа
Вывод числа с лидирующими нулями:
void Write6 ( long int x )
{
long int M = 100000;
while ( M > 0 )
{
printf ( "%d", x / M );
x %= M;
M /= 10;
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
16. Алгоритмизация и программирование. Язык C
16Алгоритмизация и
программирование.
Язык C
§ 39. Структуры
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
17. Зачем нужны структуры?
17Алгоритмизация и программирование. Язык C, 11 класс
Зачем нужны структуры?
Книги в библиотеках:
символьные
• автор
строки
• название
• количество экземпляров
целое число
•…
?
Как хранить данные?
Несколько массивов:
char authors[N][40];
char titles[N][80];
int count[N];
...
неудобно работать
(сортировать и
т.д.), ошибки
Задачa: объединить разнотипные данные в один блок.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
18. Структуры
18Алгоритмизация и программирование. Язык C, 11 класс
Структуры
Структура – это тип данных, который может включать в
себя несколько полей – элементов разных типов (в
том числе и другие структуры).
новый тип данных
typedef struct
структура
{
char author[40]; //
char title[80];
//
int count;
//
} TBook;
автор, строка
название, строка
количество, целое
название типа
данных
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
19. Объявление структур
19Алгоритмизация и программирование. Язык C, 11 класс
Объявление структур
const
TBook
TBook
?
int N = 100;
B;
Books[N];
Сколько места занимает в памяти?
printf (
printf (
printf (
"%d\n",
"%d\n",
"%d\n",
sizeof(TBook) ); // 124
sizeof(B) );
// 124
sizeof(Books) ); // 12400
typedef
typedef struct
struct
40 байт
{{
char
char author[40];
author[40];
80 байт
char
char title[80];
title[80];
int
int count;
count;
}} TBook;
4 байта
TBook;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
20. Обращение к полям структур
20Алгоритмизация и программирование. Язык C, 11 класс
Обращение к полям структур
Точечная нотация:
B.author // поле author структуры B
Books[5].count // поле count структуры
// Books[5]
printf (
printf (
printf (
"%d\n",
"%d\n",
"%d\n",
sizeof(B.author) );
sizeof(B.title) );
sizeof(B.count) );
//
//
//
40
80
4
gets ( B.author );
gets ( B.title );
scanf ( "%d", &B.count );
printf ( "%s %s. %d шт.",
B.author, B.title, B.count );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
21. Обращение к полям структур
21Алгоритмизация и программирование. Язык C, 11 класс
Обращение к полям структур
Присваивание:
strcpy ( B.author,"Пушкин А.С." );
strcpy ( B.title, "Полтава" );
B.count = 1;
Использование:
B.count --;
// одну книгу взяли
if( B.count == 0)
puts ( "Этих книг больше нет!" );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
22. Запись структур в файлы
22Алгоритмизация и программирование. Язык C, 11 класс
Запись структур в файлы
Текстовые файлы:
символ-разделитель
'Пушкин А.С.';'Полтава';12
'Лермонтов М.Ю.';'Мцыри';8
Двоичные файлы:
!
Сложно читать,
ошибки!
FILE *Fout;
Fout = fopen ( "books.dat", "wb" );
fwrite ( &B, sizeof(B), 1, Fout );
fwrite ( &Books[0], sizeof(TBook),
адрес в
размер
сколько
12,
Fout
);
памяти
блока
блоков
fclose ( Fout );
binary, двоичный
"wb" – запись в двоичный файл
"rb" – чтение двоичного файла
"ab" – добавление к двоичному файлу
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
23. Чтение структур из файла
23Алгоритмизация и программирование. Язык C, 11 класс
Чтение структур из файла
Одна структура:
FILE *Fin;
Fin = fopen ( "books.dat", "rb" );
fread ( &B, sizeof(B), 1, Fin );
printf ( "%s %s. %d шт.",
адрес в
размер
сколько
памяти B.author,
блока B.title,
блоков B.count );
fсlose ( Fin );
Сразу несколько структур:
fread ( &Books[0], sizeof(TBook), 5, Fin );
адрес в
памяти
К.Ю. Поляков, Е.А. Ерёмин, 2014
размер
структуры
сколько
структур
http://kpolyakov.spb.ru
24. Чтение структур из файла
24Алгоритмизация и программирование. Язык C, 11 класс
Чтение структур из файла
Число структур неизвестно:
const int N = 100;
int M;
...
M = fread ( &Books[0], sizeof(TBook),
N, Fin );
printf ( "Прочитано %d структур.", M );
!
fread возвращает число успешно
прочитанных структур!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
25. Сортировка структур
25Алгоритмизация и программирование. Язык C, 11 класс
Сортировка структур
Ключ – фамилия автора:
?
Какой метод?
for ( i = 0; i < N - 1; i++ )
for ( j = N - 2; j >= i; j-- )
if ( strcmp(Books[j].author,
Books[j+1].author) > 0 )
{
TBook В;
B
=
Books[j];
B = Books[j];
Books[j]
Books[j+1];
Books[j] =
= Books[j+1];
Books[j+1]
B;
Books[j+1] =
= B;
}
структуры перемещаются в памяти
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
26. Указатели
26Алгоритмизация и программирование. Язык C, 11 класс
Указатели
Указатель – это переменная, в которой можно сохранить
адрес любой переменной заданного типа.
TBook *p;
указатель на
переменную типа
TBook
p = &B;
p->author
p=
B &Books[2];
B.author
p
0
1
2
3
4
Books
p->author Books[2].author
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
27. Сортировка по указателям
27Алгоритмизация и программирование. Язык C, 11 класс
Сортировка по указателям
TBook *p[N], *p1;
for ( i = 0; i < N; i++ )
p[i] = &Books[i];
p[0]
Books
p[1]
p[2]
0
1
2
…
Нагибин Ю. … … Астафьев В. … … Васильев Б. … … …
Задача – переставить указатели:
p[2]
Books
p[0]
p[1]
0
1
2
…
Нагибин Ю. … … Астафьев В. … … Васильев Б. … … …
!
Сами структуры не перемещаются!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
28. Сортировка по указателям
28Алгоритмизация и программирование. Язык C, 11 класс
Сортировка по указателям
for ( i = 0; i < M-1; i++ )
for ( j = M-2; j >= i; j-- )
if ( strcmp ( p[j]->author,
p[j+1]->author
{
p1 = p[j]; p[j]= p[j+1];
p[j+1]= p1;
TBook
}
*p1;
Вывод результата:
обращение к
полям через
указатели
) > 0 )
переставляем
указатели!
for ( i = 0; i < M; i++ )
printf ( "%s, %s, %d\n",
p[i]->author, p[i]->title,
p[i]->count );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
29. Алгоритмизация и программирование. Язык C
29Алгоритмизация и
программирование.
Язык C
§ 40. Динамические массивы
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
30. Чем плох обычный массив?
30Алгоритмизация и программирование. Язык C, 11 класс
Чем плох обычный массив?
const int N = 100;
статический
массив
int A[N];
• память выделяется при трансляции
• нужно заранее знать размер
• изменить размер нельзя
Задача. В файле записаны фамилии (сколько –
неизвестно!). Вывести их в другой файл в алфавитном
порядке.
• выделить заранее большой блок (с запасом)
• выделять память во время работы программы
(динамически!)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
31. Динамические структуры данных
31Алгоритмизация и программирование. Язык C, 11 класс
Динамические структуры данных
… позволяют
• создавать новые объекты в памяти
• изменять их размер
• удалять из памяти, когда не нужны
Задача. Ввести с клавиатуры целое значение N, затем –
N целых чисел, и вывести на экран эти числа в
порядке возрастания.
//
//
//
прочитать данные из файла в массив
отсортировать их по возрастанию
вывести массив на экран
?
В чём проблема?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
32. Динамические массивы
32Алгоритмизация и программирование. Язык C, 11 класс
Динамические массивы
Объявление:
int *A;
!
Память не выделяется!
Выделение памяти:
размер
блока
#include <stdlib.h>
...
A = (int*) calloc ( N, sizeof(int) );
преобразовать к
указателю на int
К.Ю. Поляков, Е.А. Ерёмин, 2014
количеств
о блоков
http://kpolyakov.spb.ru
33. Динамические массивы
Алгоритмизация и программирование. Язык C, 11 класс33
Динамические массивы
Использование массива:
for ( i = 0; i < N; i++ )
scanf ( "%d", &A[i] );
...
for ( i = 0; i < N; i++ )
{
A[i] = i;
printf ( "%d ", A[i] );
}
Освобождение памяти:
free ( A );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
34. Динамические матрицы
34Алгоритмизация и программирование. Язык C, 11 класс
Динамические матрицы
!
Матрица – это массив из массивов!
Указатель на матрицу:
новый тип
данных: указатель
typedef int *pInt;
pInt *A;
указатель на указатель
Выделение памяти под массив указателей:
A =(pInt*)calloc( N, sizeof(pInt) );
Выделение памяти под элементы матрицы:
A[0] =(int*)calloc( N*M, sizeof(int));
число элементов
матрицы
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
35. Динамические матрицы
35Алгоритмизация и программирование. Язык C, 11 класс
Динамические матрицы
0
1
2
N-2
N-1
массив
указателей
A
M
M
Расстановка указателей:
for ( i = 1; i < N; i++ )
A[i] = A[i-1] + M;
Работа с матрицей:
for ( i = 0; i < N; i++ )
for ( j = 0; j < M; j++ )
A[i][j] = i + j;
К.Ю. Поляков, Е.А. Ерёмин, 2014
M
M
Удаление:
free ( A[0] );
free ( A );
http://kpolyakov.spb.ru
36. Динамические матрицы
36Алгоритмизация и программирование. Язык C, 11 класс
Динамические матрицы
0
1
2
N-2
N-1
массив
указателей
A
M
!
M
M
Строки могут быть разной длины!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
37. Динамические матрицы
37Алгоритмизация и программирование. Язык C, 11 класс
Динамические матрицы
Выделение памяти:
for ( i = 0; i < N; i++ )
A[i] =(int*) calloc(M, sizeof(int));
Освобождение памяти:
освободить
for ( i = 0; i < N; i++ )
память для
free ( A[i] );
отдельных строк
free ( A );
освободить
массив указателей
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
38. Расширение массива
38Алгоритмизация и программирование. Язык C, 11 класс
Расширение массива
Задача. С клавиатуры вводятся натуральные числа, ввод
заканчивается числом 0. Нужно вывести на экран эти
числа в порядке возрастания.
?
Какой размер массива нужен?
Расширение по 1 элементу:
N = 0;
перераспределить
scanf ( "%d", &x );
память
while ( x!= 0 ) {
N ++;
A = (int*) realloc ( A, N*sizeof(int) );
A[N-1] = x;
scanf ( "%d", &x );
Что плохо?
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
39. Расширение массива
39Алгоритмизация и программирование. Язык C, 11 класс
Расширение массива
Расширение по 10 элементов:
N = 0;
scanf ( "%d", &x );
while ( x!= 0 )
{
Зачем нужен счётчик?
N ++;
if ( N > length )
{
length += 10;
A = (int*) realloc ( A,
length*sizeof(int) );
}
A[N-1] = x;
scanf ( "%d", &x );
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
40. Алгоритмизация и программирование. Язык C
40Алгоритмизация и
программирование.
Язык C
§ 41. Списки
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
41. Зачем нужны списки?
41Алгоритмизация и программирование. Язык C, 11 класс
Зачем нужны списки?
Задача. В файле находится список слов, среди которых
есть повторяющиеся. Каждое слово записано в
отдельной строке. Построить алфавитно-частотный
словарь: список слов в алфавитном порядке, справа
от каждого слова должно быть указано, сколько раз
оно встречается в исходном файле.
!
Нужно вставлять новые слова в список!
Список – это упорядоченный набор элементов одного
типа, для которого введены операции вставки
(включения) и удаления (исключения).
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
42. Алгоритм (псевдокод)
42Алгоритмизация и программирование. Язык C, 11 класс
Алгоритм (псевдокод)
пока есть слова в файле
{
прочитать очередное слово
если оно есть в списке то
увеличить на 1 счётчик для этого слова
иначе
{
добавить слово в список
записать 1 в счетчик слова
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
43. Хранение данных
Алгоритмизация и программирование. Язык C, 11 класс43
Хранение данных
Пара «слово-счётчик»:
typedef struct
{
char word[40];
int count;
} TPair;
Список таких пар:
динамический
typedef struct
массив
{
TPair *data;
int capacity; // размер массива
int size;
количество слов
} TWordList;
в списке
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
44. Хранение данных
44Алгоритмизация и программирование. Язык C, 11 класс
Хранение данных
Переменная-список:
TWordList L;
Начальные значения:
L.size = 0;
L.capacity = 10;
L.data = (TPair*) calloc ( L.capacity,
sizeof(TPair) );
Вывод результата:
автомат: 1
F = fopen ( "output.txt", "w" ); ананас: 12
for ( p = 0; p < L.size; p++ )
...
fprintf ( F, "%s: %d\n",
L.data[p].word, L.data[p].count );
fclose ( F );
К.Ю. Поляков, Е.А. Ерёмин, 2014
?
Как объявить p?
http://kpolyakov.spb.ru
45. Основной цикл
45Алгоритмизация и программирование. Язык C, 11 класс
Основной цикл
F = fopen ( "input.txt", "r" );
while ( 1 == fscanf(F, "%s", s) )
// 1
{
p = Find ( L, s );
// 2
if ( p >= 0 )
L.data[p].count ++;
// 3
else
{
p = FindPlace ( L, s );
// 4
InsertWord ( &L, p, s );
// 5
}
}
fclose ( F );
Как объявить s?
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
46. Поиск слова
46Алгоритмизация и программирование. Язык C, 11 класс
Поиск слова
int Find( TWordList L, char word[] )
{
int i;
for ( i = 0; i < L.size; i++ )
if ( 0 == strcmp(L.data[i].word, word) )
return i;
вернуть номер
return -1;
элемента в списке
}
вернуть -1,
если нет в
списке
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
47. Поиск места вставки
47Алгоритмизация и программирование. Язык C, 11 класс
Поиск места вставки
int FindPlace ( TWordList L, char word[] )
{
int i;
for ( i = 0; i < L.size; i++ )
if ( strcmp(L.data[i].word, word) > 0 )
return i;
первое слово
return L.size;
«больше»
}
заданного
если не найдено,
вставить в конец
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
48. Вставка слова
48Алгоритмизация и программирование. Язык C, 11 класс
Вставка слова
1 автомат
1
автомат
1
2 ананас
12
ананас
12 2
...
k-1 дар
дерево k дом
k+1 дорога
...
3
дар
3
k-1
15
дерево
1
k
5
дом
15 k+1
дорога
5
...
ящерица
Сдвиг вниз:
1
1
с последнего
...
ящерица
1
L.size-1
for ( i = L.size-1; i > k; i-- )
L.data[i] = L.data[i-1];
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
49. Вставка слова
49Алгоритмизация и программирование. Язык C, 11 класс
Вставка слова
список меняется,
обращение по
указателю
void InsertWord ( TWordList *pL, int k,
char word[] )
{
увеличить размер,
int i;
если нужно
IncSize ( pL );
for ( i = pL->size-1; i > k; i-- )
сдвиг//
вниз
pL->data[i] = pL->data[i-1];
3
strcpy ( pL->data[k].word, word );
}
pL->data[k].count = 1;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
50. Расширение списка
50Алгоритмизация и программирование. Язык C, 11 класс
Расширение списка
список
меняется
void IncSize ( TWordList *pL )
{
если новый размер больше
pL->size ++;
ёмкости массива
if ( pL->size > pL->capacity )
{
добавить 10
pL->capacity += 10;
элементов
pL->data =
(TPair*) realloc ( pL->data,
sizeof(TPair)*pL->capacity );
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
51. Вся программа
51Алгоритмизация и программирование. Язык C, 11 класс
Вся программа
// объявления типов TPair и TWordList
// процедуры и функции
void main()
{
TWordList L;
int p;
char s[80];
FILE *F;
L.size = 0;
L.capacity = 10;
L.data = (TPair*) calloc ( L.capacity,
sizeof(TPair) );
// основной цикл: чтение списка слов
// вывод результата в файл
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
52. Модули
52Алгоритмизация и программирование. Язык C, 11 класс
Модули
!
Идея – вынести процедуры и функции в
отдельный файл!
alphalist.c
wordlist.c
main()
{
...
}
проще разбираться
(«разделяй и властвуй»)
модуль пишет другой
программист
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
// процедура
процедура
// процедура
процедура
// процедура
процедура
// процедура
процедура
...
...
// процедура
процедура
// процедура
процедура
1
2
33
44
N-1
N-1
N
Как связать два файла?
http://kpolyakov.spb.ru
53. Модули
53Алгоритмизация и программирование. Язык C, 11 класс
Модули
alphalist.c
в текущем
каталоге
main()
#include
"wordlist.h"
{
}
?
...
Как подключить
объявления
типов к двум
файлам?
К.Ю. Поляков, Е.А. Ерёмин, 2014
!
Нужно объявить
типы данных!
wordlist.c
#include
"wordlist.h"
void IncSize
(...)
{ ... }
int Find ( ... )
{ ... }
int FindPlace ( ... )
{ ... }
void InsertWord ( ... )
{ ... }
http://kpolyakov.spb.ru
54. Заголовочный файл wordlist.h
54Алгоритмизация и программирование. Язык C, 11 класс
Заголовочный файл wordlist.h
typedef struct {
char word[40];
int count;
} TPair;
typedef struct {
TPair *data;
int capacity;
int size;
} TWordList;
«интерфейс» –
общедоступная
информация:
•объявление типов данных
•объявления процедур и
функций
void IncSize ( TWordList *pL );
int Find ( TWordList L, char word[] );
int FindPlace ( TWordList L, char word[] );
void InsertWord ( TWordList *pL, int k,
char word[] );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
55. Проект (Dev-C++, Windows)
55Алгоритмизация и программирование. Язык C, 11 класс
Проект (Dev-C++, Windows)
исходные
файлы
объектные
файлы
транслятор
alphalist.с
wordlist.с
исполняемый
файл
компоновщик
alphalist.o
wordlist.o
alphalist.exe
стандартные
библиотеки
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
56. Связные списки
56Алгоритмизация и программирование. Язык C, 11 класс
Связные списки
Head
«голова»
данные
данные
конец
списка
данные NULL
узлы могут размещаться в разных местах в памяти
только последовательный доступ
Рекурсивное определение:
• пустой список – это список
• список – это узел и связанный с ним список
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
57. Связные списки
57Алгоритмизация и программирование. Язык C, 11 класс
Связные списки
Циклический список:
Head
данные
данные
Двусвязный список:
Head
NULL данные
данные
«хвост»
данные
данные
Tail
NULL
обход в двух направлениях
сложнее вставка и удаление
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
58. Алгоритмизация и программирование. Язык C
58Алгоритмизация и
программирование.
Язык C
§ 42. Стек, дек, очередь
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
59. Что такое стек?
59Алгоритмизация и программирование. Язык C, 11 класс
Что такое стек?
Стек (англ. stack – стопка) – это линейный список, в
котором элементы добавляются и удаляются только с
одного конца («последним пришел – первым ушел»).
LIFO = Last In – First Out.
Системный стек:
• адреса возврата из подпрограмм
• передача аргументов подпрограмм
• хранение локальных переменных
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
60. Реверс массива
60Алгоритмизация и программирование. Язык C, 11 класс
Реверс массива
Задача. В файле записаны целые числа. Нужно вывести
их в другой файл в обратном порядке.
пока файл не пуст
{
прочитать x
добавить x в стек
}
пока стек не
{
вытолкнуть
записать x
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
5
4
3
2
5
4
3
2
1
1
пуст
число из стека в x
в файл
http://kpolyakov.spb.ru
61. Использование динамического массива
61Алгоритмизация и программирование. Язык C, 11 класс
Использование динамического массива
typedef struct {
int *data;
int capacity;
int size;
} TStack;
указатель
«Втолкнуть» x в стек:
void Push ( TStack *pS, int x )
{
pS->size ++;
if ( pS->size > pS->capacity ) {
pS->capacity += 10;
pS->data = (int*) realloc ( pS->data,
sizeof(int)*pS->capacity );
}
pS->data[pS->size-1] = x;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
62. Использование динамического массива
62Алгоритмизация и программирование. Язык C, 11 класс
Использование динамического массива
«Вытолкнуть» из стека в x :
указатель
int Pop ( TStack *pS )
{
Зачем?
pS->size --;
return pS->data[pS->size];
}
?
Инициализация стека :
void InitStack ( TStack *pS, int capacity )
{
pS->data = (int*) calloc ( capacity,
sizeof(int) );
pS->capacity = capacity;
pS->size = 0;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
63. Использование динамического массива
63Алгоритмизация и программирование. Язык C, 11 класс
Использование динамического массива
Заполнение стека:
FILE *Fin;
InitStack ( &S, 10 );
while ( 1 == fscanf(Fin, "%d", &x) )
Push ( &S, x );
Вывод результата в файл:
while ( S.size > 0 )
{
x = Pop( &S );
fprintf ( Fout, "%d\n", x );
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
64. Вычисление арифметических выражений
64Алгоритмизация и программирование. Язык C, 11 класс
Вычисление арифметических выражений
?
Как компьютер вычисляет арифметические
выражения?
(5+15)/(4+7-1) инфиксная форма (знак операции
между данными)
1920 (Я. Лукашевич): префиксная форма
(знак операции перед данными)
/ + 5 15 - + 4 7 1
/ 20 - + 4 7 1
/ 20 - 11 1
/ 20 10
2
К.Ю. Поляков, Е.А. Ерёмин, 2014
не нужны скобки
первой стоит последняя
операция (вычисляем с конца)
http://kpolyakov.spb.ru
65. Вычисление арифметических выражений
65Алгоритмизация и программирование. Язык C, 11 класс
Вычисление арифметических выражений
(5+15)/(4+7-1)
1950-е: постфиксная форма
(знак операции после данных)
5 15 + 4 7 + 1 - /
20 4 7 + 1 - /
20 11 1 - /
20 10 /
2
!
К.Ю. Поляков, Е.А. Ерёмин, 2014
не нужны скобки
вычисляем с начала
Вычисляем с помощью стека!
http://kpolyakov.spb.ru
66. Использование стека
66Алгоритмизация и программирование. Язык C, 11 класс
Использование стека
5 15 + 4 7 + 1 - /
5
5
1
5
5
15
2
0
+
4
2
0
4
7
4
2
0
7
1
1
2
+
0
1
1
1
2
1
0
1
0
2
0
2
/
• если число – «втолкнуть» в стек
• если операция – выполнить с верхними элементами
стека
!
В стеке остается результат!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
67. Скобочные выражения
67Алгоритмизация и программирование. Язык C, 11 класс
Скобочные выражения
Задача. Вводится символьная строка, в которой записано
некоторое (арифметическое) выражение,
использующее скобки трёх типов: ( ), [ ] и { }.
Проверить, правильное ли расставлены скобки.
()[{()[]}]
[()
[()}
)(
([)]
Для одного типа скобок:
счётчик
?
0
(
)
(
(
)
(
(
)
)
)
1
0
1
2
1
2
3
2
1
0
Когда выражение правильное?
• счётчик всегда 0
• в конце счётчик = 0
К.Ю. Поляков, Е.А. Ерёмин, 2014
!
({[)}]
Для разных скобок
не работает!
http://kpolyakov.spb.ru
68. Скобочные выражения (стек)
68Алгоритмизация и программирование. Язык C, 11 класс
Скобочные выражения (стек)
(
[
(
(
[
(
[
(
{
[
(
(
{
[
(
{
[
(
[
(
(
(
[
(
)
{
(
)
}
]
• если открывающая скобка – «втолкнуть» в стек
• если закрывающая скобка – снять парную со стека
?
)
Когда выражение правильное?
• когда встретили закрывающую скобку, на вершине
стека лежит соответствующая открывающая
• в конце работы стек пуст
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
69. Скобочные выражения (стек)
Алгоритмизация и программирование. Язык C, 11 класс69
Скобочные выражения (стек)
Модель стека:
typedef struct {
char *data;
int capacity;
int size;
} TStack;
Cтек пуст:
bool isEmpty ( TStack S )
{
return S.size == 0;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
70. Скобочные выражения (стек)
70Алгоритмизация и программирование. Язык C, 11 класс
Скобочные выражения (стек)
Константы и переменные:
const char L[] =
R[] =
char str[80]; //
TStack S;
//
bool err;
//
int i;
char c, *p;
Вывод результата:
"([{", // открывающие
")]}"; // закрывающие
рабочая строка
стек
была ли ошибка?
if ( ! err )
printf ( "Скобки расставлены верно." );
else
printf ( "Скобки расставлены неверно." );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
71. Скобочные выражения (стек)
71Алгоритмизация и программирование. Язык C, 11 класс
Скобочные выражения (стек)
for ( i == 0; i < strlen(str); i++ ) {
p = strchr
strchr ( L,
L, str[i]
str[i] );
);
открывающую
if ( p!= NULL )
скобку в стек
Push (( &S, str[i] );
p = strchr
strchr ( R, str[i] );
если
if ( p!= NULL ) {
закрывающая
if ( isEmpty (( S ) )
скобка…
err = true;
else {
если не та
c = Pop
Pop ( &S );
скобка…
if ( p-R!= strchr(L,c)-L
strchr(L,c)-L )
err = true;
}
if ( err ) break;
}
Что ещё?
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
72. Что такое очередь?
72Алгоритмизация и программирование. Язык C, 11 класс
Что такое очередь?
Очередь – это линейный список,
для которого введены две
операции:
• добавление элемента в конец
• удаление первого элемента
FIFO = Fist In – First Out.
Применение:
• очереди сообщений в операционных системах
• очереди запросов ввода и вывода
• очереди пакетов данных в маршрутизаторах
•…
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
73. Заливка области
73Алгоритмизация и программирование. Язык C, 11 класс
Заливка области
Задача. Рисунок задан в виде матрицы A, в которой
элемент A[y][x] определяет цвет пикселя на
пересечении строки y и столбца x. Перекрасить в цвет
2 одноцветную область, начиная с пикселя (x0,y0).
0 1 2 3 4
0
1
2
3
4
0
1
0
3
0
1
1
1
3
1
0
1
0
1
1
1
2
2
2
0
К.Ю. Поляков, Е.А. Ерёмин, 2014
1
2
2
2
0
0 1 2 3 4
0
(1,2)
1
2
3
4
0
2
0
3
0
2
2
2
3
1
0
2
0
1
1
1
2
2
2
0
1
2
2
2
0
http://kpolyakov.spb.ru
74. Заливка: использование очереди
74Алгоритмизация и программирование. Язык C, 11 класс
Заливка: использование очереди
добавить в очередь точку (x00,y00)
запомнить цвет начальной точки
пока очередь не пуста
{
взять из очереди точку (x,y)
если A[y][x] = цвету начальной точки то
{
A[y][x] = 2;
добавить в очередь точку (x-1,y)
добавить в очередь точку (x+1,y)
добавить в очередь точку (x,y-1)
добавить в очередь точку (x,y+1)
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
75. Очередь (динамический массив)
75Алгоритмизация и программирование. Язык C, 11 класс
Очередь (динамический массив)
typedef struct {
int x, y;
} TPoint;
typedef struct {
TPoint *data;
int capacity;
int size;
} TQueue;
структура
«точка»
структура «очередь»
(динамический массив)
Построение структуры «точка»:
TPoint Point (( int x, int
int y ))
{
TPoint P;
P.x == x; P.y = y;
return P;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
76. Очередь (динамический массив)
76Алгоритмизация и программирование. Язык C, 11 класс
Очередь (динамический массив)
Добавить точку в очередь:
void Put ( TQueue *pQ, TPoint P )
{
расширить,
если нужно
pQ->size ++;
if ( pQ->size > pQ->capacity ) {
pQ->capacity += 10;
pQ->data =(TPoint*) realloc ( pQ->data,
sizeof(TPoint)*pQ->capacity );
}
pQ->data[pQ->size-1] = P;
}
1
2
3
4
0
1
2
3
К.Ю. Поляков, Е.А. Ерёмин, 2014
5
4
http://kpolyakov.spb.ru
77. Очередь (динамический массив)
77Алгоритмизация и программирование. Язык C, 11 класс
Очередь (динамический массив)
Получить первую точку в очереди:
TPoint Get ( TQueue *pQ )
{
TPoint P = pQ->data[0];
int i;
уменьшить
размер
pQ->size --;
for ( i = 0; i < pQ->size; i++ )
pQ->data[i] = pQ->data[i+1];
return P;
}
1
2
3
4
5
0
1
2
3
4
К.Ю. Поляков, Е.А. Ерёмин, 2014
?
продвинуть
оставшиеся
элементы
Что плохо?
http://kpolyakov.spb.ru
78. Заливка
78Алгоритмизация и программирование. Язык C, 11 класс
Заливка
Константы и переменные:
const int XMAX = 5, YMAX = 5,
NEW_COLOR = 2;
int A[YMAX][XMAX];
// матрица
TQueue Q;
// очередь
int i, j, x0, y0, color;
TPoint pt;
Начало программы:
// заполнить матрицу A
y0 = 0; x0 = 1;
// начать заливку отсюда
color = A[y0][x0]; // цвет начальной точки
Put ( &Q, Point(x0,y0) );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
79. Заливка (основной цикл)
79Алгоритмизация и программирование. Язык C, 11 класс
Заливка (основной цикл)
пока очередь не пуста
while ( ! isEmpty(Q) ) {
pt = Get ( &Q );
if ( A[pt.y][pt.x] == color ) {
A[pt.y][pt.x] = NEW_COLOR;
if ( pt.x > 0 )
Put ( &Q, Point(pt.x-1,pt.y) );
if ( pt.y > 0 )
Put ( &Q, Point(pt.x,pt.y-1) );
if ( pt.x < XMAX-1 )
Put ( &Q, Point(pt.x+1,pt.y) );
if ( pt.y < YMAX-1 )
Put ( &Q, Point(pt.x,pt.y+1) );
}
Что можно улучшить?
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
80. Очередь: статический массив
80Алгоритмизация и программирование. Язык C, 11 класс
Очередь: статический массив
голова
Head
Tail
хвост
0
1
2
3
4
Удаление элемента:
Head
N-1
5
Tail
0
N-1
1
2
3
4
Добавление элемента:
Head
5
Tail
0
N-1
2
3
4
не двигаем элементы
К.Ю. Поляков, Е.А. Ерёмин, 2014
5
6
нужно знать размер
http://kpolyakov.spb.ru
81. Очередь: статический массив
81Алгоритмизация и программирование. Язык C, 11 класс
Очередь: статический массив
Замыкание в кольцо:
Tail
Head
1
7
N
8
9
1
Очередь заполнена:
Tail
2
3
4
5
Head
1
7
6
N
8
9
10 11 12
Очередь пуста:
1
2
3
4
5
6
Tail Head
1
N
!
Вариант: хранить размер очереди в переменной!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
82. Что такое дек?
82Алгоритмизация и программирование. Язык C, 11 класс
Что такое дек?
Дек – это линейный список, в котором можно добавлять и
удалять элементы как с одного, так и с другого конца.
Моделирование:
• статический массив (кольцо)
• динамический массив
• связный список
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
83. Алгоритмизация и программирование. Язык C
83Алгоритмизация и
программирование.
Язык C
§ 43. Деревья
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
84. Что такое дерево?
84Алгоритмизация и программирование. Язык C, 11 класс
Что такое дерево?
«Сыновья» А: B, C.
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G. «Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
85. Рекурсивные определения
85Алгоритмизация и программирование. Язык C, 11 класс
Рекурсивные определения
1)
2)
пустая структура – это дерево
дерево – это корень и несколько связанных с ним
отдельных (не связанных между собой) деревьев
Двоичное (бинарное) дерево:
1) пустая структура – это двоичное дерево
2) двоичное дерево – это корень и два связанных с ним
отдельных двоичных дерева («левое» и «правое»
поддеревья)
Применение:
• поиск в большом массиве неменяющихся данных
• сортировка данных
• вычисление арифметических выражений
• оптимальное сжатие данных (метод Хаффмана)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
86. Деревья поиска
86Алгоритмизация и программирование. Язык C, 11 класс
Деревья поиска
Ключ – это значение, связанное с узлом дерева, по
которому выполняется поиск.
6
3
1
8
4
7
9
• слева от узла – узлы с
меньшими или равными
ключами
• справа от узла – узлы с
большими или равными
ключами
O(log N)
?
Сложность поиска?
К.Ю. Поляков, Е.А. Ерёмин, 2014
Двоичный поиск O(log N)
Линейный поиск O(N)
http://kpolyakov.spb.ru
87. Обход дерева
87Алгоритмизация и программирование. Язык C, 11 класс
Обход дерева
Обойти дерево «посетить» все узлы по одному разу.
список узлов
КЛП – «корень-левый-правый» (в прямом порядке):
посетить корень
обойти левое поддерево
обойти правое поддерево
ЛКП – «левый-корень-правый» (симметричный):
посетить корень
обойти левое поддерево
обойти правое поддерево
ЛПК – «левый-правый-корень» (в обратном порядке):
посетить корень
обойти левое поддерево
обойти правое поддерево
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
88. Обход дерева
88Алгоритмизация и программирование. Язык C, 11 класс
Обход дерева
(1+4)*(9-5)
*
+
«в
глубину»
1
4
9
5
КЛП: * + 1 4 – 9 5
префиксная форма
ЛКП: 1 + 4 * 9 - 5
инфиксная форма
ЛПК: 1 4 + 9 5 - *
постфиксная форма
Обход «в ширину»: «сыновья», потом «внуки», …
* + - 1 4 9 5
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
89. Обход КЛП – обход «в глубину»
89Алгоритмизация и программирование. Язык C, 11 класс
Обход КЛП – обход «в глубину»
записать в стек корень дерева
пока стек не пуст
{
выбрать узел V с вершины стека
посетить узел V
если у узла V есть правый сын то
добавить в стек правого сына V
если у узла V есть левый сын то
добавить в стек левого сына V
}
?
Почему сначала добавить правого сына?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
90. Обход КЛП – обход «в глубину»
90Алгоритмизация и программирование. Язык C, 11 класс
Обход КЛП – обход «в глубину»
(1+4)*(9-5)
*
+
4
1
*
9
+
-
1
4
-
4
-
*
+
1
К.Ю. Поляков, Е.А. Ерёмин, 2014
5
-
9
5
5
4
–
9
5
http://kpolyakov.spb.ru
91. Обход «в ширину»
91Алгоритмизация и программирование. Язык C, 11 класс
Обход «в ширину»
записать в очередь корень дерева
пока очередь не пуста
{
выбрать узел V из очереди
посетить узел V
если у узла V есть левый сын то
добавить в очередь левого сына V
если у узла V есть правый сын то
добавить в очередь правого сына V
}
?
Почему сначала добавить левого сына?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
92. Обход «в ширину»
92Алгоритмизация и программирование. Язык C, 11 класс
Обход «в ширину»
(1+4)*(9-5)
*
+
4
1
голова
очереди
*
К.Ю. Поляков, Е.А. Ерёмин, 2014
9
5
+
4
1
-
5
9
4
1
5
9
4
5
9
5
*
+
-
1
4
9
5
http://kpolyakov.spb.ru
93. Вычисление арифметических выражений
93Алгоритмизация и программирование. Язык C, 11 класс
Вычисление арифметических выражений
?
40–2*3–4*5
Что будет в корне дерева?
В корень дерева нужно поместить последнюю из
операций с наименьшим приоритетом.
-
-
40–2*3
4*5
-
-
40
*
2*3
*
40
4
К.Ю. Поляков, Е.А. Ерёмин, 2014
*
2
4
5
3
5
http://kpolyakov.spb.ru
94. Вычисление арифметических выражений
94Алгоритмизация и программирование. Язык C, 11 класс
Вычисление арифметических выражений
Построение дерева:
найти последнюю выполняемую
если операций нет то
{
создать узел-лист
выход
}
поместить операцию в корень
построить левое поддерево
построить правое поддерево
!
операцию
дерева
Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
95. Вычисление арифметических выражений
95Алгоритмизация и программирование. Язык C, 11 класс
Вычисление арифметических выражений
Вычисление по дереву:
n1 = значение
значение левого
левого поддерева
поддерева
n2 = значение
значение правого
правого поддерева
поддерева
результат = операция(n1, n2)
!
Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
96. Использование связанных структур
96Алгоритмизация и программирование. Язык C, 11 класс
Использование связанных структур
Дерево – нелинейная структура динамический
массив неудобен!
данные
данные NULL NULL
данные NULL NULL
ссылка
вперёд
typedef struct TNode *PNode;
typedef struct TNode
новый тип:
{
адрес узла
char data[20];
PNode left;
ссылки на
PNode right;
сыновей
} TNode;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
97. Работа с памятью
97Алгоритмизация и программирование. Язык C, 11 класс
Работа с памятью
PNode p;
// указатель на узел
Выделить память для узла:
p = (PNode) calloc ( 1, sizeof(TNode) );
Обращение к новому узлу (по указателю):
strcpy ( p->data, s );
p->left = NULL;
p->right = NULL;
Освобождение памяти:
free(p);
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
98. Основная программа
98Алгоритмизация и программирование. Язык C, 11 класс
Основная программа
main()
{
PNode T;
char s[80];
// ввести строку s
T = MakeTree ( s );
printf ( "Результат: %d", Calc(T) );
}
!
Нужно построить MakeTree и Calc!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
99. Построение дерева
99Алгоритмизация и программирование. Язык C, 11 класс
Построение дерева
PNode
PNode MakeTree ( char s[] )
вернёт адрес
{{
нового
int
int k;
дерева
пустая
PNode
PNode Tree;
строка!
char
char sLeft[80] = "";
Tree
Tree = (PNode) calloc ( 1, sizeof(TNode) );
kk = LastOp ( ss );
);
if ( k == -1 )) {{
// новый узел –– лист
лист (число)
(число)
}
else
else {
// новый узел –– операция
операция
// построить
построить поддеревья
поддеревья
}
return
return Tree;
}}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
100. Построение дерева
100Алгоритмизация и программирование. Язык C, 11 класс
Построение дерева
Новый узел – лист:
strcpy ( Tree->data, s );
Tree->left = NULL;
нет сыновей!
Tree->right = NULL;
Новый узел – операция:
Tree->data[0] = s[k];
один символ!
Tree->data[1] = '\0';
strncpy ( sLeft, s, k );
Tree->left =
MakeTree ( sLeft ); Рекурсия!
MakeTree ( sLeft );
Tree->right
=
MakeTree
MakeTree ( &s[k+1] );
( &s[k+1] );
k
*
s
!
sLeft
К.Ю. Поляков, Е.А. Ерёмин, 2014
дальше – нули!
http://kpolyakov.spb.ru
101. Вычисление по дереву
101Алгоритмизация и программирование. Язык C, 11 класс
Вычисление по дереву
int
int Calc
Calc (( PNode
PNode Tree
Tree ))
{{
это число
(лист)
int
int n1,
n1, n2,
n2, res;
res;
if
if (( Tree->left
Tree->left ==
== NULL
NULL ))
res
res == atoi
atoi (( Tree->data
Tree->data );
);
else
else {{
n1
n1 == Calc
Calc (( Tree->left
Tree->left );
);
Рекурсия!
n2
n2 == Calc
Calc (( Tree->right
Tree->right );
);
switch
switch (( Tree->data[0]
Tree->data[0] )) {{
case
case '+':
'+': res
res == n1
n1 ++ n2;
n2; break;
break;
case
case '-':
'-': res
res == n1
n1 -- n2;
n2; break;
break;
case
case '*':
'*': res
res == n1
n1 ** n2;
n2; break;
break;
case
case '/':
'/': res
res == n1
n1 // n2;
n2; break;
break;
default:
default: res
res == 99999;
99999;
}}
}}
return
return res;
res;
}}
!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
102. Приоритет операции
Алгоритмизация и программирование. Язык C, 11 класс102
Приоритет операции
int Priority ( char op )
{
switch ( op )
{
case '+':
case '-': return 1;
case '*':
case '/': return 2;
}
return 100;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
103. Последняя выполняемая операция
103Алгоритмизация и программирование. Язык C, 11 класс
Последняя выполняемая операция
int LastOp ( char s[] )
вернёт номер
{
символа
int i, minPrt, res;
minPrt = 50; // любое между 2 и 100
res = -1;
for ( i = 0; i < strlen(s); i++ )
if ( Priority(s[i]) <=
<= minPrt )
{
minPrt = Priority(s[i]);
res = i;
Почему <=?
}
return res;
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
104. Двоичное дерево в массиве
104Алгоритмизация и программирование. Язык C, 11 класс
Двоичное дерево в массиве
0
--
**
A[0]
A[1]
A[2]
3
4
5
6
7
8
9
10
3
4
5
6
7
8
9
10
5
6
7
8
9
10
7
8
9
10
**
0
22
2
- - *
-40
40
1
44
55
33
2
- - * 40 *
0
1
2
3
4
- - * 40 * 4 5
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
1
0
1
2
3
4
5
6
- - * 40 * 4 5
A[4]
К.Ю. Поляков, Е.А. Ерёмин, 2014
A[9]
A[10]
A[i]
2 3
A[2*i+1]
?
A[2*i+2]
?
http://kpolyakov.spb.ru
105. Алгоритмизация и программирование. Язык C
105Алгоритмизация и
программирование.
Язык C
§ 44. Графы
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
106. Что такое граф?
106Алгоритмизация и программирование. Язык C, 11 класс
Что такое граф?
Граф – это набор вершин и связей между ними (рёбер).
Матрица смежности:
A
B
C
D
Список смежности:
( A(B, C),
B(A, C, D),
C(A, B, С, D),
D(B, C) )
К.Ю. Поляков, Е.А. Ерёмин, 2014
A
0
1
1
0
B
1
0
1
1
C
1
1
1
1
D
0
1
1
0
петля
http://kpolyakov.spb.ru
107. Связность графа
107Алгоритмизация и программирование. Язык C, 11 класс
Связность графа
Связный граф – это граф, между любыми вершинами
которого существует путь.
A
B
C
D
A
C
B
D
компоненты связности
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
108. Дерево – это граф?
108Алгоритмизация и программирование. Язык C, 11 класс
Дерево – это граф?
Дерево – это связный граф без циклов (замкнутых путей).
A
C
B
D
ABC
BCD
ABDC
CCC…
К.Ю. Поляков, Е.А. Ерёмин, 2014
дерево
http://kpolyakov.spb.ru
109. Взвешенные графы
109Алгоритмизация и программирование. Язык C, 11 класс
Взвешенные графы
A
12
B
8
C
5
6
4
D
2
Весовая матрица:
A
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4
вес ребра
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
110. Ориентированные графы (орграфы)
110Алгоритмизация и программирование. Язык C, 11 класс
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра
называю дугами.
A
8
5
12
B
!
6
A
C
4
D
A
B
C
D
12
B
12
C
8
5
D
6
4
4
Весовая матрица может быть несимметрична!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
111. Жадные алгоритмы
111Алгоритмизация и программирование. Язык C, 11 класс
Жадные алгоритмы
Жадный алгоритм – это многошаговый алгоритм, в
котором на каждом шаге принимается решение,
лучшее в данный момент.
Задача. Найти кратчайший маршрут из А в F.
2
B
9
A
1
К.Ю. Поляков, Е.А. Ерёмин, 2014
C
7
8
4
D
1
3
E
F
5
http://kpolyakov.spb.ru
112. Жадные алгоритмы
112Алгоритмизация и программирование. Язык C, 11 класс
Жадные алгоритмы
Задача. Найти кратчайший маршрут из А в F.
2
9
A
4
?
!
B
C
7
8
1
D
1
3
E
F
2
Это лучший маршрут?
Жадный алгоритм не всегда даёт наилучшее
решение!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
113. Задача Прима-Крускала
113Алгоритмизация и программирование. Язык C, 11 класс
Задача Прима-Крускала
Задача. Между какими городами нужно проложить линии
связи, чтобы все города были связаны в одну систему
и общая длина линий связи была наименьшей?
(минимальное остовное дерево)
2
A
B
9
7
8
D
1
3
F
2
4
C
E
1
Алгоритм Крускала:
Лучшее решение!
• начальное дерево – пустое
• на каждом шаге добавляется ребро минимального
веса, которое ещё не входит в дерево и не
приводит к появлению цикла
!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
114. Раскраска вершин
114Алгоритмизация и программирование. Язык C, 11 класс
Раскраска вершин
2
B
9
A
4
C
7
8
1
D
1
3
E
F
2
for (i = 0; i < N; i ++) col[i] = i;
каждой
вершине
свой цвет
Сделать N-1 раз:
• ищем ребро минимальной длины среди всех рёбер,
концы которых окрашены в разные цвета;
• найденное ребро (iMin,jMin) добавляется в список
выбранных, и все вершины, имеющие цвет
col[jMin], перекрашиваются в цвет col[iMin].
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
115. Раскраска вершин
115Алгоритмизация и программирование. Язык C, 11 класс
Раскраска вершин
Данные:
const int N = 6;
int W[N][N]; // весовая матрица
int col[N]; // цвета вершин
// номера вершин для выбранных ребер
int ostov[N-1][2];
int i, j, k, iMin, jMin, min, c;
Вывод результата:
for ( i = 0; i < N-1; i ++ )
printf ( "(%d,%d)\n", ostov[i][0],
ostov[i][1] );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
116. Раскраска вершин
116Алгоритмизация и программир