- •Тема 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.Алгоритм расчета резервов времени
- •Расчет резервов времени
- •Вопросы для повторения
Вопросы для повторения
Понятие константы
Использование директивы препроцессора #define.
Понятие переменной.
Основные типы данных языка Си (int, long, short, unsigned, char, float, double)
Понятие структуры данных.
Механизмы агрегирования ячеек памяти.
Графическое представление структуры данных.
Оператор определения имени типа typedef
Понятие массива.
Понятие указателя.
Связь между массивами и указателями в Си.
Внешние и внутренние переменные.
Функция printf().
Функция scanf().
Оператор присваивания
Арифметические операции
Операции увеличения и уменьшения
Операции сравнения
Логические операции
Побитовые логические операции
Операции сдвига
Операции "увеличить на", "домножить на" и т.п.
Операции с указателями.
Операция приведения типа
Назначение управляющих конструкций
Фигурные скобки
Оператор выбора if и операция условия
Оператор множественного выбора switch
Оператор цикла while
Оператор цикла for
Оператор цикла do...while
Понятие структуры.
Указатели и структуры.
Структуры и оператор определения имени типа typedef
Понятие строки.
Представление строк в языке Си.
Матрицы и многомерные массивы.
Понятие пользовательской функции.
Синтаксис определение пользовательских функций в Си.
Прототипы функций.
Аргументы командной строки.
Резюме по теме
В данной теме рассмотрены основы языка Си.
Тема 4.Работа с файлами
Цели и задачи изучения темы
В данной теме рассматриваются основные средства языка Си для работы с файлами.
4.1.Последовательность шагов при работе с файлами
Стандартная библиотека Си содержит набор функций для работы с файлами. Прототипы этих функций описаны в заголовочном файле "stdio.h.
Отметим, что файловый ввод-вывод не является частью языка Си, и существуют другие библиотеки, поддерживающие ввод-вывод. Однако использование стандартной библиотеки позволяет легко портировать программы с одной платформы на другую.
Работа с файлами складывается из трех шагов.
1. Файл открывается. Это означает, что программа "захватывает" заданный по имени файл, и сообщает операционной системе, что далее она будет с ним работать.
2. Ведется работа с файлом. Из него данные либо считываются, либо в него записываются.
3. Файл закрывается. После этой операции он снова доступен другим программам для обработки.
4.2.Функция открытия файла fopen
Для доступа к файлу применяется структурный тип данных FILE. Этот тип определен в файле "stdio.h" и может быть системно зависимым, поэтому в целях переносимости программ обращаться явно к полям структуры FILE запрещено. Функция открытия файла fopen возвращает указатель на FILE, который используется далее для работы с открытым файлом. Прототип функции fopen выглядит следующим образом:
FILE *fopen(const char *path, const char *mode);
Здесь path - путь к файлу, mode - режим открытия файла.
Строка mode может содержать несколько букв:
"r" (от слова read) означает, что файл открывается для чтения (файл должен существовать).
"w" (от слова write) означает запись в файл, при этом старое содержимое файла теряется, а в случае отсутствия файла он создается.
"a" (от слова append) означает запись в конец существующего файла или создание нового файла, если файл не существует.
При открытии бинарного файла к строке mode следует добавлять букву "b" (от слова binary), а при открытии текстового файла - букву "t" (от слова text). Кроме того, при открытии можно разрешить выполнять как операции чтения, так и записи; для этого используется символ + (плюс). Порядок букв в строке mode следующий: сначала идет одна из букв "r", "w", "a", затем в произвольном порядке могут идти символы "b", "t", "+".
Открытие файла как текстового указывает, что файл состоит из строк, разделенных определенными символами, которые зависят от операционной системы. Например, в MS DOS и MS Windows это два символа "\r\n". При вводе символы "\r\n" заменяются одним символ "\n". Соответственно, при выводе символ "\n" заменяется на пару "\r\n". В системе Unix строки разделяются одним символом "\n". Таким образом, внутреннее представление текста в Си всегда соответствует системе Unix, а внешнее - реально используемой операционной системе.
Приведем примеры открытия файлов:
FILE *f, *g, *h;
. . .
// 1. Открыть текстовый файл "abcd.txt" для чтения
f = fopen("abcd.txt", "rt");
// 2. Открыть бинарный файл "c:\Windows\Temp\tmp.dat" для чтения и записи
// (для разделения директорий используется прямая косая черта / )
g = fopen("c:/Windows/Temp/tmp.dat", "wb+");
// 3. Открыть текстовый файл "c:\Windows\Temp\abcd.log" для дописывания
// в конец файла (для разделения директорий используется обратная косая
// черта повторенная 2 раза \\)
h = fopen("c:\\Windows\\Temp\\abcd.log", "at");
Обратите внимание, что стандартная библиотека Си позволяет в именах файлов использовать прямую косую черту и обратную, при этом обратная должна быть повторена дважды (обратная косая черта должна повторяться дважды во всех символьных строках).
Если файл открыт, то fopen возвращает ненулевой указатель на структуру типа FILE. В противном случае возвращается нулевой указатель, при этом глобальная системная переменная errno, описанная в стандартном заголовочном файле "errno.h, содержит численный код ошибки открытия файла. В следующем примере анализируется ошибка открытия файла:
#include <stdio.h>
#include <errno.h>
. . .
FILE *f = fopen("filnam.txt", "rt");
if (f == NULL) {
printf("Ошибка открытия файла с кодом %d\n",errno);
. . .
}
Константа NULL определена в файле "stdio.h". Для расшифровки кода errno можно использовать функцию perror(<строка>), которая печатает переданную строку и системное сообщение о последней ошибке.
Например, предыдущий фрагмент можно переписать следующим образом:
#include <stdio.h>
. . .
FILE *f = fopen("filnam.txt", "rt");
if (f == 0) {
perror("Не могу открыть файл на чтение");
. . .
}
При выполнении данной программы в случае отсутствия файла "filnam.txt" будет напечатано "Не могу открыть файл на чтение: No such file or directory"