В.1. Том Сойер рисует на заборе

Список литературы

Основная:

1. Емельянов А.А., Власова Е.А., Денисов Д.В., Емельянова Н.З. Основы программирования для информатиков и инженеров: Часть 1 / Под ред. А.А. Емельянова. – М.: ММИЭИФП, 2004. – 208 с.

2. Емельянов А.А., Власова Е.А., Емельянова Н.З. Практикум по основам программирования для информатиков и инженеров / Под ред. А.А. Емельянова. – М.: ММИЭИФП, 2004. – 162 с.

3. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1989. – 360 с.

4. Кнут Д. Искусство программирования для ЭВМ: в 3т. – М.: Мир, 1978.

Дополнительная:

 

5. Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения: Пер. с англ. – М.: Мир, 1982. – 386 с.

6. Лэнгсам И., Огенстайн М., Тененбаум А. Структуры данных для персо­нальных ЭВМ. – М.: Мир, 1989.

7. Сибуя М., Ямамото Т. Алгоритмы обработки данных. – М.: Мир, 1986.

8. Фокс Дж. Программное обеспечение и его разработка: Пер. с англ. – М.: Мир, 1985. – 368 с.

 

УЧЕБНАЯ ПРОГРАММА

Цель дисциплины, её место в учебном процессе

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

 

Задачи: составлять программы на алгоритмическом языке С++, знать принципы работы в среде программирования VisualC++, работать с массивами, структурами, списками, осуществлять отладку программ в среде программирования VisualC++.

 

Сфера профессионального использования

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

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

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

 

Для изучения данной дисциплины студент должен знать:

· математика;

· информатика (школьный курс);

· основы программирования.

Содержание дисциплины

 

Тема 1 . Обзор языка С++

Структура программы на языке С++. Среда программирования Visual C++. Переменные и константы. Оператор цикла. Работа с массивами. Массивы символов. Функции.

Тема 2. Типы операции и выражения

Имена переменных. Типы и размеры данных. Константы. Описания Арифметические операции. Операции отношения и логические операции. Преобразование типов. Операции увеличения и уменьшения. Побитовые логические операции. Операции и выражения присваивания. Условные выражения. Старшинство и порядок вычисления.

Тема 3.Поток управления

Операторы и блоки. Конструкция if-else. Конструкция else-if. Переключатель switch. Циклы while и for. Цикл do-while. Оператор break. Оператор continue. Оператор goto и метки.

Тема 4.Функции и структура программ

Основные сведения. Функции, возвращающие нецелые значения. Аргументы функций. Внешние переменные. Правила, определяющие область действия. Статические переменные. Регистровые переменные. Рекурсия. Препроцессор языка «C». Заголовочные файлы.

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

Указатели и адреса. Указатели и аргументы функций. Указатели и массивы. Адресная арифметика. Указатели символов и функции. Многомерные массивы. Массивы указателей; указатели указателей. Указатели и многомерные массивы. Командная строка аргументов. Указатели на функции.

Тема 6. Структуры

Основные сведения. Структуры и функции. Массивы структур. Указатели на структуры. Структуры, ссылающиеся на себя; двоичные деревья. Поиск в таблице. Битовые поля. Объединения.

 

Тема 7. Динамическое распределение памяти. Работа со списками

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

 

Тема8. Ввод, вывод и форматные преобразования данных

Стандартный ввод и вывод. Форматный ввод и вывод. Форматные преобразования в памяти. Доступ к файлам. Обработка ошибок. Ввод и вывод строк. Проверка вида символов и преобразования. Обращение к системе. Управление памятью.

 

Учебно-методическая и научная литература

3.1. Емельянов А.А., Власова Е.А., Денисов Д.В., Емельянова Н.З. Основы программирования для информатиков и инженеров: Часть 1 / Под ред. А.А. Емельянова. – М.: ММИЭИФП, 2004. – 208 с.

