Основы программирования на языке Си

А.А. Богуславский, С.М. Соколов

Основы программирования

на языкеСи++

Часть 1. Введение в программирование

на языке Си++

(длястудентовфизико-математическихфакультетов

педагогических институтов)

Коломна, 2002

ББК 32.97я73
Рекомендовано кизданию

УДК 681.142.2(075.8) редакционно-издательскимсоветом

Б 73 Коломенскогогосударственного

педагогического института

Богуславский А.А., СоколовС.М.

Б73 ОсновыпрограммированиянаязыкеСи++: Длястудентовфизико-

математических факультетовпедагогическихинститутов. –Коломна: КГПИ,

2002. – 490 с.

Пособие предназначенодляобучениястудентов, обладающих навыкамиполь-

зовательской работынаперсональномкомпьютере, основнымпонятиямиметодам

современного практическогопрограммирования. Предметомизучениякурсаявляется

объектно-ориентированноепрограммированиенаязыкеСи++ всредесовременных

32-хразрядныхоперационныхсистемсемейства Windows. Программакурсаразбита

на 4 части: (1) ВведениевпрограммированиенаязыкеСи++; (2) Основыпрограмми-

рования трехмернойграфики; (3) Объектно-ориентированное программированиена

языке Си++ и (4) Программированиедля Microsoft Windows сиспользованием Visual

C++ ибиблиотекиклассов MFC.

После изучениякурсастудентполучаетдостаточнополноепредставлениео

содержании современногообъектно-ориентированногопрограммирования, обуст-

ройстве современныхоперационныхсистем Win32 иособытийно-управляемомпро-

граммировании. Напрактическихзанятияхвырабатываютсянавыкипрограммирова-

ния наСи++ винтегрированной средеразработки Microsoft Visual C++ 5.0.

Рецензенты:

И.П. Гиривенко–к.т.н., доцент, зав. кафедройинформатикиивычислительнойтех-

ники Рязанскогогосударственногопедагогическогоуниверситета

им. С.А. Есенина.

А.А. Шамов–к.х.н., доценткафедрытеоретическойфизикиКоломенскогогосу-

дарственного педагогическогоинститута.

СОДЕРЖАНИЕ

КРАТКОЕ ОПИСАНИЕ УЧЕБНОГО КУРСА "ОСНОВЫ ПРОГРАММИРОВАНИЯ

НА ЯЗЫКЕ СИ++" ..........................................................................................................................5

ЛЕКЦИЯ 1. ОСНОВЫ СИ++.........................................................................................................7

1. НЕСКОЛЬКО ЗАМЕЧАНИЙОНАЗНАЧЕНИИПРОГРАММИРОВАНИЯ................................................7

2. ПРОИСХОЖДЕНИЕ ЯЗЫКАСИ++...................................................................................................9

3. СТАНДАРТ ANSI СИ++ ................................................................................................................9

4. СРЕДА РАЗРАБОТКИMICROSOFT DEVELOPER STUDIO VISUAL С++...........................................10

5. ПРИМЕР ПРОГРАММЫНАСИ++ .................................................................................................10

6. ВЫПОЛНЕНИЕ ВВОДА/ВЫВОДА ДАННЫХИПРИСВАИВАНИЕЗНАЧЕНИЙ....................................12

7. УПРАВЛЕНИЕ ПОРЯДКОМВЫПОЛНЕНИЯКОМАНДСПОМОЩЬЮОПЕРАТОРА IF ........................13

8. ОФОРМЛЕНИЕ ИСХОДНОГОТЕКСТА...........................................................................................15

9. СВОДКА РЕЗУЛЬТАТОВ...............................................................................................................15

10. УПРАЖНЕНИЯ ...........................................................................................................................15

ЛЕКЦИЯ 2. ПЕРЕМЕННЫЕ, ТИПЫ ДАННЫХ И ВЫРАЖЕНИЯ....................................18

1. ИДЕНТИФИКАТОРЫ ....................................................................................................................18

2. ТИПЫ ДАННЫХ...........................................................................................................................18

3. ВЫВОД ВЕЩЕСТВЕННЫХЧИСЕЛНАЭКРАН................................................................................22

4. ОПИСАНИЯ, КОНСТАНТЫ ИПЕРЕЧИСЛЕНИЯ..............................................................................24

5. ПРИСВАИВАНИЕ ИВЫРАЖЕНИЯ.................................................................................................26

6. СВОДКА РЕЗУЛЬТАТОВ...............................................................................................................28

7. УПРАЖНЕНИЯ .............................................................................................................................28

8. ПРИЛОЖЕНИЯ .............................................................................................................................29

ЛЕКЦИЯ 3. ФУНКЦИИ И ПРОЦЕДУРНАЯ АБСТРАКЦИЯ .............................................31

1. НАЗНАЧЕНИЕ ПОДПРОГРАММ.....................................................................................................31

2. ОПРЕДЕЛЕНИЕ НОВЫХФУНКЦИЙ...............................................................................................31

3. СПОСОБЫ ПЕРЕДАЧИПАРАМЕТРОВВНУТРЬФУНКЦИЙ..............................................................33

4. ПОЛИМОРФИЗМ ИПЕРЕГРУЗКАФУНКЦИЙ..................................................................................35

5. ПРОЦЕДУРНАЯ АБСТРАКЦИЯИ"ХОРОШИЙ" СТИЛЬ ПРОГРАММИРОВАНИЯ...............................36

6. МОДУЛЬНОЕ ПРОГРАММИРОВАНИЕ...........................................................................................36

7. СВОДКА РЕЗУЛЬТАТОВ...............................................................................................................38

8. УПРАЖНЕНИЯ .............................................................................................................................39

ЛЕКЦИЯ 4. ТЕКСТОВЫЕ ФАЙЛЫ И ПОТОКИ ВВОДА/ВЫВОДА ................................41

1. НАЗНАЧЕНИЕ ФАЙЛОВ................................................................................................................41

2. ПОТОКИ ВВОДА/ВЫВОДА ...........................................................................................................41

3. ПРОВЕРКА ОШИБОКВЫПОЛНЕНИЯФАЙЛОВЫХОПЕРАЦИЙ.......................................................43

4. СИМВОЛЬНЫЙ ВВОД/ВЫВОД ......................................................................................................44

5. ПРОВЕРКА ДОСТИЖЕНИЯКОНЦАФАЙЛАПРИОПЕРАЦИЯХВВОДА............................................45

6. ПЕРЕДАЧА ПОТОКОВ ФУНКЦИЯМВКАЧЕСТВЕПАРАМЕТРОВ.....................................................47

7. ОПЕРАТОРЫ ВВОДА/ВЫВОДА ">>" И "<<" .................................................................................48

8. СВОДКА РЕЗУЛЬТАТОВ...............................................................................................................50

9. УПРАЖНЕНИЯ .............................................................................................................................50

ЛЕКЦИЯ 5. ОПЕРАТОРЫ ВЕТВЛЕНИЯ И ЦИКЛЫ ...........................................................52

1. ЛОГИЧЕСКИЕ ЗНАЧЕНИЯ, ВЫРАЖЕНИЯ ИФУНКЦИИ...................................................................52

2. ЦИКЛЫ "FOR", "WHILE" И "DO...WHILE" .....................................................................................53

3. МНОЖЕСТВЕННОЕ ВЕТВЛЕНИЕИОПЕРАТОР"SWITCH" ..............................................................55

4. БЛОКИ ИОБЛАСТЬВИДИМОСТИПЕРЕМЕННЫХ..........................................................................56

5. ЗАМЕЧАНИЕ ОВЛОЖЕННЫХЦИКЛАХ.........................................................................................59

6. СВОДКА РЕЗУЛЬТАТОВ...............................................................................................................59

7. УПРАЖНЕНИЯ .............................................................................................................................60

ЛЕКЦИЯ 6. МАССИВЫ И СИМВОЛЬНЫЕ СТРОКИ.........................................................63

1. НАЗНАЧЕНИЕ МАССИВОВ...........................................................................................................63

2. ПЕРЕДАЧА МАССИВОВВКАЧЕСТВЕПАРАМЕТРОВФУНКЦИЙ....................................................66

3. СОРТИРОВКА МАССИВОВ...........................................................................................................68

4. ДВУМЕРНЫЕ МАССИВЫ..............................................................................................................69

5. СИМВОЛЬНЫЕ СТРОКИ...............................................................................................................70

6. СВОДКА РЕЗУЛЬТАТОВ...............................................................................................................73

7. УПРАЖНЕНИЯ .............................................................................................................................73

ЛЕКЦИЯ 7. УКАЗАТЕЛИ............................................................................................................75

1. НАЗНАЧЕНИЕ УКАЗАТЕЛЕЙ........................................................................................................75

2. ПЕРЕМЕННЫЕ ТИПА"МАССИВ". АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИСУКАЗАТЕЛЯМИ....................79

3. ДИНАМИЧЕСКИЕ МАССИВЫ.......................................................................................................81

4. АВТОМАТИЧЕСКИЕ ИДИНАМИЧЕСКИЕПЕРЕМЕННЫЕ................................................................82

5. СВЯЗНЫЕ СПИСКИ......................................................................................................................82

6. СВОДКА РЕЗУЛЬТАТОВ...............................................................................................................86

7. УПРАЖНЕНИЯ .............................................................................................................................87

ЛЕКЦИЯ 8. РЕКУРСИЯ...............................................................................................................89

1. ПОНЯТИЕ РЕКУРСИИ...................................................................................................................89

2. ПРОСТОЙ ПРИМЕРРЕКУРСИИ.....................................................................................................89

3. КАК ВЫПОЛНЯЕТСЯРЕКУРСИВНЫЙВЫЗОВ................................................................................90

4. ЕЩЕ ТРИПРИМЕРАРЕКУРСИИ....................................................................................................92

5. РЕКУРСИЯ ИЦИКЛЫ....................................................................................................................93

6. РЕКУРСИЯ ВСТРУКТУРАХДАННЫХ............................................................................................94

7. РЕКУРСИВНАЯ РЕАЛИЗАЦИЯАЛГОРИТМАБЫСТРОЙСОРТИРОВКИ.............................................94

8. СВОДКА РЕЗУЛЬТАТОВ...............................................................................................................97

9. УПРАЖНЕНИЯ .............................................................................................................................97

ЛЕКЦИЯ 9. СОСТАВНЫЕ ТИПЫ ДАННЫХ.......................................................................100

1. НАЗНАЧЕНИЕ СОСТАВНЫХТИПОВДАННЫХ............................................................................100

2. ОПИСАНИЕ ИИНИЦИАЛИЗАЦИЯСТРУКТУР..............................................................................100

3. ДОСТУП ККОМПОНЕНТАМСТРУКТУРЫЧЕРЕЗУКАЗАТЕЛЬ......................................................103

4. МАССИВЫ ИСТРУКТУРЫ..........................................................................................................104

5. ПЕРЕГРУЗКА ОПЕРАТОРОВ........................................................................................................105

6. ПРИМЕНЕНИЕ СТРУКТУРДЛЯРЕАЛИЗАЦИИСТЕКА ..................................................................107

7. СВОДКА РЕЗУЛЬТАТОВ.............................................................................................................111

8. УПРАЖНЕНИЯ ...........................................................................................................................112

ПРИЛОЖЕНИЕ. КРАТКОЕ РУКОВОДСТВО ПО СРЕДЕ РАЗРАБОТКИ DEVELOPER

STUDIO VISUAL C++..................................................................................................................113

1. СОЗДАНИЕ НОВОГОПРОЕКТА...................................................................................................113

2. ДОБАВЛЕНИЕ ВПРОЕКТНОВОГОИСХОДНОГОФАЙЛА.............................................................114

3. СБОРКА ПРОЕКТА.....................................................................................................................115

4. ЗАПУСК НОВОГОПРИЛОЖЕНИЯ................................................................................................116

ЛИТЕРАТУРА.............................................................................................................................117

Краткое описание учебного курса "Основы программиро-

вания на языке Си++"

Развитие современныхтехнологийпрограммированияпредполагаетвладение

программистом широкимнаборомпрактическихнавыков, средикоторыходнимииз

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

темных технологийбазовойоперационнойсистемы. Рассматриваемыйучебный курс

предназначен дляначальнойподготовкипрограммиста, владеющегоязыкомпро-

граммирования Си++ применительнокразработкепрограммвОСсемейства Win32.

При анализедоступныхвИнтернетзарубежныхкурсов, связанныхсобучени-

ем практическомупрограммированиюврамкахподготовкипоспециальностям Computer

Science, оказаласьзаметнаследующаятенденция: существуюткурсыпоизуче-

нию языкаСи++, курсыпоизучениюобъектно-ориентированногопрограммирования

на базе, чащевсего, Java иреже, Си++, ипрактическистандартныйкурс "Операцион-

ные системы", посвященныйструктуре Unix-совместимыхоперационныхсистем. Ха-

рактерной особенностьюзарубежныхуниверситетскихкурсовявляетсяотсутствие

разделов, посвященныхизучениюпрактическогопрограммированиявсредекоммер-

ческих ОСмассовогораспространения, впервуюочередь, ОС Windows. Сдругой

стороны, изучениепрограммированиядляэтихОСпредлагаетсярядом коммерческих

учебных организаций, носрокиобученияпорядка 3-5 днейпредполагаютобучение

уже грамотногоспециалиста, имеющегонавыкипрограммированиявкакой-либодру-

гой ОСилинадругомязыкепрограммирования.

В сегодняшнихроссийскихусловиях, неотрицаянеобходимостифундамен-

тальной подготовкиспециалистовповычислительнойтехникевобластитеорииалго-

ритмов иустройствавычислительныхипрограммныхсистем, можноотметитьполез-

ность изучения технологийпрактическогопрограммирования–использованиясред

разработки ибиблиотекпрограммированиядляОСмассовогораспространения. Этим

обусловлена направленностьрассматриваемогокурса–начальнаяподготовкапро-

граммистов наСи++ длясредыОС Windows.

Сложность обученияпрактическомупрограммированию, нанашвзгляд, за-

ключается втрудностисочетанияобученияабстрактнымпонятиямпрограммирова-

ния (таким, какструктурыданных, понятие алгоритма, основныекомпонентыалго-

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

изучением технологийисредпрограммированиянабазекакой-либоконкретнойОС.

Эти практическиетехнологиипребываютвпостоянномразвитии, поэтомуможет

быть сложновыделитькакие-либоконкретныесредстваразработкивкачествепред-

мета изучения.

Несмотря наширокоераспространениесредбыстройразработкиПрО (напри-

мер, Visual Basic, Inprise Builder и Inprise Delphi), выборихвкачествеучебнойсреды

представляется нецелесообразным, т.к. вэтихсредахкажущаясяпростотаразработки

ПрО касаетсятолькоформированиякаркасаприложенияизнабораготовыхкомпо-

нент, аустройствоэтихкомпонентилиизменениеструктурыкаркасатребуетсерьез-

ных знанийнетолькопоструктуребазовойОС, ноипосистемнойархитектуресреды

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

Программа данногокурсапредназначенадляобучениялиц, имеющих навыки

пользовательской работынаперсональномкомпьютере, основнымпонятиямимето-

дам современногопрактическогопрограммирования. Предметомизучениякурсаяв-

ляется объектно-ориентированноепрограммирование наязыкеСи++ всредесовре-

менных 32-хразрядныхоперационныхсистемсемейства Windows. Программакурса

разбита на 4 части:

1) ВведениевпрограммированиенаязыкеСи++ (9 лекций)

2) Основыпрограммированиятрехмернойграфики (8 лекций)

3) Объектно-ориентированноепрограммированиенаязыкеСи++ (9 лекций)

4) Программированиедля Microsoft Windows сиспользованием Visual C++ и

библиотеки классов MFC (9 лекций)

На каждоелекционное занятиедолжнобытьпредусмотреноминимумодно

практическое (2 академическихчаса) иеще, всреднем, 4 часасамостоятельныхзаня-

тий. Т.о., наизучениекурсаотводится 72 лекционныхчаса, 72 практических (т.о., 144

аудиторных часа) и 144 часасамостоятельныхзанятий.

Методические материалыдлякурсасформированынаосновепримерно 10-ти

зарубежных изданий, частьизкоторыхпереведенанарусскийязык.

В первойчастикурсарассматриваютсяпроцедурныеосновы языка Си++. Они

включают всебяоформлениетекстапрограмм, правилазаписивыраженийнаСи++,

рассмотрение простыхтиповданныхиалгоритмическихконструкцийусловныхопе-

раторов, циклов_______идр. Вконцеэтойчастикурсаподробнорассматриваютсясоставные

типы данных. Приэтомделаютсязамечанияодостоинствахинедостаткахэтихтипов

данных, чтовпоследствииупрощаетвведениепонятийобъектно-ориентированного

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

Вторая частькурсапосвященаприменениюязыкаСи++ дляпрограммирования

задач вконкретнойпредметнойобласти–трехмернойкомпьютернойграфики. Вка-

честве базовойграфическойбиблиотекивыбранабиблиотека OpenGL, являющаяся

открытым стандартомвданнойобласти. Изучениеэтойбиблиотекидемонстрирует

методику освоенияготовогоинструментария, сформированноговрезультатеприме-

нения методовструктурногопроектированиявконкретнойпредметнойобласти. По-

нятия, относящиесякмашиннойграфике, понятиекаркасаприложенияиобработки

событий иллюстрируютсяпростымипримерамиивдальнейшемиспользуютсяпри

изучении программированиявсреде Windows.

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

граммирования. Основныевопросыобъектно-ориентированногопрограммирования

на Си++ излагаются напримерепрограммированияконсольныхприложений Win32.

Рассматриваются элементарныеприемыобъектно-ориентированногопроектирования

–проектированиенаосновераспределенияобязанностей, метод CRC-карточек.

В четвертойчастикурсаизучаетсяархитектураоперационныхсистемсемейст-

ва Windows иметодыпрограммированиядляэтихОС. Примернотретьэтойчастипо-

священа рассмотрениюосновныхкомпонентоперационныхсистем Windows 9x/NT,

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

этих ОСнаязыкеСи++ науровне Win32 API. Воставшейсячастирассматриваются

приемы программированиядляОС Windows набазебиблиотекиклассов MFC. Эта

библиотека классовявляетсяпромышленнымстандартом, упрощающимразработку

программ ииспользование Win32 API. Подробноописываетсякаркасприложения

MFC, основныеклассыэтойбиблиотеки, приемыиспользованияэтихклассоввсоб-

ственных программах, архитектура однодокументныхприложений "документ/вид".

После изучениякурсастудентполучаетдостаточнополноепредставлениео

содержании современногообъектно-ориентированногопрограммирования, обуст-

ройстве современныхоперационныхсистем Win32 иособытийно-управляемомпро-

граммировании. Напрактическихзанятияхвырабатываютсянавыкипрограммирова-

ния наСи++ винтегрированнойсредеразработки Microsoft Visual C++ 5.0.

ЛЕКЦИЯ 1. Основы Си++

1. Несколько замечаний о назначении программирования

Программирование –этотехническаятворческаядеятельность, целькоторой

заключается врешенииважныхдлячеловеказадачиливыполненииопределенных

действий спомощьюкомпьютера. Нарис. 1 представленаидеализированнаясхема

решения типичнойзадачипрограммирования.

Подробное описание

задачи илинеобходимых

действий КОМПЬЮТЕР

Решение задачиили

выполнение действий

Рис. 1.
Схема решениязадачиспомощьюкомпьютера.

В рамкахтакойсхемынеобходимымикомпонентамикомпьютераявляются

центральный процессор, устройстваввода/выводаипамять (рис. 2).

Рис. 2.
Основные компонентыкомпьютера.

Конечно, вдействительностиделообстоитнетакпросто, какпоказанона

рис. 1. Например, "подробноеописание (спецификация) задачи" наестественномязы-

ке длякомпьютеранегодится (внастоящеевремя). Болеетого, длярешениязадачина

компьютере недостаточнополногоописаниязадачи, необходимотакжеснабдить

компьютер информациейотом, какименноследуетрешатьзадачу–т.е. составитьал-

горитм. Дляописанияалгоритмоврешениязадачилиалгоритмоввыполнениякаких-

либо действий (например, управлениероботом-манипулятором) спомощьюкомпью-

тера применяютсяязыкипрограммирования.

На рис. 3 показанаболееподробнаясхемарешениязадачиспомощьюкомпью-

тера, вкоторойучтенанеобходимостьиспользованияязыкапрограммирования. Ил-

люстрация этойсхемынаконкретномпримереприведенавтаблице 1.

Существует большоеколичестворазличныхязыковпрограммированияимного

способов ихклассификации. Например, "языкамивысокогоуровня" считаютсяте

языки, синтаксискоторыхсравнительно близоккестественномуязыку, втовремякак

синтаксис "низкоуровневых" языковсодержитмноготехническихподробностей, свя-

занных сустройствомкомпьютераипроцессора.

Рис. 3.
Схема решениязадачинакомпьютересиспользованиемязыкапрограммирования.

Таблица 1.
Основные этапырешениязадачипопроверкечисланапростоту.

Спецификация задачи
Требуется определить, являетсялиданноечислопростым.

Алгоритм
Ввести x

Для каждого целого числа z из диапазоне от 1 до x

Если остаток от деления x на z равен 0, то

вывести сообщение "число не простое" и закончить работу

Если такого числа z не найдено, то

вывести сообщение "число простое" и закончить работу

Описание алгоритма на

языке высокого уровня

#include <iostream.h>

int main()

{

int x;

cout << "Введите число:\n";

cin >> x;

for (int z=2; z<x; z++)

if (x % z == 0)

{

cout << "Это не простое число.\n";

return 0;

}

cout << "Это простое число.\n";

return 0;

}

Объектный код (внут-

ренний код конкретного

компьютера)

Двоичные командыпроцессора (частично)

Исполняемый файл для

конкретного компьютера

Двоичные командыпроцессора (полностью)

"Императивные" или "процедурные" языкипозволяютпрограммистуописать, в

какой последовательностикомпьютербудетвыполнятьотдельныешагиалгоритмаи,

таким образом, решатьзадачуивыдаватьнаэкранрезультат. "Декларативные" языки

предназначены большедляописаниясамойзадачиижелаемогорезультата, анедей-

ствий компьютера.

"Объектно-ориентированныеязыки" рассчитанынаприменениеособогопод-

хода кописаниюзадач, согласнокоторомувзадачевыделяютсянекоторые "объекты"

с характернымдляних "поведением" ивзаимодействующиемеждусобой. Одиниз

первых объектно-ориентированныхязыков–Смоллток, онпредназначенисключи-

тельно дляобъектно-ориентированногопрограммирования. Вотличиеотнего, язык

Си++ обладаеткакобъектно-ориентированнымивозможностями, такисредствами

традиционного процедурногопрограммирования.

Радикальные приверженцыразличныхязыковистилей программирования

иногда делаютэкстравагантныезаявления, выделяющиесемействоязыковилиодин

язык какисключительныйиидеальноподходящийдлялюбыхзадач. Например, до-

вольно распространеномнение, чтообъектно-ориентированныйподходнаиболее

близок кспособурешениязадаччеловеком. Поэтомуповодувысовременемсможе-

те составитьсобственноемнение, т.к. абсолютноистинного, очевидно, нет.

2. Происхождение языка Си++

Язык Си++ былразработанвначале 1980-хгг. БьерномСтрауструпомизком-

пании AT&T Bell Laboratories. Си++ основаннаязыкеСи. Двасимвола "++" вназва-

нии –этоиграслов, символами "++" вязыкеСиобозначаетсяоперацияинкремента

(увеличениезначенияпеременнойна 1). Т.о., Си++ был задуманкакязыкСисрас-

ширенными возможностями. БольшаячастьязыкаСивошлавСи++ какподмножест-

во, поэтомумногиепрограммынаСиможноскомпилировать (т.е. превратитьвнабор

низкоуровневых команд, которыекомпьютерможетнепосредственновыполнять) с

помощью компилятораСи++.

При классификацииязыковпрограммированияязыкСивызываетнекоторые

трудности. Посравнениюсассемблером, этовысокоуровневыйязык. ОднакоСисо-

держит многонизкоуровневых средствдлянепосредственныхоперацийспамятью

компьютера. ПоэтомуязыкСиотличноподходитдлянаписанияэффективных "сис-

темных" программ. НопрограммыдругихтиповнаСимогутоказатьсядовольно

сложными дляпонимания, иестьрядошибок, которымпрограммынаСиособенно

подвержены. Дополнительныеобъектно-ориентированныевозможностиСи++ были

добавлены вСи, вчастности, дляустраненияэтихнедостатков.

3. Стандарт ANSI Си++

Национальный ИнститутСтандартизацииСША (American National Standards

Institution, ANSI) разработал "официальные" стандартыдлямногихязыковпрограм-

мирования, втомчиследляСииСи++. Этистандартысталиобщепринятымииони

имеют оченьбольшоезначение. Программу, целикомнаписанную на ANSI Си++, га-

рантированно можнозапуститьналюбомкомпьютере, длякоторогоимеетсякомпи-

лятор ANSI Си++. Другимисловами, стандартгарантируетпереносимостьпрограмм

на языке ANSI Си++.

В действительностибольшинствоверсийСи++ представляютсобойстандарт-

ный ANSI Си++, дополненныйнекоторымимашинно-зависимымивозможностями.

Эти специфическиесредствапредназначеныдляоблегчениявзаимодействияпро-

грамм сконкретнымиоперационнымисистемами. Вообще, впрограммах, которые

должны бытьпереносимыми, подобнымиспецифическимивозможностямиследует

пользоваться какможнореже. ВтакихслучаяхчастипрограммынаСи++, вкоторых

используются не-ANSI компонентыязыка, целесообразноособымобразомпомечать,

так, чтобыихлегкоможнобылоотделитьотосновнойчастипрограммыимодифи-

цировать длядругихкомпьютеровиоперационныхсистем.

4. Среда разработки Microsoft Developer Studio Visual С++

Известно, чтолучшийспособизученияязыкапрограммированиязаключаетсяв

том, чтобыписатьнанемпрограммыипроверять, какониработаютнакомпьютере.

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

•Текстовый редактор, спомощьюкоторогоможнонабиратьиредактировать

исходный текстпрограммнаСи++.

•Компилятор. Этапрограммавыполняетпреобразованиеисходноготекстав

машинные команды, которыекомпьютерможетнепосредственновыпол-

нять.

•Компоновщик, которыйсобираетотдельныескомпилированныечастипро-

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

из готовыхбиблиотек. Врезультатекомпоновкиполучаетсяготоваякза-

пуску программа–исполняемыйфайл.

•Отладчик, спомощьюкотороголегчеискатьошибкивпрограмме. Ошибки

могут обнаружитьсякакприкомпиляции, такивовремяработыпрограм-

мы.

В данномкурсеизученияСи++ практическиеупражненияпредполагаетсявы-

полнять всредеразработкипрограммMicrosoft Developer Studio Visual C++
для

IBM-совместимыхПКподуправлениемWindows 95/NT
. Вэтомпакетеинтегрирова-

ны редактор, компилятор, компоновщикиотладчик. Всевместеониобразуютединую

удобную средупрограммирования. КраткоеописаниеработысосредойVisual C++

приведено вПриложении

.

5. Пример программы на Си++

Ниже приведенисходныйтекстпростойпрограммынаСи++.

// В языке Си++ с двойной косой черты начинаются комментарии

// (например, как эта строка). Компилятор игнорирует комментарии,

// начиная от первой черты и до конца строки.

/* Второй способ записи комментариев – после косой черты со звездочкой.

После текста комментария надо поставить звездочку, а затем – косую

черту. Комментарии, записанные подобным образом, могут занимать

больше одной строки. */

/* В программе ОБЯЗАТЕЛЬНО должно быть достаточное количество

комментариев! */

/* Эта программа запрашивает у пользователя текущий год, возраст

пользователя и еще один год. Затем программа вычисляет возраст

пользователя, который будет у него во втором введенном году.*/

#include <iostream.h>

int main()

{

int year_now, age_now, another_year, another_age;

cout << "Введите текущий год и нажмите ENTER.\n";

cin >> year_now;

cout << "Введите свой возраст (в годах).\n";

cin >> age_now;

cout << "Введите год, для которого вы хотите узнать свой возраст.\n";

cin >> another_year;

another_age = another_year - (year_now - age_now);

if (another_age >= 0)

{

cout << "В " << another_year << " году вам будет ";

cout << another_age << "\n";

}

else

{

cout << "В " << another_year << " вы еще не родились!\n";

}

return 0;

}

Программа 5.1.

Некоторые свойствапрограммы 5.1 являютсяобычнымидлябольшинствапро-

грамм наСи++. Программаначинается (послекомментариев) соператора

#include <iostream.h>

Этот операторназывается "директивойinclude". Докомпилятораисходный

текст обрабатываетсяпрепроцессором
–специальнойпрограммой, котораямодифи-

цирует текстпрограммыпоспециальнымкомандам–директивам. Директивыпре-

процессора начинаютсяссимвола "#". Директиваinclude предназначена длявклю-

чения висходныйтекстсодержимогодругогофайла. Например, впрограмму 5.1

включается файлiostream.h, содержащийописанияфункцийстандартнойбиблиоте-

ки ввода/выводадляработысклавиатуройиэкраном. (Стандартныебиблиотекиязы-

ка Си++ будутрассматриватьсяпозже).

Алгоритм, записанныйвпрограмме 5.1, оченьпростой. Поэтомуструктуру

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

(операторов). Схематичнопрограмму, содержащуюсяпоследирективы#include,

можно представитьввиде:

int main()

{

Первый оператор
;

...

Последний оператор
;

return 0;

}

Подобная структураявляетсяобщейдлявсехпрограммнаСи++. Каждыйопе-

ратор втелепрограммызавершаетсяточкойсзапятой. Вхорошоразработанной

большой программебольшинствооператоровявляютсяобращениями (вызовами) к

подпрограммам, которыезаписываютсяпосле функцииmain() или вотдельных

файлах. Каждаяподпрограмма (функция) имеетструктуру, подобнуюфункции

main(). Нофункцияmain() в каждойпрограмметолькоодна. Именноснееначина-

ется выполнениепрограммы. (Подробнеефункциибудутрассматриватьсядалее.)

