Информационные технологии и основы программирования

1.

Информационные технологии
и основы программирования
Часть 2 «Структуры данных и алгоритмы»
Целебровская Марина Юрьевна,
к.п.н., доцент кафедры Теоретической и прикладной информатики
корпус 1, ауд. 201
[email protected]

2.

Информационные технологии и основы
программирования
• Лекции – 18 часов
• Лабораторные работы – 5 работ
• Курсовая работа
• В конце семестра – экзамен

3.

Формирование рейтинга в семестре
№п/п
Вид учебной деятельности
Максимальное
количество баллов
Минимальное
количество
баллов
Срок
представления и
защиты (неделя)
1
Лабораторная работа № 1
Лабораторная работа № 2
Лабораторная работа № 3
Лабораторная работа № 4
Лабораторная работа № 5
Итого по текущему рейтингу
12
12
12
12
12
60
7
6
5
6
6
30
3
7
10
13
17
2
3
4
Экзамен
Итого за семестр
Курсовая Работа
Итого за семестр
40
100
100 (85) (70)
100
20
50
50
50
15
• Чтобы получить «4», нужно набрать 72 балла
• Чтобы получить «5», нужно набрать 90 баллов
• Чтобы получить зачет (допуск к зачету), нужно набрать 50 баллов

4.

Литература
1. Структуры данных и алгоритмы: учебное пособие. Новосиб. гос. техн. ун-т ; [сост. Тракимус Ю.В., В. П.
Хиценко]. - Новосибирск, 2022. - 127 с. : ил., табл.
2. Структуры данных и алгоритмы : методические указания к курсовой работе для 1 курса ФПМиИ
(направление 010500 - Прикладная математика и информатика, специальность 010503 Математическое обеспечение и администрирование информационных систем) дневного отделения /
Новосиб. гос. техн. ун-т ; [сост. В. П. Хиценко, Т. А. Шапошникова]. - Новосибирск, 2008. - 53, [2] с. :
ил., табл.
3. Хусаинов Б. С. Структуры и алгоритмы обработки данных. Примеры на языке Си : учебное
пособие / Б. С. Хусаинов. - М., 2004. - 463, [1] с. : ил. + 1 CD-ROM. - Рекомендовано УМО.
4. Павловская Т. А. C/C++. Программирование на языке высокого уровня : учебник для вузов / Т. А.
Павловская. - СПб., 2007. - 460 с. : ил.. - На тит. л.: Издательская программа 300 лучших учебников
для высшей школы в честь 300-летия Санкт-Петербурга. - Рекомендовано МО.
5. Вирт Н. Алгоритмы и структуры данных. - М., 1989. - 360 с. : ил.

5.

Типа данных в языке программирования

6.

Типы данных
Скалярные
Данные рассматриваются как
целые простые неделимые
объекты – атомы данных
типы данных
Структурированный
Данные рассматриваются как
составные агрегаторные
объекты, элементы которых
могут быть данными одного и
того же или различного типа.
Значения этого типа
представляют собой
совокупность значений
компонентов, относящихся к
составляющим типам и наз.
Составными.

7.

Структурированные типы данных
Фундаментальные структуры: массив,
запись, множество, последовательные
файлы (последовательности)

8.

Структурированные типы данных

9.

Структурированные типы данных

10.

Структура хранения данных – представление определенной
структуры данных в памяти машины

11.

Структура хранения данных

12.

Данные в программах
Данные со статической структурой это данные, взаиморасположение и
взаимосвязи элементов которых,
всегда остаются постоянными (во
время выполнения программы ничего
не меняется в структуре этих данных).
Данные с динамической структуройэто данные, внутреннее строение
которых, формируется по какомулибо закону, но количество их
элементов, взаиморасположение и
взаимосвязи могут изменяться во
время выполнения программы или
вообще отсутствовать. Перед
использованием динамические
данные должны быть
инициализированы, т. е. им
необходимо задать начальное
значение, как правило, это значение
«пусто».

13.

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

14.

