Конспект лекций по курсу Алгоритмические языки и программирование Основы языка С++

Министерство образования Российской Федерации

Пермский Государственный технический университет

Кафедра информационных технологий и автоматизированных систем

Викентьева О. Л.

Конспект лекций по курсу «Алгоритмические языки и программирование»

(Основы языка С++, I семестр)

Пермь 2003

Введение

В первом семестре рассматриваются основные конструкции языка Си и базовая технология программирования (структурное программирование).

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

Алгоритм и программа

      Совокупность средств и правил для представления алгоритма в виде пригодном для выполнения вычислительной машиной…

Свойства алгоритма

2. Результативность: алгоритм должен приводить к получению результата за конкретное число шагов ( при делении 1 на 3 получается периодическая дробь… 3. Определенность (детерминированность) – каждое действие алгоритма должно… 4. Дискретность – процесс должен быть описан с помощью неделимых операций, выполняемых на каждом шаге (т. е. шаги…

Компиляторы и интерпретаторы

С помощью языка программирования создается текст, описывающий ранее составленный алгоритм. Чтобы получить работающую программу, надо этот текст перевести в последовательность команд процессора, что выполняется при помощи специальных программ, которые называются трансляторами. Трансляторы бывают двух видов: компиляторы и интерпретаторы. Компилятор транслирует текст исходного модуля в машинный код, который называется объектным модулем за один непрерывный процесс. При этом сначала он просматривает исходный текст программы в поисках синтаксических ошибок. Интерпретатор выполняет исходный модуль программы в режиме оператор за оператором, по ходу работы, переводя каждый оператор на машинный язык.

Языки программирования

Языки программирования высокого уровня не учитывают особенности конкретных компьютерных архитектур, поэтому создаваемые программы на уровне исходных… Языками высокого уровня являются: 1. Фортран – первый компилируемый язык, созданный в 50-е годы 20 века. В нем были реализован ряд важнейших понятий…

Состав языка

       

Тип int

Размер типа int не определяется стандартом, а зависит от компьютера и компилятора. Для 16-разрядного процессора под него отводится 2 байта, для… Если перед int стоит спецификатор short, то под число отводится 2 байта, а… short int - занимает 2 байта, следовательно, имеет диапазон –32768 ..+32767;

Тип char

Значениями этого типа являются элементы конечного упорядоченного множества символов. Каждому символу ставится в соответствие число, которое называется кодом символа. Под величину символьного типа отводится 1 байт. Тип char может использоваться со спецификаторами signed и unsigned. В данных типа signed char можно хранить значения в диапазоне от –128 до 127. При использовании типа unsigned char значения могут находиться в диапазоне от 0 до 255. Для кодировки используется код ASCII(American Standard Code foe International Interchange). Символы с кодами от 0 до 31 относятся к служебным и имеют самостоятельное значение только в операторах ввода-вывода.

Величины типа char также применяются для хранения чисел из указанных диапазонов.

Тип wchar_t

Предназначен для работы с набором символов, для кодировки которых недостаточно 1 байта, например Unicode. Размер этого типа, как правило, соответствует типу short. Строковые константы такого типа записываются с префиксом L: L“String #1”.

Тип bool

Тип bool называется логическим. Его величины могут принимать значения true и false. Внутренняя форма представления false – 0, любое другое значение интерпретируется как true.

Типы с плавающей точкой.

Внутреннее представление вещественного числа состоит из 2 частей: мантиссы и порядка. В IBM-совместимых ПК величины типа float занимают 4 байта, из которых один разряд отводится под знак мантиссы, 8 разрядов под порядок и 24 – под мантиссу.

Величины типы double занимают 8 байтов, под порядок и мантиссу отводятся 11 и 52 разряда соответственно. Длина мантиссы определяет точность числа, а длина порядка его диапазон.

Если перед именем типа double стоит спецификатор long, то под величину отводится байтов.

Тип void

К основным типам также относится тип void Множество значений этого типа – пусто.

Переменные

int a; float x; Общий вид оператора описания: [класс памяти][const]тип имя [инициализатор];

Выражения

Приоритеты операций в выражениях Ранг Операции ( ) [ ] -> . ! ~ - ++ -- & * (тип)…    

Ввод и вывод данных

Для ввода/вывода данных в стиле Си используются функции, которые описываются в библиотечном файле stdio.h. 1) printf ( форматная строка, список аргументов); форматная строка - строка символов, заключенных в кавычки, которая показывает, как должны быть напечатаны аргументы.…

Базовые конструкции структурного программирования

Линейной называется конструкция, представляющая собой последовательное соединение двух или более операторов. Ветвление – задает выполнение одного из двух операторов, в зависимости от… Цикл – задает многократное выполнение оператора. Следование Ветвление Цикл …

Составные операторы

К составным операторам относят собственно составные операторы и блоки. В обоих случаях это последовательность операторов, заключенная в фигурные скобки. Блок отличается от составного оператора наличием определений в теле блока. Например:

{

n++; это составной оператор

summa+=n;

}

 

{

int n=0;

n++; это блок

summa+=n;

}

 

Операторы выбора

Операторы выбора - это условный оператор и переключатель.

1. Условный оператор имеет полную и сокращенную форму.

if (выражение-условие ) оператор; //сокращенная форма

В качестве выражения-условия могут использоваться арифметическое выражение, отношение и логическое выражение. Если значение выражения-условия отлично от нуля (т. е. истинно), то выполняется оператор. Например:

if (x<y&&x<z)min=x;

if ( выражение-условие ) оператор1; //полная форма

else оператор2;

Если значение выражения-условия отлично от нуля, то выполняется оператор1, при нулевом значении выражения-условия выполняется оператор2.Например:

if (d>=0)

{

x1=(-b-sqrt(d))/(2*a);

x2=(-b+sqrt(d))/(2*a);

cout<< “nx1=”<<x1<<“x2=”<<x2;

}

else cout<<“nРешения нет”;

2.Переключатель определяет множественный выбор.

switch (выражение)

{

case константа1 : оператор1 ;

case константа2 : оператор2 ;

. . . . . . . . . . .

[default: операторы;]

}

При выполнении оператора switch, вычисляется выражение, записанное после switch, оно должно быть целочисленным. Полученное значение последовательно сравнивается с константами, которые записаны следом за case. При первом же совпадении выполняются операторы помеченные данной меткой. Если выполненные операторы не содержат оператора перехода, то далее выполняются операторы всех следующих вариантов, пока не появится оператор перехода или не закончится переключатель. Если значение выражения, записанного после switch не совпало ни с одной константой, то выполняются операторы, которые следуют за меткой default. Метка default может отсутствовать.

Пример:

#include <iostream.h>

void main()

{

int i;

cout<<"nEnter the number";

cin>>i;

switch(i)

{

case 1:cout<<"nthe number is one";

case 2:cout<<"n2*2="<<i*i;

case 3: cout<<"n3*3="<<i*i;break;

case 4: cout<<"n"<<i<<" is very beautiful!";

default:cout<<"nThe end of work";

}

}

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

1. При вводе 1 будет выведено:

The number is one

2*2=1

3*3=1

2. При вводе 2 будет выведено:

2*2=4

3*3=4

3. При вводе 3 будет выведено:

3*3=9

4. При вводе 4 будет выведено:

4 is very beautiful!

5. При вводе всех остальных чисел будет выведено:

The end of work

Операторы циклов

Различают:

1) итерационные циклы;