В концефункцииmain() записана строка:

return 0;

Эта строказначит "вернутьоперационнойсистемевкачествесигналаобус-

пешном завершениипрограммызначение 0". Операторвозвратаreturn применяется

не толькопризавершениипрограммы, ноипризавершенииотдельныхподпрограмм.

В любомслучаеэтотоператорвозвращаетопределенноезначениенаболеевысокий

уровень управления.

В программе-примереиспользуются четырепеременные
:

year_now, age_now, another_year и another_age

Переменные впрограммированииотличаютсяотматематическихпеременных.

Они используютсякаксимволические имена "фрагментовоперативнойпамятиком-

пьютера". Привыполнениипрограммывразличныемоментывременипеременные

могут хранитьразличныезначения. Впрограмме 5.1 первоеупоминаниечетырехпе-

ременных содержитсявстрокесоператоромописанияпеременных:

int year_now, age_now, another_year, another_age;

Этот операторуведомляеткомпилятор, что дляхранениячетырехпеременных

типа "целоечисло" (integer –int) требуетсявыделитьнеобходимоеколичествопамя-

ти. Этаобластьпамятибудетзарезервированавтечениевыполненияоставшейсячас-

ти программы. Переменныевсегдадолжныбытьописаныдопервогоиспользования.

В программированиихорошимстилемсчитаетсяописаниевсехпеременных, исполь-

зуемых вподпрограмме, вначалеэтойподпрограммы. ВСи++ естьнесколькораз-

личных типовпеременных, ионибудутобсуждатьсянемногопозже.

6. Выполнение ввода/вывода данных и присваивание значений

После компиляции
программы ееможнозапустить на выполнение
. Результат

выполнения наэкранебудетвыглядетьпримернотак:

Введите текущий год и нажмите ENTER.

2000

Введите свой возраст (в годах).

Введите год, для которого вы хотите узнать свой возраст.

2017

В 2017 году вам будет 38

Первая, третья, пятаяиседьмаястрокивыдаютсянаэкранпрограммойспо-

мощью следующегооператора:

cout << Выражение1
<< Выражение2
<< ... << ВыражениеN
;

Этот операторвыводитнаэкрансообщение:

Выражение
1 Выражение
2 ... Выражение
N

Последовательность операторов

cout << Выражение
1;

cout << Выражение
2;

...

cout << Выражение
N;

приводит каналогичномурезультату. Еслимеждувыражениямитребуетсявставить

пробелы илиновыестроки, тоихнужноуказатьявно, спомощьюсимволов" " и

"\n" соответственно.

Числа, показанныевышевпримеревыдачинаэкранполужирным
шрифтом, бы-

ли напечатаныпользователем. Впоказанномпримере оператор

cin >> year_now;

приводит ктому, чтопеременнойyear_now присваивается
значение 2000
. Этопроис-

ходит послетого, какпользовательнапечатает "2000
" инажметклавишуEnter
. В

программе естьещеместа, гдепеременнымприсваиваютсязначения, втом числе

оператор присваивания:

another_age = another_year - (year_now - age_now);

Операция "=" означает "присвоитьпеременной, стоящейслеваотзнакаравен-

ства, значение, указанноесправа". ПроверканаравенствовСи++ обозначается двой-

ным символом: "==".

7. Управление порядком выполнения команд с помощью оператора if

В несколькихпоследнихстрокахпрограммы (достроки "return 0") записано:

if (another_age >= 0)

{

cout << "В " << another_year << " году вам будет ";

cout << another_age << "\n";

}

else

{

cout << "В " << another_year << " вы еще не родились!\n";

}

Оператор ветвления (условныйоператор) "if...else..." выглядитпримерно

одинаково вовсехпроцедурныхязыкахпрограммирования. ВСи++ онназывается

просто оператором if
, иегообщаяструктуратакова:

if ( условие )

{

Оператор
1;

...

Оператор
N;

}

else

{

Оператор
N+1;

...

Оператор
N+M;

}

Часть "else (иначе)" воператореif необязательна. Болеетого, еслипосле

"if ( условие )" стоиттолькоодиноператор, томожноопуститьфигурныескобкии

записать оператортак:

if ( условие )

Оператор
1;

В программахусловныеоператорычастовстречаютсягруппами, например:

...

if (total_test_score < 50)

cout << "Вы не прошли тест. Выучите материал как следует.\n";

else if (total_test_score < 65)

cout << "Вы прошли тест со средним результатом.\n";

else if (total_test_score < 80)

cout << "Вы хорошо выполнили тест.\n";

else if (total_test_score < 95)

cout << "Вы показали отличный результат.\n";

else

{

cout << "Вы сдали тест нечестно!\n";

total_test_score = 0;

}

...

Приведенный фрагментпрограммыможетпоказатьсядовольносложным. Тем

не менее, онсоответствуетправиламСи++. Этолегкопонять, еслиобратитьсяксин-

таксической диаграммеоператораif (рис. 4).

В овальныхиликруговыхрамкахнасинтаксическихдиаграммахуказываются

элементы языка, которыебуквальнотакивоспроизводятсявисходномтекстепро-

грамм. Впрямоугольныхрамкахприведеныэлементы, требующиедальнейшегооп-

ределения, возможно, спомощьюдругихсинтаксическихдиаграмм. Набортакихдиа-

грамм служитформальнымописаниемсинтаксисаязыкапрограммирования.

Обратите внимание, чтонарис. 4 отсутствуетсимвол ";" иразделители "{}".

Эти элементыязыкавключенывопределение (исинтаксическуюдиаграмму) для

обобщенного понятия "операторязыкаСи++".

Рис. 4.
Синтаксическая диаграммаоператораif.

При обработкеприведенногофрагментапрограммыкомпиляторСи++ трактует

весь текст, выделенныйнижеполужирнымшрифтом, какодиноператорпослеперво-

го словаelse.

...

if (total_test_score < 50)

cout << "Вы не прошли тест. Выучите материал как следует.\n";

else if (total_test_score < 65)

cout << "Вы прошли тест со средним результатом.\n";

else if (total_test_score < 80)

cout << "Вы хорошо выполнили тест.\n";

else if (total_test_score < 95)

cout << "Вы показали отличный результат.\n";

else

{

cout << "Вы сдали тест нечестно!\n";

total_test_score = 0;

}

...

8. Оформление исходного текста

Между текстомпрограммы, приведеннымвп.5 итекстом, которыйпоказан

ниже, длякомпилятораСи++ нетникакихразличий.

#include <iostream.h> int main() { int year_now, age_now, another_year,

another_age; cout << "Введите текущий год и нажмите ENTER.\n"; cin >>

year_now; cout << "Введите свой возраст (в годах).\n"; cin >> age_now;

cout << "Введите год, для которого вы хотите узнать свой возраст.\n"; cin

>> another_year; another_age = another_year - (year_now - age_now); if

(another_age >= 0) { cout << "В " << another_year << " году вам будет ";

cout << another_age << "\n"; } else { cout << "В " << another_year << "

вы еще не родились!\n"; } return 0; }

Отсутствие комментариев
, пробелов
, пустых строк
и отступов
делают эту

программу практическинепригоднойдлячтениячеловеком. Длявыработкихорошего

стиля программирования, конечно, требуется знатьнетолькоправилаоформления

текста программы, ноихследуетсоблюдатьссамогоначала. Приоформлениисобст-

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

отражали логическуюструктурувашихпрограмм.

Для переменныхследуетвыбиратьосмысленныеимена: имена "year_now",

"age_now", "another_year" и "another__age" лучше, чем "y_n", "a_n", "a_y" и

"a_a" инамноголучше, чем "w", "x", "y" и "z". Этоособенноважно, есливбудущем

ваши программымогутпотребоватьизмененияспомощьюдругихпрограммистов.

9. Сводка результатов

В даннойлекциикраткоинеформальнобылирассмотренынескольковажных

вопросов: переменныеитипыданных, вводивывод, оператор присваиванияиуслов-

ный оператор ("операторif"). Болеестрогоиподробноэтивопросыбудутрассмот-

рены впоследующихлекциях.

10. Упражнения

Для выполненияэтихупражненийтребуетсянекоторыйопытработысПКпод

управлением операционнойсистемыWindows 95/NT
.

Упражнение 1

Изучите краткоеруководствопоVisual C++
в Приложении

. Создайтепроектс

именем "AgeCalculator". СоздайтеисходныйфайлсименемAgeCalculator.cpp

и наберитевнемисходныйтекстпрограммы 5.1. Сохранитефайлнадискеидобавьте

его впроект. Соберитепроектизапуститепрограммунавыполнение.

Возможно, вывстретитесьсоследующимипроблемами:

1) В окне программы вместо русских букв выводятся какие-то странные символы.

Эта проблемаобъясняетсяразличиемтаблицкодировокWindows
и DOS
. В этих таблицах

русские буквырасположенывразныхместах. Консольныепрограммыприработеисполь-

зуют кодировкуDOS
, атекстовыйредакторVisual C++
–кодировкуWindows
. Поэтому

вам придетсядобавитьпреобразованиестроксрусскимибуквамиизкодировкиWindows

в кодировкуDOS
.

Для этоговключитевпрограмму, послефайлаiostream.h, файлwindows.h с описа-

нием функцийоперационнойсистемыWindows
:

#include <windows.h>

Перед функциейmain() создайте новуюфункциюсименем rus_str(), котораябудетвы-

полнять необходимоепреобразованиеспомощьюспециальнойфункцииWindows
:

char* rus_str( char* str )

{

CharToOem( str, str );

return str;

}

Во всехстрокахпрограммы, гденаэкранвыдаютсясимвольныестрокисрусскимибук-

вами, укажитепреобразованиеэтихстрокспомощьюновойфункции, например:

cout << rus_str( "Введите текущий год и нажмите ENTER.\n" );

2) После завершения работы окно программы закрывается и не удается увидеть ре-

зультаты.

Для исправленияэтогонедостаткапрощевсегопредусмотретьвконцепрограммыввод

произвольного символа. Покапользовательненажметкакую-нибудьсимвольнуюклави-

шу ипотомEnter
, окнопрограммыбудетоставатьсянаэкране. Дляэтогопотребуетсяза-

вести символьнуюпеременную (строкусописаниемэтойпеременнойрасположитепосле

строки сописаниемцелочисленныхпеременных):

char wait_char;

Перед строкойсоператоромвозврата "return 0" добавьтеоператордлявводасимвола

с клавиатуры:

cin >> wait_char;

Сравните результатыработысвоейпрограммыспримеромизлекции. Поэкс-

периментируйте надулучшениемилиизменениемформатавыводанаэкран.

Упражнение 2

Модифицируйте программу 5.1, чтобыприпревышениипеременной

"another_age" значения150
на экранвыводилосьсообщение:

Извините, но вы вряд ли доживете до [year]
года!

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

Упражнение 3

Измените программуизупр.2 так, чтобывнейучитывалисьигоды, имесяцы.

На экранпрограммадолжнавыводитьследующиесообщения:

Введите текущий год и нажмите ENTER.

2000

Введите текущий месяц (число от 1 до 12).

Введите свой возраст (в годах).

Введите месяц своего рождения (число от 1 до 12).

Введите год, для которого вы хотите узнать свой возраст.

2006

Введите месяц этого года.

Ваш возраст в 6/2006: 31 год и 1 месяц.

Программа должнавыдаватькорректныесообщениядляединственногоимно-

жественного числалетимесяцев, т.е. должнавыводитьнаэкран "25 лет и 1 ме-

сяц", но "24 года и 2 месяца".

Подсказка:

В программе вам потребуются дополнительные переменные. Обязатель-

но добавьте их имена в оператор описания переменных. При вычислениях могут при-

годиться некоторые стандартные операции Си++:

Символ Операция Пример Значение

+
Сложение 3 + 5 8

-
Вычитание 43 - 25 18

*
Умножение 4 * 7 28

/
Деление 9/2 4

%
Остаток приделе-

нии нацело

20 % 6 2

(Обратите внимание, что в приведенной таблице операция деления "/" применялась к

двум целым числам, поэтому результат – тоже целое число.)

Кроме арифметических операций, для проверки условий в операторе
if
вам могут

потребоваться некоторые логические операции.

Символ Операция Пример Значение

<
меньше, чем 3 < 5 TRUE (истина)

<=
меньше илиравно 43 <= 25 FALSE (ложь)

>
больше, чем 4 > 7 FALSE

>=
больше илиравно 9 >= 2 TRUE

==
равно 20 == 6 FALSE

!=
не равно 20 != 6 TRUE

&&
Логическое И 5 > 2 && 6 > 10 FALSE

||
Логическое ИЛИ 5 > 2 || 6 > 10 TRUE

ЛЕКЦИЯ 2. Переменные, типы данных и выражения

1. Идентификаторы

В исходномтекстепрограммнаСи++ используетсядовольномногоанглий-

ских словиихсокращений. Всеслова (идентификаторы), встречающиесявпрограм-

мах, можноразделитьнатрикатегории:

1) Служебные слова языка.
Например, этословаif, int и else. Назначение

этих словпредопределеноиегонельзя изменить. Нижеприведенболее

полный списокслужебныхслов:

asm continue float new signed try

auto default for operator sizeof typedef

break delete friend private static union

case do goto protected struct unsigned

catch double if public switch virtual

char else inline register template void

class enum int return this volatile

const extern long short throw while

По назначениюэтисловаможноразбитьнаотдельныегруппы (прил. 8.1).

2) Библиотечные идентификаторы.
Назначение этихсловзависитотсреды

программирования. Вслучаесерьезнойнеобходимостипрограммистможет

изменить ихсмысл. Примерытакихслов: cin, cout и sqrt (имяфункции

извлечения квадратногокорня).

3) Идентификаторы, введенные программистом.
Эти слова "создаются"

программистом –например, именапеременных (такие, какyear_now и another_

age в программе 1.5.1).

Идентификатором не можетбытьпроизвольнаяпоследовательностьсимволов.

По правиламСи++, идентификаторначинаетсясбуквыилисимволаподчеркивания

("_") исостоиттолькоизанглийскихбукв, цифрисимволовподчеркивания.

2. Типы данных

2.1 Целые числа

Правила Си++ требуют, чтобывпрограммеувсехпеременныхбылзадантип

данных. Типданныхint встречался намуженеоднократно. Переменныеэтоготипа

применяются дляхраненияцелыхчисел (integer). Описаниепеременной, какимею-

щей типint, сообщаеткомпилятору, чтоондолженсвязатьсидентификатором

(именем) переменнойколичествопамяти, достаточноедляхраненияцелогочиславо

время выполненияпрограммы.

Границы диапазонацелыхчисел, которыеможнохранитьвпеременныхтипа

int, зависятотконкретногокомпьютера. ВСи++ естьещедвацелочисленныхтипа–

short int и long int. Онипредставляют, соответственно, болееузкийиболее

широкий диапазонцелыхчисел, чемтипint. Добавлениеклюбомуизэтихтипов

префикса unsigned означает, чтовпеременной будутхранитсятольконеотрица-

тельные числа. Например, описание:

unsigned short int year_now, age_now, another_year, another_age;

резервирует памятьдляхранениячетырехотносительнонебольшихнеотрицательных

чисел.

Приведем несколькополезныхправил, касающихсязаписицелочисленных

значений висходномтекстепрограмм.

1) Нельзяпользоватьсядесятичнойточкой. Значения 26 и 26.0 одинаковы, но

"26.0" неявляетсязначениемтипа "int".

2) Нельзяпользоватьсязапятымивкачестверазделителейтысяч. Например,

число 23,897 следуетзаписывать как "23897".

3) Целыезначениянедолжныначинатьсяснезначащегонуля. Онприменяется

для обозначенияустаревшихвосьмеричныхчисел, такчтокомпиляторбу-

дет рассматриватьзначение "011" какчисло 9 ввосьмеричнойформе.

2.2 Вещественные числа

Для хранениявещественныхчиселприменяютсятипыданныхfloat и

double. Смысл знаков "+" и "-" длявещественныхтиповсовпадаетсцелыми. По-

следние незначащиенулисправаотдесятичнойточкиигнорируются. Поэтомувари-

анты записи "+523.5", "523.5" и "523.500" представляютодноитожезначение. В

Си++ такжедопускаетсязаписьвформатес плавающей запятой
(вэкспоненциальном

формате) ввидемантиссы
и порядка
. Например, 523.5 можнозаписатьввиде

"5.235e+02" (т.е. 5.235*10*10), а -0.0034 ввиде "-3.4e-03".

В большинствеслучаевиспользуетсятипdouble, онобеспечиваетболеевысо-

кую точность, чемfloat. Максимальнуюточностьинаибольшийдиапазончисел

достигается спомощьютипаlong double, ноонтребуетбольшепамяти (в

Visual C++
10 байтначисло), чем double (8 байт).

2.3 Преобразование типов в выражениях

При выполнениивычисленийиногдабываетнужногарантировать, чтоопреде-

ленное значениебудетрассматриватьсякаквещественноечисло, дажееслинасамом

деле это целое. Чащевсегоэтонужноприделенииварифметическихвыражениях.

Применительно кдвумзначениямтипаint операция деления "/" означаетделение

нацело, например, 7/2 равно 3. Вданномслучае, еслинеобходимополучитьрезультат

3.5, томожнопростодобавитьдесятичнуюточкувзаписиодногоилиобоихчисел:

"7.0/2", "7/2.0" или "7.0/2.0". Ноеслиивчислителе, ивзнаменателестоятперемен-

ные, анеконстанты, тоуказанныйспособнеподходит. Вместонегоможноприме-

нить явноепреобразованиетипа. Например, значение "7" преобразуетсявзначение

типа double с помощьювыражения "double(7)". Поэтомуввыражении

answer = double(numerator) / denominator

операция "/" всегдабудетрассматриватьсякомпиляторомкаквещественноеделение,

даже если "numerator" и "denumerator" являютсяцелымичислами. Дляявногопреоб-

разования типовможнопользоватьсяидругимиименамитиповданных. Например,

"int(14.35)" приведеткполучениюцелогочисла14.

2.4 Символьный тип

Для хранениясимвольныхданныхвСи++ предназначентип "char". Перемен-

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

или пробела). Впамятикомпьютерасимволыхранятсяввидецелыхчисел. Соответ-

ствие междусимволамииихкодамиопределяетсятаблицейкодировки, котораязави-

сит откомпьютераиоперационнойсистемы. Почтивовсехтаблицахкодировкиесть

прописные истрочныебуквыанглийскогоалфавита, цифры0,...,9, инекоторые

специальные символы, например, #, ., !, +, - и др. Самойраспространеннойтаблицей

кодировки, скореевсего, является таблицасимволов ASCII.

В текстепрограммсимвольныеконстантытипа "char" надозаключатьводи-

ночные кавычки, иначекомпиляторпойметихнеправильноиэтоможетпривестик

ошибке компиляции, или, чтоещехуже, кошибкамвременивыполнения. Например,

"'A'" являетсясимвольнойконстантой, но "A" будетрассматриватьсякомпиляторомв

качестве именипеременной. Аналогично, "'9'" являетсясимволом, а "9" –целочис-

ленной _______константой.

Т.к. впамятикомпьютерасимволыхранятсяввидецелыхчисел, тотип "char"

на самомделеявляетсяподмножествомтипа "int". НаСи++ разрешаетсяиспользо-

вать символыварифметическихвыражениях. Например, налюбомкомпьютерес

таблицей ASCII следующеевыражениедастистинноезначение (TRUE, или1):

'9'-'0' == 57-48 == 9

В таблице ASCII кодомсимвола '9' являетсядесятичноечисло 57 (вшестнадца-

теричной записи 0x39), а ASCII–код символа '0' равендесятичномучислу 48 (шестна-

дцатеричное значение 0x30). Приведенноевыражениеможнопереписатьввиде:

57-48 == 0x39-0x30 == 9

Кодами ASCII удобнеепользоватьсявшестнадцатеричнойформе. Призаписи

шестнадцатеричных чиселвСи++ применяетсядвухсимвольныйпрефикс "0x".

Переменные типа "char" существенноотличаютсяот "int" привыполнении

ввода данныхсклавиатурыивыводанаэкран. Рассмотримследующуюпрограмму.

#include <iostream.h>

int main()

{

int number;

char character;

cout << "Напечатайте символ и нажмите Enter:\n";

cin >> character;

number = character;

cout << "Вы ввели символ '" << character;

cout << "'.\n";

cout << "В памяти компьютера он хранится в виде числа ";

cout << number << ".\n";

return 0;

}

Программа 2.1.

Программа 2.1 выдаетнаэкранследующиесообщения:

Напечатайте символ и нажмите Enter:

Вы ввели символ '9'.

В памяти компьютера он хранится в виде числа 57.

Программу 2.1 можноизменитьтак, чтобыонапечаталавсютаблицусимволов

ASCII. Дляэтогопридетсяприменить "операторциклаfor". "Циклfor" является

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

следующих лекций. Операторfor имеет следующийсинтаксис:

for (инициализация
; условие_повторения
; изменение_значений
)

{

Оператор
1;

...

Оператор
N;

}

Цикл for выполняется вследующемпорядке: (1) Сначалавыполняетсяопера-

тор инициализации
. (2) Выполняетсяпроверка, являетсялиусловие_повторения
истин-

ным. Еслиусловиеложно, тооператор for завершается. Еслиусловиеистинно, то

последовательно выполняютсяоператорытелациклаОператор
1...Оператор
N, изатем

выполняется операторизменение_значений
. Послеэтогопроисходитпереходнанача-

ло шага (2).

Чтобы кодсимволавывестинаэкранвшестнадцатеричнойформе, надоснача-

ла послатьнаэкранслужебный символ-манипулятор. Программадляпечатифраг-

мента таблицы ASCII (от 32-госимвола (пробел) до 126-го (символ '~')), будетвыгля-

деть так:

#include <iostream.h>

int main()

{

int number;

char character;

for (number = 32; number <= 126; number = number + 1 )

{

character = number;

cout << "Символ '" << character;

cout << "' имеет код ";

cout << dec << number << " (дес.) или ";

cout << hex << number << " (шестнд.).\n";

}

return 0;

}

Программа 2.2.

Программа 2.2 напечатаетнаэкране:

Символ ' ' имеет код 32 (дес.) или 20 (шестнд.).

Символ '!' имеет код 33 (дес.) или 21 (шестнд.).

...

Символ '}' имеет код 125 (дес.) или 7D (шестнд.).

Символ '~' имеет код 126 (дес.) или 7E (шестнд.).

2.5 Символьные строки

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

используются символьныестроки. ВСи++ символьныестрокизаключаютсявдвой-

ные кавычки. Поэтомувпрограммахчастовстречаются операторывыводавроде:

cout << "' имеет код ";

На самомделевСи++ строковыйтип ("string") неявляетсястандартнымти-

пом данных, таким, как, например, "int", "float" или "char". Строкихранятсявпамя-

ти ввидесимвольныхмассивов, поэтомустрокибудутрассматриватьсяпозднее, при

изучении массивов.

2.6 Типы данных, определяемые пользователем

Вопрос отипахданных, определяемыхпользователем, будетобсуждатьсяна-

много болееподробновпоследующихлекциях. Будетпоказано, какпрограммист

может определитьсобственныйтипданных, необходимыйдлярешенияконкретной

задачи. Средстваопределенияновыхтиповданных–однаизнаиболеемощныхвоз-

можностей Си++, которыепозволяютхранитьиобрабатыватьвпрограммахнаСи++

сложные структурыданных.

3. Вывод вещественных чисел на экран

При выводенаэкранчисленныхзначенийтипа "float", "double" или "long

double" возможноуказаниеточностипредставленияданныхнаэкранеизаданиене-

которых дополнительныхпараметровотображения, например, отображениезначений

в форматесфиксированнойилиплавающейточкой.

В программе 3.1 вещественноечислоотображаетсявформатесфиксированной

точкой идвумядесятичнымизнакамипослезапятой. Идентификатор "sqrt" является

именем библиотечнойфункцииизвлеченияквадратногокорня. Описаниебиблиотеки

математических функций содержитсявзаголовочномфайле "math.h".

#include <iostream.h>

#include <math.h>

int main()

{

float number;

cout << "Введите вещественное число.\n";

cin >> number;

cout << "Корень из ";

cout.setf(ios::fixed); // СТРОКА 12

cout.precision(2);

cout << number;

cout << " примерно равен " << sqrt( number ) << ".\n";

return 0;

}

Программа 3.1.

Программа 3.1 напечатаетнаэкране:

Введите вещественное число.

200

Корень из 200.00 примерно равен 14.14.

Если СТРОКУ 12 заменитьна "cout.setf(ios::scientific);", товидрезульта-

та изменится:

Введите вещественное число.

200

Корень из 2.00e+02 примерно равен 1.41e+01.

В выходныеданныеможновключитьпараметрытабуляции. Дляэтогопредна-

значена функцияшириныполя, например, "cout.width(20)". Оназадаетширинусле-

дующего выводимогонаэкранзначенияравной, какминимум, 20 символам (при

меньшей ширинеавтоматическибудутдобавленыпробелы). Этавозможностьосо-

бенно полезнадляпечатитаблиц.

В компилятореVisual C++
при указаниишириныполяпоумолчаниюпредпо-

лагается, чтозначениявыравниваютсяпоправойгранице. Чтобызадатьвыравнива-

ние полевойграницеполя, потребуетсяиспользоватьещенесколькоманипуляторов

ввода-вывода. Этоспециальныефункциииоператоры, содержащиесявбиблиотеке

ввода/выводаСи++. Ониописанывзаголовочномфайлеiomanip.h. Для заданиявы-

равнивания полевойграниценадоустановитьспециальныйфлажок (переключатель)

с помощьюфункцииsetiosflags:

#include <iostream.h>

#include <iomanip.h>

#include <math.h>

int main()

{

int number;

cout << setiosflags( ios::left );

cout.width(20);

cout << "Число" << "Квадратный корень\n\n";

cout.setf( ios::fixed );

cout.precision(2);

for ( number = 1 ; number <= 10 ; number = number + 1 )

{

cout.width(20);

cout << number << sqrt(number) << "\n";

}

return 0;

}

Программа 3.2.

Программа 3.2 выдастнаэкранследующиесообщения:

Число Квадратный корень

1 1.00

2 1.41

3 1.73

4 2.00

5 2.24

6 2.45

7 2.65

8 2.83

9 3.00

10 3.16

(ПРИМЕЧАНИЕ
: вовсехпримерахидентификатор "cout" являетсяименемперемен-

ной-объектакласса "stream" (поток). Функции "setf(...)", "precision(...)" и

"width(...)" являютсяфункциями-членами класса "stream". Понятия "объект",

"класс", "функция-член" идр. будутподробнорассматриватьсявкурсеобъектно-

ориентированного программирования.)

4. Описания, константы и перечисления

Как выужезнаете, впрограммахнаСи++ переменныеобязательнодолжны

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

float number;

После оператораописаниядомоментавыполненияпервогооператорапри-

сваивания значениепеременной "number" будетнеопределенным, т.е. этапеременная

может иметьслучайноезначение. ВСи++ можно (ижелательно) инициализировать

переменные конкретнымизначенияминепосредственноприописаниипеременных.

Например, возможенследующийоператорописаниясинициализацией:

float PI = 3.1416;

Если значениепеременнойвпрограмменикогданеизменяется, тоеецелесооб-

разно защититьотслучайногоизмененияспомощьюслужебногослова "const" –т.е.,

превратить вконстанту.

4.1 Тип "Перечисление"

Для описаниянаборасвязанныхпосмыслуконстанттипа "int" вСи++ есть

оператор перечисления. Например, описаниевида

enum { MON, TUES, WED, THURS, FRI, SAT, SUN };

эквивалентно описанию 7 констант-кодовднейнедели:

const int MON = 0;

const int TUES = 1;

const int WED = 2;

const int THURS = 3;

const int FRI = 4;

const int SAT = 5;

const int SUN = 6;

По умолчаниючленамперечисления "enum" присваиваютсязначения 0, 1, 2, и

т.д.. Принеобходимостичленыперечисленияможноинициализироватьдругимизна-

чениями. Неинициализированнымявночленамбудутприсвоенызначенияпопоряд-

ку, начинаяотпредыдущегопроинициализированногочлена:

enum { MON = 1, TUES, WED, THURS, FRI, SAT = -1, SUN };

В приведенномпримере "FRI" имеетзначение 5, а "SUN" –значение 0.

4.2 Расположение описаний констант и переменных в исходном тексте

В исходномтекстеописанияконстантчащевсегоразмещаютсявзаголовке

программы передфункцией "main". Послених, ужевтелефункции "main", размеща-

ются описанияпеременных. Дляиллюстрацииэтогопорядканижеприведенфраг-

мент программы, котораярисуетнаэкранеокружностьзаданногорадиусаивычисля-

ет еедлину (набиратьэтотпримерненадо, посколькуонприведеннеполностью.)

#include <iostream.h>

const float PI = 3.1416;

const float SCREEN_WIDTH = 317.24;

int drawCircle(float diameter); /* Это "прототип функции" */

int main()

{

float radius = 0;

cout << "Введите радиус окружности.\n";

cin >> radius;

drawCircle(radius*2);

cout.setf(ios::fixed);

cout.precision(2);

cout << "Длина окружности радиуса " << radius;

cout << " примерно равна " << 2*PI*radius << ".\n";

return 0;

}

int drawCircle(float diameter)

{

float radius = 0;

if (diameter > SCREEN_WIDTH)

radius = SCREEN_WIDTH/2.0;

else

radius = diameter/2.0;

...

}

После определенияфункции "main()" вэтойпрограммесодержитсяопределе-

ние функциирисованияокружности "drawCircle(...)". Деталиреализацииэтой

функции сейчаснесущественны (будемсчитать, чтофункцияdrawCircle(...)" реа-

лизована корректноиеюможнопользоватьсятакже, как, например, функцией

"sqrt(...)"). Обратитевнимание, что, хотяпеременная "radius" используетсявобеих

функциях "main()" и "drawCircle(...)", этонеоднаитажепеременная, адверазных
.

Если быпеременная "radius" былаописанадофункции "main", товтакомслу-

чае онабылабыглобальной переменной
(общедоступной). Тогда, предполагая, что