Динамическая структура данных
• количество элементов структуры может не фиксироваться;
• размерность структуры может меняться в процессе выполнения программы;
• в процессе выполнения программы может меняться характер взаимосвязи между элементами
структуры;
• ей выделяется память в процессе выполнения программы;
• она не имеет имени;
• структуре данных ставится в соответствие статическая переменная типа указатель (ее значение –
адрес этого динамического объекта) посредством которой осуществляется доступ к динамической
структуре.
Данные динамической структуры могут иметь связное и несвязное представление в оперативной
памяти. Несвязное (последовательное, линейное) представление возможно как в статической, так и в
динамической памяти. При отображении динамической структуры данных в статической памяти
приходится вносить ограничение на размер данных (максимальное число элементов в значении
структуры) и обеспечивать возможность изменения фактической размерности в процессе выполнения
программы. Связное представление возможно только в динамической памяти.

15.

Тип Указатель
Значением типа указатель является адрес участка оперативной па
мяти, выделенного для объекта (переменной, константы, функции)
конкретного типа (можно говорить, что значение типа указатель –
это ссылка на объект). Связь указателя p с объектом графически
представляется следующим образом:

16.

Тип Указатель
По указателю осуществляется обращение (доступ) к объекту. Определение
переменной типа указатель:
type *имя_указателя;
Здесь type – обозначение типа, на который будет указывать переменная с именем
(идентификатором) имя_указателя. Символ ‘*’ является признаком типа указатель.
При определении переменной-указателя можно выполнить инициализацию:
type *имя_указателя инициализатор;
Инициализатор имеет две формы записи, поэтому допустимо:
type *имя_указателя = инициализирующее_ выражение;
type *имя_указателя(инициализирующее_ выражение);

17.

18.

Тип Указатель
Переменной типа указатель (далее - указатель) можно задать значение следующим образом:
• присваивая ей адрес объекта с помощью операции & (тип объекта должен быть тот же, что и тип объекта, на который
ссылается указатель);
• присваивая ей значение другой переменной или выражения типа указатель (типы объектов, на которые они
ссылаются должны быть одинаковыми);
• с помощью операции new.
Над указателями допускается выполнение следующих операций:
Разыменование - это операция взятия значения по адресу, при помощи оператора "*" (звёздочка);
присваивание;
сложение и вычитание;
инкремент и декремент. Инкремент ++ – это увеличение на единицу. Декремент - - – это уменьшение на единицу;
операции отношения;
получение адреса (&).
Все операции применимы к указателям на объекты одного типа и к указателю и целой константе, в
противном случае требуется явное преобразование типов.
Операция сложения допустима только для указателя и целочисленного значения.
Вычитая два указателя одного типа, можно получить “расстояние” между двумя участками памяти.
“Расстояние“ определяется в единицах, кратных размеру памяти объекта того типа, к которому отнесен
указатель.

19.

Тип Указатель

20.

Операция new позволяет выделить свободный участок в оперативной памяти (динамической), размеры
которого соответствуют типу данных, определяемому именем типа. В случае успешного выполнения
операция new возвращает адрес начала выделенного участка памяти, таким образом, создан
(порожден) динамический объект. Если участок нужного размера не может быть выделен (нет
свободной памяти нужного размера), то операция new возвращает нулевое значение адреса (NULL). В
случае инициализации в выделенный участок заносится значение, определяемое инициализатором, т. е.
динамическому объекту присваивается начальное значение, иначе значение динамического объекта не
определено.

21.

Уничтожение динамического объекта (освобождение памяти, выделенной под динамическую переменную)
осуществляется операцией delete:
delete имя_указателя;
Здесь указатель адресует освобождаемый участок памяти, ранее выделенный с помощью операции new. После
выполнения операции delete значение указателя становится неопределенным (хотя в некоторых реализациях языка
может и не меняться).
Для освобождения памяти, выделенной для массива, используется следующая модификация этой операции:
delete [] имя_указателя;
При уничтожении динамического объекта следует не оставлять “висячих” ссылок. “Висячая” ссылка – это ссылка на
несуществующий объект.
Над динамическими объектами выполняются операции, допустимые для типа данного динамического объекта.
...
int *a = new int, *b = new int;
*a = 15;
*b = -1;
a = b; delete b;
...

