Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Таким образом, динамические структуры данных, как показывает автор, являются наиболее эффективным способом распределения оперативной памяти и соответственно необходимо их использовать в программе, применяя указатели.

8. Избранные алгоритмы

В этой главе Юрген Плате рассматривает наиболее распространенные и типичные виды алгоритмов, реализованные на Си.

• Обработка строк символов(Strings)

К простым операторам строк, которые задаются с помощью , автор относит следующие операторы:

Наряду с простыми операторами имеется ряд комплексных команд для строковых символов. Прототипы находятся в стандартной библиотеке .

• strcat (char *a, char *b) – Последовательность символов b прибавляется к a.

• strncat ( char *a , char *b , int n ) – прибавляются к а n символов b.

• strcpy ( char *a , char *b ) – строка b копируется после a

• strncpy ( char *a , char *b , int n ) – n символов строки b копируется после a

• int n = strlen ( char *a ) – возвращает длину строки

• Арифметика дат

В этом параграфе автором собраны достаточно простые алгоритмы, связанные с использованием даты и времени.

В первую очередь автор рассказывает о юлианском датоисчислении. При этом не имелось бы никакой проблемы 2000 года. Вместо этого дата сохранялась в компьютерах как строка символов (TTMMJJ) и это привело к тому, чтобы после 99 шел год 00. Причина такого датоисчисления была связана с необходимостью экономии памяти.

Алгоритм расчета даты по Юлианскому стилю можно представить следующим образом:

Y = год, М = месяц, D = день

Если M> 2, то Y и М остаются неизменными. Если М = 1 или М = 2, то

Y = Y - 1

М = М + 13

Для нахождения текущей даты имеем:

JD = INT (365 .25 * (Y + 4 716)) + INT (3 0.6001 * (М + 1)) + D + B - 1524.5

• Числовой тип

Здесь профессор приводит некоторые алгоритмы, которые работают с числовыми данными.

Достаточно часто в алгоритмах необходимо определить является ли число простым. Чтобы это устанавить, необходимо делить число X на числами, которые больше 2 и меньше X. Если число ни на какое из них не делится, оно должно быть простым.

Затем автор рассказывает о нахождении нулей функций. Для этого применяют методы аппроксимации. Если задан интервал (a;b), на котором определена функция, то необходимо каждый раз делить интервал пополам и проверять где находится нуль. Повторяется действие до тех пор, пока интервал не станет достаточно мал.

Еще один типичный пример рассмотрен в этом параграфе автором – решение систем линейных уравнений методом Гаусса.

Пусть задана система уравнений вида Ax = b. Считается, что если k-е уравнение будет решено, то:

При решении методом Гаусса исходные уравнения преобразуют таким образом, что матрица коэффициентов содержит нули ниже главных диагоналей. Для этого используются операции сложения и вычитания уравнений, а также умножения их на число. При этом система принимает вид:

• Статистическая мера

В этом параграфе автор затрагивает статистический метод обработки информации и построение программ на основе этого метода. Статистика обрабатывает эмпирические числа и на основании этой обработки делаются прогнозы и принимаются решения.

Методом математической статистики анализируют массовые явления. При этом обнаруживаются определенные закономерности, которые нельзя формулировать для единичных явлений. Лучшим представлением статистических данных является графическое изображение. В качестве примера изображено распределение частоты гауссового нормального распределения.

Наряду с функцией частоты основную совокупность данных можно охарактеризовать с помощью среднего значения и дисперсии. Арифметическое среднее значение определяется так:

а дисперсия следующим образом:

При работе с измерительными величинами часто необходимо установить связь между отдельными точками. Здесь помогают такие операции как интерполяция и регрессия.

При линейной интерполяции выполняют аппроксимацию функциональных значений f (x) на промежутке (x₁,x₂) из известных значений f (x₁) и f (x₂).

Поиск и сортировка

В этом параграфе автор рассказывает о наиболее распространенных в программировании операций с данными – поиске и сортировке.

Сортировка значительно облегчает работы с данными в программировании. Следствием таких операций является более эффективный поиск в программе.

Различают несколько основных методов поиска, зависящих от типа данных:

1. Табличный поиск осуществляется по индексу данных в таблице.

2. Линейный поиск предполагает просмотр всех элементов по порядку до нахождения нужного.

3. Бинарный поиск осуществляется после проведения сортировки, суть которого состоит в проверке среднего элемента последовательности и определения по ключу в какую сторону двигаться для нахождения нужного элемента.

Сортировка является одной из самых важных операций с данными. Профессор приводит такое определение сортировки:

Сортировка - процесс упорядочения заданного множества объектов в определенном порядке. Выделяют следующие виды алгоритмов сортировки:

• Пузырьковая сортировка. В первом проходе массив обрабатывается с конца до начала и сравнивается при каждом шаге текущий компонент со следующим. Если нижний компонент меньше чем верхний, то они меняются местами. Это происходит до тех пор, пока последовательность не будет возрастающей или убывающей.