2) арифметические циклы.

Группа действий, повторяющихся в цикле, называется его телом. Однократное выполнение цикла называется его шагом.

В итерационных циклах известно условие выполнения цикла.

1. Цикл с предусловием:

while (выражение-условие)

оператор;

В качестве <выражения-условия> чаще всего используется отношение или логическое выражение. Если оно истинно, т. е. не равно 0, то тело цикла выполняется до тех пор, пока выражение-условие не станет ложным.

Пример

while (a!=0)

{

cin>>a;

s+=a;

}

2. Цикл с постусловием:

do

оператор

while (выражение-условие);

Тело цикла выполняется до тех пор, пока выражение-условие истинно.

Пример:

do

{

cin>>a;

s+=a;

}

while(a!=0);

 

3. Цикл с параметром:

for ( выражение_1;выражение-условие;выражение_3)

оператор;

выражение_1 и выражение_3 могут состоять из нескольких выражений, разделенных запятыми. Выражение_1 - задает начальные условия для цикла (инициализация). Выражение-условие> определяет условие выполнения цикла, если оно не равно 0, цикл выполняется, а затем вычисляется значение выражения_3. Выражение_3 - задает изменение параметра цикла или других переменных (коррекция). Цикл продолжается до тех пор, пока выражение-условие не станет равно 0. Любое выражение может отсутствовать, но разделяющие их « ; » должны быть обязательно.

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

1) Уменьшение параметра:

for ( n=10; n>0; n--)

{ оператор};

2) Изменение шага корректировки:

for ( n=2; n>60; n+=13)

{ оператор };

3) Возможность проверять условие отличное от условия, которое налагается на число итераций:

for ( num=1;num*num*num<216; num++)

{ оператор };

4) Коррекция может осуществляться не только с помощью сложения или вычитания:

for ( d=100.0; d<150.0;d*=1.1)

{ <тело цикла>};

for (x=1;y<=75;y=5*(x++)+10)

{ оператор };

5) Можно использовать несколько инициализирующих или корректирующих выражений:

for (x=1, y=0; x<10;x++;y+=x);

 

Операторы перехода

Операторы перехода выполняют безусловную передачу управления.

1) break - оператор прерывания цикла.

{

< операторы>

if (<выражение_условие>) break;

<операторы>

}

Т. е. оператор break целесообразно использовать, когда условие продолжения итераций надо проверять в середине цикла.

Пример:

// ищет сумму чисел вводимых с клавиатуры до тех пор, пока не будет введено 100 чисел или 0

for(s=0, i=1; i<100;i++)

{

cin>>x;

if( x==0) break; // если ввели 0, то суммирование заканчивается

s+=x;

}

2) continue - переход к следующей итерации цикла. Он используется, когда тело цикла содержит ветвления.

Пример:

//ищет количество и сумму положительных чисел

for( k=0,s=0,x=1;x!=0;)

{

cin>>x;

if (x<=0) continue;

k++;s+=x;

}

3) Оператор goto

Оператор goto имеет формат: goto метка;

В теле той же функции должна присутствовать конструкция: метка:оператор;

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

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

