Константные строки

Строки

Графы

Множества

Множества, графы

Обход дерева

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

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

Наиболее распространены два способа реализации множеств:

а) на основе бинарного дерева;

б) если размер множества ограничен, то наилучшим решением будет использование массива битов, в котором 1 соотвествует присутствию элемента со значением, соответствующим номеру бита в массиве; в этом случае сложность вставки, удаления и поиска =1, а расходы памяти составляют N/8 байт.

В математике графу дается следующее определение: графом называется пара множеств (V,E), где V - конечное множество элементов, называемых вершинами графа, а E - конечное множество упорядоченных пар e = (A,B), называемых дугами, где A и B - вершины. Говорят, что дуга e выходит из вершины A и входит в вершину B. Вершины А и В называют инцидентными дуге е, а дугу е - инцидентной вершинам А и В.

Структуру графа можно описать, сопоставив каждой вершине множество дуг, выходящих из неё, причем каждая дуга, выходящая из вершины, идентифицируется своим концом - номером вершины, в которую эта дуга входит. Такое описание называют S-графом (set-graph).

Пусть в графе N вершин, а класс Set реализует множество чисел от 0 до N-1, тогда S-граф можно представить следующим образом:

struct SGraph

{

Set vertex[N];

};

Для такого графа достаточно легко реализуется добавление и проверка принадлежности дуг. Задача подсчета количества дуг решается полным перебором всех вершин.

Другим распространенным способом представления графа является представление в виде матрицы смежности размера NxN. В этой матрице в элементе с индексом (i,j) указывается наличие дуги из i в j. Такое представление называют M-графом (matrix-graph). При таком представлении графа может быть указано не только наличие дуги, но и её вес. Недостатком такого представления является большой занимаемый объем памяти. Если число дуг невелико, то размер памяти, занимаемый M-графом будет сущесвенно больше, чем занимаемый S-графом.

struct MGraph

{

char vertex[N][N];

};

Если число исходящих из вершин дуг невелико, их удобно представлять в виде связанного списка. Такое представление называют L-графом (list-graph).

Это такие строки, под которые выделяется единая область памяти, определяемая исходя из длины строки. При переприсваивании значения строки память, как правило, перевыделяется.

Есть два основных представления константных строк.

1 В представлении с хранимой длиной дополнительно к самой строке хранится её длина (как правило, в первом байте). Такое представление достаточно удобно с точки зрения вычисления длины строки и обращения к её элементам, но неэффективно для представления строк длинее 255 символов. Это представление используется в языке Turbo Pascal и его потомках.

Пример: |6|'с'|'т'|'р'|'о'|'к'|'а'|

2. В представлении с символом-терминатором длинна строки отдельно не хранится, а сама строка завершается специальным символом. Если код такого символа 0, то её ещё называют строкой с завершающим нулем. При таком представлении нет ограничения на длину строки (кроме размера непрерывного свободного блока оперативной памяти, конечно), но вычисление длины строки имеет сложность O(N). Также, если по каким-то причинам символ-терминатор будет потерян, это приведет к неприятным последствиям. Такое представление используется в Си-подобных языках.

Дата добавления: 2014-01-05