Полетаев Д.И.

Технология программирования

Конспект лекций

Часть 1. Языки программирования «С», «С++».

Краткая характеристика
Си (англ. C) — стандартизированный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Денисом Ритчи как развитие языка Би. Си был создан для использования в операционной системе UNIX. С тех пор он был портирован на многие другие операционные системы и стал одним из самых используемых языков программирования. Си ценят за его эффективность; он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ. Несмотря на то, что Си не разрабатывался для новичков, он активно используется для обучения программированию. В дальнейшем синтаксис языка Си стал основой для многих других языков.

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

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

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

Си (как и ОС UNIX, с которой он долгое время был связан) создавался программистами и для программистов, круг которых был бы ненамного шире круга разработчиков языка. Несмотря на это, область использования языка значительно шире задач системного программирования.

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

Алфавит

В алфавит языков С, С++ входят:

- прописные и строчные буквы латинского алфавита;

- арабские цифры;

- специальные знаки: “ { } , | [ ] ( ) + - / % \ ; ‘ : ? < = > _ ! & # ~ ^ . *

Некоторые среды разработки, например, Ms Visual Studio 2008, позволяют использовать национальные шрифты, например, кириллицу.

Из символов алфавита формируются следующие лексемы языка.

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

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

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

2. Константы.

3. Знаки операций.

4. Разделители.

Операторы заканчиваются символом «;».

Существуют две формы записи комментариев: однострочные комментарии начинаются составным символом «//», многострочные заключаются между символами «/*» и «*/»;

Примеры:

// Комментарий должен уместиться до конца строки

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

В качестве операторных скобок используются символы «{» и «}».

Объявление переменных. Типы данных

В языке Си среди простых типов присутствуют только числовые. Логический и символьный типы отсутствуют:

– в логических выражениях значению «ложь» соответствует ноль, значению «истина» – любое другое значение;

– символьные константы преобразуются компилятором в коды соответствующих символов;

– любое целое число может быть выведено как соответствующий ему символ.

В простейшем случае переменные объявляются следующим образом:

<тип_данных> <имя_переменной>

int x; bool flag; char s;

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

int a,b,c; //объявление трёх переменных типа int.

При объявлении переменным могут быть присвоены начальные значения:

int a=3, b=4, c; //Переменной «c» начальное значение не задано.

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

Простые типы данных

Существуют три категории простых типов: целые числа, вещественные числа и пустой тип. Стандарт на язык «С++» не определяет диапазоны каждого из типов, но определяет, какой из типов имеет больший диапазон (или точность для вещественных чисел), а какой – меньший. Типы данных будут перечислены от меньшего к большему.

В языке С++ введён дополнительно логический тип, отсутствующий в С.

Целые числа: char, short, int, long, long long.

Вещественные числа: float, double, long double.

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

Логический тип: bool. Принимает одно из двух значений: true или false.

Целочисленные типы данных могут быть как знаковыми, так и беззнаковыми. Для определения, является тип знаковым или беззнаковым, используются ключевые слова signed и unsigned соответственно, которые записываются перед идентификатором типа данного. Если явно не указано, является тип знаковым или беззнаковым, он считается знаковым. Однако, настройки компилятора могут переопределять это умолчание.

Пример.

int x; // тоже, что и signed int x;

unsigned long t;

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

Таблица 1.

	Borland C/C++ (16 bit)	Ms Visual Studio 2008
char	8	8
short	16	16
int	16	32
long	32	32
long long	64	64
float	32	32
double	64	64
long double	80	64
bool	8	8

Структурированные типы данных

К структурированным типам данных относятся структуры и объединения.

struct <name> {type1 name1; type2 name2;}; // структура

union <name> {type1 name1; type2 name2;}; // объединение (все данные размещены с одного адреса в памяти)

Константы

Целые константы задаются с помощью целых чисел без разделяющей точки и имеют тип int. Можно явно указать тип long или unsigned при помощи использования суффиксов соответственно «l», «L», «u», «U».

Пример: 123L, 43u, 53lu, 63UL

Константа с плавающей точкой может включать семь частей: целая часть, десятичная точка, дробная часть, символ экспоненты, показатель десятичной степени (со знаком или без), суффикс. При отсутствии суффикса константы имеют представление double, суффикс f или F соответствует float, суффикс l или L – long double.

В записях вещественных констант могут опускаться (не одновременно): или целая или дробная часть; или десятичная точка или признак экспоненты; суффикс.

Пример: 45. .6 4.6 1.25f 3.5e-4 5E+6L

Перечислимые константы вводятся при помощи служебного слова enum. Это целочисленные константы, которым присвоены идентификаторы. Идентификаторы могут быть перечислены через запятую, тогда им последовательно присваиваются значения от нуля. Или для каких-нибудь из них могут быть указаны значения, которые меняют порядок присвоения.

Примеры:

enum {zero ,one, two, three} соответствует zero=0, one=1, two=2, three=3.

enum {one=1, two, three} соответствует one=1, two=2, three=3.

enum {ten=10, two=2, three} соответствует ten=10, two=2, three=3.

Символьные (литерные) константы – это один или два символа, заключённые в апострофы. Во время компиляции символьные константы заменяются их кодами. Для записи специальных символов используют эскейп-последовательности, которые состоят из двух-четырёх символов и начинаются с символа «обратный слеш». Например \n соответствует переводу строки (код 10), \r – возврат каретки (код 13), \t – табуляция (код 09) и т.д. Для записи некоторых символов также используются эскейп-последовательности: \\ – обратный слеш, \” – двойная кавычка, \’ – одинарная кавычка, \? – знак вопроса.

ВНИМАНИЕ Частой ошибкой является запись «\» вместо «\\», т.к. она не определяется компилятором.

Строковые константы – это набор символов, заключённый в двойные кавычки. в строковых константах также могут быть применены эскейп-последовательности. Для записи строковой константы, которая занимает несколько строк, в конце каждой из них должен быть использован символ «\».

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

Пример:

const int t = 0;

t = 5; // ошибка, нельзя переприсваивать значения константных переменных

Операции

Присваивание.

x=a;

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

A=x=9;

5+(x=4) → 9

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

Арифметические:

a+b; a-b; a*b; a/b – соответственно сложение, вычитание, умножение, деление.

a%b – остаток от деления

Если оба операнда целочисленные, результат тоже целочисленный, если хотя бы один из операндов вещественный – результат вещественный.

ВНИМАНИЕ при делении целочисленных операндов результат также целочисленный. Например, 5/2 → 2. Следует записать «5./2» или «5/2.».

a<<b, a>>b - сдвиги операнда а на b двоичных разрядов влево / вправо.

-a; +a – унарные минус и плюс.

a&b – поразрядное логическое И (например, 1001b & 1100b → 1000b)

a|b – поразрядное логическое ИЛИ

a^b – поразрядное логическое исключающее ИЛИ (XOR)

~x – логическое поразрядное отрицание

Логические (результат – логическое значение).

В языке «С» результатом логической операции является целое число: «1», если результат истинен, и «0», если ложен. В языке «С++» результатом является логическое значение.

a&&b, a||b - логические И и ИЛИ

Например, 5&&3 → 1 (в значении ИСТИНА), 8||0 → 1, 5&&0 → 0.

a<b ,a>b, a<=b,a>=b – операции сравнения.

a= =b – проверка на равенство (например, 5==3 → 0, 4==4 → 1)

a!=b – проверка на неравенство

!x – логическое общее отрицание

Операции работы с указателями.

&x – взятие адреса

*x – разыменовывание указателя

Укороченные операции:

x+=a – тоже, что и x=x+a

аналогично определены операции x-=a, x*=a, x/=a, x%=a, x&=a, x|=a, x^=a, x<<=a, x>>=a.

Инкремент и декремент

++x, --x – увеличивает или уменьшает x на 1, затем подставляет в выражение.

