- •Тема 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.1.3.Структуры данных
Базовым строительным блоком структуры данных является ячейка, которая предназначена для хранения значения определенного базового или составного типа данных. Структуры данных создаются путем задания имен совокупностям (агрегатам) ячеек и (необязательно) интерпретации значения некоторых ячеек как представителей (указателей) других ячеек.
В качестве простейшего механизма агрегирования ячеек в большинстве языков программирования можно применять (одномерный) массив, т.е. последовательность ячеек определенного типа. Массив также можно рассматривать как отображение множества индексов в множество ячеек.
Другим общим механизмом агрегирования ячеек в языках программирования является структура (запись). Запись можно рассматривать как ячейку, состоящую из нескольких других ячеек (называемых полями), значения в которых могут быть разных типов. Записи часто группируются в массивы; тип данных определяется совокупностью типов полей записи.
Массивы и записи являются структурами с произвольным доступом, подразумевая под этим, что время доступа к компонентам массива или записи не зависит от значения индекса массива или указателя поля записи.
Третий метод агрегирования ячеек, который можно найти в языках программирования это файл. Файл, как и одномерный массив, является последовательностью значений определенного типа. Различают файлы прямого и последовательного доступа. В файле прямого доступа имеет индекс, т.е. все ячейки (компоненты) файла пронумерованы. Доступ может быть осуществлен к любой ячейки. Файл последовательного доступа не имеет индексов: его элементы доступны только в том порядке, в каком они были записаны в файл.
Достоинство агрегирования с помощью файла заключается в том, что файл не имеет ограничения на количество составляющих его элементов и это количество может изменяться во время выполнения программы.
В дополнение к средствам агрегирования ячеек в языках программирования можно использовать указатели и курсоры. Указатель — это ячейка, чье значение указывает на другую ячейку. При графическом представлении структуры данных в виде схемы тот факт, что ячейка А является указателем на ячейку В, показывается с помощью стрелки от ячейки А к ячейке В.
Курсор — это ячейка с целочисленным значением, используемая для указания на массив. В качестве способа указания курсор работает так же, как и указатель, но курсор можно использовать и в языках, которые не имеют явного типа указателя.
В схемах структур данных принято рисовать стрелку из ячейки курсора к ячейке, на которую указывает курсор. Иногда также указывают целое число в ячейке курсора, напоминая тем самым, что это не настоящий указатель.
Пример структуры данных представлен на рис.3.1. В данной структуре ячейка header содержит указатель на запись, состоящую из двух полей: cur и next. Поле cur содержит курсор, содержащий индекс логически первого элемента массива reclist (в данном случае четвертый элемент массива является логически первым, см. ниже). Поле next содержит указатель на аналогичную запись, в которой поле cur содержит курсор на логически последнюю запись массива reclist (в примере это вторая запись), а поле next содержит пустой указатель. Массив reclist состоит из четырех записей с индексами от 1 до 4. Каждая запись состоит из двух полей: data и next. Поле data содержит данные (в примере это символы a,b,c,d). Логический порядок элементов массива определяется значением курсора в поле next - курсор хранит индекс логически следующего элемента массива. Так за четвертым элементом следует первый, за первым - третий, за третьим - второй. Второй элемент массива логически последний, т.к. значение поля next второго элемента равно 0, т.е. отличается от любого значения индекса массива - 1,2,3 или 4.
Некоторые способы описания новых типов на языке Си, создания различных структур данных (массивов, файлов, структур) и испоьзования указателей будут рассмотрены в дальнейшем. Также будут рассмотрены различные способы предятавления данных в памяти ЭВМ.