22.

...
int *a = new int, *b = new int;
*a = 15;
*b = -1;
a = b; delete b;
...
Память, занимаемая динамическим объектом, на
который указывают a и b освобождена, но указатель a
сохранил значение адреса объекта. Указатель a –
“висячая” ссылка.

23.

Векторы

24.

Векторы

25.

Для того, чтобы обеспечить хранение данных в динамическом векторе,
необходимо выполнить

26.

Пример программы организации хранения структуры данных в векторной памяти и обработки ее
элементов

27.

Список

28.

Список

29.

Список

30.

Структура Список
Список – это конечное множество (возможно пустое) данных,
имеющих некоторый общий смысл для решаемой задачи,
размерность множества может быть заранее неизвестна.
Рекурсивное определение списка:
<список> = <пустой список> │ <непустой список>
<непустой список> = <элемент из множества объектов>│
<непустой список> <элемент из множества объектов>
Рекурсивное определение списка отражает рекурсивную природу
самой динамической структуры.

31.

Линейный список
Линейный список – это состоящее из n ⩾ 0 элементов (x1, x2, … , xn) множество, структурные свойства которого
ограничиваются линейным относительным положением элементов. Другими словами, если n > 0, то существует
элемент, который является первым – x1, и есть последний элемент – xn, а для всех 1< k < n для xk есть следующий
за ним элемент – x k + 1 и предшествующий ему элемент – x k - 1.
В статической памяти список можно представить как множество данных, которые располагаются
последовательно и непрерывно друг за другом и это множество дополнено информацией, которая позволяет
вносить изменения в динамическую структуру данных. Такой список будем называть статическим списком. На
языке C статический список можно представить неоднородной структурой:
• struct list
•{
• int n;
• type elem[k];
• };
• n – количество элементов в списке, k-размер структуры
Это несвязный список!

32.

Линейный односвязный (однонаправленный)список
В динамической памяти список можно представить как множество данных, расположенных в памяти
произвольно (в процессе их создания) и связанных между собой указателями. Будем называть такой
список (условно) – динамический список.

33.

Линейный односвязный (однонаправленный)список
При задании динамического списка нужно описать его звено с использованием структуры. Задание типа
элемента списка:
Пример определения 1-го элемента списка:

34.

Линейный односвязный (однонаправленный)список

35.

Формирование ациклического списка с заглавным звеном
struct list
{
list *next;char elem;
} *l;
void main()
{
char c = 0;
List *p;
// Создание заглавного звена:
l = new list; // l получил значение адреса
// заглавного звена,
l->next = NULL; // его полю next присвоено
// значение пустой ссылки.
// Таким образом, создан пустой
// список с заглавным звеном.
list *p = l;// Текущему указателю p присвоена
// ссылка на заглавное звено
while ((c = getchar()) != ‘\n’)
{
p->next = new list; // Создание очередного звена,
// поле next текущего звена
// получило значение адреса
// вновь созданного звена.
p = p->next; // Текущему указателю p присвоена
// ссылка на очередное звено.
p->elem = c; // Информационное поле elem текущего
}
// звена получило значение символа c.
p->next = NULL; // Определение конца списка:
// ccылочному полю последнего
}
// сформированного звена (хвост списка)
// присвоено значение пустой ссылки.

36.

Линейный односвязный (однонаправленный)список
Основными операциями обработки односвязного списка являются:
- поиск заданного элемента по его значению или порядковому номеру; операция
заканчивается, когда элемент найден или просмотрен весь список (если элемента нет);
результат операции должен определять, есть ли элемент в списке или нет и, если есть, то
возможно его адрес или значение;
- включение (вставка) в список нового элемента перед или после заданного элемента (в том
числе перед первым элементом или после последнего); включению, как правило,
предшествует поиск элемента после и/или перед которым происходит включение; при
включении элемента перед первым в список без заглавного звена меняется заголовок списка;
при включении после некоторого элемента меняется ссылочное поле у элемента, за которым
происходит включение, для этого надо определять ссылку на элемент за которым происходит
включение;
- удаление (исключение) заданного элемента из списка (в том числе удаление первого
элемента или последнего); исключению, как правило, предшествует поиск, исключаемого
элемента; результатом поиска должна быть ссылка на элемент, предшествующий
исключаемому, так как при удалении элемента из списка меняется ссылочное поле у
элемента, предшествующего удаляемому; при удалении первого элемента в списке без
заглавного звена меняется заголовок списка;
- определение числа звеньев списка;
- копирование списка;
- объединение списков;
- упорядочение элементов списка по значению информационного поля

