Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

7. Материально-техническое обеспечение дисциплины

Компьютерный класс, оснащенный ПК не ниже Pentium 75 МГц с ОС Windows 95 и выше или Windows NT.

8. Методические рекомендации по организации изучения дисциплины

Использование специального методического обеспечения не предусмот­

рено.

Программа составлена в соответствии с Государственным образователь­ ным стандартом высшего профессионального образования по направлению 5502 "Автоматизация и управление" подготовки бакалавров и по направлению 6519 "Автоматизация и управление" подготовки специалистов.

Программу составили:

Лекарев Михаил Федорович, д.т.н., профессор, СПбГТУ (ЛПИ) Давыдов Владимир Григорьевич, к.т.н., доцент, СПбГТУ (ЛПИ)

Программа одобрена на заседании учебно-методического совета по на­ правлению 5502 "Автоматизация и управление" 14.11.2000, протокол №

Председатель Совета УМО

Приложение П.7. Прилагаемый компакт-диск.

На прилагаемом компакт-диске содержатся исходные тексты всех примеров программ. Имеются также и исполняемые файлы этих программ, так что Вам не надо обязательно компилировать за­ интересовавшие Вас примеры. Все программные проекты примеров "самодостаточны". Это означает, что ни одному из них не требуются файлы других проектов.

Кроме исходных текстов примеров программ на компакт-диске имеются:

•описание ПМ-ассемблера в формате текстового редактора Word 2000;

•интегрированная среда программирования ПМ-ассемблера (рабо­ тает как DOS-приложение);

•файл с полным текстом приложений к учебному пособию в фор­

мате текстового редактора Word 2000 и др.

Более полные сведения о содержимом компакт-диска и работе с этой информацией имеется в файле ReadMe, расположенном в корневой папке компакт диска.

Обратите внимание, что пользование данной книгой возможно и без компакт-диска, но его наличие обеспечит Вам большие удоб­ ства и дополнительный сервис. В частности, без компакт-диска Вы не будете располагать описанием ПМ-ассемблера, специально раз­ работанного для использования в учебном процессе, и его интегри­ рованной средой программирования.

ЛИТЕРАТУРА

1. Давыдов	В.Г.,	Пекарев	М.Ф.	Учебный машинно-
ориентированный	язык	(ПМ-ассемблер): Учебное пособие. - СПб.:

Санкт-Петербургский государственный политехнический универси­ тет, 2002.

2.Пекарев М.Ф. Модули с двумя выходами в программных проектах. - СПб.: СПбГТУ, 2000.

3.Рассохин Д. От Си к C++. - М.: Издательство "ЭДЕЛЬ",

1993.

4.От Си к C++ / Е.И. Козелл, Л.М. Романовская, Т.В. Русс и др. - М.: Финансы и статистика, 1993.

5.C/C++. Программирование на языке высокого уровня / Т.А. Павловская. - СПб.: Питер, 2001.

6.Давыдов В.Г. Теория и технология программирования: Кон­ спект лекций. Ч. 2. СПб: Издательство СПбГПУ, 2001.

СОДЕРЖАНИЕ

ПРЕДИСЛОВИЕ	3
1. ВВЕДЕНИЕ	5
1.1. Системы счисления	5
1.2. Классификация языков программирования и их
краткая характеристика	8
1.2.1. Машинные языки	9

1.2.2. Ассемблерные языки		(на		примере
ПМ-ассемблера)						12
1.2.3. Макроассемблерные		языки				12
1.2.4. Машинно-независимые			языки			14
ЧАСТЬ 1. БАЗОВЫЙ ЯЗЫК						16
2. ЯЗЫК ПРОГРАММИРОВАНИЯ ВЫСОКОГО
УРОВНЯ C++						16
2.1. Введение. Структурное и модульное
программирование						17
2.1.1.Алгоритм и способы		его записи				17
2.1.2. Структурное	и модульное			программирование		21
2.2. Язык программирования и его описание						27
2.3. Структура и конструкция программы на Си/С++						31
2.3.1. Комментарии						31
2.3.2. Идентификаторы						32
2.3.3. Слуэюебные	слова					32
2.3.4. Константы						33
2.3.5. Структура	Си-программы					38
2.4. Простой ввод-вывод в языках Си/С++						41
2.4.1. Ввод-вывод	потока					41
2.4.2. Ввод с использованием			функций		scanf-fscanf	43
2.4.3. Вывод с использованием			функций		printf-fprintf	49
2.4.4. Упразднения	для самопроверки					54
3. ТИПЫ ДАННЫХ И ИХ АТРИБУТЫ						56
3.1. Имена						56
3.2. Типы данных						57
3.3. Класс хранения: область действия и время жизни						60
3.4. Внешние и внешние статические данные						61
3.5. Функции						68
3.6. Автоматические, регистровые и внутренние
статические данные						74
3.7. Инициализация данных						78
3.8. Упражнения для самопроверки						79

443