Нельзя передавать управление внутрь операторов if, switch и циклов. Нельзя переходить внутрь блоков, содержащих инициализацию, на операторы, которые стоят после инициализации. Пример:

int k;

goto m;

. . .

{

int a=3,b=4;

k=a+b;

m: int c=k+1;

. . .

}

В этом примере при переходе на метку m не будет выполняться инициализация переменных a , b и k.

4) Оператор return – оператор возврата из функции. Он всегда завершает выполнение функции и передает управление в точку ее вызова. Вид оператора:

return [выражение];

5. Примеры решения задач с использованием основных операторов Си++

«Начинающие программисты, особенно студенты, часто пишут программы так: получив задание, тут же садятся за компьютер и начинают кодировать те фрагменты алгоритма, которые им удается придумать сразу. Переменным дают первые попавшиеся имена типа х и у. Когда компьютер зависает, делается перерыв, после которого все написанное стирается, и все повторяется заново. Периодически высказываются сомнения в правильности работы компилятора, компьютера и операционной системы. Когда программа доходит до стадии выполнения, в нее вводятся произвольные значения, после чего экран становится объектом пристального удивленного изучения. «Работает» такая программа обычно только в бережных руках хозяина на одном наборе данных, а внесение в нее изменений может привести автора к потере веры в себя и ненависти к процессу программирования.

Ваша задача состоит в том, чтобы научиться подходить к программированию профессионально. В конце концов, профессионал отличается тем, что может достаточно точно оценить, сколько времени у него займет написание программы, которая будет работать в полном соответствии с поставленной задачей. Кроме «ума, вкуса и терпения», для этого требуется опыт, а также знание основных принципов, выработанных программистами в течение более, чем полувека развития этой дисциплины. Даже к написанию самых простых программ нужно подходить последовательно, соблюдая определенную дисциплину.» (Павловская Т. А., стр.109)

Решение задач по программированию предполагает ряд этапов:

1) Разработка математической модели. На этом этапе определяются исходные данные и результаты решения задачи, а также математические формулы, с помощью которых можно перейти от исходных данных к конечному результату.

2) Разработка алгоритма. Определяются действия, выполняя которые можно будет от исходных данных придти к требуемому результату.

3) Запись программы на некотором языке программирования. На этом этапе каждому шагу алгоритма ставится в соответствие конструкция выбранного алгоритмического языка.

4) Выполнение программы (исходный модуль ->компилятор ->объектный модуль -> компоновщик -> исполняемый модуль)

5) Тестирование и отладка программы. При выполнении программы могут возникнуть ошибки 3 типов:

a. синтаксические – исправляются на этапе компиляции;

b. ошибки исполнения программы (деление на 0, логарифм от отрицательного числа и т. п.) – исправляются при выполнении программы;

c. семантические (логические) ошибки – появляются из-за неправильно понятой задачи, неправильно составленного алгоритма.

Чтобы устранить эти ошибки программа должна быть выполнена на некотором наборе тестов. Цель процесса тестирования – определение наличия ошибки, нахождение места ошибки, ее причины и соответствующие изменения программы – исправление. Тест – это набор исходных данных, для которых заранее известен результат. Тест выявивший ошибку считается успешным. Отладка программы заканчивается, когда достаточное количество тестов выполнилось неуспешно, т. е. программа на них выдала правильные результаты.

Для определения достаточного количества тестов существует два подхода. При первом подходе программа рассматривается как «черный ящик», в который передают исходные данные и получают результаты. Устройство самого ящика неизвестно. При этом подходе, чтобы осуществить полное тестирование, надо проверить программу на всех входных данных, что практически невозможно. Поэтому вводят специальные критерии, которые должны показать, какое конечное множество тестов является достаточным для программы. При первом подходе чаще всего используются следующие критерии:

1) тестирование классов входных данных, т. е. набор тестов должен содержать по одному представителю каждого класса данных:

X					-1		-1
Y						-1	-1

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

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

1) Тестирование команд. Набор тестов должен обеспечивать прохождение каждой команды не менее одного раза.

2) Тестирование ветвей. Набор тестов в совокупности должен обеспечивать прохождение каждой ветви не менее одного раза. Это самый распространенный критерий в практике программирования.

Программирование ветвлений

                -3    

Программирование арифметических циклов.

Задача №2 Дана последовательность целых чисел из n элементов. Найти среднее… #include <iostream.h>

Итерационные циклы

Задача №5 Дана последовательность целых чисел, за которой следует 0. Найти минимальный… #include <iostream.h>

Вложенные циклы

Задача №7: Напечатать N простых чисел.

#include<iostream.h>

void main()

{

int a=1,n,d;

cout<<"nEnter N";

cin>>n;

for(int i=0;i<n;)//внешний цикл

{

a++;d=1;

do //внутренний цикл

{

d++;

}

while(a%d!=0);//конец внутреннего цикла

if(a==d){

cout<<a<<" ";

i++;}

 

}//конец внешнего цикла

}

 

Массивы

- массив элементов заданного типа; - указатель на объект заданного типа; - функция, возвращающая значение заданного типа.

Обработка одномерных массивов

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

Перебор элементов массива характеризуется:

- направлением перебора;

- количеством одновременно обрабатываемых элементов;

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

По направлению перебора массивы обрабатывают :

- слева направо (от начала массива к его концу);

- справа налево (от конца массива к началу);

- от обоих концов к середине.

