ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

 

 

Министерство образования Республики Беларусь

 

Учреждение образования

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»

 

Кафедра «Вычислительные методы и программирование»

 

В.Л.Бусько, А.Г.Корбит, Т.М.Кривоносова

 

 

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

ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

 

для студентов всех специальностей и всех форм обучения

 

Минск 2004

 

УДК 621.3.6 (075.8)

ББК22.193 Я73

С 35

 

Рецензент: канд. техн. наук, доцент, зав. кафедры ПОИТ БГУИР В.В.Бахтизин

 

 

Бусько В.Л., Корбит А.Г., Кривоносова Т.М.

Конспект лекций по курсу «Основы алгоритмизации и программирования» для студентов всех специальностей и всех форм обучения. - Мн.: БГУИР, 2004. - 89 с.: ил. 4.

 

ISBN

 

Общий курс программирования предполагает знакомство с устройством ПЭВМ, теорией кодирования и хранения данных в памяти; изучение и закрепление навыков разработки вычислительных алгоритмов решения задач; изучение языка программирования Си; освоение операционных систем, изучение и освоение различных технологий программирования при решении конкретных задач.

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

Настоящее пособие по курсу «Основы алгоритмизации и программирования» представляет собой конспект лекций по темам, охватывающим основные конструкции языка Си. Неотъемлемой частью данного пособия является лабораторный практикум [1], при выполнении которого студенты осваивают основные конструкции среды программирования и получают навыки алгоритмизации и решения задач на персональном компьютере.

 

УДК 621.3.6 (075.8)

ББК22.193 Я73

ISBN

 

 

ã Коллектив авторов, 2004

СОДЕРЖАНИЕ

	Стр.
1. Введение
1.1. История создания ЭВМ
1.2. Структура ПЭВМ
1.3. Классификация языков программирования
1.4. Размещение данных и программ в памяти ПЭВМ
1.5. Программные модули
1.6. Ошибки
1.7. Функциональная и модульная декомпозиции
1.8. Файловая система хранения информации
1.9. Операционная система
2. Основные понятия и определения
2.1. Этапы решения задач на ЭВМ
2.2. Понятие алгоритма и способы его записи
2.3. Свойства алгоритмов
2.4. Способы описания алгоритмов
2.5. Графическое описание алгоритма
2.6. Основные символы схемы алгоритма
2.7. Пример простейшего линейного алгоритма
2.8. Немного истории
3. Синтаксис языка Cи
3.1. Алфавит языка
3.2. Лексемы
3.3. Идентификаторы и ключевые слова
3.4. Знаки операций
3.5. Литералы (константы)
3.6. Комментарии
4. Базовые типы объектов
4.1. Простейшая программа
4.2. Основные типы данных
4.3. Декларация (объявление) объектов
4.4. Данные целого типа (int)
4.5. Данные символьного типа (char)
4.6. Данные вещественного типа (float, double)
5. Константы в программах
5.1. Целочисленные константы
5.2. Константы вещественного типа
5.3. Символьные константы
5.4. Строковые константы
	Стр.
6. Обзор операций
6.1. Операции, выражения
6.2. Арифметические операции
6.3. Операции присваивания
6.4. Сокращенная запись операции присваивания
6.5. Преобразование типов операндов арифметических операций
6.6. Операция приведения типа
6.7. Операции сравнения
6.8. Логические операции
6.9. Побитовые логические операции. Операции над битами
6.10. Операция , (запятая)
7. Обзор базовых инструкций языка С
7.1. Стандартная библиотека языка Си
7.2. Стандартные математические функции
7.3. Функции вывода данных на дисплей
7.4. Функции ввода информации
7.5. Ввод - вывод потоками
7.6. Дополнительные функции
8. Синтаксис операторов языка C
8.1. Условные операторы
8.2. Условная операция «? :»
8.3. Оператор выбора альтернатив (переключатель)
9. Составление циклических алгоритмов
9.1. Понятие цикла
9.2. Оператор с предусловием while
9.3. Оператор цикла с постусловием do – while
9.4. Оператор цикла с предусловием и коррекцией for
10. Операторы передачи управления
10.1. Оператор безусловного перехода goto
10.2. Оператор continue
10.3. Оператор break
10.4. Оператор return
11 . Указатели
11.1. Указатели
11.2. Операции над указателями (косвенная адресация)
12. Массивы
12.1. Понятие массива
12.2. Одномерные массивы
12.3. Многомерные массивы
12.4. Операция sizeof
12.5. Применение указателей
12.6. Указатели на указатели
12.7. Адресная функция
	Стр.
13. Работа с динамической памятью
13.1. Пример создания одномерного динамического массива:
13.2. Пример создание двуxмерного динамического массива:
4. Строки в языке Си
14.1. Русификация под Visual
15. Функции пользователя
15.1. Декларация функции
15.2. Вызов функции
15.3. Операция typedef
15.4. Указатели на функции
15.5. Параметры командной строки функции main
15.6. Функции с переменным числом параметров
16. Классы памяти и области действия объектов
16.1. Классы памяти объектов в языке Cи
16.2. Автоматические переменные
16.3. Внешние переменные
16.4. Область действия переменных
17. Структуры, объединения, перечисления
17.1. Структуры
17.2. Декларация структурного типа данных
17.3. Создание структурных переменных
17.4. Вложенные структуры
17.5. Массивы структур
17.6. Размещение структурных переменных в памяти
17.7. Объединения
17.8. Перечисления
18. Файлы в языке С
18.1. Открытие файла
18.2. Закрытие файла
18.3. Запись - чтение информации
18.4. Текстовые файлы
18.5. Бинарные файлы
Список рекомендуемой литературы
Список используемой литературы
Приложение 1. Таблицы символов ASCII
Приложение 2. Операции языка Си
Приложение 3. Возможности препроцессора

 

1. Введение

 

1.1. История создания ЭВМ

Проблема вычислений сопровождает человечество на всем историческом отрезке его существования. Первый счетный инструмент абак был известен еще в V веке до нашей эры в Египте, Финикии, Греции и представлял дощечку, покрытую слоем песка, на которой острой палочкой проводили линии и в получавшихся колонках по позиционному принципу размещали камешки. В древнем Риме абак назывался Calculi. От этого слова произошло в дальнейшем латинское calculatore (вычислять).

Первую счетную машину для выполнения сложения и вычитания сконструировал в 1623г. профессор математики и астрономии Тюбингенского университета В.Шинкард. Она была изготовлена в одном экземпляре и, сгорев во время пожара в 1624г., не оказала влияния на развитие идей счетной техники.