3.9. Производные типы данных		81
3.9.1. Массивы		81
3.9.2. Массивы — как аргументы функций		86
3.9.3. Упраэюнения	для самопроверки	88
3.9.4. Структуры		88
3.9.5. Структуры	в качестве аргументов функций	91
3.9.6. Упраэюнения	для самопроверки	93
4. ОПЕРАТОРЫ И УПРАВЛЕНИЕ ИХ ИСПОЛНЕНИЕМ ....		95
4.1. Пустой оператор		95
4.2. Операторы-выражения		95
4.3. Операторы break и continue		96
4.4. Блок операторов		96
4.5. Оператор return		97
4.6. Оператор if		97
4.7. Оператор switch		100
4.8. Оператор while		101
4.9. Оператор do-while		104
4.10. Оператор for		105
4.11. Оператор goto и метки операторов		108
4.12. Упражнения для самопроверки		108
5. ВЫРАЖЕНИЯ И ОПЕРАЦИИ		111
5.1. Операции ссылки		113
5.2. Унарные операции		116
5.3. Бинарные операции		118
5.4. Тернарная операция		121
5.5. Операция присваивания		121
5.6. Операция "запятая"		122
6. УКАЗАТЕЛИ		123
6.1. Зачем нужны указатели?		123
6.2. Указатели и их связь с массивами и строками		123
6.3. Определение и применение указателей		124
6.4. Указатели на структуры		128
6.5. Использование указателей в качестве аргументов
функций		129
6.6. Указатель как значение, возвращаемое функцией		133
6.7. Массивы указателей		134
6.8. Замена типов указателей		137
6.9. Упражнения для самопроверки		141
7. ПОЛЯ БИТОВ И ПОБИТОВЫЕ ОПЕРАЦИИ		143
7.1. Поля битов		143
7.2. Побитовые операции		144

444

8.ДИНАМИЧЕСКОЕ РАЗМЕЩЕНИЕ ОБЪЕКТОВ В ПАМЯТИ. ОДНОНАПРАВЛЕННЫЙ НЕКОЛЬЦЕВОЙ

ЛИНЕЙНЫЙ СПИСОК И ОПЕРАЦИИ С НИМ	148
8.1. Понятие об однонаправленном линейном списке.
Динамическое размещение объектов в памяти	148
8.2. Инициализация линейного списка	152
8.3. Добавление элемента в начало списка	163
8.4. Добавление элемента в конец списка	163
8.5. Создание ЛС с первым занесенным элементом
в начале	164
8.6. Создание ЛС с первым занесенным элементом
в конце списка	164
8.7. Удаление элемента из начала списка	165
8.8. Удаление элемента из конца списка	166
8.9. Разрушение ЛС с освобождением занятой им
динамической памяти	166
8.10. Печать содержимого ЛС	167
8.11. Добавление элемента после каждого элемента ЛС,
содержащего заданное значение	167
8.12. Добавление элемента перед каждым элементом ЛС,
содержащим заданное значение	168
8.13. Удаление элемента после каждого элемента ЛС,
содержащего заданное значение	168
8.14. Удаление элемента перед каждым элементом ЛС,
содержащим заданное значение	170
8.15. Зачем нужен линейный список	171
8.16. Упражнения для самопроверки	172
9. ПРЕПРОЦЕССОР ЯЗЫКА СИ/С++	173
9.1. Директивы препроцессора	173
9.2. Подстановка имен	173
9.3. Включение файлов	177
9.4. Условная компиляция	178
9.5. Указания по работе с препроцессором	180
10. РЕДКО ИСПОЛЬЗУЕМЫЕ СРЕДСТВА
ЯЗЫКОВ СИ/С++	182
10.1. Объявление имени типа typedef	182
10.2. Объекты перечислимого типа	183
10.3. Объединения	186
11. МОДЕЛИ ПАМЯТИ	189
11.1. Адресация near, far и huge	190
11.2. Стандартные модели памяти для
шестнадцатибитной среды DOS	193

445

11.3. Изменение размера указателей в
стандартных моделях памяти для
шестнадцатибитной среды DOS	194
11.4. Макроопределения для работы с указателями	195
11.5. Работа с памятью для среды WINDOWS	196

12.НОВЫЕ ВОЗМОЖНОСТИ ЯЗЫКА C++, НЕ СВЯЗАННЫЕ С ОБЪЕКТНО-ОРИЕНТИРОВАННЫМ

ПРОГРАММИРОВАНИЕМ				197
12.1. Прототипы функций. Аргументы по умолчанию				198
12.2. Доступ к глобальным переменным, скрытым
локальными переменными с тем же именем				199
12.3. Модификаторы const и volatile				200
12.4. Ссылки				201
12.5. Подставляемые функции				202
12.6. Операции динамического распределения памяти				202
12.7. Перегрузка функций				203
12.8. Шаблоны функций				205
12.9. Перегрузка операций				206
13. ТЕХНОЛОГИЯ СОЗДАНИЯ ПРОГРАММ [5]				208
13.1. Кодирование и документирование программы				208
13.2. Проектирование и тестирование программы [5]				212
13.2.1. Этап	1: постановка		задачи	213
13.2.2. Этап	2: разработка		внутренних
структур		данных		214
13.2.3. Этап	3: проектирование структуры
программы		и взаимодействия модулей		214
13.2.4. Этап	4: структурное		программирование	215
13.2.5. Этап	5: нисходящее		тестирование	216
ЧАСТЬ 2. ПРИКЛАДНОЕ ПРОГРАММИРОВАНИЕ				218
14. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ [5]				218
14.1. Линейные списки				219
14.2. Бинарные деревья				220
14.3. Очереди и их частные разновидности				221
14.4. Реализация динамических структур с
помощью массивов				222
15. СОРТИРОВКА				224
15.1. Сортировка массивов				226
15.2. Сортировка массива простым выбором				228
15.3. Сортировка массива простыми включениями				248
15.4. Сортировка массива простым обменом
(метод "пузырька")				250
15.5. Выводы по простым методам сортировки				251