3.2. Березин Б.И., Березин С.Б. Начальный курс С и С++. – М.: ДИАЛОГ-МИФИ, 1996. – 288 с.

3.3. Джехани Н. Программирование на языке Си. - М.: Радио и связь, 1988.3.4. Керниган Б., Ритчи Д. Язык программирования Си.\ Пер. с англ., 3-е изд. испр. - СПб.: «Невский Диалект», 2001. – 352 с.

3.5. Крупник А. Изучаем С++. – СПб.:Питер, 2003. – 251 с.

3.6.Культин Н.Б. С/С++ в задачах и примерах. – СПб.: БХВ-Петербург, 2003. – 288 с.

3.7. Подбельский В.В. Язык Си++. - М.: Финансы и статистика, 1995.

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

УЧЕБНОЕ ПОСОБИЕ

 

    В первой части книги в систематической форме излагаются основы теории алгоритмизации и практики программирования на языке «С».

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

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

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

 

СОДЕРЖАНИЕ

 

ПРЕДИСЛОВИЕ. 6

 

ВВЕДЕНИЕ 8

В.1. Том Сойер рисует на заборе. 8

В.2. Сид выполняет команды.. 9

В.3. Программисты.. 10

В.4. Язык С++. 11

 

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АЛГОРИТМИЗАЦИИ И.. 12

ПРОГРАММИРОВАНИЯ.. 12

1.1. Основные понятия алгоритмизации. 12

1.2. Особенности алгоритмов. Программы.. 16

1.3. Математическая индукция. 23

1.4. Обобщенный алгоритм Евклида. 26

 

2. ПЕРВЫЕ ШАГИ «НАЧИНАЮЩИХ». 33

2.1. Давайте начнем, пожалуй! 34

2.2. Переменные и арифметика. 37

2.3. Оператор for 42

2.4. Символические константы.. 43

2.5. Набор полезных программ. 44

2.6. Массивы.. 52

2.7. Функции. 55

2.8. Аргументы: вызов по значению.. 57

2.9. Массивы символов. 58

2.10. Область действия: внешние переменные. 61

2.11. Некоторые оптимистичные выводы.. 64

 

3. ТИПЫ, ОПЕРАЦИИ И ВЫРАЖЕНИЯ.. 66

3.1. Имена переменных. 66

3.2. Типы и размеры данных. 66

3.3. Константы.. 68

3.4. Описания. 70

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

3.6. Операции отношения и логические операции. 72

3.7. Преобразование типов. 73

3.8. Операции увеличения и уменьшения. 77

3.9. Побитовые логические операции. 80

3.10. Операции и выражения присваивания. 82

3.11. Условные выражения. 83

3.12. Старшинство и порядок вычисления. 85

 

4. ПОТОК УПРАВЛЕНИЯ.. 88

4.1. Операторы и блоки. 88

4.2. Конструкция if-else. 88

4.3. Конструкция else-if 90

4.4. Переключатель switch. 92

4.5. Циклы while и for 94

4.6. Цикл do-while. 98

4.7. Оператор break. 99

4.8. Оператор continue. 100

4.9. Оператор goto и метки. 101

 

5. ФУНКЦИИ И СТРУКТУРА ПРОГРАММ.. 103

5.1. Основные сведения. 103

5.2. Функции, возвращающие нецелые значения. 107

5.3. Еще об аргументах функций. 110

5.4. Внешние переменные. 111

5.5. Правила, определяющие область действия. 116

5.6. Статические переменные. 120

5.8. Блочная структура. 122

5.9. Инициализация. 123

5.10. Рекурсия. 126

5.11. Препроцессор языка «C». 128

5.12. Заголовочные файлы.. 130

 

6. УКАЗАТЕЛИ И МАССИВЫ.. 132

6.1. Указатели и адреса. 132

6.2. Указатели и аргументы функций. 134

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

6.4. Адресная арифметика. 139

6.5. Указатели символов и функции. 143

6.6. Указатели – не целые. 146

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