Индексы могут меняться

- линейно (с постоянным шагом);

- нелинейно (с переменным шагом).

Перебор массива по одному элементу

Элементы можно перебирать:

1) Слева направо с шагом 1, используя цикл с параметром

for(int I=0;I<n;I++){обработка a[I];}

2) Слева направо с шагом отличным от 1, используя цикл с параметром

for (int I=0;I<n;I+=step){обработка a[I];}

3) Справа налево с шагом 1, используя цикл с параметром

for(int I=n-1;I>=0;I--){обработка a[I];}

4) Справа налево с шагом отличным от 1, используя цикл с параметром

for (int I=n-1;I>=0;I-=step){обработка a[I];}

 

Формирование псевдодинамических массивов

Псевдодинамические массивы реализуются следующим образом: 1) при определении массива выделяется достаточно большое количество памяти: … const int MAX_SIZE=100;//именованная константа

Найти максимальный элемент массива.

#include<stdlib.h> void main() {

Перебор массива по два элемента

1) Элементы массива можно обрабатывать по два элемента, двигаясь с обеих сторон массива к его середине:
int I=0, J=N-1;
while( I<J)

{обработка a[I] и a[J];I++;J--;}

 

2) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 1(т. е. обрабатываются пары элементов a[1]и a[2], a[2]и a[3] и т. д.):
for (I=1;I<N;I++)
{обработка a[I] и a[I+1]}

3) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 2 (т. е. обрабатываются пары элементов a[1]и a[2], a[3]и a[4] и т. д.)
int I=1;
while (I<N-1 )
{обработка a[I] и a[I+1];
I+=2;}

 

Классы задач по обработке массивов

1) К задачам 1 класса относятся задачи, в которых выполняется однотипная обработка всех или указанных элементов массива.

2) К задачам 2 класса относятся задачи, в которых изменяется порядок следования элементов массива.

3) К задачам 3 класса относятся задачи, в которых выполняется обработка нескольких массивов или подмассивов одного массива. Массивы могут обрабатываться по одной схеме – синхронная обработка или по разным схемам – асинхронная обработка массивов.

4) К задачам 4 класса относятся задачи, в которых требуется отыскать первый элемент массива, совпадающий с заданным значением – поисковые задачи в массиве.

Задачи 1-ого класса

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

#include<iostream.h>

#include<stdlib.h>

void main()

{

int a[100];

int n;

cout<<”nEnter the size of array:”;cin>>n;

for(int I=0;I<n;I++)

{a[I]=rand()%100-50;

cout<<a[I]<<” “;

}

int Sum=0;

for(I=0;I<n;I++)

Sum+=a[I];

Cout<<”Среднее арифметическое=”<<Sum/n”;

}

Задачи 2-ого класса

Обмен элементов внутри массива выполняется с использованием вспомогательной переменной:
int R=a[I];a[I]=a[J]; a[J]:=R; // обмен a[I] и a[J] элементов массива.

Пример1.

Перевернуть массив.

//формирование массива

for(int i=0,j=n-1;i<j;i++,j--)

{int r=a[i];

a[i]=a[j];

a[j]=r;}

//вывод массива

Пример 2.

Поменять местами пары элементов в массиве: 1и2, 3 и 4, 5 и 6 и т. д.

for(int i=0;i<n-1;i+=2)

{int r=a[i];

a[i]=a[i+1];

a[i+1]=r;}

Пример 3.

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

int k,i,t,r;

cout<<"nK=?";cin>>k;

 

for(t=0;t<k;t++)

{

r=a[0];

for(int i=0;i<n-1;i++)

a[i]=a[i+1];

a[n-1]=r;

}

Задачи 3-ого класса

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

Пример 1. Заданы два массива из n целых элементов. Получить массив c, где c[I]=a[I]+b[I].

For(int I=0;I<n;I++)c[I]=a[I]+b[I];

При асинхронной обработке массивов индекс каждого массива меняется по своей схеме.

Пример 2. В массиве целых чисел все отрицательные элементы перенести в начало массива.

int b[10];//вспомогательный массив

int i,j=0;

for(i=0;i<n;i++)

if(a[i]<0){b[j]=a[i];j++;}//переписываем из а в b все отрицательные элементы

for(i=0;i<n;i++)

if(a[i]>=0){b[j]=a[i];j++;}// переписываем из а в b все положительные элементы

for(i=0;i<n;i++) cout<<b[I]<<” “;

Пример3.

Удалить из массива все четные числа

int b[10];

int i,j=0;

for(i=0;i<n;i++)

if(a[i]%2!=0){b[j]=a[i];j++;}

 

for(i=0;i<j;i++) cout<<b[i]<<" ";

cout<<"n";

Задачи 4-ого класса

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

- нужный элемент найден ;

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

Пример1. Найти первое вхождение элемента К в массив целых чисел.

int k;

cout<<"nK=?";cin>>k;

int ok=0;//признак найден элемент или нет

int i,nom;

for(i=0;i<n;i++)

if(a[i]==k){ok=1;nom=i;break;}

if(ok==1)

cout<<"nnom="<<nom;

else

cout<<"nthere is no such element!";

Сортировка массивов

Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.