446

15.6. Сортировка массива сложным выбором
(с помощью двоичного дерева)			252
15.7. Сложная сортировка вставками (сортировка Шелла) ...			257
15.8. Сложная сортировка обменом (сортировка Хоора)			259
15.9. Сравнительные показатели производительности
различных методов сортировки массивов			264
16. ГРАФЫ. ТРАНСПОРТНАЯ ЗАДАЧА (ЗАДАЧА
КОММИВОЯЖЕРА)			266
16.1. Терминология			266
16.2. Формы задания графа			268
16.3. Почему для решения задачи подходит
рекурсивный алгоритм			269
16.4. Представление кратчайшего пути до каждой
вершины			270
16.5. Как найти минимальный путь			271
16.5.1. Требуется ли полный перебор путей			271
16.5.2. Организация	перебора путей		271
16.6. Пример поиска минимального пути в графе			285
16.7. Печать информации о наилучшем пути			286
17. ПОИСК			288
17.1. Постановка задачи внутреннего поиска			288
17.2. Последовательный поиск			290
17.3. Логарифмический (бинарный) поиск			305
17.4. Поиск с использованием перемешанной
таблицы (хэш-таблицы)			308
18. ОТВЕТЫ И РЕШЕНИЯ К УПРАЖНЕНИЯМ
ДЛЯ САМОПРОВЕРКИ			312
18.1. Для подраздела 2.4.4			312
18.2. Для подраздела 3.8			314
18.3. Для подраздела 3.9.3			315
18.4. Для подраздела 3.9.6			317
18.5. Для подраздела 4.12			319
18.6. Для подраздела 6.9			321
18.7. Для подраздела 8.16			321
ПРИЛОЖЕНИЯ			327
Приложение П. 1. Тесты и программные проекты.
Варианты заданий			327
П. 1.1. Тесты (контрольные		работы)	327
П. 1.1.1. Программирование		на ПМ-ассемблере.
Варианты тестов			327
П.1.1.2. Ввод в языках Си/С++. Варианты тестов			330
П. 1.1.3. Вывод в языках	Си/С++. Варианты тестов		337

447

п. 1.1.4. Простейшие

ветвления. Варианты

тестов

342

П.1.1.5. Циклы. Варианты

тестов

345

П. 1.1.6. Структуры. Варианты тестов

350

П.1.1. 7. Функции. Варианты тестов

359

П. 1.1.8. Области

действия определений.

Варианты тестов

361

П. 1.1.9. Массивы

и указатели.

Варианты

тестов

373

П. 1.1.10. Операции над линейным списком.

Работа

с динамической

памятью. Варианты тестов

379

П.1.1.11. Препроцессор, перечисления, функции с умалчиваемыми

значениями

аргументов, перегрузка функций, шаблоны

функций, перегрузка операций. Варианты тестов

388

П.1.2.

Программные

проекты

392

П. 1.2.1. Программирование

на ПМ-ассемблере.

Варианты

программных

проектов

393

П. 1.2.2. Структурное

программирование

средствами языков

Си/С-^+ . Варианты программных проектов

395

П. 1.2.3. Средства

модульного

программирования

в языке C++.

Варианты программных проектов

402

П.1.3.

Экзаменационное

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

405

Приложение П.2. Создание программного проекта

408

П.2.1.

IDE MS

Visual

Studio

C++ 6.0.

Создание

программного

проекта

408

П.2.2. IDE Borland

C++

3.1.

Создание

программного

проекта

411

Приложение П.З. Рекомендации по структуре

однофайловой программы с одной функцией и пример

оформления исходного текста

412

Приложение П.4. Методика отладки программы

414

П.4.1.

Компиляция

и компоновка

программного

проекта.

Устранение

синтаксических

огиибок

415

П.4.2.

Отладка

программного

проекта.

Устранение

логических

(алгоритмических)

огиибок

417

77.4.3. Тестирование

программного

проекта

420

Приложение П. 5. Рекомендации по созданию

многофайлового программного проекта с несколькими

функциями и пример оформления исходного текста

421

77.5.7. Спецификация

программного

проекта

421

П. 5.2. Пример

оформления

исходного

текста

программы

428

Приложение П.6. Примерная программа дисциплины

"Программирование и основы алгоритмизации"

434

Приложение П.7. Прилагаемый компакт-диск

441

ЛИТЕРАТУРА

442

448