x++ ,x-- – подставляет x в выражение, а затем увеличивает/уменьшает на 1.

Пример (в каждом примере изначально x=3):

(++x)+6 → 10, (x++)+6 → 9 (в обоих случаях в результате x=4)

(++x) + (++x) → 9

(x++) + (x++) → 7

Операция ","

возвращает крайнее правое значение.

Пример (объявлены переменные x,x1,x2,x3):

x = (x1=4+6, x2=x1-2, x3=x2+7)

В результате: x1=10, x2=8, x3=15, x=15.

Операция "?:"

x?a:b - возвращает a, если х истинно, иначе возвращает b.

Пример:

(5>2?4:6) → 4, (8<3?5:9) → 9, 5+(7>3?5:2) → 10

Операция sizeof(тип_данных/имя_переменной).

Возвращает размер (в байтах), занимаемый данной переменной или типом данных.

sizeof(short) → 2

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

if

if (условие) действие1;

else действие2;

Если условие истинно, выполняется действие1, иначе выполняется действие2. Секция else необязательна.

while

while (условие) действие;

Цикл с предусловием. Действие выполняется, пока условие истинно.

Есть также цикл с постусловием:

do действие while (условие);

for

Цикл for выглядит следующим образом и в общем случае не является циклом с заданным числом повторений (в отличие, например, от ЯВУ Pascal).

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

Например,

for (x=0;x<10;x++) a+=f(x);

break

Оператор break используют для выхода из циклов for / while и ветвления switch. Для вложенных циклов выход осуществляется на один уровень.

continue

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

for(int i=a, s=0; i<b; i++)

{

if (i%3==0) continue; //переходим к следующему значению i

s+=i;

}

switch

Структура записи оператора switch следующая.

switch(переменная)

{

case значение1: набор_действий1; break;

case значение2: набор_действий2; break;

…

default: набор_действий_по_умолчанию;

}

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

Формально, секции «case …: » являются метками, на которые осуществляется переход при совпадении значений. Именно поэтому после перехода на метку выполняются все команды до конца секции switch-case либо до оператора break. Этим можно пользоваться для уменьшения дублирования кода. Например, пусть задано условие: если переменная x равна 0, то вызвать функцию f1(), а если равно 2, то вызвать f1() и f2().

switch(x)

{

case 2: f2(); //не используем break, т.к. требуется выполнение и следующей команды.

case 0: f1(); //не используем break, т.к. дошли до конца.

}

Функции

Объявляются следующим образом:

возвращаемый_тип имя_функции(список_формальных_параметров)

{

ТЕЛО ФУНКЦИИ

}

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

Для функции, которая не возвращает значения (процедура в Паскале), предусмотрен тип данных void.

Функции, возвращающие значение, должны обязательно содержать оператор "return возвращаемые_данные". На данном операторе происходит возврат из функции независимо от того, есть ли дальше другие операторы.

Пример.

int sum(int x, int y)

{

return x+y;

}

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

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

Пример:

void myfunc(int, int);

// здесь продолжение кода с вызовом myfunc

void myfunc(int x, int y) {…}

Допустимо явно не указывать параметры функции, для этого используется многоточие в конце списка параметров. В этом случае компилятор контролирует только явно указанные аргументы. Никаких специальных средств по работе с неявно указанными параметрами функции языки «С» и «С++» не предоставляют, но известно, что переданные фактические параметры располагаются в памяти после явно указанных.

Языки «С» и «С++» разрешают использование рекурсии, то есть вызова функцией самой себя.

Пример (функция вычисления факториала):

long fact(int k)

{

if (k<0) return 0;

if (k==0) return 1;

return k*fact(k-1);

}

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

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

– параметры по умолчанию (С++);

– подставляемые (inline) функции (С++);

Директивы препроцессора

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

#include <имя_файла> - добавить в данное место содержимое файла, файл содержится в специальном каталоге подключаемых файлов;

#include "имя_файла" - тоже, но для файла из текущей папки.

Стандартные заголовочные файлы (аналоги библиотек в других ЯВУ):

stdio.h – стандартный ввод-вывод;

string.h – работа со строками;

math.h – математические операции;

limits.h – константы предельных значений;

Следующие заголовочные файлы определены только для ОС Ms Dos и консольных приложений Ms Windows

conio.h – консольный ввод-вывод;

mem.h – функции работы с памятью;

dos.h – команды ОС Ms Dos.

#define идентификатор строка_замещения - заменяет все идентификаторы от директивы до конца файла на строку замещения.

#define WIDTH 80

#define LENGTH ( WIDTH + 10 )

#define test( f1, f2 ) ( f1 * f2 )

#undef идентификатор - отменяет директиву define, после данной директивы замен не производится.

#if, #elif, #else, #endif – организуют ветвление.

#ifdef, #ifndef – далее следующий код будет откомпилирован только если определена / неопределенна макроподстановка.

Метки

Идентификатор с последующим двоеточием является меткой. Метка является адресом оператора, следующего за меткой. Используется в операторах switch и goto. Пример есть выше.

Указатели

Переменные хранят данные и не позволяют управлять их размещением в памяти. Единственная доступная операция – взятие адреса (&).

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

int x;

int *t; // объявили указатель t на переменную типа int

t = &x; // присваиваем указателю адрес переменной x

*t = 4; // используя указатель, присваиваем x значение 4

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

int x,*t=&x;

Константа NULL предназначена для обозначения неинициализированных указателей.

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

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

(новый_тип)переменная

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

Примеры приведены далее.

Типизированные и нетипизированные указатели. Операции над указателями

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

Существуют также нетипизированные указатели (void*), способные указывать на любой тип данных. Сохранение размера и типа данного возложено на программиста.

Пример:

int x;

float y;

void *t = &x; //допустимо

*t = 5; // операция НЕДОПУСТИМА, т.к. неизвестен тип данного

*(int *)t = 5; //допустимо обращение при соответствующем приведении типов

t =& y;

*(double*)t = 2.5;

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

Также для типизированных указателей определена операция разности указателей. Данная операция возвращает количество элементов (размер_области_памяти/размер_элемента) между указателями.

Например (будем считать, что sizeof(float)=4):

float *a=1000, *c;

short x;

c = a+10; // c = 1000+10*sizeof(float)=1040

c = c – 4; // c = 1020 – 4*sizeof(float) = 1024

x = c – a; // x = (1024-1000)/sizeof(float) = 6

Массивы

Массивы являются набором однотипных данных, последовательно размещённых в памяти.

Одномерный массив можно объявить так:

тип_данного имя_массива[размер];

Например: int x[5];

Обращение к элементам массива происходит через операцию []. Минимальный индекс всегда ноль. Максимальный индекс – на единицу меньше размера массива.

ВНИМАНИЕ Автоматический контроль границ отсутствует.

Имя массива является указателем на начало массива. Операция x[i] тождественно равна *(x+i).

Возможно использование многомерных массивов.

int x[4][4][3];

x[0][0][0] = 5;

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

Примеры:

int x[3][2]={{1,2},{3,4},{5,6}}; //заданы и размеры массива, и инициализирующие значения

long y[] = {1,2,3,4}; // размер массива определяется фактическому по количеству значений (4)

char t[][4] = {{1,2,3,4},{5,6}}; // последняя размерность определяется по числу значений (2) и // элементы t[1][2] и t[1][3] не определены

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

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

void f(char *x, double []y) {…}

Как передавать многомерные массивы? (typedef)

Для передачи в функцию константного указателя используется служебное слово const. Данные, на которые указывают такие указатели не могут быть переопределены, а также нельзя освободить память, занимаемую ими (это правда?).

void f2(const char *t)

{

t[0] = ‘x’ //недопустимо

free(t); //недопустимо

}

Может, перенести сюда указатели на функции?

Функции работы с памятью

(заголовочные файлы alloc.h, stdlib.h, mem.h; в Visual Studio – memory.h, stdlib.h)