Сортировки массивов подразделяются по быстродействию. Существуют простые методы сортировок, которые требуют n*n сравнений, где n – количество элементов массива и быстрые сортировки, которые требуют n*ln(n) сравнений. Простые методы удобны для объяснения принципов сортировок, т. к. имеют простые и короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами операции более сложные, поэтому для небольших массивов простые методы более эффективны.

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

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

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

- сортировка методом простого обмена;

Сортировка методом простого включения (вставки)

  В процессе поиска нужного места осуществляются пересылки элементов больше… - если найден элемент a[J]>a[I];

Сортировка методом простого выбора

Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.

		мин

 

int i,min,n_min,j;

for(i=0;i<n-1;i++)

{

min=a[i];n_min=i;//поиск минимального

for(j=i+1;j<n;j++)

if(a[j]<min){min=a[j];n_min=j;}

a[n_min]=a[i];//обмен

a[i]=min;

}

 

Сортировка методом простого обмена

Сравниваются и меняются местами пары элементов, начиная с последнего. В результате самый маленький элемент массива оказывается самым левым элементом массива. Процесс повторяется с оставшимися элементами массива.

				94

 

for(int i=1;i<n;i++)

for(int j=n-1;j>=i;j--)

if(a[j]<a[j-1])

{int r=a[j];a[j]=a[j-1];a[j-1]=r;}

}

 

Поиск в отсортированном массиве

Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Т .к. массив упорядочен, то если a[S]<X, то… L S R S=(L+R)/2=4

Указатели

Понятии указателя

Пример: Когда компилятор обрабатывает оператор определения переменной, например, int i=10;, то в памяти выделяется участок памяти в соответствии с…     а

Динамические переменные

Для работы с динамической памятью используют указатели. С их помощью осуществляется доступ к участкам динамической памяти, которые называются… Для создания динамических переменных используют операцию new, определенную в… указатель = new имя_типа[инициализатор];

Операции с указателями

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

1) разыменование (*);

2) присваивание;

3) арифметические операции (сложение с константой, вычитание,
инкремент ++, декремент --);

4) сравнение;

5) приведение типов.

1) Операция разыменования предназначена для получения значения переменной или константы, адрес которой хранится в указателе. Если указатель указывает на переменную, то это значение можно изменять, также используя операцию разыменования.

Примеры:

int a; //переменная типа int

int*pa=new int; //указатель и выделение памяти под динамическую переменную

*pa=10;//присвоили значение динамической переменной, на которую указывает указатель

a=*pa;//присвоили значение переменной а

Присваивать значение указателям-константам запрещено.

2) Приведение типов

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

int a=123;

int*pi=&a;

char*pc=(char*)&a;

float *pf=(float*)&a;

printf("n%xt%i",pi,*pi);

printf("n%xt%c",pc,*pc);

printf("n%xt%f",pf,*pf);

При выполнении этой программы получатся следующие результаты:

66fd9c 123

66fd9c {

66fd9c 0.000000

Т. е. адрес у трех указателей один и тот же, но при разыменовании получаются разные значения в зависимости от типа указателя.

В примере при инициализации указателя была использована операция приведения типов. При использовании в выражении указателей разных типов, явное преобразование требуется для всех типов, кроме void*. Указатель может неявно преобразовываться в значения типа bool, при этом ненулевой указатель преобразуется в true, а нулевой в false.

3) Арифметические операции применимы только к указателям одного типа.

- Инкремент увеличивает значение указателя на величину sizeof(тип).

Например:

char *pc;

int *pi;

float *pf;

. . . . .

pc++;//значение увеличится на 1

pi++;//значение увеличится на 4

pf++;//значение увеличится на 4

- Декремент уменьшает значение указателя на величину sizeof(тип).

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

Например:

int a=123,b=456,c=789;

int*pi1=&a;

int *pi2=&b;

int*pi3=&c;

printf("n%x",pi1-pi2);

printf("n%x",pi1-pi3);

Результат

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

Можно суммировать указатель и константу:

pi3=pi3+2;

pi2=pi2+1;

printf("n%xt%d",pi1,*pi1);

printf("n%xt%d",pi2,*pi2);

printf("n%xt%d",pi3,*pi3);

Результат выполнения программы:

66fd9c 123

66fd9c 123

66fd9c 123

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

 

1. Ссылки

Понятие ссылки

Ссылка – это синоним имени объекта, указанного при инициализации ссылки.

Формат объявления ссылки

тип & имя =имя_объекта;

Примеры:

int x;// определение переменной

int& sx=x;// определение ссылки на переменную х

const char& CR=’n’;//определение ссылки на константу

8.1. Правила работы со ссылками:

1) Переменная ссылка должна явно инициализироваться при ее описании, если она не является параметром функции, не описана как extern или не ссылается на поле класса.

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

3) Не существует указателей на ссылки, массивов ссылок и ссылок на ссылки.

4) Операция над ссылкой приводит к изменению величины на которую она ссылается

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

Пример1:

#include <iostream.h>

void main()

{

int I=123;

int &si=I;

cout<<”ni=”<<I<<” si=”<<si;

I=456;

cout<<”ni=”<<I<<” si=”<<si;

I=0; cout<<”ni=”<<I<<” si=”<<si;

}

 

Выведется

I=123 si=123

I=456 si=456

I=0 si=0

 

Указатели и массивы

Одномерные массивы и указатели

Примеры: int a[100]; int k=sizeof(a);// результатом будет 4*100=400 (байтов).

