Методы программирования

МИНИCTEPCTBO НАУКИ И Высшего образования 
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное 
образовательное учреждение высшего образования
«СЕВЕРО-КАВКАЗСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
МЕТОДЫ ПРОГРАММИРОВАНИЯ
ЛАБОРАТОРНЫЙ ПРАКТИКУМ 
Направление подготовки 
10.05.01 – Компьютерная безопасность
Профиль подготовки 
«Информационно-аналитическая и техническая экспертиза 
компьютерных систем»
Квалификация выпускника – специалист
Ставрополь
2022

УДК 	519.68 (075.8)
ББК 	22.18 я73
М 54
Печатается по решению 
редакционно-издательского совета 
Северо-Кавказского 
федерального университета
© ФГАОУ ВО «Северо-Кавказский 
федеральный университет», 2022
М 54   Методы программирования : лабораторный практикум  / 
          Д. Л. Осипов, А. C. Павлов. – Ставрополь: Изд-во СКФУ, 2022.          
          – 194 с.
Пособие представляет лабораторный практикум по дисциплине 
«Методы программирования». Он составлен в соответствии с программой дисциплины. 
В нём приведены основные алгоритмы и структуры, применяемые 
в программировании, а также рассмотрены современные методы и 
технологии, используемые при разработке программного обеспечения. 
Структурно каждая из работ состоит из краткого изложения теоретического материала, необходимого для ее выполнения, указаний по порядку выполнения работы, заданий для самостоятельного выполнения 
и контрольных вопросов.
Предназначен для специалистов 10.05.01 «Компьютерная безопасность».
УДК 519.68 (075.8)
ББК 22.18 я73
Рецензенты:
д-р техн. наук, профессор, ген. директор ООО «Инфоком-С» 
В. В. Копытов,
канд. техн. наук, доцент, Л. Л. Гусева
(Институт цифрового развития СКФУ)

СОДЕРЖАНИЕ
Предисловие..........................................................................................................4
Лабораторные работы
Исследование структур данных......................................................6
2.
Алгоритмы работы с двоичными файлами...............................12
3. 	 Оценка алгоритмов..........................................................................18
4.
Алгоритмы сортировки массивов 
2
N ........................................23
5.
Алгоритмы сортировки массивов N(LogN)...............................29
6.
Алгоритмы сортировки последовательностей..........................35
7.
Полустатические структуры данных...........................................41
8.
Динамические структуры данных................................................47
9.
Двоичные деревья поиска..............................................................54
10. 	Поиск данных по образцу..............................................................58
11. 	Красно-черные деревья...................................................................65
12. 	Представление графов в памяти...................................................69
13. 	Алгоритмы обхода графа................................................................73
14. 	Минимальное остовное дерево графа.........................................77
15. 	Поиск кратчайшего пути в графе.................................................82
16. 	Алгоритмы хеширования...............................................................86
17. 	Псевдослучайные последовательности.......................................90
18. 	Методы сжатия данных, алгоритм LZW.....................................95
19. 	Алгоритм Хаффмана.....................................................................100
20. 	Алгоритм вывода отрезка............................................................104
21. 	Технологичность программного обеспечения........................108
22. 	Разработка технического задания..............................................113
23. 	Функциональная спецификация ПО.........................................119
24. 	Проектирование классов..............................................................124
25. 	Объектный подход к проектированию ПО. Язык UML.......131
26. 	Оконное приложение на Windows API.....................................137
27. 	Управление процессами в Windows...........................................142
28. 	Многопоточные приложения......................................................147
29. 	Динамически подключаемые библиотеки................................153
30. 	Передача данных через буфер обмена.......................................159
31. 	Взаимодействие процессов с помощью сообщений..............165
32. 	Сетевое взаимодействие с помощью почтовых слотов........172
33. 	Сетевое взаимодействие с помощью именованных каналов.......179
34. 	Сетевое взаимодействие с помощью сокетов.........................186
Литература ....................................................................................................193

Предисловие
Дисциплина «Методы программирования» является одной из 
основных при подготовке специалистов в области компьютерной 
безопасности. Материал, представленный в учебном пособии по 
дисциплине «Методы программирования» направлен на формирование набора общепрофессиональных и профессиональных 
компетенций специалистов, обучающихся по направлению 
10.05.01 «Компьютерная безопасность», специализации «Информационно-аналитическая и техническая экспертиза компьютерных систем». В том числе:
ОПК-8 – способностью использовать языки и системы программирования, инструментальные средства для решения профессиональных, исследовательских и прикладных задач;
ОПК-10 – способностью к самостоятельному построению 
алгоритма, проведению его анализа и реализации в современных программных комплексах;
ПК-17 – способностью производить установку, наладку, тестирование и обслуживание современного общего и специального программного обеспечения, включая операционные системы, системы управления базами данных, сетевое программное 
обеспечение.
Главная задача учебного пособия – вооружить будущего 
специалиста в области компьютерной безопасности всеми необходимыми знаниями для создания профессиональных программных продуктов.
Задачи учебного пособия (лабораторного практикума) совпадают с задачами изучения дисциплины «Методы программирования» и могут быть сформулированы следующим образом:
1)
применение современных методов и технологий программирования;
2)
оценка качества программного обеспечения;
3)
изучение структур данных;
4)
изучение основных алгоритмов;
5)
оценка сложности работы алгоритма;