Биография механических счетных машин ведется от арифметической ма­ши­ны французского математика, физика и философа Б.Паскаля, созданной в 1642г. Над счетной машиной Б.Паскаль работал 12 лет и сделал около 50 действующих моделей. Первый арифмометр, выполняющий все четыре арифме­тических действия, был предложен в 1670г. немецким ученым Г.В.Лей­бни­цем. В Беларуси первая суммирующая машина была изобретена и изготовлена в 1770г. в г. Несвиже Евной Якобсоном, часовым мастером и механиком.

Идею универсальной вычислительной машины с программным упра­­влением впервые предложил в своем неосуществленном проекте в 1834 г. английский ученый Ч.Бэббедж. Ее структура совпадала по существу со стру­кту­рой современных ЭВМ.

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

Двоичную арифметику разработал Г.В.Лейбниц. Он также предложил ари­ф­ме­­тизацию логики за 200 лет до создания алгебры Дж.Буля (1815). Как двоичная арифметика представляет все числа с помощью двух символов (0,1), так и булева алгебра оперирует с двумя понятиями (истина, ложь) и тремя операциями (и, или, не).

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

Первая ЭВМ была создана в 1945г. (США), она представляла огромное сооружение, содержащее 18000 электронных ламп, 1500 реле и выполняла около 3000 умножений в секунду. Мировой парк ЭВМ к 1965г. насчитывал порядка 50 тысяч компьютеров, к началу 1975г. – более 200 тысяч.

Первые персональные ЭВМ (ПЭВМ) появились в начале 70-х годов. Скорость вычислений достигает 10⁸ операций в секунду.

 

Структура ПЭВМ

   

Классификация языков программирования

1. По степени абстракции от архитектуры компьютера:

- языки программирования низкого уровня - машинный язык (язык машин­ных кодов). Используя такой язык, программист должен полностью владеть архитектурой ЭВМ;

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

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

2. По структурному строению программ:

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

- объектно-ориентированные языки (C++, Java и др.) – из области решаемой проблемы выделяются классы, объединяющие связанные каким-либо признаком данные и функции по их обработке. Далее создаются объекты данных классов, которые, взаимодействуя друг с другом, осуществляют решение поставленной задачи.

 

Размещение данных и программ в памяти ПЭВМ

Таким образом, в одной ячейке из 8 двоичных разрядов помещается объем информации в один байт. Поэтому объем памяти принято оценивать количеством… Для помещения данных в такие ячейки производится их запись с помощью нулей и… При кодировании числа преобразуются в двоичное представление. Например,

Программные модули

Транслятор - программа, осуществляющая перевод текстов с одного языка на другой, т.е. транслятор переводит программу с входного языка системы… Интерпретатор представляет собой программный продукт, выполняющий созданную… Большинство трансляторов языка Си, с которыми мы будем работать - компиляторы.

Ошибки

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

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

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

Причина ошибки алгоритма - несоответствие построенного алгоритма ходу получения конечного результата сформулированной задачи.

Причина семантической ошибки - неправильное понимание смысла (сема­нти­ки) операторов языка.

 

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

Один из основных приемов - разбивка алгоритма на отдельные функции и/или модули, используя функциональную и/или модульную декомпозиции… Функциональная декомпозиция - метод разбивки большой программы на отдельные… Алгоритм декомпозиции можно представить следующим образом:

Файловая система хранения информации

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

Операционная система

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

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

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

В настоящее время наибольшее распространение имеют OC WindowsХХ и LinuxХХ.

 

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

Этапы решения задач на ЭВМ

Решение задачи на ЭВМ можно разбить на следующие этапы:

- математическая или информационная формулировка задачи;

- выбор метода (например, численного) решения поставленной задачи;

- построение алгоритма решения поставленной задачи;

- запись построенного алгоритма, т.е. написание текста программы;

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

- выполнение программы - получение требуемого результата.

 

Понятие алгоритма и способы его записи

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

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

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

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

 

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

Дискретность - значения новых величин (данных) вычисляются по опреде­лен­ным правилам из других величин с уже известными значениями.

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

Результативность (конечность) - алгоритм решает поставленную задачу за конечное число шагов.

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

 

Способы описания алгоритмов

Словесное описание алгоритма рассмотрим на конкретном примере: пусть необходимо найти наибольший общий делитель для двух целых положительных чисел a… 1) Сравнить a и b. Если a<b, то положить d=a; m=b, иначе d=b и m=a. 2) Разделить m на d. Обозначить остаток от деления r.

Графическое описание алгоритма

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

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

Схема данных содержит:

- символы данных (могут отображать тип носителя данных);

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

- символы линий, указывающих потоки данных между процессами и носите­ля­ми данных;

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

 

Основные символы схемы алгоритма

- данные ввода/вывода (носитель не определен);  

Специальные символы

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

Терминатор - вход из внешней среды или выход во внешнюю среду (начало или конец схемы программы).

Коментарий.

 

Пример простейшего линейного алгоритма

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

при x>0 - вещественное, m - целое.

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

Для того чтобы не было "длинных" операторов, исходное выражение полезно разбить на ряд более простых. В нашей задаче предлагается схема вычислений, представленная на рис. 3.

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

 

Немного истории

Язык продолжает развиваться и в 1985 г. появляется язык С++, который в основном сохраняет все черты обычного С, но дополнен новыми существен­ными… Язык С отражает возможности современных компьютеров. Программы на С отличаются… Области применения языка C - системное программирование и прикладные задачи с жесткими требованиями по скорости и…

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

Алфавит языка Си включает: - прописные и строчные буквы латинского алфавита, а также знак подчеркивания… - арабские цифры от 0 до 9;

Лексемы

Из символов алфавита формируются лексемы языка – минимальные значимые единицы текста в программе:

- идентификаторы;

- ключевые (зарезервированные) слова;

- знаки операций;

- константы;

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

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

Идентификаторы и ключевые слова

Длина иденти­фикатора определяется реализацией (версией) транслятора Cи и редактора связей (компоновщика). Современная тенденция - снятие… При именовании объектов следует придерживаться общепринятых соглашений: - ID переменной обычно пишется строчными буквами, например index (для сравнения: Index – это ID типа или функции, а…

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

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

Литералы (константы)

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

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

Комментарии

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

В Си комментарии ограничиваются парами символов /* и */, а в С++ был введен вариант комментария, который начинается символами // и заканчивается символом перехода на новую строку.

Базовые типы объектов

 

Простейшая программа

Общая структура программы на языке Си имеет вид: <директивы препроцессора> <определение типов пользователя – typedef>

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

Основные типы базовых данных: стандартный целый (int), веще­ствен­ный с одинарной точностью (float) и символьный (char). В свою очередь, данные целого типа могут быть короткими (short), длинными… Сложные типы – массивы, структуры (struct), объединения или смеси (union), перечисление (enum).

Константы в программах

 

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

- самоопределенные арифметические, символьные и строковые данные;

- идентификаторы массивов и функций;

- элементы перечислений.

Арифметические константы могут быть целого или вещественного типов.

 

Целочисленные константы

Десятичные константы - последовательность цифр 0...9, первая из которых не должна быть 0. Например, 22 и 273 - обычные целые константы, если нужно… Существует система обозначений для восьмеричных и шестнадца­те­­ри­чных… Восьмеричные константы - последовательность цифр от 0 до 7, первая из которых должна быть 0, например: 020 =…

Константы вещественного типа

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

1) с фиксированной десятичной точкой, формат записи: ±n.m, где n, m - целая и дробная части числа;

