Алгоритмы и структуры данных. Программирование в Cи (стр. 5 из 7)
· при передаче параметра
· при обработке массивов
· для обработки текста
· для доступа к специальным ячейкам памяти
Обозначаются указатели следующим образом: int *pc; , т.е. переменная pc является указателем тип int.
При этом используют преимущественно два типа указателей:
1. Оператор адреса &, который применяется к объекту, доставляющему адрес этого объекта. Например, pc=&c.
2. Смысловой оператор *, который применяет указатель к объекту, находящемуся в этой ячейке. Например, 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 - это бинарное дерево, наиболее важный случай.Древовидная структура имеет рекурсивную природу, так как наследники узла соответственно могут пониматься как корни деревьев. Бинарное дерево можно изобразить следующим образом:
Таким образом, динамические структуры данных, как показывает автор, являются наиболее эффективным способом распределения оперативной памяти и соответственно необходимо их использовать в программе, применяя указатели.
В этой главе Юрген Плате рассматривает наиболее распространенные и типичные виды алгоритмов, реализованные на Си.
· Обработка строк символов(Strings)
К простым операторам строк, которые задаются с помощью <ctype.h>, автор относит следующие операторы: