Программирование курс лекций

---

Введение

 

Учебное пособие представляет собой конспект лекций по языку программирования С++. Пособие предназначено для студентов начинающих изучать язык С++, но может быть полезным и более опытным в программировании читателям. Цель пособия не только обучить студентов языку С++, но и познакомить студентов с технологией разработки программ. Все теоретические материалы сопровождаются примерами законченных программ.

Пособие содержит десять разделов. В разделе «Знакомство с языком С++» рассматриваются элементарные конструкции языка и структура простой программы на языке С++.

В разделе «Основные типы данных» рассматриваются встроенные в язык типы данных и их использование для записи выражений.

Раздел «Структурное программирование» посвящен изучению синтаксиса и семантики операторов С++. В разделе приводятся программы, реализующие линейные, разветвляющиеся и циклические алгоритмы.

В разделах «Массивы», «Строки» и «Структуры и объединения» рассматривается использование составных типов данных в программировании.

В разделе «Указатели» изучаются операции над указателями и их использование для работы с динамическими массивами. Материал этого раздела является основой для программной реализации динамических структур данных.

Раздел «Модульное программирование» посвящен нисходящей разработке программ и функциям языка С++, знание которых необходимо для создания больших программ.

В разделе «Работа с файлами» описываются средства языка С++ для работы с данными на внешних носителях. Приводится большое количество программ для работы с текстовыми и двоичными файлами.

В разделе «Данные с динамической структурой» изучаются динамические структуры данных: линейные списки, деревья и графы.

1. Знакомство с языком С++

 

1.1. Элементы языка программирования

 

Для программирования на языке высокого уровня надо изучить правила построения языковых конструкций (синтаксис языка) и правила их использования (семантику языка). Изучение этих правил начнем с разбора простой программы на языке С++.

Пример программы на языке С++ для вычисления математического выражения z=cos(x)+у²:

//Вычисление выражения

#include <iostream.h>

#include <conio.h>

#include <math.h>

void main()

{

float x, y, z;

cout<<”x, y? ”;

cin>>x>>y;

z=cos(x)+y*y;

cout<<“z=”<<z;

getch();

}

Комментарии к программе.

1 строка – это однострочный комментарий. Комментарии используются для документирования программы и облегчения чтения ее исходного кода. Однострочный комментарий должен размещаться в одной строке и начинаться двумя символами \. Комментарии могут быть многострочными. Такие комментарии заключаются в пары символов /* */, например:

/* Это многострочный

комментарий */).

2-4 строки – это директивы препроцессора. Директивы препроцессора записывают в отдельных строках. Они начинаются с символа #. До символа # могут быть пробелы. Директива препроцессора #include применяется для включения в программу копии указанного в ней файла. В примере директивы #include включают в программу заголовочные файлы стандартных библиотек: потокового ввода-вывода (iostream.h), математических функций (math.h) и консольного ввода-вывода (conio.h).

5 строка – это заголовок функции main. Функция с именем main должна обязательно содержаться в консольном приложении. Программа на С++ может содержать несколько функций. Выполнение программы всегда начинается с первого оператора функции main.

Строки 6, 13 начинают и заканчивают тело функции. Тело функции заключается в фигурные скобки.

Строка 7 – содержит объявление вещественных переменных с именами х, y и z. Переменные x и y используются в программе для хранения входных данных, а z – для хранения результата вычисления выражения. В языке С++ все переменные перед их использованием в программе должны быть объявлены. Объявления переменных могут находиться: вне функций (глобальные объявления), в определениях функций и даже внутри составного оператора и оператора цикла.

Строка 8 – содержит оператор-выражение, который выводит на экран текст x, y?. Выводимый текст заключается в кавычки. Оператор посылает поток символов x, y? объекту cout, который связан с экраном. Операция << называется «поместить в поток вывода».

Строка 9 – содержит оператор-выражение, который вводит с клавиатуры два вещественных числа и помещает их в переменные х и у. Операция >> называется «взять (получить) из потока ввода». cin – имя входного потока, связанного с клавиатурой.

Строка 10 – содержит оператор-выражение, который вычисляет выражение и присваивает результат переменной z.

Строка 11 – содержит оператор-выражение, который выводит значение переменной z с поясняющим текстом на экран.

Строка 12 – содержит оператор, в котором вызывается функция getch из стандартной библиотеки conio для задержки результатов программы на экране. Функция getch ждет нажатия пользователем программы любой клавиши на клавиатуре.

Основные правила записи программы:

1. Программа на языке С++ состоит из операторов, объявлений, определений функций, директив препроцессора и комментариев.
2.  Все переменные должны быть объявлены до их первого использования в операторах.
3. Программа записывается с помощью символов, входящих в алфавит языка С++. Язык С++ является чувствительным к регистру: строчные и прописные буквы в программе различаются. Служебные слова языка и имена функций из стандартных библиотек пишутся строчными буквами, имена для переменных могут содержать как строчные, так и прописные буквы.
4. Программа записывается в свободном формате: вся программа может быть записана в одну строку, а один оператор (или объявление) может быть записан в нескольких строках. Компилятор распознает конец оператора или объявления по символу; (точка с запятой), котрым заканчивается каждый оператор и каждое объявление. Чтобы программа лучше читалась, желательно ее записывать структурно: размещать каждый оператор и каждое объявление с новой строки, делать отступы в 3-4 пробела для вложенных операторов.

 

1.2. Алфавит языка

 

Алфавит – это допустимый набор символов, используемых при записи программы. Алфавит языка С++ включает:

• латинские буквы,
• цифры,
• специальные знаки:
• + – * % /
• < >  =
• () {} []
• . , ! ? ‘ “ : ;
• | \ & # ~ ^ _
• пробельные символы: пробел, табуляция, переход на новую строку.

1.3. Лексемы

 

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

Идентификатор – это имя программного объекта. Идентификатор может содержать буквы, цифры и символы подчеркивания. Первым символом идентификатора может быть буква или символ подчеркивания. Для улучшения читаемости программы следует задавать осмысленные идентификаторы. Идентификаторы не должен совпадать с ключевыми словами языка С++. Примеры правильной записи идентификаторов: a1, max, file_name.

Ключевые слова – зарезервированные слова языка, которые можно использовать только в определенных конструкциях языка. Список основных ключевых слов языка С++ приведен в табл. 1.

 

Таблица 1

Список ключевых слов С++

 

asm	auto	bool	break
case	catch	char	class
const	continue	default	delete
do	double	else	enum
extern	false	float	for
friend	goto	if	inline
int	long	namespace	new
operator	private	protected	public
register	return	short	signed
sizeof	static	struct	switch
template	this	throw	true
try	typedef	typename	union
unsigned	using	virtual	void
volatile	while

Разделители – это скобки, знаки препинания (запятая, точка с запятой), пробельные символы, к которым относятся пробел, символ табуляции и символ перехода на новую строку.Знак операции – это один или более символов алфавита, определяющих действия над операндами. Примеры знаков операций: +  <=.

Константы – это неизменяемые программные объекты. В табл. 2 приведены примеры констант разных типов.

 

Таблица 2

Константы языка С++

 

1.4. Концепция данных

 

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

• множество допустимых значений, которые могут принимать данные;
• допустимые операции над данным;
• формат хранения данных в памяти компьютера.

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

float x;

Принадлежность константы к определенному типу задается ее записью. Например, в операторе-выражении х=2; компилятор отнесет константу 2 к целому типу данных, так как в записи константы отсутствует точка. Тип значения вычисляемого выражения определяется правилами языка для типа выражений, которые будут рассмотрены позже.

 

1. Основные типы данных

 

Все типы данных С++ можно разделить на два класса: класс основных типов и класс производных типов. К основным типам данных относятся целый, вещественный, вещественный с двойной точностью, символьный, логический и тип void. Производные типы данных строятся на их основе. К производным типам данных относятся массивы, структуры, объединения, классы, функции, указатели и перечисления.

 

2.1.        Обьявление переменных

 

Переменная – это программный объект, который предназначен для хранения данных. Переменная имеет имя (идентификатор) и значение, которое может изменяться при работе программы. Имя переменная получает при объявлении. Объявление переменной должно располагаться в программе до ее первого использования. При объявлении переменной с ее именем связывается область оперативной памяти, в которой будет храниться значение переменной.

Синтаксис объявления переменных основных типов:

Тип список_имен_переменных;

Тип переменных задается одним из ключевых слов: int, float, double, char, bool. Перед типом переменных могут использоваться модификаторы типа: short, long, signed, unsigned. Модификаторы short и long изменяют размер оперативной памяти, выделяемую переменной для хранения данных в соответствии с ее типом, а модификаторы signed и unsigned изменяют способ использования старшего бита. При использовании модификатора unsigned старший бит рассматривается как часть кода числа. Диапазон значений и размер памяти для данных основных типов приведенны в табл. 3.

Таблица 3

Диапазон и размер данных основных типов

Тип	Размер (в байтах)	Диапазон значений
int (signed int)	2 или 4 определяется процессором	-32768 – 32767 или -2147483648 – 2147483647
short (signed short int)	2	-32768 – 32767
unsigned short int	2	0 – 65535
unsigned long int	4	0 – 4 294 967 295
signed long int	4	-2147483648 – 2147483647
char	1	0 – 255
signed char	1	-127 – 128
unsigned char	1	0 – 255
float	4	3.4Е-38 – 3.4Е38
double	8	1.7Е-308 – 1.7Е308
long double	10	3.4E-4932 – 3.4E+4932
bool	1	true, false

 

Примеры объявлений переменных:

int a,b;

long double y;

unsigned short w;

Переменной при объявлении можно присвоить начальное значение (инициализировать ее).

Примеры инициализации переменной:

int k=0; //инициализация со знаком присваивания

int x (100); //инициализация с использованием круглых скобок

const float pi=3.1459; //объявление именованной константы

Переменная, объявленная с модификатором const, называется именованной константной, или просто константой: изменять ее значение в программе нельзя.

Пример программы вычисления площади прямоугольника:

#include <iostream.h>

#include <conio.h>

void main()

{

float a, b, s; //основание, высота и площадь

cout<<”a, b? “;

cin>>a>>b;

s=a*b;

cout<<”s=”<<s;

getch();

}

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

После выделения памяти под переменные a, b и s эти переменные содержат случайные значения. При вводе значений в переменные a и b вводимые значения замещают значения, ранее хранившиеся в них. При присваивании переменной s выражения a*b значение выражения вычисляется для текущих значений переменных a и b, а затем результат выражения заносится в область памяти, выделенную под переменную s. При выводе значения переменной s на экран значение s в памяти не разрушается, так как для вывода на экран используется копия значения s.

 

2.2. Операции

 

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

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

• унарные (имеют 1 операнд);
• бинарные (имеют 2 операнда);
• тернарные (имеют 3 операнда).

Приоритет операции определяет порядок выполнения операций в выражении. Унарные операции имеют больший приоритет, чем бинарные и тернарная операция. Приритет операций в порядке убывания приритетов приведен в табл. 4.

Таблица 4

Операции С++

Категория приоритета	Знак операции	Наименование операции
1	::( ) [ ] . ->	Указание области видимости Вызов функции Индексация Выбор поля структуры по ее имени Выбор поля структуры по указателю на структуру
2	.*    -> *	Обращение к компоненту класса по имени объекта и указателю на компонент Обращение к компоненту класса по указателю на объект и указателю на компонент
3	+- ~ ! ++ – – & * new delete sizeof (тип) тип ( )	Унарный плюс Унарный минус Побитовое отрицание Логическое отрицание (НЕ) Инкремент Декремент Вычисление адреса Косвенная адресация Выделение динамической памяти Освобождение выделенной памяти Вычисление размера объекта Каноническая операция приведения типа Функциональная операция приведения типа
4	*/ %	Умножение Деление Остаток от целочисленного деления
5	+-	Сложение Вычитание
6	<<>>	Сдвиг влево Сдвиг вправо
7	<> <= >=	Меньше Больше Меньше или равно Больше или равно
8	= =!=	Равно Не равно
9	&	Поразрядная конъюнкция (И)
10	^	Поразрядное исключающее ИЛИ
11	|	Поразрядная дизъюнкция (ИЛИ)
12	&&	Конъюнкция (И)
13	| |	Дизъюнкция (ИЛИ)
14	?:	Условная операция
15	=  +=  -=   *=   /=   %=   &=   |=  ^=   <<=   >>=	Операции присваивания
16	,	Операция запятая

 

2.2.1. Арифметические операции

 

Арифметические операции используются в арифметических выражениях. Рассмотрим особенности использования некоторых арифметических операций в выражениях.