внутри функции "drawCircle(...)" описанияпеременнойуженет, если "drawCircle(...)"

присвоит глобальнойпеременнойзначение "SCREEN_WIDTH/2.0", тоэто

значение чутьпозжефункция "main()" используетдлявычислениядлины окружности

и получитсяневерныйрезультат.

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

переменных "radius". Например, перваяпеременная "radius" являетсялокальной
пе-

ременной функции "main()", или, говорят, чтофункция "main()" являетсяобластью

видимости
этой переменной.

Константы общегоназначения, такие, как "PI" и "SCREEN_WIDTH", принятоопи-

сывать глобально
, чтобыонибылидоступнывнутрилюбойфункции.

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

повторное отображениеданных, введенныхпользователем. Другимисловами, задан-

ное пользователемзначение "radius" ещеразпечатаетсянаэкранепередотображени-

ем длиныокружности.

5. Присваивание и выражения

5.1 Краткая форма записи операторов присваивания

В программахчастовстречаютсяоператорыприсваивания, вкоторыхсправа

стоит выражение, модифицирующеетекущеезначениепеременной, например:

number = number + 1;

Переменным частоприсваиваютсязначения, вычисленныенаосновеихстарых

значений. ПоэтомувСи++ былавведена краткаяформазаписидляподобныхопера-

торов присваивания. Любуюизопераций "+" (сложение), "-" (вычитание), "*" (умно-

жение), "/" (деление) и "%" (остатокотделениянацело) можноуказатьвкачестве

префикса оператораприсваивания ("=") (cм. следующуютаблицу).

Пример:

number += 1;

total -= discount;

bonus *= 2;

time /= rush_factor;

change %= 100;

amount *= count1 + count2;

Эквивалентное выражение:

number = number + 1;

total = total - discount;

bonus = bonus * 2;

time = time / rush_factor;

change = change % 100;

amount = amount * (count1 + count2);

Первый примердопускаетещеболеекраткуюзаписьспомощью оператораин-

кремента "++":

number++;

Оператор "++" существуетивпрефикснойформе:

++number;

Постфиксная ипрефикснаяформазаписиимеютважноеразличие, котороене-

обходимо помнить. ПрефиксныйоператорприменяетсяДО
вычисления остальной

части выражения, апостфиксный–ПОСЛЕ
. Например, посолевыполненияоперато-

ров

x = 4;

y = x++;

переменная "x" получитзначение 5, а "y" –значение 4. Вслучаеоператоров

x = 4;

y = ++x;

обе переменныеполучатзначение 5. Этообъясняетсятем, что "++x" выполняетсядо

того, какзначение "x" будетиспользовановвыражении, а "x++" –после. ВСи++ су-

ществует аналогичныйоператордекремента "--", уменьшающийзначениеперемен-

ной на 1, иунеготожеестьпрефикснаяипостфикснаяформа.

Вообще, выражениесоператоромприсваиванияимеетзначение, равноезначе-

нию левойчастипослевыполненияприсваивания. Нижеприведеновыражение, соот-

ветствующее правиламСи++, котороеможноиспользоватьдляпроверкиусловия:

(y = ++x) == 5

Это выражениеозначаетследующее: "послеприсвоенияпеременнойy инкре-

ментированного значенияx проверить, неравнолизначениеy числу 5".

5.2 Логические выражения и операторы

Интуитивно логическиевыражениянаподобие "2<7", "1.2!=3.7" и "6>=9" вос-

принимаются человекомкакутверждения, которыемогутбыть "истинными (true)"

или "ложными (false)" (операция "!=" означает "неравно"). Допускаетсяобъеди-

нение несколькихподобныхвыраженийвболеесложноевыражениеспомощью ло-

гических операций "&&" ("И"), "||" ("ИЛИ") и "!" ("НЕ") (см. таблицу).

Выражение:

(6 <= 6) && (5 < 3)

(6 <= 6) || (5 < 3)

(5 != 6)

(5 < 3) && (6 <= 6) || (5 != 6)

(5 < 3) && ((6 <= 6) || (5 != 6))

!((5 < 3) && ((6 <= 6) || (5 != 6)))

Истинно или ложно:

false

true

false

true

В таблицевчетвертомпримеревыражениеистинно, посколькуприоритетопе-

рации "&&" выше, чему "||". Приоритет (порядоквыполнения) различныхопераций

Си++ можноузнатьвучебникеилируководствепоязыкуСи++, атакжевсправочной

системе Visual C++
(темаOperator Precedence
). Еслиувасвозникаютсомненияотно-

сительно приоритетаопераций, применяйтекруглыескобки(). Применениеэтих

скобок облегчаетчтениепрограмм.

Составные логическиевыраженияобычноприменяютсявкачествеусловийв

операторах if и вциклахfor. Например:

...

if ( total_test_score >= 50 && total_test_score < 65 )

cout << "Вы прошли тест со средним результатом.\n";

...

У логических выраженийвСи++ естьещеодноважноесвойство. ВСи++ ис-

тинное значение ("true") представляетсяввидецелогочисла 1 (большинство ком-

пиляторов любоеположительноечислосчитаютистиннымзначением), аложное

значение ("false") ввидезначения 0. Этоможетпривестикошибкам. Например,

легко напечатать "=" вместо "==". Поэтомуфрагмент

...

if ( number_of_people = 1 )

cout << "Есть только один человек.\n";

...

всегда будетпечататьсообщение "Естьтолькоодинчеловек", дажееслидооператора

if переменная "number_of_people" былабольше 1.

6. Сводка результатов

В даннойлекциидовольноподробнорассматривалисьпеременныеязыкаСи++.

У переменныхвсегдаестьопределенныйтипданных. Переменныеприменяютсядля

временного илипостоянногохранениязначенийразныхтипов. Значенияпеременным

можно присваиватьразличнымиспособами. Ввыраженияхдлявычисленияновых

значений переменныхможно использоватьразличныеарифметическиеилогические

операции.

7. Упражнения

Упражнение 1

Для преобразованиятемпературыизшкалыЦельсиявабсолютнуюшкалутем-

ператур (шкалуКельвина) надо добавить ктемпературепоЦельсиюзначение 273.15.

В шкалуФаренгейтатемпературапоЦельсиюпреобразуетсяt
= 1.8t
o + 32 f
.

Напишите программупреобразованиязначенийтемпературы, котораябудет

печатать наэкранеследующуютаблицу:

Цельсий Фаренгейт Абсолютная температура

0 32.00 273.15

20 68.00 293.15

40 104.00 313.15

... ... ...

300 572.00 573.15

Упражнение 2

Измените программуизупражнения 1 так, чтобыоназапрашивалаупользова-

теля минимальную имаксимальнуютемпературупоЦельсию, которыедолжныбыть

в первойипоследнейстрокахтаблицы. Программатакжедолжназапроситьшагиз-

менения температуры (наэтозначениедолжныотличатьсятемпературывсоседних

строках таблицы, вупражнении 1 шагбылравен 20-тиградусам).

Перед таблицейпрограммадолжнавывестинесколькострокспояснениемсво-

их действий, атакжеповторитьвыводнаэкранвведенныхпользователемданных.

Упражнение 3

Напишите программу, котораясчитываетсклавиатурысимвол (ch) изатемвы-

водит одноизследующихсообщений (вместо ch долженвыводитьсявведенныйсим-

вол, авместо ... –соответствующаяпрописнаяилистрочнаябуква):

а) еслисимвол ch является 2ьстрочнойбуквой–сообщение "Букве ch соответст-

вует прописнаябуква ...",

б) если ch являетсяпрописнойбуквой–сообщение "Букве ch соответствует

строчная буква ...",

в) если ch неявляетсябуквой–сообщение "Символ ch неявляетсябуквой".

Для составлениянеобходимыхусловийобратитеськрасширеннойтаблице

символов ASCII (см. п.8.3).

Упражнение 4

Напишите программудлявозведенияпроизвольногочислаx в положительную

степень n с помощьюциклаfor. (Естьлиспособыповышенияэффективностивашей

программы?)

8. Приложения

8.1 Служебные слова Си++

По назначениюслужебныесловаязыкаСи++ можноразделитьнанесколько

групп. Нижеперечисленыэтигруппыиотносящиесякнимслова. Полужирным

шрифтом выделеныслова, назначениекоторыхвыузнаетевданномвводномкурсе.

•Типы данных (определяюттипыданных, которыеможнохранитьвпамяти

компьютера).

char short int long
(целые числа)

enum
(тип "перечисление")

double float
(вещественные числа)

void

struct
union typedef
(типы, определяемые

пользователем)

•Модификаторы типовданных (позволяютзадатьнекоторыесвойствахране-

ния данныхвпамяти).

signed unsigned

volatile register

const static extern
auto

•Управление порядкомвыполненияоператоров.

if else
(ветвление с двумя вариантами)

switch case default
(множественное ветвление)

for while do
(циклы)

break continue

return
(возврат из функции)

goto (безусловный переход)

•Динамическое распределениепамяти.

new delete

•Объектно-ориентированноепрограммирование (этисловабудутподробно

рассматриваться вотдельномкурсеобъектно-ориентированногопрограм-

мирования ипроектирования).

class private protected public

virtual this friend template

operator

•Обработка исключений (особыймеханизмобработкиошибоквобъектно-

ориентированных программах).

try throw catch

•Разное.

sizeof
inline asm

8.2 Таблица символов ASCII

8.3 Расширенная таблица символов ASCII для кодовой страницы DOS-866

ЛЕКЦИЯ 3. Функции и процедурная абстракция

1. Назначение подпрограмм

Естественный иинтуитивнопонятныйподходкрешениюбольшихсложных

задач состоитвтом, чтобыразбитьбольшуюзадачунанаборменьших, которыемож-

но решитьболееилименеенезависимоизатемскомбинироватьполученныерешения

для полученияполногорешения. Натакомподходеоснованаметодологияструктур-

ного программирования, котороегосподствоваловразработкепрограммногообеспе-

чения допоявления объектно-ориентированногоподхода.

При структурномпрограммированиибольшаяпрограммаразделяетсянанабор

более илименеенезависимыхподпрограмм
. ВСи++ подпрограммыназываются

функциями
(вПаскалеинекоторыхдругих языкахпрограммированияестьдватипа

подпрограмм – "процедуры" и "функции").

Подпрограммы уженеоднократновстречалисьвпредыдущихлекциях. Напри-

мер, впрограмме 2.3.2 дляпостроениятаблицыквадратныхкорнейбылприменен

следующий циклfor:

...

#include<math.h>

...

for ( number=1 ; number<=10 ; number=number+1 )

{

cout.width(20);

cout << number << sqrt(number) << "\n";

}

...

Функция "sqrt(...)" –этоподпрограмма, описаниекоторойхранитсявзаголо-

вочном файле "math.h", ареализация–вбиблиотечномфайле "math.lib". Привызове

функции "sqrt(...)" ейпередаетсячисловойпараметр "number", функцияприменяет

алгоритм вычисленияквадратногокорняизэтогочисла, изатемвозвращаетвычис-

ленное значениеобратновместовызова. Дляпримененияэтойфункциипрограмми-

сту совсемнеобязательнознать, какойименноалгоритмреализованвнутринее. Глав-

ное, чтобыфункциягарантированновозвращалаверныйрезультат. Былобыдовольно

нелепо включатьвявномвидеалгоритмизвлеченияквадратногокорня (и, возможно,

делать этонеоднократно) вглавнуюфункциюпрограммы "main".

В даннойлекцииописывается, какпрограммистможетопределятьсвоисобст-

венные функции. Сначалапредполагается, чтоэтифункцииразмещаютсяводном

файле сфункцией "main". Вконцелекциипоказывается, какраспределятьфункции

программы понесколькимфайлам.

2. Определение новых функций

Простым примеромопределенияииспользованияновойфункцииявляется

программа 2.1 (внейпользовательскаяфункцияназывается "area(...)"). Этапро-

грамма вычисляетплощадьпрямоугольниказаданнойдлиныиширины.

#include<iostream.h>

int area(int length, int width); /* Описание функции */

// ГЛАВНАЯ ФУНКЦИЯ:

int main()

{

int this_length, this_width;

cout << "Введите длину: "; /* <--- строка 10 */

cin >> this_length;

cout << "Введите ширину: ";

cin >> this_width;

cout << "\n"; /* <--- строка 14 */

cout << "Площадь прямоугольника с размерами ";

cout << this_length << "x" << this_width;

cout << " равна " << area(this_length, this_width) << "\n";

return 0;

}

// КОНЕЦ ГЛАВНОЙ ФУНКЦИИ

// ФУНКЦИЯ ВЫЧИСЛЕНИЯ ПЛОЩАДИ:

int area(int length, int width) /* Начало определения функции */

{

int number;

number = length * width;

return number;

} /* Конец определения функции */

// КОНЕЦ ФУНКЦИИ

Программа 2.1.

Программа 2.1, конечно, допускаетзаписьвболеесжатойформе, новданном

виде онаслужитхорошейиллюстрациейнекоторыхсвойствфункцийСи++:

•Структура определения (реализации) функцииподобнаструктурефункции

"main()" –втелефункцииестьописаниялокальныхпеременныхииспол-

няемые операторы.

•У функциимогутбытьпараметры, которыеуказываютсявспискевнутри

круглых скобокпослеименифункции. Укаждогопараметразадаетсятип.

•Если вызовфункциивстречаетсяранееееопределения, товначалепро-

граммы должносодержатьсяописаниефункции (прототип). Прототип

функции описываетеепараметрыитипвозвращаемогозначения. Обычно

прототипы функцийразмещаютсяпослеописанияглобальныхконстант.

Внутри функцииможетбытьнесколькооператороввозврата "return". Функ-

ция завершаетсяпослевыполнениялюбогооператора "return". Например:

double absolute_value(double number)

{

if (number >= 0)

return number;

else

return -number;

}

3. Способы передачи параметров внутрь функций

Во всехрассмотренныхдосихпорпримерахпараметры функцийпередавались

по значению
. Привызовеизфункции "main()" вызываемойфункциипередаютсяко-

пии
указанных переменных. Например, впрограмме 2.1 функции "area(...)" переда-

ются текущиезначенияпеременных "this_length" и "this_width". Затемфункция

"area(...)" сохраняетпереданныезначениявсобственныхлокальныхпеременных, и

именно этипеременныеучаствуютвпоследующихвычисленияхвнутрифункции.

3.1 Передача параметров по значению

Функции, принимающиепараметрыпо значению
, "безопасны" втомсмысле,

что онинемогутслучайноизменитьпеременныевызывающейфункции (т.е. уфунк-

ций нетскрытыхпобочных эффектов
). Большинствофункцийпроектируютсяименно

таким образом.

Программа 3.1 поясняет, почемуважногарантировать "сохранность" перемен-

ных вызывающейфункции. Этапрограммадолжнавыводитьнаэкранфакториали

корень изчисла, введенногопользователем:

Введите положительное число:

Факториал 4! равен 24, а квадратный корень из 4 равен 2.

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

"sqrt(...)". Библиотечнойфункциидлявычисленияфакториаланет, поэтомупри-

дется написатьсобственнуюфункцию (вычисляющуюдлялюбогоположительного

целого числаn значение n!=(1*2*3*...*n)).

#include<iostream.h>

#include<math.h>

int factorial(int number);

// ГЛАВНАЯ ФУНКЦИЯ:

int main()

{

int whole_number;

cout << "Введите положительное число:\n";

cin >> whole_number;

cout << "Факториал " << whole_number << "! равен ";

cout << factorial(whole_number);

cout << ", а квадратный корень из " << whole_number;

cout << " равен " << sqrt(whole_number) << ".\n";

return 0;

}

// КОНЕЦ ГЛАВНОЙ ФУНКЦИИ

// ФУНКЦИЯ ДЛЯ ВЫЧИСЛЕНИЯ ФАКТОРИАЛА:

int factorial(int number)

{

int product = 1;

for ( ; number > 0 ; number--)

product *= number;

return product;

}

// КОНЕЦ ФУНКЦИИ

Программа 3.1.

Если быфункция "factorial(...)" изменялапеременнуювызывающей

функции, топрограмма 3.1 выдавалабыследующийответ (формальноправильный,

но посмыслузадачинекорректный):

Введите положительное число:

Факториал 4! равен 24, а квадратный корень из 0 равен 0.

3.2 Передача параметров по ссылке

Все-такииногдабываетнеобходимо, чтобыфункцияизменилазначениепере-

данного ейпараметра. Рассмотримпрограмму 2.1. С 10-йпо 14-юстрокувнейвы-

полняется запросразмеров прямоугольника, азатемвычисляетсяегоплощадь.

При структурномпрограммированиинезависимыепосмыслучастипрограммы

принято оформлятьввидеотдельныхфункций. Дляполученияданныхотпользова-

теля создадимфункцию "get_dimensions". Вданномслучаенеобходимо, чтобыэта

функция изменялазначенияпеременных "this_length" и "this_width" (переданныхей

в качествепараметров) –помещалавнихзначения, введенныепользователемскла-

виатуры. Изменениепараметровфункциивозможноприпередачепараметровпо

ссылке
. Утакихпараметроввзаголовкефункциипослеименитипауказываетсясим-

вол "&".

#include<iostream.h>

int area( int length, int width );

void get_dimensions( int& length, int& width );

// ГЛАВНАЯ ФУНКЦИЯ:

int main()

{

int this_length, this_width;

get_dimensions( this_length, this_width );

cout << "Площадь прямоугольника с размерами ";

cout << this_length << "x" << this_width;

cout << " равна " << area( this_length, this_width ) << "\n";

return 0;

}

// КОНЕЦ ГЛАВНОЙ ФУНКЦИИ

// ФУНКЦИЯ ВВОДА РАЗМЕРОВ ПРЯМОУГОЛЬНИКА:

void get_dimensions( int& length, int& width )

{

cout << "Введите длину: ";

cin >> length;

cout << "Введите ширину: ";

cin >> width;

cout << "\n";

}

// КОНЕЦ ФУНКЦИИ

// ФУНКЦИЯ ВЫЧИСЛЕНИЯ ПЛОЩАДИ:

int area( int length, int width )

{

return length*width;

}

// КОНЕЦ ФУНКЦИИ

Программа 3.2.

Функция _______"get_dimensions" изменяетзначенияпараметров "this_length" и

"this_width", ноневозвращаетникакогозначения (т.е. неявляется "функцией" вма-

тематическом смысле). Этотфактотражаетсяивпрототипе, ивопределениифунк-

ции –вкачествевозвращаемогозначенияуказантип "void" ("пустой" тип).

4. Полиморфизм и перегрузка функций

Одним изхарактерныхсвойствобъектно-ориентированногоязыка, втомчисле

и Си++, являетсяполиморфизм
–использованиеодногоименидлявыполненияраз-

личных действийнадразличнымиобъектами. Применительнокфункциямэтоназы-

вается перегрузкой
. ДляосновныхоперацийСи++ перегрузкаужевстроенавязык:

например, усложениясуществуеттолькоодноимя, "+", ноегоможноприменятьдля

сложения какцелых, такивещественныхзначений. Этаидеярасширяетсянаобра-

ботку операций, определенныхпользователем, т.е., функций.

Перегруженные функцииимеютодинаковыеимена, норазныеспискипарамет-

ров ивозвращаемыезначения (см. программу 4.1).

#include<iostream.h>

int average( int first_number, int second_number,

int third_number );

int average( int first_number, int second_number );

// ГЛАВНАЯ ФУНКЦИЯ:

int main()

{

int number_A = 5, number_B = 3, number_C = 10;

cout << "Целочисленное среднее чисел " << number_A << " и ";

cout << number_B << " равно ";

cout << average(number_A, number_B) << ".\n\n";

cout << "Целочисленное среднее чисел " << number_A << ", ";

cout << number_B << " и " << number_C << " равно ";

cout << average(number_A, number_B, number_C) << ".\n";

return 0;

}

// КОНЕЦ ГЛАВНОЙ ФУНКЦИИ

// ФУНКЦИЯ ДЛЯ ВЫЧИСЛЕНИЯ ЦЕЛОЧИСЛЕННОГО СРЕДНЕГО

// ЗНАЧЕНИЯ 3-Х ЦЕЛЫХ ЧИСЕЛ:

int average( int first_number, int second_number,

int third_number )

{

return ((first_number + second_number + third_number)/3);

}

// КОНЕЦ ФУНКЦИИ

// ФУНКЦИЯ ДЛЯ ВЫЧИСЛЕНИЯ ЦЕЛОЧИСЛЕННОГО СРЕДНЕГО

// ЗНАЧЕНИЯ 2-Х ЦЕЛЫХ ЧИСЕЛ:

int average( int first_number, int second_number )

{

return ((first_number + second_number)/2);

}

// КОНЕЦ ФУНКЦИИ

Программа 4.1.

Программа 4.1. выводитнаэкрансообщения:

Целочисленное среднее чисел 5 и 3 равно 4.

Целочисленное среднее чисел 5, 3 и 10 равно 6.

5. Процедурная абстракция и "хороший" стиль программирования

Функции помогаютприменятьдляразработкипрограммструктурныйметод

проектирования "сверху вниз
". Приэтомрешаемаязадачаделитсянаподзадачи (иза-

тем напод-подзадачиит.д.). Длярешениякаждойподзадачипрограммистреализует

отдельную функцию, приэтомемуненужнознатьдеталиреализацииостальных

функций.

Чтобы функциеймогвоспользоватьсядругойпрограммист, онадолжнаиметь

осмысленное имяикомментарийсописаниемназначенияфункции, еепараметров и

возможных возвращаемыхзначений.

Опытные программистынаначальныхэтапахразработкичастоприменяют

пустые функции (заглушки
), которыесодержаттолькооператорвозвратазначениясо-

ответствующего типа. Этифункцийоблегчаютотладкуглавнойфункцииилипросто

функции болеевысокогоуровня.

Выделение врешаемойзадачефункций методом "сверхувниз" частоназывает-

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

друг отдругафункцийширокоприменяетсяпередачапараметровпозначениюило-

кальные переменные внутрифункций. Послереализациипрограммистможетрас-

сматривать подобныефункциикак "черныеящики". Дляихиспользованиязнатьде-

тали реализациинеобязательно.

6. Модульное программирование

Помимо метода "сверхувниз", вторымважнымметодомструктурногопроек-

тирования являетсяметодмодульногопрограммирования. Онпредполагаетразделе-

ние текстапрограммынанесколькофайлов, вкаждомизкоторыхсосредоточеныне-

зависимые частипрограммы (сгруппированныепосмыслуфункции).

В программахнаСи++ частоприменяютсябиблиотечныефункции (например,

"sqrt(...)"). Дляиспользованиябольшинства функций, втомчислеибиблиотечных,

необходимы двафайла (вскобкахпримерыданыдля "sqrt(...)"):

•Заголовочный файл
("math.h") спрототипомфункции ("sqrt(...)" имногих

других математическихфункций). Поэтомувпрограммах, вызывающих

"sqrt(...)", естьстрока "#include <math.h>", анеявноеобъявлениеэтой

функции.

•Файл реализации
(дляпользовательскихфункцийэтофайлысисходным

текстом наСи++, абиблиотечныефункцииобычнохранятсявскомпилиро-

ванном видевспециальныхбиблиотечных файлах, например,

"libcmtd.lib"). Файлыреализациипользовательскихфункций (обычнос

расширением ".cpp") содержатопределенияэтихфункций.

Разделение исходноготекстаназаголовочныефайлыифайлыреализациипо-

казано впрограмме 6.1, котораявыполняеттежедействия, чтоипрограмма 4.1. Те-

перь программасостоитизтрехфайлов: главногофайла, заголовочногофайласопи-

саниями двухфункцийрасчетасреднегозначения, исоответствующегофайлареали-

зации.

В главномфайлесодержитсяследующийтекст:

#include <iostream.h>

#include "averages.h"

int main()

{

int number_A = 5, number_B = 3, number_C = 10;

cout << "Целочисленное среднее чисел " << number_A << " и ";

cout << number_B << " равно ";

cout << average(number_A, number_B) << ".\n\n";

cout << "Целочисленное среднее чисел " << number_A << ", ";

cout << number_B << " и " << number_C << " равно ";

cout << average(number_A, number_B, number_C) << ".\n";

return 0;

}

Главный файл программы 6.1.

Обратите внимание, чтоимяфайластандартнойбиблиотеки "iostream.h" вди-

рективе препроцессора "include" заключеновугловыескобки ("<>"). Файлысимена-

ми вугловыхскобкахпрепроцессорищетвбиблиотечныхкаталогах, указанныхвна-

стройках компилятора. Именапользовательскихзаголовочныхфайловобычноза-

ключаются вдвойныекавычки, ипрепроцессорищетихвтекущемкаталогепро-

граммы.

Далее приведеносодержимоефайла "averages.h". Внем естьидентификатор

препроцессора "AVERAGES_H" ислужебныесловапрепроцессора "ifndef" ("еслинеоп-

ределено"), "define" ("определить") и "endif" ("конецдирективыif"). Идентифика-

тор "AVERAGES_H" являетсяглобальным символическимименемзаголовочногофайла.

Первые двестрокифайласлужатзащитойотповторнойобработкитекстазаголовоч-

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

"#include "averages.h"" встречаетсянесколькораз.

В заголовочныхфайлах, кромепрототиповфункций, часторазмещаютсяопи-

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

курсе объектно-ориентированногопрограммирования.

#ifndef AVERAGES_H

# define AVERAGES_H

// (Определения констант и пользовательских типов)

// ПРОТОТИП ФУНКЦИИ ДЛЯ ВЫЧИСЛЕНИЯ ЦЕЛОЧИСЛЕННОГО СРЕДНЕГО

// ЗНАЧЕНИЯ 3-Х ЦЕЛЫХ ЧИСЕЛ:

int average( int first_number, int second_number,

int third_number );

// ПРОТОТИП ФУНКЦИИ ДЛЯ ВЫЧИСЛЕНИЯ ЦЕЛОЧИСЛЕННОГО СРЕДНЕГО

// ЗНАЧЕНИЯ 2-Х ЦЕЛЫХ ЧИСЕЛ:

int average( int first_number, int second_number );

#endif

Заголовочный файл averages.h.

Ниже показаносодержимоефайла "averages.cpp" сисходнымтекстомполь-

зовательских функций:

#include <iostream.h>

#include "averages.h"

// ФУНКЦИЯ ДЛЯ ВЫЧИСЛЕНИЯ ЦЕЛОЧИСЛЕННОГО СРЕДНЕГО

// ЗНАЧЕНИЯ 3-Х ЦЕЛЫХ ЧИСЕЛ:

int average( int first_number, int second_number,

int third_number )

{

return ((first_number + second_number + third_number)/3);

}

// ФУНКЦИЯ ДЛЯ ВЫЧИСЛЕНИЯ ЦЕЛОЧИСЛЕННОГО СРЕДНЕГО

// ЗНАЧЕНИЯ 2-Х ЦЕЛЫХ ЧИСЕЛ:

int average( int first_number, int second_number )

{

return ((first_number + second_number)/2);

}

Файл реализации averages.cpp.

Программа
6.1
демонстрирует основное достоинство модульного подхода
:
при

изменении деталей реализации в файле
"
averages.cpp
"
не обязательно вносить из
-

менения в файл
"
averages.h
"
или в главный файл программы
.

7. Сводка результатов

В данной лекции описано
,
как в Си
++
можно создавать новые функции
.
Есть

два способа передачи параметров внутрь функции
:
по значению и по ссылке
.
Функ
-

ции облегчают применение процедурной абстракции при разработке программ мето
-

дом
"
сверху вниз
".
При модульном подходе описание и реализация функций разме
-

щаются в отдельных файлах
,
в таком случае для вызова функции необходимо вклю
-

чать в текст программы заголовочный файл
.

8. Упражнения

Упражнение 1

В программе из упражнения
2
лекции
2 (
файл
ex2_2.cpp)
выделите
6
функций
,

имена и назначение которых перечислены ниже
:

fahrenheit_of

Возвращает значение температуры по шкале Фаренгейта для передан-

ного значения по шкале Цельсия.

absolute_value_of

Возвращает значение температуры в абсолютной шкале для передан-

ного значения по шкале Цельсия.

print_preliminary_message

Печать сообщения
,
поясняющего назначение программы
.

input_table_specifications

Запрос параметров таблицы с клавиатуры
.

print_message_echoing_input

Повторное отображение параметров
,
введенных пользователем
.

print_table

Печать таблицы температур
.

Проверьте свою программу для различных исходных данных
.
В качестве кон
-

трольного примера можете использовать следующие выходные данные
:

Эта программа печатает значения температур в разных шкалах.

Введите минимальное (целое) значение температуры

по Цельсию, которое будет в первой строке таблицы:
0

Введите максимальное значение температуры:
100

Введите разницу температур между соседними строками таблицы:
20

Преобразование значений температуры от 0 градусов Цельсия

до 100 градусов Цельсия, с шагом 20 градусов:

Цельсий Фаренгейт Абсолютная температура

0 32.00 273.15

20 68.00 293.15

40 104.00 313.15

... ... ...

100 212.00 485.15

Упражнение 2

Разделите программу из упражнения
1
на три файла
:

1)
главный файл программы
;

2)
заголовочный файл
"
conversions.h
"
с прототипами функций

"
fahrenheit_of(...)
"
и
"
absolute_value_of(...)
";

3)
файл реализации с определением этих двух функций
.

Снова проверьте свою программу для различных исходных данных
.

Упражнение 3

(
а
)
Создайте заголовочный файл
"
statistics.h
"
и соответствующий файл реализа
-

ции
"
statistics.cpp
"
с функциями
"
average(...)
"
и
"
standard_deviation(...)
".

Эти функции должны вычислять среднее значение и среднеквадратическое откло
-

нение для последовательности из
1, 2, 3
или
4
вещественных чисел
.
Среднеквадра
-

тическое отклонение чисел
r

1
, ...,
r

N
определяется как корень из среднего значения

квадратов отклонений чисел от своего среднего
:

Σ
=

= −

i

r m

N

1