37.

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

38.

Линейный двусвязный список

39.

Операции, выполняемые над двусвязным списком
Основные операции, выполняемые над двусвязным списком, те же, что и для односвязного списка. Так
как двусвязный список более гибкий, чем односвязный, то при включении элемента в список, можно
использовать указатель как на элемент, за которым происходит включение, так и указатель на элемент,
перед которым происходит включение.
При исключении элемента из списка можно использовать как указатель на сам исключаемый элемент,
так и указатель на элемент, предшествующий или следующий за исключаемым. Но, так как элемент
двусвязного списка имеет два указателя, то при выполнении операций включения/исключения элемента
надо изменять больше связей, чем в односвязном списке.
Поиск элемента в двусвязном списке можно вести:
а) просматривая элементы от начала к концу списка;
б) просматривая элементы от конца списка к началу;
в) просматривая список в обоих направлениях одновременно: от начала к середине списка и от конца к
середине (учитывая, что элементов в списке может быть четное или нечетное количество).

40.

Линейные структуры данных
• Стек
• Очередь
• Дек

41.

42.

Стек

43.

Стек
Стек состоит из ячеек, которые представлены в виде
структуры, содержащей какие-либо данные и
указатель типа данной структуры на следующий
элемент.
На данной картинке схематично изображен стек. Блок
вида «Данные/*next» и есть наша ячейка. *next, как мы
видим, указывает на следующий элемент, другими
словами указатель *next хранит адрес следующей
ячейки. Указатель *TOP указывает на вершину стек, то
есть хранит её адрес. Это динамический стек!

44.

Стек

45.

Определение стека
Статический стек
Динамический стек
s.top=-1 Стек пуст
s.top=n-1 Стек полон
s.top=0 В стеке 1 элемент
s/top=-1 При взятии из стека единственного элемента
S –указатель на вершину стека
S=NULL для создания пустого динамического списка
S->elem обращение к значению элемента в вершине
динамического стека

46.

Стек. Операции над стеками.
struct stack
{
int
top;
char
el[n];
};
- операция создать стек состоит в инициализации
стека пустым значением (выделение памяти под стек
осуществляется в вызывающей подпрограмме)
void create(stack *s)
{
s->top = -1;
}
- операция проверить стек на пустоту
int empty(stack s)
{
return s.top == -1;
}

47.

Стек. Операции над стеками.
операция положить элемент в стек
int push(char c, stack *s)
{
if (s->top != n - 1)
{
s->el[s->top++]
= c; return 1;
}
else
return 0;
}

48.

Стек. Операции над стеками.

49.

50.

51.

52.

Применение стеков при разработке
приложений

53.

Применение стеков при разработке
приложений

54.

55.

56.

Очередь
Очереди очень похожи на стеки. Они также не дают доступа к
произвольному элементу, но, в отличие от стека, элементы
кладутся (enqueue) и забираются (dequeue) с разных концов. Такой
метод называется «первый вошел, первый вышел» (First-In-First-Out
или FIFO). То есть забирать элементы из очереди мы будем в том же
порядке, что и клали. Как реальная очередь или конвейер.
Очереди часто используются в программах для реализации буфера, в
который можно положить элемент для последующей обработки,
сохраняя порядок поступления. Например, если база данных
поддерживает только одно соединение, можно использовать очередь
потоков, которые будут, как ни странно, ждать своей очереди на доступ
к БД.

57.

Очередь

58.

Очередь
• Очередь с несвязным представлением, отображаемую в статической памяти, будем называть
статическая очередь.
• В статической памяти очередь можно представить как множество данных, которые располагаются в
списке последовательно и непрерывно друг за другом.
• Это множество дополнено информацией, которая позволяет вносить изменения в динамическую
структуру данных (информация о количестве элементов в очереди). При задании такой очереди
вносится ограничение на ее размер.
• Статическую очередь можно представить:
• а) линейным массивом с двумя указателями: на начало и на конец очереди. Указатель на начало
определяет позицию очереди (массива), откуда можно взять элемент, указатель на конец – позицию,
в которую элемент кладется:
struct queue
{
int beg, end; type data[N];
};

59.

Очередь
• Для инициализации очереди достаточно определить начальное значение (пустое) указателя на
начало и/или конец очереди.
• Для этого полю end присвоим значение, не принадлежащее диапазону от 0 до N - 1 (а полю beg
можно присвоить значение, указывающее на первый элемент очереди
• q.beg = 0; q.end = -1;
• При включении элемента в очередь увеличивается на единицу значение указателя end, при
извлечении элемента из очереди - значение указателя на начало beg.
• Если поле end равно N - 1, то очередь полна.
• Освободившиеся после взятия элементов из очереди позиции не используются, поэтому возможно
мнимое заполнение очереди. Если end равно N - 1 и beg равно 0 – очередь полна, а если beg больше
0, то очередь псевдополна (т. е. из очереди были взяты элементы и в начале массива есть свободные
позиции).
• Обращение к элементу при взятии из очереди: q.data[q.beg], при занесении в очередь: q.data[q.end].
• Если в очереди один элемент, то оба указателя показывают на него, т. е. их значения равны, если из
очереди взять единственный элемент, она должна стать пустой;

60.

Очередь можно представить
1. Линейным массивом с одним указателем на начало или на конец очереди,
вторая позиция очереди фиксируется.
• Например, начало очереди – это первый элемент массива. В таком случае
содержимое очереди сдвигается после каждого взятия из нее элемента и
уменьшается на единицу поле end. Если поле beg равно 0, а поле end равно N - 1, то
очередь полна:
struct queue
{
int end; type data[N];
};
2. Линейным массивом с двумя указателями (аналогично приведенному выше
варианту 1). При достижении конца массива (последнего элемента) очередь
сдвигается на начало массива (к первому элементу), если есть свободные позиции в
начале массива. Если поле beg равно 0, а поле end равно N - 1, то очередь полна;

61.

Циклическая очередь
Циклическая очередь – линейный массив с двумя указателями (аналогично варианту 1), в котором при достижении
каким-либо указателем конца массива (последнего элемента) значение этого указателя очереди округляется по
модулю N, где N – размер массива. Таким образом, в циклической очереди при достижении конца массива (end = N1) и наличии свободных позиций в начале (beg > 0), новый элемент помещается в массив на место с индексом 0, при
этом указателю end присваивается значение 0.
Очередь будет полна, если поле end = N - 1, а поле beg = 0 или поле end = K, а beg = K + 1. Здесь 0 ⩽ K ⩽ N - 1.

62.

Динамическая очередь
Очередь со связным представлением, отображаемую в динамической памяти, будем называть «динамическая
очередь».
Динамическую очередь можно представить :
1. Линейным односвязным списком с двумя указателями:
struct list
{
type data;
list *next = NULL;
};
struct queue
{
list *beg = NULL, *end = NULL;
};
Задать динамическую очередь – это определить переменную типа queue:
queue q;

63.

Динамическая очередь
2. Линейным двусвязным циклическим списком с одним указателем:
struct queue
{
type data;
queue *next = NULL, *prev = NULL;}
Здесь начало (аналогично конец) очереди можно сделать как в начале, так и в конце списка. Задать
динамическую очередь – это определить переменную-указатель на элемент типа queue:
queue *q;
Для инициализации очереди достаточно указателю q присвоить значение NULL:
q = NULL;

64.

Операции над очередью

65.

Операции над очередью

66.

Дек