Курс лекций мдк 01. 02 «Прикладное программирование» пм 01 «Разработка программных модулей программного обеспечения для компьютерных систем»

string (char *st) – конструктор класса, в который мы передаём строку int len_str() – возвращает длину строки
char* sub_str(int i, int j) – копирует часть строки начиная с позиции i и до

позиции j

void print_str() – печатает строку

int kol_sim( char c) – определяет сколько раз встречается указанный символ в строке

Шаблон класса строки

class string {
private:

char *s;

public:
string (char *st);
~string();

int len_str();

char* sub_str(int i, int j);

void print_str();

int kol_sim( char c);

};

Тема «Создание класса ‘дерево’»


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

КОРЕНЬ

левое поддерево
правое поддерево

Ира

левый дочерний узел

Вика
правый дочерний узел

Наташа

Аня Дина Лена Света

NULL NULL NULL NULL NULL NULL NULL NULL
РИС. 10 Хранение слов в дереве двоичного поиска.

42
Идея состоит в том, что каждый узел имеет два дочерних узла: левый и правый. Упорядочение определяется тем, что элемент в левом узле предшествует элементу в родительском узле, а элемент в правом узле следует за элементом в родительском узле. Эта связь сохраняется для каждого узла, имеющего дочерние узлы. Более того, все элементы, которые могут проследить свою родословную к левому узлу родительского узла, содержат элементы, которые предшествуют родительскому элементу. А каждый элемент, ведущий свое происхождение от правого узла, содержит элементы, которые по порядку следуют за родительским элементом. Дерево, показанное на рисунке 3, хранит слова, упорядоченные этим способом. Верхняя часть дерева называется корнем. Дерево - иерархическая организация, а это означает, что данные организованы по рангам, или уровням. Если дерево двоичного поиска полностью заполнено, каждый уровень имеет вдвое больше узлов, чем уровень, расположенный выше него.

Каждый узел в дереве двоичного поиска сам является корнем узлов, исходящих из него, делая узел и его дочерние узлы поддеревом. Например, на рисунке 3 узлы, содержащие слова Вика, Аня, Дина, образуют левое поддерево всего дерева, а слово Света - правое поддерево поддерева Наташа-Лена-Света.

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

• 
  2 раза (Двоичный поиск).
  

Применим этот метод, присутствует ли слово Люда в дереве, показанном на рисунке. Сравнивая элемент Люда с элементом Ира (элемент корневого узла), видим, что элемент Люда, если присутствует, должен находится в правой половине дерева. Поэтому мы обращаемся к правому дочернему узлу и сравниваем Люда с элементом Наташа. В этом случае Люда предшествует узловому элементу, поэтому необходимо следовать за связью к левому узлу. Там мы находит элемент Лена, который предшествует искомому элементу Люда. Теперь необходимо следовать по правой ветви, но она пуста, следовательно, три сравнения показывают, что слово Люда отсутствует в дереве.

Абстрактный тип данных(ADT) - двоичное дерево.

Краткое неформальное описание этого типа:

43