Предисловие
6) 	 основы структурного и объектно-ориентированного программирования;
7) 	 порядок разработки современного безопасного программного обеспечения (ПО) и жизненный цикл ПО;
8) 	 освоение современных тенденций разработки и сопровождения ПО.
Учебное пособие по дисциплине «Методы программирования» представляет собой лабораторный практикум по дисциплине «Методы программирования» и составлено в соответствии 
с рабочей программой дисциплины для специалистов 10.05.01 
«Компьютерная безопасность», специализации «Информационно-аналитическая и техническая экспертиза компьютерных 
систем».
В методических указаниях приведены алгоритмы, структуры и технологии, широко используемые для разработки современного прикладного программного обеспечения. Структурно 
каждая из работ, в предлагаемом учебном пособии, состоит из 
краткого изложения теоретического материала, необходимого 
для ее выполнения, листингов с примерами исходного кода на 
языках C и C++, заданий к лабораторной работе, методики выполнения заданий, контрольных вопросов, списка литературы, 
рекомендуемой к использованию в данной теме.

1. Исследование структур данных
Цель работы: исследование особенностей представления в 
памяти простых типов данных и структур.
Знания, умения и владения, приобретаемые обучающимся в 
результате освоения темы в рамках формируемых компетенций:
•	
знать: языки и системы программирования; методы построения алгоритма и проведения его анализа; механизмы установки, наладки, тестирования и обслуживания 
современного общего и специального программного обеспечения;
•	
уметь: корректно использовать современные технологии 
программирования для разработки ПО; разработать алгоритм и провести его анализ; осуществлять наладку и 
тестирование современного общего и специального ПО;
•	
владеть: современными технологиями программирования для разработки программного обеспечения; приемами разработки и анализа алгоритма; навыками установки, наладки, тестирования и обслуживания современного 
общего и специального программного обеспечения.
Теоретическая часть
Современные языки программирования, в том числе и C++ 
обладают возможностью определять структуры – набор переменных, объединённых одним именем. Это весьма удобное решение, листинг 1.1 предлагает пример структуры, предназначенной для хранения информации о студенте.
Листинг 1.1. Определение структуры
struct student{
	
char[20] fname;             //имя
	
char[20] sname;             //фамилия
	
unsigned short int y,m,d;   //год, месяц и день рождения
};
Структура student объединяет в себе 6 полей, позволяющих 
сохранить имя, фамилию, дату рождения и номер курса. 

Описанная в листинге 1.1 структура является не переменной, 
а составным типом данных, на основе которого можно объявлять другие переменные (листинг 1.2).
Листинг 1.2. Объявление и инициализация переменных-структур
student st1={«Petr»,»Petrov»,2001,10,5,1};
student st2;
        st2.fname=»Ivan»;
        st2.fname=»Ivanov»;
        st2.y=1995;
        st2.m=1;
        st2.d=12;
        st2.academicyear=2;
Для вычисления размера, занимаемого в памяти любой переменной или структурой, следует обратиться за помощью к оператору sizeof. Листинг 1.3 демонстрирует несколько способов 
применения оператора.
Листинг 1.3. Получение размера переменных и структур
int x;
    x=sizeof(int); //размер типа данных int
    x=sizeof(x);   //размер переменной x
float a[100];
      x=sizeof(a);   //размер массива a
      x=sizeof(a)/sizeof(float); //число эл-тов в массиве a
struct type_str{     //
double d;
      unsigned int i;
      char c;
};
x=sizeof(type_str);   //размер структуры type_str
Представление массива – это отображение (абстрактного) 
массива компонент типа T в память, которая представляет собой 
массив компонент типа word.
Адрес, или индекс памяти, i -ой компоненты массива вычисляется с помощью линейной функции отображения:
	
0
i
i
i
S
=
+ ×
,	
(1.1)
где: 0i  – адрес первой компоненты; S  – число слов, которые занимает компонента.

