- •Тема 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.Алгоритм расчета резервов времени
- •Расчет резервов времени
- •Вопросы для повторения
7.1.2.Поиск элемента в упорядоченном массиве.
Поиск элемента в упорядоченном массиве может быть осуществлен с помощью алгоритма бинарного поиска. Принцип, лежащий в основе алгоритма бинарного поиска (и некоторых других алгоритмов), состоит в том, что иногда удаётся последовательно уменьшать объём задачи до такой степени, что её решение, в конце концов, становится тривиальным. Главный шаг при бинарном поиске – взять элемент из середины массива и, если он не равен искомому, то в зависимости от его значения исключить из рассмотрения ту или другую половину массива. Повторное выполнение этого шага быстро сокращает размер области поиска.
Алгоритм бинарного поиска для массива, упорядоченного по возрастанию.
1.Определить середину массива.
2.Если элемент, находящийся в середине массива, совпадает с искомым, то поиск завершен.
3.Если элемент, находящийся в середине массива, больше искомого, применить бинарный поиск к первой половине массива.
4.Если элемент, находящийся в середине массива, меньше искомого, бинарный поиск необходимо применить ко второй половине массива.
5. Пункт 1-4 повторять, пока размер области поиска не уменьшается до нуля. Если это произойдет – ключа в массиве нет.
Алгоритм бинарного поиска для массива, упорядоченного по убыванию, реализуйте самостоятельно.
Рассмотренный алгоритм бинарного поиска представлен блок-схемой на рис.7.2.
Нетрудно заметить, что в худшем случае (искомого элемента в массиве нет) алгоритм бинарного поиска сделает не более O(log2N) шагов. Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не более O(log2N) таких уменьшений.
7.1.3.Фонетический поиск
Под фонетическим поиском понимается поиск по нечеткому значению ключа, если в качестве ключа используется фамилия, так как она воспринимается на слух. Наибольшее распространение при организации фонетического поиска получил метод "Soundex" [4]. Метод создает для фамилии ключ, причём похожим фамилиям или неверным написаньям одной фамилии будет соответствовать один ключ. Поэтому, если оператор городской справки, кассир в банке, авиадиспетчер или кто-либо другой наберёт вашу фамилию неверно, доступ к вашей записи в базе данных все равно будет получен, так как поиск ведётся по ключам.
Первоначально метод "Soundex" развит Маргарет К. Оуделли и Робертом К. Расселом [см.U.S.Patents 1261167 (1918), 1435663 (1922)]. Метод "Soundex" заключеется в следующем:
1.Оставить первую букву фамилии; все буквы а,е,h,i,о,u,w,у, стоящие на других местах, вычеркнуть.
2.Оставшимся буквам (кроме первой) присвоить следующие значения:
b, f, p, v= 1;
l= 4;
c, g, j, k, q, s, x, z= 2;
m, n=5;
d, t=3;
r= 0.
3.Если в исходной фамилии рядом стояли несколько букв с одинаковыми кодами, пренебречь всеми, кроме первой из этой группы.
4.Дописывая в случае надобности нули или опуская лишние цифры, преобразовать полученное выражение в форму "буква, цифра, цифра, цифра".
Например, фамилии Euler, Gauss, Hilbert, Knuth, Lloyd и Lukasiewicz имеют коды соответственно Е460, G200, H416, K530, L300, L222.
Разумеется, такая система собирает вместе не только родственные, но и достаточно различные фамилии. Приведенные выше шесть кодов могли быть получены из фамилий Ellery, Ghosh, Heilbronn, Kant, Ladd и Lissajous. С другой стороны, такие родственные имена, как Rogers и Rodgers, Sinclair и St.Clair или Tchebysheff и Chebyshev, имеют разную кодировку. Но, вообще говоря, система "Soundex" намного увеличивает вероятность обнаружить имя под одной из его масок [4-6].
Несмотря на свою простоту, метод "Soundex" дает достаточно хорошие результаты фонетического поиска. Функции, реализующие данный метод встречаются во многих СУБД и других инструментальных средствах. Однако сам метод и большинство инструментальных средств являются англоязычными. Для фонетического поиска русских фамилий требуется модифицировать метод "Soundex" или разработать метод аналогичный по функциональным возможностям.