- •Тема 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.3.9.Операции с указателями. Указатели и массивы
Кроме рассмотренных двух унарных операций * и &, с указателями можно выполнять следующие операции:
сложение или вычитание указателя и целого числа, результат - указатель;
увеличение или уменьшение переменной типа указатель, что эквивалентно прибавлению или вычитанию единицы;
вычитание двух указателей, результат - целое число.
Прибавление к указателю p целого числа n означает увеличение адреса, который содержится в переменной p, на суммарный размер n элементов того типа, на который ссылается указатель. Другими словами значение указателя при прибавлении к нему целого числа n увеличивается на произведение n на количество байтов, занимаемое одним элементом того типа, на который ссылается указатель. Аналогичный смысл имеет вычитание целого числа n из указателя.
Разность двух указателей - это количество элементов данного типа, которое умещается между двумя адресами. Результатом вычитания указателей является целое число. Физически оно вычисляется как разность значений двух адресов, деленная на размер одного элемента заданного типа.
Отметим, что указатели нельзя складывать. В отличие от разности указателей, операция сложения указателей (т.е. сложения адресов памяти) не имеет смысла.
Напомним, что имя массива a является указателем на его первый элемент, т.е. выражения a и &(a[0]) эквивалентны. Для массива a операция сложения указателя a и целого числа n имеет смысл сдвига указателя a на n элементов вправо, если считать, что индексы элементов массива возрастают слева направо. Аналогично вычитание целого числа n из указателя a означает сдвиг указателя a влево на n элементов.
Учитывая арифметику указателей, получаем эквивалентность следующих выражений: a[i] и *(a+i). Действительно, при прибавлении к a целого числа i происходит сдвиг на i элементов вправо. Поскольку имя массива является адресом его начального элемента, получается адрес i-го элемента массива a. Применяя операцию звездочка *, получаем сам элемент a[i]. Точно так же эквивалентны выражения &(a[i]) и a+i.
Эта особенность арифметики указателей позволяет вообще не использовать квадратные скобки, т.е. обращение к элементу массива; вместо этого можно использовать указатели и операцию звездочка *.
Таким образом, выбор между массивами и указателями - это выбор между двумя эквивалентными способами записи программ. Указатели, возможно, нравятся системным программистам, которые привыкли к работе с адресами объектов. Массивы больше отвечают традиционному стилю.
3.3.10.Операция приведения типа
Операция приведения типа используется, когда значение одного типа преобразуется к другому типу. Операция обозначается именем типа, заключенным в круглые скобки; она записывается перед ее единственным аргументом.
Рассмотрим два примера. Пусть требуется преобразовать целое число к вещественному типу. В примере значение целой переменной n приводится к вещественному типу и присваивается вещественной переменной x:
double x;
int n;
. . .
x = (double) n; // Операция приведения к типу double
В данном случае никакой потери информации не происходит, поэтому такое приведение допустимо и по умолчанию:
x = n; // Эквивалентно x = (double) n;
Во следующем примере вещественное значение преобразуется к целому типу. При этом дробная часть вещественного числа отбрасывается, а знак числа сохраняется:
double x, y;
int n, k;
. . .
x = 3.7;
y = -1.5;
n = (int) x; // n присваивается значение 3
k = (int) y; // k присваивается значение -1
В результате выполнения операции приведения вещественного числа к целому типу происходит отбрасывание дробной части числа, т.е. потеря информации. Поэтому, если использовать операцию приведения типа неявно (т.е. в результате простого присваивания целой переменной вещественного значения), например,
double x; int n;
. . .
n = x; // неявное приведение вещественного типа к целому
то компилятор обязательно выдаст предупреждение или ошибку. Когда используется явное приведение типа, компилятору сообщается, что это не случайная ошибка, а намеренное приведение вещественного значения к целому типу, при котором дробная часть отбрасывается. При этом компилятор никаких предупреждений не выдает.
Операция приведения типа чаще всего используется для преобразования указателей (см. разд. 1.8).