Деление (/) Если хотя бы один из операндов операции вещественный, то и результат операции вещественный, иначе – тип результата целочисленный (дробная часть результата отбрасывается). Например, результатом вычисления выражения 5/2 будет 2, а результатом вычисления выражения 5.0/2 будет 2.5.

Остаток от целочисленного деления (%) Операнды этой операции могут быть только целого типа. Результат выражения 5%2 равен 1.

Пример программы вычисления суммы старшей и младшей цифр целого положительного трехзначного числа:

#include <iostream.h>

#include <conio.h>

void main()

{

int a, s; //вводимое число и сумма цифр старшей и младшей цифр

cout<< “a? “

cin>>a;

s=a/100+a%10;

cout<< “s=”<<s;

getch();

}

Инкремент и декремент (++, –) Эти унарные операции увеличивают (++) или уменьшают (–) операнд на 1.

Тип операнда может быть: целым, вещественным и указателем. Операнд может быть только переменной. Например, допустимо выражение х++, но выражение 3++ или (a+b)++ в программе С++ недопустимо.

При вычислении выражения с инкрементом или декрементом кроме приоритета операций учитывается форма операций инкремента и декремента. Операции могут быть записаны в одной из двух форм: постфиксной форме, когда знак операции записывается после операнда (х++), или в префиксной форме, когда знак операнда записывается перед операндом (++х). Если инкремент (декремент) записан в префиксной форме, то вначале операнд изменяется, а затем уже измененным участвует в выражении. Если инкремент (декремент) записан в постфиксной форме, то вначале операнд участвует в выражении, а затем уже изменяется.

Пример программы, демонстрирующей различие между префиксной и постфиксной формами операции инкремента:

#include <iostream.h>

#include <conio.h>

void main()

{

int a=2;

int b=2;

int x;

x=++a+4;

cout<<a<<‘ ‘<<x<< <<endl;

x=4+b++;

cout<<b<<‘ ‘<<x;

getch();

}

Результат работы программы:

3 7

3 6

 

2.2.2. Операции присваивания

 

Язык С++ содержит несколько операций присваивания:

• обычное присваивание =;
• операции составного присваивания Ɵ=, где Ɵ – это один из знаков бинарных операций: +, -, *, /, %, &, |, ^, >>, <<.

Выражение с операцией составного присваивания aƟ=b эквивалентно выражению a=a Ɵ b.

Примеры операций составного присваивания:

x+=2; //сложить и присвоить, эквивалентно х=х+2

x-=y; //вычесть и присвоить, эквивалентно х=х-y

x*=10; // умножить и присвоить, эквивалентно x=x*10

Операции составного присваивания позволяют сократить запись выражений. Кроме того, операции составного присваивания выполняются быстрее, чем эквивалентные выражения с обычным присваиванием.

Операция = может многократно встречаться в выражении, например, x=y=z=3;

 

2.2.3. Операции отношения

 

Операции отношения:

• <, > меньше и больше;
• <=, >= меньше или равно и больше или равно;
• ==, != равно и не равно.

Эти операции используются для задания простых условий.

Пример программы, определяющей попадает ли точка с координатами {x, y} в правую полуплоскость:

#include <iostream.h>

#include <conio.h>

void main()

{

float x, y;

cout<<”x, y? ”;

cin>>x>>y;

if (x>0)

cout<<”Yes”;

else

cout<<”No”;

getch();

}

 

2.2.4. Логические операции

 

Логические операции языка С++:

• && логическое И;
• || логическое ИЛИ;
• ! логическое отрицание.

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

Пример программы, определяющей принадлежит ли вещественное число х диапазону [a, b]:

#include <iostream.h>

#include <conio.h>

void main()

{

float x, a, b;

cout<<”a, b? ”;

cin>>a>>b;

cout<<”x? ”;

cin>>x;

if (x>=a && x<=b)

cout<<”Yes”;

else

cout<<”No”;

getch();

}

 

2.2.5. Поразрядные операции

 

В языке С++ используются следующие поразрядные операции:

• ~ поразрядное отрицание;
• << >> сдвиг влево и сдвиг вправо;
• & поразрядное И;
• ^ поразрядное исключающее ИЛИ;
• | поразрядное ИЛИ.

Они работают с двоичным представлением целых чисел и обеспечивают доступ к отдельному разряду числа. Операнды операций – целые числа или символы.