void* malloc(unsigned s) – выделение памяти s байт.

void* calloc(unsigned n, unsigned m) – выделение n элементов по m байт.

void* realloc(void* ptr, unsigned ns) – перевыделение памяти.

void free(void* ptr) – освобождение памяти.

int memcmp(void* s1, void* s2, unsigned n) – сравнивает две области памяти.

void* memcpy(const void* dest, const void* src, unsigned n) – копирование области памяти n байт из src в dest.

void* memset(void *ptr, int c, unsigned n) – запись числа c в память начиная с ptr.

Консольные функции.

void clreol() – удаление символов от курсора до конца строки.

void clrscr() – очистка экрана.

int cprintf(char *format [,..,]) – вывод строки с учётом параметров консоли.

void gotoxy(int x, int y) – перемещение курсора в позицию (x,y) экрана.

void textbackground(int c) – цвет фона.

void textcolor(int c) – цвет шрифта.

void textmode(int m) – режим (C40, C80, C4350).

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

#include <stdio.h>

#include <conio.h>

#include <memory.h>

#include <stdlib.h>

struct voidarray

{

void **data;

int size, topsize, step;

};

int init(voidarray*array, int initsize)

{

array->topsize = array->step = initsize;

array->size=0;

array->data=(void**)malloc(initsize*sizeof(void*));

return array->data!=NULL;

}

int add(voidarray*array, void* element)

{

array->size++;

if (array->size>array->topsize)

{

void **data2=(void**)malloc((array->topsize+array->step)*sizeof(void*));

if (data2==NULL) return -1;

memcpy(data2,array->data,array->topsize*sizeof(void*));

array->topsize+=array->step;

free(array->data);

array->data=data2;

}

array->data[array->size-1] = element;

return 0;

}

void dispose(voidarray*array)

{

free(array->data);

array->size = array->topsize = 0;

}

void* getat(voidarray*array,int n) {return n<array->size?array->data[n]:0;}

int main()

{

voidarray array;

init(&array,10);

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

{add(&array,new int(i));}

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

printf("%d",*(int*)getat(&array,i));

dispose(&array);

_getch();

}

Строки.

Строкой является массив данных типа char. Используется строка с завершающим нулём, то есть признаком конца строки является символ с кодом «0».

Строки могут инициализироваться текстом, заключенным в двойные кавычки: строковой константой, – которая имеет тип const char*.

char t[] = “Hello, World”;

Функции работы со строками (библиотека string.h).

char *strcat(char *dest, char *src) – в dest помещается результат объединения dest и src, возвращает ссылку на dest (!!! в dest должно быть достаточно места для помещения результата)

char *strchr(char *str, int c) – поиск символа «c» в str, результат – ссылка на первый найденный символ или NULL, если символ не найден;

int strcmp(char *str1, char *str2) – посимвольное сравнение строк, возвращает -1, если str1<str2, +1 если str1>str2 и 0 если str1==str2;

char* strcpy(char *dest, char *src) – копирует src в dest, возвращает указатель на dest;

unsigned strlen(char *str)

char* strset(char *str, int c) , возвращает s.

char *strstr(const char *str, const char *substr)

Определены модификации некоторых функций, принимающие в качестве дополнительного аргумента длину строки. Данные функции начинаются с strn вместо str. Это функции strncat, strncmp, strncpy, strnset.

Пример:

char* strncat(char *dest, char *src, unsigned n) – то же, что strcat, но используются n символов src.

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

В языках С / С++, как и в большинстве остальных ЯВУ есть три типа переменных.

1. Статические. Статическими являются переменные, объявленные вне какой-либо функции, а также объявленные внутри функций и классов с использованием служебного слова static. Такие переменные создаются при запуске программы, уничтожаются при её завершении и доступны из любой функции программы.

2. Автоматические. Это все переменные, объявленные внутри какой-либо функции (кроме объявленных с использованием слова static). Такие переменные создаются при их объявлении и уничтожаются при выходе за пределы операторных скобок фрагмента программы, в котором они определены. Эти переменные размещаются в стеке. Поэтому максимальный размер всех автоматических переменных ограничен размером выделенного стека, на это следует обращать внимание при создании больших автоматический массивов.

3. Динамические. Это переменные, созданные с помощью специальных функций (malloc, calloc и др.) или операций (new, new[]). Временем жизни таких переменных управляет программист. Область видимости определяется доступностью указателей. Такие переменные расположены как правило в «куче» (heap). В Ms Windows при завершении приложения все динамические переменные также уничтожаются в связи с уничтожением кучи, связанной с данным приложением.

Пример (С++).

int main()

{

char a = 5;

…

{

int b = a + 5; //здесь a существует и доступно

…

} //уничтожена переменная b

short c;

c = a + b; // ошибка, т.к. b уже не существует

for(int i = 0;i<10;i++) {…}

c = i; //ошибка, i существует только в теле цикла for

int i=0; //переменная может быть объявлена, т.к. i объявленная выше уже не существует

for(;i<10;i++) {…}

c = i; //допустимо, т.к. i объявлено в этом же блоке

i = 10;

{

int i = 3; //допустимо, перекрывает видимость i, объявленной ранее

…

}

// здесь i=10;

} //уничтожены переменные a,c,i

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

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

тип_функции (*имя_указателя) (спецификация параметров)

пример:

void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void *p1, const void *p2);

вызов: fcmp(p1,p2);

функция сравнения чисел:

int comp(const void *p1, const void *p2)

{

return *(int*)p1 - *(int*)p2;

}

Работа с файлами.

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

Для работы с файлом его необходимо открыть, для этого предназначена функция

FILE *fopen(const char *filename,const char *mode);

filename – абсолютное или относительное имя файла, mode – режим открытия и доступа.

Режимы:

"r" – открытие существующего файла только для чтения (файл должен существовать);

"w" – создание пустого файла для записи;

"a" – открытие существующего файла для записи данных в конец файла; создание файла, если файла с заданным именем не существует;

"r+" – открытие существующего файла для чтения и записи (файл должен существовать);

"w+" – создание нового файла для чтения и записи;

"a+" – тоже, что “a”, но с возможностью чтения;

Другие функции работы с файлами:

int fclose( FILE *stream ); // 0 в случае успеха

int _fcloseall( void ); //количество закрытых файлов

int fflush(FILE *stream);

int feof( FILE *stream);

int fgetc( FILE *stream);

int fgetpos( FILE *stream, fpos_t *pos);

int fputc(int c, FILE *stream);

int fseek( FILE *stream, long offset, int origin);

long ftell( FILE *stream);

Существуют стандартные файлы (потоки) (тип данных – FILE*):

stdin – стандартный поток ввода (по умолчанию – клавиатура);

stdout – стандартный поток вывода (по умолчанию – монитор в текстовом режиме);

stderr – стандартный поток ошибок;

stdaux – стандартный вспомогательный поток;

stdprn – стандартный принтер.

Данные потоки могут быть переопределены с использованием функции fopen.

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

Для форматированного вывода в поток предназначена функция

fprintf(FILE* stream, const char* formatted_string, arguments, …)

Для подстановки значений переменных в строку вывода используют символы подстановки (спецификаторы формата), начинающиеся с символа «%»:

%[флаги][размер][.точность][модификатор_длины]тип_данного

Флаги:

«-» – выравнивание результата по левому краю (по умолчанию – по правому относительно заданного количества выводимых символов);

«+» – результат всегда начинается со знака (+/-);

«#» – особая форма отображения результата.

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

n – минимум n символов отводится для записи числа, недостающие символы заменяются пробелами;

0n – то же, но недостающие символы заменяются нулями;

* – список аргументов содержит размеры данных.

Точность показывает для вещественных чисел количество знаков после десятичной точки.

Модификатор длины может принимать одно из значений:

F – «длинный» указатель;

N – «короткий» указатель;

h – short int;