2
) ( 1
σ
,
где
Σ
=

i

r

Подсказки:

(1) Примените средства перегрузки функций Си++. (2) Функции

можно вызывать изнутри друг друга. (3) Максимально используйте возможности

текстового редактора по копированию фрагментов исходного текста.

(
б
)
Напишите тестовую программу для проверки функций из файла
"
statistics.h
",

которая в цикле запрашивает исходные данные до тех пор
,
пока пользователь не

сообщит о завершении работы
(
некоторым специально оговоренным числом
).
Ва
-

ша тестовая программа должна выдавать на экран сообщения
,
подобные приве
-

денным ниже
:

Эта программа предназначена для тестирования функций из

заголовочного файла "statistics.h".

Сколько чисел будет в тестовой последовательности – 1, 2, 3

или 4? (для завершения работы введите 0):
3

Введите первое число:
5

Введите второе число:
7

Введите третье число:
9

Среднее значение: 7. Среднеквадратическое отклонение: 1.63299.

Сколько чисел будет в тестовой последовательности – 1, 2, 3

или 4? (для завершения работы введите 0):
1

Введите первое число:
5.8

Среднее значение: 5.8. Среднеквадратическое отклонение: 0.

Сколько чисел будет в тестовой последовательности – 1, 2, 3

или 4? (для завершения работы введите 0):
8

Извините, но эта программа может работать только с 1, 2, 3

или 4-мя числами.

Сколько чисел будет в тестовой последовательности – 1, 2, 3

или 4? (для завершения работы введите 0):
0

Программа тестирования функций из заголовочного файла

"statistics.h" завершила работу.

Подсказки:

(1) Разрабатывайте свою программу методом "сверху вниз ". Начни-

те с написания короткой главной функции, в которой вызываются функции-

заглушки, например, "

test_three_values()
". Детали этих функций вы уточни-

те позже, после отладки функции "

main()
". (2) В качестве высокоуровневой

структуры программы вы можете использовать цикл

for
с пустым разделом

инициализации и пустым оператором изменения значений (эквивалент цикла

while
, который будет рассматриваться в следующих лекциях).

ЛЕКЦИЯ 4. Текстовые файлы и потоки ввода/вывода

1. Назначение файлов

Во всех рассматривавшихся до сих пор программах ввод данных производился

только с клавиатуры
,
а вывод
–
только на экран
.
Если в качестве устройств вво
-

да
/
вывода ограничиться только клавиатурой и экраном
,
то в таком случае будет

сложно обработать большие объемы входных данных
.
Выходные данные
,
отображен
-

ные на экране
,
после выключения компьютера безвозвратно теряются
.

Для устранения подобных проблем удобно сохранять данные на запоминаю
-

щих устройствах
,
предназначенных для долговременного хранения данных
(
обычно

это магнитные диски
).
Данные
,
сгенерированные с помощью одной программы
,
мож
-

но сохранить на диске и в дальнейшем
,
при необходимости
,
извлечь и обработать в

другой программе
.

На дисках данные хранятся в виде структур данных
,
обслуживаемых операци
-

онной системой
,
–
в виде
файлов

.
Файл проще всего представить как линейную по
-

следовательность символов
.
Текст этой лекции
(
если не учитывать специальные сим
-

волы форматирования
)
можно сохранить в файле с именем
"Lecture_4.txt"
в виде

(
рис
. 1):

Рис. 1. Начало файла
"
lecture_4.txt
".

2. Потоки ввода/вывода

Перед началом изучения файловых операций в Си
++,
необходимо ознакомить
-

ся с понятием
потока ввода/вывода

.
Поток напоминает
"
канал
"
или
"
трубу
",
через ко
-

торую данные поступают от передатчика к приемнику
.
Исключительно важная осо
-

бенность потоковой обработки данных состоит в том
,
что элементы данных можно

посылать или считывать из потока только по одному за раз
,
т
.
е
.
последовательно

.

В данном курсе рассматриваются только однонаправленные потоки
,
в которых

данные всегда передаются в одном направлении
.
Из программы данные можно отпра
-

вить
(
записать
)
в
поток вывода

,
а получить
(
прочитать
)
их в программе из
потока

ввода

.
Например
,
сразу после запуска программы
,
поток стандартного ввода
"cin"

подключается к клавиатуре
,
а поток стандартного вывода
"cout"
–
к экрану
.

Потоки ввода
/
вывода
,
вроде
"cin"
и
"cout",
являются примерами
объектов

класса
"
поток
".
Поэтому изучение потоков полезно и по той причине
,
что позволяет

ознакомиться с элементами синтаксиса и некоторыми объектно
-
ориентированными

понятиями Си
++.

Список функций для работы с файловыми потоками хранится в заголовочном

файле
"fstream.h".
Поэтому во всех рассматриваемых ниже фрагментах программ

предполагается
,
что в начале программы есть соответствующая директива
"#include":

#include<fstream.h>

2.1 Создание потоков

В программе перед первым обращением к потоку ввода или вывода необходи
-

мо
"
создать
"
поток
.
Операторы для создания потоков похожи на описания перемен
-

ных
,
и они обычно размещаются в начале программы или функции рядом с описа
-

ниями переменных
.
Например
,
операторы

ifstream in_stream;

ofstream out_stream;

создают поток с именем
"in_stream",
являющийся объектом
класса

(
как типа данных
)

"ifstream" (input-file-stream,
файловый поток ввода
),
и поток с именем
"out_stream",

являющийся объектом класса
"ofstream" (output-file-stream,
файловый поток вывода
).

Аналогию между потоками и обычными переменными
(
типа
"int", "char"
и т
.
д
.)
не

следует понимать слишком буквально
.
Например
,
к потокам нельзя применять опера
-

тор присваивания
(
например
,
нельзя записать
"in_stream1 = in_stream2").

2.2 Подключение и отключение потоков от файлов

После создания потока его можно подключить к файлу
(
открыть файл
)
с помо
-

щью
функции-члена

"open(...)". (
В предыдущих лекциях уже использовались несколь
-

ко функций
-
членов потоков вывода
.
Например
,
во
2-
й лекции применялись

"precision(...)"
и
"width(...)".)
Функция
"open(...)"
у потоков
ifstream
и
ofstream
работает

по
-
разному
(
т
.
е
.
это полиморфная функция
).

Для подключения потока
ifstream
с именем
"in_stream"
к файлу с именем

"Lecture_4.txt"
надо применить следующий вызов
:

in_stream.open("Lecture_4.txt");

Этот оператор подключит поток
"in_stream"
к началу файла
"Lecture_4.txt"

(
графически состояние программы после выполнения оператора показано на рис
. 2).

Рис. 2. Состояние программы после подключения потока ввода к файлу
.

Чтобы к файлу
"Lecture_4.txt"
подключить поток вывода
ofstream
с именем

"out_stream",
надо выполнить аналогичный оператор
:

out_stream.open("Lecture_4.txt");

Этот оператор подключит поток
"out_stream"
к файлу
"Lecture_4.txt",
но при

этом прежнее содержимое файла будет удалено
.
Файл будет подготовлен к приему

новых данных
(
рис
. 3).

Рис. 3. Состояние программы после подключения потока вывода к файлу
.

Для отключения потока
"in_stream"
от файла
,
к которому он подключен
(
для

закрытия файла
),
надо вызвать функцию
-
член
"close()":

in_stream.close();

После этого состояние программы по отношению к файлу будет таким
,
как на

рис
. 4.

Рис. 4. Состояние программы после отключения потока ввода от файла
.

Функция
-
член отключения от файла у потока вывода
:

out_stream.close();

выполняет аналогичные действия
,
но
,
дополнительно
,
в конец файла добавляется

служебный символ
"end-of-file (
маркер конца файла
)".
Т
.
о
.,
даже если в поток вывода

не записывались никакие данных
,
то после отключения потока
"out_stream"
в файле

"Lecture_4.txt"
будет один служебный символ
(
рис
. 5).
В таком случае файл

"Lecture_4.txt"
останется на диске
,
но он будет
пустым

.

Рис. 5. Состояние программы после отключения потока вывода от файла
,
в

который не было записано ни одного символа
..

3. Проверка ошибок выполнения файловых операций

Файловые операции
,
например
,
открытие и закрытие файлов
,
известны как

один из наиболее вероятных источников ошибок
.
В надежных коммерческих про
-

граммах всегда выполняется проверка
,
успешно или нет завершилась файловая опе
-

рация
.
В случае ошибки вызывается специальная функция
-
обработчик ошибки
.

Простейший способ проверки ошибок файловых операций заключается в вызо
-

ве функции
-
члена
"fail()".
Вызов

in_stream.fail();

возвращает истинное значение
(True),
если последняя операция потока
"in_stream"

привела к ошибке
(
может быть
,
была попытка открытия несуществующего файла
).

После ошибки поток
"in_stream"
может быть поврежден
,
поэтому лучше не продол
-

жать работу с ним
.

В приведенном ниже фрагменте программы в случае ошибки при открытии

файла на экран выдается сообщение и программа завершает работу с помощью биб
-

лиотечной функции
"exit()" (
она описана в файле
"stdlib.h"):

#include <iostream.h>

#include <fstream.h>

#include <stdlib.h>

int main()

{

ifstream in_stream;

in_stream.open( "Lecture_4.txt" );

if ( in_stream.fail() )

{

cout << "Извините, открыть файл не удалось!\n";

exit(1);

}

...

4. Символьный ввод/вывод

4.1 Функция ввода "
get(...)
"

После того
,
как файл для ввода данных открыт
,
из него можно считывать от
-

дельные символы
.
Для этого служит функция
"get(...)".
У нее есть параметр типа

"char&".
Если программа находится в состоянии
,
как на рис
. 2,
то после вызова
:

in_stream.get(ch);

произойдет следующее
: (
а
)
переменной
"ch"
будет присвоено значение
"'
Л
'",
и
(
б
)
по
-

ток
"in_stream"
будет подготовлен для чтения следующего символа
(
рис
. 6).

Рис. 6. Состояние программы после чтения из файла первого символа
.

4.2 Функция вывода "
put(...)
"

С помощью потока вывода класса
ofstream
в открытый файл можно
записы-

вать

отдельные символы
.
Для этого у класса
ofstream
есть функция
-
член
"put(...)".

Записываемый символ передается ей как параметр типа
"char".
Если программа пре
-

бывает в состоянии
,
представленном на рис
. 3,
то оператор

out_stream.put('Л');

изменит состояние на то
,
которое показано на рис
. 7:

Рис. 7. Состояние программы после записи в файл первого символа
.

4.3 Функция "
putback(...)
"

В Си
++
у потока
ifstream
есть функция
-
член
"
putback(...)
".
На самом деле

она не
"
возвращает символ назад
" (
т
.
е
.
не изменяет содержимого файла ввода
),
но ве
-

дет себя так
,
как будто это делает
.
На рис
. 8
показано состояние
,
в которое перейдет

программа из состояния рис
. 6
после выполнения оператора
:

in_stream.putback(ch);

Рис. 8. Состояние программы после вызова функции
"
putback('Л')
".

"
Вернуть назад
"
можно любой символ
.
Состояние программы после вызова

in_stream.putback('7');

показано на рис
. 9.

Рис. 9. Состояние программы после вызова функции
"
putback('7')
".

5. Проверка достижения конца файла при операциях ввода

5.1 Проверка конца файла с помощью функции "
eof()
"

При работе с потоком ввода надо следить за тем
,
чтобы не пропустить момент

достижения конца файла
.
В большинстве реализаций Си
++ (
в том числе и в Microsoft

Visual C++
)
в класс
"
поток ввода
"
встроен
флаг

"
конец файла
(end-of-file, EOF)"
и

функция
-
член
"
eof()
"
для чтения этого флага
.
С помощью функции
"
eof()
"
можно

узнать
,
находится ли в данный момент флаг в состоянии
True
(
конец файла достиг
-

нут
)
или
False
(
конца файла пока нет
).

При открытии файла
,
когда поток
ifstream
только подключается к нему
,
флаг

EOF
сбрасывается в значение
False
(
даже если файл пуст
).
Но
,
если
ifstream

"
in_stream
"
сейчас расположен в конце файла
,
и флаг
EOF
равен
False
,
то после вы
-

зова

in_stream.get(ch);

переменная
"
ch
"
окажется в неопределенном состоянии
,
а флагу
EOF
будет присвоено

значение
True
.
Если флаг
EOF
равен
True
,
то программа не должна пытаться выпол
-

нить чтение из файла
,
поскольку результат чтения будет неопределенным
.

Допустим
,
программа находится с состоянии
,
показанном на рис
. 10.

Рис. 10. Состояние программы после чтения предпоследнего символа из файла
.

Тогда после выполнения оператора

in_stream.get(ch);

программа перейдет в состояние
,
изображенное на рис
. 11.

Рис. 11. Состояние программы после чтения последнего символа из файла
.

Теперь логическое выражение

in_stream.eof()

будет иметь истинное значение
True
.
Если снова выполнить чтение символа
:

in_stream.get(ch);

то в результате получится состояние
,
показанное на рис
. 12.

Рис. 12. Состояние программы после операции чтения символа при установ
-

ленном флаге
EOF.

Ниже приведена простая программа для копирования текстового файла

"
Lecture_4
.txt
"
одновременно и на экран
,
и в другой файл
"
Copy_of_4.txt
".
Для

прекращения копирования применяется вызов функции
"
eof()
".
Обратите внимание

на цикл
"
while
".
Цикл с префиксным условием
(
предусловием
) "
while
"
является уп
-

рощенным вариантом цикла
"
for
".
У цикла
"
while
"
в круглых скобках
"
()
"
нет опе
-

раторов инициализации и изменения значений
(
подробно эти циклы рассматриваются

в следующей лекции
).

#include <iostream.h>

#include <fstream.h>

int main()

{

char character;

ifstream in_stream;

ofstream out_stream;

in_stream.open( "Lecture_4.txt" );

out_stream.open( "Copy_of_4.txt" );

in_stream.get( character );

while ( !in_stream.eof() )

{

cout << character;

out_stream.put(character);

in_stream.get(character);

}

out_stream.close();

in_stream.close();

return 0;

}

Программа 5.1.

6. Передача потоков функциям в качестве параметров

Потоки можно использовать в качестве параметров функций
,
но их
обязатель-

но

надо передавать
по ссылке

(
а не по значению
).
Ниже приведен усовершенствован
-

ный вариант программы
5.1,
в котором копирование выполняется специальной функ
-

цией
"
copy_to(...)
".

#include <iostream.h>

#include <fstream.h>

void copy_to( ifstream& in, ofstream& out );

// Главная функция

int main()

{

ifstream in_stream;

ofstream out_stream;

in_stream.open( "Lecture_4.txt" );

out_stream.open( "Copy_of_4.txt" );

copy_to( in_stream, out_stream );

out_stream.close();

in_stream.close();

return 0;

}

// Конец главной функции

// Функция для копирования файла в другой файл и на экран

void copy_to( ifstream& in, ofstream& out )

{

char character;

in.get( character );

while ( !in.eof() )

{

cout << character;

out.put( character );

in.get( character );

}

// Конец функции

Программа 6.1.

7. Операторы ввода/вывода ">>" и "<<"

До сих пор рассматривались способы записи и чтения из файлов отдельных

символов
.
На нижнем уровне
,
скрытом внутри классов
ofstream
and
ifstream
,
объ
-

екты этих классов всегда работают с файлами как с последовательностями символов
.

Поэтому данные других типов
("
int
", "
double
"
и др
.)
для записи в файл должны быть

преобразованы в последовательность символов
.
При чтении из файла эти последова
-

тельности должны быть преобразованы обратно
.

Некоторые преобразования типов данных автоматически выполняются опера
-

торами
"
>>
"
и
"
<<
" (
в предыдущих лекциях они часто использовались для ввода с кла
-

виатуры и вывода на экран
).
Например
,
из состояния
,
показанного на рис
. 13:

Рис. 13. Состояние программы после открытия файла вывода
(
после подклю
-

чения потока вывода к файлу
).

с помощью оператора

out_stream << 437 << ' ';

программа перейдет в новое состояние
,
изображенное на рис
. 14.

Рис. 14. Состояние программы после записи в поток вывода целого значения

"
437
"
и пробела
.

При использовании операторов
"
>>
"
и
"
<<
"
обязательно надо после каждого за
-

писанного значения записывать еще как минимум один символ
' '
(
пробел
)
или слу
-

жебный символ
'\n'
(
маркер конца строки
).
Это гарантирует
,
что элементы данных

будут корректно отделены в файле друг от друга
,
и их можно будет извлекать оттуда

с помощью оператора
"
>>
".
Например
,
в состоянии
,
показанном на рис
. 15:

Рис. 15. Состояние программы в некоторый момент времени
,
когда текущая

позиция потока ввода установлена на пробел
.

если
"
n
"
является переменной типа
"
int
"
и имеет значение
10
,
то выполнение опера
-

тора

in_stream >> n;

приведет к состоянию
,
показанному на рис
. 16.

Рис. 16. Состояние программы после чтения из потока ввода целого значения

"
437
".

Обратите внимание
,
что оператор
"
>>
"
перед числом
437
пропустил пробел
' '
.

Этот оператор всегда пропускает пробелы
,
независимо от типа считываемых данных

(
даже при чтении символов
).

Работа с операторами
"
>>
"
и
"
<<
"
продемонстрирована в программе
7.1.
Снача
-

ла она создает файл
"
Integers.txt
",
записывает в него целые числа
51
,
52
,
53
,
54
и

55
,
а затем считывает эти числа из файла
.

#include <iostream.h>

#include <fstream.h>

int main()

{

char character;

int number = 51;

int count = 0;

ofstream out_stream;

ifstream in_stream1; // Поток для подсчета целых чисел.

ifstream in_stream2; // Поток для подсчета символов.

// Создание файла

out_stream.open( "Integers.txt" );

for ( count = 1; count <= 5; count++ )

out_stream << number++ << ' ';

out_stream.close();

// Подсчет количества целых чисел в файле

in_stream1.open( "Integers.txt" );

count = 0;

in_stream1 >> number;

while ( !in_stream1.eof() )

{

count++;

in_stream1 >> number;

}

in_stream1.close();

cout << "В файле хранится " << count << " целых чисел,\n";

// Подсчет количества символов, не являющихся разделителями

in_stream2.open( "Integers.txt" );

count = 0;

in_stream2 >> character;

while ( !in_stream2.eof() )

{

count++;

in_stream2 >> character;

}

in_stream2.close();

cout << "представленных с помощью " << count << " символов.\n";

return 0;

}

Программа 7.1.

Программа
7.1
выведет на экран следующие сообщения
:

В файле хранится 5 целых чисел,

представленных с помощью 10 символов.

При подсчете символов в последней части программы
7.1
снова обратите вни
-

мание на то
,
что
,
в отличие от функции
"
get(...)
",
оператор
"
>>
"
игнорирует в файле

пробелы
(
которые разделяют пять целых чисел
).

8. Сводка результатов

В лекции рассмотрены способы работы с текстовыми файлами с помощью по
-

токов ввода
/
вывода
. "
Низкоуровневый
"
ввод
/
вывод выполняется с помощью функций

"
get(...)
"
и
"
put(...)
",
а
"
высокоуровневый
"
ввод
/
вывод значений разных типов
–
с

помощью потоковых операторов
"
>>
"
и
"
<<
".

9. Упражнения

Упражнение 1

Напишите программу
,
печатающую на экране содержимое собственного ис
-

ходного файла на Си
++.

Упражнение 2

Разработайте программу
,
которая
(1)
начинается с оператора вывода тестового

сообщения
:

cout << "Проверка: " << 16/2 << " = " << 4*2 << ".\n\n";

и затем
(2)
копирует собственный исходный файл на Си
++
в файл

"
WithoutComments.cpp
"
и на экран
,
при этом пропуская все комментарии между

маркерами
"
/* ... */
" (
и маркеры комментариев тоже
).

Получившийся файл
"
WithoutComments.cpp
"
должен компилироваться и ра
-

ботать точно так же
,
как и исходная программа
.

Подсказки:

(1) вам может пригодиться функция "

putback()
"; (2) для отслежива-

ния состояния, находитесь ли вы внутри комментария или нет, можете применить

логический "флаг".

Упражнение 3

Напишите программу
,
которая подсчитывает и выводит на экран количество

символов
(
включая пробелы
)
в собственном исходном файле
.

Упражнение 4

Без использования массива
(
массивы будут рассмотрены в
6-
й лекции
)
напи
-

шите программу
,
которая печатает на экране собственный исходный файл в обратном

порядке
.

Подсказки:

(1) Для начальной части этой программы может пригодиться програм-

ма из упражнения 3. (2) Будьте внимательны и не используйте поток ввода после

ошибки – вместо этого работайте с новым потоком.

Примечание:

не беспокойтесь, если перед началом печати происходит небольшая

задержка – открытие и закрытие файлов требует некоторого времени.

Упражнение 5

Что выведет на экран следующая программа
?

#include <iostream.h>

#include <fstream.h>

int main()

{

char character;

int integer;

ofstream out_stream;

ifstream in_stream;

// Создание текстового файла и запись в него двух целых чисел

out_stream.open( "Integers.txt" );

out_stream << 123 << ' ' << 456;

out_stream.close();

// Попытка чтения из только что созданного файла

// "Integers.txt" символа, затем целого числа,

// затем снова символа, затем опять целого числа.

in_stream.open( "Integers.txt" );

in_stream >> character >> integer;

cout << "символ: '" << character << "'\n";

cout << "целое число: " << integer << "\n";

in_stream >> character >> integer;

c
out << "символ: '" << character << "'\n";

cout << "целое число: " << integer << "\n";

in_stream.close();

return 0;

}

ЛЕКЦИЯ 5. Операторы ветвления и циклы

1. Логические значения, выражения и функции

В этой лекции подробно рассматриваются операторы ветвления
("
if
"
и

"
switch
")
и операторы циклов
"
for
"
и
"
while
".
Для применения всех этих операто
-

ров необходимо хорошо знать
,
что такое логические выражения и как они вычисля
-

ются
.

Язык Си
++
унаследовал от языка Си соглашение
,
согласно которому целое

значение
0
считается логическим
"
false
" (
ложное значение
),
а ненулевое целое
–
ло
-

гическим
"
true
" (
истинным значением
).
Но выражения вроде

условие1 == 1

или

условие2 == 0

не слишком удобны при чтении теста программ человеком
.
Было бы лучше записы
-

вать логические выражения в интуитивно понятном виде
:

условие1 == true

условие2 == false

Поэтому в Си
++
был добавлен специальный логический тип
"
bool
".
Перемен
-

ные типа
"
bool
"
могут принимать значения
"
true
"
и
"
false
",
которые при необхо
-

димости автоматически преобразуются в выражениях в значения
1
и
0
.

Тип данных
"
bool
"
можно использовать в программах точно так же
,
как и ти
-

пы
"
int
", "
char
"
и др
. (
например
,
для описания переменных или для создания функ
-

ций
,
возвращающих значения типа
"
bool
").

Программа
1.1
приведена в качестве примера использования типа данных

"
bool
".
Она запрашивает с клавиатуры возраст кандидата
,
сдававшего некий тест
,
и

полученную кандидатом оценку в баллах
.
Затем программа оценивает результат вы
-

полнения теста по шкале
,
зависящей от возраста кандидата и делает вывод о том
,
сдан

тест или нет
.
Для кандидатов до
14
лет порог сдачи теста составляет
50
баллов
,
для
15

или
16
лет
–
55
баллов
,
старше
16-
ти лет
–
60
баллов
.

#include <iostream.h>

bool acceptable( int age, int score );

int main()

{

int candidate_age, candidate_score;

cout << "Введите возраст кандидата: ";

cin >> candidate_age;

cout << "Введите результат тестирования: ";

cin >> candidate_score;

if ( acceptable( candidate_age, candidate_score ) )

cout << "Этот кандидат сдал тест успешно.\n";

else

cout << "Этот кандидат тест не прошел.\n";

return 0;

}

// Функция оценки результата тестирования: тест сдан/не сдан

bool acceptable( int age, int score )

{

if ( age <= 14 && score >= 50 )

return true;

else if ( age <= 16 && score >= 55 )

return true;

else if ( score >= 60 )

return true;

else

return false;

}

Программа 1.1.

2. Циклы "for", "while" и "do...while"

Циклы
"
for
"
впервые встречались во
2-
й лекции
,
цикл
"
while
"
упоминался в

4-
й лекции
.
Любой цикл
"
for
"
можно переписать в виде цикла
"
while
"
и наоборот
.

Рассмотрим программу
2.1 (
она похожа на программу
2.2
из
2-
й лекции
).

#include <iostream.h>

int main()

{

int number;

char character;

for ( number = 32; number <= 126; number = number + 1 )

{

character = number;

cout << "Символ '" << character;

cout << "' имеет код " << number << "\n";

}

return 0;

}

Программа 2.1.

Программу
2.1
можно переписать с помощью цикла
"
while
" (
программа
2.2):

#include <iostream.h>

int main()

{

int number;

char character;

number = 32;

while ( number <= 126 )

{

character = number;

cout << "Символ '" << character;

cout << "' имеет код " << number << "\n";

number++;

}

return 0;

}

Программа 2.2.

Замена цикла
"
while
"
на цикл
"
for
"
выполняется совсем просто
.
Например
,
в

программе
2.2
строку

while (number <= 126)

можно заменить эквивалентным циклом
"
for
"
без операторов инициализации и из
-

менения значений
:

for ( ; number <= 126; )

В Си
++
есть еще один
,
третий
,
вариант цикла
–
оператор цикла с постфиксным

условием
(
постусловием
)
"do {...} while"

.
Он отличается от циклов
"
for
"
и
"
while
"

тем
,
что тело цикла внутри скобок
"
{}
"
обязательно выполняется как минимум один

раз
,
т
.
к
.
условие повторения цикла проверяется только после выполнения тела цикла
.

Циклы
"
Do ... while
"
используются довольно редко
.
Например этот цикл можно

применить для проверки корректности введенных с клавиатуры данных
(
програм
-

ма
2.2
а
).

...

do {

cout << "Введите результат тестирования: ";

cin >> candidate_score;

if ( candidate_score > 100 || candidate_score < 0 )

cout << "Допускается оценка от 0 до 100.\n";

} while ( candidate_score > 100 || candidate_score < 0 );

...

Фрагмент программы 2.2a.

В программе
2.2a
цикл с постусловием позволяет избавиться от дублирования

операторов печати приглашения и ввода данных
,
которое возникает при использова
-

нии эквивалентного цикла
"
while
" (
программа
2.2b).

...

cout << "Введите результат тестирования: ";

cin >> candidate_score;

while ( candidate_score > 100 || candidate_score < 0 )

{

cout << "Допускается оценка от 0 до 100.\n";

cout << "Введите результат тестирования: ";

cin >> candidate_score;

}

...

Фрагмент программы 2.2b.

3. Множественное ветвление и оператор "switch"

Вложенные операторы
"
if
",
предназначенные для выполнения
"
множествен
-

ного ветвления
",
уже встречались в
1-
й лекции
.
Упрощенная версия этого примера

приведена ниже
:

...

if ( total_test_score < 50 )

cout << "Вы не прошли тест. Выучите материал как следует.\n";

else if ( total_test_score < 60 )

cout << "Вы прошли тест со средним результатом.\n";

else if ( total_test_score < 80 )

cout << "Вы хорошо выполнили тест.\n";

else if ( total_test_score < 100 )

cout << "Вы показали отличный результат.\n";

else

{

cout << "Вы выполнили тест нечестно";

сout << "(оценка должна быть меньше 100 баллов)!\n";

}

...

Вложенные операторы
"
if
"
выглядят слишком громоздко
,
поэтому в Си
++

реализован еще один способ множественного ветвления
–
оператор
"
switch
".
Он по
-

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

текущего значения определенной переменной или выражения
.

В приведенном выше примере сообщение для печати выбирается в зависимо
-

сти от значения переменной
"
total_test_score
".
Это может быть произвольное целое

число в диапазоне от
0
до
100.
Диапазон проверяемых значений можно сузить
,
если

учесть
,
что оценка теста проверяется с точностью до
10-
ти баллов
.
Введем дополни
-

тельную целочисленную переменную
"
score_out_of_ten
"
и присвоим ей значение
:

score_out_of_ten = total_test_score/10;

Теперь проверку в программе можно сформулировать так
: (1)
если переменная

"
score_out_of_ten
"
равна
0, 1, 2, 3
или
4,
то печатать сообщение
"
Вы не прошли

тест. Выучите материал как следует.
", (2)
если
"
score_out_of_ten
"
равна

5,
то печатать сообщение
"
Вы прошли тест со средним результатом.
"
и

т
.
д
.
В целом оператор
"
switch
"
будет выглядеть так
:

...

score_out_of_ten = total_test_score / 10;

switch ( score_out_of_ten )

{

case 0 :

case 1 :

case 2 :

case 3 :

case 4 :

cout << "Вы не прошли тест. Выучите материал как следует.\n";

break;

case 5 :

cout << "Вы прошли тест со средним результатом.\n";

break;

case 6 :

case 7 :

cout << "Вы хорошо выполнили тест.\n";

break;

case 8 :

case 9 :

case 10 :

cout << "Вы показали отличный результат.\n";

break;

default :

cout << "Вы выполнили тест нечестно\n";

сout << "(оценка не должна быть больше 100 баллов)!\n";

}

...

Фрагмент программы 3.1.

Оператор
"
switch
"
имеет следующий синтаксис
:

switch (
селектор

)

{

case
метка

1 :

<операторы

1
>

break;

...

case
метка

N :

<операторы

N
>

break;

default :

<операторы>

}

Сделаем несколько важных замечаний относительно оператора
"
switch
":

•
Внутри
"
switch
"
выполняются операторы
,
содержащиеся между меткой
,

совпадающей с текущим значением селектора
,
и первым встретившимся по
-

сле этой метки оператором
"
break
".

•
Операторы
"
break
"
необязательны
,
но они улучшают читабельность про
-

грамм
.
С ними сразу видно
,
где заканчивается каждый вариант множествен
-

ного ветвления
.
Как только при выполнении операторов внутри
"
switch
"

встречается
"
break
",
то сразу выполняется переход на первый оператор про
-

граммы
,
расположенный после оператора
"
switch
".
Иначе продолжается

последовательное выполнение операторов внутри
"
switch
".

