- •Тема 1. Алгоритмы и программы 4
- •Тема 2. Характеристика языка Си 6
- •Тема 3. Основы языка Си 11
- •Тема 4.Работа с файлами 33
- •Тема 5.Распределение памяти 40
- •Тема 6. Методы организации данных в памяти эвм 43
- •Тема 7. Некоторые алгоритмы обработки данных 58
- •Тема 1. Алгоритмы и программы Цели и задачи изучения темы
- •1.1.Понятие алгоритма. Понятие программы. Способы записи алгоритмов.
- •1.2.Критерии качества программ
- •1.3.Низкоуровневые и высокоуровневые языки программирования
- •1.4.Принципы структурного программирования
- •Принципы структурного программирования.
- •2.2.Основные характеристики языка Си.
- •2.2.1.Достоинства языка Си
- •2.2.2.Компиляторы и интерпретаторы
- •2.2.3.Сильная типизация
- •2.3.Структура простой программы
- •Вопросы для повторения
- •3.1.2.Основные типы данных
- •3.1.3.Структуры данных
- •3.1.4.Оператор определения имени типа typedef
- •3.1.5.Массивы
- •3.1.6.Указатели
- •3.1.7.Указатели и массивы
- •3.1.8.Внешние и внутренние переменные
- •3.2.Стандартные функции ввода-вывода
- •3.3. Операции, операторы и выражения
- •3.3.1.Оператор присваивания
- •3.3.2.Арифметические операции
- •3.3.3.Операции увеличения и уменьшения
- •3.3.4.Операции сравнения
- •3.3.5.Логические операции
- •3.3.6.Побитовые логические операции
- •3.3.7.Операции сдвига
- •3.3.8.Операции "увеличить на", "домножить на" и т.П.
- •3.3.9.Операции с указателями. Указатели и массивы
- •3.3.10.Операция приведения типа
- •3.4.Управляющие конструкции
- •3.4.1.Фигурные скобки
- •3.4.2.Оператор выбора if и операция условия
- •3.4.3.Оператор множественного выбора switch
- •3.4.4.Оператор цикла while
- •3.4.5.Оператор цикла for
- •3.4.6.Оператор цикла do...While
- •3.5.Данные (более детальные сведения)
- •3.5.1.Структуры
- •3.5.2.Указатели и структуры
- •3.5.3.Структуры и оператор определения имени типа typedef
- •3.5.4.Строки
- •3.5.5.Матрицы и многомерные массивы
- •3.6.Пользовательские функции
- •3.6.1.Определение функций
- •3.6.2.Прототипы функций
- •3.6.3.Аргументы командной строки
- •Вопросы для повторения
- •4.2.Функция открытия файла fopen
- •4.3.Функции бинарного чтения и записи fread и fwrite
- •4.4.Функция закрытия файла fclose
- •4.5.Функции форматного чтения и записи fscanf и fprintf
- •4.6.Другие функции ввода-вывода
- •4.6.1.Функции посимвольного ввода-вывода
- •Int fgetc(file *f); - ввести один символ из файла f.
- •Int fputc(int c, file *f); - записать один символ в файл f.
- •4.6.2.Функции построкового ввода-вывода
- •Char *fgets(char *line,int size, file *f); - ввести строку из файла f.
- •Char *fputs(char *line, file *f); - записать строку в файл f.
- •4.6.3.Функции позиционирования в файле
- •Int fseek(file *f, long offset, int whence); - установить текущую позицию в файле f
- •Long ftell(file *f); - получить текущую позицию в файле f
- •Int feof(file *f); - проверить,достигнут ли конец файла f
- •Функция открытия файла fopen
- •Функции бинарного чтения и записи fread и fwrite
- •Функция закрытия файла fclose
- •5.2.Функции malloc и free
- •5.3.Выделение памяти под матрицы на этапе выполнения программы
- •Функции malloc и free.
- •6.2.Время выполнения программ
- •6.3.Списки
- •6.4.Реализация списков
- •6.5.Стеки
- •6.6.Реализация стеков
- •6.7.Очереди
- •6.8.Реализация очередей
- •6.9.Графы и деревья
- •6.10.Некоторые сд для хранения графов и деревьев
- •Матрица смежности графа, изображенного на рис.6.10
- •Матрица инцидентности графа, изображенного на рис.6.10
- •Матрица весов графа, изображенного на рис.6.11
- •Матрица смежности дерева, изображенного на рис.6.16
- •Вопросы для повторения
- •Реализация стеков.
- •Реализация очередей.
- •7.1.1.Поиск элемента в неупорядоченном массиве
- •7.1.2.Поиск элемента в упорядоченном массиве.
- •7.1.3.Фонетический поиск
- •7.2.Алгоритмы сортировки
- •7.2.1.Сортировка методом пузырька.
- •7.2.2.Сортировка вставками
- •7.2.3.Сортировка выбором
- •7.2.4.Пирамидальная сортировка
- •7.2.5.Быстрая сортировка
- •7.2.6.Сортировка слиянием
- •Этапы слияния файлов f1 и f2
- •7.3.Поиск на графах
- •7.3.1.Поиск в глубину
- •7.3.2.Поиск в ширину
- •7.4.Топологическая сортировка графа
- •7.5.Сетевое планирование
- •Информация о проекте
- •7.5.1.Алгоритм расчета наиболее ранних сроков наступления событий
- •7.5.2.Алгоритм расчета наиболее поздних сроков наступления событий
- •7.5.3.Алгоритм расчета резервов времени
- •Расчет резервов времени
- •Вопросы для повторения
2.2.2.Компиляторы и интерпретаторы
Для выполнения исходной программы на языке высокого уровня необходимо транслиировать (перевести) данную программу на машинный язык (язык машинных команд). Программые и/или аппаратные средства, осуществляющие этот процесс, называются трансляторами. Трансляторы могут быть построены различным образом.
Первый способ - осуществлять покомандную (пооператорную) трансляцию исходной программы на машинный язык и сразу осуществлять выполнение результата трансляции команды. Трансляторы подобного типа называются интерпретаторами. Пример языков интерпретируемого типа: Бейсик, Лого и др.
Достоинства интерпретаторов
Хорошая переносимость интерпретируемых программ - программа будет работать на любой платформе, на которой есть соответствующий интерпретатор.
Как правило, более совершенные и наглядные средства диагностики ошибок в исходных кодах.
Упрощение отладки исходных кодов программ.
Недостатки интерпретаторов
Интерпретируемая программа не может выполняться отдельно без программы-интерпретатора.
Интерпретируемая программа выполняется медленнее, поскольку промежуточный анализ исходного кода и планирование его выполнения требуют дополнительного времени в сравнении с непосредственным исполнением машинного кода, в который мог бы быть скомпилирован исходный код.
Практически отсутствует оптимизация кода, что приводит к дополнительным потерям в скорости работы интерпретируемых программ.
Второй способ - транслировать всю программу на машинный язык и в результате получить программу готовую к исполнению. Трансляторы такого типа называются компиляторами. Пример языков компилируемого типа: Паскаль, Фортран и др.
Достоинства компиляторов:
Программа, полученная в результате компиляции, может выполняться независимо от компилятора.
Программа, полученная в результате компиляции, выполняется быстрее интерпретируемой программы, поскольку промежуточный анализ исходного кода и планирование его выполнения не требуются.
В компиляторе, как правило, проводится оптимизация компилируемых программ.
Недостатки компиляторов:
Для переносимости компилируемых программ на новую платформу требуется компилятор работоспособный на новой платформе. С помощью данного компилятора необходимо выполнить компиляцию исходного кода и получить исполняемую программу для новой платформы. Этот процесс требует определенных временных затрат и квалификации.
Отладка и диагностика компилируемых программ может быть более трудоемкой по сравнению с интерпретируемыми программами.
Распространены также трансляторы, сочетающие в себе функции интерпретатора и компилятора. Такие трансляторы называют интерпретаторами компилирующего типа. Эти системы состоят из компилятора, переводящего исходный код программы в промежуточное представление (байт-код или p-код) и интерпретатора, который выполняет полученный промежуточный код (виртуальная машина). Достоинством интерпретаторов компилирующего типа является более высокая скорость выполнения программ по сравнению с интерпретаторами. Недостатки - большее требование к ресурсам. Применяется в таких языках, как Java, PHP, Python, Perl и др., а также в различных СУБД
Си - язык компилируемого типа. Процесс создания программы на Си обычно состоит из следующих шагов:
Создание программы на языке Си. Для этих целей используется редактор текстов.
Компиляция программу с помощью некоторого компилятора. Компилятор проведет проверку правильности программы. Если компилятор обнаружит ошибки в программе, то он выдаст сообщение об этом. Если ошибок не будет, компилятор выполнит перевод программы на машинный язык и поместит результат в новый файл. В некоторых вычислительных системах второй этап может быть разбит на два или три шага.
Выполнение программы полученной в результате компиляции.
Для упрощения процесса создания программ используются интегрированные среды разработки, ИСР (англ. IDE, Integrated development environment или integrated debugging environment). ИСР это система программных средств, используемая для разработки программного обеспечения.
Обычно среда разработки включает в себя:
текстовый редактор
компилятор и/или интерпретатор
средства автоматизации сборки
отладчик.
Иногда содержит также средства для интеграции с системами управления версиями и разнообразные инструменты для упрощения конструирования графического интерфейса пользователя. Многие современные среды разработки также включают браузер классов, инспектор объектов и диаграмму иерархии классов используемую при объектно-ориентированной разработке ПО.
Существуют среды разработки, предназначенные для нескольких языков программирования - такие, как Eclipse, NetBeans, Qt Creator, Microsoft Visual Studio и др.. Также существуют ИСР предназначенные для одного определённого языка программирования, например, Visual Basic, Delphi и др.
Частный случай ИСР - среды визуальной разработки, которые включают в себя возможность визуального редактирования интерфейса программы.
В рамках данного курса будет использоваться ИСР Eclipse (см. описание лабораторной работы №1)