2) с плавающей десятичной точкой (экспоненциальная форма): ±n.mE±p, где n, m - целая и дробная части числа, р - порядок; ±0.xxxE±p - нормализованный вид, например, 1,25×10^-8 = 0.125E-8.

Примеры констант с фиксированной и плавающей точками:

1.0 -3.125 100е-10 0.12537е+13

 

Символьные константы

Так же используются специальные последовательности символов, это управляющие последовательности (escape-последовательности), основные их них: … При присваивании символьной переменной эти последователь­ности должны быть… Текстовые символы непосредственно вводятся с клавиатуры, а специальные и управляющие представляются в исходном тексте…

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

Строковая константа представляет собой последователь­ность символов кода ASCII, заключенная в кавычки (”) . Во внутреннем представлении к строковым константам добавляется нулевой символ '\0', еще называемый нуль-терминатор, отмечающий конец строки. Кавычки не являются частью строки, а служат только для ее ограничения. Строка - это массив, состоящий из символов. Внутреннее представление константы "01234\0ABCDEF":

'0','1','2','3','4','\0','A','B','C','D','E','F','\0'

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

"Система", "\n\t Аргумент \n", "Состояние \"WAIT\""

В конец строковой константы компилятор автоматически помещает нуль-символ. Нуль-символ - это не цифра 0, он на печать не выводится и в таблице кода ASCII имеет код 0.

Например, строка " " - пустая строка (нуль-строка).

Обзор операций

 

Операции, выражения

Операции языка Си предназначены для управления данными (более 40). Для их использования необходимо знать:

- синтаксис;

- приоритеты (15 уровней);

- порядок выполнения.

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

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

Большинство операций выполняются слева направо, например, a+b+c ® (a+b)+c. Исключение: унарные операции, операции присваивания и условная операция (?:) - справа налево.

Полный список операций в соответствии с их приоритетом приводится в Приложении 2.

Рассмотрим кратко основные операции языка Си.

 

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

Арифметические операции - бинарные. Перечень арифметических операций и их обозначений:

+ - сложение;

- - вычитание (либо унарная операция - изменение знака);

/ - деление (для int операндов - с отбрасыванием остатка);

* - умножение;

% - остаток от деления целочисленных операндов со знаком первого операнда (деление по модулю).

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

Порядок выполнения операций:

- выражения в круглых скобках;

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

- * / выполняются слева направо;

- + ─ слева направо.

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

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

Таким образом, так как операции *, /, % обладают высшим приоритетом над операциями +, -, при записи сложных выражений нужно использовать общеприня­тые математические правила:

x+y*z-a/b Û x+(y*z)-(a/b)

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

Формат операции присваивания:

< ID > = <выражение>;

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

int i, j, k;

float x, y, z;

...

i = j = k = 0; Û k = 0; j = k; i = j;

x = i+(y = 3) - (z = 0); Û z = 0; y = 3; x = i + y - z;

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

а) присваивание константе: 2 = x+y;

б) присваивание функции: getch() = i;

в) присваивание результату операции: (i+1) = 2+y;

Сокращенная запись операции присваивания

В языке Cи допускается две разновидности сокращений записи операции присваивания:

a) вместо записи:

v = v @ e;

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

v @ = e;

например, i = i + 2; « i + = 2;

б) вместо записи (автоувеличение):

x = x # 1;

где # - символ + либо -, обозначающий операцию инкремента либо декремента, x - целочисленная переменная, переменная-указатель), рекомендуется использовать запись

префиксная: ##x; постфиксная: x##;

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

Примеры использования сокращений (фрагменты программ):

1) int i,j,k;

float x,y;

...

x* = y; « x = x*y;

i+ = 2; « i = i+2;

x/ = y+15; « x = x/(y+15);

k--; « k = k-1;

--k; « k = k-1;

j = i++; « j = i; i = i+1;

j = ++i; « i = i+1; j = i;

 

2) int n,a,b,c,d;

n = 2; a = b = c = 0;

a = ++n; // n=3, a=3

a+ = 2; // a=5

b = n++; // b=3, n=4

b- = 2; // b=1

c = --n; // n=3, c=3

c* = 2; // c=6

d = n--; // d=3, n=2

d% = 2; // d=1

 

Рекомендации использования сокращений обоснованы возможностью оптимизации программы. Например, схема выражения вида v@=e соответствует схеме выполнения многих машинных команд типа "регистр-память", а использование ##х и x## наличием в Си специальных процессорных команд инкремента и декремента.

 

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

Типы операндов преобразуются в порядке увеличения их "размера памяти", т.е. объема памяти, необходимого для хранения их значений. Поэтому… short, char ® int ® unsigned ® long ® double float ® double

Операция приведения типа

Вид записи операции: (тип) выражение; Ее результат - значение выражения, преобразованное к заданному типу… Операция приведения типа вынуждает компилятор выполнить указанное преобразование, но ответственность за последствия…

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

== - равно или эквивалентно;

!= - не равно;

< - меньше;

<= - меньше либо равно;

> - больше;

>= - больше либо равно.

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

Общий вид операций отношений:

<выражение1> <знак_операции> <выражение2>

Общие правила:

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

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

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

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

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

! - отрицание (логическое НЕТ);

&& - коньюнкция (логическое И);

|| - дизьюнкция (логическое ИЛИ).

Общий вид операции отрицания:

!<выражение>

Общий вид операций коньюнкции и дизьюнкции

<выражение1> <знак_операции> <выражение2>

Например:

y>0 && x=7 ® истина, если 1-е и 2-е выражения истинны;

e>0 || x=7 ® истина, если хотя бы одно выражение истинно.

Ненулевое значение операнда трактуется как "истина", а нулевое - "ложь".

Например:

!0 ® 1

!5 ® 0

x=10;

!((x=y)>0) ® 0

Особенность операций коньюнкции и дизьюнкции – экономное последовательное вычисление выражений-операндов:

<выражение1> <операция><выражение2>,

- если выражение1 операции коньюнкция ложно, то результат операции - ноль и выражение2 не вычисляется;

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

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