l – long int, double;

L – long double.

Тип данного может принимать одно из значений:

%d, %i – знаковое десятичное целое;

%u – беззнаковое десятичное целое;

%o – беззнаковое восьмеричное целое;

%x, %X – беззнаковое шестнадцатеричное целое;

%f – знаковое вещественное;

%e, %E – знаковое вещественное в экспоненциальной форме;

%g, %G – знаковое вещественное, форма зависит от числа, размера и точности;

%c – символ;

%s – строка;

%% – символ «%»;

%n, %p – указатель.

Аргументы, передаваемые в функцию, должны соответствовать количеству и типу спецификаторам формата.

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

fscanf(FILE* stream, const char* formatted_string, arguments, …)

Строка также может содержать спецификаторы формата, при этом:

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

– строкой считается слово до разделителя (пробел, табуляция, перевод строки).

Для стандартных потоков определены аналогичные функции:

printf(const char* formatted_string, arguments, …)

scanf(const char* formatted_string, arguments, …)

являющиеся аналогами описанных ранее функций, разница заключается в том, что используются стандартные потоки ввода и вывода (stdin, stdout) которые в качестве аргументов не указываются.

Определены функции, использующие вместо потока строку:

sprintf(char *dest, const char* formatted_string, arguments, …)

sscanf(char *src, const char* formatted_string, arguments, …)

Виды переменных:

– статические (staic);

typedef тип_данного имя_типа

typedef тип_данного имя_типа[размер]

typedef void DRAWF( int, int );

typedef float (*PTF)(float)

typedef char* (*PTC)(char)

создание объектов через new и delete.

Виды переменных и области их существования.

Часть 2. Введение в технологию программирования.

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

Технология программирования включает:

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

– перечисление условий, при которых выполняется операция;

– описание самих операций;

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

Этапы развития программирования.

1. Стихийное программирование (до сер. 60-х годов):

– программирование в 2-х кодах;

– появление ассемблеров;

– появление ЯВУ (Fortran, Algol);

– появление подпрограмм, работающих с глобальными данными);

– локализация данных в подпрограммах;

– стихийное использование подхода «снизу-вверх», сложные интерфейсы функций.

2. Структурное программирование (сер. 60 – сер. 80):

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

– проектирование «сверху вниз»;

– использование 3 базовых алгоритмических конструкций (следование, ветвление, цикл);

– структурирование данных, пользовательские типы;

– модульное программирование – выделение группы подпрограмм, использующих одни данные, в отдельно компилируемые модули.

Языки: PL/1, Algol-68, Pascal, C.

3. Объектный подход (сер. 80 – конец 90).

– представление программы в виде совокупности объектов, которые являются экземплярами определённого класса;

– классы образуют иерархию с наследованием свойств;

– система сообщений;

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

– визуальное программирование.

Примеры языков: Simula, Smalltalk, C++, Modula, Java, Object Pascal.

4. Компонентный подход и CASE-технологии.

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

– компоненты собираются в двоичные библиотеки или исполняемые файлы;

Примеры:

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

Объекты COM функционируют в составе сервера: внутреннего, локального, удалённого.

На его основе построены OLE-Automation и ActiveX.

CORBA (Common Object Request Broker Architecture).

CASE-технологии (Computer-Aided Software/System Engineering) – автоматизированные технологии разработки и сопровождения ПО.

Проблемы разработки сложных программных систем:

1. Сложность формального определения требований к ПС.

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

3. Коллективная разработка.

4. Необходимость увеличения степени повторяемости кода.

Жизненный цикл программного продукта.

Жизненный цикл (ЖЦ) – это период от момента появления идеи создания ПО до момента завершения его поддержки.

Постановка задачи (Техническое задание).
Анализ требований и разработка спецификаций (Эскизный проект).
Проектирование (Технический проект).
Реализация (Рабочий проект).
Сопровождение (отсутствует в современном стандарте).

Стандарт ISO/IEC 12207: 1995 “Information Technology – Software Life Cycle Process”. Содержит этапы: подготовительная работа (выбор моделей ЖЦ, методов, средств разработки, составление плана работ); анализ требований к системе; проектирование архитектуры; анализ требований к программному обеспечению; проектирование архитектуры ПО; детальное проектирование ПО; кодирование и тестирование ПО; интеграция ПО; квалификационное тестирование ПО; интеграция системы; квалификационное тестирование системы; установку ПО; приёмку ПО.

Модели ЖЦ.

Каскадная (водопадная) модель.

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

КМ с промежуточным контролем.
Спиральная модель.

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

RAD – технология.

5. Экстремальное программирование.

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

1. Короткий цикл обратной связи (Fine scale feedback)

– Разработка через тестирование (Test driven development) – техника программирования, при которой модульные тесты для программы или её фрагмента пишутся до самой программы (англ. test-first development) и, по существу, управляют её разработкой. Является одной из основных практик экстремального программирования;

– Игра в планирование (Planning game)

– Заказчик всегда рядом (Whole team, Onsite customer)

– Парное программирование (Pair programming)

2. Непрерывный, а не пакетный процесс

– Непрерывная интеграция (Continuous Integration) – это практика разработки программного обеспечения, которая заключается в выполнении частых автоматизированных сборок проекта для скорейшего выявления и решения интеграционных проблем;

– Рефакторинг (Design Improvement, Refactor) – процесс полного или частичного преобразования внутренней структуры программы при сохранении её внешнего поведения.

– Частые небольшие релизы (Small Releases)

3. Понимание, разделяемое всеми

– Простота (Simple design)

– Метафора системы (System metaphor)

– Коллективное владение кодом (Collective code ownership) или выбранными шаблонами проектирования (Collective patterns ownership) – каждый член команды несёт ответственность за весь исходный код, каждый вправе вносить изменения в любой участок программы

– Стандарт кодирования (Coding standard or Coding conventions) – набор правил и соглашений, используемых при написании исходного кода на некотором языке программирования

4. Социальная защищенность программиста (Programmer welfare):

– 40-часовая рабочая неделя (Sustainable pace, Forty hour week)

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

Стандарты ISO 9000-9004. Необходимые условия для достижения минимального уровня организации процесса ППО.
CMM (Capability Maturity Model) – модель зрелости процессов создания ПО. Включает 5 уровней: начальный, повторяемый, определённый, управляемый, оптимизирующий.
SPICE (Software Process Improvement and Capability dEtermination) (ISO/IES 15504) – определение возможностей и улучшение процесса создания программного обеспечения.

Проектирование надёжного ПС.

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

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

Почему техника надёжнее программ?

1. Большее разнообразие входных данных.

2. Отношение к возможным применениям.

3. Различная природа компонент.

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

На каждом из этапов возможны ошибки по взаимодействию исполнителей.

Микромодель перевода.

Чтение à Запоминание à анализ à распространение

Причины ошибок:

- чтение между строк à всё, что непонятно, надо уточнять у автора документа;

- непонимание;

- нечёткое выражение мыслей.

Четыре подхода к надёжности.

1. Предупреждение ошибок.

2. Обнаружение ошибок.

3. Исправление ошибок.

4. Устойчивость к ошибкам.

- динамическая избыточность (неприменимо);

- отступление (обработка исключений try – throw – catch);

- изоляция ошибок (задача ОС).

Борьба со сложностью.

Сложность – основная причина ошибок перевода, и, следовательно, одна из главных причин ненадёжности.

Концепции:

- независимость – компоненты должны быть максимально независимы;

- иерархическая структура.

Проектирование.

- вовлечение пользователя в процесс принятия решений;

- понимание культуры пользователя;

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

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

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

Требования, цели

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

Требования могут быть сформулированы в форме hipo – диаграмм, которые состоят из оглавления функций программного продукта и описания каждой из них.

Оглавление – описание иерархии задач со ссылками на диаграммы. Диаграммы содержат вход (слева), обработку (по центру), выход (справа).

