Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Казанский государственный технический университет им. А. Н. Туполева
А.Р. Бикмурзина, Шершуков К.В.
Учебно-методический комплекс
ОПД.Ф.05 “Программирование на языке высокого уровня”
Лекции
Направление: 230100 “Информатика и вычислительная техника”,
Специальности: 230102 “Автоматизированные системы обработки
информации и управления”,
230101 “Вычислительные машины, комплексы, системы
и сети”
Формы обучения: очная, очно-заочная и заочная
Содержание
Часть 1: «Основы программирования»
Лекция 1. Содержание дисциплины 3
Лекция 2. Основные понятия. Структура программы. Ввод-вывод 12
Лекция 3. Программирование циклов. Оператор цикла while 27
Лекция 4. Операторы цикла for и do while. Программирование ветвлений. 36
Лекция 5. Обработка числовых последовательностей 42
Лекция 6. Последовательная обработка символьных данных 55
Лекция 7. Обработка массивов 62
Лекция 8. Указатели. Динамические массивы. Подпрограммы 74
Лекция 10. Разработка алгоритмов и программ сверху вниз. Примеры
зачетных задач 95
Лекция 11. Рекурсивные функции. Библиотечные функции обработки
символьных строк 104
Лекция 12. Массивы и функции как параметры 114
Лекция 13. Структуры и работа с файлами 123
Часть 2: «Методы программирования»
Лекция 14. Данные и алгоритмы 137
Лекция 15. Создание списков 146
Лекция 16. Обработка списков 156
Лекция 17. Таблицы 166
Лекция 18. Очереди 178
Лекция 19. Стеки 185
Лекция 20. Графы 196
Лекция 21. Деревья. Обход дерева 211
Лекция 22. Обход графа 222
Лекция 23. Кратчайшие пути и расстояния в графе 229
Лекция 24. Древовидные таблицы 235
Лекция 25. Примеры задач по структурам данных 242
Лекция 1
Введение
Основной целью преподавания дисциплины является обучение студентов методам разработки программ, языкам программирова ния, средствам и методам обработки данных с различной структу рой, приобретение ими навыков программирования задач обработки числовой и символьной информации.
Лекционный курс для студентов специальностей 230101 и 230102 состоит из двух частей «Основы программирования» и «Методы программирования» и рассчитан на два семестра.
В первой части «Основы программирования» студенты должны познакомиться с современными методами и средствами pазpаботки алгоритмов и пpогpамм, приемами стpуктуpного пpогpаммиpования, способами записи алгоpитма на базовом языке высокого уpовня.
В качестве базового языка используется язык С (Си).
Студенты должны уметь составлять и тестировать программы обработки данных разного типа (арифметических, логических, символьных) с использованием подпрограмм.
Во второй части «Методы программирования» рассматриваются различные методы организации и обработки данных. Студенты должны знать способы эффективной реализации абстрактных стpуктуp дан ных (очередей, стеков, таблиц, графов, деревьев, множеств) и комбинаторные алгоритмы, уметь описывать их на базовом языке.
На лабораторных занятиях студенты осваивают работу в системе программирования на ба зовом языке и получают навыки разработки и отладки программ.
Студенты заочной формы обучения должны самостоятельно выполнить ряд контрольных заданий: разработать алгоритмы решения задач, составить и отладить на компьютере программы, оформить выполненные задания в виде отчетов и сдать преподавателю.
В первом семестре студенты сдают зачет по дисциплине, во втором – экзамен. Кроме того, необходимо выполнить курсовую работу (в третьем семестре студентам очной формы обучения, во втором семестре студентам очно-заочной и заочной форм обучения).
Основой данного лекционного курса послужил читаемый на кафедре АСОИУ курс лекций по программированию для двух направлений “Информатика и вычислительная техника” и “Информационные системы ”. Данный курс переработан, во-первых с целью его использования для дистанционного обучения, во-вторых дополнен контрольными заданиями и примерами их выполнения для студентов заочной формы обучения.
Содержание части 1 «Основы программирования»
В этой части дается классификация языков программирования, рассматриваются основные понятия: алгоритм, программа, система программирования. Рассматриваются способы описания алгоритмов, критерии качества программы.
Рассматриваются основные конструкции языка С (и С++) и базовая технология создания программ, отвечающих современным требованиям качества и надежности.
Чтобы программа была качественной и надежной, она должна иметь простую структуру, быть хорошо читаемой и легко модифицируемой. Структурный подход к программированию позволяет создавать такие программы.
Структурное программирование – это технология создания программ, основанная на использовании трех базовых структур: последовательности, ветвления и цикла. На структуры накладывается ряд ограничений, что позволяет упростить разработку алгоритмов и программ, облегчить отладку программ и при необходимости их модификацию.
На рис. 1.1 представлены базовые структуры структурного программирования. Каждая структура должна иметь один вход и один выход. Любой алгоритм строится только из этих структур, где каждый блок, изображенный в виде прямоугольника («процесс») может быть заменен любой из трех структур. Например, внутри цикла может быть последовательность, содержащая ветвление и внутренний цикл (рис. 1.2).
Рис. 1.2. Вложение базовых структур
Каждой структуре в конкретном языке программирования соответствует определенный оператор. Например, в языке С (С++) структура ветвления программируется с помощью условного оператора if, цикл с предусловием – с помощью оператора цикла while или for, а циклу с постусловием соответствует оператор do while. Если внутри цикла или ветвления содержится последовательная структура, то в программе пишется составной оператор – группа операторов, заключенная в фигурные скобки.
В структурной программе нет необходимости использовать оператор goto, который только запутывает программу. В программе нет беспорядочных переходов вверх/вниз, операторы выполняются последовательно. Такую программу легко читать (и понять), легко модифицировать.
Сложные программы разбиваются на отдельные части, которые оформляются как подпрограммы. Разбиение программы на подпрограммы позволяет облегчить процесс написания и отладки программы. Правила определения подпрограмм и их вызова тоже рассмотрены в первой части курса программирования.
Рассмотрен также вопрос разработки сложных программ по принципу «сверху вниз», когда разработка программы осуществляется поэтапно. На первом этапе разрабатывается главная программа, на втором этапе – подпрограммы, вызываемые из главной программы, на следующем этапе – подпрограммы следующего уровня и т. д. Этот метод, так же как и структурный подход, позволяет облегчить разработку и отладку сложных программ.
Часть 1 содержит различные примеры решения типовых задач числовой и символьной обработки, использования массивов, структур, примеры работы с файлами.
Содержание части 2 «Методы программирования»
В этой части рассматриваются методы организации и обработки данных в оперативной памяти компьютера.
Любая задача, решаемая на компьютере, представляет собой обработку данных. Для решения задачи необходимо разработать структуру данных и алгоритм. Сложность алгоритма, его эффективность во многом зависят от того, какую структуру имеют данные в программе. В сложных программных системах могут использоваться данные разных типов, например, таблицы, очереди, стеки, графы, деревья, множества. Это так называемые абстрактные структуры (типы) данных – АСД. Как описать АСД в программе (и, следовательно, как они будут храниться в памяти компьютера), как реализовать операции над этими данными, должен знать любой программист. С этими вопросами вам и предстоит познакомиться во втором семестре.
Существующие методы хранения данных в ОП можно разбить на две группы: последовательное (сплошное) размещение данных и связанное (цепное) хранение.
При последовательном хранении все элементы структур данных размещаются в памяти последовательно, между элементами нет промежутков (участков памяти, не принадлежащих данной структуре). К таким структурам хранения относятся массивы.
При связанном (цепном) представлении данных элементы структуры данных размещаются в памяти в произвольном порядке, между ними могут быть промежутки. Чтобы отыскать в памяти отдельные элементы, в каждом элементе хранятся адреса одного или нескольких других элементов. К таким структурам хранения относятся списки (связанные) и сети. В списках обычно каждый элемент, кроме информационной части, содержит один указатель на следующий элемент списка. В сетях в каждом элементе может быть несколько указателей на другие элементы.
В лекционном материале второй части рассматриваются вопросы организации списков и сетей, программирования операций над списками и сетями на языке С (С++).
Далее рассматриваются различные абстракт ные структуры данных. Дается их определение, перечисляются основные операции, способы их хранения и реализация операций на языке С (С++). Рассматриваются также основные комбинаторные алгоритмы.
Контрольные задания
В каждом семестре студенты заочной формы обучения должны выполнить несколько индивидуальных контрольных заданий (номера заданий выдаются преподавателем).
К каждому из заданий необходимо составить программу на языке С, подобрать тесты для проверки программы и отладить программу на компьютере. К заданиям первого семестра дополнительно необходимо составить схему алгоритма и трассировочную таблицу для проверки алгоритма на одном-двух тестах. По каждому заданию оформляется отчет, содержащий формулировку задания, схему алгоритма, трассировочную таблицу, текст программы и результаты тестирования программы на компьютере.
Рекомендуемая литература
а) Основная литература
1. Хохлов Д.Г. Введение в программирование: Учебное посо бие.- Казань: Изд-во Казан. техн. ун-та, 2005. - 136 с.
2. Хохлов Д.Г. Структуры данных и комбинаторные алгоритмы. Учебное пособие. - Казань: Изд-во Казан. техн. ун-та, 2006. - 100 с.
3. Хохлов Д.Г., Захарова З.Х. Введение в программирова ние. Практикум на языке С: Учебное пособие. - Казань: Изд-во Казан. техн. ун-та, 2006. - 96 с.
4. Хохлов Д.Г., Захарова З.Х. Практикум по структурам данных и комбинаторным алгоритмам: Учебное пособие.- Казань: Изд-во Казан. техн. ун-та, 2005. - 48 с.
5. Бикмурзина А.Р. Программирование на языке высокого уровня: Лабораторный практикум. – Казань. Изд-во Казан. гос. техн. ун-та , 2009. - 107 с.
6. Хохлов Д.Г. Основы технологии модульного программирования. Учебное пособие. - Казань. Изд-во Казан. гос. техн. ун-та , 2005. - 64 с.
7. Павловская Т.А. С/С++. Программирование на языке высокого уровня. - СПб: Питер, 2004. - 461с.
8. Павловская Т.А., Щупак Ю.А. С/С++. Структурное программирование: Практикум. - СПб: Питер, 2002. - 240с.
9. Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. Программирование и структуры данных: Учебное пособие. - Казань. Изд-во Казан. гос. техн. ун-та , 2008. - 147 с.
б) Дополнительная литература
10. Керниган Б., Ритчи Д. Язык программирования Си.- М.: Финансы и статистика, 2002. - 279 с.
11. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406 с.
12. Липский В. Комбинаторика для программистов. - М.: Мир, 1988.- 213 с.
13. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2000. - 960 с.
14. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные ал горитмы. Теория и практика. - М.: Мир, 1980. - 476 с.
15. Гудман С., Хидетниеми С. Введение в разработку и ана лиз алгоритмов. - М.: Мир, 1981. - 368 с.
16. Кнут Д. Искусство программирования на ЭВМ. Т. 1. Ос новные алгоритмы. - М.: Издат. Дом «Вильямс», 2000. - 720 с., Т. 2. Получисленные алгоритмы. - М.: Издат. Дом «Вильямс», 2000. - 832 с., Т. 3. Сортировка и поиск. - М.: Издат. Дом «Вильямс», 2000. - 832 с.
17. Холл П. Вычислительные структуры. Введение в не численное программирование. - М.: Мир, 1978. - 214 с.
да+
нет
ет
да
а) Последова- б) Цикл в) Цикл
тельность с предусловием с постусловием
условие
условие
г) Ветвление д) Сокращенное ветвление
условие
условие
Рис. 1.1. Базовые структуры структурного программирования
нет--
-
+
а) Последова- б) Цикл в) Цикл
тельность с предусловием с постусловием
условие
условие
г) Ветвление д) Сокращенное ветвление
условие
условие
Рис. 1.1. Базовые структуры структурного программирования
да
нет
нет
да