• Сортировка выбором. В этом случае берут первый элемент последовательности и ищут самый маленький элемент, с которым его и меняют местами. Затем начинают со второго и его меняют на самый маленький в оставшейся последовательности и т.д.

• Сортировка вставкой. При этом предполагается, что часть последовательности уже отсортирована. Элементы не сортированной части по порядку перемещают в сортированную до тех пор пока элемент не станет больше или равным впереди идущего элемента.

• Сортировка методом Шелла. Сначала массив разделяется на несколько групп, между членами которых имеется равное расстояние. Пусть, например, используется расстояние 3, тогда компоненты 1, 4, 7 принадлежат одной группе, так же как и 2, 5, 8..., 3, 6, 9... и т.д. эти группы упорядочиваются в отдельности, затем расстояние уменьшается и действия повторяется до расстояния 1.

• Быстрая сортировка. Выбирают любой компонент массива - к примеру, средний - и массив делится на 2 группы: одна с компонентами, которые больше чем выбранный, а другая с меньшими. Эти обе группы делятся вновь по заданному алгоритму. Таким образом, получается рекурсивная функция, которая достаточно быстро сортирует данные.

• Реализация множеств

Автор в этой главе упоминает о множествах – достаточно важной структуре программирования. Другие языки программирования (например, Паскаль) имеют тип данных множества. В языке C такого не имеется.

Однако множества возможно представить с помощью битовых массивов. Элементы массива нумеруются, и каждый элемент множества представляет собой 1 бит. Если соответствующий бит установлен (1), то элемент содержится в множестве, если бит равен 0, соответствующий элемент не содержится в множестве. Пересечение и объединение можно использовать с помощью логических операторов UND и ODER. Так как переменные величины типа int или char только относительно маленькие множества могут представлять, то получить к ним доступ можно с помощью указателя на битовый массив.

8.2 Экскурс: процессы или сигналы

В этом параграфе профессор несколько уходит от программирования и пытается объяснить, как выполняются программы в операционной системе на примере ОС Linux.

Linux - это многозадачная операционная система, которая может выполнять несколько заданий одновременно. При этом каждая из этих программ ведет себя таким образом, как если бы она была единственной, запускаемой в данный момент на компьютере.

Если под Linux запускается программа, она получает однозначный идентификационный номер ID, который лежит в диапазоне между 1 и 32 767. Посредством этого номера ОС может идентифицировать находящиеся в памяти программы и получить доступ к ним. Для работы с ID используются две функции, которые определены в файле заголовка unistd.h:

1. pid_t getpid(void) – возвращает PID

2. pid_t getppid(void) – возвращает родителей PID-процесса.

Следующий важный элемент для операционных систем - сигналы, которые предоставляют возможность запускать новые процессы или заменять процесс другим процессом. Сигналы - это сообщения, которые посылаются операционной системой в текущую программу для каких-либо действий. Некоторые сигналы вызываются в результате ошибки в программе, другие вызываются по требованию пользователя.

В таблице автор приводит список чаще всего подаваемых Unix сигналов.

9. Стиль программирования. Ловушки

9.1 Стиль программирования в C

Существует такое понятие в программировании как стиль программирования. Для различных языков программирования он разный. Автор пытается дать рекомендации для программирования в C. Из многочисленных советов автора можно выделить следующие, самые общие:

• Используйте *define для символьных констант.

• Используйте исключительно прописные буквы для констант и смешанную форму записи или символ подчеркивания для переменных и имен функций.

• Используйте функции, чтобы Ваши программы были короткими, ясными и соблюдался принцип модульности. Каждый шаг необходимо комментировать.

• Язык C предусматривает только минимальную проверку ошибок в программе. Это значительно ускоряет работу программы и допускает некоторые вольности в программировании. Но, тем не менее, программисту необходимо проверять некоторые значения в программе с помощью различных структур.

• При написании выражений, особенно условий, используйте скобки, чтобы указать последовательность и приоритет оценки.

• Выравнивайте команды таким образом, что легко определялась структура программы, состоящая из отдельных блоков.

• Используйте массивы с указателями из строк символов вместо двумерных массивов, если строки символов имеют различную длину.

• По возможности используйте динамические структуры данных

9.2 Ловушки в C

В заключении профессор предостерегает нас от наиболее часто встречающихся ошибок программирования в C:

• Чтобы избежать ошибок memory fault(недостаток памяти) необходимо в программе проверять границы получаемых строковых величин.

• Одна из частых ошибок – постановка точки с запятой в конце команды. Компилятор C замечает это только в следующей строке и указывает затем на эту ошибку.

• При написании условной структуры часто не ясно, к какому IF принадлежит ELSE. Например,

if (i > j)

Характеристики

Список файлов реферата