•
Селектор
(
переменная или выражение
)
может быть целочисленного
(
напри
-

мер
, "
int
"
или
"
char
")
или любого перечислимого типа
,
но не веществен
-

ного типа
.

•
Вариант
"
default
" ("
по умолчанию
")
необязателен
,
но для безопасности

лучше его предусмотреть
.

4. Блоки и область видимости переменных

В Си
++
фигурные скобки
"
{}
"
позволяют оформить составной оператор
,
кото
-

рый содержит несколько операторов
,
но во всех конструкциях языка может подстав
-

ляться как один оператор
.
На описания переменных фигурные скобки также оказы
-

вают важное влияние
.

Составной оператор
,
внутри которого описана одна или несколько переменных
,

называется
блоком

.
Для переменных
,
объявленных внутри блока
,
этот блок является

областью видимости

.
Другими словами
,
переменные
"
создаются
"
каждый раз
,
когда

при выполнении программа входит внутрь блока
,
и
"
уничтожаются
"
после выхода из

блока
.

Если одно и то же имя используется для переменной внутри и снаружи блока
,

то это две разных
,
независимых переменных
.
При выполнении внутри блока про
-

грамма по умолчанию полагает
,
что имя относится к внутренней переменной
.
Обра
-

щение к внешней переменной происходит только в том случае
,
если переменная с та
-

ким именем не описана внутри блока
.
Действие этого правила продемонстрировано в

программе
4.1.

#include <iostream.h>

int integer1 = 1;

int integer2 = 2;

int integer3 = 3;

int main()

{

int integer1 = -1;

int integer2 = -2;

{

int integer1 = 10;

cout << "integer1 == " << integer1 << "\n";

cout << "integer2 == " << integer2 << "\n";

cout << "integer3 == " << integer3 << "\n";

}

cout << "integer1 == " << integer1 << "\n";

cout << "integer2 == " << integer2 << "\n";

cout << "integer3 == " << integer3 << "\n";

return 0;

}

Программа 4.1.

Программа
4.1
выводит на экран сообщения
:

integer1 == 10

integer2 == -2

integer3 == 3

integer1 == -1

integer2 == -2

integer3 == 3

Применение локальных переменных иногда объясняется экономией памяти
,
а

иногда необходимостью использования в различных частях программы разных пере
-

менных с одинаковыми именами
.
См
.
в качестве примера программу
4.2,
которая пе
-

чатает таблицу умножения для чисел от
1
до
10.

#include <iostream.h>

int main()

{

int number;

for ( number = 1; number <= 10; number++ )

{

int multiplier;

for ( multiplier = 1; multiplier <= 10; multiplier++ )

{

cout << number << " x " << multiplier << " = ";

cout << number * multiplier << "\n";

}

cout << "\n";

}

return 0;

}

Программа 4.2.

Программу
4.2
можно переписать в более понятном виде с помощью функ
-

ции
(
см
.
программу
4.3).

#include <iostream.h>

void print_times_table( int value, int lower, int upper );

int main()

{

int number;

for ( number = 1; number <= 10; number++ )

{

print_times_table( number, 1, 10 );

cout << "\n";

}

return 0;

}

void print_times_table( int value, int lower, int upper )

{

int multiplier;

for ( multiplier = lower; multiplier <= upper; multiplier++ )

{

cout << value << " x " << multiplier << " = ";

cout << value * multiplier << "\n";

}

Программа 4.3.

Далее
,
программу
4.3
можно усовершенствовать
,
исключив описания всех пе
-

ременных из
"
main()
"
и добавив две функции
(
см
.
программу
4.4).

#include <iostream.h>

void print_tables( int smallest, int largest );

void print_times_table( int value, int lower, int upper );

int main()

{

print_tables( 1, 10 );

return 0;

}

void print_tables( int smallest, int largest )

{

int number;

for ( number = smallest; number <= largest; number++ )

{

print_times_table( number, 1, 10 );

cout << "\n";

}

void print_times_table( int value, int lower, int upper )

{

int multiplier;

for ( multiplier = lower; multiplier <= upper; multiplier++ )

{

cout << value << " x " << multiplier << " = ";

cout << value * multiplier << "\n";

}

Программа 4.4.

5. Замечание о вложенных циклах

В первоначальном варианте программы
"
таблица умножения
" (
программа
4.2)

есть вложенные циклы
.
В последующих вариантах программы читабельность исход
-

ного текста улучшается с помощью процедурной абстракции
.
Преобразование тела

цикла в вызов функции позволяет производить разработку этого алгоритма независи
-

мо от остальной части программы
.
Поэтому уменьшается вероятность ошибок
,
свя
-

занных с областью видимости переменных и перегрузкой имен переменных
.

Недостаток выноса тела цикла в отдельную функцию заключается в уменьше
-

нии быстродействия
,
поскольку на вызов функции тратится больше времени
,
чем на

итерацию цикла
.
Если цикл выполняется не очень часто и не содержит большого ко
-

личества итераций
(
больше нескольких десятков
),
то временными затратами на вызов

функции вполне можно пренебречь
.

6. Сводка результатов

Тип данных
"
bool
"
предназначен для использования в логических выражениях

и в качестве возвращаемого значения логических функций
.
Такие функции можно

применять в качестве условий в условных операторах и операторах циклов
.
В Си
++

есть три варианта циклов
: "
for
", "
while
"
и
"
do ... while
".

Вложенные операторы
"
if
"
в некоторых случаях можно заменить оператором

множественного ветвления
"
switch
".

Внутри составного оператора
(
блока
),
ограниченного _______фигурными скобка
-

ми
"
{}
",
допускается описание локальных переменных
(
внутренних переменных бло
-

ка
).

7. Упражнения

Упражнение 1

Разработайте функцию
,
которая принимает целочисленный параметр и возвра
-

щает логическое
("
bool
")
значение
"
true
",
только если переданное ей число является

простым числом из диапазона от
1
до
1000 (
число
1
простым не считается
).
Проверьте

свою функцию на различных входных данных с помощью тестовой программы
.

Подсказка:

(1) если число не является простым, то оно имеет как минимум один

простой множитель, меньший или равный квадратному корню из числа.

(2) (32*32)=1024 и 1024>1000.

Упражнение 2

Напишите функцию
"
print_pyramid(...)
",
которая получает целочисленный

параметр
"
height
(
высота
)"
и отображает на экране
"
пирамиду
"
заданной высоты из

символов
"
*
".
Проверьте функцию с помощью простой тестовой программы
,
которая

должна воспроизводить следующий примерный диалог с пользователем
:

Эта программа печатает на экране "пирамиду"

заданной высоты.

Введите высоту пирамиды:
37

Введите другое значение (из диапазона от 1 до 30):
6

****

******

********

**********

************

Упражнение 3

Цикл
"
for
"
всегда можно переписать в форме цикла
"
while
",
и наоборот
.
Яв
-

ляются ли две показанных ниже программы эквивалентными
?
Какие сообщения они

печатают на экране
?
Объясните свой ответ и проверьте его опытным путем
.

Программа
3
а
:

#include <iostream.h>

int main()

{

int count = 1;

for ( ; count <= 5; count++ )

{

int count = 1;

cout << count << "\n";

}

return 0;

}

Программа
3b:

#include <iostream.h>

int main()

{

int count = 1;

while ( count <= 5 )

{

int count = 1;

cout << count << "\n";

count++;

}

return 0;

}

Упражнение 4

Приведенная ниже программа должна печатать время закрытия магазина в раз
-

личные дни недели
(
в виде таблицы
).
В программе объявлен новый перечислимый

тип данных
"
День
"
и определена функция
"
closing_time(...)
",
которая должна воз
-

вращать час закрытия магазина в заданный день
(
пока эта функция не слишком слож
-

на
–
для любого дня возвращает значение
17).
Программа демонстрирует
,
как можно

использовать типы
"
int
"
и
"
D
ay
"
в преобразованиях типов
(
в заголовке цикла
"
for
"
и

при вызове функции
"
closing_time(...)
").

#include <iostream.h>

enum Day { Monday, Tuesday, Wednesday, Thursday,

Friday, Saturday, Sunday };

int closing_time( Day day_of_the_week );

// Главная функция

int main()

{

int count;

// Печать заголовка таблицы

cout.width(17);

cout << "ДЕНЬ";

cout.width(19);

cout << "ВРЕМЯ ЗАКРЫТИЯ \n\n";

// Печать таблицы от понедельника (Monday) до

// воскресенья
___________
(Sunday)

for ( count = int(Monday); count <= int(Sunday); count++ )

{

cout.width(19);

switch ( count )

{

case 0 : cout << "Понедельник"; break;

case 1 : cout << "Вторник";
break;

case 2 : cout << "Среда"; break;

case 3 : cout << "Четверг"; break;

case 4 : cout << "Пятница"; break;

case 5 : cout << "Суббота"; break;

case 6 : cout << "Воскресенье"; break;

default : cout << "ОШИБКА!";

}

cout.width(9);

cout << closing_time( Day(count) ) << ":00\n";

}

return 0;

}

// Конец главной функции

// Функция, возвращающая время закрытия магазина

// в заданный день недели

int closing_time( Day day_of_the_week )

{

return 17;

}

(
а
)
Что произойдет
(
и почему
),
если заменить оператор
"
switch
"
на строку

cout << Day(count);
?

Вместо этого замените
"
switch
"
на строку

print_day( Day(count), cout );

и добавьте описание и определение функции
"
print_day(...)
",
внутри которой

разместите удаленный из главной функции оператор
"
switch
" (
поток стандарт
-

ного вывода
"
cout
"
передавайте в функцию как параметр по ссылке ти
-

па
"
ostream&
").

(
б
)
Магазин закрывается в воскресенье в
13:00,
в субботу в
17:00,
в среду в
20:00
и в

остальные дни в
18:00.
С помощью оператора
"
switch
"
внесите соответствующие

изменения в функцию
"
closing_time(...)
"
и проверьте работу программы
.

Упражнение 5

Напишите программу
,
которая отображает в виде таблицы количество строч
-

ных английских букв
(
от
'a'
до
'z'
)
в собственном исходном файле
"
ex5_5.cpp
"

(
сохраните исходный текст программы именно в этом файле
).

При разработке программы предположите
,
что у компьютера очень мало памя
-

ти
–
используйте только одну переменную типа
"
ifstream
",
одну переменную типа

"
char
"
и две переменных типа
"
int
".
Программа должна выдавать на экран сообще
-

ния
,
похожие на следующие
:

СИМВОЛ КОЛИЧЕСТВО ВХОЖДЕНИЙ

a 38

b 5

c 35

d 7

e 58

f 8

...

w 4

x 4

y 0

z 1

ЛЕКЦИЯ 6. Массивы и символьные строки

1. Назначение массивов

В программировании часто возникают задачи
,
связанные с обработкой боль
-

ших объемов данных
.
Для постоянного хранения этих данных удобно пользоваться

файлами
.
Например
,
в программе для ввода и сортировки длинных числовых списков

данные можно ввести с клавиатуры один раз и сохранить в файле для последующего

многократного использования
.
Но до сих пор не было рассмотрено удобного способа

представления больших объемов данных внутри программ
.
Для этой цели в Си
++

часто применяются
массивы

–
простейшая разновидность
структурных типов дан-

ных

(
о более сложных структурах данных будет говориться в следующих лекциях
).

Массив
–
это набор переменных одного типа
("
int
", "
char
"
и др
.).
При объявле
-

нии массива компилятор выделяет для него
последовательность

ячеек памяти
,
для

обращения к которым в программе применяется одно и то же имя
.
В то же время мас
-

сив позволяет получить прямой доступ к своим отдельным элементам
.

1.1 Объявление массивов

Оператор описания массива имеет следующий синтаксис
:

<тип данных> <имя переменной>[<целое значение>];

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

работанных в течении недели группой из
6-
ти сотрудников
.
Для хранения этих дан
-

ных можно объявить массив
:

int hours[6];

или
,
лучше
,
задать численность группы с помощью специальной константы
:

const int NO_OF_EMPLOYEES = 6;

int hours[NO_OF_EMPLOYEES];

Если подобные массивы будут часто встречаться в программе
,
то целесообраз
-

но определить новый тип
:

const int NO_OF_EMPLOYEES = 6;

typedef int Hours_array[NO_OF_EMPLOYEES];

Hours_array hours;

Hours_array hours_week_two;

В любом из трех перечисленных вариантов
,
в программе будет объявлен мас
-

сив из
6
элементов типа
"
int
",
к которым можно обращаться с помощью имен
:

hours[0] hours[1] hours[2] hours[3] hours[4] hours[5]

Каждое из этих имен является именем
элемента

массива
.
Числа
0
,
...
,
5
назы
-

ваются
индексами

элементов
.
Отличительная особенность массива заключается в том
,

что его элементы
–
однотипные переменные
–
занимают в памяти компьютера после
-

довательные ячейки памяти
(
рис
. 1).

Рис. 1.
.
Расположение элементов массива в оперативной памяти
(
направление

сверху вниз соответствует возрастанию адресов ячеек памяти
).

1.2 Использование элементов массивов в выражениях

С элементами объявленного массива можно выполнять все действия
,
допусти
-

мые для обычных переменных этого типа
(
выше был приведен пример целочисленно
-

го массива
,
т
.
е
.
типа
"
int
").
Например
,
возможны операторы присваивания наподо
-

бие
:

hours[4] = 34;

hours[5] = hours[4]/2;

или логические выражения с участием элементов массива
:

if (number < 4 && hours[number] >= 40) { ...

Присвоить значения набору элементов массива часто бывает удобно с помо
-

щью циклов
"
for
"
или
"
while
".
В программе
1.1
в цикле у оператора запрашивается

количество часов
,
отработанных каждым сотрудником группы за неделю
.
Хотя более

естественной может показаться нумерация сотрудников от
1
до
6,
а не от
0
до
5,
но

необходимо помнить
,
что индексация массивов в Си
++
начинается с
0.
Поэтому про
-

грамма
1.1
вычитает
1
из порядкового номера сотрудника
,
чтобы вычислить индекс

соответствующего элемента массива
.

#include <iostream.h>

const int NO_OF_EMPLOYEES = 6;

typedef int Hours_array[NO_OF_EMPLOYEES];

int main()

{

Hours_array hours;

int count;

for ( count = 1; count <= NO_OF_EMPLOYEES; count++ )

{

cout << "Сколько часов отработал сотрудник";

cout << " номер "
<< count << "?: ";

cin >> hours[count - 1];

}

return 0;

}

Программа 1.1.

В типичном сеансе работы программа
1.1
выведет на экран подобные сообщения
:

Сколько часов отработал сотрудник номер
1?:
38

Сколько часов отработал сотрудник номер
2?:
42

Сколько часов отработал сотрудник номер
3?:
29

Сколько часов отработал сотрудник номер
4?:
35

Сколько часов отработал сотрудник номер
5?:
38

Сколько часов отработал сотрудник номер
6?:
37

На рис
. 2.
показано состояние целочисленного массива после ввода этих данных
.

Рис. 2.
.
Состояние массива после присвоения значений его элементам
.

Полезно разобраться
,
что произошло бы
,
если бы в программе
1.1
внутри цикла

"
for
"
в операторе
"
cin ...
"
отсутствовало бы вычитание
1
из переменной
"
count
".

Компилятор Си
++ (
в отличие
,
например
,
от Паскаля
)
не обнаруживает ошибки выхо
-

да за пределы массива
,
поэтому участок памяти компьютера с массивом и сразу за

ним оказался бы в состоянии
,
показанном на рис
. 3.

Рис. 3.
.
Ошибка выхода за пределы массива
.

Другими словами
,
значение
"
37
"
было бы размещено в ячейке памяти
,
доста
-

точной для хранения целого числа
,
которая расположена сразу после массива
"
hours
".

Это чрезвычайно нежелательная ситуация
,
потому что компилятор может зарезерви
-

ровать эту ячейку памяти для другой переменной
(
например
,
для переменной

"
count
").

Массивы могут быть любого типа
,
не обязательно типа
"
int
".
Ниже приведена

программа
1.2,
в которой символьный
("
char
")
массив применяется для печати собст
-

венного исходного файла на экране в обратном порядке
.

#include <iostream.h>

#include <fstream.h>

const int MAX_LEN = 1000;

typedef char File_array[MAX_LEN];

int main()

{

char character;

File_array file;

int count;

ifstream in_stream;

in_stream.open("prg6_1_2.cpp");

in_stream.get(character);

for ( count = 0; !in_stream.eof() && count < MAX_LEN; count++ )

{

file[count] = character;

in_stream.get(character);

}

in_stream.close();

while (count > 0)

cout << file[--count];

return 0;

}

Программа 1.2.

В заголовке цикла
"
for
"
обратите внимание на условие
"
... && count < MAX ;

...
",
специально предусмотренное для предотвращения выхода за пределы массива
.

2. Передача массивов в качестве параметров функций

Чтобы у программ была понятная человеку структура
,
допускающая модифи
-

кацию и повторное использование исходного текста
,
отдельные алгоритмы следует

реализовывать в виде самостоятельных функций
.
Т
.
к
.
для хранения данных часто

применяются массивы
,
то бывают необходимы и функции для их обработки
.
Этим

функциям массивы можно передавать в качестве параметров
.
В показанном ниже

фрагменте программы
2.1
содержится определение функции
,
которая принимает мас
-

сив типа
"
Hours_array
" (
см
.
программу
1.1)
и возвращает среднее количество часов
,

отработанных сотрудниками группы
.

float average( Hours_array hrs )

{

float total = 0;

int count;

for ( count = 0; count < NO_OF_EMPLOYEES; count++ )

total += float(hrs[count]);

return ( total/NO_OF_EMPLOYEES );

}

Фрагмент программы 2.1.

Эту функцию можно сделать более универсальной
,
если размер массива не

фиксировать в ее определении
,
а передать в качестве второго параметра
:

float average( int list[], int length )

{

float total = 0;

int count;

for ( count = 0 ; count < length; count++ )

total += float(list[count]);

return ( total/length );

}

В этом примере показан очень распространенный способ оформления функций
,

работающих с массивами
:
в одном параметре передается длина массива
,
а в другом
–

сам массив
,
причем в описании параметра
-
массива не указывается длина массива
(
на
-

пример
, "
int list[]
").

Параметры
-
массивы всегда передаются по ссылке
(
а не по значению
),
хотя при

их описании в заголовке функции символ
"
&
"
не указывается
.
Правило
"
массивы все
-

гда передаются по ссылке
"
введено для того
,
чтобы функции не делали собственных

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

привести к нерациональным затратам памяти
.
Следовательно
,
как и параметры по

ссылке
,
рассматривавшиеся в
3-
ей лекции
,
все изменения элементов параметров
-

массивов внутри функций будут видны и в вызывающей функции
.

Далее показана функция
(
фрагмент программы
2.2),
принимающая в качестве

параметров три массива
.
После ее вызова каждый элемент третьего массива будет ра
-

вен сумме двух соответствующих элементов первого и второго массивов
.

void add_lists( int first[], int second[], int total[],

int length )

{

int count;

for ( count = 0; count < length; count++ )

total[count] = first[count] + second[count];

}

Фрагмент программы 2.2.

В целях безопасности
,
для защиты от случайного изменения элементов масси
-

ва
,
в описание первых двух параметров функции добавим модификатор типа
"
const
":

void add_lists( const int fst[], const int snd[], int tot[],

int len )

{

int count;

for ( count = 0; count < len; count++ )

tot[count] = fst[count] + snd[count];

}

Теперь компилятор не будет обрабатывать ни один оператор в определении

функции
,
который пытается модифицировать элементы константных массивов
"
fst
"

или
"
snd
".
Фактически
,
ограничение
,
накладываемое модификатором
"
const
"
в дан
-

ном контексте
,
в некоторых ситуациях оказывается слишком строгим
.
Например
,

компилятор выдаст ошибку при обработке следующих двух функций
:

void no_effect( const int list[] )

{

do_nothing( list );

}

void do_nothing( int list[] )

{

;

}

Фрагмент программы 2.3.

Ошибка компиляции программы
2.3
объясняется тем
,
что
,
хотя фактически

функция
"
do_nothing(...)
"
не выполняет никаких действий
,
но в ее заголовке отсут
-

ствует модификатор
"
const
".
Когда компилятор в теле функции
"
no_effect(...)
"

встретит вызов функции
"
do_nothing(...)
",
то он обратится только к заголовку функ
-

ции
"
do_nothing(...)
",
и выдаст ошибку о невозможности передачи константного

массива в эту функцию
.

3. Сортировка массивов

По отношению к массивам часто возникает задача сортировки по убыванию

или возрастанию
.
Разработано много различных алгоритмов сортировки
,
например
,

пузырьковая сортировка

и
быстрая сортировка

.
В этом параграфе кратко рассматри
-

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

наименьшего элемента

.

Основные действия алгоритма для сортировки массива длиной
L

заключаются

в следующем
:

Для каждого значения индекса
i

выполнить два действия
:

1)
Среди элементов с индексами от
i

до
(
L

-1)
найти

элемент с минимальным значением
.

2)
Обменять значения
i

-
го и минимального элемен
-

тов
.

Работу этого алгоритма рассмотрим на примере сортировки массива из
5
целых

чисел
:

int a[5];

Значения элементов неотсортированного массива показаны на рис
. 4.

Рис. 4.
.
Начальное состояние массива
.

В процессе сортировки методом выбора наименьшего элемента массив будет

последовательно переходить в состояния
,
показанные на рис
. 5 (
слева направо
).
Каж
-

дое состояние получается из предыдущего путем перестановки двух элементов
,
поме
-

ченных на рис
. 5
кружками
.

Рис. 5.
.
Последовательные шаги сортировки массива методом выбора наи
-

меньшего элемента
.

На Си
++
алгоритм сортировки можно реализовать в виде трех функций
.
Функ
-

ция высокого уровня будет называться
"
selection_sort(...)
" (
у нее два параметра
–

сортируемый массив и его длина
).
Сначала эта функция вызывает вспомогательную

функцию
"
minimum_from(array,position,length)
",
которая возвращает индекс мини
-

мального элемента массива
"
array
",
расположенного в диапазоне между индексом

"
position
"
и концом массива
.
Затем для обмена двух элементов массива вызывается

функция
"
swap(...)
".

void selection_sort( int a[], int length )

{

for ( int count = 0; count < length - 1; count++ )

swap( a[count], a[minimum_from(a,count,length)] );

}

int minimum_from( int a[], int position, int length )

{

int min_index = position;

for ( int count = position + 1; count < length; count++ )

if ( a[count] < a[min_index] )

min_index = count;

return min_index;

}

void swap( int& first, int& second )

{

int temp = first;

first = second;

second = temp;

}

Фрагмент программы 3.1.

4. Двумерные массивы

Массивы в Си
++
могут иметь более одной размерности
.
В данном параграфе

кратко описаны двумерные массивы
.
Они широко применяются для хранения дву
-

мерных структур данных
,
например
,
растровых изображений и матриц
.

При обработке изображений часто используются битовые маски
–
вспомога
-

тельные двуцветные
(
черно
-
белые
)
изображения
,
состоящие только из
0 (
белая точка
)

и
1 (
черная точка
) (
или
,
логических значений
"
false
"
и
"
true
").
Предположим
,
что

требуется маска размером
64
х
32
пиксела
.
Для описания соответствующего массива

возможны операторы
:

const int BITMAP_HEIGHT = 64;

const int BITMAP_WIDTH = 32;

bool bitmap[BITMAP_HEIGHT][BITMAP_WIDTH];

При обращении к элементам массива
"
bitmap
"
необходимо указывать два ин
-

декса
.
Например
,
чтобы изменить значение
2-
го пиксела слева в
4-
й строке надо запи
-

сать оператор
:

bitmap[3][1] = true;

Все сказанное во
2-
м параграфе относительно одномерных массивов как пара
-

метров функций верно и для двумерных массивов
,
но у них есть еще одна особен
-

ность
.
В прототипах и заголовках функций можно опускать первую размерность мно
-

гомерного массива
-
параметра
(
т
.
е
.
записывать пустые квадратные скобки
"
[]
"),
но все

остальные размерности надо обязательно указывать
.
Далее в качестве примера приве
-

дена функция
,
заполняющая битовую карту черными пикселами
.

void clear_bitmap( bool bitmap[][BITMAP_WIDTH],

int bitmap_height )

{

for ( int row = 0; row < bitmap_height; row++ )

for ( int column = 0; column < BITMAP_WIDTH; column++ )

bitmap[row][column] = false;

}

5. Символьные строки

Во многих уже рассматривавшихся программах для вывода на экран часто ис
-

пользовались символьные строки
,
например
, "
"Введите возраст:"
".
В Си
++
строки

хранятся и обрабатываются в виде символьных массивов
,
на которые накладывается

дополнительное ограничение
(
см
.
п
.5.1).

5.1 Завершающий нуль-символ '\0'

Символьный массив для хранения строки должен иметь длину на
1
символ

больше
,
чем длина строки
.
В последнем элементе массива хранится специальный

нуль
-
символ
(
символ с кодом
0,
часто обозначается
'\0'
).
Этот служебный символ

обозначает конец строки
,
и это общепринятое правило представления строк
,
которое

соблюдают все библиотечные функции для работы со строками
.

На рис
. 6
показаны два массива
,
в которых хранятся символы строки
"
"
Введите

возраст:"
",
но из них только массив
"
phrase
"
является правильным представлением

строки
.
Хотя и
"
phrase
",
и
"
list
"
являются символьными массивами
,
но только

"
phrase
"
имеет достаточную длину для хранения символьной строки
"
"Введите воз-

раст:"
"
вместе с завершающим символом
"
'\0'
".

Рис. 6.
.
Правильное
("phrase")
и неправильное
("list")
представление сим
-

вольной строки
.

5.2 Объявление и инициализация символьных строк

Символьные строки описываются как обычные массивы
:

char phrase[17];

Массивы можно полностью или частично проинициализировать непосредст
-

венно в операторе описания
.
Список значений элементов массива заключается в фи
-

гурные скобки
"
{}
" (
это правило верно для любых массивов
,
а не только для сим
-

вольных
).
Например
,
оператор

char
phrase[17] = { 'В','в','е','д','и','т','е',' ',

'в','о','з','р','а','с','т',

':', '\0' };

одновременно и объявляет массив
"
phrase
",
и присваивает его элементам значения

согласно рис
. 6.
То же самое делает оператор
:

char phrase[17] = "Введите возраст:";

Если не указывать размер
"
17
",
то размер массива будет выбран в соответствии

с количеством инициализирующих значений
(
с учетом завершающего нуль
-
символа
).

Т
.
е
.
строку можно описать с помощью любого из двух следующих операторов
:

char phrase[] = { 'В','в','е','д','и','т','е',' ',

'в','о','з','р','а','с','т',

':', '\0' };

char phrase[] = "Введите возраст:";

Очень важно запомнить
,
что символьные строки хранятся в виде массивов
.
По
-

этому их нельзя приравнивать и сравнивать с помощью операций
"
=
"
и
"
==
".
Напри
-

мер
,
нельзя записать оператор присваивания
:

phrase = "Вы напечатали строку:";

Для копирования и сравнения строк следует применять специальные библио
-

течные функции
.

5.3 Библиотечные функции для работы с символьными строками

В стандартном библиотечном файле
"
string.h
"
хранятся прототипы большо
-

го количества полезных функций для обработки символьных строк
.
Будем полагать
,

что в рассматриваемые далее программы этот заголовочный файл включается с по
-

мощью директивы препроцессора
:

#include <string.h>

Если в программе есть строковая переменная
"
a_string
",
то скопировать в нее

содержимое другой строки можно с помощью функции
"
strcpy(...)
":

strcpy( a_string, "Вы напечатали строку:" );

Этот оператор скопирует в массив
a_string
символы константной строки
"
"Вы

напечатали строку:"
"
и добавит в конец массива
(
т
.
е
.
присвоит
21-
му элементу
)
за
-

вершающий нуль
-
символ
"
'\0'
".
Вызов оператора

strcpy( a_string, another_string );

приведет к копированию строки
,
хранящейся в массиве
"
another_string
",
в массив

"
a_string
".
При копировании строк важно
,
чтобы длина массива
-
приемника

("
a_string
")
была
,
как минимум
, (
L

+1),
где
L

–
длина копируемой строки

("
another_string
").
В противном случае вызов функции приведет к ошибке выхода за

пределы массива
,
которая не обнаруживается компилятором
,
но может привести к

серьезным сбоям во время выполнения программы
.

Для вычисления длины строки предназначена функция
"
strlen(...)
".
Вызов

"
strlen(another_string)
"
возвращает длину строки
"
another_string
" (
без учета нуль
-

символа
).

Функция
"
strcmp(...)
"
выполняет сравнение двух переданных ей строк
.
Если

строки одинаковы
,
то эта функция возвратит
0 (
т
.
е
. "
false
"),
а если строки различа
-

ются
,
то функция возвратит ненулевое значение
.

Функция конкатенации
(
соединения
)
строк
"
strcat(...)
"
получает два пара
-

метра
-
строки и копирует вторую строку в конец первой
.
При работе с
"
strcat(...)
",

как и с функцией
"
strcpy(...)
",
надо обязательно следить за размером массива
-

приемника
.
Си
++
не проверяет
,
достаточен ли размер первого массива
,
переданного

этой функции
,
для хранения соединенных строк
.
При малом размере массива про
-

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

Работа с библиотечными строковыми функциями продемонстрирована в про
-

грамме
5.1.

5.4 Чтение символьных строк из потока ввода с помощью функции "getline(...)"

Для ввода строк
(
например
,
с клавиатуры
)
пригоден оператор
"
>>
",
но его при
-

менение ограничено
,
поскольку этот оператор считает пробелы разделителями
.
До
-

пустим
,
в программе содержатся операторы
:

...

cout << "Введите имя: ";

cin >> a_string;

...

После сеанса работы со следующими экранными сообщениями
:

...

Введите имя: Вася Иванов

...

Переменной
"
a_string
"
будет присвоено значение
"
"Вася"
",
т
.
к
.
оператор
"
>>
"

считает пробел разделителем
,
который сигнализирует о завершении ввода значения
.

Для ввода символьных строк часто более удобной оказывается функция

"
getline(...)
",
имеющая
2
параметра
.
Например
,
оператор
:

cin.getline(a_string, 80);

позволяет получить от пользователя строку с пробелами длиной до
79
символов
(
по
-

следний
, 80-
й символ строки
–
служебный нуль
-
символ
).

В программе
5.1
демонстрируется действие функций
"
getline(...)
",

"
strcmp(...)
", "
strcpy(...)
"
и
"
strcat(...)
".

#include <iostream.h>

#include <string.h>

const int MAXIMUM_LENGTH = 80;

int main()

{

char first_string[MAXIMUM_LENGTH];

char second_string[MAXIMUM_LENGTH];

cout << "Введите первую строку: ";

cin.getline(first_string,MAXIMUM_LENGTH);

cout << "Введите вторую строку:
";

cin.getline(second_string,MAXIMUM_LENGTH);

cout << "До копирования строки были ";

if ( strcmp(first_string,second_string) )

cout << "не ";

cout << "одинаковыми.\n";

strcpy( first_string, second_string );

cout << "После копирования строки стали ";

if ( strcmp(first_string,second_string) )

cout << "не ";

cout << "одинаковыми.\n";

strcat( first_string, second_string);

cout << "После конкатенации первая строка равна: ";

cout << first_string;

return 0;

}

Программа 5.1.

Программа
5.1
в типичном сеансе работы выводит сообщения
:

Введите первую строку:
Строка 1.

Введите вторую строку:
Строка 2.

До копирования строки были не одинаковыми.

После копирования строки стали одинаковыми.

После конкатенации первая строка равна:
Строка 2.Строка 2.

6. Сводка результатов

Набор однотипных переменных можно представить в виде массива
.
Массивы

можно передавать в качестве параметров внутрь функций
.
В лекции описан простой

алгоритм сортировки массивов методом выбора наименьшего элемента
.
Кратко рас
-

смотрены приемы работы с двумерными массивами
.

Символьные строки в Си
++
хранятся в виде символьных массивов
,
последний

символ в которых является служебным нуль
-
символом
.
В стандартной библиотеке

Си
++
есть специальные функции для обработки символьных строк
.

7. Упражнения

Упражнение 1

Напишите библиотеку функций для работы с целочисленными массивами
.

Прототипы
_______функций поместите в заголовочный файл
"
IntegerArray.h
",
а опреде
-

ления
–
в файл реализации
"
IntegerArray.cpp
".
Библиотека должна содержать

следующие функции
:

•
"
input_array(a,n)
"
для ввода с клавиатуры первых
n
значений массива
a
.

•
"
display_array(a,n)
"
для вывода на экран первых
n
значений массива
a
.

•
"
copy_array(a1,a2,n)
"
для копирования первых
n
элементов массива
a2
в соответ
-

ствующие элементы массива
a1
.

•
"
standard_deviation(a,n)
",
которая вычисляет и возвращает среднеквадратическое

отклонение первых
n
элементов массива
a.
(
Для реализации этой функции может

пригодиться функция
"
average(a,n)
"
из программы
2.1.)
Формула для вычисления

среднеквадратического отклонения дана в упражнении
3
из лекции
3.

Проверьте разработанные функции с помощью подходящей тестовой программы
.

Упражнение 2

Из функции
"
selection_sort(...)
",
рассматривавшейся в лекции
,
сделайте

функцию сортировки символьной строки
"
string_sort(...)
".
У этой функции один

параметр
–
строка
,
которая должны быть отсортирована в алфавитном порядке
(
точ
-

нее
,
по возрастанию
ASCII-
кодов
,
при этом все прописные буквы будут помещены до

строчных
).
Позиция завершающего нуль
-
символа при сортировке не меняется
.
Про
-

верьте работу функции с помощью тестовой программы
,
которая должна выводить на

экран сообщения
:

Введите строку:
Вася Иванов

Отсортированная строка равна: ВИааввнося

Упражнение 3

Напишите функцию
"
no_repetitions(...)
",
которая удаляет из строки все по
-

вторяющиеся символы
.
Напишите тестовую программу для проверки этой функции
,

которая воспроизводит следующий диалог с пользователем
:

Введите строку:
Эта строка содержит повторяющиеся символы

Строка без повторяющихся символов равна: Эта срокдежипвяющмлы

Подсказка:

Как и многие задачи программирования, эту задачу легче решить с по-

мощью процедурной абстракции.

Упражнение 4

С использованием двумерных массивов напишите функцию
(
и соответствую
-

щую тестовую программу
)
для умножения целочисленной матрицы размером
mxn
на

матрицу размером
nxr
.
В тестовой программе для задания значений
m
,
n
и
r
заведите

глобальные константы
.
Ниже приведен пример сообщений
,
выдаваемых программой
:

Введите первую матрицу (размер 2x2):

Введите 2 значения для 1-й строки (через пробелы):
3 4

Введите 2 значения для 2-й строки (через пробелы):
5 7

Введите вторую матрицу (размер 2x2):

Введите 2 значения для 1-й строки (через пробелы):
1 1

Введите 2 значения для 2-й строки (через пробелы):
2 2

3 4

5 7

УМНОЖИТЬ

1 1

2 2

РАВНО

11 11

19 19

ЛЕКЦИЯ 7. Указатели

1. Назначение указателей

Язык Си
++
унаследовал от языка Си мощные средства для работы с оператив
-

ной памятью
:
динамическое выделение и освобождение блоков памяти
,
доступ к от
-

дельным ячейкам памяти по их адресам
.
Эти возможности делают язык Си
++,
как и

Си
,
удобным для разработки системного программного обеспечения и прикладных

программ
,
в которых применяются динамические структуры данных
(
т
.
е
.
такие
,
раз
-

мер которых не известен на этапе компиляции и может меняться во время выполне
-

ния программы
).

Во всех программах из предыдущих лекций переменные объявлялись так
,
что

компилятор резервировал для каждой из них некоторое количество памяти
(
в соот
-

ветствии с типом данных
)
еще на этапе компиляции
.
В начале выполнения блока опе
-

раторов
,
внутри которого объявлена переменная
,
автоматически выполняется выде
-

ление памяти для этой переменной
,
а при выходе из блока
–
освобождение памяти
.

В данной лекции подробно рассматривается понятие
указателя

,
–
средства
,
ко
-

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

ния
/
освобождения памяти во время выполнения программ
.

1.1 Объявление указателей

Указателем называется адрес переменной в оперативной памяти
.
Переменная

указательного типа

(
часто она называется переменная
-
указатель или просто указа
-

тель
)
–
это переменная
,
размер которой достаточен для хранения адреса оперативной

памяти
.
Переменные
-
указатели объявляются с помощью символа
"
*
",
который добав
-

ляется после названия обычного типа данных
.
Например
,
оператор описания
(
его

можно прочитать как
"
указатель на целочисленную переменную
"):

int* number_ptr;

объявляет переменную
-
указатель
"
number_ptr
",
которая может хранить адреса пере
-

менных типа
"
int
".

Если в программе используется много однотипных указателей
,
то для их объ
-

явления можно ввести новый тип
.
Это делается с помощью оператора описания ново
-

го типа
"
typedef
".
Например
,
если записать оператор
:

typedef int* IntPtrType;

то в программе можно будет объявлять сразу несколько переменных
-
указателей
,
не

применяя для каждой из них символ
"
*
":

IntPtrType number_ptr1, number_ptr2, number_ptr3;

1.2 Применение символов "*" и "&" в операторах присваивания значений указателям

В операторах присваивания допускается совместное использование обычных и

указательных переменных одного типа
(
например
, "
int
").
Для получения значения

переменной по ее указателю предназначена операция
разыменования указателя

"
*
".
У

нее есть обратная операция
–
операция
взятия адреса

"
&
".
Упрощенно
,
операция
"
*
"

означает
"
получить значение переменной
,
расположенной по этому адресу
",
а опера
-

ция
"
&
"
–
"
получить адрес этой переменной
".
Для пояснения смысла этих операций

далее приводится программа
1.1.

#include <iostream.h>

typedef int* IntPtrType;

int main()

{

IntPtrType ptr_a, ptr_b;

int num_c = 4, num_d = 7;

ptr_a = &num_c; /* СТРОКА 10 */

ptr_b = ptr_a; /* СТРОКА 11 */

cout << *ptr_a << " " << *ptr_b << "\n";

ptr_b = &num_d; /* СТРОКА 13 */

cout << *ptr_a << " " << *ptr_b << "\n";

*ptr_a = *ptr_b; /* СТРОКА 15 */

cout << *ptr_a << " " << *ptr_b << "\n";

cout << num_c << " " << *&*&*&num_c << "\n";

return 0;

}

Программа 1.1.

Программа
1.1
выдает на экран следующие сообщения
:

4 4

4 7

7 7

Графически состояние программы
1.1
после выполнения операторов присваи
-

вания в
10-11-
й строках
, 15-
й и
19-
й показано
,
соответственно
,
на рис
. 1, 2
и
3.

Рис. 1.
.
Состояние про
-

граммы
1.1
после выпол
-

нения
10-
й и
11-
й строк
.

Рис. 2.
.
Состояние про
-

граммы
1.1
после выпол
-

нения
13-
й строки
.

Рис. 3.
.
Состояние про
-

граммы
1.1
после выпол
-

нения
15-
й строки
.

Операции
"
*
"
и
"
&
",
в некотором смысле
,
являются взаимно обратными
,
так что

выражение
"
*&*&*&num_c
"
означает то же самое
,
что и
"
num_c
".

1.3 Операторы "new" и "delete". Константа "NULL"

Рассмотрим оператор присваивания в
10-
й строке программы
1.1:

ptr_a = &num_c;

Можно считать
,
что после выполнения этого оператора у переменной
"
num_c
"

появляется еще одно имя
–
"
*ptr_a
".
Часто в программах бывает удобно пользоваться

переменными
,
у которых есть только такие имена
–
динамическими переменными

.
Не
-

зависимых имен у них нет
.
К динамическим переменным можно обращаться только

через указатели с помощью операции разыменования
(
например
, "
*ptr_a
"
и
"
*ptr_b
").

Динамические переменные
"
создаются
"
с помощью оператора распределения

динамической памяти
"
new
",
а
"
уничтожаются
" (
т
.
е
.
занимаемая ими память освобож
-

дается для дальнейшего использования
)
с помощью оператора
"
delete
".
Действие

этих операторов показано в программе
1.2 (
она очень похожа на программу
1.1).

#include <iostream.h>

typedef int* IntPtrType;

int main()

{

IntPtrType ptr_a, ptr_b; /* СТРОКА 7 */

ptr_a = new int; /* СТРОКА 9 */

*ptr_a = 4; /* СТРОКА 10 */

ptr_b = ptr_a; /* СТРОКА 11 */

cout << *ptr_a << " " << *ptr_b << "\n";

ptr_b = new int; /* СТРОКА 15 */

*ptr_b = 7; /* СТРОКА 16 */

cout << *ptr_a << " " << *ptr_b << "\n";

delete ptr_a;

ptr_a = ptr_b; /* СТРОКА 21 */

cout << *ptr_a << " " << *ptr_b << "\n";

delete ptr_a; /* СТРОКА 25 */

return 0;

}

Программа 1.2.

Программа
1.2
печатает на экране следующие сообщения
:

4 4

4 7

7 7

На рисунках
4-8
показаны состояния программы
1.2
после выполнения
7-
й
, 9-

11-
й
, 15-16-
й
, 21-
й и
25-
й строк
.

Рис. 4.
.
Состояние про
-

граммы
1.2
после выпол
-

нения
7-
й строки с описа
-

ниями переменных
.

Рис. 5.
.
Программа
1.2

после выполнения опера
-

торов присваивания в
9-
й
,

10-
й и
11-
й строках
.

Рис. 6.
.
Программа
1.2

после выполнения опера
-

торов присваивания в
15-

й и
16-
й строках
.

Рис. 7.
.
Программа
1.2
после

выполнения оператора присваи
-

вания в
21-
й строке
.

Рис. 8.
.
Программа
1.2
после вы
-

полнения оператора
"
delete
"
в

25-
й строке
.

Состояния на рис
. 4
и рис
. 8
похожи тем
,
что значения указателей
"
ptr_a
"
и

"
ptr_b
"
не определены
,
т
.
е
.
они указывают на несуществующие объекты
.
Обратите

внимание
,
что указатель
"
ptr_b
"
в конце программы оказывается в неопределенном

состоянии
,
хотя при вызове оператора
"
delete
"
этот указатель явно не передавался
.

Если указатель
"
ptr
"
указывает на несуществующий объект
,
то использование

в выражениях значения
"
*ptr
"
может привести в непредсказуемым
(
и часто катастро
-

фическим
)
результатам
.
К сожалению
,
в Си
++
нет встроенного механизма проверки

несуществующих указателей
.
Программист может сделать свои программы более

безопасными
,
если всегда будет стараться присваивать несуществующим указателям

нулевой адрес
(
символическое имя нулевого адреса
–
"
NULL
").
Для хранения перемен
-

ных в Си
++
нулевой адрес не используется
.

Константа
"
NULL
" (
целое число
0
)
описана в библиотечном заголовочном файле

"
stddef.h
".
Значение
"
NULL
"
можно присвоить любому указателю
.
Например
,
в про
-

грамме
1.3,
являющемся усовершенствованным вариантом программы
1.2,
для защи
-

ты от использования неопределенных указателей
"
*ptr_a
"
и
"
*ptr_b
"
были добавлены

следующие строки
:

#include <iostream.h>

#include <stddef.h>

...

delete ptr_a;

ptr_a = NULL;

delete ptr_b;

ptr_b = NULL;

...

if ( ptr_a != NULL )

{

*ptr_a = ...

...

Фрагмент программы 1.3.

В случае
,
если для создания динамической переменной не хватает свободной

оперативной памяти
,
то после вызова
"
new
"
Си
++
автоматически присвоит соответст
-

вующему указателю значение
"
NULL
".
В показанном ниже фрагменте программы
1.4

этот факт используется для организации типичной проверки успешного создания ди
-

намической переменной
.

#include <iostream.h>

#include <stdlib.h> /* "exit()" описана в файле stdlib.h */

#include <stddef.h>

...

ptr_a = new int;

if ( ptr_a == NULL )

{

cout << "Извините, недостаточно оперативной памяти";

exit(1);

}

...

Фрагмент программы 1.4.

Указатели можно передавать в качестве параметров функций
.
В программе
1.5

проверка на корректность указателя выполняется в отдельной функции
,
выполняю
-

щей создание динамической целочисленной переменной
:

void assign_new_int( IntPtrType& ptr )

{

ptr = new int;

if ( ptr == NULL )

{

cout << "Извините, недостаточно оперативной памяти";

exit(1);

}

Фрагмент программы 1.5.

2. Переменные типа "массив". Арифметические операции с указателями

В
6-
й лекции были рассмотрены массивы
–
наборы однотипных переменных
.
В

Си
++
понятия массива и указателя тесно связаны
.
Рассмотрим оператор описания
:

int hours[6];

Этот массив состоит из
6-
ти элементов
:

hours[0] hours[1] hours[2] hours[3] hours[4] hours[5]

Массивы в Си
++
реализованы так
,
как будто имя массива
(
например
, "
hours
")

является указателем
.
Поэтому
,
если добавить в программу объявление целочисленно
-

го указателя
:

int* ptr;

то ему можно присвоить адрес массива
(
т
.
е
.
адрес первого элемента массива
):

ptr = hours;

После выполнения этого оператора обе переменные
–
"
ptr
"
и
"
hours
"
–
будут

указывать на целочисленную переменную
,
доступную в программе как
"
hours[0]
".

Фактически
,
имена
"
hours[0]
", "
*hours
"
и
"
*ptr
"
являются тремя различными

именами одной и той же переменной
.
У переменных
"
hours[1]
", "
hours[2]
"
и т
.
д
.

также появляются новые имена
:

*(hours + 1) *(hours + 2) ...

или

*(ptr + 1) *(ptr + 2) ...

В данном случае
"
+2
"
означает
"
добавить к адресу указателя смещение
,
соот
-

ветствующее
2-
м целым значениям
".
Из арифметических операций к указателям часто

применяется сложение и вычитание
(
в том числе операции инкремента и декремента

"
++
"
и
"
--
"),
а умножение и деление не используются
.
Значения однотипных указате
-

лей можно вычитать друг из друга
.

Главное
,
что нужно запомнить относительно сложения и вычитания значений

из указателя
–
в выражениях Си
++
указывается не число
,
которое нужно вычесть
(
или

добавить
)
из адреса
,
а количество переменных заданного типа
,
на которые нужно

"
сместить
"
адрес
.

Арифметические выражения с указателями иногда позволяют более кратко за
-

писать обработку массивов
.
В качестве примера см
.
функцию для преобразования

английской строки в верхний регистр
(
фрагмент программы
2.1).

void ChangeToUpperCase( char phrase[] )

{

int index = 0;

while ( phrase[index] != '\0' )

{

if ( LowerCase(phrase[index]) )

ChangeToUpperCase( phrase[index] );

index++;

}

bool LowerCase( char character )

{

return ( character >= 'a' && character <= 'z');

}

void ChangeToUpperCase( char& character )

{

character += 'A' - 'a';

}

Фрагмент программы 2.1.

Обратите внимание на полиморфизм функции
"
ChangeToUpperCase(...)
"
–
при

обработке вызова компилятор различает две перегруженных функции
,
т
.
к
.
у них раз
-

ные параметры
(
у одной
–
параметр типа
"
char
",
а у другой
–
параметр типа
"
сим
-

вольный массив
").
Имя массива
"
phrase
"
является переменной
-
указателем
,
поэтому

функцию с параметром
-
массивом можно переписать короче
,
если использовать

арифметические выражения с указателями
:

void ChangeToUpperCase( char* phrase )

{

while ( *phrase != '\0' )

{

if ( LowerCase(*phrase) )

ChangeToUpperCase(*phrase);

phrase++;

}

Фрагмент программы 2.2.

Эта модификация функции не влияет на остальные части программы
–
вызовы

вариантов функций с параметром
-
указателем или параметром
-
массивом записывают
-

ся одинаково
,
например
:

char a_string[] = "Hello World";

...

ChangeToUpperCase( a_string );

3. Динамические массивы

Правила создания и уничтожения динамических переменных типов
"
int
",

"
char
", "
double
"
и т
.
п
. (
см
.
п
.1.3)
распространяются и на динамические массивы
.
По

отношению к массивам динамическое распределение памяти особенно полезно
,
по
-

скольку иногда бывают массивы больших размеров
.

Динамический массив из
10-
ти целых чисел можно создать следующим обра
-

зом
:

int* number_ptr;

number_ptr = new int[10];

Переменные
-
массивы в Си
++
являются указателям
,
поэтому к
10-
ти элементам

динамического массива допускается обращение
:

number_ptr[0] number_ptr[1] ... number_ptr[9]

или
:

number_ptr *(number_ptr + 1) ... *(number_ptr + 9)

Для уничтожения динамического массива применяется оператор
"
delete
" c

квадратными скобками
"
[]
":

delete[] number_ptr;

Скобки
"
[]
"
играют важную роль
.
Они сообщают оператору
,
что требуется

уничтожить все элементы массива
,
а не только первый
.

Работа с динамическими массивами показана в программе
3.1.
В приведенном

фрагменте программы у пользователя запрашивается список целых чисел
,
затем вы
-

числяется и выводится на экран их среднее значение
.

...

int no_of_integers, *number_ptr;

cout << "Введите количество целых чисел в списке: ";

cin >> no_of_integers;

number_ptr = new int[no_of_integers];

if ( number_ptr == NULL )

{

cout << "Извините, недостаточно памяти.\n";

exit(1);

}

cout << "Наберите " << no_of_integers;

cout << " целых чисел, разделяя их пробелами:\n";

for ( int count = 0; count < no_of_integers; count++ )

cin >> number_ptr[count];

cout << "Среднее значение: ";

cout << average( number_ptr, no_of_integers );

delete[] number_ptr;

...

Фрагмент программы 3.1.

Динамические массивы
,
как и обычные
,
можно передавать в качестве парамет
-

ров функций
.
Поэтому в программе
3.1
без изменений будет работать функция

"
average()
"
из предыдущей лекции
(
лекция
6,
п
. 2).

4. Автоматические и динамические переменные

В некоторых случаях без динамических переменных не удается обойтись
,
но их

количество можно уменьшить за счет тщательного проектирования структуры про
-

граммы и применения процедурной абстракции
.
Большинство переменных в про
-

граммах из предыдущих лекций являются
автоматическими

переменными
.
Они ав
-

томатически создаются
,
когда начинает выполнятся блок
(
или функция
),
где эти пе
-

ременные объявлены
.
При выходе из блока
(
или функции
)
переменные автоматически

уничтожаются
.
Поэтому в хорошо структурированной программе не слишком много

операторов для создания и уничтожения переменных
.

(
ПРИМЕЧАНИЕ.

В Си
++,
кроме автоматических и динамических
,
существуют
статические

пере
-

менные
.
Для объявления статической переменной в ее операторе описания надо перед названием ти
-

па данных добавить служебное слово
"
static
".
Статические переменные существуют в течение все
-

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

константы
,
которые объявляются в заголовочных файлах или в начале исходных файлов
.)

5. Связные списки

В этом параграфе кратко рассматривается одна из разновидностей
абстракт-

ных типов данных

(abstract data type, ADT)
–
связный список

.
Связный список интере
-

сен тем
,
что при его реализации применяются указатели
.
О других абстрактных типах

данных более подробно будет говориться в последующих лекциях
.

Связный список состоит из
узлов

.
В каждом узле хранятся некоторые данные и

указатель на следующий узел списка
(
рис
. 9).
В программе
,
работающей со списком
,

обычно есть еще один отдельный указатель
,
ссылающийся на первый узел списка

("
pointer
"
на рис
. 9).
В указатель последнего узла принято записывать значение

"
NULL
".

Размер связных списков
,
в отличие от массивов
,
можно изменять динамически

(
во время выполнения программы можно добавлять
/
удалять отдельные узлы в любом

месте списка
).

Рис. 9.
.
Структура связного списка
.

Далее будем рассматривать реализацию на Си
++
связного списка для хранения

символьных строк
.
Сначала определим на Си
++,
из чего состоит
"
узел
"
нашего спи
-

ска
.
Для этого надо объединить строку и указатель в тип данных
"
узел
".
Это делается

с помощью оператора описания
структуры

.
Оператор
"
struct
"
позволяет создать

новый тип данных
,
в отличие от оператора
"
typedef
",
который
,
по существу
,
предна
-

значен для присвоения нового имени уже существующему типу данных
.

Структура
–
это набор разнотипных переменных
(
в противоположность масси
-

ву
,
состоящему из элементов одного типа
).
Применительно к нашей задаче
,
тип
"
node
"

–
это структура
,
состоящая из символьного массива размером

MAX_WORD_LENGTH
и указателя на такую же структуру
:

struct node

{

char word[MAX_WORD_LENGTH];

node* ptr_to_next_node;

};

Обратите внимание на точку с запятой после закрывающей фигурной скоб
-

ки
"
}
".
Слово
"
struct
"
является служебным словом Си
++ (
это аналог
"
record
"
в Пас
-

кале
).
Возможно описание узла с применением нового типа данных
"
указатель на

узел
":

struct node;

typedef node* node_ptr;

struct node

{

char word[MAX_WORD_LENGTH];

node_ptr ptr_to_next_node;

};

В строке
"
struct node;
"
имя
"
node
"
является пустым описанием
.
Оно напоми
-

нает прототип
(
описание
)
функции
–
детали структуры
"
node
"
определяются в после
-

дующих строках
.
Пустое определение позволяет в следующей строке с помощью опе
-

ратора
"
typedef
"
объявить новый тип данных
"
указатель на структуру
node
".

5.1 Операторы "." и "->"

После определения структуры
"
node
(
узел
)"
в программе можно объявлять пе
-

ременные этого типа
:

node my_node, my_next_node;

Для доступа к полям
(
внутренним переменным
)
структуры
"
my_node
"
надо

пользоваться оператором
"
.
" (
точка
):

cin >> my_node.word;

my_node.ptr_to_next_node = &my_next_node;

Допустим
,
что в программе были объявлены указатели на узлы
,
а сами узлы

списка были созданы динамически
:

node_ptr my_node_ptr, another_node_ptr;

my_node_ptr = new node;

another_node_ptr = new node;

В таком случае для доступа к полям узлов можно пользоваться совместно опе
-

раторами
"
звездочка
"
и
"
точка
":

cin >> (*my_node_ptr).word;

(*my_node_ptr).ptr_to_next_node = another_node_ptr;

Более кратко эти выражения записываются с помощью специального операто
-

ра
"
->
",
который предназначен для доступа к полям структуры через указатель
:

cin >> my_node_ptr->word;

my_node_ptr->ptr_to_next_node = &my_next_node;

Другими словами
,
имена
"
my_node_ptr->word
"
и
"
(*my_node_ptr).word
"
обозна
-

чают одно и то же
–
поле
"
word
"
структуры типа
"
node
",
на которую ссылается указа
-

тель
"
my_node_ptr
".

5.2 Создание связного списка

Ниже приведена функция создания связного списка для хранения символьных

строк
,
которые пользователь вводит с клавиатуры
.
Указатель
"
a_list
"
ссылается на

первый узел нового списка
(
на
"
голову
"
списка
).
Для завершения ввода данных поль
-

зователь должен ввести специальный завершающий символ
(
точку
).

void assign_list( node_ptr& a_list )

{

node_ptr current_node, last_node;

assign_new_node( a_list );

cout <<
"Введите первое слово";

cout << "(или '.' для завершения списка): ";

cin >> a_list->word;

if ( !strcmp( ".", a_list->word ) )

{

delete a_list;

a_list = NULL;

}

current_node = a_list; /* СТРОКА 13 */

while ( current_node != NULL )

{

assign_new_node( last_node );

cout << "Введите следующее слово";

cout << "(или '.' для завершения списка): ";

cin >> last_node->word;

if ( !strcmp( ".", last_node->word ) )

{

delete last_node;

last_node = NULL;

}

current_node->ptr_to_next_node = last_node;

current_node = last_node;

}

Фрагмент программы 5.1.

Функция
"
assign_new_node(...)
"
для создания нового узла аналогична

функции
"
assign_new_int(...)
"
из программы
1.5.

Порядок действий функции
"
assign_list(...)
"
поясняется на рис
. 10-16.
На

рис
. 10
показано состояние программы после выполнения вызова
:

assign_new_node( a_list );

Рис. 10.
.
Состояние программы
5.1
после создания нового списка
.

Предположим
,
что пользователь напечатал слово
"
мой
".
Тогда после
13-
й стро
-

ки программа окажется в состоянии
,
показанном на рис
. 11.

Рис. 11.
.
Состояние программы после заполнения данными первого узла
.

После первой строки в теле цикла
"
while
"
программа перейдет в состояние
,

показанное на рис
. 12.

Рис. 12.
.
В хвост списка был добавлен новый узел
.

Далее
,
если пользователь напечатал слово
"
список
",
то после итерации цикла

"
while
"
программа будет в состоянии
,
как на рис
. 13.

Рис
____________
. 13.
Последний узел списка заполнен данными и в предыдущий узел по
-

мещен соответствующий указатель
.

После выполнения первой строки во второй итерации цикла
"
while
"
состояние

программы см
.
рис
. 14.

Рис. 14.
.
В хвост списка был добавлен новый узел
.

Допустим
,
в ответ на следующий запрос пользователь напечатает
"
.
".
Тогда

после завершения цикла
"
while
"
программа будет в состоянии
,
как на рис
. 15.

Рис. 15.
.
Был удален последний узел списка
.

Символ
"
.
"
сигнализирует о том
,
что пользователь захотел прекратить ввод

данных для списка
.
Поэтому функция
"
assign_list(...)
"
завершается и при выходе

из нее автоматически уничтожаются локальные переменные
-
указатели
"
current_node
"

и
"
last_node
" (
которые были объявлены в теле функции
).
После возврата из функции

состояние программы будет таким
,
как на рис
. 16.

Рис. 16.
.
Состояние программы
5.1
после выхода из функции ввода списка с

клавиатуры
.

5.3 Печать связного списка

Напечатать содержимое связного списка на экране несложно
.
Ниже приведена

функция для печати строк
,
хранящихся в узлах списка
:

void print_list( node_ptr a_list )

{

while ( a_list != NULL )

{

cout << a_list->word << " ";

a_list = a_list->ptr_to_next_node;

}

Фрагмент программы 5.1.

6. Сводка результатов

В лекции описаны способы динамического распределения оперативной памяти

и работа с динамическими переменными с помощью указателей
.
В Си
++
имена мас
-

сивов можно рассматривать как указатели
.
Поэтому массивы можно создавать и

уничтожать динамически
.
В выражениях с указателями можно применять арифмети
-

ческие операции сложения и вычитания
.
В конце лекции кратко рассмотрены основ
-

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

данных с помощью указателей
.

7. Упражнения

Упражнение 1

Не запуская приведенную далее программу
,
определите
,
какие сообщения она

выводит на экран
.
Для проверки своего ответа запустите программу
.

#include <iostream.h>

#include <stddef.h>

typedef int* IntPtrType;

int main()

{

IntPtrType ptr_a, ptr_b, *ptr_c;

ptr_a = new int;

*ptr_a = 3;

ptr_b = ptr_a;

cout << *ptr_a << " " << *ptr_b << "\n";

ptr_b = new int;

*ptr_b = 9;

cout << *ptr_a << " " << *ptr_b << "\n";

*ptr_b = *ptr_a;

cout << *ptr_a << " " << *ptr_b << "\n";

delete ptr_a;

ptr_a = ptr_b;

cout << *ptr_a << " " << *&*&*&*&*ptr_b << "\n";

ptr_c = &ptr_a;

cout << *ptr_c << " " << **ptr_c << "\n";

delete ptr_a;

ptr_a = NULL;

return 0;

}

Упражнение 2

Напишите логическую функцию с двумя параметрами
-
строками
.
Функция

должна возвращать
"
true
",
если ее первый параметр
-
строка по алфавиту расположе
-

на раньше
,
чем вторая строка
.
В противном случае функция должна возвращать

"
false
".
Можете считать
,
что обе строки содержат только строчные буквы
,
и в них

нет ни пробелов
,
ни служебных символов
.
Проверьте работу функции с помощью

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

арифметических выражений с указателями
.
Убедитесь
,
что функция работает так же
,

как и первый вариант
.

Упражнение 3

В программу
5.1
добавьте
3
новых функции и измените программу так
,
чтобы

проверить их действие
.

•
Функция

void add_after(node_ptr& list, char a_word[], char word_after[])

Вставляет в связный список
"
list
"
после первого встретившегося узла со

словом
"
a_word
"
новый узел со словом
"
word_after
".
Если в списке
"
list
"

нет узла со словом
"
a_word
",
то функция не должна модифицировать спи
-

сок
.

•
Функция

void delete_node(node_ptr& a_list, char a_word[])

Удаляет в связном списке
"
a_list
"
первый встретившийся узел

со словом
"
a_word
".

•
Функция

void list_selection_sort(node_ptr& a_list)

Выполняет сортировку узлов списка в алфавитном порядке
(
см
.
Упражне
-

ние
2).

Пример экранного ввода
/
вывода текстовой программы в типичном сеансе работы
:

Введите первое слово (или '.' для завершения списка):
это

Введите следующее слово (или '.' для завершения списка):
тестовое

Введите следующее слово (или '.' для завершения списка):
сообщение

Введите следующее слово (или '.' для завершения списка):
из

Введите следующее слово (или '.' для завершения списка):
нескольких

Введите следующее слово (или '.' для завершения списка):
слов

Введите следующее слово (или '.' для завершения списка):
на

Введите следующее слово (или '.' для завершения списка):
русском

Введите следующее слово (или '.' для завершения списка):
языке

Введите следующее слово (или '.' для завершения списка):
.

ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:

это тестовое сообщение из нескольких слов на русском языке

ПОСЛЕ КАКОГО СЛОВА ВЫ ХОТИТЕ ВСТАВИТЬ НОВОЕ СЛОВО? это

КАКОЕ СЛОВО ВЫ ХОТИТЕ ВСТАВИТЬ? небольшое

ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:

это небольшое тестовое сообщение из нескольких слов на русском языке

КАКОЕ СЛОВО ВЫ ХОТИТЕ УДАЛИТЬ? тестовое

ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:

это небольшое сообщение из нескольких слов на русском языке

СОДЕРЖИМОЕ СПИСКА ПОСЛЕ СОРТИРОВКИ:

из на небольшое нескольких русском слов сообщение это языке

Подсказки.

Основные черты алгоритма добавления нового узла заключаются в сле-

дующем:

1) Для поиска и запоминания узла, после которого надо вставить новый

узел, применяется дополнительный указатель.

2) Для создания нового узла применяется еще один дополнительный указа-

тель.

3) После выполнения действий 1) и 2) следует модифицировать соответ-

ствующие указатели.

Возможный алгоритм удаления узла:

1) Заведите дополнительный указатель на узел перед удаляемым узлом и указатель

на удаляемый узел.

2) Измените указатель внутри узла, расположенном до удаляемого узла, так, чтобы

он указывал на узел, расположенный после удаляемого.

3) Удалите лишний узел.

Для сортировки связного списка несложно адаптировать алгоритм сортиров-

ки массива из 6-й лекции.

ЛЕКЦИЯ 8. Рекурсия

1. Понятие рекурсии

В хорошо спроектированной программе на Си
++
в определениях функций час
-

то встречаются вызовы других функций этой же программы или библиотеки Си
++.

Например
,
в предыдущей
(7-
й
)
лекции
,
в определении функции
"
assign_list(...)
"

есть вызов
"
assign_new_node(...)
".
Если в определении функции содержится вызов ее

самой
,
то такая функция называется
рекурсивной

.

Понятие рекурсии хорошо известно в математике и логике
.
Например
,
можно

привести следующее рекурсивное определение натуральных чисел
:

•
1
является натуральным числом

•
целое число
,
следующее за натуральным
,
есть натуральное число
.

В данном контексте понятие рекурсии тесно связано с понятием
математиче-

ской индукции

.
Обратите внимание
,
что в приведенном определении натуральных чи
-

сел есть нерекурсивная часть
(
базовое утверждение о том
,
что
1
является натураль
-

ным числом
).

Еще одним известным примером рекурсивного определения является опреде
-

ление функции факториала
"!"
для неотрицательных целых чисел
:

•
0! = 1

•
если
n>0
,
то
n! = n*(n-1)!

В этом определении факториала
"
!
"
есть базовое утверждение
(
определение
0!)

и рекурсивная часть
.
Согласно определению
,
факториал
6
вычисляется следующим

образом
:

6! = 6*5! = 6*5*4! = 6*5*4*3! = 6*5*4*3*2! = 6*5*4*3*2*1! = 6*5*4*3*2*1*1 = 720

2. Простой пример рекурсии

Рассмотрим рекурсивную функцию
"
print_backwards()
"
из программы
2.1.
Эта

функция предназначена для ввода с клавиатуры последовательности символов
.
Для

прекращения ввода пользователь должен напечатать специальный символ
(
точку
).

После этого функция печатает введенные символы в обратном порядке
.

#include<iostream.h>

void print_backwards();

int main()

{

print_backwards();

cout << "\n";

return 0;

}

void print_backwards()

{

char character;

cout << "Введите символ (или '.' для завершения ввода): ";

cin >> character;

if ( character != '.' )

{

print_backwards();

cout << character;

}

Программа 2.1.

Программа
2.1
печатает на экране подобные сообщения
:

Введите символ (или '.' для завершения ввода):
H

Введите символ (или '.' для завершения ввода):
i

Введите символ (или '.' для завершения ввода):
.

Порядок выполнения функции
"
print_backwards()
"
подробно описан в сле
-

дующем параграфе
.
Пока обратите внимание на то
,
что вызов
"
print_backwards()
" (
в

ее собственном определении
)
находится внутри оператора
"
if
".

В определениях рекурсивных функций обычно есть некоторый оператор ветв
-

ления
,
у которого
,
как минимум
,
одна нерекурсивная ветвь
,
реализующая
"
базовое

утверждение
"
определения функции
.
Если такой ветви нет
,
то функция будет вызы
-

вать себя бесконечно
(
в действительности
,
до тех пор
,
пока не будет занята вся па
-

мять
).

В программе
2.1
базовое утверждение реализовано неявно
–
это возврат из

функции
,
если был введен символ
"
.
" (
точка
).

3. Как выполняется рекурсивный вызов

Порядок выполнения программы
2.1
легко понять с помощью нескольких схем
.

Главная функция начинается с вызова
"
print_backwards()
".
Для выполнения вы
-

зова функции в памяти компьютера выделяется некоторое количество памяти
(
необ
-

ходимое для запоминания адреса возврата
,
для создания копий параметров по значе
-

нию и для передачи параметров
-
указателей
).
Свободная область памяти в момент

первого вызова
"
print_backwards()
"
на рис
. 1
изображена в виде пустого прямо
-

угольника
.
Внутри прямоугольника показано содержимое экрана в соответствующие

моменты времени
(
на схемах считается
,
что направление
"
сверху
-
вниз
"
соответствует

увеличению времени
,
прошедшему с момента запуска программы
).

Рис. 1.
.
Свободная область памяти перед

первым вызовом
"
print_backwards()
"

Рис. 2.
Свободная область памяти перед

вторым вызовом
"
print_backwards()
"
.

Выполнение функции
"
print_backwards()
"
начинается со ввода символа
,
а за
-

тем происходит второй вызов
"
print_backwards()
" (
в этот момент программа еще не

начинала обратную печать символов
).
Для второго вызова также выделяется некото
-

рое количество памяти
,
поэтому объем свободной памяти уменьшается
(
рис
. 2).

Далее процесс повторяется
,
но
,
допустим
,
при третьем вызове

"
print_backwards()
"
пользователь ввел завершающий символ
(
точку
).
Поэтому после

третьего вызова происходит возврат в вызывающую функцию
(
т
.
е
.
во второй экземп
-

ляр
"
print_backwards()
"),
см
.
рис
. 3.

Рис. 3.
Возврат из
3-
го экземпляра функции

"
print_backwards()
"
во второй
.

Рис. 4.
.
Завершение выполнения программы
.

Второй экземпляр
"
print_backwards()
"
завершается
,
но перед завершением вы
-

водит на экран символ
"
i
".
В свою очередь
,
первый экземпляр функции перед завер
-

шением работы напечатает на экране символ
"
H
" (
рис
. 4).

Для организации вызовов функций и создания автоматических переменных в

программах на Си
++
отводится специальная область памяти
–
стек

.
Память
,
необхо
-

димая для очередного вызова функции
,
выделяется в верхней части стека
(
в старших

адресах
).
При завершении функции размер стека уменьшается на соответствующую

величину
.
Изменение состояния программного стека для рассмотренного выше при
-

мера показано на рис
. 5.

Рис. 5.
.
Последовательность состояний стека программы
2.1
применительно к

тестовому примеру
.

Стек в программах на Си
++
используется при вызове всех функций
,
а не только

рекурсивных
.
Стек
,
как и связный список
,
является одной из разновидностей абст
-

рактных типов данных
.
Характерная особенность стека
–
соответствие принципу
"
по
-

следним прибыл
–
первым обслужен
" (
в отличие от стека
,
очередь

является примером

абстрактного типа данных
,
действующего по принципу
"
последним прибыл
–
послед
-

ним обслужен
").

4. Еще три примера рекурсии

В этом параграфе приводятся три примера рекурсивных функций
.
В
3-
й лекции

рассматривалась функция для вычисления факториала целого положительного числа

(
лекция
3,
программа
3.1).
Ниже приведен рекурсивный аналог этой функции
:

int factorial( int number )

{

if ( number < 0 )

{

cout << "\nОшибка - отрицательный аргумент факториала\n";

exit(1);

}

else if ( number == 0 )

return 1;

return number*factorial( number - 1 );

}

Фрагмент программы 4.1.

В качестве второго примера
(
фрагмент программы
4.2)
дана функция
,
возводя
-

щая свой первый параметр
(
типа
"
double
")
в степень с показателем
,
который переда
-

ется в качестве второго параметра
(
неотрицательное целое число
).

double raised_to_power( double number, int power )

{

if ( power < 0 )

{

cout << "\nОшибка - отрицательный показатель степени\n";

exit(1);

}

else if ( power == 0 )

return 1.0;

return number*raised_to_power( number, power - 1 );

}

Фрагмент программы 4.2.

В рекурсивных функциях из программ
4.1
и
4.2
особое внимание уделено за
-

щите от
"
бесконечного вызова
".
Эта защита основана на проверке параметров
,
обес
-

печивающей выполнение вычислений только для корректных значений переданных

параметров
.
Т
.
о
.
гарантируется
,
что будут произведены корректные вычисления и в

конечном счете произойдет возврат из функции
.
При недопустимых значениях пара
-

метров выдается сообщение об ошибке и выполняется возврат из функций или завер
-

шение работы программы
.

Третий пример
(
фрагмент программы
4.3)
–
это рекурсивная функция для вы
-

числения суммы первых
n
элементов целочисленного массива
"
a[]
".

int sum_of( int a[], int n )

{

if ( n < 1 || n > MAXIMUM_NO_OF_ELEMENTS )

{

cout << "\nОшибка - допускается суммирование от 1 до ";

cout << MAXIMUM_NO_OF_ELEMENTS << " элементов\n";

exit(1);

}

else if ( n == 1 )

return a[0];

return a[n-1]+sum_of( a, n-1 );

}

Фрагмент программы 4.3.

5. Рекурсия и циклы

При программировании на Си
++
рекурсию применять совсем не обязательно
,
и

на практике она используется довольно редко
.
Любую рекурсивную функцию можно

реализовать итеративно
,
т
.
е
.
с помощью циклов
"
for
", "
while
"
или
"
do...while
".
В

некотором смысле
,
какое определение функции выбрать
(
рекурсивное или итераци
-

онное
)
–
вопрос пристрастий программиста
.
Исходный текст рекурсивных функций

иногда легче для понимания
,
но итерационные функции практически всегда работают

быстрее
.
Далее приводятся итерационные аналоги двух рекурсивных функций
,
кото
-

рые ранее рассматривались в данной лекции
.

void print_backwards()

{

char chars[MAX_ARRAY_LENGTH];

int no_of_chars_input = 0;

do {

cout << "Введите символ (или '.' для завершения ввода): ";

cin >> chars[no_of_chars_input];

no_of_chars_input++;

} while ( chars[no_of_chars_input - 1] != '.'

&& no_of_chars_input < MAX_ARRAY_LENGTH );

for ( int count = no_of_chars_input - 2; count >= 0; count-- )

cout << chars[count];

}

Фрагмент программы 2.1b.

int factorial( int number )

{

int product = 1;

if ( number < 0 )

{

cout
<< "\nОшибка - отрицательный аргумент факториала\n";

exit(1);

}

else if ( number == 0 )

return 1;

for ( ; number > 0; number-- )

product *= number;

return product;

}

Фрагмент программы 4.1b.

Конечно
,
вопрос о том
,
какая реализация конкретной функции более понятна
,

довольно спорный
.
Обычно в итерационную функцию приходится включать больше

локальных переменных
,
например
,
в первом примере был добавлен массив

"
chars[MAX_ARRAY_LENGTH]
",
а во втором примере
–
целочисленная переменная

"
product
".
Другими словами
,
в итеративных функциях память тратится на локальные

переменные
,
а рекурсивных функциях
–
на организацию вызовов
.

6. Рекурсия в структурах данных

На практике рекурсия чаще встречается в структурных типах данных
,
а не в

функциях
.
Рекурсивная структура данных уже использовалась в предыдущей лекции

для определения узла связного списка
.
В структуре
"
узел
"
хранится указатель струк
-

туру такого же типа
:

struct node

{

char word[MAX_WORD_LENGTH];

node *ptr_to_next_node;

};

В последующих лекциях будут более подробно рассматриваться другие приме
-

ры рекурсивных структур данных и особенности их описания на Си
++.

7. Рекурсивная реализация алгоритма быстрой сортировки

В завершающей части этой лекции кратко рассмотрим известный пример ре
-

курсивного алгоритма
–
алгоритм быстрой сортировки
QuickSort

.
Этот рекурсивно

определенный алгоритм предназначен для упорядочения значений
,
хранящихся в

массиве
,
по возрастанию или по убыванию
.

Предположим
,
что
11
элементов массива имеют следующие значения
(
рис
. 6).

Рис. 6.
.
Начальное состояние массива
.

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

две части и переупорядочении элементов в этих частях
.
Разбиение выполняется путем

выбора некоторого элемента
,
который будем называть
граничным

.
После разбиения

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

меньшие или равные граничному элементу
,
а в другой части
–
только большие или

равные
.

Например
,
если выбрать в качестве граничного элемента значение
8,
то после

переупорядочения массив окажется в состоянии
,
показанном на рис
. 7.
Затем тот же

самый процесс независимо выполняется для левой и правой частей массива
.

Рис. 7.
.
Массив после разделения на две части и переупорядочения элементов в них
.

Процесс разбиения и переупорядочения частей массива можно реализовать ре
-

курсивно
.
Индекс граничного элемента вычисляется как индекс среднего элемента
:

(first + last)/2

где
"
first
"
и
"
last
"
являются индексами первого и последнего элементов обрабаты
-

ваемой части массива
.

Далее подробно рассматривается процедура переупорядочения элементов мас
-

сива
.

Индексы
"
left_arrow
"
и
"
right_arrow
"
определим как индексы крайних элемен
-

тов обрабатываемой части массива
(
которая подвергается разбиению
,
см
.
рис
. 8).

Рис. 8.
.
Значения индексов
"
left_arrow
"
и
"
right_arrow
"
перед нача
-

лом процедуры переупорядочения
.

В процессе переупорядочения индексы
"
left_arrow
"
и
"
right_arrow
"
смещают
-

ся в направлении граничного элемента
.
Так
, "
right_arrow
"
перемещается влево
,
пока

значение элемента не окажется меньше или равно граничному значению
(
рис
. 9).

Рис. 9.
.
Обнаружение левого и правого элементов для обмена
.

Аналогично
, "
left_arrow
"
смещается вправо
,
пока не встретится элемент
,

больший или равный граничному
.
В нашем примере этот элемент расположен в нача
-

ле массива
(
рис
. 9).
Теперь значения двух найденных элементов массива меняются

местами
(
рис
. 10).

Рис. 10.
.
Состояние массива после обмена двух элементов
.

После обмена двух элементов
"
right_arrow
"
продолжает смещаться влево
.

Смещение прекращается
,
когда находится очередной элемент
,
меньший или равный

граничному
(
рис
. 11).

Рис. 11.
.
Справа обнаружен элемент для обмена
.

Индекс
"
left_arrow
"
смещается вправо
,
пока не встретится элемент
,
требую
-

щий перестановки
(
рис
. 12).

Рис. 12.
.
Слева обнаружен элемент для обмена
.

Значения найденных элементов меняются местами
(
рис
. 13).

Рис. 13.
.
Состояние массива после обмена второй пары элементов
.

Переупорядочение частей массива прекращается после выполнения условия

"
left_arrow > right_arrow
".
В состоянии на рис
. 13
это условия ложно
,
поэтому

"
right_arrow
"
продолжает смещаться влево
,
пока не окажется в положении
,
показан
-

ном на рис
. 14.

Рис. 14.
.
Справа обнаружен элемент для обмена
.

Перемещение
"
left_arrow
"
приведет к состоянию
,
показанному на рис
. 15.
По
-

скольку при перемещении вправо надо найти элемент
,
больший или равный
"
pivot
",

то
"
left_arrow
"
прекращает перемещение после достижения граничного элемента
.

Рис. 15.
.
Левый элемент для обмена совпадает с граничным
.

Теперь выполняется обмен
,
включающий граничный элемент
(
такой обмен до
-

пустим
),
и массив переходит в состояние
,
показанное на рис
. 16.

Рис. 16.
.
Состояние массива после обмена третьей пары элементов
.

После обмена элементов
"
right_arrow
"
перемещается влево
,
а
"
left_arrow
"
–

вправо
(
рис
. 17).

Рис. 17.
.
Переупорядочение прекращается после прохождения индексами се
-

редины массива
.

В состоянии
,
показанном на рис
. 17,
становится истинным условие завершения

процедуры переупорядочения
"
left_arrow > right_arrow
".
Поэтому первую процеду
-

ру разбиения и переупорядочения массива можно считать выполненной
.

Ниже приведена функция на Си
++,
в которой рекурсивно реализован алгоритм

сортировки
QuickSort:

void quick_sort( int list[], int left, int right )

{

int pivot, left_arrow, right_arrow;

left_arrow = left;

right_arrow = right;

pivot = list[(left + right)/2];

do {

while ( list[right_arrow] > pivot )

right_arrow--;

while ( list[left_arrow] < pivot )

left_arrow++;

if ( left_arrow <= right_arrow )

{

swap( list[left_arrow], list[right_arrow] );

left_arrow++;

right_arrow--;

}

} while ( right_arrow >= left_arrow );

if ( left < right_arrow )

quick_sort( list, left, right_arrow );

if ( left_arrow < right )

quick_sort( list, left_arrow, right );

}

Программа 7.1.

8. Сводка результатов

На Си
++
можно писать рекурсивные функции
.
В лекции кратко описан порядок

выполнения рекурсивных функций и назначение стека
.
Для любой рекурсивной

функции можно разработать итерационный аналог
.
В лекции указаны преимущества

и недостатки рекурсивной реализации
.
В качестве примера приведен известный алго
-

ритм быстрой сортировки
QuickSort
и его рекурсивная реализация на Си
++.

9. Упражнения

Упражнение 1

Последовательность чисел Фибоначчи может быть определена следующим образом
:

•
a

(1) = 1

•
a

(2) = 1

•
для всех
n

>2
a

(
n

) =
a

(
n

-1) +
a

(
n

-2)

Это определение позволяет сгенерировать такую последовательность
:

1
,

1
,

2
,

3
,

5
,

8
,

13
,

21
,

...

Напишите на Си
++
функцию
"
fibonacci(...)
",
которая вычисляет числа Фи
-

боначчи по их порядковому номеру
,
например
,
fibonacci(7)==13
.

Упражнение 2

Для выполнения этого упражнения используйте программу
5.1
из
7-
й лекции
.

а
)
Напишите две рекурсивных функции
"
print_list_forwards(...)
"
и

"
print_list_backwards(...)
",
которые должны печатать на экране содержимое

связного списка
,
рассмотренного в
7-
й лекции
,
соответственного
_______в прямом и

обратном порядке
. (
Функция
"
print_list_forwards(...)
"
должна вести себя

точно так же
,
как и функция
"
print_list(...)
"
из
7-
й лекции
).
Измените про
-

грамму
5.1
из
7-
й лекции так
,
чтобы проверить свои функции
.
Ваша программа

должна выдавать на экран следующие сообщения
:

Введите первое слово (или '.' для завершения списка):
это

Введите следующее слово (или '.' для завершения списка):
короткое

Введите следующее слово (или '.' для завершения списка):
тестовое

Введите следующее слово (или '.' для завершения списка):
сообщение

Введите следующее слово (или '.' для завершения списка):
.

ПЕЧАТЬ СОДЕРЖИМОГО СПИСКА В ПРЯМОМ ПОРЯДКЕ:

это короткое тестовое сообщение

ПЕЧАТЬ СОДЕРЖИМОГО СПИСКА В ОБРАТНОМ ПОРЯДКЕ:

сообщение тестовое короткое это

Подсказка:

при разработке функции "

print_list_backwards()
" еще раз посмотрите

на программу 2.1.

б
)
Напишите и протестируйте итерационный
(
т
.
е
.
нерекурсивный
)
вариант функ
-

ции
"
print_list_backwards(...)
". (
Какой вариант функции вам показался про
-

ще в разработке
?)

Упражнение 3

Даны два положительных целых числа
m

и
n

таких
,
что
m

<
n

.
Известно
,
что

наибольший общий делитель чисел
m

и
n

совпадает с наибольшим общим делителем

чисел
m

и
(
n

-
m

).
С учетом этого свойства напишите рекурсивный вариант функции

"
greatest_common_divisor(...)
",
которая принимает два положительных целых пара
-

метра и возвращает их наибольший общий делитель
.
Проверьте свою функцию с по
-

мощью подходящей тестовой программы
.

Упражнение 4

Бинарный поиск

–
это рекурсивно определенный алгоритм поиска заданного

значения в отсортированном массиве
.
Он особенно эффективен при обработке боль
-

ших массивов
,
т
.
к
.
не требует последовательного просмотра всех элементов массива
.

Основные действия алгоритма заключаются в следующем
.
Предположим
,
тре
-

буется определить в массиве
a[]
индекс элемента со значением
v
.
Массив
a[]
предва
-

рительно отсортирован по возрастанию
.
Сначала проверим значение среднего эле
-

мента массива
a[]
.
Если это значение равно
v
,
то работа алгоритма завершается
,
и

функция возвращает в качестве результата индекс среднего элемента
.
Если же оказы
-

вается
,
что средний элемент меньше
,
чем v
,
то требуется выполнить поиск только во

второй половине массива
.
При этом повторяется процедура деления массива пополам
.

Аналогично
,
если среднее значение оказывается больше
,
чем v
,
то требуется продол
-

жить поиск только в первой половине массива
.

Работу этого алгоритма легко понять
,
если мысленно применить его к поиску

заданного слова в словаре
.
Применяя бинарный поиск
,
вы должны начать с середины

словаря и затем ограничить поиск половиной словаря или до
,
или после средней

страницы
.
Затем деление просматриваемых страниц словаря повторяется и т
.
д
..

Для выполнения бинарного поиска напишите функцию с прототипом
:

int binary_search( int value, int list[], int first, int last );

Эта функция должна искать значение
"
value" в массиве
"
list[]
"
в интер
-

вале индексов от
"
list[first]
"
до
"
list[last]
".
Если значение
"
value
"
обнаружено в

заданном диапазоне
,
то функция должна возвратить индекс соответствующего эле
-

мента массива
"
list[]
".
В противном случае функция должна вернуть
-1
.
Например
,

для массива

list = { 2, 2, 3, 5, 8, 14, 16, 22, 22, 24, 30 }

функция

binary_search( 24, list, 0, 10 );

должна вернуть значение
9
,
функция

binary_search( 24, list, 2, 6 );

должна вернуть
-1
,
а функция

binary_search( 22, list, 0, 10 );

должна вернуть значение
7
или
8.

Проверьте свою функцию с помощью подходящей тестовой программы
. (
Для

этого вы можете модифицировать программу
7.1).

100

ЛЕКЦИЯ 9. Составные типы данных

1. Назначение составных типов данных

В программах часто приходится обрабатывать информацию
,
описывающую

более сложные объекты
,
чем числа и символы
.
Например
,
в библиотечной базе дан
-

ных требуется обрабатывать данные об объектах
"
Книги
",
в системе кадрового учета

–
"
Сотрудники
", "
Отделы
"
и т
.
п
.
В зависимости от решаемой задачи
,
программист оп
-

ределяет
,
какие характеристики
(
свойства
)
объектов нужно учитывать
.
Для хранения

этих свойств в программе выделяются переменные подходящих типов
,
например
,

символьный массив для имени сотрудника и вещественное число для его зарплаты
.

Оказывается
,
если свойства объектов хранить в отдельных переменных
,
то при боль
-

шом количестве различных свойств и при наличии большого количества экземпляров

однотипных объектов программисту становится довольно сложно следить за кор
-

ректным использованием переменных
.

В Си
++
для построения новых типов данных используются классы
,
объеди
-

няющие в себе и свойства объектов
,
и действия
(
алгоритмы
),
которые эти объекты

способны выполнять
.
Но
,
поскольку проблема обработки сложных типов данных ста
-

ла актуальной еще до распространения объектно
-
ориентированного программирова
-

ния
,
уже в язык Си было введено понятие структуры
.
Структура

– это составной

тип данных, который получается путем объединения компонент, принадлежащих к

другим типам данных (возможно, тоже составным).

Впоследствии в Си
++
понятие

структуры было расширено до класса
.

Пример структур в математике
–
комплексные числа
,
состоящие из двух веще
-

ственных чисел
,
и координаты точек
,
состоящие из двух или более вещественных чи
-

сел в зависимости от размерности координатного пространства
.
Пример из обработки

данных
–
это описание людей с помощью нескольких существенных характеристик
,

таких
,
как имя и фамилия
,
дата рождения
,
пол и семейное положение
.

Понятие структуры встречается во многих языках программирования и в об
-

ласти баз данных
,
только вместо термина
"
структура
",
специфичного для Си
++,
в

других языках обычно применяется термин
"
запись
" (
подразумевается
,
что перемен
-

ные составных типов предназначены для записи существенных характеристик объек
-

тов
,
обрабатываемых в программе
,
например
,
людей или материальных предметов
).

2. Описание и инициализация структур

Структура предназначена для объединения нескольких переменных в один тип

данных
.
Сначала тип структуры надо описать
,
а затем можно создавать переменные

этого нового типа
.
Описание типа структуры
"
T
"
имеет следующий синтаксис
:

struct T {

T1 var1;

T2 var2;

...

T3 var3;

};

где
"
T1
", "
T2
", "
T3
"
–
имена встроенных типов данных
("
int
", "
char
"
и др
.)
или дру
-

гих составных типов
. "
var1
", "
var2
", "
var3
"
–
это имена внутренних переменных

структуры
(
они также называются
компонентами

,
полями

или
членами

структуры
).

101

Далее приведены три примера описания структур для представления ком
-

плексных чисел
,
дат и сведений о людях
:

struct Complex {

double re;

double im;

};

struct Date {

int day;

int month;

int year;

};

struct Person {

char name[50];

Date birthdate;

double salary;

};

Обратите внимание на точку с запятой в конце описания типа структуры
.
Это

одно из очень немногих мест в Си
++,
где необходимо ставить точку с запятой после

фигурной скобки
.
На примере типа
"
Person
"
видно
,
что компоненты структуры мо
-

гут
,
в свою очередь
,
тоже быть составными
.
Переменные типа структуры описывают
-

ся аналогично переменным встроенных типов
:

Complex z;

Date d;

Person p;

В операторе описания переменные можно инициализировать путем перечисле
-

ния значений компонент в фигурных скобках
(
аналогично инициализации массивов
):

Complex z = { 1.6, 0.5 };

Date d = { 1, 4, 2001 };

Person p = { "Сидоров", {10, 3, 1978}, 1500.48 };

Для обращения к отдельным компонентам структуры применяется опера
-

ция
"
.
" (
точка
).
Сначала указывается имя переменной
-
структуры
,
а затем
–
имя ком
-

поненты
.
Например
:

z.im = 3.2;

d.month = 7;

p.birthdate.year = 1980;

p.salary = 2000.00;

Важно отметить
,
что не все возможные комбинации значений компонент

структуры могут иметь смысл применительно к конкретной задаче
.
Например
,
тип

"
Date
",
определенный выше
,
включает значения
{50, 5, 1973}
и
{100, 22, 1815},
хотя

дней с такими датами не существует
.
Т
.
о
.,
определение этого типа не отражает реаль
-

ного положения вещей
,
но все же оно достаточно близко к практическим целям
.
От
-

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

смысленные значения
,
возлагается на программиста
.

102

В программе
2.1
демонстрируется
,
как в исходном тексте на Си
++
располага
-

ются описание типа структуры
,
объявление переменных и обращение к компонентам

структуры
.

struct SimpleStructure {

char c;

int i;

float f;

double d;

};

void main()

{

SimpleStructure s1, s2;

s1.c = 'a';

s1.i = 1;

s1.f = 3.14f; // Буква 'f' в конце вещественной константы

//
означает, что это константа типа float,

// а не double

s1.d = 0.00093;

s2.c = 'b';

s2.i = 2;

s2.f = 6.28f;

s2.d = 0.15;

}

Программа 2.1.

В программе
2.1
в функции
"
main()
"
создаются две переменные типа

"
SimpleStructure
"
с именами
"
s1
"
и
"
s2
".
У каждой из этих переменных есть соб
-

ственный набор компонент с именами
"
c
", "
i
", "
f
",
и
"
d
".
Т
.
е
. "
s1
"
и
"
s2
"
являются

наборами независимых переменных
.
Для выбора компонент внутри
"
s1
"
или
"
s2
"

применяется _______операция
"
.
" (
точка
).
Подобная запись применялась в предыдущих лек
-

циях для обращения к функциям
-
членам объектов
"
cin
"
и
"
сout
".
Обращения к ком
-

понентам классов в объектно
-
ориентированном Си
++
очень похожи на обращения к

компонентам структур
.

Переменные типа структуры можно присваивать
,
передавать
,
как параметры

функции
,
и возвращать из функции в качестве результата
.
Например
:

Person current;

Person set_current_person( Person& p )

{

Person prev = current;

current = p;

return prev;

}

Остальные операции
,
такие
,
как сравнение
("
==
"
и
"
!=
"),
для структур по умол
-

чанию не определены
,
но программист может их определить при необходимости
.

Имя типа структуры можно использовать еще до того
,
как этот тип будет опре
-

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

Например
,
допустимы следующие прототипы функций
:

103

struct S; // S - имя некоторого типа

S f();

void g(S v1);

Но эти функции нельзя вызывать
,
если тип
"
S
"
не определен
:

void h()

{

S a; // ошибка: S не объявлено

f(); // ошибка: S не объявлено

g(a); // ошибка: S не объявлено

}

3. Доступ к компонентам структуры через указатель

Во всех предыдущих примерах компоненты структур использовались в выра
-

жениях подобно обычным переменным
.
Аналогично обычным переменным
,
можно

создавать указатели на переменные
-
структуры
.
Для доступа к компонентам структу
-

ры через указатель применяется операция
"
->
".
Например
:

void print_person( Person* p )

{

cout << p->name << '\n';

cout << p->birthdate.day << '\n';

cout << p->birthdate.month << '\n';

cout << p->birthdate.year << '\n';

cout << p->salary << '\n\n';

}

Функцию
"
print_person()
"
можно переписать в эквивалентном виде с по
-

мощью операции разыменования указателя
"
*
"
и операции доступа к компонентам

структуры
"
.
".
Обратите внимание на скобки в записи
"
(*p).
",
которые необходимы
,

поскольку приоритет операции
"
.
"
выше
,
чем у
"
*
":

void print_person( Person* p )

{

cout << (*p).name << '\n';

cout << (*p).birthdate.day << '\n';

cout << (*p).birthdate.month << '\n';

cout << (*p).birthdate.year << '\n';

cout << (*p).salary << '\n\n';

}

Использование указателей на структуры показано в программе
3.1.
В функции

"
main()
"
этой программы указателю
"
sp
" c
начала присваивается адрес
"
s1
",
и затем

с помощью операции
"
->
"
компонентам
"
s1
"
присваиваются начальные значения
.
За
-

тем указателю
"
sp
"
присваивается адрес
"
s2
",
и компоненты этой структуры также

инициализируются
.
Возможность динамического перенаправления на различные объ
-

екты является одним из важнейших свойств указателей
,
которые
,
в частности
,
полез
-

ны для реализации динамических структур данных
(
например
,
связного списка или

стека
).

struct ExStruct {

104

char c;

int i;

float f;

double d;

};

void main()

{

ExStruct s1, s2;

ExStruct* sp = &s1;

sp->c = 'a';

sp->i = 1;

sp->f = 3.14f;

sp->d = 0.00093;

sp = &s2;

sp->c = 'b';

sp->i = 2;

sp->f = 6.28f;

sp->d = 2.5;

}

Программа 3.1.

В
7-
й лекции
(
для реализации связного списка
)
и в
8-
й лекции уже рассматри
-

валось понятие рекурсивных структур данных
.
Для создания в структуре ссылки на

структуру такого же типа необходимо пользоваться указателем
.
В программе
3.2
соз
-

даются две структуры
,
содержащие ссылки друг на друга
.

struct SelfReferential {

int i;

SelfReferential* sr;

};

void main()

{

SelfReferential sr1, sr2;

sr1.sr = &sr2;

sr2.sr = &sr1;

sr1.i = 47;

sr2.i = 1024;

}

Программа 3.2.

Описание без указателя является недопустимым
,
т
.
к
.
в нем при описании ком
-

поненты структуры тип структуры используется в тот момент
,
когда этот тип еще не

определен полностью
:

struct SelfReferential {

int i;

SelfReferential sr; // Недопустимое описание компоненты

};

4. Массивы и структуры

У массива и структуры есть общее свойство
:
оба этих типа данных являются

типами с произвольным доступом
.
Но структура более универсальна
,
поскольку не

105

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

торых случаях массив предоставляет б
o
льшие возможности
,
т
.
к
.
индексы его элемен
-

тов могут вычисляться
,
а имена компонент структуры
–
это фиксированные иденти
-

фикаторы
,
задаваемые в описании типа
.

Массивы и структуры могут комбинироваться различными способами
.
Напри
-

мер
,
i

-
я компонента массива
"
a
",
который является компонентой структуры
"
r
",
обо
-

значается как

r.a[i]

Напротив
,
компонента с именем
"
s
",
входящая в
i

-
ю компоненту
-
структуру

массива структур
"
a
"
обозначается как

a[i].s

В качестве примера далее приведено описание переменной
"
screen
",
которая

является двумерным массивом структур типа
"
Cell
".
Этот массив предназначен для

хранения содержимого текстового экрана размером
80
х
25
знакомест
:

struct Cell {

unsigned char character;
// Символ

int foreground; // Цвет символа

int background; // Цвет фона

bool blink; // Мигание включено/выключено

};

void main()

{

Cell screen[25][80];

...

}

5. Перегрузка операторов

В
3-
й лекции
(
п
. 4)
были описаны средства перегрузки функций
.
Си
++
допус
-

кает перегрузку не только функций
,
но и операторов
,
таких
,
как _______
"
+
", "
-
", "
*
" (
и боль
-

шинство других
–
"
+=
", "
->
"
и даже
"
()
").
Средства перегрузки операторов полезны

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

программ выглядели в выражениях подобно встроенным типам Си
++.
Поясним это на

нескольких примерах
.

Для сложения комплексных чисел
(
описание структуры см
.
п
.2)
можно приме
-

нить функцию
:

Complex C_add( const Complex& x, const Complex& y )

{

Complex t;

t.re = x.re + y.re;

t.im = x.im + y.im;

return t;

}

Параметры функции
"
C_add(...)
"
передаются по ссылке
,
и
,
кроме того
,
опи
-

саны как константы
,
чтобы запретить изменения параметров внутри функции
.
Пере
-

дача по ссылке обеспечивает эффективный вызов функции
,
без копирования парамет
-

ров
,
а константное описание защищает параметры от изменений
.

106

Допустим
,
в программе реализована также функция
"
C_mult(...)
"
для умно
-

жения двух комплексных чисел
.
Ниже приведен пример использования этих функ
-

ций
:

Complex u, v, w, z, t;

...

t = C_add( u, v );

w = C_mult( z, t );

Конечно
,
более естественной является запись
:

Complex u, v, w, z;

...

w = z * ( u + v );

Тип
"
Complex
"
является типом
,
введенным пользователем
,
и
,
естественно
,
в

языке Си
++
арифметические операторы для этого типа не определены
.
Поэтому для

естественной записи выражений с числами в виде структур
"
Complex
"
надо перегру
-

зить операторы сложения и умножения
:

Complex operator +( const Complex& x, const Complex& y )

{

Complex t;

t.re = x.re + y.re;

t.im = x.im + y.im;

return t;

}

Complex operator *( const Complex& x, const Complex& y )

{

Complex t;

t.re = x.re*y.re - x.im*y.im;

t.im = x.re*y.im + x.im*y.re;

return t;

}

Правила размещения перегруженных операторов в исходном тексте программ

аналогичны правилам размещения функций
:
прототипы отдельно
,
определения от
-

дельно
(
возможно
,
прототипы операторов расположены в заголовочном файле
,
а оп
-

ределения
–
в файле реализации
).

Аналогично арифметическим операторам
,
в Си
++
допускается перегружать

операторы потокового ввода
/
вывода
"
>>
"
и
"
<<
".
Например
,
вывести комплексное

число на экран можно так
:

void main()

{

Complex u, v;

u.re = 2.1; u.im = 3.6;

v.re = 6.5; v.im = 7.8;

cout << "Числа равны (" << u.re << " + " << u.im << "i) и ";

cout << " (" << v.re << " + " << v.im << "i).\n";

}

107

В результате выполнения этой программы на экране будет напечатана строка
:

Числа равны (2.1 + 3.6i) и (6.5 + 7.8i).

Для упрощения записи операции печати комплексного числа на экране можно

перегрузить оператор вывода в поток
:

ostream& operator <<( ostream& s, const Complex& x )

{

s << "(" << x.re << " + " << x.im << "i)";

return s;

}

void main()

{

Complex u, v;

u.re = 2.1; u.im = 3.6;

v.re = 6.5; v.im = 7.8;

cout << "Числа равны " << u << " и " << v << ".\n";

}

В определении оператора фигурирует тип
"
ostream
".
Это класс
"
поток выво
-

да
",
объектом которого является стандартный поток вывода на экран
"
cout
".
Для по
-

токового ввода
/
вывода в файл необходимо перегружать операторы применительно к

классам
"
ofstream
"
и
"
ifstream
" (
см
. 4-
ю лекцию
).

6. Применение структур для реализации стека

Абстрактный тип данных
"
стек
"
кратко рассматривался в
8-
й лекции
(
компиля
-

тор использует стек для организации вызовов функций
).
Стек встречается не только в

компиляторах
,
но и во многих численных алгоритмах
.
В данном параграфе рассмат
-

риваются два варианта реализации стека на Си
++
с помощью структур
.

Среди значений английского слова
"stack"
есть значения
"
пачка
"
и
"
стопа
".
Аб
-

страктный тип данных
,
соответствующий принципу
"
последним прибыл
–
первым

обслужен
"
получил свое название из
-
за своего сходства со стопкой тарелок
(
рис
. 1).

Рис. 1.
.
Поведение стека при записи и чтении элементов
.

Основные свойства стека
:

1)
Элементы добавляются или удаляются только сверху стека
.

2)
Для добавления элемента применяется функция
"
push()
".