Цели – конкретные ориентиры программного продукта.

Типичные ошибки:

- неявное формулирование целей;

- составление наброска без учёта всех целей;

- есть конфликты при формулировании целей (должны быть компромиссы);

Цели ПО могут быть разбиты на 10 групп:

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

- психологические факторы – мера лёгкости понимания, удобства использования, защиты от неверных действий пользователя;

- адаптируемость – мера лёгкости расширения;

- удобство сопровождения – мера затрат времени и средств на исправление ошибок;

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

- документация;

- стоимость продукта;

- календарный план;

- эффективность (производительность);

- надёжность (средства повышения надёжности снижают эффективность).

Внешнее проектирование.

Составляется детальное описание каждой функции пользователя:

- описание входных данных;

- описание выходных данных и их функциональной связи с входными;

- изменения системы под воздействием входных данных;

- характеристики надёжности;

- эффективность (по расходу памяти и по быстродействию);

- замечания по программированию.

Проверка:

- контроль «плюс-минус один» – эскизный проект контролируется исполнителями предыдущего и следующего этапов;

- контроль со стороны пользователя;

- таблицы решений;

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

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

Диаграммы потоков данных (Data Flow Diagrams).

Внешняя сущность – материальный объект или физическое лицо, выступающие в качестве источника или приёмника информации.

Процесс – преобразование входных потоков данных в выходные.

Хранилище данных – абстрактное устройство для хранения информации.

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

Нотация Гейна-Сарсона.

Диаграммы «сущность-связь» (Entity-Relationship Diagrams).

(см. структуры данных)

Диаграммы переходов состояний (State Transition Diagrams).

Функциональные диаграммы.

(слева – вход, справа – выход, сверху – управление, снизу – механизм)

Описание структур данных

Абстрактные структуры данных.

– элементы не связаны между собой (множества, кортежи);

– структуры с неявными связями элементов: векторы, матрицы, строки.

– структуры с явной связью элементов: графы.

Иерархические модели.

– диаграммы Джексона;

– скобочные диаграммы Ора.

Сетевые модели (почти реляционные).

Нотация Баркера.

Диаграммы применения.

Проектирование архитектуры

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

Архитектура показывает, как система выглядит «со стороны». Требуется только для больших проектов. Примеры: автономная программа (вырожденная архитектура), комплекс параллельно выполняющихся программ, слоистая (вертикальное взаимодействие) и т.д.

Проектирование модульной структуры.

Модуль

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

В структурном программировании:

– одна функция;

– набор функций, объединённых общими данными и/или назначением и собранные (как правило) в один файл;

В объектно-ориентированном программировании:

– класс;

– метод класса;

– несколько классов, объединённых общими данными и/или назначением и собранные (как правило) в один файл;

Хороший модуль снаружи проще, чем внутри. Хороший модуль проще использовать, чем построить.

Свойства.

1. Прочность – мера внутренних связей. Исторически сложились различные уровни прочности:

- по совпадению – между его элементами нет осмысленных связей, может возникать при «модулизации» программы;

- по логике – содержит набор независимо вызываемых связанных функций;

- по классу – последовательное выполнение набора несвязанных функций (инициализация, завершение);

- процедурно прочный – выполняет последовательность действий, обусловленную задачей;

- коммуникационно-прочный – процедурная прочность + связи по данным;

- функционально прочный – выполняет одну «элементарную» (с функциональной ТЗ) функцию;

- информационно прочный – выполняет несколько функций (со своими точками входа), работающих на единой структуре данных).

Для функции или метода рекомендуется функциональная прочность, для класса – информационная.

2. Сцепление – мера связи по данным.

- по содержимому – один модуль ссылается на данные другого;

- по общей памяти – ссылаются на единую структуру данных;

- по внешним данным – совместно используют глобальные простые типы данных;

- по управлению – один модуль запускает фрагменты другого;

- по формату – передача структуры данных;

- по данным – передача неструктурированных данных.

Другие свойства:

- предсказуемость – независимость от предыстории;

- структура принятия решений – влияние только на подчинённые модули;

Внешнее проектирование модулей

Внешняя спецификация модуля включает:

– имя модуля;

– назначение (решаемые задачи);

– список параметров;

– вход;

– выход (зависимость от входных, в т.ч. при неверных входных данных);

– внешние действия (печать, чтение файла и т.д.)

Проектирование модуля:

– выбор языка программирования;

– проектирование внешних спецификаций;

– проверка внешних спецификаций (в основном интерфейсов разработчиками соседних модулей);

– выбор алгоритма и структуры данных (желательно на первых этапах использовать стандартные и простые алгоритмы);

– запись начальных и конечных операторов в соответствии с синтаксисом языка;

– объявление данных интерфейса;

– объявление прочих локальных данных;

– усовершенствование кода;

– улучшение читаемости кода;

– проверка кода;

– компиляция.

Модульная декомпозиция

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

Структурная схема – отображает состав и взаимодействие по управлению. Состоит из условных обозначений модулей с указанием связей (по данным и управлению) между ними.

Функциональная схема (схема данных ГОСТ 19.701-90) – схема взаимодействия компонент программного обеспечения с описанием информационных потоков, состава данных в потоках и указанием используемых файлов и устройств.

Функциональная схема кроме модулей может включать обозначения:

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

Метод пошаговой детализации – построение иерархической модульной структуры.

Структурные карты Констайтайна.

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

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

– если ошибка вызвана недостаточной аккуратностью, это плохо;

– компилятор может не обнаружить некоторые ошибки (двойное толкование, отключение предупреждений и т.д.);

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

Введение в объектно-ориентированное программирование

