- •Тема 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.3.Оператор множественного выбора switch
Оператор switch имеет следующий вид:
switch (выражение) {
case значение1:
действие1;
case значение2:
действие2;
. . .
default: // Необязательный фрагмент
фрагментN;
}
Выражение должно быть дискретного типа (целое число или указатель). Значения должны быть константами того же типа, что и выражение в заголовке. Оператор switch работает следующим образом:
сначала вычисляется значение выражения в заголовке switch;
затем осуществляется переход на метку "case L:", где константа L совпадает с вычисленным значением выражения в заголовке;
если такого значения нет среди меток внутри тела switch, то
если есть метка "default:", то осуществляется переход на нее;
если метка "default:" отсутствует, то осуществляется переход на оператор, следующий за switch.
Подчеркнем, что после перехода на метку "case L:" текст программы выполняется последовательно. Например, при выполнении фрагмента программы
int n, k;
n = 2;
switch (n) {
case 1:
k = 2;
case 2:
k = 4;
case 3:
k = 8;
}
переменной k будет присвоено значение 8, а не 4. Дело в том, что при переходе на метку "case 2:" будут выполнена сначала строка
k = 4;
и затем строка
k = 8;
что делает приведенный фрагмент совершенно бессмысленным. Чтобы исправить этот фрагмент, следует использовать оператор
break;
Этот оператор приводит к выходу из фигурных скобок, обрамляющих тело оператора switch. Приведенный фрагмент надо переписать следующим образом:
int n, k;
n = 2;
switch (n) {
case 1:
k = 2;
break;
case 2:
k = 4;
break;
case 3:
k = 8;
break;
}
В результате выполнения этого фрагмента переменной k будет присвоено значение 4. Если бы значение n равнялось 1, то k было бы присвоено значение 2, если n равнялось бы 3, то 8. Если n не равно ни 1, ни 2, ни 3, то k останется неопределенным.
3.4.4.Оператор цикла while
Цикл while является циклом с предусловием, т.е. условие проверяется перед выполнением тела цикла. В Си для определения цикла while используется следующаий оператор:
while (условие)
действие;
Сначала проверяется условие. Если оно истинно, то выполняется действие. Затем снова проверяется условие; если оно истинно, то снова повторяется действие, и т.д. Цикл завершается, когда условие становится ложным. Пример:
int n, p;
. . .
p = 1;
while (2*p <= n)
p *= 2;
В результате выполнения этого фрагмента в переменной p будет вычислена максимальная степень двойки, не превосходящая целого положительного числа n.
Если условие ложно с самого начала, то действие не выполняется ни разу.
Тело цикла может состоять из одного или нескольких операторов. В последнем случае их надо заключить в фигурные скобки.
3.4.5.Оператор цикла for
Цикл for как цикл while является циклом с предусловием. В Си для определения цикла for используется следующаий оператор:
for (инициализация; условие продолжения; итератор)
действие;
Инициализация выполняется один раз перед первой проверкой условия продолжения и первым выполнением тела цикла. Условие продолжения проверяется перед каждым выполнением тела цикла. Если условие истинно, то выполняется действие, иначе цикл завершается. Итератор выполняется после каждого выполнения тела цикла (перед следующей проверкой условия продолжения).
Рассмотрим пример суммирования массива с использованием цикла for:
double a[100]; // Массив a содержит не более 100 эл-тов
int n; // Реальная длина массива a (n <= 100)
double sum; // Переменная для суммы эл-тов массива
int i; // Переменная цикла
. . .
sum = 0.0;
for (i = 0; i < n; ++i)
sum += a[i]; // Увеличиваем сумму на a[i]
Здесь целочисленная переменная i используется в качестве переменной цикла. В операторе инициализации переменной i присваивается значение 0. Условием продолжения цикла является условие i<n. Итератор ++i увеличивает переменную i на единицу. Таким образом, переменная i последовательно принимает значения 0, 1, 2,..., n-1. Для каждого значения i выполняется оператор sum += a[i];.
В большинстве других языков программирования арифметический цикл жестко связан с использованием переменной цикла, которая должна принимать значения из арифметической прогрессии. В Си это не так, здесь инициализация, условие продолжения и итератор могут быть произвольными выражениями, что обеспечивает гораздо большую гибкость программы. Конструкцию цикла for можно реализовать с помощью цикла while:
Например, фрагмент с суммированием массива
for (i=0; i < n; ++i)
sum += a[i];
реализуется с использованием цикла while следующим образом:
i = 0;
while (i < n) {
sum += a[i];
++i;
}
Кроме того, что в цикле for в качестве инициализации и итератора можно использовать любые выражения, можно выполнить несколько действий при инициализации или в итераторе. Для этого язык Си предоставляет операцию "запятая", которая позволяет объединить несколько выражений в одно. Например, фрагмент суммирования массива
sum = 0.0;
for (i = 0; i < n; ++i)
sum += a[i];
можно переписать следующим образом:
for (sum = 0.0, i = 0; i < n; sum += a[i], ++i);
Здесь тело цикла вообще пустое, все действия вынесены в заголовок цикла. Лучше избегать такого стиля программирования: он ничего не добавляет в смысле эффективности готовой программы, но делает текст менее понятным и, таким образом, увеличивает вероятность ошибок.