3)
Для удаления элемента применяется функция
"
pop()
".

108

6.1 Реализация стека на основе статического массива

В качестве задачи поставим разработку стека для хранения вещественных чи
-

сел
.
Свойства стека очень просты
,
поэтому для работы со стеком
,
например
,
из
20-
ти

вещественных чисел достаточно несложно написать программу
,
похожую на про
-

грамму
6.1.

#include <iostream.h>

struct Stack {

double v[20];

int top;

};

void push( Stack& s, double val )

{

s.v[s.top] = val;

s.top++;

}

double pop( Stack& s )

{

return s.v[--(s.top)];

}

void init( Stack& s )

{

s.top = 0;

}

bool full( Stack& s )

{

return s.top >= 20;

}

void main()

{

Stack s;

init( s ); // Инициализация стека

push( s, 2.31); // Помещение в стек первого элемента

push( s, 1.19 ); // Помещение в стек второго элемента

cout << pop( s ) << '\n'; // Извлечение верхнего элемента

// и вывод его на экран

push( s, 6.7 ); // Помещение в стек элемента

push( s, pop(s)+pop(s) ); // Замена двух верхних элементов

// стека их суммой

}

Программа 6.1.

В программе
6.1
стек реализован на базе статического массива
,
один из элемен
-

тов которого играет роль верхушки стека
.
Индекс этого элемента хранится в компо
-

