При построении цепочного списка отдельные элементы списка выстраиваются в определенном порядке друг за другом:

где символ электрической массы в конце списка указывает на NULL-указатель, который показывает конец списка, а root - указатель, показывающий происхождение списка (как правило, глобальная переменная)

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

· при построении родословного дерева;

· как организационная структура предприятия

· при распределении текста по главам, разделам, абзацам и т.д.

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

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

· Элементы дерева называют узлами, причем начальный элемент называется корневым узлом, а конечные точки - листами.

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

· Узлы, которые одинаково удалены от корня образуют уровень дерева. Общее число уровней указывает глубину дерева.

· Максимальное количество наследников, которые имеет узел, определяют степень дерева. Дерево степени 2 - это бинарное дерево, наиболее важный случай.

Древовидная структура имеет рекурсивную природу, так как наследники узла соответственно могут пониматься как корни деревьев. Бинарное дерево можно изобразить следующим образом:

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

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

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

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

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

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

· 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) на промежутке (x1,x2) из известных значений f (x1) и f (x2).

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

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

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

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

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)

if (k < 100)

tuwas();

else

tuwasanderes();

При этом получается, что ELSE принадлежит первому IF. На самом деле она принадлежит всегда ближайшему IF.

§ Если объявляется переменная double d=3/4, то в результате получается 0, так как 3 и 4 - целые числа. Для того, чтобы получить результат необходимо записать 3.0 и 4.0

§ NULL определяется только #define NULL. Указатели не могут быть никакими целыми значениями. Указатель должен быть инициализирован допустимым адресом памяти.

Заключение

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

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

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

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

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

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

Стоит обратить внимание на то, что автор периодически отвлекается от процесса программирования и рассматривает общие информатические вопросы каким-то образом связанные с темой (системы счисления, процессы в операционной системе). Это дает возможность утверждать, что данный труд является не только обучающим пособием по программированию, но и по информатике в целом.

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

Страницы: 1, 2, 3