scanf("%d",&i) && test1(i) && test2(i) ® нулевой результат одной из функций приведет к игнорированию вызова остальных;

search1(x) || search2(x) || search3(x) ® только ненулевой результат одной из функций приведет к игнорированию вызова остальных.

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

0<x<100 « (0<x)&&(x<100)

 

Побитовые логические операции. Операции над битами

В СИ предусмотрен набор операций для работы с отдельными битами слов. Эти операции нельзя применять к переменным вещественного типа (float, double).

Перечень операций над битами и их обозначения:

~ - дополнение (унарная операция); инвертирование (одноместная операция);

& - побитовое И - конъюнкция;

| - побитовое включающее ИЛИ - дизъюнкция;

^ - побитовое исключающее ИЛИ - сложение по модулю 2;

>> - сдвиг вправо;

<< - сдвиг влево.

Пары символов (>>,<<) разделять нельзя.

Общий вид операции инвертирования:

~<выражение>

Остальные операции над битами имеют вид:

<выражение1> <знак_операции> <выражение2>

Операндами операций над битами могут быть только выражения, приводимые к целому типу. Операции (~, &, |, ^) выполняются поразрядно над всеми битами операндов (знаковый разряд особо не выделяется):

~0xF0 Û x0F

0xFF & 0x0F Û x0F

0xF0 | 0x11 Û xF1

0xF4 ^ 0xF5 Û x01

Операция & часто используется для маскирования некоторого множества битов. Например, оператор w = n & 0177 передает в w семь младших битов n, полагая остальные равными нулю.

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

Операция (!) используется для включения битов w = x ! y, устанавливает в единицу те биты в x, которые =1 в y.

Необходимо отличать побитовые операции & и ! от логических операций && и ||, которые подразумевают вычисление значения истинности слева направо. Если x=1, y=2, то x & y равно нулю, а x && y равно 1.

0x81<<1 Û 0x02

0x81>>1 Û 0x40

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

Унарная операция (~) дает дополнение к целому. Это означает, что каждый бит со значением 1 получает значение 0 и наоборот. Эта операция обычно оказывается полезной в выражениях типа:

X & (~)077,

где последние 6 битов X маскируются нулем. Это выражение не зависит от длины слова и поэтому предпочтительнее, чем, например:

X & 0177700,

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

Операции сдвига << и >> осуществляют соответственно сдвиг вправо (влево) своего левого операнда, на число битовых позиций, задаваемых правым операндом. Таким образом, x<<2 сдвигает x влево на две позиции, заполняя, освобождающиеся биты, нулями, что эквивалентно умножению на 4.

Операции сдвига вправо на k разрядов весьма эффективны для деления, а сдвиг влево - для умножения целых чисел на 2 в степени k:

x<<1 « x*2

x>>1 « x/2

x<<3 « x*8

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

Двуместные операции над битами (&, |, ^, <<, >>) могут использоваться в сокращенных формах записи операции присваивания:

int i,j,k;

. . .

i |= j « i = i | j - включение в поле i единиц из поля j;

i &= 0xFF « i = i & 0xFF - выделение в поле i единиц по маске поля 0x00FF;

k ^= j - выделение в поле k отличающихся разрядов в полях k и j;

i ^= i - обнуление всех разрядов поля i .

 

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

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

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

~ - дополнение; | - объединение; & - пересечение.

Простейшее применение - проверка нечетности целого числа:

int i;

...

if (i &1) printf(" Значение i четно!");

 

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

(x + 15)>>4

Другие возможности оперирования над битами:

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

- доступ к битам как разрядам арифметических данных.

 

6.10. Операция , (запятая)

Данная операция используется при организации строго гарантированной последовательности вычисления выражений. Форма записи:

выражение1, …, выражениеN;

выражения1,…,N вычисляются гарантированно последовательно и результатом операции становится значение выражения N.

Пример:

m=(i=1, j=i++, k=6, n=i+j+k);

получим последовательность вычислений: i=1, j=i=1, i=2, k=6, n=2+1+6, и в результате m=n=9. Данный пример ничем не отличается от такого участка кода:

i =1; j = i; i++; k = 6; n = i+j+k; m = n;

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

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

 

Обзор базовых инструкций языка С

Стандартная библиотека языка Си

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

Часть библиотек - стандартизована и поставляется с компилятором.

В стандартную библиотеку входят функции, макросы, глобальные константы. Это файлы с расширением *.h, хранящиеся в папкеinclude.

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

 

Стандартные математические функции

Аргументы тригонометрических функций должны быть заданы в радианах (2π радиан = 3600). Большинство математических функций (приведенных здесь) возвращают значение…  

Функции вывода данных на дисплей