ненте
top
. (
рис
. 2).

109

Рис. 2.
.
Стек на основе массива с фиксацией верхушки стека
.
Серым цветом

обозначены помещенные в стек элементы
.

6.2 Недостатки структуры данных Stack

Приведенному в п
. 6.1
простейшему варианту реализации стека
(
в виде струк
-

туры
"
Stack
")
присущи ряд недостатков
,
которые можно разбить на две группы
:

1)
Малая гибкость применения

•
У стека ограниченный размер
(20
элементов
).

•
В стеке могут храниться только значения типа
double
.

•
Имена функций наподобие
"
full()
"
и
"
init()
"
очень распростра
-

нены и может возникнуть конфликт этих имен с именами функций из

других библиотек
.

2)
Безопасность использования стека

•
Внутренние переменные стека не защищены от изменений извне
.
По
-

этому стек легко повредить путем изменения значений компонент

структуры
.
Это может привести к сложно обнаружимым ошибкам
.

•
Назначение компонент стека тесно связано с особенностями реализа
-

ции обслуживающих функций
("
init()
", "
push()
", "
pop()
"
и др
.).

•
В обслуживающих функциях не предусмотрена обработка типичных

ошибок
:
переполнение стека
,
попытка извлечения элемента из пусто
-

го стека
,
повторная инициализация стека
,
нет способа проверки со
-