Объе́ктно-ориенти́рованное программи́рование (ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов.

Класс — это тип, описывающий устройство объектов. Понятие «класс» подразумевает некоторое поведение и способ представления. Понятие «объект» подразумевает нечто, что обладает определённым поведением и способом представления. Говорят, что объект — это экземпляр класса.

Абстракция данных

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

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

– Сокрытие данных — неотделимая часть ООП, управляющая областями видимости. Является логическим продолжением инкапсуляции. Целью сокрытия является невозможность для пользователя узнать или испортить внутреннее состояние объекта.

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

– Полиморфизмом называют явление, при котором функции (методу) с одним и тем же именем соответствует разный программный код (полиморфный код) в зависимости от того, объект какого класса используется при вызове данного метода. Полиморфизм обеспечивается тем, что в классе-потомке изменяют реализацию метода класса-предка с обязательным сохранением сигнатуры метода. Это обеспечивает сохранение неизменным интерфейса класса-предка и позволяет осуществить связывание имени метода в коде с разными классами — из объекта какого класса осуществляется вызов, из того класса и берётся метод с данным именем. Такой механизм называется динамическим (или поздним) связыванием — в отличие от статического (раннего) связывания, осуществляемого на этапе компиляции.

С++

Класс состоит из полей (данных) и методов (функций). Существуют специальные методы: конструктор (вызывается при создании экземпляра класса) и деструктор(вызывается при уничтожении объекта).

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

Перегрузка операций – позволяет определять операции для классов.

Виртуализация функций.

Язык UML.

Курсив – абстрактная операция. Видимость атрибутов: «+» public, «-» private, «#» protected.

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

Тести́рование программного обеспечения — процесс выявления ошибок в программном обеспечении (ПО). К сожалению, существующие на сегодняшний день методы тестирования ПО не позволяют однозначно и полностью устранить все дефекты и ошибки и установить корректность функционирования анализируемой программы особенно в закрытых частных программах. Поэтому все существующие методы тестирования действуют в рамках формального процесса проверки исследуемого или разрабатываемого ПО.

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

Существует множество подходов к решению задачи тестирования и верификации ПО, но эффективное тестирование сложных программных продуктов — это процесс в высшей степени творческий, не сводящийся к следованию строгим и чётким процедурам или созданию таковых. [источник?]

Конечной целью любого процесса тестирования является обеспечение такого ёмкого (совокупного) понятия как Качество, с учётом всех или наиболее критичных для данного конкретного случая составляющих.

С точки зрения ISO 9126, Качество (программных средств) можно определить как совокупную характеристику исследуемого ПО, с учётом следующих составляющих:

Надёжность, Сопровождаемость, Практичность, Эффективность, Мобильность, Функциональность

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

Модульное тестирование (юнит-тестирование) — тестируется минимально возможный для тестирования компонент, например, отдельный класс или функция

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

Системное тестирование — тестируется интегрированная система на её соответствие исходным требованиям

Альфа-тестирование — имитация реальной работы с системой штатными разработчиками, либо реальная работа с системой потенциальными пользователями/заказчиком на стороне разработчика. Часто альфа-тестирование применяется для законченного продукта в качестве внутреннего приёмочного тестирования. Иногда альфа-тестирование выполняется под отладчиком или с использованием окружения, которое помогает быстро выявлять найденные ошибки. Обнаруженные ошибки могут быть переданы тестировщикам для дополнительного исследования в окружении, подобном тому, в котором будет использоваться ПО.

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

Тестирование «белого ящика» и «чёрного ящика»

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

При тестировании белого ящика (англ. white-box testing, также говорят — прозрачного ящика), разработчик теста имеет доступ к исходному коду программ и может писать код, который связан с библиотеками тестируемого ПО. Это типично для юнит-тестирования (англ. unit testing), при котором тестируются только отдельные части системы. Оно обеспечивает то, что компоненты конструкции — работоспособны и устойчивы, до определенной степени. При тестировании белого ящика используются метрики покрытия кода.

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

Если «альфа-» и «бета-тестирование» относятся к стадиям до выпуска продукта (а также, неявно, к объёму тестирующего сообщества и ограничениям на методы тестирования), тестирование «белого ящика» и «черного ящика» имеет отношение к способам, которыми тестировщик достигает цели.

Бета-тестирование в целом ограничено техникой чёрного ящика (хотя постоянная часть тестировщиков обычно продолжает тестирование белого ящика параллельно бета-тестированию). Таким образом, термин «бета-тестирование» может указывать на состояние программы (ближе к выпуску чем «альфа»), или может указывать на некоторую группу тестировщиков и процесс, выполняемый этой группой. Итак, тестировщик может продолжать работу по тестированию белого ящика, хотя ПО уже «в бете» (стадия), но в этом случае он не является частью «бета-тестирования» (группы/процесса).

Статическое и динамическое тестирование

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

При статическом тестировании программный код не выполняется — анализ программы происходит на основе исходного кода, который вычитывается вручную, либо анализируется специальными инструментами. В некоторых случаях, анализируется не исходный, а промежуточный код (такой как байт-код или код на MSIL).

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

Основная статья: Регрессионное тестирование

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

Тестовые скрипты

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

Покрытие кода

Основная статья: Покрытие кода

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

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

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

Цитаты

«Тестирование программ может использоваться для демонстрации наличия ошибок, но оно никогда не покажет их отсутствие.» — Дейкстра, 1970 г.

Документирование.

Документа́ция на программное обеспечение — это документы, сопровождающие некоторое программное обеспечение (ПО) — программу или программный продукт. Эти документы описывают то, как работает программа и/или то, как её использовать.

Существует четыре основных типа документации на ПО:

архитектурная/проектная — обзор программного обеспечения, включающий описание рабочей среды и принципов, которые должны быть использованы при создании ПО
техническая — документация на код, алгоритмы, интерфейсы, API
пользовательская — руководства для конечных пользователей, администраторов системы и другого персонала
маркетинговая

Единая система программной документации (ЕСПД) — комплекс государственных стандартов, устанавливающих взаимосвязанные правила разработки, оформления и обращения программ и программной документации.

Перечень стандартов, входящих в ЕСПД

ГОСТ 19.001-77. ЕСПД. Общие положения.

ГОСТ 19.005-85. ЕСПД. Р-схемы алгоритмов и программ. Обозначения условные графические и правила выполнения.

ГОСТ 19.101-77. ЕСПД. Виды программ и программных документов.

ГОСТ 19.102-77. ЕСПД. Стадии разработки.

ГОСТ 19.103-77. ЕСПД. Обозначение программ и программных документов.

ГОСТ 19.104-78. ЕСПД. Основные надписи.

ГОСТ 19.105-78. ЕСПД. Общие требования к программным документам.

ГОСТ 19.106-78. ЕСПД. Требования к программным документам, выполненным печатным способом.

ГОСТ 19.201-78. ЕСПД. Техническое задание. Требования к содержанию и оформлению.

ГОСТ 19.202-78. ЕСПД. Спецификация. Требования к содержанию и оформлению.

ГОСТ 19.301-79. ЕСПД. Программа и методика испытаний. Требования к содержанию и оформлению.

ГОСТ 19.401-78. ЕСПД. Текст программы. Требования к содержанию и оформлению.

ГОСТ 19.402-78. ЕСПД. Описание программы.

ГОСТ 19.403-79. ЕСПД. Ведомость держателей подлинников.

ГОСТ 19.404-79. ЕСПД. Пояснительная записка. Требования к содержанию и оформлению.

ГОСТ 19.501-78. ЕСПД. Формуляр. Требования к содержанию и оформлению.

ГОСТ 19.502-78. ЕСПД. Общее описание. Требования к содержанию и оформлению.

ГОСТ 19.503-79. ЕСПД. Руководство системного программиста. Требования к содержанию и оформлению.

ГОСТ 19.504-79. ЕСПД. Руководство программиста. Требования к содержанию и оформлению.

ГОСТ 19.505-79. ЕСПД. Руководство оператора. Требования к содержанию и оформлению.

ГОСТ 19.506-79. ЕСПД. Описание языка. Требования к содержанию и оформлению.

ГОСТ 19.507-79. ЕСПД. Ведомость эксплуатационных документов.

ГОСТ 19.508-79. ЕСПД. Руководство по техническому обслуживанию. Требования к содержанию и оформлению.

ГОСТ 19.601-78. ЕСПД. Общие правила дублирования, учета и хранения.

ГОСТ 19.602-78. ЕСПД. Правила дублирования, учета и хранения программных документов, выполненных печатным способом.

ГОСТ 19.603-78. ЕСПД. Общие правила внесения изменений.

ГОСТ 19.604-78. ЕСПД. Правила внесения изменений в программные документы, выполненные печатным способом.

ГОСТ 19.701-90 (ИСО 5807-85). ЕСПД. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

Пользовательский интерфейс

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

Типы.

Процедурно-ориентированные:

а) примитивный – взаимодействие в консольном режиме;

б) меню;

в) со свободной навигацией – графические пользовательские интерфейсы.

Объектно-ориентированные (прямого манипулирования).

API – интерфейс прикладного программирования (иногда интерфейс программирования приложений) (англ. application programming interface, API [эй-пи-ай])[1] — набор готовых классов, функций, структур и констант, предоставляемых приложением (библиотекой, сервисом) для использования во внешних программных продуктах.

API определяет функциональность, которую предоставляет программа (модуль, библиотека), при этом API позволяет абстрагироваться от того, как именно эта функциональность реализована.

Если программу (модуль, библиотеку) рассматривать как чёрный ящик, то API — это множество «ручек», которые доступны пользователю данного ящика, которые он может вертеть и дёргать.

Часть 3. Типовые структуры данных и алгоритмы.

3.1 Структуры данных

Логические структуры данных:

1. Множества – важен только факт вхождения элемента в структуру; примеры: математические множества, таблицы реляционных баз данных.

2. Массивы – важно местоположение (номер) элемента; пример: массивы различной размерности.

3. Графы – важны связи между элементами; пример: деревья, сети, графы.