Многомерные массивы и указатели

  *(a+1) – адрес строки массива с номером 1 int…     Элементы типа *int

Динамические массивы

new тип_массива Такая операция выделяет для размещения массива участок динамической памяти… Примеры:

Символьная информация и строки

Примеры: const char c=’c’; //символ – занимает один байт, его значение не меняется char a,b;//символьные переменные, занимают по одному байту, значения меняются

Объявление и определение функций

Функция, во-первых, является одним из производных типов СИ++, а ,во-вторых, минимальным исполняемым модулем программы.    

Прототип функции

double line(double x1,double y1,double x2,double y2); double square(double a, double b, double c); bool triangle(double a, double b, double c);

Параметры функции

При передаче по значению выполняются следующие действия: - вычисляются значения выражений, стоящие на месте фактических параметров; … - в стеке выделяется память под формальные параметры функции;

Локальные и глобальные переменные

int*f() { int a;

Функции и массивы

Передача одномерных массивов как параметров функции

Пример1: Удалить из массива все четные элементы #include <iostream.h>

Передача строк в качестве параметров функций

Строки при передаче в функции могут передаваться как одномерные массивы типа char или как указатели типа char*. В отличие от обычных массивов в функции не указывается длина строки, т. к. в конце строки есть признак конца строки /0.

Пример: Функция поиска заданного символа в строке

int find(char *s,char c)

{

for (int I=0;I<strlen(s);I++)

if(s[I]==c) return I;

return –1

}

С помощью этой функции подсчитаем количество гласных букв в строке.

void main()

{

char s[255];

gets(s)

char gl=”aouiey”;

for(int I=0,k=0;I<strlen(gl);I++)

if(find(s,gl[I])>0)k++;

printf(“%d”,k);

}

 

 

Передача многомерных массивов в функцию

Пример: Транспонирование квадратной матрицы Если определить заголовок функции: void transp(int a[][],int n){…..} – то получится, что мы хотим передать в функцию массив с неизвестными размерами. По…

Функции с начальными (умалчиваемыми) значениями параметров

Пример: void print(char*name=”Номер дома: ”,int value=1) {cout<<”n”<<name<<value;}

Подставляемые (inline) функции

Например: inline float Line(float x1,float y1,float x2=0, float y2=0) {return sqrt(pow(x1-x2)+pow(y1-y2,2));}//функция возвращает расстояние от точки с координатами(x1,y1)(по умолчанию…

Функции с переменным числом параметров

тип имя (явные параметры,. . . ) {тело функции } После списка обязательных параметров ставится запятая, а затем многоточие, которое показывает, что дальнейший контроль…

Перегрузка функций

Пример. #include<iostream.h> #include <string.h>

Шаблоны функций

template <class имя_типа [,class имя_типа]> заголовок_функции {тело функции}

Указатель на функцию

тип_функции(*имя_указателя)(спецификация параметров) Примеры: 1. int f1(char c){. . . . }//определение функции

Void f1()

{cout<<"nThe end of work";exit(0);}

Void f2()

{cout<<"nThe work #1";}

Void f3()

{cout<<"nThe work #2";}

Void main()

{

void(*fptr[])()={f1,f2,f3};

Int n;

while(1)//бесконечный цикл

{

cout<<"n Enter the number";

cin>>n;

fptr[n]();//вызов функции с номером n

}

}

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

Пример.

#include <iostream.h>

#include <math.h>

typedef float(*fptr)(float);//тип – указатель на функцию

float root(fptr f, float a, float b, float e)//решение уравнения методом половинного деления

//уравнение передается с помощью указателя на функцию

{float x;

do

{

x=(a+b)/2;

if ((*f)(a)*f(x)<0)b=x; else a=x;

}

while((*f)(x)>e&&fabs(a-b)>e);

return x;

}

float testf(float x)

{return x*x-1;}

void main()

{

float res=root(testf,0,2,0.0001);

cout<<”nX=”<<res;

}

 

Ссылки на функцию

Подобно указателю на функцию определяется и ссылка на функцию:

тип_функции(&имя_ссылки)(параметры) инициализирующее_выражение;

Пример.

int f(float a,int b){. . . }//определение функции

int(&fref)(float,int)=f;//определение ссылки

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

Пример.

#include <iostream.h>

void f(char c)

{cout<<”n”<<c;}

void main()

{

void (*pf)(char);//указатель на функцию

void(&rf)(char);//ссылка на функцию

f(‘A’);//вызов по имени

pf=f;//указатель ставится на функцию

(*pf)(‘B’);//вызов с помощью указателя

rf(‘C’);//вызов по ссылке

}

 

 

 

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

Переименование типов

Типу можно задавать имя с помощью ключевого слова typedef:

typedef тип имя_типа [размерность];

Примеры:

typedef unsigned int UNIT;

typedef char Msg[100];

Такое имя можно затем использовать также как и стандартное имя типа:

UNIT a,b,c;//переменные типа unsigned int

Msg str[10];// массив из 10 строк по 100 символов

 

Перечисления

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

enum [имя_типа] {список констант};

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

Пример:

Enum Err{ErrRead, ErrWrite, ErrConvert);

Err error;

. . . .

switch(error)

{

case ErrRead: …..

case ErrWrite: …..

case ErrConvert: …..

}

Структуры

Форматы определения структурного типа следующие: 1. struct имя_типа //способ 1 {

Инициализация структур.

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

Примеры:

1. struct Student

{

char name[20];

int kurs;

float rating;

};

Student s={”Иванов”,1,3.5};

2. struct

{

char name[20];

char title[30];

float rate;

}employee={“Петров", “директор”,10000};

Работа со структурами

Присваивание структур

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

Student ss=s;

Доступ к элементам структур

Доступ к элементам структур обеспечивается с помощью уточненных имен:

Имя_структуры.имя_элемента

employee.name – указатель на строку «Петров»;

employee.rate – переменная целого типа со значением 10000

Пример:

#include <iostream.h>

void main()

{

struct Student

{

char name[30];

char group[10];

float rating;

};

Student mas[35];

//ввод значений массива

for(int i=0;i<35;i++)

{

cout<<”nEnter name:”;cin>>mas[i].name;

cout<<”nEnter group:”;cin>>mas[i].group;

cout<<”nEnter rating:”;cin>>mas[i].rating;

}

cout<<”Raitng <3:”;

for( i=0;i<35;i++)

if(mas[i].name<3)

cout<<”n”<<mas[i].name;

}

Указатели на структуры

Указатели на структуры определяются также как и указатели на другие типы.

Student*ps;

Можно ввести указатель для типа struct, не имеющего имени (способ 2):

Struct

{

char *name;

int age;

} *person;//указатель на структуру

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

Student *ps=&mas[0];

Указатель на структуру обеспечивает доступ к ее элементам 2 способами:

1.(*указатель).имя_элемента

2. указатель->имя_элемента

cin>>(*ps).name;

cin>>ps->title;

Битовые поля

Битовые поля – это особый вид полей структуры. При описании битового поля указывается его длина в битах (целая положительная константа).

Пример:

struct {

int a:10;

int b:14}xx,*pxx;

. . . .

xx.a=1;

pxx=&xx;

pxx->b=8;

 

Битовые поля могут быть любого целого типа. Они используются для плотной упаковки данных. Например, с их помощью удобно реализовать флажки типа «да» / «нет».

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

Объединения

Пример union{ char s[10];

Динамические структуры данных

- линейные списки; - стеки; - очереди;

Линейный однонаправленный список

struct имя_типа { информационное поле;

Работа с двунаправленным списком

Рис. 6 Двунаправленный список  

Ввод-вывод в С

Файл – это именованная область внешней памяти. Файл имеет следующие характерные особенности:

1. имеет имя на диске, что дает возможность программам работать с несколькими файлами;

2. длина файла ограничивается только емкостью диска.

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

Библиотека С поддерживает три уровня ввода-вывода:

- потоковый ввод-вывод;

- ввод-вывод нижнего уровня;

- ввод-вывод для консоли портов (зависит от конкретной ОС).

Рассмотрим потоковый ввод-вывод.

Потоковый ввод-вывод

1. Открывать и закрывать потоки (при этом указатели на поток связываются с конкретными файлами); 2. Вводить и выводить строки, символы, форматированные данные, порции данных… 3. Управлять буферизацией потока и размером буфера;

Открытие и закрытие потока

#include <stdio.h> . . . . . . . . FILE*f;//указатель на поток

Стандартные файлы и функции для работы с ними

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

- стандартный поток ввода (stdin);

- стандартный поток вывода (stdout);

- стандартный поток вывода об ошибках (stderr).

По умолчанию stdin ставится в соответствие клавиатура, а потокам stdout и stderr - монитор. Для ввода-вывода с помощью стандартных потоков используются функции:

- getchar()/putchar() – ввод-вывод отдельного символа;

- gets()/puts() – ввод-вывод строки;

- scanf()/printf() – форматированный ввод/вывод.

Функции рассматривались, когда мы рассматривали строковые и символьные данные. Теперь мы можем связать их со стандартными потоками: ввод осуществляется из стандартного потока stdin вывод осуществляется в стандартный поток stdout. Аналогично работе со стандартными потоками выполняется ввод-вывод в потоки, связанные с файлами.

Символьный ввод-вывод

- int fgetc(FILE*fp), где fp – указатель на поток, из которого выполняется считывание. Функция возвращает очередной символ в форме int из потока fp.… - int fputc(int c, FILE*fp), где fp – указатель на поток, в который… Пример:

Строковый ввод-вывод

1) char* fgets(char* s,int n,FILE* f), где char*s – адрес, по которому размещаются считанные байты, int n – количество считанных байтов,

Блоковый ввод-вывод

1) int fread(void*ptr,int size, int n, FILE*f), где void*ptr – указатель на область памяти, в которой размещаются считанные из… int size – размер одного считываемого элемента,

Форматированный ввод-вывод

1) int fprintf(FILE *f, const char*fmt,. . .) , где FILE*f – указатель на файл, в который производится запись, const char*fmt – форматная строка,

Прямой доступ к файлам

Средства прямого доступа дают возможность перемещать указатель текущей позиции в потоке на нужный байт. Для этого используется функция int fseek(FILE *f, long off, int org), где FILE *f - – указатель на файл,

Удаление и добавление элементов в файле

void del(char *filename) { //удаление записи с номером х

Вопросы к экзамену.

1. Алгоритм и его свойства. Способы записи алгоритма. Программа. Языки программирования. Примеры алгоритмов и программ.

2. Структура программы на языке С++. Примеры. Этапы создания исполняемой программы.

3. Состав языка С++. Константы и переменные С++.

4. Типы данных в С++.

5. Выражения. Знаки операций.

6. Основные операторы С++ (присваивание, составные, выбора, циклов, перехода). Синтаксис, семантика, примеры

7. Этапы решения задачи. Виды ошибок. Тестирование.

8. Массивы (определение, инициализация, способы перебора).

9. Сортировка массивов (простой обмен, простое включение, простой выбор).

10. Поиск в одномерных массивах (дихотомический и линейный).

11. Указатели. Операции с указателями. Примеры

12. Динамические переменные. Операции new и delete. Примеры.

13. Ссылки. Примеры.

14. Одномерные массивы и указатели. Примеры.

15. Многомерные массивы и указатели. Примеры.

16. Динамические массивы. Примеры.

17. Символьная информация и строки. Функции для работы со строками (библиотечный файл string.h).

18. Функции ввод-вывода (scanf(), printf(), puts(), gets(), putchar(),getchar()).

19. Функции в С++. Формальные и фактические параметры. Передача параметров по адресу и по значению. Локальные и глобальные переменные. Примеры.

20. Прототип функции. Библиотечные файлы. Директива препроцессора #include.

21. Передача одномерных массивов в функции. Примеры.

22. Передача многомерных массивов в функции. Примеры.

23. Передача строк в функции. Примеры.

24. Функции с умалчиваемыми параметрами. Примеры.

25. Подставляемые функции. Примеры.

26. Функции с переменным числом параметров. Примеры.

27. Перегрузка функции. Шаблоны функций. Примеры.

28. Указатели на функции. Примеры.

29. Ссылки на функции. Примеры.

30. Типы данных, определяемые пользователем (переименование типов, перечисление, структуры, объединения). Примеры.

31. Структуры. Определение, инициализация, присваивание структур, доступ к элементам структур, указатели на структуры, битовые поля структур.

32. Динамические структуры данных (однонаправленные и двунаправленные списки).

33. Создание списка, печать, удаление, добавление элементов (на примере однонаправленных и двунаправленных списков).

34. Потоковый ввод-вывод в С++. Открытие и закрытие потока. Стандартные потоки ввода-вывода.

35. Символьный, строковый, блоковый и форматированный ввод-вывод.

36. Прямой доступ к файлам.

37. Создание бинарных и текстовых файлов, удаление, добавление, корректировка элементов, печать файлов.

 

 

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

1.

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

		-3

 

 

2. Дана последовательность целых чисел из n элементов. Найти:

· - среднее арифметическое;

· - (максимальное значение;

· - количество отрицательных элементов;

· -номер минимального элемента;

· -количество четных чисел;

· - минимальный из четных элементов этой последовательности.

 

3. Дана последовательность целых чисел, за которой следует 0. Найти:

· - среднее арифметическое;

· - (максимальное значение;

· - количество отрицательных элементов;

· -номер минимального элемента;

· -количество четных чисел;

· - минимальный из четных элементов этой последовательности.

4. Найти сумму чисел Фибоначчи, меньших заданного числа Q.

5. Напечатать N простых чисел.

6. Дан массив целых чисел. Найти:

· - среднее арифметическое;

· - (максимальное значение;

· - количество отрицательных элементов;

· -номер минимального элемента;

· -количество четных чисел;

· - минимальный из четных элементов этого массива.

7. Дан массив целых чисел. Перевернуть массив.

8. Дан массив целых чисел. Поменять местами пары элементов в массиве: 1и2, 3 и 4, 5 и 6 и т. д.

9. Циклически сдвинуть массив на К элементов влево (вправо).

10. Найти первое вхождение элемента К в массив целых чисел.

11. Удалить из динамической матрицы строку с номером K.

12. Дана строка символов, состоящая из слов, слова разделены между собой пробелами. Удалить из строки все слова, начинающиеся с цифры.

13. Сформировать динамический массив строк. Удалить из него строку с заданным номером.

14. Заданы координаты сторон треугольника. Если такой треугольник существует, то найти его площадь. Решить задачу с использованием функций.

15. Дан массив int a[100]. Удалить из массива все четные элементы.

16. Дан массив int *a.Удалить из массива все элементы, совпадающие с первым элементом, используя динамическое выделение памяти.

17. Найти количество цифр в строке символов, используя функции.

18. Удалить из однонаправленного (двунаправленного) списка элемент с заданным номером (ключом).

19. Добавить в однонаправленный (двунаправленный) список элемент с заданным номером.

20. Удалить из бинарного файла, в котором записаны целые числа все четные элементы.

21. Добавить в бинарный файл, в который записаны элементы типа

struct Student

{char name[20];int age;};

К элементов после элемента с заданной фамилией.

22. Удалить из текстового файла все четные строки.

23. Добавить порядковый номер в каждую строку текстового файла.

24. struct Date

{сhar Month[15];int Day;}

В файле содержатся даты типа Date. Заменить все даты, у которых поле Month равно “Май”,”Июнь” или ”Июль” на даты, у которых поле Day не меняется а поле Month меняется на “Август”.

25. В текстовом файле заменить все строки, начинающиеся с буквы ‘f’ на строки, начинающиеся с буквы ‘a’.