Контрольная работа по программированию заказать

Если у вас нету времени на контрошу по программированию вы всегда можете попросить меня, вам нужно написать мне, и я вам помогу онлайн или в срок 1-3 дня всё зависит что там у вас за работа, вдруг она огромная!

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

 

 

 

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

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

Задача этого пособия - дать краткое и четкое изложение языка С++. Пособие предназначено для студентов, изучающих язык «с нуля», но будет полезно и более искушенным в программировании.

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

 

Состав языка

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

Контрольная работа по программированию заказать

Алфавит языка, или его символы - это основные неделимые знаки, с помощью которых пишутся все тексты на языке.

Лексема, или элементарная конструкция - минимальная единица языка, имеющая самостоятельный смысл.

Выражение задает правило вычисления некоторого значения.

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

Для описания сложного действия требуется последовательность операторов. Операторы могут быть объединены в составной оператор, или блок (блоком в языке С++ считается последовательность операторов, заключенная в фигурные скобки { }). В этом случае они рассматриваются как один оператор.

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

 

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

Алфавит С++ включает:

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

 

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

Помощь с контрольными работами

 

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

Идентификатор - это имя программного объекта. В идентификаторе могут использоваться латинские буквы, цифры и знак подчеркивания. Прописные и строчные буквы различаются, например, sysop, SySoP и SYSOP - три различных имени. Первым символом идентификатора может быть буква или знак подчеркивания, но не цифра. Пробелы внутри имен не допускаются.

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

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

 

По этой ссылке вы сможете научиться оформлять контрольную работу:

Теоретическая контрольная работа примеры оформления

 

Ключевые слова

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

 

Таблица 1 - Список ключевых слов С++

asm

auto

bool

break

case

catch

char

class

const

const_cast

continue

default

delete

do

double

dynamic_cast

else

enum

explicit

export

extern

false

float

for

friend

goto

if

inline

int

long

mutable

namespace

new

operator

private

protected

public

register

reinterpret_cast

return

short

signed

sizeof

static

static_cast

struct

switch

template

this

throw

true

try

typedef

typeid

typename

union

unsigned

using

virtual

void

volatile

wchar_t

while

 

 

 

 

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

Знак операции - это один или более символов, определяющих действие над операндами. Внутри знака операции пробелы не допускаются. Операции делятся на унарные, бинарные и тернарную по количеству участвующих в них операндов. Один и тот же знак может интерпретироваться по-разному в зависимости от контекста. Все знаки операций за исключением [ ], ( ) и ? : представляют собой отдельные лексемы.

 

 

Константы

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

Форматы констант, соответствующие каждому типу, приведены в таблице 2.

Допустимые диапазоны значений целых и вещественных констант приведены в таблице 4.

Если требуется сформировать отрицательную целую или вещественную константу, то перед константой ставится знак унарной операции изменения знака (-), например: -218, -022, -0х3С, -4.8, -0.1е4.

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

 

Таблица 2 - Константы в языке С++

Константа

Формат

Примеры

Целая

Десятичный: последовательность десятичных цифр, начинающаяся не с нуля, если это не число нуль

8, 0, 199226

Восьмеричный: нуль, за которым следуют восьмеричные цифры (0,1,2,3,4,5,6,7)

01, 020, 07155

Шестнадцатеричный: 0х или 0Х,

за которым следуют шестнадцатеричные

цифры (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)

0хА, 0x1В8, 0X00FF

Вещественная

Десятичный: [цифры].[цифры]

5.7, .001, 35

Экспоненциальный: [цифры][.][цифры]{Е|е}[+|-][цифры]

0.2Е6, .11e-3, 5Е+10

Символьная

Один или два символа, заключенных в апострофы

'А', 'ю', '*', 'db', '\0', '\n'

Строковая

Последовательность символов, заключенная в кавычки

"Здесь был Vasia", "\tЗначение r=\0xF5\n"

 

Символьные константы, состоящие из одного символа, занимают в памяти один байт и имеют стандартный тип char. Двухсимвольные константы занимают два байта и имеют тип int, при этом первый символ размещается в байте с меньшим адресом.

 

По этой ссылке вы сможете заказать контрольную работу:

Заказать контрольную работу

 

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

  • кодов, не имеющих графического изображения (например, \a - звуковой сигнал, \n - перевод курсора в начало следующей строки);
  • символов апострофа ( ' ), обратной косой черты ( \ ), знака вопроса (?) и кавычки ( " );
  • любого символа с помощью его шестнадцатеричного или восьмеричного кода, например, \073, \0xF5. Числовое значение должно находиться в диапазоне от 0 до 255.

Последовательности символов, начинающиеся с обратной косой черты, называют управляющими, или escape-последовательпостями. В таблице 3 приведены их допустимые значения. Управляющая последовательность интерпретируется как одиночный символ. Если непосредственно за обратной косой чертой следует символ, не предусмотренный таблицей 3, результат интерпретации не определен. Если в последовательности цифр встречается недопустимая, она считается концом цифрового кода.

 

Таблица 3 - Управляющие последовательности в языке С++

Изображение

Шестнадцатеричный код

Наименование

7

Звуковой сигнал

\b

8

Возврат на шаг

\f

С

Перевод страницы (формата)

\n

А

Перевод строки

D

Возврат каретки

\t

9

Горизонтальная табуляция

\v

В

Вертикальная табуляция

\\

Обратная косая черта

\'

27

Апостроф

\"

22

Кавычка

\?

3F

Вопросительный знак

\0ddd

-

Восьмеричный код символа

\0xddd

ddd

Шестнадцатеричный код символа

 

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

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

В конец каждого строкового литерала компилятором добавляется нулевой символ, представляемый управляющей последовательностью \0. Поэтому длина строки всегда на единицу больше количества символов в ее записи. Таким образом, пустая строка "" имеет длину 1 байт. Обратите внимание на разницу между строкой из одного символа, например, "А", и символьной константой 'А'.

Пустая символьная константа недопустима.

 

Комментарии

Комментарий либо начинается с двух символов «прямая косая черта» (//) и заканчивается символом перехода на новую строку, либо заключается между символами-скобками /* и */. Внутри комментария можно использовать любые допустимые на данном компьютере символы, а не только символы из алфавита языка С++, поскольку компилятор комментарии игнорирует. Вложенные комментарии-скобки стандартом не допускаются, хотя в некоторых компиляторах разрешены.

Рекомендуется использовать для пояснений //-комментарии, а скобки /* */ применять для временного исключения блоков кода при отладке.

 

Типы данных С++

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

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

Тип данных определяет:

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

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

 

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

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

  • int (целый);
  • char (символьный);
  • wchar_t [1](расширенный символьный);
  • bool (логический);
  • float (вещественный);
  • double (вещественный с двойной точностью).

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

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

  • short (короткий);
  • long (длинный);
  • signed (знаковый);
  • unsigned (беззнаковый).
  • целый тип (int)

Размер типа int не определяется стандартом, а зависит от компьютера и компилятора. Для 16-разрядного процессора под величины этого типа отводится 2 байта, для 32-разрядного - 4 байта.

Спецификатор short перед именем типа указывает компилятору, что под число требуется отвести 2 байта независимо от разрядности процессора. Спецификатор long означает, что целая величина будет занимать 4 байта. Таким образом, на 16-разрядном компьютере эквиваленты int и short int, а на 32-разрядном - int и long int.

Внутреннее представление величины целого типа - целое число в двоичном коде. При использовании спецификатора signed старший бит числа интерпретируется как знаковый (0 - положительное число, 1 - отрицательное). Спецификатор unsigned позволяет представлять только положительные числа, поскольку старший разряд рассматривается как часть кода числа. По умолчанию все целочисленные типы считаются знаковыми, то есть спецификатор signed можно опускать.

 

Возможно вам пригодятся эти страницы:

Контрольная работа по гидравлике заказать
Контрольная работа по механике заказать
Контрольная работа по электронике заказать
Контрольная работа по бизнес планированию заказать

 

Константам, встречающимся в программе, приписывается тот или иной тип в соответствии с их видом. Если этот тип по каким-либо причинам не устраивает программиста, он может явно указать требуемый тип с помощью суффиксов L, l (long) и U, u (unsigned). Например, константа 32L будет иметь тип long и занимать 4 байта. Можно использовать суффиксы L и U одновременно, например, 0x22UL или 05Lu.

Типы short int, long int, signed int и unsigned int можно сокращать до short, long, signed и unsigned соответственно.

Символьный тип (char)

Под величину символьного типа отводится количество байт, достаточное для размещения любого символа из набора символов для данного компьютера, что и обусловило название типа. Как правило, это 1 байт. Тип char, как и другие целые типы, может быть со знаком или без знака. В величинах со знаком можно хранить значения в диапазоне от -128 до 127. При использовании спецификатора unsigned значения могут находиться в пределах от 0 до 255. Этого достаточно для хранения любого символа из 256-символьного набора ASCII. Величины типа char применяются также для хранения целых чисел, не превышающих границы указанных диапазонов.

Логический тип (bool)

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

Типы с плавающей точкой (float, double и long double)

Стандарт С++ определяет три типа данных для хранения вещественных значений: float, double и long double.

Типы данных с плавающей точкой хранятся в памяти компьютера иначе, чем целочисленные. Внутреннее представление вещественного числа состоит из двух частей - мантиссы и порядка. В IBM PC-совместимых компьютерах величины типа float занимают 4 байта, из которых один двоичный разряд отводится под знак мантиссы, 8 разрядов под порядок и 23 под мантиссу. Мантисса - это число, большее 1.0, но меньшее 2.0. Поскольку старшая цифра мантиссы всегда равна 1, она не хранится.

Для величин типа double, занимающих 8 байт, под порядок и мантиссу отводится 11 и 52 разряда соответственно. Длина мантиссы определяет точность числа, а длина порядка - его диапазон. Как можно видеть из таблицы 4, при одинаковом количестве байт, отводимом под величины типа float и long int, диапазоны их допустимых значений сильно различаются из-за внутренней формы представления.

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

Константы с плавающей точкой имеют по умолчанию тип double. Можно явно указать тип константы с помощью суффиксов F, f (float) и L, l (long). Например, константа 2E+6L будет иметь тип long double, а константа 1.82f - тин float.

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

 

 

Таблица 4 - Диапазоны значений простых типов данных для IBM PC

Тип

Диапазон значений

Размер (байт)

bool

true и false

1

signed char

-128 ... 127

1

unsigned char

0 ... 255

1

signed short int

-32 768 ... 32 767

2

unsigned short int

0 ... 65 535

2

signed long int

-2 147 483 648 ... 2 147 483 647

4

unsigned long int

0 ... 4 294 967 295

4

float

3.4e-38 ... 3.4e+38

4

double

1.7e-308 ... 1.7c+308

8

long double

3.4e-4932 ... 3.4e+4932

10

 

Тип void

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

 

Структура программы

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

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

Пример структуры программы, содержащей функции main, f1 и f2:

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

описания

int main(){операторы главной функции}

int f1(){операторы функции f1}

int f2(){операторы функции f2}

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

 

Ввод/вывод

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

Основные функции ввода/вывода в стиле С:

scanf // ввод

printf // вывод

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

 

Таблица 5 - Спецификации формата для функций семейства printf

Спецификация

Пояснение

с

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

d, i

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

е, Е

аргумент, рассматриваемый как переменная типа float или double, преобразуется в десятичную форму в виде

[-]m.nnnnnne[+-]xx, где длина строки из n определяется указанной точностью. Точность по умолчанию равна 6

f

аргумент, рассматриваемый как переменная типа float или double, преобразуется в десятичную форму в виде

[-]mmm.nnnnn, где длина строки из n определяется указанной точностью. Точность по умолчанию равна 6

g,G

используется формат или %f, который короче; незначащие нули не печатаются

o

аргумент преобразуется в беззнаковую восьмеричную форму (без лидирующего нуля)

р

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

s

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

u

аргумент преобразуется в беззнаковую десятичную форму

х, X

аргумент преобразуется в беззнаковую шестнадцатеричную форму (без лидирующих 0х)

%

выводится символ %

 

Модификаторы формата

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

Если указанного количества позиций для размещения значения недостаточно, автоматически выделяется большее количество позиций: %minC (%-minC) или %min.precisionC (%-min.precisionC).

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

  • при выводе строки (спецификация %s) precision указывает максимальное число символов для вывода;
  • при выводе вещественного числа (спецификации %f или ) precision указывает количество цифр после десятичной точки;
  • при выводе целого числа (спецификации %d или %i), precision указывает минимальное количество выводимых цифр. Если число представляется меньшим числом цифр, чем указано в precision, выводятся ведущие (начальные) нули;
  • при выводе вещественного числа (спецификации %g или %G) precision указывает максимальное количество значащих цифр, которые будут выводиться.

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

Перед спецификацией могут использоваться префиксы l и h, например, %lf, %hu.

Префикс h с типами d, i, о, х и X указывает на то, что тип аргумента short int, а с типом u - short unsigned int.

Префикс l с типами d, i, о, х и X указывает на то, что тип аргумента long int, с типом u - long unsigned int, а с типами е, Е, f, g и G - что тип аргумента double, а не float.

Пример использования строки формата:

#include <stdio.h>

int main(){

int int1 = 45, int2 = 13;

float f = 3.621;

double dbl = 2.23;

char ch = 'z', *str = "ramambahari";

printf("intl = %d| int2 = %10d| int2 = %-15d|\n", int1, int2, int2);

printf("intl = %X| int2 = %10x| int2 = %-15o|\n", int1, int2, int2);

printf("f = %f| f = %4.2f| f = %6.1f|\n", f, f, f);

printf("f = %g| f = %e| f = %+E|\n", f, f, f);

printf("dbl = %5.2lf| dbl = %e| dbl = %4.1G| \n", dbl, dbl, dbl);

printf("ch = %c| ch = %3c| \n", ch, ch);

printf("str = %14s| \nstr = %-14s| \nstr = %s| \n", str, str, str);

return 0;

}

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

intl = 45| int2 = 13| int2 = 13 |

intl = 2D| int2 = D| int2 = 15 |

f = 3.621000| f = 3.62| f = 3.6|

f = 3.621| f = 3.621000e+000| f=+3.621000E+000|

dbl = 2.23| dbl = 2.230000e+000| dbl = 2|

ch = z| ch = z |

str = ramambahari|

str = ramambahari |

str = ramambahari|

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

#include <stdio.h>

int main(){

int i;

printf("Введите целое число\n");

scanf("%d", &i);

printf("Вы ввели число %d, спасибо!", i);

return 0;

}

Первая строка этой программы - директива препроцессора (#include), по которой в текст программы вставляется заголовочный файл <stdio.h>, содержащий описание использованных в программе функций ввода/вывода (в данном случае угловые скобки являются элементом языка). Все директивы препроцессора начинаются со знака #. Третья строка - описание переменной целого типа с именем i. Функция printf в четвертой строке выводит приглашение «Введите целое число» и переходит на новую строку в соответствии с управляющей последовательностью \n. Функция scanf заносит введенное с клавиатуры целое число в переменную i (знак & означает операцию получения адреса), а следующий оператор выводит на экран указанную в нем строку, заменив спецификацию преобразования на значение этого числа.

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

#include <iostream.h>

int main(){

int i;

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

cin >> i;

cout << "Вы ввели число " << i << ", спасибо!";

return 0;

}

Заголовочный файл <iostream.h> содержит описание набора классов для управления вводом/выводом. В нем определены стандартные объекты-потоки cin для ввода с клавиатуры и cout для вывода на экран, а также операции помещения в поток << и чтения из потока >>.

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

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

Флаги и форматирующие методы

Флаги представляют собой отдельные биты, объединенные в поле x_flags типа long класса ios. Флаги перечислены в таблице 6.

 

Таблица 6 - Флаги форматирования

Флаг

Положение

Умолчание

Описание действия при установленном бите

skipws

0x0001

+

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

left

0x0002

 

Выравнивание по левому краю поля

right

0x0004

+

Выравнивание по правому краю поля

internal

0x0008

 

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

dec

0x0010

+

Десятичная система счисления

oct

0x0020

 

Восьмеричная система счисления

hex

0x0040

 

Шестнадцатеричная система счисления

showbase

0x0080

 

Выводится основание системы счисления (0х для шестнадцатеричных чисел и 0 для восьмеричных)

showpoint

0x0100

 

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

uppercase

0x0200

 

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

showpos

0x0400

 

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

scientific

0x0800

 

Печатать вещественные числа в форме мантиссы с порядком

fixed

0x1000

 

Печатать вещественные числа в форме с фиксированной точкой (точность определяется полем x_precision)

unitbuf

0x2000

 

Выгружать буферы всех потоков после каждого вывода

stdio

0x4000

 

Выгружать буферы потоков stdout и stderr после каждого вывода

 

Флаги (left, right и internal), (dec, oct и hex), а также (scientific и fixed) взаимно исключают друг друга, то есть в каждый момент может быть установлен только один флаг из каждой группы.

Для управления флагами в классе ios есть методы flags, setf и unsetf:

long ios::flags(); - возвращает текущие флаги потока;

long ios:: flags (long); - присваивает флагам значение параметра;

long ios:: setf (long, long); - присваивает флагам, биты которых установлены в первом параметре, значение соответствующих битов второго параметра;

long ios:: setf (long); - устанавливает флаги, биты которых установлены в параметре;

long ios::unsetf(long); - сбрасывает флаги, биты которых установлены в параметре.

Все функции возвращают прежние флаги потока.

Кроме флагов, для форматирования используются следующие поля класса ios:

  • int x_width - минимальная ширина поля вывода;
  • int x_precision - количество цифр в дробной части при выводе вещественных чисел с фиксированной точкой или общее количество значащих цифр при выводе в форме с мантиссой и порядком;
  • int x_fill - символ заполнения поля вывода.

Для управления этими полями используются методы width, precision и fill:

  • int ios:: width () - возвращает значение ширины поля вывода;
  • int ios:: width (int) - устанавливает ширину поля вывода в соответствии со значением параметра;
  • int ios:: precision() - возвращает значение точности представления при выводе вещественных чисел;
  • int ios: precision (int) - устанавливает значение точности представления при выводе вещественных чисел, возвращает старое значение точности;
  • char fill() - возвращает текущий символ заполнения;
  • char fill (char) - устанавливает значение текущего символа заполнения, возвращает старое значение символа.

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

adjustfield (left | right | internal)

basefield (dec | oct | hex)

floatfield (scientific | fixed)

Пример форматирования при выводе с помощью флагов и методов:

#include <iostream.h>

int main(){

long a = 1000, b = 077;

cout.width(7);

cout.setf(ios::hex | ios::showbase | ios:uppercase);

cout « a;

cout.width(7);

cout « b « endl;

double d = 0.12, с = 1.3e-4;

cout. setf (ios::left);

cout « d « endl;

cout « c;

return 0;

}

В результате работы программы в первой строке будут прописными буквами выведены переменные а и b в шестнадцатеричном представлении, под каждую из них отводится по 7 позиций (функция width действует только на одно выводимое значение, поэтому ее вызов требуется повторить дважды). Значения переменных с и d прижаты к левому краю поля:

0Х3Е8 0X3F

0.12

0.00013

Манипуляторы

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

Простые манипуляторы

Ниже перечислены манипуляторы, не требующие указания аргументов:

  • dec - устанавливает при вводе и выводе флаг десятичной системы счисления;
  • oct - устанавливает при вводе и выводе флаг восьмеричной системы счисления;
  • hex - устанавливает при вводе и выводе флаг шестнадцатеричной системы счисления;
  • ws - устанавливает при вводе извлечение пробельных символов;
  • endl - при выводе включает в поток символ новой строки и выгружает буфер;
  • ends - при выводе включает в поток нулевой символ;
  • flush - при выводе выгружает буфер.

Изменения системы счисления действуют до следующего явного изменения.

Пример:

cout « 13 « hex « ' ' « 13 « oct « ' ' « 13 « endl;

Если другие значения флагов установлены по умолчанию, будет выведено: 13 d 15

 

Параметризованные манипуляторы

Ниже перечислены манипуляторы, требующие указания аргумента (для их использования требуется подключить к программе заголовочный файл <iomanip>):

  • setbase(int n) - задает основание системы счисления (n = 8, 16, 10 или 0). 0 является основанием по умолчанию (десятичное, кроме случаев, когда вводятся 8- или 16-ричиые числа);
  • resetiosflags(long) - сбрасывает флаги состояния потока, биты которых установлены в параметре;
  • setiosflags(long) - устанавливает флаги состояния потока, биты которых в параметре равны 1;
  • setfill (int) - устанавливает символ-заполнитель с кодом, равным значению параметра;
  • setprecision(int) - устанавливает максимальное количество цифр в дробной части для вещественных чисел в форме с фиксированной точкой (флаг fixed) или общее количество значащих цифр для чисел в форме с мантиссой и порядком (флаг scientific);
  • setw(int) - устанавливает максимальную ширину поля вывода.

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

#include <iostream.h>

#include <iomanip.h>

int main(){

double d[] = {1.234, -12.34567, 123.456789, -1.234, 0.00001};

cout « setfill('.') « setprecision(4)

« setiosflags(ios::showpoint | ios::fixed);

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

cout « setw(12) « d[i] « endl;

return 0;}

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

…...1.2340
….-12.3457
….123.4568
…..-1.2340
…...0.0000

 

Переменные и выражения

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

Рассмотрим составные части выражений и правила их вычисления.

 

Переменные

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

Пример описания целой переменной с именем а и вещественной переменной х: int a; float х;.

Общий вид оператора описан ия переменных:

[класс памяти] [const] тип имя [инициализатор];

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

  • необязательный класс памяти может принимать одно из значений auto, extern, static и register. О них рассказывается чуть дальше;
  • модификатор const показывает, что значение переменной изменять нельзя. Такую переменную называют именованной константой, или просто константой;
  • при описании можно присвоить переменной начальное значение, это называется инициализацией. Инициализатор можно записывать в двух формах - со знаком равенства = значение или в круглых скобках (значение).

Константа должна быть инициализирована при объявлении. В одном операторе можно описать несколько переменных одного типа, разделяя их запятыми.

Примеры:

short int а = 1; // целая переменная а

const char С = 'С'; // символьная константа С

char s, sf = ' f'; // инициализация относится только к sf

char t (54);

float с = 0.22, x(3), sum;

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

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

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

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

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

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

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

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

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

static - статическая переменная. Время жизни - постоянное. Инициализируется один раз при первом выполнении оператора, содержащего определение переменной. В зависимости от расположения оператора описания статические переменные могут быть глобальными и локальными. Глобальные статические переменные видны только в том модуле, в котором они описаны;

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

int а; // 1 глобальная переменная a

main(){

int b; // 2 локальная переменная b

extern int x; // 3 переменная x определена в другом месте

static int c; // 4 локальная статическая переменная с

a = 1; // 5 присваивание глобальной переменной

int a; // 6 локальная переменная а

a = 2; // 7 присваивание локальной переменной

::a = 3; // 8 присваивание глобальной переменной

return 0;}

int x = 4; // 9 определение и инициализация х

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

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

Имя переменной должно быть уникальным в своей области действия (например, в одном блоке не может быть двух переменных с одинаковыми именами).

 

Операции

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

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

Таблица 7 - Основные операции языка С++

Операция

Краткое описание

Унарные операции

++

увеличение на 1

--

уменьшение на 1

sizeof

размер

~

поразрядное отрицание

!

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

-

арифметическое отрицание (унарный минус)

+

унарный плюс

&

взятие адреса

*

разадресация

new

выделение памяти

delete

освобождение памяти

(type)

преобразование типа

Бинарные и тернарная операции

*

умножение

/

деление

%

остаток от деления

+

сложение

-

вычитание

<<

сдвиг влево

>>

сдвиг вправо

<

меньше

<=

меньше или равно

>

больше

>=

больше или равно

==

равно

!=

не равно

&

поразрядная конъюнкция (И)

^

поразрядное исключающее ИЛИ

|

поразрядная дизъюнкция (ИЛИ)

&&

логическое И

||

логическое ИЛИ

?:

условная операция (тернарная)

=

присваивание

*=

умножение с присваиванием

/=

деление с присваиванием

%=

остаток отделения с присваиванием

+=

сложение с присваиванием

-=

вычитание с присваиванием

<<=

сдвиг влево с присваиванием

>>=

сдвиг вправо с присваиванием

&=

поразрядное И с присваиванием

|=

поразрядное ИЛИ с присваиванием

^=

поразрядное исключающее ИЛИ с присваиванием

,

последовательное вычисление

     

 

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

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

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

#include <stdio.h>

int main(){

int x = 3, у = 3;

printf("Значение префиксного выражения: %d\n", ++х);

printf("Значение постфиксного выражения: %d\n", у++);

printf("Значение х после приращения: %d\n", х);

printf("Значение у после приращения: %d\n", у);

return 0;

}

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

Значение префиксного выражения: 4

Значение постфиксного выражения: 3

Значение х после приращения: 4

Значение у после приращения: 4

Операция определения размера sizeof предназначена для вычисления размера объекта или типа в байтах, и имеет две формы: sizeof выражение и sizeof ( тип ).

Операции отрицания (-, ! и ~). Арифметическое отрицание (унарный минус -) изменяет знак операнда целого или вещественного типа на противоположный. Логическое отрицание (!) дает в результате значение 0, если операнд есть истина (не нуль), и значение 1, если операнд равен нулю. Операнд должен быть целого или вещественного типа, а может иметь также тип указатель. Поразрядное отрицание (~), часто называемое побитовым, инвертирует каждый разряд в двоичном представлении целочисленного операнда.

Деление (/) и остаток от деления (%). Операция деления применима к операндам арифметического типа. Если оба операнда целочисленные, результат операции округляется до целого числа, в противном случае тип результата определяется правилами преобразования. Операция остатка от деления применяется только к целочисленным операндам. Знак результата зависит от реализации.

Операции сдвига (« и ») применяются к целочисленным операндам. Они сдвигают двоичное представление первого операнда влево или вправо на количество двоичных разрядов, заданное вторым операндом. При сдвиге влево («) освободившиеся разряды обнуляются. При сдвиге вправо (») освободившиеся биты заполняются нулями, если первый операнд беззнакового типа, и знаковым разрядом в противном случае. Операции сдвига не учитывают переполнение и потерю значимости.

Операции отношения (<, <=, >, >=, == (два =), !=) сравнивают первый операнд со вторым. Операнды могут быть арифметического типа или указателями. Результатом операции является значение true или false (любое значение, не равное нулю, интерпретируется как true). Операции сравнения на равенство и неравенство имеют меньший приоритет, чем остальные операции сравнения.

Поразрядные операции (&, |, ^) применяются только к целочисленным операндам и работают с их двоичными представлениями. При выполнении операций операнды сопоставляются побитово (первый бит первого операнда с первым битом второго, второй бит первого операнда со вторым битом второго, и т д.).

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

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

При поразрядном исключающем ИЛИ (операция обозначается ^) бит результата равен 1 только тогда, когда соответствующий бит только одного из операндов равен 1.

#include <iostream.h>

int main(){

cout « "\n 6 & 5 = " « (6 & 5);

cout « "\n 6 | 5 = " « (6 | 5);

cout « "\n 6 ^ 5 = " « (6 ^ 5);

return 0;

}

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

6 & 5 = 4

6 | 5 = 7

6 ^ 5 = 3

Логические операции (&& и ||). Операнды логических операций И (&&) и ИЛИ (||) могут иметь арифметический тип или быть указателями, при этом операнды в каждой операции могут быть различных типов. Преобразования типов не производятся, каждый операнд оценивается с точки зрения его эквивалентности нулю (операнд, равный нулю, рассматривается как false, не равный нулю - как true).

Результатом логической операции является true или false. Результат операции логическое И имеет значение true, только если оба операнда имеют значение true. Результат операции логическое ИЛИ имеет значение true, если хотя бы один из операндов имеет значение true. Логические операции выполняются слева направо. Если значения первого операнда достаточно, чтобы определить результат операции, второй операнд не вычисляется.

Операции присваивания (=, +=, *= и т. д.). Операции присваивания могут использоваться в программе как законченные операторы.

Формат операции простого присваивания (=):

переменная = выражение

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

В сложных операциях присваивания (+=, *=, /= и т.п.) при вычислении выражения, стоящего в правой части, используется и значение из левой части. Например, при сложении с присваиванием к правому операнду прибавляется левый, и результат записывается в левый операнд, то есть выражение a+=b является более компактной записью выражения a=a+b.

Условная операция (?:). Эта операция тернарная, то есть имеет три операнда. Ее формат: операнд_1 ? операнд_2 : операнд_3

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

#include <stdio.h>

int main(){

int a = 11, b = 4, max;

max = (b > a)? b : a;

printf("Наибольшее число: %d", max);

return 0;

}

Результат работы программы: Наибольшее число: 11

 

Выражения

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

В выражениях можно также использовать стандартные математические функции, описание которых находится в заголовочных файлах <math.h> (<cmath>). Они позволяют получить абсолютное значение (abs, fabs), округленное число (ceil, floor), квадратный корень (sqrt), степень (pow), значения тригонометрических функций (sin, cos, tan, sinh, cosh, tanh, asin, acos, atan, atan2), экспоненту (exp), логарифм (log, logl0), дробную и целую части числа (modf), остаток от деления (fmod) и другие.

Примеры выражений:

(а + 0.12)/6

х && у || !z

(t * sin(x)-1.05e4)/((2 * k + 2) * (2 * k + 3))

Операции выполняются в соответствии с приоритетами. Для изменения порядка выполнения операций используются круглые скобки. Если в одном выражении записано несколько операций одинакового приоритета, унарные операции, условная операция и операции присваивания выполняются справа налево, остальные - слева направо. Например, а = b = с означает а = (b = c), a a + b + c означает (а + b) + с. Порядок вычисления подвыражений внутри выражений не определен: например, нельзя считать, что в выражении (sin(x + 2) + cos (у +1)) обращение к синусу будет выполнено раньше, чем к косинусу, и что х + 2 будет вычислено раньше, чем y + 1.

Результат вычисления выражения характеризуется значением и типом. Например, если а и b - переменные целого тина и описаны так:

int а = 2, b = 5;

то выражение а + b имеет значение 7 и тип int, а выражение а = b имеет значение, равное помещенному в переменную а (в данному случае 5) и тип, совпадающий с типом этой переменной. Таким образом, в С++ допустимы выражения вида а = b = с: сначала вычисляется выражение b = с, а затем его результат становится правым операндом для операции присваивания переменной а.

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

 

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

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

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

Контрольная работа по программированию заказать

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

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

 

 

Оператор «выражение»

Любое выражение, завершающееся точкой с запятой, рассматривается как оператор, выполнение которого заключается в вычислении выражения. Частным случаем выражения является пустой оператор ; (он используется, когда по синтаксису оператор требуется, а по смыслу - нет). Примеры:

i++; // выполняется операция инкремента

а* = b + с; // выполняется умножение с присваиванием

fun(i, k); // выполняется вызов функции

Контрольная работа по программированию заказать

 

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

Условный оператор if

Условный оператор if используется для разветвления процесса вычислений на два направления. Структурная схема оператора приведена на рисунке 6.3. Формат оператора:

if ( выражение ) оператор_1; [else оператор_2;]

Контрольная работа по программированию заказать

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

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

Примеры:

if (а<0) b = 1; // 1

if (a<b && (a>d || a==0)) b++; else {b *= a; a = 0;} // 2

if (a<b) {if (a<c) m = a; else m = c;} else {if (b<c) m = b; else m = c;} // 3

if (a++) b++; // 4

if (b>a) max = b; else max = a; // 5

В примере 1 отсутствует ветвь else. Подобная конструкция называется «пропуск оператора», поскольку присваивание либо выполняется, либо пропускается в зависимости от выполнения условия.

Если требуется проверить несколько условий, их объединяют знаками логических операций. Например, выражение в примере 2 будет истинно в том случае, если выполнится одновременно условие а<b и одно из условий в скобках. Если опустить внутренние скобки, будет выполнено сначала логическое И, а потом - ИЛИ.

Оператор в примере 3 вычисляет наименьшее значение из трех переменных. Фигурные скобки в данном случае не обязательны, так как компилятор относит часть else к ближайшему if.

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

Конструкции, подобные оператору в примере 5, проще и нагляднее записывать в виде условной операции (в данном случае: max = (b > а) ? b : а;).

Распространенная ошибка при записи условных операторов - использование в выражениях вместо проверки на равенство (==) простого присваивания (=), например, if(a=l) b=0;. Синтаксической ошибки нет, так как операция присваивания формирует результат, который и оценивается на равенство/неравенство нулю. В данном примере присваивание переменной b будет выполнено независимо от значения переменной а.

Вторая ошибка - неверная запись проверки на принадлежность диапазону. Например, чтобы проверить условие 0<х<1, нельзя записать его в условном операторе непосредственно, так как будет выполнено сначала сравнение 0<х, а его результат (true или false, преобразованное в int) будет сравниваться с 1. Правильный способ записи: if(0<x && х<1).

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

 

Оператор switch

Оператор switch (переключатель) предназначен для разветвления процесса вычислений на несколько направлений. Структурная схема оператора приведена на рисунке 6.4. Формат оператора:

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

case константное_выражение_1: [список_операторов_1]

case константное_выражение_2: [список_операторов_2]

case константное_выражение_n: [список_операторов_n]

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

}

Контрольная работа по программированию заказать

 

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

Выход из переключателя обычно выполняется с помощью операторов break или return. Оператор break выполняет выход из самого внутреннего из объемлющих его операторов switch, for, while и do. Оператор return выполняет выход из функции, в теле которой он записан.

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

Пример (программа реализует простейший калькулятор на 4 действия):

#include <iostream.h>

int main(){

int a, b, res;

char op;

cout « "\nВведите 1й операнд : ";

cin » a;

cout « "\nВведите знак операции : ";

cin » op;

cout « "\nВведите 2й операнд : ";

cin » b;

bool f = true;

switch (op){

case '+' : res = a+b; break;

case '-' : res = a-b; break;

case '*' : res = a*b; break;

case '/' : res = a/b; break;

default : cout «"\nНеизвестная операция"; f = false;

}

if (f) cout « "\nРезультат : "« res;

return 0;

}

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

 

Задачи для решения на тему «условные алгоритмы»

Вариант 1. Заданы три числа: а. b, с. Определить, могут ли они быть сторонами треугольника, и если да, то определить его тип: равносторонний, равнобедренный, равносторонний.

Замечание. Условия существования треугольника: a<=b + c, b<=a+c, c<=a+b.

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

Вариант 2. Треугольник задан длинами своих сторон: ша, b, c. Определить, является ли он тупоугольным, прямоугольным или остроугольным.

Замечание. Достаточно, используя теорему косинусов, найти знаки косинусов внутренних углов треугольника, не вычисляя самих углов (они могут быть нулевыми или развернутыми).

Вариант 3. Треугольник задан координатами своих вершин на плоскости: А(хa,уa), B(xb,yb), C(xc,yc). Определить, является он прямо-, остро- или тупоугольным.

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

Вариант 4. Написать программу, определяющую, могут ли введенные три числа являться сторонами треугольника.

Замечание. Числа а, b, с тогда и только тогда являются сторонами треугольника, когда существуют такие положительные х, у, z, что а = х+у, b = y+z, c = х+z.

Вариант 5. Четырехугольник ABCD задан координатами своих вершин на плоскости; А(хa,уa), В(хb,уb), C(xc,yc), D(xd,yd). Проверить, является ли он выпуклым.

Замечание. Есть несколько способов проверки выпуклости: анализ линейных неравенств, задаваемых сторонами; разбиение четырехугольника на треугольники со сравнением сумм их площадей и другие.

Вариант 6. Четырехугольник ABCD задан координатами своих вершин на плоскости; А(хa,уa), В(хb,уb), C(xc,yc), D(xd,yd). Определить тип четырехугольника: прямоугольник, параллелограмм, трапеция, произвольный четырехугольник.

Вариант 7. Определить, пройдет ли кирпич со сторонами а и b сквозь прямоугольное отверстие со сторонами r и s. Стороны отверстия должны быть параллельны граням кирпича.

Вариант 8. Может ли шар радиуса r пройти через ромбообразное отверстие с диагоналями р и q?

Вариант 9. Можно ли коробку размером A×B×C упаковать в посылку размером X×Y×Z. Углом укладывать нельзя.

Вариант 10. Можно ли из круглой заготовки радиуса r вырезать две прямоугольные пластинки с размерами A×B и C×D?

Вариант 11. Можно ли на прямоугольном участке застройки размером а на b метров разместить два дома размером в плане р на q и r на s метров? Дома можно располагать только параллельно сторонам участка.

Вариант 12. Проверить, лежит ли окружность (х-а)2 + (у-b)2 =r2 целиком внутри окружности (x-c)2 + (y-d)2 =s2 или наоборот.

Вариант 13. Лежит ли точка М(х,у) внутри треугольника, заданного координатами своих, вершин A(хa, уa), В(хb, уb), С(хс, yc) на плоскости?

Вариант 14. Два отрезка на плоскости заданы координатами своих концов. Определить, имеют ли эти: отрезки общие точки.

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

Вариант 15. Среди заданных целых чисел a,b,c найти пары кратных.

Вариант 16. Как известно, число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Проверить этот признак на примере заданного трехзначного числа.

Вариант 17. Заданы координаты вершин треугольника АВС на плоскости. Вывести их в порядке обхода по часовой стрелке (для проверки достаточно рассмотреть знаки внутренних углов).

Вариант 18. Путник двигался t1 часов со скоростью v1, затем t2 часов - со скоростью v2 и t3 часов - со скоростью v3. За какое время он одолел первую половину пути, после чего запланировал привал?

Вариант 19. Можно ехать на такси со скоростью v км/ч и оплатой р руб/км либо идти пешком со скоростью u км/ч бесплатно. Как с наименьшими затратами преодолеть путь за время t, если это возможно? Каковы эти затраты?

Замечание. Рекомендуется рассмотреть «запредельные» случаи: когда времени слишком мало, чтобы успеть даже на такси, либо слишком много, так что и пешком можно с запасом успеть до отхода поезда.

Вариант 20. Даны три числа a, b, c. Найти произведение наибольшего из этих чисел на наименьшее.

 

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

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

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

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

 

Контрольная работа по программированию заказать

 

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

Цикл завершается, если условие его продолжения не выполняется. Возможно принудительное завершение, как текущей итерации, так и цикла в целом. Для этого служат операторы break, continue, return и goto (смотри раздел 6.4 Операторы передачи управления). Передавать управление извне внутрь цикла не рекомендуется.

Для удобства, а не по необходимости, в С++ есть три разных оператора цикла - while, do while и for.

 

 

Цикл с предусловием (while)

Цикл с предусловием реализует структурную схему, приведенную на рисунке 6.6 а, и имеет вид:

while ( выражение ) оператор

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

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

while (int х = 0){ ... /* область действия х */ }

Пример (программа печатает таблицу значений функции у=х2+1 во введенном диапазоне):

#include <stdio.h>

int main(){

float Xn, Xk, Dx;

printf("Введите диапазон и шаг изменения аргумента: ");

scanf("%f%f%f", &Xn, &Xk, &Dx);

printf("| X | Y |\n"); // шапка таблицы

float X = Xn; // установка параметра цикла

while (X <= Xk){ // проверка условия продолжения

printf("| %5.2f | %5.2f |\n", X, X*X+1); // тело цикла

X += Dx; // модификация параметра

}

return 0;

}

 

 

Цикл с постусловием (do while)

Цикл с постусловием реализует структурную схему, приведенную на рисунке 6.5б, и имеет вид:

do оператор while выражение;

Сначала выполняется простой или составной оператор, составляющий тело цикла, а затем вычисляется выражение. Если оно истинно (не равно false), тело цикла выполняется еще раз. Цикл завершается, когда выражение станет равным false или в теле цикла будет выполнен какой-либо оператор передачи управления. Тип выражения должен быть арифметическим или приводимым к нему.

Пример (программа осуществляет проверку ввода):

#include <iostream.h>

int main(){

char answer;

do{

cout « "\nКупи слоника! ";

cin » answer; }

while (answer != 'y');

return 0;

}

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

,

где yn-1 - предыдущее приближение к корню (в начале вычислений выбирается произвольно); уn - последующее приближение. Процесс вычислений прекращается, когда приближения станут отличаться друг от друга по абсолютной величине менее чем на величину заданной точности.

#include <stdio.h>

#include <math.h>

int main(){

double X, Eps; // аргумент и точность

double Yp, Y = 1; // предыдущее и последующее приближение

printf("Введите аргумент и точность: ");

scanf("%f%f", &Х, &Eps);

do{

Yp = Y;

Y = (Yp + X/Yp)/2;}

while (fabs(Y - Yp) >= Eps);

printf("\nKopeнь из %f равен %f", X, Y);

return 0;

}

 

Цикл с параметром (for)

Цикл с параметром имеет следующий формат:

for (инициализация; выражение; модификации) оператор;

Инициализация используется для объявления и присвоения начальных значений величинам, используемым в цикле. В этой части можно записать несколько операторов, разделенных запятой (операцией «последовательное выполнение»), например, так:

for (int i = 0, j = 2; ...

int k, m;

for (k = 1, m = 0; ...

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

Выражение определяет условие выполнения цикла: если его результат, приведенный к типу bool, равен true, цикл выполняется. Цикл с параметром реализован как цикл с предусловием.

Модификации выполняются после каждой итерации цикла и служат обычно для изменения параметров цикла. В части модификаций можно записать несколько операторов через запятую. Простой или составной оператор представляет собой тело цикла. Любая из частей оператора for может быть опущена (но точки с запятой надо оставить на своих местах!).

Пример (оператор, вычисляющий сумму чисел от 1 до 100):

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

Пример (программа печатает таблицу значений функции у=х2+1 во введенном диапазоне):

#include <stdio.h>

int main(){

float Xn, Xk, Dx, X;

printf("Введите диапазон и шаг изменения аргумента: ");

scanf("%f%f%f", &Хn, &Xk, &Dx);

printf("| X | Y |\n");

for (X = Xn; Х<=Хk; X += Dx)

printf("| %5.2f | %5.2f |\n", X, X*X+1);

return 0;

}

Любой цикл while может быть приведен к эквивалентному ему циклу for и, наоборот, по следующей схеме:

for (b1;b2;b3) оператор

b1;

while (b2){

оператор;

b3;}

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

Чтобы избежать ошибок, рекомендуется:

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

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

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

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

Оператор for предпочтительнее в большинстве остальных случаев.

 

Задачи для решения на тему «сочетание цикла и разветвления»

 

Протабулировать кусочную функцию F на интервале Xstart до Xfinish с шагом dX, где a,b,c, Xstart, Xfinish, dX – действительные числа (вводятся с клавиатуры).

 

Операторы передачи управления

 

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

  • оператор безусловного перехода goto;
  • оператор выхода из цикла break;
  • оператор перехода к следующей итерации цикла continue;
  • оператор возврата из функции return.

 

 

Оператор goto

Оператор безусловного перехода goto имеет формат:

goto метка;

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

метка: оператор;

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

Использование оператора безусловного перехода оправдано в двух случаях:

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

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

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

int k; ...

goto metka; ...

{int а = 3, b = 4;

k = а + b;

metka: int m = k + 1; ...

}

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

 

 

Оператор break

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

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

#include <iostream.h>

#include <math.h>

int main(){

const int MaxIter = 500; // ограничитель количества итераций

double х, eps;

cout « "\nВведите аргумент и точность: ";

cin » х » eps;

bool flag = true; // признак успешного вычисления

double у = х, ch = х; // сумма и первый член ряда

for (int n = 0; fabs(ch) > eps; n++) {

ch *= x * x /(2 * n + 2)/(2 * n + 3); // очередной член ряда

у += ch;

if (n > MaxIter){

cout «"\nРяд расходится!";

flag = false; break;}

}

if (flag) cout « "\nЗначение функции: " « у;

return 0;

}

 

Оператор continue

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

 

Оператор return

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

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

Выражение должно иметь скалярный тип. Если тип возвращаемого функцией значения описан как void, выражение должно отсутствовать.

 

 

Задачи для решения на тему «вложенные циклы (вычисление суммы ряда)»

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

 

 

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

Указатели

Когда компилятор обрабатывает оператор определения переменной, например, int i=10;, он выделяет память в соответствии с типом (int) и инициализирует ее указанным значением (10). Все обращения в программе к переменной по ее имени (i) заменяются компилятором на адрес области памяти, в которой хранится значение переменной. Программист может определить собственные переменные для хранения адресов областей памяти. Такие переменные называются указателями.

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

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

тип (*имя) ( список_типов_аргументов );

Например, объявление:

int (*fun) (double, double);

задает указатель с именем fun на функцию, возвращающую значение типа int и имеющую два аргумента типа double.

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

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

int *а, b, *с;

описываются два указателя на целое с именами а и с, а также целая переменная b.

Размер указателя зависит от модели памяти. Можно определить указатель на указатель и т. д.

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

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

Указатель может быть константой или переменной, а также указывать на константу или переменную. Рассмотрим примеры:

int i; // целая переменная

const int ci = 1; // целая константа

int * pi; // указатель на целую переменную

const int * pci; // указатель на целую константу

int * const ср = &i; // указатель-константа на целую переменную

const int * const срс = &ci; // указатель-константа на целую константу

Как видно из примеров, модификатор const, находящийся между именем указателя и звездочкой, относится к самому указателю и запрещает его изменение, a const слева от звездочки задает постоянство значения, на которое он указывает. Для инициализации указателей использована операция получения адреса &.

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

 

Инициализация указателей

Указатели чаще всего используют при работе с динамической памятью, называемой некоторыми эстетами кучей (перевод с английского языка слова heap). Это свободная память, в которой можно во время выполнения программы выделять место в соответствии с потребностями. Доступ к выделенным участкам динамической памяти, называемым динамическими переменными, производится только через указатели. Время жизни динамических переменных - от точки создания до конца программы или до явного освобождения памяти. В С++ используется два способа работы с динамической памятью. Первый использует семейство функций malloc и достался в наследство от С, второй использует операции new и delete.

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

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

  1. Присваивание указателю адреса существующего объекта:
    • с помощью операции получения адреса:

int а = 5; // целая переменная

int * р = &а; //в указатель записывается адрес а

int * р (&а); //то же самое другим способом

    • с помощью значения другого инициализированного указателя: int * r = р;
    • с помощью имени массива или функции, которые трактуются как адрес:

int b[10]; // массив

int * t = b; // присваивание адреса начала массива

void f(int а ){ /* ... */ } // определение функции

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

pf = f; // присваивание адреса функции

  1. Присваивание указателю адреса области памяти в явном виде:

char* vp = (char *)0хВ8000000;

Здесь 0хВ8000000 - шестнадцатеричная константа, (char *) - операция приведения типа: константа преобразуется к типу «указатель на char».

  1. Присваивание пустого значения:

int* rulez = 0;

  1. Выделение участка динамической памяти и присваивание ее адреса указателю:
    • с помощью операции new:

int * n = new int; // 1

int * m = new int (10); // 2

int * q = new int [10]; // 3

    • с помощью функции mallос (для того чтобы использовать malloc, требуется подключить к программе заголовочный файл <malloc.h>):

int * u = (int *)malloc(sizeof(int)); // 4

В операторе 1 операция new выполняет выделение достаточного для размещения величины типа int участка динамической памяти и записывает адрес начала этого участка в переменную n. Память под саму переменную n (размера, достаточного для размещения указателя) выделяется на этапе компиляции.

В операторе 2, кроме описанных выше действий, производится инициализация выделенной динамической памяти значением 10.

В операторе 3 операция new выполняет выделение памяти под 10 величин типа int (массива из 10 элементов) и записывает адрес начала этого участка в переменную q, которая может трактоваться как имя массива. Через имя можно обращаться к любому элементу массива.

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

В операторе 4 делается то же самое, что и в операторе 1, но с помощью функции выделения памяти malloc, унаследованной из библиотеки С. В функцию передается один параметр - количество выделяемой памяти в байтах. Конструкция (int*) используется для приведения типа указателя, возвращаемого функцией, к требуемому типу. Если память выделить не удалось, функция возвращает 0.

Операцию new использовать предпочтительнее, чем функцию malloc, особенно при работе с объектами.

Освобождение памяти, выделенной с помощью операции new, должно выполняться с помощью delete, а памяти, выделенной функцией malloc, – посредством функции free. При этом переменная-указатель сохраняется и может инициализироваться повторно. Приведенные выше динамические переменные уничтожаются следующим образом:

delete n; delete m; delete [] q; free (u);

Если память выделялась с помощью new[], для освобождения памяти необходимо применять delete[]. Размерность массива при этом не указывается. Если квадратных скобок нет, то никакого сообщения об ошибке не выдается, но помечен как свободный будет только первый элемент массива, а остальные окажутся недоступны для дальнейших операций. Такие ячейки памяти называются мусором.

С помощью комбинаций звездочек, круглых и квадратных скобок можно описывать составные типы и указатели на составные типы, например, в операторе int *(*р[10])(); объявляется массив из 10 указателей на функции без параметров, возвращающих указатели на int.

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

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

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

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

int *(*р[10])():

5 4 2 1 3 // порядок интерпретации описания

 

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

С указателями можно выполнять следующие операции: разадресация, или косвенное обращение к объекту (*), присваивание, сложение с константой, вычитание, инкремент (++), декремент (--), сравнение, приведение типов. При работе с указателями часто используется операция получения адреса (&).

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

char а; // переменная типа char

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

*р = 'Ю'; а = *р; // присваивание значения обеим переменным

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

Инкремент перемещает указатель к следующему элементу массива, декремент - к предыдущему. Фактически значение указателя изменяется на величину sizeof (тип). Если указатель на определенный тип увеличивается или уменьшается на константу, его значение изменяется на величину этой константы, умноженную на размер объекта данного типа, например:

short * р = new short [5];

р++; // значение р увеличивается на 2

long * q = new long [5];

q++: // значение q увеличивается на 4

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

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

*р++ = 10;

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

*р = 10; р++;

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

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

 

Ссылки

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

тип & имя;

где тип - это тип величины, на которую указывает ссылка;

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

int kol;

int & pal = kol; // ссылка pal - альтернативное имя для kol

const char & CR = '\n'; // ссылка на константу

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

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

 

Массивы

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

float а [10]; // описание массива из 10 вещественных чисел

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

int b[5] = {3, 2, 1}; // b[0]=3, b[1]=2, b[2]=1, b[3]=0, b[4]=0

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

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

#include <iostream.h>

int main(){

const int n = 10;

int i, sum;

int marks[n] = {3, 4, 5, 4, 4};

for (i = 0, sum = 0; i<n; i++) sum += marks[i];

cout « "Сумма элементов: " « sum;

return 0;

}

Пример. Сортировка целочисленного массива методом выбора. Алгоритм состоит в том, что выбирается наименьший элемент массива и меняется местами с первым элементом, затем рассматриваются элементы, начиная со второго, и наименьший из них меняется местами со вторым элементом, и так далее n-1 раз (при последнем проходе цикла при необходимости меняются местами предпоследний и последний элементы массива).

#include <iostream.h>

int main(){

const int n = 20; // количество элементов массива

int b[n]; // описание массива

int i;

for (i = 0; i<n; i++) cin » b[i]; // ввод массива

for (i =0; i<n-1; i++){ // n-1 раз ищем наименьший элемент

// принимаем за наименьший первый из рассматриваемых элементов:

int imin = i;

// поиск номера минимального элемента из неупорядоченных:

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

// если нашли меньший элемент, запоминаем его номер:

if (b[j] < b[imin]) imin = j;

int a = b[i]; // обмен элементов

b[i] = b[imin]; // с номерами

b[imin] = a; // i и imin

}

// вывод упорядоченного массива:

for (i = 0; i<n; i++) cout « b[i] « ' ';

return 0;

}

Идентификатор массива является константным указателем на его нулевой элемент. Например, для массива из предыдущего листинга имя b - это то же самое, что &b[0], а к i-му элементу массива можно обратиться, используя выражение *(b+i). Можно описать указатель, присвоить ему адрес начала массива и работать с массивом через указатель. Следующий фрагмент программы копирует все элементы массива a в массив b:

int а[100], b[100];

int *ра = а; // или int *р = &а[0]:

int *pb = b;

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

*pb++ = *pa++; // или pb[i] = pa[i];

Динамические массивы создают с помощью операции new, при этом необходимо указать тип и размерность, например:

int n = 100;

float *р = new float [n];

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

Преимущество динамических массивов состоит в том, что размерность может быть переменной, то есть объем памяти, выделяемой под массив, определяется на этапе выполнения программы. Доступ к элементам динамического массива осуществляется точно так же, как к статическим, например, к элементу номер 5 приведенного выше массива можно обратиться как р[5] или *(р+5).

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

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

int matr [6][8];

задает описание двумерного массива из 6 строк и 8 столбцов. В памяти такой массив располагается в последовательных ячейках построчно. Многомерные массивы размещаются так, что при переходе к следующему элементу быстрее всего изменяется последний индекс. Для доступа к элементу многомерного массива указываются все его индексы, например, matr[i][j], или более экзотическим способом: *(matr[i]+j) или *(*(matr+i)+j). Это возможно, поскольку matr[i] является адресом начала i-й строки массива.

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

int mass2 [][2] - { {1, 1}, {0, 2}, {1, 0} };

int mass2 [3][2] = {1, 1, 0, 2, 1, 0};

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

#include <stdio.h>

int main(){

const int nstr = 4, nstb = 5; // размерности массива

int b[nstr][nstb]; // описание массива

int i, j;

for (i = 0; i<nstr; i++) // ввод массива

for (j = 0; j<nstb; j++) scanf("%d", &b[i][j]);

int istr = -1, MaxKol = 0;

for (i = 0; i<nstr; i++){ // просмотр массива по строкам

int Kol = 0:

for (j = 0; j<nstb; j++) if (b[i][j] = 0)Kol++;

if (Kol > MaxKol){istr = i; MaxKol = Kol;}

}

printf("Исходный массив:\n");

for (i = 0; i<nstr; i++){

for (j = 0; j<nstb; j++)

printf("%d", b[i][j]);

printf("\n");}

if (istr == -1) printf("Нулевых элементов нет");

else printf("Номер строки: %d", istr);

return 0;

}

Номер искомой строки хранится в переменной istr, количество нулевых элементов в текущей (i-й) строке - в переменной Kol, максимальное количество нулевых элементов - в переменной MaxKol. Массив просматривается по строкам, в каждой из них подсчитывается количество нулевых элементов (обратите внимание, что переменная Kol обнуляется перед просмотром каждой строки). Наибольшее количество и номер соответствующей строки запоминаются.

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

int nstr = 5;

int ** m = (int **) new int [nstr][10];

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

int nstr, nstb;

cout « " Введите количество строк и столбцов :";

cin » nstr » nstb;

int **a = new int *[nstr]; // 1

for(int i = 0; i<nstr; i++) // 2

a[i] = new int [nstb]; // 3

В операторе 1 объявляется переменная типа «указатель на указатель на int» и выделяется память под массив указателей на строки массива (количество строк - nstr). В операторе 2 организуется цикл для выделения памяти под каждую строку массива. В операторе 3 каждому элементу массива указателей на строки присваивается адрес начала участка памяти, выделенного под строку двумерного массива. Каждая строка состоит из nstb элементов типа int (рисунок 7.1).

Освобождение памяти из-под массива с любым количеством измерений выполняется с помощью операции delete []. Указатель на константу удалить нельзя.

Контрольная работа по программированию заказать

 

Для правильной интерпретации объявлений полезно запомнить мнемоническое правило: «суффикс привязан крепче префикса». Если при описании переменной используются одновременно префикс * (указатель) и суффикс [] (массив), то переменная интерпретируется как массив указателей, а не указатель на массив: int * р[10]; - массив из 10 указателей на int.

 

Задачи для решения на тему «одномерные массивы»

 

Дан массив, состоящий из n вещественных элементов, вычислить:

Вариант 1

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

Вариант 2

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

Вариант 3

  1. произведение элементов массива с четными номерами;
  2. сумму элементов массива, расположенных между первым и последним нулевыми элементами;
  3. преобразовать массив таким образом, чтобы сначала располагались все положительные элементы, а потом - все отрицательные (элементы, равные 0, считать положительными).

Вариант 4

  1. сумму элементов массива с нечетными номерами;
  2. сумму элементов массива, расположенных между первым и последним отрицательными элементами;
  3. сжать массив, удалив из него все элементы, модуль которых не превышает 1. Освободившиеся в конце массива элементы заполнить нулями.

Вариант 5

  1. максимальный элемент массива;
  2. сумму элементов массива, расположенных до последнего положительного элемента;
  3. сжать массив, удалив из него все элементы, модуль которых находится в интервале [а, b]. Освободившиеся в конце массива элементы заполнить нулями.

Вариант 6

  1. минимальный элемент массива;
  2. сумму элементов массива, расположенных между первым и последним положительными элементами;
  3. преобразовать массив таким образом, чтобы сначала располагались все элементы, равные нулю, а потом - все остальные.

Вариант 7

  1. номер максимального элемента массива;
  2. произведение элементов массива, расположенных между первым и вторым нулевыми элементами;
  3. преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоявшие в нечетных позициях, а во второй половине - элементы, стоявшие в четных позициях.

Вариант 8

  1. номер минимального элемента массива;
  2. сумму элементов массива, расположенных между первым и вторым отрицательными элементами;
  3. преобразовать массив таким образом, чтобы сначала располагались все элементы, модуль которых не превышает 1, а потом - все остальные.

Вариант 9

  1. максимальный по модулю элемент массива;
  2. сумму элементов массива, расположенных между первым и вторым положительными элементами;
  3. преобразовать массив таким образом, чтобы элементы, равные нулю, располагались после всех остальных.

Вариант 10

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

Вариант 11

  1. номер минимального по модулю элемента массива;
  2. сумму модулей элементов массива, расположенных после первого отрицательного элемента;
  3. сжать массив, удалив из него все элементы, величина которых находится в интервале [а, b]. Освободившиеся в конце массива элементы заполнить нулями.

Вариант 12

  1. номер максимального по модулю элемента массива;
  2. сумму элементов массива, расположенных после первого положительного элемента;
  3. преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых лежит в интервале [а, b], а потом - все остальные.

Вариант 13

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

Вариант 14

  1. количество элементов массива, равных 0;
  2. сумму элементов массива, расположенных после минимального элемента;
  3. упорядочить элементы массива по возрастанию модулей элементов.

Вариант 15

  1. количество элементов массива, больших С;
  2. произведение элементов массива, расположенных после максимального по модулю элемента;
  3. преобразовать массив таким образом, чтобы сначала располагались все отрицательные элементы, а потом - все положительные.

Вариант 16

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

Вариант 17

  1. количество положительных элементов массива;
  2. сумму элементов массива, расположенных после последнего элемента, равного нулю;
  3. преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых не превышает 1, а потом - все остальные.

Вариант 18

  1. количество элементов массива, меньших С;
  2. сумму целых частей элементов массива, расположенных после последнего отрицательного элемента;
  3. преобразовать массив таким образом, чтобы сначала располагались все элементы, отличающиеся от максимального не более чем на 20%, а потом - все остальные.

Вариант 19

  1. произведение отрицательных элементов массива;
  2. сумму положительных элементов массива, расположенных до максимального элемента;
  3. изменить порядок следования элементов в массиве на обратный.

Вариант 20

  1. произведение положительных элементов массива;
  2. сумму элементов массива, расположенных до минимального элемента;
  3. упорядочить по возрастанию отдельно элементы, стоящие на четных местах, и элементы, стоящие на нечетных местах.

 

 

Задачи для решения на тему «двумерные массивы»

Вариант 1. Дана целочисленная прямоугольная матрица. Определить:

  1. количество столбцов, не содержащих ни одного положительного элемента;
  2. сумму столбцов, содержащих хотя бы один нулевой элемент.

Вариант 2. Дана целочисленная прямоугольная матрица.

Определить количество столбцов, не содержащих ни одного нулевого элемента.

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

Вариант 3. Дана целочисленная прямоугольная матрица. Определить:

  1. количество столбцов, содержащих хотя бы один нулевой элемент;
  2. номер строки, в которой находится самая длинная серия одинаковых элементов.

Вариант 4. Дана целочисленная квадратная матрица. Определить:

  1. произведение элементов в тех строках, которые не содержат отрицательных элементов;
  2. максимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.

Вариант 5. Дана целочисленная квадратная матрица. Определить:

  1. сумму элементов в тех столбцах, которые не содержат отрицательных элементов;
  2. минимум среди сумм модулей элементов диагоналей, параллельных побочной диагонали матрицы.

Вариант 6. Дана целочисленная прямоугольная матрица. Определить:

  1. сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент;
  2. номера строк и столбцов всех седловых точек матрицы.

Примечание. Матрица А имеет седловую точку Аs, если Аij является минимальным элементом в i-й строке и максимальным в j-м столбце.

Вариант 7. Дана целочисленная прямоугольная матрица размером 8 на 8

  1. найти такие k, что k-я строка матрицы совпадает с k-м столбцом;
  2. найти сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент.

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

Найти сумму элементов в тех столбцах, которые содержат хотя бы один отрицательный элемент.

Вариант 9. Соседями элемента Аij в матрице назовем элементы Аkl с
i-1<=k<=i+1, j-1<=l<=j+1 при (k,l) не равно (i,j). Операция сглаживания матрицы дает новую матрицу того же размера, каждый элемент которой получается как среднее арифметическое имеющихся соседей соответствующего элемента исходной матрицы. Построить результат сглаживания заданной вещественной матрицы размером 10 на 10. В сглаженной матрице найти сумму модулей элементов, расположенных ниже главной диагонали.

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

Найти сумму модулей элементов, расположенных выше главной диагонали.

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

Найти количество строк, среднее арифметическое элементов которых меньше заданной величины.

Вариант 12. Уплотнить заданную матрицу, удаляя из нее строки и столбцы, заполненные нулями.

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

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

Вариант 14. Осуществить циклический сдвиг элементов квадратной матрицы размерности М × N вправо на k элементов таким образом: элементы 1-й строки сдвигаются в последний столбец сверху вниз, из него = в последнюю строку справа налево, из нее - в первый столбец снизу вверх, из него - в первую строку; для остальных элементов - аналогично.

Вариант 15. Дана целочисленная прямоугольная матрица.

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

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

Вариант 16. Дана целочисленная прямоугольная матрица.

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

Найти номер первого из столбцов, не содержащих ни одного отрицательного элемента.

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

Найти номер первой из строк, не содержащих ни одного положительного элемента.

Вариант 18. Дана целочисленная прямоугольная матрица. Определить:

  1. количество строк, содержащих хотя бы один нулевой элемент;
  2. номер столбца, в котором находится самая длинная серия одинаковых элементов.

Вариант 19. Дана целочисленная квадратная матрица. Определить:

  1. сумму элементов в тех строках, которые не содержат отрицательных элементов;
  2. минимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.

Вариант 20. Дана целочисленная прямоугольная матрица. Определить:

  1. количество отрицательных элементов в тех строках, которые содержат хотя бы один нулевой элемент;
  2. номера строк и столбцов всех седловых точек матрицы.

Примечание. Матрица А имеет седловую точку Аs, если Аij является минимальным элементом в i-й строке и максимальным в j-м столбце.

 

Строки

Строка представляет собой массив символов, заканчивающийся нуль-символом. Нуль-символ - это символ с кодом, равным 0, что записывается в виде управляющей последовательности '\0'. По положению нуль-символа определяется фактическая длина строки. Строку можно инициализировать строковым литералом:

char str[10] = "Vasia";

// выделено 10 элементов с номерами от 0 до 9

// первые элементы - 'V', 'a', 's', 'i', 'а', '\0'

В этом примере под строку выделяется 10 байт, 5 из которых занято под символы строки, а шестой - под нуль-символ. Если строка при определении инициализируется, ее размерность можно опускать (компилятор сам выделит соответствующее количество байт):

char str[] = "Vasia"; // выделено и заполнено 6 байт

Оператор

char *str = "Vasia"

создает не строковую переменную, а указатель на строковую константу, изменить которую невозможно (к примеру, оператор str[1]='o' не допускается). Знак равенства перед строковым литералом означает инициализацию, а не присваивание. Операция присваивания одной строки другой не определена (поскольку строка является массивом) и может выполняться с помощью цикла или функций стандартной библиотеки.

Пример. Программа запрашивает пароль не более трех раз.

#include <stdio.h>

#include <string.h>

int main(){

char s[80], passw[] = "kuku"; // passw - эталонный пароль.

// Можно описать как *passw = "kuku";

int i, k = 0;

for (i = 0; !k && i<3; i++){

printf("\nвведите пароль:\n");

gets(s); // функция ввода строки

if (strstr(s,passw)) k = 1; // функция сравнения строк

}

if (k) printf("\nпароль принят");

else printf("\nпароль не принят");

return 0;

}

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

При работе со строками удобно пользоваться функциями стандартной библиотеки C или определенным в С++ классом string, который обеспечивает индексацию, присваивание, сравнение, добавление, объединение строк и поиск подстрок, а также преобразование из С-строк, то есть массивов типа char, в string, и наоборот.

 

Функции стандартной библиотеки

Полный список функций заголовочного файла <string.h> приведен в таблице 8.

Более подробно о каждой функции, а также список аргументов можно посмотреть в справке.

В заголовочных файлах <stdlib.h> и <cstdlib> содержатся полезные функции преобразования строк в числа (обратные преобразования можно сделать с помощью функции sprintf):

double atof(const char* p) - преобразует переданную строку в double;

int atoi (const char* p) - преобразует переданную строку в int;

long atol (const char* p) - преобразует переданную строку в long.

Пробелы и табуляции в начале строки пропускаются. Преобразование прекращается при встрече недопустимого символа или конца строки. Если строку нельзя преобразовать в число, возвращается 0. Если число выходит за пределы диапазона данного типа, переменной errno (заголовочный файл <cerrno>) присваивается значение ERANGE и возвращается допустимое число.

Пример (программа заполняет массив типа double из строки):

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

int main(){

char s[] = "2, 38.5, 70, 0, 0, 1", *p = s;

double m[10];

int i = 0;

do{

m[i++] = atof(p);

if (i>9) break;

}while(p = strchr(p, ','), p++);

for( int k = 0; k<i; k++) printf("%5.2f ", m[k]);

return 0;

}

 

Таблица 8 - Заголовочный файл <string.h> (<cstring>) - функции работы со строками в стиле С

Имя функции

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

memchr

Ищет первое вхождение символа в блок памяти

memcmp

Сравнивает блоки памяти

memcpy

Копирует блок памяти

memmove

Переносит блок памяти

memset

Заполняет блок памяти символом

strcat

Складывает строки

strchr

Ищет символ в строке

strcmp

Сравнивает строки

strcoll

Сравнивает строки с учетом установленной локализации

strcpy

Копирует одну строку в другую

strcspn

Ищет один из символов одной строки в другой

strerror

Возвращает указатель на строку с описанием ошибки

strlen

Возвращает длину строки

strncat

Складывает одну строку с n символами другой

strncmp

Сравнивает одну строку с n символами другой

strncpy

Копирует первые n символов одной строки в другую

strpbrk

Ищет один из символов одной строки в другой

strrchr

Ищет символ в строке

strspn

Ищет символ одной строки, отсутствующий в другой

strstr

Ищет подстроку в строке

strtok

Выделяет из строки лексемы

strxfrm

Преобразует строки на основе текущей локализации

wcscat

Складывает строки

wcschr

Ищет символ в строке

wcscmp

Сравнивает строки

wcscol1

Сравнивает строки с учетом установленной локализации

wcscpy

Копирует одну строку в другую

wcscspn

Ищет один из символов одной строки в другой

wcslen

Возвращает длину строки

wcsncat

Складывает одну строку с n символами другой

wcsncmp

Сравнивает одну строку с n символами другой

wcsricpy

Копирует первые n символов одной строки в другую

wcspbrk

Ищет один из символов одной строки в другой

wcsrchr

Ищет символ в строке

wcsspn

Ищет символ одной строки, отсутствующий в другой

wcsstr

Ищет подстроку в строке

wcstok

Выделяет из строки лексемы

wcstrxfrm

Преобразует строки на основе текущей локализации

wmemcpy

Копирует блок памяти

wmemmove

Переносит блок памяти

wmemset

Заполняет блок памяти символом

 

В стандартной библиотеке имеются также функции и работы с символами (заголовочные файлы <ctype.h> и <cctype>), приведенные в таблице 9.

 

Таблица 9 – Функции работы со строками заголовочных файлов <ctype.h> и <cctype>

Имя функции

Проверка на принадлежность символа множеству:

isalnum

букв и цифр (A-Z, a-z, 0-9)

isalfa

букв (A-Z, a-z)

iscntrl

управляющих символов (с кодами 0..31 и 127)

isdigit

цифр (0-9)

isgraph

печатаемых символов, кроме пробела (isalfa | isdigit | ispunct)

islower

букв нижнего регистра (a-z)

isprint

печатаемых символов

ispunct

знаков пунктуации

isspace

символов-разделителей

isupper

букв верхнего регистра (A-Z)

isxdigit

шестнадцатеричных цифр (A-F, a-f, 0-9)

 

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

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

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

 

 

Задачи для решения на тему «строки»

Вариант 1. Проверить, правильно ли в текст входят круглые скобки.

Вариант 2. Удалить из текста все буквы b.

Вариант 3. Удалить из текста все буквы k, идущие за буквой n.

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

Вариант 5. Подсчитать количество слов в тексте, начинающихся и заканчивающихся с одной и той же буквы.

Вариант 6. Подсчитать число слов в тексте, содержащих букву b.

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

Вариант 8. Удалить из слова повторяющиеся буквы.

Вариант 9. Если в заданный текст входит каждая их букв слова key, напечатать yes, иначе no.

Вариант 10. Напечатать буквы, которые идут в тексте непосредственно за буквой а.

Вариант 11. Удалить из текста все пары букв оо.

Вариант 12. Подсчитать число слов в тексте, оканчивающихся буквой w.

Вариант 13. Проверить, является ли данное слово перевертышем.

Вариант 14. Подсчитать количество слов в тексте, содержащих ровно три буквы е.

Вариант 15. Удалить из слов в тексте все гласные буквы.

Вариант 16. Если слово нечетной длины, удалить из него среднюю букву.

Вариант 17. Заменить в тексте строчные буквы прописными, а прописные строчными.

Вариант 18. Найти в тексте самое большое число.

Вариант 19. Подсчитать частоты вхождения букв в текст.

Вариант 20. Вывести на экран самое длинное слово в тексте.

 

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

Переименование типов (typedef)

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

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

В данном случае квадратные скобки являются элементом синтаксиса. Размерность может отсутствовать. Примеры:

typedef unsigned int UINT;

typedef char Msg[100];

typedef struct{

char fio[30];

int date, code;

double salary;} Worker;

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

UINT i, j; // две переменных типа unsigned int

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

Worker staff[100]; // массив из 100 структур

 

Перечисления (enum)

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

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

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

enum Err {ERR_READ, ERR_WRITE, ERR_CONVERT};

Err error;

...

switch (error){

case ERR_READ: /* операторы */ break;

case ERR_WRITE: /* операторы */ break;

case ERR_CONVERT: /* операторы */ break;

}

Константам ERR_READ, ERRJJRITE, ERR_CONVERT присваиваются значения 0, 1 и 2 соответственно.

Другой пример:

enum {two = 2, three, four, ten = 10, eleven, fifty = ten + 40};

Константам three и four присваиваются значения 3 и 4, константе eleven - 11.

 

 

Структуры (struct)

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

struct [ имя_типа ] {

тип_1 элемент_1;

тип_2 элемент_2;

тип_n элемент_n;

} [ список_описателей ];

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

// Определение массива структур и указателя на структуру:

struct {

char fio[30];

int date, code;

double salary;

} staff[100], *ps;

Если список отсутствует, описание структуры определяет новый тип, имя которого можно использовать в дальнейшем наряду со стандартными типами, например:

struct Worker{ // описание нового типа Worker

char fio[30];

int date, code;

double salary;

}; // описание заканчивается точкой с запятой

// определение массива типа Worker и указателя на тип Worker:

Worker staff[100], *ps;

Имя структуры можно использовать сразу после его объявления (определение можно дать позднее) в тех случаях, когда компилятору не требуется знать размер структуры, например:

struct List; // объявление структуры List

struct Link{

List *p; // указатель на структуру List

Link *prev, *succ; // указатели на структуру Link

}:

struct List { /* определение структуры List */};

Это позволяет создавать связные списки структур.

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

struct{

char fio[30];

int date, code;

double salary;

} worker = {"Страусенко", 31, 215, 3400.55};

При инициализации массивов структур следует заключать в фигурные скобки каждый элемент массива (учитывая, что многомерный массив - это массив массивов):

struct complex{

float real, im;

} compl [2][3] = {

{{1, 1}, {1, 1}, {1, 1}}, // строка 1, то есть массив compl[0]

{{2, 2}, {2, 2}, {2, 2}} // строка 2, то есть массив compl[1]

};

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

Доступ к полям структуры выполняется с помощью операций выбора . (точка) при обращении к полю через имя структуры и -> при обращении через указатель, например:

Worker worker, staff[100], *ps;

worker.fio = "Страусенко";

staff[8].code = 215;

ps->salary = 0.12;

Если элементом структуры является другая структура, то доступ к ее элементам выполняется через две операции выбора:

struct A {int a; double х;};

struct В {A a; double х;} х[2];

х[0].а.а = 1;

х[1].х = 0.1;

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

 

Битовые поля

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

struct Options{

bool centerX:1;

bool centerY:1;

unsigned int shadow:2;

unsigned int palette:4;

};

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

 

Задачи для решения на тему «структуры»

Вариант 1. Описать структуру, содержащую следующие поля:

  • фамилия и инициалы;
  • номер группы;
  • успеваемость (3 предмета).

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на дисплей фамилий и номеров групп для всех студентов, если средний балл студента больше 4.

Вариант 2. Описать структуру, содержащую следующие поля:

  • фамилия и инициалы;
  • номер группы;
  • успеваемость (3 предмета).

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на дисплей фамилий и номеров групп для всех студентов, имеющих оценки 4 и 5.

Вариант 3. Описать структуру, содержащую следующие поля:

  • фамилия и инициалы;
  • номер группы;
  • успеваемость (3 предмета).

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур.
  • вывод на дисплей фамилий и номеров групп для всех студентов, имеющих хотя бы одну оценку 2.

Вариант 4. Описать структуру, содержащую следующие поля:

  • название пункта назначения рейса;
  • номер рейса;
  • тип самолета.

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

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

Вариант 5. Описать структуру, содержащую следующие поля:

  • название пункта назначения рейса;
  • номер рейса;
  • тип самолета.

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

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

Вариант 6. Описать структуру, содержащую следующие поля:

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

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

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

Вариант 7. Описать структуру, содержащую следующие поля:

  • название пункта назначения;
  • номер поезда;
  • время отправления.

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

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

Вариант 8. Описать структуру, содержащую следующие поля:

  • название пункта назначения;
  • номер поезда;
  • время отправления.

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

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

Вариант 9. Описать структуру, содержащую следующие поля:

  • название пункта назначения;
  • номер поезда;
  • время отправления.

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на экран информации о поезде, номер которого введен с клавиатуры.

Вариант 10. Описать структуру, содержащую следующие поля:

  • название начального пункта маршрута;
  • название конечного пункта маршрута;
  • номер маршрута.

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на экран информации о маршруте, номер которого введен с клавиатуры.

Вариант 11. Описать структуру, содержащую следующие поля:

  • название начального пункта маршрута;
  • название конечного пункта маршрута;
  • номер маршрута.

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

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

Вариант 12. Описать структуру, содержащую следующие поля:

  • фамилия, имя;
  • номер телефона;
  • дата рождения (число, месяц, год).

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на экран информации о человеке, номер телефона которого введен с клавиатуры.

Вариант 13. Описать структуру, содержащую следующие поля:

  • фамилия, имя;
  • номер телефона;
  • дата рождения (число, месяц, год).

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

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

Вариант 14. Описать структуру, содержащую следующие поля:

  • фамилия, имя;
  • номер телефона;
  • дата рождения (число, месяц, год).

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на экран информации о человеке, чья фамилия введена с клавиатуры.

Вариант 15. Описать структуру, содержащую следующие поля:

  • фамилия, имя;
  • знак Зодиака;
  • дата рождения (число, месяц, год).

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структу;
  • вывод на экран информации о человеке, чья фамилия введена с клавиатуры.

Вариант 16. Описать структуру, содержащую следующие поля:

  • фамилия, имя;
  • знак Зодиака;
  • дата рождения (число, месяц, год).

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на экран информации о людях, родившихся под знаком, название которого введено с клавиатуры.

Вариант 17. Описать структуру, содержащую следующие поля:

  • фамилия, имя;
  • знак Зодиака;
  • дата рождения (число, месяц, год).

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на экран информации о людях, родившихся в месяц, значение которого введено с клавиатуры.

Вариант 18. Описать структуру, содержащую следующие поля:

  • название товара;
  • название магазина, в котором продается товар;
  • стоимость товара в рублях.

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на экран информации о товаре, название которого введено с клавиатуры.

Вариант 19. Описать структуру, содержащую следующие поля:

  • название товара;
  • название магазина, в котором продается товар;
  • стоимость товара в рублях.

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

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

Вариант 20. Описать структуру, содержащую следующие поля:

  • название товара;
  • название магазина, в котором продается товар;
  • стоимость товара в рублях.

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

  • ввод с клавиатуры данных в массив, состоящий из 5 структур;
  • вывод на экран информации о товаре с минимальной ценой.

 

Функции

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

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

Любая программа на С++ состоит из функций, одна из которых должна иметь имя main (с нее начинается выполнение программы). Функция начинает выполняться в момент вызова. Любая функция должна быть объявлена и определена. Как и для других величин, объявлений может быть несколько, а определение только одно. Объявление функции должно находиться в тексте раньше ее вызова для того, чтобы компилятор мог осуществить проверку правильности вызова.

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

[ класс ] тип имя ([ список_параметров ]) [throw ( исключения )]

{ тело функции }

Рассмотрим составные части определения:

  • с помощью необязательного модификатора класс можно явно задать область видимости функции, используя ключевые слова extern и static:
    1. extern - глобальная видимость во всех модулях программы (по умолчанию);
    2. static - видимость только в пределах модуля, в котором определена функция;
  • тип возвращаемого функцией значения может быть любым, кроме массива и функции (но может быть указателем на массив или функцию). Если функция не должна возвращать значение, указывается тип void;
  • список параметров определяет величины, которые требуется передать в функцию при ее вызове. Элементы списка параметров разделяются запятыми. Для каждого параметра, передаваемого в функцию, указывается его тип и имя (в объявлении имена можно опускать).

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

Тип возвращаемого значения и типы параметров совместно определяют тип функции.

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

Пример функции, возвращающей сумму двух целых величин:

#include <iostream.h>

int sum(int a, int b); // объявление функции

int main(){

int a = 2, b = 3, c, d;

с = sum(a, b); // вызов функции

cin » d;

cout « sum(c, d); // вызов функции

return 0;

}

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

return (а + b);

}

Пример функции, выводящей на экран поля переданной ей структуры:

#include <iostream.h>

struct Worker{

char fio[30];

int date, code;

double salary;

};

void print_worker(Worker); //объявление функции

int main(){

Worker staff[100];

... /* формирование массива staff */

for (int i = 0; i<100; i++) print_worker(staff[i]); // вызов функции

return 0;

}

void print_worker(Worker w){ //определение функции

cout « w.fio « ' ' « w.date « ' ' « w.code « ' ' « w.salary « endl;

}

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

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

#include <iostream.h>

void f(int a){

int m = 0;

cout « "n m p\n";

while (a--){

static int n = 0;

int p = 0;

cout « n++ « ' ' « m++ « ' ' « p++ « '\n';

}

}

int main(){ f(3); f(2); return 0;}

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

 

Программа выведет на экран:

n m р

0 0 0

1 1 0

2 2 0

n m р

3 0 0

4 1 0

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

 

 

Глобальные переменные

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

 

Возвращаемое значение

Механизм возврата из функции в вызвавшую ее функцию реализуется оператором

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

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

Примеры:

int fl(){return 1;} //правильно

void f2(){return 1;} // неправильно, f2 не должна возвращать значение

double f3(){return 1;} // правильно, 1 преобразуется к типу double

 

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

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

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

Существует два способа передачи параметров в функцию: по значению и по адресу.

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

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

#include <iostream.h>

void f(int i, int * j, int & k);

int main(){

int i = 1, j = 2, k = 3;

cout «"i j k\n";

cout « i «' '« j «' '« k «'\n';

f(i, &j, k);

cout « i «' '« j «' '« k;

return 0;

}

void f(int i, int* j, int& k){

i++; (*j)++; k++;

}

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

i j k

1 2 3

1 3 4

Первый параметр (i) передается по значению. Его изменение в функции не влияет на исходное значение. Второй параметр (j) передается по адресу с помощью указателя, при этом для передачи в функцию адреса фактического параметра используется операция взятия адреса, а для получения его значения в функции требуется операция разыменования. Третий параметр (k) передается по адресу с помощью ссылки.

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

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

 

Передача массивов в качестве параметров

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

#include <iostream.h>

int sum(const int * mas, const int n);

int const n = 10;

int main(){

int marks[n] = {3, 4, 5, 4, 4};

cout « "Сумма элементов массива: " « sum(marks, n);

return 0;

}

int sum(const int * mas, const int n){

// варианты: int sum(int mas[], int n)

// или int sum(int mas[n], int n)

// (величина n должна быть константой)

int s = 0;

for (int i = 0; i<n; i++) s += mas[i];

return s;

}

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

#include <stdio.h>

#include <stdlib.h>

int sum(const int *a, const int nstr, const int nstb);

int main(){

int b[2][2] = {{2, 2}, {4, 3}};

printf("Cуммa элементов b: %d\n", sum(&b[0][0], 2, 2));

// имя массива передавать в sum нельзя из-за несоответствия типов

int i, j, nstr, nstb, *a;

printf("Введите количество строк и столбцов: \n");

scanf("%d%d", &nstr, &nstb);

а = (int *)malloc(nstr * nstb * sizeof(int));

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

for (j = 0; j<nstb; j++)

scanf("%d", &a[i * nstb + j]);

printf("Cyммa элементов a: %d\n", sum(a, nstr, nstb));

return 0;

}

int sum(const int *a, const int nstr, const int nstb){

int i, j, s = 0;

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

for (j = 0; j<nstb; j++) s += a[i * nstb + j];

return s;

}

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

#include <iostream.h>

int sum(int **a, const int nstr, const int nstb);

int main(){

int nstr, nstb;

cin » nstr » nstb;

int **a, i, j;

// Формирование матрицы a:

a = new int* [nstr];

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

a[i] = new int [nstb];

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

for (j = 0; j<nstb; j++) cin » a[i][j];

cout « sum(a, nstr, nstb);

return 0;

}

int sum(int **a, const int nstr, const int nstb){

int i, j, s = 0;

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

for (j = 0; j<nstb; j++)s += a[i][j];

return s;

}

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

 

 

Параметры со значениями по умолчанию

Чтобы упростить вызов функции, в ее заголовке можно указать значения параметров по умолчанию. Эти параметры должны быть последними в списке и могут опускаться при вызове функции. Если при вызове параметр опущен, должны быть опущены и все параметры, стоящие за ним. В качестве значений параметров по умолчанию могут использоваться константы, глобальные переменные и выражения:

int f(int a, int b = 0);

void f1(int, int = 100, char* = 0); /* обратите внимание на пробел между * и = (без него получилась бы операция сложного присваивания *=) */

void err(int errValue = errno); // errno - глобальная переменная

f(100); f(a, 1); // варианты вызова функции f

f1(a); f1(a, 10); f1(a, 10, "Vasia"); // варианты вызова функции f1

f1(a, ,"Vasia") // неверно!

 

 

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

Если список формальных параметров функции заканчивается многоточием, это означает, что при ее вызове на этом месте можно указать еще несколько параметров. Проверка соответствия типов для этих параметров не выполняется, char и short передаются как int, a float - как double. В качестве примера можно привести функцию printf, прототип которой имеет вид:

int printf (const char*, ...);

Это означает, что вызов функции должен содержать по крайней мере один параметр типа char* и может либо содержать, либо не содержать другие параметры:

printf("Введите исходные данные"); // один параметр

printf("Cyммa: %5.2f рублей", sum); // два параметра

printf("%d %d %d %d", a, b, c, d); // пять параметров

Для доступа к необязательным параметрам внутри функции используются макросы библиотеки va_start, va_arg и va_end, находящиеся в заголовочном файле <stdarg.h>.

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

 

 

Рекурсивные функции

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

Классическим примером рекурсивной функции является вычисление факториала (это не означает, что факториал следует вычислять именно так). Для того чтобы получить значение факториала числа n, требуется умножить на n факториал числа (n-1). Известно также, что 0!=1 и 1!=1.

long fact(long n){

if (n==0 || n==1) return 1;

return (n * fact(n - 1);

}

To же самое можно записать короче:

long fact(long n){

return (n>1) ? n * fact(n - 1) : 1;

}

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

 

 

Задачи для решения на тему «функции»

1. Даны действительные числа s, t. Получить f(t, -2s, 1.17)+f(2.2, t, s-t), где .

2. Даны действительные числа s, t. Получить g(1.2, s)+g(t, s)-g(2s-1, st), где .

3. Дано действительное число y. Получить , где

4. Даны действительные числа a, b, c. Получить .

5. Даны действительные числа a, b. Получить u= min(a, b), v = min(ab,a+b), d = min(u+v2, 3.1416).

6. Даны натуральные числа n, m, целые числа a1, ..., an, b1, ..., bm, c1, ..., c30. Получить

 

при

в противном случае

7. Даны натуральные числа k, l, m, действительные числа x1, ..., xk, y1, ..., yl, z1, ..., zm. Получить

 

при

в противном случае

8. Даны действительные числа s, t. Получить h(s, t)+max(h2(s-t, st), h4(s-t, s+t))+h(1, 1), где

9. Даны действительные числа a0, ..., a6. Получить для x=1, 3, 4 значения p(x+1)-p(x), где p(y)=a6 y6 +a5y5 +...+a0.

10. Даны действительные числа s, t, a0, ...., a12. Получить p(1)-p(t)+p(s-t)-p(1), где p(x)=a12x12 +a11x11 +...+a0.

11. Даны действительные числа a1, ..., an, b1, ..., bm. В последовательности a1, ..., an, и в последовательности b1, ..., bm, все члены, следующие за членом с наибольшим значением (за первым по порядку, если их несколько), заменить на 0.5.

12. Даны целые числа a1, ..., an, b1, ..., bm, k. Если в последовательности a1, ..., an, нет ни одного члена со значением k, то первый по порядку член этой последовательности, не меньший всех остальных членов, заменить на значение k. По такому же правилу преобразовать последовательность b1, ..., bm применительно к значению 10.

13. Даны натуральные числа n, m найти НОД(n, m). Использовать программу, включающую РЕКУРСИВНУЮ процедуру вычисления НОД, основанную на соотношении НОД(n, m)= НОД(m, r), где r - остаток от деления n на m.

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

15. Написать процедуру сортировки строк матрицы в порядке неубывания максимального по модулю элемента. Оформить как функцию вычисление максимального по модулю элемента строки и как процедуру – перестановку строк.

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

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

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

 

 

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

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

 

Директива #include

Директива #include <имя_файла> вставляет содержимое указанного файла в ту точку исходного файла, где она записана. Включаемый файл также может содержать директивы #include. Поиск файла, если не указан полный путь, ведется в стандартных каталогах включаемых файлов. Вместо угловых скобок могут использоваться кавычки (" ") - в этом случае поиск файла ведется в каталоге, содержащем исходный файл, а затем уже в стандартных каталогах.

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

Заголовочные файлы обычно имеют расширение .h и могут содержать:

  • определения типов, констант, встроенных функций, шаблонов, перечислений;
  • объявления функций, данных, имен, шаблонов;
  • пространства имен;
  • директивы препроцессора;
  • комментарии.

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

 

Директива #define

Директива #definе определяет подстановку в тексте программы. Она используется для определения:

  • символических констант: #define имя текст_подстановки (все вхождения имени заменяются на текст подстановки);
  • макросов, которые выглядят как функции, но реализуются подстановкой их текста в текст программы: #define имя( параметры) текст_подстановки;
  • символов, управляющих условной компиляцией. Они используются вместе с директивами #ifdef и #ifndef. Формат:

#define имя

Примеры:

#define VERSION 1

#define VASIA "Василий Иванович"

#define MAX(x,y) ((x)>(y)?(x):(y))

#define MUX

Имена рекомендуется записывать прописными буквами, чтобы зрительно отличать их от имен переменных и функций. Параметры макроса используются при макроподстановке, например, если в тексте программы используется вызов макроса у = MAX(sum1, sum2), он будет заменен на

у = ((sum1)>(sum2)?(sum1):(sum2));

Отсутствие круглых скобок может привести к неправильному порядку вычисления, поскольку препроцессор не оценивает вставляемый текст с точки зрения синтаксиса. Например, если к макросу #define sqr(x) (х*х) обратиться как sqr(y+l), в результате подстановки получится выражение (у+1*у+1).

Макросы и символические константы унаследованы из языка С, при написании программ на С++ их следует избегать. Вместо символических констант предпочтительнее использовать const или enum, а вместо макросов - встроенные функции или шаблоны.

 

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

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

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

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

struct Node{

Data d; // тип данных Data должен быть определен ранее

Node *р;

};

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

 

 

Линейные списки

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

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

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

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

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

struct Node{

int d;

Node *next;

Node *prev;

};

Ниже приведена программа, которая формирует список из 5 чисел, добавляет число в список, удаляет число из списка и выводит список на экран. Указатель на начало списка обозначен pbeg, на конец списка - pend, вспомогательные указатели - pv и pkey.

#include <iostream.h>

struct Node{

int d;

Node *next;

Node *prev;

};

//-----------------------------------------------------------

Node * first(int d);

void add(Node **pend, int d);

Node * find(Node * const pbeg, int i);

bool remove(Node **pbeg, Node **pend, int key);

Node * insert(Node * const pbeg, Node **pend, int key, int d);

//-----------------------------------------------------------

int main(){

Node *pbeg = first(1); // Формирование первого элемента списка

Node *pend = pbeg; // Список заканчивается, едва начавшись

// Добавление в конец списка четырех элементов 2, 3, 4 и 5:

for (int i = 2; i<6; i++) add(&pend, i);

// Вставка элемента 200 после элемента 2:

insert(pbeg, &pend, 2, 200):

// Удаление элемента 5:

if (!remove (&pbeg, &pend, 5))cout « "не найден";

Node *pv = pbeg;

while (pv){ // вывод списка на экран

cout « pv->d « ' ';

pv = pv->next;

}

return 0;

}

//-----------------------------------------------------------

// Формирование первого элемента

Node * first(int d){

Node *pv = new Node;

pv->d = d;

pv->next = 0;

pv->prev = 0;

return pv;

}

//-----------------------------------------------------------

// Добавление в конец списка

void add(Node **pend, int d){

Node *pv = new Node;

pv->d = d;

pv->next = 0;

pv->prev = *pend;

(*pend)->next = pv;

*pend = pv;

}

//-----------------------------------------------------------

// Поиск элемента по ключу

Node * find(Node * const pbeg, int d){

Node *pv = pbeg;

while (pv){

if(pv->d == d)break;

pv = pv->next;

}

return pv;

}

//-----------------------------------------------------------

// Удаление элемента

bool remove(Node **pbeg, Node **pend, int key){

if(Node *pkey = find(*pbeg, key)){ // 1

if (pkey == *pbeg){ // 2

*pbeg = (*pbeg)->next;

(*pbeg)->prev =0;}

else if (pkey == *pend){ // 3

*pend = (*pend)->prev;

(*pend)->next =0;}

else{ // 4

(pkey->prev)->next = pkey->next;

(pkey->next)->prev = pkey->prev;}

delete pkey;

return true; // 5

}

return false; // 6

}

//-----------------------------------------------------------

// Вставка элемента

Node * insert (Node * const pbeg, Node **pend, int key, int d){

if (Node *pkey = find(pbeg, key)){

Node *pv = new Node;

pv->d = d;

// 1 - установление связи нового узла с последующим:

pv->next = pkey->next;

// 2 - установление связи нового узла с предыдущим:

pv->prev = pkey;

// 3 - установление связи предыдущего узла с новым:

pkey->next = pv;

// 4 - установление связи последующего узла с новым:

if( ркеу != *репd) (pv->next)->prev = pv;

// Обновление указателя на конец списка,

// если узел вставляется в конец:

else *pend = pv;

return pv;

}

return 0;

}

Результат работы программы: 1 2 200 3 4

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

Рассмотрим подробнее функцию удаления элемента из списка remove. Ее параметрами являются указатели на начало и конец списка и ключ элемента, подлежащего удалению. В строке 1 выделяется память под локальный указатель pkey, которому присваивается результат выполнения функции нахождения элемента по ключу find. Эта функция возвращает указатель на элемент в случае успешного поиска и 0, если элемента с таким ключом в списке нет. Если pkey получает ненулевое значение, условие в операторе if становится истинным (элемент существует), и управление передается оператору 2, если нет - выполняется возврат из функции со значением false (оператор 6).

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

Если удаляемый элемент находится в конце списка (оператор 3), требуется сместить указатель pend конца списка на предыдущий элемент, адрес которого можно получить из поля prev последнего элемента. Кроме того, нужно обнулить для нового последнего элемента указатель на следующий элемент. Если удаление происходит из середины списка, то единственное, что надо сделать, - обеспечить двустороннюю связь предыдущего и последующего элементов. После корректировки указателей память из-под элемента освобождается, и функция возвращает значение true.

Работа функции вставки элемента в список проиллюстрирована на рисунке 11.1. Номера около стрелок соответствуют номерам операторов в комментариях.

Контрольная работа по программированию заказать

 

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

Ниже приведена функция формирования упорядоченного списка (предполагается, что первый элемент существует):

void add_sort(Node **pbeg, Node **pend, int d){

Node *pv = new Node; // добавляемый элемент

pv->d = d;

Node * pt = *pbeg;

while (pt){ // просмотр списка

if (d < pt->d){ // занести перед текущим элементом (pt)

pv->next = pt;

if (pt == *pbeg){ // в начало списка

pv->prev = 0;

*pbeg = pv;}

else{ // в середину списка

(pt->prev)->next = pv;

pv->prev = pt->prev;}

pt->prev = pv;

return;

}

pt = pt->next;

}

pv->next = 0; // в конец списка

pv->prev = *pend;

(*pend)->next = pv;

*pend = pv;

}

 

Стеки

Стек - это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last in - first out, последним пришел - первым ушел). Стек проще всего представить себе как закрытую с одного конца узкую трубу, в которую бросают мячи. Достать первый брошенный мяч можно только после того, как вынуты все остальные. Кстати, сегмент стека назван так именно потому, что память под локальные переменные выделяется по принципу LIFO. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.

Ниже приведена программа, которая формирует стек из пяти целых чисел (1,2, 3, 4, 5) и выводит его на экран. Функция помещения в стек по традиции называется push, а выборки - pop. Указатель для работы со стеком (top) всегда ссылается на его вершину.

#include <iostream.h>

struct Node{

int d;

Node *p;

};

Node * first(int d);

void push(Node **top, int d);

int pop(Node **top);

//-----------------------------------------------------------

int main(){

Node *tор = first(1);

for (int i = 2; i<6; i++) push(&top, i);

while (top)

cout « pop(&top) « ' ';

return 0;

}

//-----------------------------------------------------------

// Начальное формирование стека

Node * first(int d){

Node *pv == new Node;

pv->d = d;

pv->p = 0;

return pv;

}

//-----------------------------------------------------------

// Занесение в стек

void push(Node **top, int d){

Node *pv = new Node;

pv->d = d;

pv->p = *top;

*top = pv;

}

//-----------------------------------------------------------

// Выборка из стека

int pop (Node **tор){

int temp = (*top)->d;

Node *pv = *tор;

*tор = (*top)->p;

delete pv;

return temp;

}

Результат работы программы: 5 4 3 2 1

 

Очереди

Очередь - это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка - из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in - first out, первым пришел - первым ушел). Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например, при моделировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе.

Ниже приведена программа, которая формирует очередь из пяти целых чисел и выводит ее на экран. Функция помещения в конец очереди называется add, а выборки - del. Указатель на начало очереди называется pbeg, указатель на конец - pend.

#include <iostream.h>

struct Node{

int d;

Node *p;

};

Node * first(int d);

void add(Node **pend, int d);

int del(Node **pbeg);

//-----------------------------------------------------------

int main(){

Node *pbeg = first(1);

Node *pend = pbeg;

for (int i = 2; i<6; i++) add(&pend, i);

while (pbeg)

cout « del(&pbeg) « ' ';

return 0;

}

//-----------------------------------------------------------

// Начальное формирование очереди

Node * first(int d){

Node *pv = new Node;

pv->d = d;

pv->p = 0;

return pv;

}

//-----------------------------------------------------------

// Добавление в конец

void add(Node **pend, int d){

Node *pv = new Node;

pv->d = d;

pv->p = 0;

(*pend)->p = pv;

*pend = pv;

}

//-----------------------------------------------------------

// Выборка

int del(Node **pbeg){

int temp = (*pbeg)->d;

Node *pv = *pbeg;

*pbeg = (*pbeg)->p;

delete pv;

return temp;

}

Результат работы программы: 1 2 3 4 5

 

Бинарные деревья

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

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

function way_around ( дерево ){

way_around ( левое поддерево )

посещение корня

way_around ( правое поддерево )

}

Для бинарных деревьев определены операции:

  • - включения узла в дерево;
  • - поиска по дереву;
  • - обхода дерева;
  • - удаления узла.

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

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

#include <iostream.h>

struct Node{

int d;

Node *left;

Node *right;

};

Node * first (int d);

Node * search_insert(Node *root, int d);

void print_tree(Node *root, int l);

//-----------------------------------------------------------

int main(){

int b[] = {10, 25, 20, 6, 21, 8, 1, 30};

Node *root = first(b[0]);

for (int i = 1; i<8; i++) search_insert(root, b[i]);

print_tree(root, 0);

return 0;

}

//-----------------------------------------------------------

// Формирование первого элемента дерева

Node * first (int d){

Node *pv = new Node;

pv->d = d;

pv->left = 0;

pv->right = 0;

return pv;

}

//-----------------------------------------------------------

// Поиск с включением

Node * search_insert(Node *root, int d){

Node *pv = root, *prev;

bool found = false;

while (pv && !found){

prev = pv;

if (d == pv->d) found =true;

else if (d < pv->d) pv = pv->left;

else pv = pv->right;

}

if (found) return pv;

// Создание нового узла:

Node *pnew = new Node;

pnew->d = d;

pnew->left = 0;

pnew->right = 0;

if (d < prev->d)

// Присоединение к левому поддереву предка:

prev->left == pnew;

else

// Присоединение к правому поддереву предка:

prev->right = pnew;

return pnew;

} '

//-----------------------------------------------------------

// Обход дерева

void print_tree(Node *p, int level){

if (p){

print_tree(p->left, level +1); // вывод левого поддерева

for (int i = 0; i<level; i++)cout « " ";

cout « p->d « endl; // вывод корня поддерева

print_tree(p->right, level +1); // вывод правого поддерева

}

}

Текущий указатель для поиска по дереву обозначен pv, указатель на предка pv обозначен prev, переменная pnew используется для выделения памяти под включаемый в дерево узел. Рекурсии удалось избежать, сохранив всего одну переменную (prev) и повторив при включении операторы, определяющие, к какому поддереву присоединяется новый узел.

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

 

Задачи на тему «динамические структуры»

Вариант 1. Сформировать файл из реальных чисел и с помощью очереди за один просмотр файла напечатать элементы файла в следующем порядке: сначала все числа, меньшие а, затем все числа из отрезка [a, b], и наконец – все остальные числа, сохраняя исходный порядок в каждой из этих групп чисел.

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

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

Вариант 4. В текстовом файле записана без ошибок формула вида: цифра или М(формула, формула) или m(формула, формула), где М обозначает функцию max, m – min. Вычислить значение данной формулы (например, M(5,m(6,8))=6).

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

Вариант 6. В текстовом файле записана без ошибок формула вида: цифра или R(формула, формула) или L(формула, формула), где R обозначает функцию взять правое число, L – взять левое число. Вычислить значение данной формулы (например, R(8,R(3,L(4,5)))=4).

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

Вариант 8. В текстовом файле записан текст, сбалансированный по круглым скобкам. Написать программу, которая для каждой пары, соответствующей открывающей и закрывающей скобок, печатает номера их позиций в тексте, упорядочив пары номеров в порядке возрастания номеров позиций закрывающих скобок. Например, для текста A+(45–F(x)*(B–C)) надо напечатать: 8, 10; 12, 16; 3, 17.

Вариант 9. Сформировать файл из натуральных чисел и с помощью очереди за один просмотр файла напечатать элементы файла в следующем порядке: сначала все числа, большие b, затем числа из отрезка [a, b], сохраняя исходный порядок каждой из этих групп чисел.

Вариант 10. В текстовом файле записана без ошибок формула вида: цифра или S(формула, формула) или P(формула, формула), где S(a,b)=(a+b) mod 10, P(a,b)=(a*b) mod 10. Вычислить значение данной формулы (например, P(6,S(8,4))=2).

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

Вариант 12. В текстовом файле записана без ошибок формула вида: цифра или m(формула, формула) или p(формула, формула), где m(a,b)=(a–b) mod 10, p(a,b)=(a+b) mod 10. Вычислить значение данной формулы (например, m(9,p(p(3,5),m(3,8)))=6).

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

Вариант 14. Сформировать файл из натуральных чисел и за один просмотр файла напечатать его элементы в следующем порядке: сначала все однозначные числа, затем все двузначные. Первая группа чисел выводится в исходном порядке, вторая – в обратном (например, 2,15,7,24,37,8 –> 2,7,8,37,24,15).

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

Вариант 16. Дан текстовый файл, состоящий из n целых чисел. Создать двоичное дерево, состоящее из его компонент, и составить программу, увеличивающую все ключи дерева на число k.

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

Вариант 18. Дан текстовый файл, состоящий из n целых чисел. Создать двоичное дерево, состоящее из его компонент, и составить программу, определяющую количество вершин k-го уровня дерева.

Вариант 19. Дан текстовый файл, состоящий из n целых чисел. Создать двоичное дерево, состоящее из его компонент, и составить программу, проверяющую равенство деревьев T1 и T2.

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

 

Задание на курсовую работу

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

  • 1. Личная библиотека. Картотека домашней библиотеки: выходные данные книги (авторы, название, издательство и так далее), раздел библиотеки (специальная литература, хобби, домашнее хозяйство, беллетристика и так далее), происхождение и наличие книги в данный момент, субъективная оценка книги. Выбор книг по произвольному запросу; инвентаризация библиотеки.
  • 2. Картотека Интерпола. Данные по каждому зарегистрированному преступнику: фамилия, имя, кличка, рост, цвет волос и глаз, особые приметы, гражданство, место и дата рождения, последнее место жительства, знание языков, преступная профессия, последнее дело и так далее. Преступные и мафиозные группировки (данные о подельщиках). Выборка по любому подмножеству признаков. Перенос «завязавших» в архив; удаление - только после смерти.
  • 3. Бюро знакомств. База потенциальных женихов и невест: пол, регистрационный номер, дата регистрации, сведения о себе, требования к партнеру. Выбор подмножества подходящих кандидатур, подготовка встреч (формирование приглашения для знакомства). Перенос в архив пар, решивших свои семейные проблемы, удаление клиентов, отказавшихся от услуг.
  • 4. Биржа труда. База безработных: анкетные данные, профессия, образование, место и должность последней работы, причина увольнения, семейное положение, жилищные условия, контактные координаты, требования к будущей работе. База вакансий: фирма, должность, условия труда и оплаты, жилищные условия, требования к специалисту. Поиск и регистрация вариантов с той и другой стороны; формирование объявлений для печати, удаление в архив после трудоустройства, полное удаление при отказе от услуг.
  • 5. Записная книжка. Анкетные данные, адреса, телефоны, место работы или учебы, должность знакомых, коллег и родственников, характер знакомства, деловые качества) и т.д. Автоматическое формирование поздравления с днем рождения (по текущей дате). Упорядочение по алфавиту и по дате последней корректировки. Поиск по произвольному шаблону.
  • 6. Касса аэрофлота. Расписание: помер рейса, маршрут, пункты промежуточной посадки, время отправления, дни полета. Количество свободных мест на каждом рейсе. Выбор ближайшего рейса до заданного пункта (при наличии свободных мест), оформление заданного числа билетов по согласованию с пассажиром (с уменьшением числа свободных мест), оформление посадочной ведомости.
  • 7. Справочник потребителя (служба быта). База предприятий бытового обслуживания города: название, разряд, адрес и телефоны, специализация, перечень оказываемых услуг, форма собственности, часы и дни работы. Поиск предприятия по заданной услуге и другим признакам.
  • 8. Справочник покупателя. База торговых точек города: название, адрес и телефоны, специализация, форма собственности, время работы. Выбор магазинов по произвольному шаблону.
  • 9. Магазин с одним продавцом. Компьютер вместо кассового аппарата. База наличия товаров: наименование, единица измерения, цена единицы, количество, дата последнего завоза. Регистрация поступления товара (как старых, так и новых наименований). Оформление покупки: выписка чека, корректировка базы. Проблема уценки и списания. Инвентаризация остатков товара с вычислением суммарной стоимости.
  • 10. Отдел кадров. База данных о сотрудниках фирмы: паспортные данные, образование, специальность, подразделение, должность, оклад, даты поступления в фирму и последнего назначения и т.д. Выбор по произвольному шаблону. Сокращение штатов: выбор для увольнения лиц пенсионного и предпенсионного возраста, подготовка приказа.
  • 11. Генеалогическое дерево. Паспортные данные членов некоторого родового клана; ссылки на детей (или на родителей). Поиск всех потомков или всех предков для указанного лица.
  • 12. Склад. База товаров, хранящихся на складе: наименование, единица измерения, цена единицы, количество, дата последнего завоза. Регистрация поступления товара (формирование приходной накладной) и отгрузки (расходная накладная). Вывод инвентарной ведомости.
  • 13. Касса автовокзала. Расписание автобусов: номер рейса, конечный и промежуточный пункты, время отправления. Количество свободных мест на каждом рейсе. Выбор ближайшего рейса до заданного пункта (при наличии свободных мест), оформление билетов, оформление посадочной ведомости. Предварительная продажа, возврат билетов.
  • 14. Администратор гостиницы. Список номеров: класс, число мест. Список гостей: паспортные данные, даты приезда и отъезда, номер. Поселение гостей: выбор подходящего номера (при наличии свободных мест), регистрация, оформление квитанции. Отъезд: выбор всех постояльцев, отъезжающих сегодня, освобождение места или оформление задержки с выпиской дополнительной квитанции. Возможность досрочного отъезда с перерасчетом. Поиск гостя по произвольному признаку.
  • 15. Сбербанк. Сведения о вкладчиках банка: номер лицевого счета, категория вклада, паспортные данные, текущая сумма вклада, дата последней операции. Операции приема и выдачи любой суммы, автоматическое начисление процентов.
  • 16. Ломбард. База хранимых товаров и недвижимости: анкетные данные клиента, наименование товара, оценочная стоимость; сумма, выданная под залог, дата сдачи, срок хранения. Операции приема товара, возврата, продажи по истечении срока хранения.
  • 17. Справочник селекционера. Наименование сорта какой-либо культуры, автор, родительские сорта, урожайность, характеристики плодов, морозоустойчивость, устойчивость к вредителям и болезням, наличие в том или ином селекционном фонде. Выбор сортов, обладающих заданными свойствами.
  • 18. Справочник работника ГИБДД. Марка, цвет, заводской и бортовой номера, дата выпуска, особенности конструкции и окраски, дата последнего техосмотра транспортного средства (автомобиля, мотоцикла, прицепа ит. д.), паспортные данные владельца. Выбор транспортных средств по произвольному шаблону. Формирование приглашений на техосмотр в соответствии со сроком.
  • 19. Каталог запчастей автомобиля. В автомобиле насчитывается несколько тысяч деталей; некоторые используются в разных марках. Таблицы: страна, фирма-изготовитель, марка автомобиля, агрегат, узел, деталь. Учет взаимозаменяемости. Пользователи: работники автосервиса, магазинов запчастей; поставщики-оптовики.
  • 20. Телепрограмма. Программа телепередач нескольких телекомпаний (на неделю по дням, часам). Разные жанры телепередач: новости, спорт, художественные фильмы, сериалы и т. д. Выбор совокупной программы по определенному запросу (вкусу). Программирование видеомагнитофона при временных «накладках» передач.