Примеры: очередь (FIFO, LIFO (стэк)), множество, дерево, поле указателей.

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

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

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

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

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

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

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

Вектор: более быстрый доступ к элементу; малые расходы памяти на вспомогательные структуры данных. Список: размер ограничен только объёмом доступной виртуальной памяти; более быстрое добавление и удаление элементов (кроме последнего). Эти достоинства и недостатки проявляются сильнее с увеличением числа элементов.

Как реализовать: 2 и 3-мерные таблицы: через векторы, через вектор списков.

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

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

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

Сортированные структуры данных.

Ассоциативный массив (словарь) — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары (ключ, значение) и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу. Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами. В паре (k,v) значение v называется значением, ассоциированным с ключом k.

STL

Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.

Стандартная библиотека шаблонов до включения в стандарт C++ была сторонней разработкой, в начале — фирмы HP, а затем SGI. Стандарт языка не называет её «STL», так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода/вывода (iostream), подраздел Си и др.).

Контейнер (container) - хранение набора объектов в памяти.

Итератор (iterator) - обеспечение средств доступа к содержимому контейнера.

vector – C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за O(1). Добавление-удаление элемента в конец vector занимает амортизированное O(1) время, та же операция в начале или середине vector — O(n). Стандартная быстрая сортировка за O(n * log(n)). Поиск элемента перебором занимает O(n). Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.

list – Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из за большего времени доступа к элементу. Доступ по индексу за O(n). В любом месте контейнера вставка и удаление производятся очень быстро - за O(1).

deque – Очередь. Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за O(1). Реализован в виде двусвязанного списка линейных массивов.

set – Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска.

multiset – То же что и set, но позволяет хранить повторяющиеся элементы.

map – Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.

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

stack – Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца.

queue – Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.

priority_queue – Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте.

bitset – Служит для хранения битовых масок. Похож на vector<bool> фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти.

basic_string – Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет организовать быстрый доступ ко всей последовательности. Элементы должны быть POD'ами. Определена конкатенация с помощью +.

valarray – Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций. Определены операции над двумя valarray и над valarray и скаляром (поэлементные). Эти операции возможно эффективно реализовать как на векторных процессорах, так и на скалярных процессорах с блоками SIMD.

#include <iostream>

#include <deque>

using namespace std;

deque<char > chardeque;

Другие примеры.

#include <vector>

using namespace std;

void main()

{

vector<int> arr;

for(int i=0;i<1000;i++) arr.push_back(i);

for(int i=0;i<1000;i++) printf("%d,",arr[i]);

_getch();

}

#include <list>

using namespace std;

void main()

{

list<int> lst;

for(int i=0;i<1000;i++) lst.push_back(i);

for(list<int>::iterator i=lst.begin();i!=lst.end();i++) printf("%d,",*i);

_getch();

}

Организация двусвязанного списка.

Пример через класс (хранимое данное: нетипизированный указатель (void*)). Особенностью списка является отсутствие управляющей структуры данных, операции над списком могут быть выполнены над любым элементом. Другой особенностью является «закольцованность», т.е. после последнего элемента идёт опять первый, перед первым – последний. Это позволяет в любой момент выбрать любой элемент списка в качестве первого.

class List

{

private:

List *next,*prev; //адрес следующего и предыдущего элементов

int *cnt; //указатель на количество элементов списка

public:

bool linkdata; //удалять ли связанные данные при удалении элемента

void *data; //указатель на данные

protected:

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

List(void* data,int *cnt):data(data),linkdata(false),cnt(cnt)

{

}

public:

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

List(void* data = NULL):data(data),linkdata(false)

{

prev=next=this;

cnt = new int(1); //создаётся новый счётчик числа элементов

}

virtual ~List() //деструктор

{

if (linkdata&&data!=NULL) free(data);//если есть данные и они «связаны», то удаляем их

next->prev=prev; prev->next=next; //переопределение связей

--(*cnt); //уменьшение количества элементов списка

if (*cnt==0) delete cnt; //если это последний элемент, то удаляем и счётчик

}

inline List* Next() {return next;} //следующий элемент

inline List* Prev() {return prev;} //предыдущий элемент

inline List* PushAfter(void* data = NULL) //добавить элемент после текущего

{

List *t = new List(data,cnt); //создаём новый элемент

if (t==NULL) return NULL; //если создание неуспешно, возврат

t->prev = this; //переопределение связей

t->next = next;

t->data = data;

next->prev = t;

next = t;

++(*cnt); //увеличение счётчика

return t;

}

void Clear() //очистка списка, остаётся только текущий элемент

{

List *t = next;

while (t!=this)

{

if (t->linkdata) free(t->data);

t = t->next;

delete t->prev;

}

cnt = 1;

next = prev = this;

}

inline int Count() {return *cnt;} //количество элементов

};

Организация на языке «С» (struct)

struct List

{

List *next,*prev;

int *cnt;

void *data;

char linkdata;

}

int Init(List* element)

{

element->prev= element->next= element;

if (element->cnt = malloc(sizeof(int))==NULL) return -1;

return 0;

}

List* PushAfter(List* elenemt, void* data)

{

List *t = malloc(sizeof(List));

if (t==NULL) return NULL;

t->data = data;

t->cnt = cnt;

t->linkdata = 0;

t->prev = element;

t->next = element->next;

t->data = element->data;

element->next->prev = t;

element->next = t;

++(*element->cnt);

return t;

}

int Delete(List* element)

{

if (element->linkdata&&element->data!=NULL) free(data);

element->next->prev= element->prev; element->prev->next=element->next;

--(*element->cnt);

if (*element->cnt==0) free(element->cnt);

free(element);

}

Организация массива переменного размера:

1. С быстрым извлечением – создаётся вектор размера top, если происходит попытка записи элемента с номером n больше top, происходит перевыделение памяти так, чтобы (n < top). Может дополнительно задаваться шаг роста массива. Далее существующие данные копируются в новый массив; освобождается место, где ранее размещался массив. Недостаток – существенные временные затраты на «рост».

2. С быстрым расширением – создаётся список векторов, инициализируется только первый вектор (размер top). При попытке записи элемента с номером n больше top к списку добавляются один или несколько векторов, чтобы (n<top). Для ускорения доступа все векторы целесообразно создавать одного размера. Доступ к элементу осуществляется по номеру вектора (k) и номеру элемента в векторе (m). При равных размерах векторов (top) и заданном порядковом номере элемента (n) получаем: k=n/top, m=n%top.

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

class Vector

{

protected:

void** data; //поле данных

int top,step; //верхняя граница и шаг роста

public:

//конструктор принимает аргументы: начальный размер вектора и шаг роста

tVector(int top = 10, int step = 10):top(top),step(step)

{

data = (void**)malloc(top*sizeof(void*));

memset(data,0,top*sizeof(void*)); //сброс всех данных в ноль

}

~tVector()

{

free(data);

}

void* GetAt(int n)

{

if (n>-1 && n<top) return data[n];

return NULL; //если данные за допустимым диапазоном

}

bool SetAt(int n, void* element)

{

if (n>=top) //рост массива если вышли за границы

{

int oldtop = top;

while((top+=step)<=n);

void **tdata = (void**)malloc(top*sizeof(void*));

if (tdata == NULL) return false;

memcpy(tdata,data,oldtop*sizeof(void*));

memset(tdata+oldtop,0,(top-oldtop)*sizeof(void*));

free(data);

data = tdata;

}

*(data+n) = element;

return true;

}

int Count() {return top;} //верхняя граница

};

Библиотека STL (standard template library) предоставляет стандартные классы структур данных.

deque – очереди;

list – двусвязанный список;

vector – вектор;

map / multimap – карта – каждый элемент задаётся двумя аргументами: ключом и значением;

set / multiset – множество.

multi- соответствует возможности множественного вхождения.

Организация бинарного дерева.

class Tree

