. Смысловой оператор *, который применяет указатель к объекту, находящемуся в этой ячейке. Например, c=*pc; *pc=5; Особенно важным является то, что * и & имеют более высокий приоритет, чем арифметические операторы. При этом если используются несколько операторов указателя последовательно, то выражение обрабатывается справа налево.Аргументы указателя обладают возможностью обращаться к объектам функции из другой функции и изменять их. Автор также показывает, что с указателями можно проводить определенные арифметические операции и операции сравнения. Разрешены, конечно, только такие операции, которые ведут к осмысленным результатам. К указателям могут целочисленные значения прибавляться и вычитаться из них. К указателям могут также применять декремент. Можно указатели посредством операторов >,> =, <, <=, != и == сравнивать друг с другом. Всевозможные арифметические и логические операции, не описанные выше, не разрешены с указателями. 6.2 Указатель и массивКак отмечает автор в следующих параграфах, между указателями и полями существует ярко выраженная связь. Каждая операция, которая может применяться к элементам массива, может выражаться также и указателями. Программа, содержащая указатели выполняется гораздо быстрее. Однако понять смысл использования указателей гораздо тяжелее. Присваивание pa = *a [0] показывает, что pa указывает на 0-ой элемент массива a, т.е. pa содержит адрес a [0]. Вместо этого можно записать следующее: pa = a;К отдельным элементам массива можно обращаться 3 различными способами: · a [i] - i-ый элемент массива· * (pa+i) - указатель pa + i * (длина элементов массива a)· * (a+i) начало массива + i * (длина элементов a)Таким образом, каждое значение индекса массива может определяться также как значение смещения указателя и наоборот. Выражение pa + i не значит, что к pa значение i прибавляется, а i устанавливает смещение объекта от pa.Многомерные массивы можно задавать через указатели следующим образом: Matrix[1][2]=*(Matrix[1]+2)Matrix[1][2]=*(*(Matrix+1)+2)Matrix[1][2]=*(*Matrix+1*M+2)Так называемые структурные указатели имеют несколько другое обозначение:Указатель на структурную переменную -> название элементаНапример, punkt.px соответствует (*punkt)-> pxТак как структура указателей и массивов очень похожа, то далее автор объясняет как составить массив указателей.Массив указателей - это массив, состоящий из элементов-указателей. Вектор указателей определяется следующим образом: Тип исходных данных *Имя вектора[]Эту запись необходимо отличать от указателя на вектор: (*Имя вектора) []Компоненты вектора могут быть также адресами массивов. При этом такой массив указателей похож на многомерный массив. Например, char *Z[3], где происходит определение массива с 3 элементами, которые являются соответственно указателями типа char. При этом Z является указателем на массив с 3 указателями char.6.3 Указатель на функциюПомимо указателей на типы данных в C можно определять указатели и на функцию, которые можно использовать затем как переменные величины. Это может пригодиться для передачи значения функции в другую функцию.Указатель на функцию в C записывается следующим образом: Тип возврата (*Имя функции) (Аргументы функции)Здесь необходимо обратить особое внимание на то, что имя функции стоит в скобках. Если мы запишем без скобок *Имя функции (), то функция будет возвращать значение указателя. Функциональные указатели можно использовать в следующих случаях: · Как переменную-указатель, которая на функцию указывает. · Распределять значения функциональных указателей.· Определять массивы функциональных указателей. · Передавать указатель на функцию как параметр.· Получать указатель на функцию как возвращенное значение. Таким образом, профессор обращает также особенное внимание на широкое использование указателей при программировании в С. Это, в общем-то, оправданно довольно высоким быстродействием программ с указателями, но может привести к дополнительным ошибкам программирования из-за трудностей восприятия указателей. 7. Динамические структуры данныхВ этой главе автор рассматривает совершенно иной способ хранения данных в памяти.7.1 Динамическое управление памятьюДо сих пор речь шла только об объектах данных, для которых компилятор C предоставляет память и ее количество и величина должны быть определены к началу перевода программы в машинные коды. Такие объекты называют статическими. Работать с ними не всегда удобно, так как в процессе выполнения программы возникает необходимость увеличить размеры памяти, выделенной для этой структуры. Для борьбы с этим необходимо определять такие объекты с максимальной величиной. Наиболее приемлемым решением здесь будет применение динамически распределяемой памяти, т.е. определять объекты во время действия, т.е. динамично. Это решение позволяет оперативно освобождать большое количество памяти и избегать ее переполнения или напрасного расходования при статическом распределении.Динамические объекты определяются несколько по-другому. К ним обращаются не по имени, а только по их адресу. Эта адресация возникает при распределении памяти и назначается обычно с помощью переменных-указателей. Динамическое распределение памяти происходит посредством стандартных функций языка Cи:· void *malloc (size_t size) - занимает определенную связную область памяти и поставляет из нее начальный адрес. · void *calloc (size_t nobj, size_t size) - возвращает начальный адрес большой области; содержание этой области инициализируется значением 0. · void * realloc (void *ptr, size_t size) - изменение величины размещения блока памяти. · void free(void *) - используется для освобождения области памяти, которая больше не используется. · size_t sizeof (something) - определяет длину аргумента.При использовании указателей, которые служат в качестве значений, возвращаемых функцией, нужно следить, чтобы они не указывали на локальные объекты, которые исчезают после работы функции.7.2 Динамические структуры данныхДинамические структуры данных, как поясняет Юрген Плате в следующих параграфах, изменяют свою структуру и занятое ими пространство памяти во время выполнения программы. Они формируются из отдельных элементов, так называемых 'узлов', между которыми существуют определенные взаимосвязи. Речь в основном при этом идет о структурах, которые обозначаются как 'списки' или 'деревья'. Отношение отдельных узлов выстраиваются следующим образом: указатель одного узла указывает на место памяти «соседа». Самыми важными из этих структур данных являются: · Линейные списки - простые цепочные списки, двойные цепочные списки, специальные формы, буфер(FIFO), стек(LIFO).· Деревья - Бинарные деревья - 2 соседа, многодорожные деревья - больше чем 2 соседа. · Общие графы Линейные списки используют элементы, в которых указаны связанные сведения в форме строки символов. Элементы списков можно представить наглядно следующим образом: |
Информация элементов списка (строки символов, например, имя) | Указатель на следующий элемент | | |
При построении цепочного списка отдельные элементы списка выстраиваются в определенном порядке друг за другом: где символ электрической массы в конце списка указывает на NULL-указатель, который показывает конец списка, а root - указатель, показывающий происхождение списка (как правило, глобальная переменная)Еще одна важная динамическая структура, о которой рассказывает автор в этой главе - древовидная. Древовидные структуры играют очень важную роль в организации данных. Их используют в следующих случаях:· при построении родословного дерева; · как организационная структура предприятия · при распределении текста по главам, разделам, абзацам и т.д. Дерево определяется следующим образом: · Древовидные структуры имеют разветвления, которые могут исходить из начального элемента структуры и из самих разветвлений до тех пор, пока конечных точек не достигнут. · Элементы дерева называют узлами, причем начальный элемент называется корневым узлом, а конечные точки - листами. · Линии соединения двух узлов называется ребрами. Последовательность ребер от корня до любого узла называется путем. · Узлы, которые одинаково удалены от корня образуют уровень дерева. Общее число уровней указывает глубину дерева. · Максимальное количество наследников, которые имеет узел, определяют степень дерева. Дерево степени 2 - это бинарное дерево, наиболее важный случай. Древовидная структура имеет рекурсивную природу, так как наследники узла соответственно могут пониматься как корни деревьев. Бинарное дерево можно изобразить следующим образом:
Таким образом, динамические структуры данных, как показывает автор, являются наиболее эффективным способом распределения оперативной памяти и соответственно необходимо их использовать в программе, применяя указатели. 8. Избранные алгоритмы В этой главе Юрген Плате рассматривает наиболее распространенные и типичные виды алгоритмов, реализованные на Си. · Обработка строк символов(Strings)К простым операторам строк, которые задаются с помощью <ctype.h>, автор относит следующие операторы:|
islower(c) | Строчная буква | | isupper(c) | Прописная буква | | isalpha(c) | Строчная или прописная буква | | isdigit(c) | Десятичное число | | isalnum(c) | Строчная или прописная буква или десятичное число | | |
Наряду с простыми операторами имеется ряд комплексных команд для строковых символов. Прототипы находятся в стандартной библиотеке <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 сигналов. |
Имя | Значение | Функция | | SIGHUP | 1 | Выход из системы | | SIGINT | 2 | Прерывание пользователя (клавиши Ctrl+C) | | SIGQUIT | 3 | Запрос пользователя на окончание (клавиша CTRL + \) | | SIGFPE | 8 | Ошибка с плавающей запятой | | SIGKILL | 9 | Принудительное завершение процесса | | |
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, 4
|
