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

МИНИ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

лАборАторНые рАботы

1.
Исследование структур данных .....................................................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

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

Предисловие

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

- 5 
Предисловие

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

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

1. Исследование структур данных

Цель работы: исследование особенностей представления в 
памяти простых типов данных и структур.
Знания, умения и владения, приобретаемые обучающимся в 
результате освоения темы в рамках формируемых компетенций:
• 
знать: языки и системы программирования; методы построения алгоритма и проведения его анализа; механизмы установки, наладки, тестирования и обслуживания 
современного общего и специального программного обеспечения;
• 
уметь: корректно использовать современные технологии 
программирования для разработки ПО; разработать алгоритм и провести его анализ; осуществлять наладку и 
тестирование современного общего и специального ПО;
• 
владеть: современными технологиями программирования для разработки программного обеспечения; приемами разработки и анализа алгоритма; навыками установки, наладки, тестирования и обслуживания современного 
общего и специального программного обеспечения.

Теоретическая часть

Современные языки программирования, в том числе и C++ 
обладают возможностью определять структуры – набор переменных, объединённых одним именем. Это весьма удобное решение, листинг 1.1 предлагает пример структуры, предназначенной для хранения информации о студенте.

Листинг 1.1. Определение структуры
struct student{
 
char[20] fname;             //имя
 
char[20] sname;             //фамилия
 
unsigned short int y,m,d;   //год, месяц и день рождения
};

Структура student объединяет в себе 6 полей, позволяющих 
сохранить имя, фамилию, дату рождения и номер курса. 

- 7 
Лабораторная работа 1

Описанная в листинге 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  – число слов, которые занимает компонента.

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

Так как по определению 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  – размер компоненты.

- 9 
Оборудование и материалы

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

Лабораторная работа 1

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

5.
Подготовьте структуру для хранения сведений об автотранспортных средствах на стоянке: тип автомобиля
(грузовой, легковой, …), регистрационный номер, марка,
когда поставлен на стоянку, ФИО владельца.
6.
Подготовьте структуру для описания телевизора. В структуру должны входить: производитель, марка, диагональ,
разрешение (HD, Full HD, 4K, и т.п.).

Указания по порядку выполнения работы

Для выполнения задания необходимо изучить теоретическую 
часть к лабораторной работе и приведенные в ней листинги.  
В отчете следует схематично изобразить представление в памяти данных в упакованном и неупакованном виде. Сделайте выводы об особенностях определения структур с учётом минимизации расхода памяти.

Содержание отчета

Отчет по лабораторной работе должен состоять из: 
1.
Названия лабораторной работы.
2.
Ответов на контрольные вопросы.
3.
Формулировки задания и порядка его выполнения.

Контрольные вопросы

1.
Какие скалярные типы данных вам известны?
2.
Что такое выравнивание?
3.
С помощью какого оператора можно выяснить размер
переменной или структуры в памяти?
4.
Как рассчитывается коэффициент использования памяти?

Указания по технике безопасности

Техника безопасности при выполнении лабораторной работы совпадает с общепринятой для пользователей персональных 
компьютеров. В частности: самостоятельно не производить 
ремонт персонального компьютера, установку и удаление программного обеспечения; в случае неисправности персонально