6.8. Массивы указателей; указатели указателей. 150

6.9. Инициализация массивов указателей. 154

6.10. Указатели и многомерные массивы.. 155

6.11. Командная строка аргументов. 156

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

 

7. СТРУКТУРЫ.. 164

7.1. Основные сведения. 164

7.2. Структуры и функции. 166

7.3. Массивы структур. 169

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

7.5. Структуры, ссылающиеся на себя; двоичные деревья. 176

7.6. Поиск в таблице. 181

7.7. Битовые поля. 184

7.8. Объединения. 186

7.9. Определение «нового» типа данных. 188

 

8. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ. 190

РАБОТА СО СПИСКАМИ.. 190

8.1. Динамическое выделение и освобождение памяти. 190

8.2. Понятие списка; основные виды списковых образований. 191

8.3. Создание и удаление списка. 194

8.4. Программы позиционирования для работы со списками. 197

 

9. ВВОД, ВЫВОД И ФОРМАТНЫЕ ПРЕОБРАЗОВАНИЯ.. 200

ДАННЫХ.. 200

9.1. Обращение к стандартной библиотеке. 200

9.3. Форматный вывод: функция printf 203

9.4. Форматный ввод: функция scanf 205

9.5. Форматные преобразования в памяти. 208

9.6. Доступ к файлам. 209

9.7. Обработка ошибок: stderr и exit 212

9.8. Ввод и вывод строк. 213

9.9. Несколько разнообразных функций. 215

 

ЛИТЕРАТУРА.. 217

 

ПРЕДИСЛОВИЕ

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

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

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

 

В язык «C++» в качестве основного, базового средства включен более старый язык «C» (по-русски произносится как «си», поэтому некоторые авторы пишут его название как «Си»), который первоначально предназначался для написания операционной системы U nix; он был разработан и реализован Деннисом Ричи. Операционные системы U nix и Windows, компиляторы с языка «C++» и большинство прикладных программных систем сейчас создаются на языке «C++». Этот язык, однако, не связан с какими-либо определенными аппаратными средствами или системами, и на нем легко писать программы, которые можно пропускать без изменений на любом компьютере или ЭВМ, имеющей C-компилятор.

Целью первого учебного курса «Основы алгоритмизации и программирования» является обучение основам программирования. В это время студент, не будучи асом алгоритмизации, не сможет по достоинству оценить возможности объектно-ориентированного программирования, предоставляемые «C++». Поэтому сначала обучение ведется на классическом языке «С» (он входит в состав любой версии «С++) с минимальным привлечением дополнительных средств, имеющихся в «C++».

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

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

Мы не претендуем на оригинальность изложения теоретического материала по программированию. При создании данного учебного пособия нами использовались хрестоматийным образом данные из книг, пособий и справочников известных авторов: М.И. Болски, Б. Кернигана, Д. Кнута, Д. Дж. Круглински, А.Б. Крупника, Д. Ритчи, Г. Шилдта.

В качестве основного методического приема используется прагматический подход, изложенный в знаменитой книге Б. Кернигана и Д. Ритчи «Язык программирования Си», – это обучение на «живых» примерах.

Однако имеется и оригинальный материал. Например, глава 8 «Динамическое распределение памяти. Работа со списками» (в первой части книги), а также весь практикум по программированию.

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

 

 

    Редактор,     п рофессор А.А. Емельянов

ВВЕДЕНИЕ ^*

В.1. Том Сойер рисует на заборе

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

Марк Твен, «Приключения Тома Сойера»

 

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

1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0

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

2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 = 2⁸ = 256 способами.

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

Какие же буквы показаны на заборе? Ответ на этот вопрос зависит от договоренности: какому числу соответствует та или иная буква. Первое число (11010010) на заборе равно (в привычном нам десятичном представлении) 210, второе (11001110) – это 206, третье (11001100) равно 204. И вся эта тройка соответствует в операционной системе Windows, скорее всего установленной у вас на компьютере, слову «ТОМ».