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

Размещено на http://www.allbest.ru/

Министерство образования и науки, молодёжи и спорта Украины

Харьковский национальный университет радиоэлектроники

Центр заочной формы обучения

Контрольная работа

По дисциплине «Информатика»

Харьков 2012

1. Алгоритмический язык С++. Символы языка. Типы данных и их внутренне представление

Язык C++ - это язык программирования общего назначения, цель которого - сделать работу серьёзных программистов более приятным занятием. За исключением несущественных деталей, язык C++ является надмножеством языка С. Помимо возможностей, предоставляемых языком С, язык C++ обеспечивает гибкие и эффективные средства определения новых типов.

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

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

адресов и т.д. Это позволяет реализовывать пользовательские типы с достаточной степенью эффективности.

1) Алфавит

Множество символов языка C включает:

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

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

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

- разделители: , . ; : ? ! ' " | / \ ~ _ ^ ( ) { } [ ] < > # % & - = + *

Остальные символы могут быть использованы только в символьных строках, символьных константах и комментариях. Язык C++ различает большие и маленькие буквы, таким образом, name и Name - разные идентификаторы.

2) Литералы

Литералы в языке C++ могут быть целые, вещественные, символьные и строковые.

Целые:

- десятичные: 10, 132, -32179;

-восьмеричные (предваряются символом «0»): 010, 0204, -076663;

- шестнадцатеричные (предваряются символами «0х»): 0хА, 0x84, 0x7db3.

Вещественные: 15.75, 1.575e1, .75, -.125

Символьные: 'a', 'e', '.', '?', '2'.

Строковые: "строка".

3) Типы данных языка C++

В языке C++ существуют перечислимый тип - enum, который является подмножеством целого типа, и пустой тип - void, который имеет специальное назначение. Он используется для объявления функций, которые не возвращают никакого значения, а также для объявления указателей на значение типа void. Такие указатели могут быть преобразованы к указателям на любой другой тип.

В языке С++ можно объявлять структуры и так называемые объединения.

В языке C++ нет специальных типов для массивов и строк, которые представляются массивом символов.

В языке С не существовало логического типа. Логические значения представлялись данными целого типа, при этом значение 0 соответствовало логическому значению ложь, а все остальные целые значения соответствовали логическому значению истина. В языке С++ сохранена данная логика. По определению, true имеет значение 1 при преобразовании к целому типу, а false - значение 0. И наоборот, целые можно неявно преобразовать в логические значения: при этом ненулевые целые преобразуются в true, а ноль - в false. В любом месте, где требуется логическое значение, может стоять целочисленное выражение. В арифметических и логических выражениях логические значения преобразуются в целые, операции выполняются над преобразованными величинами.

Указатель можно неявно преобразовать в логическое значение, при этом ненулевой указатель принимает значение true, нулевой - false.

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

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

а) если один из операндов имеет тип long double, другой тоже преобразуется в long double;

- иначе, если один операнд имеет тип double, то второй операнд преобразуется к типу double;

- иначе, если один операнд имеет тип float, то второй операнд преобразуется к типу float;

- иначе над обоими операндами производится интегральное продвижение, а именно: значения типов char, signed char, unsigned char, short int и unsigned short int преобразуются в int, если int может представить все значения исходных типов, в противном случае они преобразуются в unsigned int; bool преобразуется в int.

б) затем если один операнд имеет тип unsigned long, то второй операнд преобразуется к типу unsigned long;

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

- иначе, если один операнд имеет тип long int, то второй операнд преобразуется к типу long int;

-иначе, если один операнд имеет тип unsigned int, то второй операнд преобразуется к типу unsigned int;

- иначе оба операнда имеют тип int.

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

4) Операции языка C++

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

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

[ ] - индексное выражение, используется для работы с массивами.

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

Операции static_cast (преобразование с проверкой во время компиляции), dynamic_cast (преобразование с проверкой во время выполнения), reinterpret_cast (преобразование без проверки), const_cast (константное преобразование) осуществляют различные преобразования типов. Они имеют следующий синтаксис: операция<новый тип>(выражение). Угловые скобки являются элементом синтаксиса. Операция static_cast осуществляет преобразование родственных типов, например, указателя на один тип к указателю на другой тип из той же иерархии классов, целый тип в перечисление или тип с плавающей точкой в интегральный. Операция reinterpret_cast управляет преобразованиями между несвязанными типами, например, целых в указатели или указателей в другие (несвязанные) указатели. Такое различие позволяет компилятору осуществлять минимальную проверку типов при использовании static_cast, а программисту - легче обнаружить опасные преобразования, представляемые reinterpret_cast. Преобразование dynamic_cast выполняется и проверяется на этапе выполнения. Преобразование const_cast аннулирует действие модификатора const.

- - унарный минус.

~ - обратный код

! - логическое отрицание.

* - косвенная адресация

& - адресация

2. Обработка строковых данных. Текстовые переменные. Обработка текстов

Строка - это последовательность (массив) символов (типа char), которая заканчивается специальным символом - признаком конца строки. Это символ записывается как '\0' (не путайте с символом переноса строки '\n') и равен 0. При вводе строки символ конца строки добавляется автоматически. Все функции работы со строками - и стандартные, и создаваемые программистом - должны ориентироваться на этот символ. Если требуется сформировать новую строку, то обязательно надо добавлять признак конца строки. Если этого не сделать, то при дальнейшей работе возникнут ошибки.

'a' // Символьная константа - один символ

"a" // Строковый литерал - массив из двух символов 'a' и '\0', заменяется на адрес.

char str[51]; // Объявление строки

char *str; // Нельзя, т.к. не выделяется память под элементы строки

char *str = "abcd"; // Можно, но очень осторожно!

char *str1 = "abc", *str2 = "abc"; // Не известно, будет ли выполняться str1 == str2?

Строковым литералом называется последовательность символов, заключённых в двойные кавычки. В строковом литерале на один символ больше, чем используется при его записи - добавляется символ '\0'.

Тип строкового литерала есть «массив с надлежащим количество константных символов». Строковый литерал можно присвоить переменной типа char *. Это разрешается, потому что в предыдущих определениях С и C++ типом строкового литерала был char *. Однако изменение строкового литерала через такой указатель является ошибкой.

char *str = "С & С++";

str[2] = '?'; // Ошибка времени выполнения!

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

char str[] = "С & С++"; // Массив из 8 символов

str[2] = '?'; // Правильно

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

const char *error_massage()

{ return "Недостаточно параметров"; } // После выхода из функции память, содержащая строку, не будет освобождена

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

for (int i = 0; str[i] != '\0'; i++) { ... }.

Можно опустить сравнение с нулем, для C++ это будет эквивалентно:

for (int i = 0; str[i]; i++) { ... }.

Можно использовать указатели для обработки строк:

char str[50], *p;

for (p = str; *p; p++) { ... }.

Заголовки стандартных функций работы со строками хранятся в файле <string.h>. Основными из этих функций являются:

- Определение длины строки - int strlen(const char *str);

- Сравнение строк - int strcmp(const char *str1, const char *str2);

- Копирование - char *strcpy(char *str1, const char *str2);

- Конкатенация строк - char *strcat(char *str1, const char *str2);

- Поиск символа в строке - char *strchr(const char *str, char c);

- Поиск подстроки - char *strstr(const char *str1, const char *str2);

Ввод/вывод строки:

- Ввод строки до пробела или другого разделителя - функция scanf с форматом %s;

- Ввод строки, содержащей пробелы - char *gets (char *buffer);

- Ввод строки из файла, n задаёт максимальное количество символов для ввода - char *fgets(char *string, int n, FILE *stream);

- Вывод строки с форматированием - функция printf с форматом %s;

- Вывод строки - int puts(const char *string);

- Вывод строки в файл - int fputs(const char *string, FILE *stream);

программирование рекурсия данные переменная

3. Рекурсия

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

Термин «рекурсия» используется в различных специальных областях знаний - от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

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

Примеры

*Метод Гаусса - Жордана для решения систем линейных алгебраических уравнений является рекурсивным.

*Факториал целого неотрицательного числа n (обозначается ) определяется как

*Числа Фибоначчи определяются с помощью рекуррентного соотношения:

Первое и второе числа Фибоначчи равны 1

Для n>2,n -e число Фибоначчи равно сумме (n-1)-го и (n-2) -го чисел Фибоначчи

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

*Рекурсивные акронимы: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) и т. д.

4. Рекурсия в программировании. Функции

В программировании рекурсия - вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функциюB , а функция A - функцию B. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

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

Любую рекурсивную функцию можно заменить циклом и стеком.

Данные

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

struct element_of_list

{

element_of_list *next; /* ссылка на следующий элемент того же типа */

int data; /* некие данные */

};

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

Перечень ссылок

1. Подбельский В.В Язык С++: Учеб. пособие. -5-е изд. - М.: Финансы и статистика, 2003.-560с.

2. Язык С++: Учебн. пособие/ И.Ф. Астахова, С.В. Власов, В.В. Фертиков, А.В. Ларин. - Мн.: Новое знание, 2003.-203с.

3. Информационный портал filefacts.net http://www.filefacts.net/ru/doc-file-extension

Размещено на Allbest.ru