Так как по определению WORD есть минимальная доступная 
единица памяти, то, по-видимому, желательно, чтобы S  было 
целым числом. Если S  не целое число слов памяти (а так бывает 
довольно часто), то S  обычно округляется до ближайшего большего целого числа [ ]
S . В этом случае каждая компонента массива занимает [ ]
S  слов, причем часть слова величиной [ ]  
S
S
−
 
остается неиспользованной. Округление числа занимаемых слов 
до ближайшего целого называется выравниванием.
Для упаковки структур в C++ применяют директиву #pragma 
pack, например, так, как представлено в листинге 1.4.
Листинг 1.4. C++ Упаковка структуры
#pragma pack(push, 1)
struct Foo{
    // ...
};
#pragma pack(pop)
Директива pack действует на первое объявление struct, union 
или class после этой директивы #pragma.
Отношение размера памяти, которая отводится для описания 
структуры данных, к размеру действительно занятой памяти называется коэффициентом использования памяти:
	
[ ]
'
s
s
u
s
s
=
=
,	
(1.2).
С одной стороны, разработчик стремится получить коэффициент использования памяти, близкий к 1. Но поскольку, 
с другой стороны, доступ к частям слова неясный и довольно 
неэффективный процесс, разработчику приходится идти на некоторый компромисс. Выравнивание понижает коэффициент использования памяти. Отказ от выравнивания может привести к 
неэффективному обращению к частям слова.
Записи отображаются в память простым объединением отображений их компонент. Адрес компоненты ir  относительно начального адреса записи называется смещением 
ik :
	
1
2
1
...
i
i
k
S
S
S −
=
+
+
+
,	
(1.3)
где 
iS  – размер компоненты.

Для выполнения лабораторной работы необходим персональный компьютер со следующими характеристиками: процессор 
32-битный или 64-битный (x86-64, EM64T) с тактовой частотой 
1,5 ГГц или выше (рекомендуется 2 ГГц), оперативная память – 
2 ГБ (рекомендуется 4 Гб), свободное дисковое пространство – 
1,75 Гб, монитор типа  Super XGA c разрешением 1024 × 768 
(или выше) с 24-битными (или больше) цветами с диагональю 
не менее 19˝, клавиатура, мышь. Программное обеспечение – 
операционная система семейства Windows или Linux, среда программирования (по выбору студента).
Задания
На языке программирования Си разработайте структуру данных согласно полученного варианта.
Варианты к заданию
1.	
Разработайте структуру данных позволяющую составлять прайс-лист магазина. В прайс-лист входят следующие позиции: название товара, цена за единицу, единица 
измерения, количество товара в магазине.
2.	
Подготовьте структуру данных позволяющую создавать 
расписание телепередач на неделю. В расписание входят 
следующие позиции: день недели, номер канала, время 
начала передачи, название передачи, жанр передачи.
3.	
Подготовьте структуру, предназначенную для описания 
информации в зачётной книжке студента. Необходимо 
предусмотреть следующие элементы: дисциплина, количество часов, вид отчётности (экзамен, зачёт, курсовая 
работа), оценка.
4.	
Подготовьте структуру для хранения данных о квартирах 
многоэтажного дома. В структуру следует включить следующие позиции: номер квартиры, число комнат, номер 
этажа, площадь, наличие балкона(ов), признак первого 
этажа, признак последнего этажа.

Подготовьте структуру для хранения сведений об автотранспортных средствах на стоянке: тип автомобиля
(грузовой, легковой, …), регистрационный номер, марка,
когда поставлен на стоянку, ФИО владельца.
6.
Подготовьте структуру для описания телевизора. В структуру должны входить: производитель, марка, диагональ,
разрешение (HD, Full HD, 4K, и т.п.).
Указания по порядку выполнения работы
Для выполнения задания необходимо изучить теоретическую 
часть к лабораторной работе и приведенные в ней листинги. 
В отчете следует схематично изобразить представление в памяти данных в упакованном и неупакованном виде. Сделайте выводы об особенностях определения структур с учётом минимизации расхода памяти.
Содержание отчета
Отчет по лабораторной работе должен состоять из: 
1.
Названия лабораторной работы.
2.
Ответов на контрольные вопросы.
3.
Формулировки задания и порядка его выполнения.
Контрольные вопросы
1.
Какие скалярные типы данных вам известны?
2.
Что такое выравнивание?
3.
С помощью какого оператора можно выяснить размер
переменной или структуры в памяти?
4.
Как рассчитывается коэффициент использования памяти?
Указания по технике безопасности
Техника безопасности при выполнении лабораторной работы совпадает с общепринятой для пользователей персональных 
компьютеров. В частности: самостоятельно не производить 
ремонт персонального компьютера, установку и удаление программного обеспечения; в случае неисправности персонально