Поразрядные операции применяются для:

• обработки массивов, каждое данное которых имеет одно из двух возможных значений;
• быстрого умножения и деления чисел на 2ⁿ;
• создания битовых масок.

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

Пример:

unsigned short x, z;

x=2; //0000000000000010

z=~x;//1111111111111101

cout<<z;// 65533

Операция сдвиг влево сдвигает все разряды влево на заданное число, заполняя освободившиеся разряды значением 0.

Пример:

unsigned short x, z;

x=2; //0000000000000010

z=x<<3;//000000000010000 равносильно умножению на 2³

cout<<z;//16

Операция сдвиг вправо cдвигает все разряды вправо на заданное число, заполняя освободившиеся разряды значением 0, если число беззнаковое, и значением 0 или значением знакового разряда (в зависимости от реализации С++).

Пример:

unsigned short x, z;

x=16; //0000000000010000

z=x>>3; //000000000000010 равносильно делению на 2³

cout<<z; //2

Операция поразрядное И формирует результат, каждый разряд которого равен 1 только тогда, когда соответствующие разряды операндов равны 1.

Пример:

unsigned short x, y, z;

x=2; //0000000000000010

y=3; //0000000000000011

z=x&y;//000000000000010

cout<<z; //2

Операция поразрядное исключающее ИЛИ формирует результат, каждый разряд которого равен 1 только тогда, когда соответствующие разряды операндов различны.

Пример:

unsigned short x, y, z;

x=2; //0000000000000010

y=3; //0000000000000011

z= x^y; //0000000000000001

cout<<z; //1

Операция поразрядное ИЛИ формирует результат, каждый разряд которого равен 1 тогда, когда хотя бы у одного из операндов соответствующий разряд 1.

Пример:

unsigned short x, y, z;

x=2; //0000000000000010

y=3; //0000000000000011

z= x|y; //0000000000000011

cout<<z; //3

Пример программы получения значение i-разряда целого числа (разряды нумеруются справа налево и нумерация начинается с 0):

#include <iostream.h>

#include <conio.h>

void main()

{

int i; //номер разряда

int x, y; //вводимое число и значение i-разряда

cout<<”x? “; cin>>x;

cout<<”i? “; cin>>i;

y=x>>i & 1;

cout<<”y=”<<y;

getch();

}

Тест:

х=5 (0000000000000101), i=2           у: 1

 

2.2.6. Вычисление выражений

 

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

В языке С++ допускается в выражениях использовать операнды разных типов. Например, можно складывать два числа, одно из которых 16-разрядное, а другое 32-разрядное или одно целое, а другое вещественное. В этом случае перед вычислением выражения происходит автоматическое преобразование операндов к одному типу (неявное преобразование типов): более короткий тип преобразуется к более длинному, целый операнд преобразуется к вещественному. Преобразование очень естественно и выполняется таким образом, чтобы при вычислениях  сохранить значимые разряды операндов и их точность. Исключением из этого правила являются операции присваивания, в которых всегда тип правого операнда преобразуется к типу левого операнда. При этом может происходить потеря точности и значимости (без выдачи сообщений). Полностью правила преобразования типов операндов приведены в [1, 2].

Примеры присваиваний:

int a=32768;

short b;

float c=1.2;

char z;

b=a; cout<<b<<endl; //-32768, потеря значимости

a=c;  cout<<a<<endl; //1, потеря точности

c=a; cout<<c<<endl; //1

z=65; cout<<z<<endl; //А

Иногда при записи выражений требуется вместо неявного преобразования типов использовать явное преобразование. Например, необходимо найти среднее арифметическое значение нескольких целых чисел. Для таких случаев в языке С++ предусмотрены операции явного приведения типа. Существует две формы операции приведения типа:

• каноническая форма: (тип) операнд;
• функциональная форма: тип (операнд).

Пример программы, вычисляющей среднее арифметическое трех целых чисел:

#include <iostream.h>

#include <conio.h>

void main()

{

int a, b, c;

float avg; //среднее арифметическое

cout<<”a, b, c? “;

cin>>a>>b>>c;

avg= float(a+b+c)/3;

cout<<”avg=“<<avg;

getch();

}

Тест:

a=4, b=5, c=4     результат: 4.3333