- •Тема 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.Алгоритм расчета резервов времени
- •Расчет резервов времени
- •Вопросы для повторения
3.4.6.Оператор цикла do...While
Цикл do...while является циклом с постусловием. Сначала выполняется тело цикла и только после этого проверяется условие продолжения цикла. В Си для определения цикла do...while используется следующаий оператор:
do
действие;
while (условие);
Вначале выполняется действие. Далее проверяется условие и если условие истинно, то снова выполняется действие и так до тех пор пока условие не станет ложным. Таким образом, действие будет выполнено 1 раз, даже если условие ложно с самого начала. Это является потенциальным источником ошибок. Лучше всегда использовать цикл с предусловием while.
3.5.Данные (более детальные сведения)
3.5.1.Структуры
Структура - это конструкция, которая позволяет объединить несколько переменных с разными типами и именами в один составной объект. Она позволяет строить новые типы данных языка Си. В других языках программирования структуры называют записями или кортежами.
Описание структуры выглядит следующим образом:
struct имя_структуры {
описание полей структуры
};
Здесь имя_структуры - это любое имя, соответствующее синтаксису языка Си, описания полей структуры - любая последовательность описаний переменных, имена и типы этих переменных могут быть произвольными. Эти переменные называются полями структуры. Заканчивается описание структуры закрывающей фигурной скобкой. За закрывающей фигурной скобкой в описании структуры обязательно следует точка с запятой.
В качестве примера опишем точку в трехмерном пространстве, который задается тремя вещественными координатами x, y, z:
struct R3Point {
double x;
double y;
double z;
};
Таким образом, вводится новый тип struct R3Point. После того как структура определена, можно описывать переменные такого типа, при этом в качестве имени типа следует использовать выражение struct R3Point. Например, две точки в трехмерном пространстве с именами u, v будут описаны следующим образом:
struct R3Point u, v;
Переменные u,v содержит внутри себя три вещественных поля с именами x, y, z. Для доступа к полям структуры используется операция точка ".". Например, u.x является полем x структуры u, с ним можно работать как с обычной переменной.
В приведенных примерах все поля структуры R3Point имеют один и тот же тип double, однако полями структуры могут быть другие структуры, никаких ограничений нет.
При определении структуры можно выполнить инициализации ее полей:
struct R3Point u={0.1, 0.1, 0.7};
3.5.2.Указатели и структуры
Указатель на структуру S описывается обычным образом, в качестве имени типа фигурирует struct S*. Например, в следующем фрагменте переменная p описана как указатель на структуру S:
struct S { . . . }; // Определение структуры S
struct S *p; // Описание указателя на структуру S
Описание структуры может содержать указатель на структуру того же типа в качестве одного из полей. Язык Си допускает использование указателей на структуры, определение которых еще не завершено. Например, рассмотрим структуру TreeNode (вершина дерева), которая используется при определении бинарного дерева. Она содержит указатели на родительский узел и на левого и правого сыновей, которые также имеют тип struct TreeNode:
struct TreeNode { // Вершина дерева
struct TreeNode *parent; // Указатель на отца,
struct TreeNode *left; // на левого сына,
struct TreeNode *right; // на правого сына
void *value; // Значение в вершине
};
Здесь при описании полей parent, left, right используется тип struct TreeNode * -указатель на структуру TreeNode, определение которой еще не завершено. Возможны и более сложные комбинации.
Для доступа к полям структуры через указатель на структуру служит операция стрелочка, которая обозначается двумя символами −> (минус и знак больше). Пусть S — имя структуры, f — некоторое поле структуры S, p — указатель на структуру S. Тогда выражение p−>f обозначает поле f структуры S. Это выражение можно записать, используя операцию звездочка (доступ к объекту через указатель), p−>f эквивалентно (*p).f. В записи (*p).f круглые скобки вокруг выражения *p обязательны, поскольку приоритет операции точка выше, чем операции звездочка.