стояния стека
(
поврежден
/
не поврежден
).

•
Присвоение структур
(
напр
., "
A=B
")
приводит к возникновению вися
-

чих указателей
,
т
.
к
.
присвоение компонент
-
массивов означает при
-

своение указателей
,
а не копирование отдельных элементов
.

Перечисленные недостатки показаны во фрагменте программы
6.2.

void Stack_Print( Stack& A )

{

if ( A.top = 0 ) // Ошибка: присваивание вместо сравнения

cout << "Стек пуст.\n";

else

cout << "Стек не пуст.\n";

}

void main()

{

Stack A;

double x;

push( A, 3.141 ); // Стек A не был проинициализирован

110

init( A );

x = pop( A ); // Ошибка: A в данный момент пуст,

// поэтому стек окажется в поврежденном

// состоянии, а значение x не определено

A.v[3] = 2.13; // Так помещать элементы в стек нельзя

A.top = -42; // Теперь стек окажется в логически

// некорректном состоянии

Stack C, D;

push( C, 0.9 );

push( C, 6.1 );

init( D );

D = C; // Такое присвоение допускается по

// правилам языка, но не обеспечивает

//
копирования элементов стека

init( C ); // Эта инициализация очищает содержимое

// и C, и D, поскольку они обращаются

// к одному массиву

}

Фрагмент программы 6.2.

6.3 Реализация стека с использованием динамической памяти

Для реализации стека можно предложить структуру
,
позволяющую создать

стек произвольного размера и работать с элементами стека через указатели
.
Далее

_______приведен один из вариантов этой структуры
:

struct DStack {

double* bottom;

double* top;

int size; // Это максимальный размер стека,

};
// а не количество элементов в нем

Массив для хранения элементов стека должен создаваться динамически на эта
-

пе инициализации
.
Два внутренних указателя стека ссылаются на начало массива

("
bottom
")
и на элемент
-
верхушку стека
("
top
").
Устройство стека на базе динамиче
-

ского массива показана на рис
. 3.

Рис. 3.
.
Стек с хранением элементов в динамической памяти
.

Для работы со стеком целесообразно сделать несколько обслуживающих функ
-

ций
:

1)
Инициализация стека.

bool DStack_init( DStack& s, int N );

111

Эта функция динамически создает целочисленный массив размером
N
эле
-

ментов и сохраняет его указатель в компонентах структуры
"
DStack
".
Если

операция инициализации прошла успешно
,
то функция возвращает
"
true
",

а если памяти недостаточно
–
то
"
false
".

2)
Добавление элемента в стек.

bool DStack_push( DStack& s, double val );

Помещает элемент на верх стека
.
Возвращает
"
true
",
если это удалось сде
-

лать
,
или
"
false
",
если стек целиком заполнен
.

3)
Извлечение верхнего элемента.

double DStack_pop( DStack& s );

Возвращает верхний элемент из стека или вохвращает
0.0 (
или некоторое

другое специально оговоренное значение
),
если стек пуст
.

4)
Проверка на пустоту.

bool DStack_empty( Dstack& s );

Возврашает
"
true
",
если стек пуст
,
или
"
false
"
в противном случае
.

5)
Удаление стека.

void DStack_free();

Освобождает динамическую память
,
занятую при создании стека
.

По сравнению со стеком из п
.6.1,
в описанном варианте реализации достигает
-

ся ряд улучшений
:

1)
Есть возможность создания стеков разного размера
.

2)
В обслуживающих функциях предусмотрена обработка элементарных оши
-

бок переполнения и обращения к пустому стеку
.

3)
Имена обслуживающих функций
,
начинающиеся с
"
DStack_
",
менее веро
-

ятно обнаружить в других библиотеках
.

К сожалению
,
опасность несанкционированного изменения внутренних пере
-

менных стека сохраняется и в этой реализации
.

7. Сводка результатов

Составной тип данных позволяет объединить под одним именем несколько пе
-

ременных уже существующих типов
.
В Си
++
для описания составного типа применя
-

ется служебное слово
"
struct
".
Структуры могут быть вложенными
.
Для обращения

к компонентам структуры используются операции точка
"
.
"
или
"
->
" (
если обраще
-

ние выполняется через указатель на структуру
).

Внутрь функций структуры чаще передаются по ссылке
.
Если параметры
-

структуры внутри функции заведомо не изменяются
,
то такие параметры обычно опи
-

сываются как константные параметры
.

Можно создавать и использовать массивы структур
,
или использовать массивы

в качестве компонент структур
.
Для более краткой и естественной записи выражений

со структурами допускается перегрузка операторов
.

В лекции рассмотрено два варианта реализации стека на базе статического мас
-

сива и с использованием динамической памяти
.
Явным недостатком обоих вариантов

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

ректных изменений извне
.

112

8. Упражнения

Упражнение 1

Напишите функцию для печати на экране содержимого стека
,
представленного

в виде структуры
"
Stack
"
из п
. 6.1.
Перегрузку операторов не используйте
.
Проверь
-

те работу функции с помощью подходящей тестовой программы
.

Упражнение 2

Разработайте статический стек для хранения целых чисел и для хранения сим
-

вольных строк длиной до
100
символов
.
Для каждого из стеков сделайте отдельные

заголовочные файлы
("
stack_int.h
"
и
"
stack_string.h
")
и файлы реализации

("
stack_int.cpp
"
и
"
stack_string.cpp
").
Проверьте работу стеков с помощью

соответствующей тестовой программы
.

Упражнение 3

Согласно описанию из п
. 6.3
реализуйте стек с использованием динамической

памяти
(
примените операторы
"
new
"
и
"
delete
").

Упражнение 4

Напишите функции для записи содержимого массива структур
"
Person
"

(
см
.
п
.2)
в файл
,
для чтения структур
"
Person
"
из файла и для печати этих структур

на экране
.
Для ввода
/
вывода из файла и для вывода на экран примените перегружен
-

ные операторы
"
>>
"
и
"
<<
".

113

ПРИЛОЖЕНИЕ. Краткое руководство по среде разработки

Developer Studio Visual C++

Microsoft Developer Studio
–
это интегрированная среда разработки программ
,

объединяющая текстовый редактор
,
компилятор
,
компоновщик и отладчик
.
Эта среда

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

числе на Си
++
и
Java.

В этом приложении подробно описаны действия
,
необходимые для написания

простой программы на Си
++,
ее компиляции и запуска с помощью
Developer Studio

Visual C++
на ПК под управлением операционной системы
Windows 95/NT
.

Visual C++
выполняет компиляцию и запуск программ в соответствии с
про-

ектом

.
Проект
–
это структура данных
,
содержащая всю информацию
,
необходимую

для компиляции исходных файлов программы и ее компоновки со стандартными биб
-

лиотеками
(
например
,
библиотекой ввода
/
вывода
).

Компиляция и компоновка исходных файлов называется
сборкой

проекта
.
В ре
-

зультате успешной сборки
Visual C++
создает
приложение

(
двоичный исполняемый

файл программы
).

В данном учебном курсе все проекты рассчитаны на создание
32-
битных кон
-

сольных приложений
.
Консольные приложения общаются с пользователем через про
-

стейшее окно ввода
/
вывода
,
которое называется
консольным окном

.

1. Создание нового проекта

Проект состоит из набора файлов с исходным текстом программы
(
исходных

файлов
)
и набора параметров
,
определяющих компиляцию и компоновку этих файлов

в исполняемый файл приложения
.
У проекта должно быть уникальное имя
.
Парамет
-

ры проекта хранятся в файлах с расширениями
"
.DSW
"
и
"
.DSP
"
в
папке проекта

.

Далее подробно описаны действия по созданию проекта для простого консоль
-

ного приложения
hello_world
,
которые вы можете воспроизвести самостоятельно
.

Сначала с помощью главного меню
Windows
запустите
Visual C++
.
Затем про
-

делайте перечисленные ниже действия
.

1)
Выберите команду верхнего меню
File

⇒
New

(
рис
. 1).

Рис. 1.
Выбор команды
File

⇒
New

(
Файл

⇒
Новый

).

Рис. 2.
Закладка
Projects
(
Проекты
)
в окне соз
-

дания нового файла
.

114

2)
Перейдите на закладку
Projects
(
рис
. 2).

3)
Выберите проект типа
Win32 Console application

(
консольное приложение для платформы
Win32
,
т
.
е
.
Windows 95/98
и

NT/2000
).

4)
В строке
Location
(
Местоположение
)
укажите

папку диска
C:\
,
имя которой совпадает с вашей фамилией
(
например
,

"
C:\Ivanov
").
В строке
Project Name
(
Имя проекта
)
введите

"
hello_world
".
По умолчанию
Developer Studio
сделает новую папку про
-

екта
C:\Ivanov\hello_world
.
В ней будут сохраняться все файлы
,
отно
-

сящиеся к данному проекту
.

5)
По умолчанию в качестве целевой платформы

проекта указывается
Win32
.
Не изменяйте этот параметр
.

6)
Нажмите
OK
для создания проекта с заданными

параметрами
.

2. Добавление в проект нового исходного файла

Чтобы включить в проект исходный текст программы
,
надо создать новый тек
-

стовый файл с текстом программы на Си
++
и добавить его в проект
.
Для этого вы
-

полните следующие действия
:

1)
Выберите команду меню
File

⇒
New

.

2)
В окне создания нового файла перейдите на закладку
Files
(
рис
. 3).

3)
В списке выберите тип нового файла
:
C++ Source code
(
исходный файл Си
++).

4)
По умолчанию новый файл будет добавлен в текущий проект
hello_world
(
т
.
к
.

установлен флажок
Add to project
).

5)
В строке
File name
наберите имя нового файла
–
hello
(
расширение
"
.CPP
"
будет

добавлено автоматически
).

6)
Нажмите
OK
.

Рис. 3.
Закладка
Files
(
Файлы
)
в окне создания нового файла
.

Developer Studio
создаст новый файл
hello.cpp
в папке

C:\Ivanov\hello_world
и добавит его в проект
hello_world
.
Новый файл авто
-

матически будет открыт в окне текстового редактора
(
рис
. 4).
Наберите в нем текст

программы
,
печатающей на экране короткое сообщение
:

#include <iostream.h>

int main()

115

{

cout << "Hello world!\n";

return 0;

}

Чтобы сохранить набранный текст на диске
,
выберите команду меню

File

⇒
Save

(
Файл

⇒
Сохранить

).

Рис. 4.
Окно текстового редактора с открытым файлом hello.cpp распо
-

ложено в правой части окна
Developer Studio
.

3. Сборка проекта

Результатом сборки проекта является исполняемый файл программы
,
который

может работать независимо от
Developer Studio
.

Для сборки проекта выберите команду меню
Build

⇒
Build hello_world.exe

(
рис
. 5).
В нашем примере проект содержит только один исходный файл

(
hello.cpp
).
В процессе сборки он будет скомпилирован и скомпонован со стан
-

дартной библиотекой ввода
/
вывода
.

Рис. 5.
Выбор команды
Build

⇒
Build hello_world.exe

(
Сборка

⇒
Сборка при-

ложения hello_world.exe

).

Информация о выполнении сборки отображается в окне
Output window

(
рис
. 6).
В нем выводятся сообщения
,
выдаваемые программами
,
работающими при

сборке проекта
:
препроцессором
,
компилятором и компоновщиком
.
Среди этих со
-

общений могут встретиться сообщения об ошибках
(errors)
и предупреждения о воз
-

можных ошибках
(warnings).
Если таких сообщений не возникло
,
значит
,
сборка ус
-

пешно завершена
(
рис
. 6).

Рис. 6.
Окно
Output window
(
Окно вывода
)
расположено в нижней части

окна
Developer Studio
.

116

Если есть ошибки
,
их надо устранить
(
в нашем случае просто внимательно

сверьте исходный текст с образцом
)
и снова попытаться собрать проект
.

4. Запуск нового приложения

В результате сборки было создано консольное приложение
.
Такие приложения

широко использовались до появления систем
Windows
.
Они удобны для учебных це
-

лей
,
т
.
к
.
простая структура консольных программ позволяет на начальном этапе изу
-

чения языка программирования не отвлекаться на системные особенности программ

для
Windows
.

Для запуска приложения выберите команду меню
Build

⇒
Execute

hello_world.exe

(
рис
. 7).
Для удобства
Developer Studio
помещает имя исполняемого

файла в название команды меню
.

Рис. 7.
Выбор команды
Build

⇒
Execute hello_world.exe

(
Сборка

⇒
Запуск

приложения hello_world.exe

).

После выбора команды запуска
Developer Studio
создаст консольное окно
–

окно
,
напоминающее экран компьютера
,
работающего под управлением
MS-DOS
,
а

не
Windows
.
Консольное приложение осуществляет ввод
/
вывод данных в пределах

этого окна
(
рис
. 8).

Рис. 8.
Окно консольного приложения hello_world.exe
.

Более подробные сведения об использовании среды разработки содержатся в

справочной системе
Developer Studio
.
В Приложении
2
описаны некоторые способы

отладки программ и служебные клавиши отладчика
Developer Studio
.

117

Литература

1) Miller R., Clark D, White B., Knottenbelt W. An Introduction to the Imperative Part

of C++. Imperial College of Science, Technology and Medicine, London. 1996-1999.

(
Вводное описание программирования на Си
++,
послужившее основой данной

части учебного курса
.)

2) Savitch W., Problem Solving with C++: The Object of Programming, 2nd Edition, Addison

Wesley Publishing Company, Inc., 1999. (
Учебник начального уровня по про
-

граммированию
,
языку Си
++
и объектно
-
ориентированному программированию
.)

3)
Вирт Н
.
Алгоритмы
+
структуры данных
=
программы
.
М
.:
Мир
, 1985. (
В этой моно
-

графии подробно рассматриваются алгоритмы сортировки
,
рекурсивные алгорит
-

мы и динамические типы данных
.
Изложение базируется на языке Паскаль
,
но из
-

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

Си
++.)

4)
Страуструп Б
.
Язык программирования С
++.
Вторая редакция
.
К
.:"
ДиаСофт
",

1993. ("
Классическое
"
справочное руководство по языку Си
++,
написанное авто
-

ром языка
.
Эта книга пригодится тем
,
кто собирается в будущем серьезно зани
-

маться программировать на Си
++.)

5)
Уэйт М
.,
Прата С
.,
Мартин Д
.
Язык Си
.
Руководство для начинающих
.
М
.:
Мир
,

1988. (
Учебник начального уровня по языку Си без объектно
-
ориентированных

возможностей
.
В отличие от данных лекций
,
в этой книге используются библио
-

течные функции ввода
-
вывода языка Си
,
а не потоковые объекты Си
++.)

118

Учебно
-
методическое издание

А
.
А
.
Богуславский
,
С
.
М
.
Соколов

Основы программирования на языке Си
++

В
4-
х частях
.

(
для студентов физико
-
математических факультетов

педагогических институтов
)

Компьютерная верстка Богуславский А
.
А
.

Технический редактор Пономарева В
.
В
.

Сдано в набор
12.04.2002
Подписано в печать
16.04.2002

Формат
60
х
84
х
1/16
Бумага офсетная

Печ
.
л
. 20,5
Учетно
-
изд
.
л
. ____
Тираж
100

Лицензия ИД №
06076
от
19.10.2001

140410
г
.
Коломна
,
Моск
.
обл
.,
ул
.
Зеленая
, 30.
Коломенский государственный педаго
-

гический институт
.

119
__

Не сдавайте скачаную работу преподавателю!

Данный реферат Вы можете использовать для подготовки курсовых проектов.

Доработать Узнать цену написания по вашей теме

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Заказать работу:

!	Курсовая работа
!	Дипломная работа
!	Реферат
!	Решение задач
!	Отчет по практике
!	Контрольная работа

Пишем реферат самостоятельно:

!	Как писать рефераты Практические рекомендации по написанию студенческих рефератов.
!	План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
!	Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
!	Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
!	Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:

→	Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Другие популярные рефераты:

Реферат	Механические волны
Реферат	Обратная матрица
Реферат	Инверсия и ее применение
Реферат	Социокультурная динамика межпоколенных взаимодействий
Реферат	Расследование преступлений в сфере компьютерной информации
Реферат	Туристско-краеведческая характеристика Калининградской области
Реферат	Организация административно-хозяйственной службы гостиницы
Реферат	Диагностика психологической готовности ребенка к школе 2
Реферат	Модель современного менеджера
Реферат	Условия формирования военно-административной системы Южного Зауралья в XVII - первой половине XIX века

Сейчас смотрят :

Реферат	Порядок заполнения налоговой декларации по НДС при ввозе товаров из России
Реферат	Аннотация магистерской программы «Стратегическое управление компанией и модели делового совершенства» Реализует программу
Реферат	Тесты по общей хирургии 3 курс
Реферат	Хирургия (Рак молочной железы)
Реферат	Калий в организме человека
Реферат	Национальный бизнес
Реферат	Цели в системе управления
Реферат	Хартия экономических прав и обязанностей государств
Реферат	Великий Князь Сергей Александрович и ФМ Достоевский духовное родство
Реферат	Управление, как власть и искусство
Реферат	Остеопатия. Кранио-сакральная техника (КСТ)
Реферат	Nudging The Glass Ceiling Essay Research Paper
Реферат	Договор дарения в современном гражданском праве
Реферат	Что самое главное в оценке персонала?
Реферат	Определение оптимальных параметров производства в краткосрочном периоде на предприятии ОП Шахта "Шахтёрская-Глубокая"

Реферат по предмету "Информатика"

Основы программирования на языке Си

Другие популярные рефераты:

Сейчас смотрят :