{

class Node

{

public void *item;

public Node *left,*right;

public Node(void* item) { this->item = item;}

}

3.2 Алгоритмы

Быстрая сортировка

"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

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

из массива выбирается некоторый опорный элемент a[i],

запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,

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

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

В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм подробнее.

Разделение массива

На входе массив a[0]...a[N] и опорный элемент p, по которому будет производиться разделение.

Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.

Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] <= p.

Далее, если i <= j, меняем a[i] и a[j] местами и продолжаем двигать i,j по тем же правилам...

Повторяем шаг 3, пока i <= j.

Рассмотрим работу процедуры для массива a[0]...a[6] и опорного элемента p = a[3].

Теперь массив разделен на две части: все элементы левой меньше либо равны p, все элементы правой - больше, либо равны p. Разделение завершено.

Реализация на Си.

template<class T>

void quickSortR(T* a, long N) {

// На входе - массив a[], a[N] - его последний элемент.

long i = 0, j = N; // поставить указатели на исходные места

T temp, p;

p = a[ N/2]; // центральный элемент

// процедура разделения

do {

while ( a[i] < p ) i++;

while ( a[j] > p ) j--;

if (i <= j) {

temp = a[i]; a[i] = a[j]; a[j] = temp;

i++; j--;

}

} while ( i<=j );

// рекурсивные вызовы, если есть, что сортировать

if ( j > 0 ) quickSortR(a, j);

if ( N > i ) quickSortR(a+i, N-i);

}

Каждое разделение требует, очевидно, Theta(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n2) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге... Вообще говоря, малореальная ситуация.

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

Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек.

Поиск пути

На гребне волны...

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

Алгоритм работает следующим образом. Находим точку А, из которой начинается поиск, и в этом месте в вспомогательном массиве ставим 0. Во всех свободных ячейках, которые прилегают к ячейке с нулем, пишем 1. Во всех свободных от цифр и препятствий ячейках, которые прилегают к ячейкам с 1, пишем 2. Повторяем этот процесс для всех остальных ячеек, пока не дойдем до ячейки B, путь до которой нам требовалось найти. Если вы визуализируете этот процесс в динамике, то увидите, что от точки A разбегается волна из цифр. Отсюда и название алгоритма. Как только наша цифровая волна захлестнет точку B, строим от нее путь до точки A по правилу: следующая точка пути должна лежать в ячейке с меньшим, чем в текущей ячейке числом.

Алгоритм неплохо справляется с разного рода тупиками и всегда найдет путь из A в B, если он вообще существует. Другое дело, что этот путь редко будет кратчайшим из возможных. К сожалению, волновой поиск нельзя использовать на больших картах (с десятком тысяч и более клеток), так как он работает очень медленно.

Поиск в глубину

Предыдущий алгоритм иногда называют поиском в ширину, потому что он уровень за уровнем просматривает ближайшие клетки. Поиск в глубину выбирает какое-то одно направление и просматривает его вглубь на заданное число клеток, переходит к следующему направлению и так далее, пока не найдет конечную точку. Представленная ниже рекурсивная функция находит не все возможные пути. Чтобы найти кратчайший путь, надо вызвать эту функцию для каждой из клеток, прилегающих к начальной клетке. Во вспомогательном булевом массиве Mark такого же размера, как и остальная карта, хранится 1, если текущая клетка уже пройдена алгоритмом, и 0 — в противном случае. В переменных Destination_x и Destination_y должны храниться координаты точки, куда в итоге надо попасть. В глобальной перемененной Length будет храниться длина текущего пути, чтобы мы не залетели вглубь матрицы дальше, чем MAX_LENGTH.

Procedure DepthSearch(x,y:integer);

Var

i : integer;

Begin

If Length>MAX_LENGTH then exit;

Mark[x,y] := True;

If (x=Destination_x) and (y=Destination_y) then

Begin

{

Мы нашли эту точку! Искомый путь представлен значениями True в массиве Mark. Здесь вы можете запомнить построенный путь и очистить Mark[x,y], чтобы продолжить поиск, или же остановиться, если задачей было найти хотя бы один путь.

}

End;

Length:=Length+1;

If Mark[x+1,y]=false then DepthSearch(x+1,y);

If Mark[x,y+1]=false then DepthSearch(x,y+1);

If Mark[x+1,y+1]=false then DepthSearch(x+1,y+1);

If Mark[x-1,y-1]=false then DepthSearch(x-1,y-1);

If Mark[x-1,y]=false then DepthSearch(x-1,y);

If Mark[x,y-1]=false then DepthSearch(x,y-1);

Length:=Length-1;

End;

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

Примеры программ

Половинное деление

int Find(int *array, int size)

{

int a = 0,b = size-1,t;

{

t = (b+a)/2;

if (m[t] == x)return t;

if (m[t]>x) b = t;

else a = t;

}while (b-a>1);

if (m[a] == x) return a;

if (m[b] == x) return b;

return -1;

}

Сортировка пузырьком

int t;

char flag;

{

flag = 0;

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

if (m[i]>m[i+1]) {t=m[i];m[i]=m[i+1];m[i+1]=t;flag=1;}

}while(flag)

Обход дерева

struct Node

{

Node *parent,*left,*right;

};

void Action(Node *node)

{

if (node == NULL) return;

//action;

Action(node->left);

Action(node->right);

}

void Action2(Node *node)

{

queue<Node*> q;

q.push(node);

{

node = q.front();

q.pop();

//action

if (node->left!=NULL) q.push(node->left);

if (node->right!=NULL) q.push(node->right);

}

while(!q.empty)

}

Список литературы

Иванова Г.С. Технология программирования: Учебник для вузов. – М.: МГТУ им. Н.Э.Баумана, 2002.
Подбельский В.В. Язык С++: Учебн. пособие. – М.: Финансы и статистика, 1995.
Г. Майерс. Надёжность программного обеспечения. 1976 // Перев. на русский язык под ред. И.А.Махован и др. – М.: Мир, 1980.
В. В. Шураков. Надежность программного обеспечения систем обработки данных : учеб. для вузов. Изд. 2-е, пеpеpаб. и доп. — М. : Финансы и статистика, 1987 .— 272 с
Электронная энциклопедия ru.wikipedia.org

Бесплатный конструктор сайтов — uCoz

Часть 1. Языки программирования «С», «С++».

Алфавит

Объявление переменных. Типы данных

Простые типы данных

Структурированные типы данных

Константы

Операции

Присваивание.

Арифметические:

Логические (результат – логическое значение).

Операции работы с указателями.

Укороченные операции:

Инкремент и декремент

Операция ","

Операция "?:"

Операция sizeof(тип_данных/имя_переменной).

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

if

while

for

break

continue

switch

Функции

Директивы препроцессора

Метки

Указатели

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

Типизированные и нетипизированные указатели. Операции над указателями

Массивы

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

Функции работы с памятью

Строки.

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

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

Работа с файлами.

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

Часть 2. Введение в технологию программирования.

Этапы развития программирования.

Проблемы разработки сложных программных систем:

Жизненный цикл программного продукта.

Модели ЖЦ.

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

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

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

Требования, цели

Внешнее проектирование.

Диаграммы потоков данных (Data Flow Diagrams).

Диаграммы «сущность-связь» (Entity-Relationship Diagrams).

Диаграммы переходов состояний (State Transition Diagrams).

Функциональные диаграммы.

Описание структур данных

Проектирование архитектуры

Проектирование модульной структуры.

Модуль

Внешнее проектирование модулей

Модульная декомпозиция

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

Рекомендации по внесению ясности в текст программы:

Введение в объектно-ориентированное программирование

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

Документирование.

Пользовательский интерфейс

Часть 3. Типовые структуры данных и алгоритмы.

3.1 Структуры данных

Логические структуры данных:

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

Организация двусвязанного списка.

Организация массива переменного размера:

3.2 Алгоритмы

Быстрая сортировка

Поиск пути

Примеры программ

Список литературы