Формат функции printf(): printf((<управляющая строка>, список объектов вывода); - в управляющей строке, заключенной в кавычки, записывают: поясняющий текст; список модификаторов форматов,…

Функции ввода информации

Общий вид этой функции: scanf (<управляющая строка>, список адресов элементов ввода>); Количество, тип и порядок следования форматов должен точно совпадать с количеством, типом и порядком следования…

Ввод - вывод потоками

Чтение данных из потока - это извлечение (extraction). Вывод данных в поток - помещение или включение (insertion). Для ввода-вывода используются две переопределенные операции побитового сдвига << , >>. Формат записи:

Дополнительные функции

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

Функция void clrscr(void); - полностью очищает экран дисплея, переводя курсор в верхний левый угол. При работе в Visual C++ очистку экрана можно выполнить, используя функцию system(“cls”);

Функция int kbhit(void); - возвращает ненулевое целое значение при нажатии клавиши, в противном случае - нулевое.

 

Синтаксис операторов языка C

 

Операторы языка Си можно разделить на три группы:

- операторы-декларации (рассмотрены ранее);

- операторы преобразования объектов;

- операторы управления процессом выполнения алгоритма.

Программирование процесса преобразования объектов программы производится посредством записи выражений. Выражение включает один или несколько операндов и символов операций. Любое выражение, заканчивающееся символом «;» (точка с запятой), является оператором.

Простейший вид операторов - операторы-выражения.

Простые операторы:

- оператор присваивания - выполнение операций присваивания;

- оператор вызова функции - выполнение операции вызова функции;

- пустой оператор «;».

Классы управляющих операторов в языке Си следующие:

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

- оператор выбора альтернатив (переключатель);

- операторы организации циклов;

- операторы передачи управления (перехода).

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

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

 

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

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

if (выражение) оператор1;

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

Примеры записи:

if (x>0) x=0;

if (i!=1) j++, s=1; - используем операцию «запятая»;

if (i!=1) { j++; s=1; } - последовательность операций;

if (getch()!=27) { - если нажата клавиша, не “Esc”.

k=0;

}

if (i) exit(1); « if (i!=0) exit(1);

if (i>0)

if (i<n) k++; « if ((i>0)&&(i<n)) k++;

if (1) i=0; « i=0;

 

Синтаксис полного оператора условного выполнения:

if (выражение) оператор1;

else оператор2;

Если выражение в скобках не ноль (истина), то выполняется оператор1, иначе - оператор2. Операторы 1 и 2 могут быть простыми или составными.

Примеры записи:

if (x>0) j=k+10;

else m=i+10;

Если есть вложенная последовательность операторов if-else, то else связывается с ближайшим предыдущим if, не содержащим else. Например:

if (n>0)

if(a>b) z=a;

else z=b;

Если необходимо связать фразу else с внешним if, то используем операторные скобки:

if(n>0)

{ if (a>b) z=a; }

else z=b;

В следующей цепочке операторов if-else-if выражения просматриваются последовательно:

if (выражение1) оператор1;

else if (выражение2) оператор2;

else if (выражение3) оператор3;

else оператор4;

Если какое-то выражение оказывается истинным, то выполняется относящийся к нему оператор и этим вся цепочка заканчивается. Каждый оператор может быть либо отдельным оператором, либо группой операторов в фигурных скобках. Последняя часть с else имеет дело со случаем, когда ни одно из проверяемых условий не выполняется. Иногда при этом не нужно предпринимать никаких явных действий, в этом случае else оператор4; может быть опущен, или его можно использовать для контроля, чтобы засечь "невозможное" условие (экономия на проверке условий).

Пример:

if ( n < 0 ) printf ( "n отрицательное\n" );

else if ( n==0 ) printf ( "n равно нулю\n );

else prinf ( "n положительное\n );

 

8.2. Условная операция «? :»

Условная операция - тернарная, в ней участвуют три операнда. Формат написания условной операции следующий:

выражение 1 ? выражение 2 : выражение 3;

если выражение 1 отлично от нуля (Истинно), то результатом операции является выражение 2, в противном случае - результатом операции является выражения 3. Каждый раз вычисляется только одно из выражений 2 или 3.

Запишем оператор if, вычисляющий максимум из а и b и присваивающий его значение z.

if (a > b) z=a;

else z=b;

Используя условную операцию, этот пример можно записать:

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

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

Оператор выбора альтернатив (переключатель)

Общий вид оператора:

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

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

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

...

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

default: оператор(N+1); break; // может отсутствовать

}

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

case константное выражение:

Целочисленное выражение (константа выбора) после вычисления сравни­вается со значениями констант и при совпадении с одной из них выполняется передача управления соответствующему оператору. В случае несовпадения значения выражения с одной из констант происходит переход на метку default, либо, при ее отсутствии, к оператору, следующему за оператором switch.

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

Пример 1 с использованием оператора break:

void main(void)

{ int i = 2;

switch(i) {

case 1: puts ( "Случай 1. "); break;

case 2: puts ( "Случай 2. "); break;

case 3: puts ( "Случай 3. "); break;

default: puts ( "Случай default. "); break;

}

}

Для того, чтобы выйти из оператора switch в любом месте использовали оператор break, поэтому результатом будет: Случай 2.

Пример 2 (оператор break отсутствует):

void main()

{ int i=2;

switch(i) {

case 1: puts ( "Случай 1. ");

case 2: puts ( "Случай 2. ");

case 3: puts ( "Случай 3. ");

default: puts ( "Случай default. ");

}

}

Так как оператор разрыва отсутствует, результатом будет:

Случай 2.

Случай 3.

Случай default.

 

 

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

Понятие цикла

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

Для организации циклов используются специальные операторы.

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

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

Перечень разновидностей операторов цикла:

- оператор цикла с предусловием;

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

- оператор цикла с предусловием и коррекцией.

 

Оператор с предусловием while

Общий вид:

while (выражение) код_цикла;

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

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

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

char ch;

int count=0;

while (( ch=getchar())!='\n') count++;

Для выхода из цикла while при истинности выражения, как и для выхода из других циклов можно пользоваться оператором break.

Пример 1:

while (1) { // Организация бесконечного цикла

...

if (kbhit()&&(getch()==27)) break;

// Если нажата клавиша (результат работы функции kbhit()>0) и код ее равен 27 // (код клавиши “Esc”), то выходим из цикла

...

}

Пример 2:

...

while (!kbhit()); // Выполнять до тех пор, пока не нажата клавиша

...

Оператор цикла с постусловием do - while

Общий вид записи:

do код_цикла while (выражение);

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

 

Оператор цикла с предусловием и коррекцией for

Общий вид оператора:

for (выражение1; выражение2; выражение3) код_цикла;

Цикл for эквивалентен последовательности инструкций:

выражение1;

while (выражение2)

{

код_цикла ...

выражение3;

}

здесь выражение1 - инициация счетчика (начальное значение), выражение2 -условие продолжения счета, выражение3 - увеличение счетчика. Выражения 1,2 и 3 могут отсутствовать (пустые выражения), но символы «;» опускать нельзя.

Например, для суммирования первых N натуральных чисел можно записать:

sum = 0;

for ( i=1; i<=N; i++) sum+=i;

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

for ( sum=0 , i=1; i<=N; sum+= i , i++) ;

Оператор for имеет следующие возможности:

- можно вести подсчет с помощью символов, а не только чисел:

for (ch = 'a'; ch<='z'; ch++) ... ;

- можно проверить выполнение некоторого произвольного условия:

for (n = 0; s[i]>='0' && s[i]<'9'; i++) ... ;

или:

for (n = 1; n*n*n <=216; n++) ... ;

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

for (printf(" вводить числа по порядку! \n"); num!=6;)

scanf("%d", & num);

printf(" последнее число - это то, что нужно.\n");

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

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

Например:

for (n = 1; n<1000; n += delta) ... ;

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

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

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

printf("%6d%c",a[i],( (i%10==0) || (i==n-1) ) ? '\n' : ’ ‘);

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

 

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

 

Формально к операторам передачи управления относятся:

- оператор безусловного перехода goto;

- оператор перехода к следующему шагу (итерации) цикла continue;

- выход из цикла, либо оператора switch - break;

- оператор возврата из функции return.

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

 

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

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

goto < метка >;

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

m1: ;

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

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

for (...)

for (...)

{ ...

if ( ошибка ) goto error;

}

...

error: - операторы для устранения ошибки;

 

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

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

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

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

{

if (v[i][j]<0) goto found;

... // Не найден

}

found: ... // Найден

 

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

found = 0;

for (i=0; i<N && !found; i++)

for (j=0; j<M && !found; j++)

found = v[i][j]<0;

if (found) ... // Найден

else ... // Не найден

Оператор continue

Этот оператор может использоваться во всех типах циклов, но не в операторах переключателя switch. Наличие оператора continue вызывает пропуск "оставшей­ся" части итерации и переход к началу следующей, т.е. досрочное завершение текущего шага и переход к следующему шагу.

В циклах while и do это означает непосредственный переход к проверочной части. В цикле for управле­ние передается на шаг коррекции, т.е. модификации выражения 3.

Фрагмент программы обработки только положительных элементов массива a, отрицательные значения пропускаются:

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

{ if( a[i]<0) continue;

... // обработка положительных элементов

}

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

 

Оператор break

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

 

Оператор return

Оператор return; производит досрочный выход из текущей функции. Он, так же возвращает значение результата функции: return <выражение>;

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

Пример 1:

float estim(float *x, int n) {

int i;

float y;

if ((!x)||(!n) {

error(x,n);

return 0;

}

for (y=i=0; i<n; i++) y+=x[i];

return y/n;

}

 

Пример 2:

void error(void *x, int n)

{

if (!x) printf("\nМассив не создан");

if (!n) printf("\nМассив пустой");

}

 

 

Указатели

 

Указатели

<тип> *< ID переменной-указателя>; Например: int *a; double *f; char *w; С указателями связаны две унарные операции & и *.

Операции над указателями (косвенная адресация)

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

p # ie, ##p, p##, p# = ie,

где: p - указатель, ie - целочисленное выражение, # - символ операции '+' или '-'.

Значением таких выражений является увеличенное или уменьшенное значение указателя на величину ie*sizeof(*p). Следует помнить, что операции с указателями выполняются в единицах памяти того типа объекта, на который ссылается этот указатель.

Текущее значение указателя всегда ссылается на позицию некоторого объекта в памяти с учетом правил выравнивания для соответствующего типа данных. Таким образом, значение p#ie указывает на объект того же типа, расположенный в памяти со смещением на ie позиций.

При сравнении указателей могут использоваться отношения любого вида (">", ">=", "<", "<=", "==", "!="). Наиболее важными видами проверок являются отношения равенства или неравенства.

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

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

Любой указатель можно сравнивать со значением NULL, которое означает недействительный адрес. Значение NULL можно присваивать указателю как признак пустого указателя. NULL заменяется препроцессором на выражение (void *)0.

 

Ссылка

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

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

type &ID = инициализатор;

Инициализатор - это идентификатор объекта, на который в дальнейшем будет указывать ссылка. Пример:

int a = 8;

int &r = a;

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

a++;

r++;

 

 

12. Массивы

 

Понятие массива

. Произведение матрицы на вектор .

Одномерные массивы

<тип> < ID_массива>[размер]={список начальных значений}; где: тип – базовый тип элементов (целый, вещественный, символьный); размер – количество элементов массива.

Многомерные массивы

Как уже отмечалось, в языке Си кроме одномерных массивов возможна работа с многомерными массивами. Объявление многомерного массива:

<тип> < ID >[размер1][размер2]…[размерN]={{список начальных значений},

{список начальных значений},…};

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

Например, элементы двухмерного массива b[3][2] размещаются в памяти компьютера в следующем порядке:

b[0][0], b[0][1], b[1][0], b[1][1], b[2][0], b[2][1].

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

int a[3][4] = {{1,2,0,0},{9,-2,4,1},{-7,0,0,0}};

Если в какой-то группе { } список значений короче, то оставшимся элементам присваивается 0.

 

Операция sizeof

sizeof(параметр); где: «параметр» – тип или идентификатор объекта (не ID функции). Если указан идентификатор сложного объекта (массив, структура, объединение), то получаем размер всего сложного…

Применение указателей

Пусть объявлены массив a из 5 целочисленных элементов и указатель q на целочисленные переменные: int a[5], *q; ID массива a является константным указателем на его начало.

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

int a=5; int *p1=&a; int **pp1=&p1;

Адресная функция

Можно избежать таких расходов, если ввести адресную функцию для доступа к элементам одномерного массива (цепочка одномерных массивов со значениями)… L(i, j, k)=n1*n2*(i-1) + n2*(j-1)+k, где индексы принадлежат диапазонам: i=1..n1, j=1..n2, k=1..n3.

Работа с динамической памятью

В языке С размерность массива при объявлении должна задаваться константным выражением. При необходимости работы с массивами перемен­ной размерности… Пример создания динамического массива: float *x;

Строки в языке Си

В языке Си отдельного типа данных «строки символов» нет. Работа со строками реализована путем использования одномерных массивов типа char, т.е.… Нулевой байт – это байт, каждый бит которого равен нулю, при этом для нулевого… Например, char a[7]; - означает, что строка может содержать шесть символов, а последний байт отведен под нулевой.

Русификация под Visual

... #include<windows.h> char bufRus[256];

Функции пользователя

 

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

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

 

Декларация функции

Описание функции заключается в приведении вначале программного файла ее прототипа. Прототип функции сообщает компилятору о том, что далее в тексте… В стандарте языка используется следующий способ декларации функций: тип_результата ID_функции(тип переменной1, …, тип переменной N);

Вызов функции

ID _функции (список_аргументов); где в качестве аргументов можно использовать константы, переменные, выражения… Аргументы списка вызова должны полностью совпадать со списком параметров вызываемой функции по количеству, по порядку…

Операция typedef

typedef <тип> <новое_имя>; Введенный таким образом новый тип используется аналогично стандартным типам,… typedef unsigned int UINT;

Параметры командной строки функции main

Функция main может иметь третий параметр, который принято называть argp, и который служит для передачи в функцию main параметров операционной… Заголовок функции main с параметрами имеет вид: int main (int argc, char *argv[], char *argp[])

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

void varParFun(param_list, ...); void varParFun(...); Первый формат предоставляет объявления для части параметров. В этом случае проверка типов для объявленных параметров…

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

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

Внешние переменные

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

Структуры, объединения, перечисления

 

Структуры

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

Термин «структура» в языке Си соответствует двум разным по смыслу понятиям:

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

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

Определение объектов типа структуры производится за два шага:

- декларация структурного типа данных, не приводящая к выделению участка памяти;

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

 

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

struct ID структурного типа { описание полей };

Создание структурных переменных

Способ 1. В любом месте программы для декларации структурных переменных, массивов, функций и т.д., используется объявленный в шаблоне структурный… struct Stud_type student; - структурная переменная; Stud_type Stud[100]; - массив структур

Вложенные структуры

Например, в структуре person, содержащей сведения - Ф.И.О., дата рождения, сделать дату рождения внутренней структурой date по отношению к структуре… struct date { int day, month, year;

Массивы структур

Структурный тип "struct ID_структуры" как правило используют для декларации массивов, элементами которых являются структурные переменные. Это позволяет создавать программы, оперирующие с "примитивными базами данных". Например:

struct person spisok[100]; // spisok - массив структур

Или можно записать так:

struct person {

char fio[40];

int day, month, year;

} spisok[100];

В данном случае обращение к полю, например, day i-той записи может быть выполнено одним из следующих способов:

spisok[i].day=22; *(spisok+i).day=22; (spisok+i)->day=22;

 

Размещение структурных переменных в памяти

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

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

- любое поле структурной переменной начинается на границе слова, т.е. с четного адреса и имеет четное смещение по отношению к началу переменной;

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

 

Объединения

Объединенный тип данных декларируется подобно структурному типу: union ID_объединения { описание полей

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

Определение перечислимого типа данных имеет вид enum ID_перечислимого_типа { список_значений

Открытие файла

FILE*указатель на файл; FILE - идентификатор структурного типа, описанный в стандартной библиотеке… type struct{ short level; - число оставшихся в буфере непрочитанных байт; обычный размер буфера - 512…

Закрытие файла

Для закрытия нескольких файлов введена функция, объявленная следующим образом: void fcloseall(void); Если требуется изменить режим доступа к файлу, то для этого сначала необходимо… FILE* freopen(char *ID_файла, char *режим, FILE *указатель_файла);

Запись - чтение информации

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

- операции посимвольного ввода-вывода;

- операции построчного ввода-вывода;

- операции ввода-вывода по блокам.

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

Посимвольный ввод-вывод

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

int fgetc(FILE *f)	- считывает и возвращает символ из файла f;
int fputc(int ch, FILE *f)	- записывает в файл f код ch символа.

 

Построчный ввод-вывод

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

int fgets (char *S, int m, FILE *f)	- чтение из файла f в строку S m байт;
int fputs (char *S, FILE *f)	- запись в файл f строки S до тех пор, пока не встретится '\0', который в файл не пере­но­си­т­ся и на символ '\n' не заменя­ется.

 

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

Форматированный ввод-вывод производится функциями: int fscanf(FILE *f, char *формат, список адресов объектов)   -… Данные функции аналогичны функциям scanf() и printf(), рассмотренным раньше,…  

Текстовые файлы

Для работы с текстовыми файлами удобнее всего пользоваться функциями fprintf(), fscanf(), fgets() и fputs().

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

Рассмотрим пример создания текстового файла:

#include<stdio.h>

void main(void) {

FILE *f1;

int a=2, b=3;

If(!(f1=fopen(“d:\\work\\f_rez.txt”,”w+t”)))

{

puts(“Файл не создан!”);

return;

}

fprintf(f1,” Файл результатов \n”);

fprintf(f1,” %d плюс %d = %d\n”,a,b,a+b);

fclose(f1);

}

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

 

Бинарные файлы

Рассмотрим наиболее распространенные функции с помощью которых можно организовать работу с файлами: int fileno(FILE *f) – …   Пример программы работы с файлом структур:

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

 

1. Бусько В.Л., Корбит А.Г. и др. Программирование. Лабораторный практикум для студентов 1-2-го курсов всех специальностей БГУИР всех форм обучения. Часть 2. Основы программирования на алгоритмическом языке С.

2. Аксенкин М.А., Целобенок О.Н. Язык С. - Мн.: Унiверсiтэцкае, 1995. – 302 c.

3. Березин Б.И., Березин С.Б. Начальный курс С и С++. – М.: Диалог-МРТИ,1999. - 288 с.

4. Берри В., Микинз Б. Язык СИ: введение для программистов. - М.: Финансы и статистика,1988.

5. Больски М.Н. Язык программирования СИ. Справочник. - М.: Радио и связь, 1988.

6. Демидович Е.М. Основы алгоритмизации и программирования. Язык СИ. - Мн.: Бест­принт, 2001. – 440 c.

7. Касаткин А.И., Вольвачев А.Н. Профессиональное программирование на языке Си: Oт Turbo–C к Borland C++: Справочное пособие – Мн.: Вышэйшая школа,1992. - 240 с.

8. Касаткин А.Н. Профессиональное программирование на языке СИ. Управление ресурсами. Справочное пособие. Мн.: Высш. школа.1992

9. Керниган Б., Ритчи Д. Язык программирования Си. - М.: Финансы и статистика,1992. - 271 с.

10. Климова Л.И. С++. Практическое программирование. - М.: Кудиц-Образ, 2001. – 587 c.

11. Котлинская Г.П., Галиновский О.И. Программирование на языке СИ. - Мн.: Выш.шк., 1991. – 155 c.

12. Подбельский В.В., Фомин С.С. Программирование на языке Си. М.: Финансы и статистика. 2001.

13. Романовская Л.М., Русс Т.В., Свитковский С.Г. Программирование в среде СИ для ПЭВМ ЕС. - М.: Финансы и статистика, 1992.

14. Страуструп Б. Язык программирования С++. 2-е изд.: В 2 т. Киев: ДиаСофт,1993.

15. Тимофеев В.В. Программирование в среде С++ Builder 5. - М.: БИНОМ, 2000.

16. Уингер Р. Язык Турбо СИ. - М.: Мир, 1991.

17. Уэйт М., Прама С., Мартин Д. Язык СИ. Руководство для начинающих. - М.: Мир, 1988.

18. Фьюэр А. Задачи по языку СИ. - М.: Финансы и статистика, 1985.

19. Хэнкок Л., Кригер М. Введение в программирование на языке СИ. - М.: Радио и связь,1986.

20. Шилд Г. Программирование на Borland С++. - Мн.: ПОПУРРИ, 1999. – 800 c.

21. Юлин В.А., Булатова И.Р. Приглашение к СИ. - Мн.: Высш.шк., 1990.

 

Список используемой литературы

1. Синицын А.К. Конспект лекций по курсу «Программирование» для студентов 1-2-го курсов радиотехнических специальностей. - Мн.: БГУИР, 2001. - 75с.: ил. 10.

Приложение 1

Стандартная часть таблицы символов (ASCII)

КС

С

КС

С

КС

С

КС

С

КС

С

КС

С

КС

С

КС

С

►

@

P

`

p

☺

◄

!

A

Q

a

q

☻

↕

"

B

R

b

r

♥

‼

#

C

S

c

s

♦

¶

$

D

T

d

t

♣

§

%

E

U

e

u

♠

▬

&

F

V

f

v

•

↨

'

G

W

g

w

◘

↑

(

H

X

h

x

○

↓

)

I

Y

i

y

◙

→

*

:

J

Z

j

z

♂

←

+

;

K

[

k

{

♀

∟

,

<

L

\

l

|

♪

↔

-

=

M

]

m

}

♫

▲

.

>

N

^

n

~

☼

▼

/

?

O

_

o

⌂

 

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

Дополнительная часть таблицы символов

КС

С

КС

С

КС

С

КС

С

КС

С

КС

С

КС

С

КС

С

А

Р

а

░

└

╨

р

Ё

Б

С

б

▒

┴

╤

с

ё

В

Т

в

▓

┬

╥

т

Є

Г

У

г

│

├

╙

у

є

Д

Ф

д

┤

─

╘

ф

Ї

Е

Х

е

╡

┼

╒

х

ї

Ж

Ц

ж

╢

╞

╓

ц

Ў

З

Ч

з

╖

╟

╫

ч

ў

И

Ш

и

╕

╚

╪

ш

°

Й

Щ

й

╣

╔

┘

щ

∙

К

Ъ

к

║

╩

┌

ъ

·

Л

Ы

л

╗

╦

█

ы

√

М

Ь

м

╝

╠

▄

ь

№

Н

Э

н

╜

═

▌

э

¤

О

Ю

о

╛

╬

▐

ю

■

П

Я

п

┐

╧

▀

я

 

В таблицах обозначение КС означает "код символа", а С – "символ".

Приложение 2

 

 

Операции языка Си

 

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

 

Опера­ция	Краткое описание	Использование	Порядок выполнения
Унарные операции
.	Доступ к члену	объект . член	Слева направо
->	Доступ к члену по указателю	указатель -> член
[]	Индексирование	переменная[выражение]
()	Вызов функции	ID(список_выр.)
++	Постфиксный инкремент	lvalue++	Справа налево
--	Постфиксный декремент	lvalue--
sizeof	Размер объекта или типа	sizeof(выражение или тип)
++	Префиксный инкремент	++lvalue
--	Префиксный декремент	--lvalue
~	Побитовое НЕ	~выражение
!	Логическое НЕ	!выражение
-	Унарный минус	-выражение
+	Унарный плюс	+выражение
*	Раскрытие указателя	*выражение
&	Адрес	&выражение
()	Приведение типа	(тип)выражение
Бинарные и тернарная операции
*	Умножение	выражение * выражение	Слева направо
/	Деление	выражение / выражение
%	Получение остатка	выражение % выражение
+	Сложение	выражение + выражение
-	Вычитание	выражение – выражение
<<	Сдвиг влево	выражение << выражение
>>	Сдвиг вправо	выражение >> выражение
<	Меньше	выражение < выражение
<=	Меньше или равно	выражение <= выражение
>	Больше	выражение > выражение
>=	Больше или равно	выражение >= выражение
==	Равно	выражение == выражение
!=	Не равно	выражение != выражение
&	Побитовое И	выражение & выражение
^	Побитовое исключающее ИЛИ	выражение ^ выражение
|	Побитовое ИЛИ	выражение | выражение
&&	Логическое И	выражение && выражение
||	Логическое ИЛИ	выражение || выражение
?:	Условная операция (тернарная)	выражение ? выражение : выражение
Опера­ция	Краткое описание	Использование	Порядок выполнения
=	Присваивание	lvalue = выражение	Справа налево
*=	Умножение с присваиванием	lvalue *= выражение
/=	Деление с присваиванием	lvalue /= выражение
%=	Остаток от деления с присваиванием	lvalue %= выражение
+=	Сложение с присваиванием	lvalue += выражение
-=	Вычитание с присваиванием	lvalue -= выражение
<<=	Сдвиг влево с присваиванием	lvalue <<= выражение
>>=	Сдвиг вправо с присваиванием	lvalue >>= выражение
&=	Поразрядное И с присваиванием	lvalue &= выражение
|=	Поразрядное ИЛИ с присваиванием	lvalue |= выражение
^=	Поразрядное ИСКЛЮЧАЮ­ЩЕЕ ИЛИ с присваиванием	lvalue ^= выражение
,	Последовательное вычисление	выражение, выражение	Слева направо

 

 

Приложение 3

 

Возможности препроцессора и его вызов

 

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

Напомним, что признаком директивы препроцессора является символ # (обычно в начале строки). При необходимости продолжения директивы в следующей строке, текущую строку должен завершать символ '\'.

Возможности препроцессора языка C:

- лексемное замещение идентификаторов;

- макрозамещение;

- включение файлов исходного текста;

- условная компиляция;

- изменение нумерации строк и текущего имени файла.

 

Директивы лексемного замещения идентификаторов

Директива определения значения идентификатора:

#define ID строка

В результате каждое вхождение в исходный текст элемента «ID» заменяется на значение элемента «строка»:

#define L_bufs 2048

#define binary int

#define WAIT fflush(stdin); getch()

#define BEEP sound(800);\

delay(100);\

nosound()

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

#define YES 1

#define NO 2

#define ESC 27

#define Enter 30

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

if (x==ESC) break;

BEEP;

return(YES);

Директива отмены

#undef ID

Далее по исходному тексту можно назначить новое значение такого идентификатора.

Макрозамещение

#define ID(параметр1,... ) строка здесь между элементом «ID» и открывающей скобкой пробелы не допускаются. Такой вариант директивы define иногда называют макроопределением. Элемент «строка» обычно содержит параметры, которые…

Подключение файлов исходного текста

#include < ID_файла> вводит содержимое файла из стандартного каталога (обычно - \include\), а… #include " ID_файла"

Условная компиляция

а) условное включение (аналог работы оператора if): #if<предикат_условия> ТЕКСТ_1

Изменение нумерации строк и идентификатора файла

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

Директива

#line номер_строки ID_файла

позволяет с целью более приметной привязки к фрагментам текста изменить номер текущей строки и ID файла на новые значения («ID­_фай­ла» можно опустить). В системе программирования TURBO-C оператор line игнорируется.

 

 

Св. план 2004, поз. 27

 

 

Учебное издание

 

 

Бусько Виталий Леонидович,

Корбит Анатолий Григорьевич,

Кривоносова Татьяна Михайловна

 

 

 

 

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

ОСНОВЫ АЛГОРИТИМЗАЦИИ И ПРОГРАММИРОВАНИЯ

 

для студентов всех специальностей и всех форм обучения

 

 

Редактор Е.Н.Батурчик

Компъютерная верстка Т.В.Шестакова

 

Подписано в печать Формат 60x84 1/16. Бумага офсетная

Печать ризографическая Гарнитура «Ариал» Усл. печ. л.

Уч.-изд.л. Тираж 500 экз. Заказ .

 

Издатель и полиграфическое исполнение:

Учреждение образования

«Белорусский государственный университет информатики и радиоэлектроники»

Лицензия ЛП № 156 от 05.02.2001.

Лицензия ЛВ № 509 от 03.08.2001.

Минск, П.Бровки, 6.