Var HeadOfStr: Pointer; ElemOfStr: DynStr;
Для создания цепочки выполняется последовательность операторов, связанная с начальным указателем.
new( ElemOfStr ); ElemOfStr^.Elem:= --; ElemOfStr^.NextElem:= nil; HeadOfStr:= ElemOfStr;
new( ElemOfStr^.NextElem ); ElemOfStr:= ElemOfStr^.NextElem; ElemOfStr^.Elem:= --;
Для создания каждого следующего элемента списка должна быть выполнена следующая последовательность операторов:
ElemOfStr^.NextElem:= nil; {признак конца списка}
Для поиска заданного элемента строки необходимо просмотреть последовательные звенья цепочки и сравнить значение информативного поля каждого из них с заданным. Этот процесс может окончиться при получении следующих результатов:
1. очередной элемент списка содержит заданный элемент; тогда значение функции v истинно, а также известно значение ссылки на это звено;
2. список исчерпан и заданное значение информационного поля элемента не найдено; при этом значение функции ложно.
function FoundElem(st: DynStr; Info: TypeOfElem; var Result: Pointer): Boolean;
var q: DynStr;
begin
FoundElem:= False;
Result:= nil;
q:= st^.NextElem;
while ( q <> nil ) and ( Result= nil ) do begin
if q^.Elem= Info then begin
FoundElem:= True
;
Result:= q
end;
q:= q^.NextElem
end
end;
Операция удаления элемента списка должна решать две задачи:
1. изменение ссылки предыдущего элемента так, чтобы она указывала на следующий;
2. уничтожение элемента с помощью функции dispose.
элемент в связующем поле того элемента, который должен предшествовать новому в списке.
procedure DelElem( ElemOfStr: DynStr );
var q, p: DynStr;
begin
if ElemOfStr^.NextElem <> nil then begin
q:= ElemOfStr^.NextElem;
p:= ElemOfStr^.NextElem;
ElemOfStr^.NextElem:= p^.NextElem;
dispose( q );
end
end;
Для вставки элемента в список необходимо выполнить следующую последовательность действий:
1. создать новый динамический объект, который будет представлять элемент списка;
2. инициализировать информационное поле нового элемента;
3. полю ссылки нового элемента присвоить значение поля ссылки того элемента, после которого
вставляется новый;
4. полю ссылки элемента, после которого вставляется новый присвоить значение ссылки на новый элемент.
Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом, требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка.
Динамические типы данных – деревья. Виды, структура, основные свойства. Применение.
БИНАРНЫЕ ДЕРЕВЬЯ
Цель работы: изучить теорию и научиться программировать бинарные
деревья.
Теоретические сведения
Связные списки не охватывают весь спектр возможных представлений
данных. Например, с их помощью сложно описать иерархические структуры
подобные каталогам и файлам или хранения информации генеалогического
древа. Для этого лучше подходит модель известная как бинарные деревья.
Графически бинарные деревья можно изобразить как последовательность
объектов, каждый из которых может быть связан с двумя последующими
Каждый объект бинарного дерева имеет два указателя: на «левый» и
«правый» вершины. Самый верхний уровень называется корнем дерева. Если
указатели объекта left и right равны NULL, то он называет листом дерева.
При описании структуры каталогов с помощью бинарного дерева можно
воспользоваться следующим правилом. Переход по «левым» указателям будет
означать список файлов, а переход по «правым» – список каталогов. Например,
для описания простой структуры (рис. 6), бинарное дерево будет иметь вид,
представленный на рис. 7.
Объекты, из которых состоит бинарное дерево удобно представить в виде
структур. Также как и в связных списках, первая структура будет описывать
данные, хранящиеся в вершинах дерева, а вторая представлять связи между
вершинами.
typedef struct tag_data {
char name[100];
} DATA;
typedef struct tag_tree {
DATA data;
struct tag_tree* left, *right;
} TREE;
TREE* root = NULL;
Для формирования дерева введем функцию add_node(), которая в качестве
аргументов будет принимать указатель на вершину дерева, к которому
добавляются новые вершины, имя вершины и тип вершины: левая или правая.
Кроме того, данная функция будет возвращать указатель на новую созданную
вершину.
TREE* add_node(TREE* node,char* name, TYPE type = LEFT)
{
TREE* new_node = (TREE *)malloc(sizeof(TREE));
if(type == LEFT && node != NULL) node->left = new_node;
else if(node != NULL) node->right = new_node;
strcpy(new_node->data.name,name);
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
Последний аргумент функции имеет тип TYPE, который удобно
определить как перечисляемый тип:
typedef enum tag_type {RIGHT, LEFT} TYPE;
и определить параметр по умолчанию LEFT.
Для отображения дерева целесообразно воспользоваться рекурсивными
функциями show_next(), которые вызываются из функции show_tree()
следующим образом:
void show_next(TREE* node,int off)
{
if(node != NULL)
{
for(int i=0;i < off;i++) putchar(' ');
printf("%s\n",node->data.name);
show_next(node->left,off);
show_next(node->right,off+1);
}
}
void show_tree()
{
if(root != NULL)
{
printf("%s\n",root->data.name);
show_next(root->left,0);
show_next(root->right,1);
}
}
Первый параметр функции show_next() служит для перемещения к
следующим вершинам дерева, а второй – для смещения при отображении строк
на экране монитора, принадлежащих разным вершинам. Рекурсия функций
show_next() выполняется до тех пор, пока указатель на левую или правую
вершину не станет равным NULL. В этом случае работа функции завершается,
и управление передается предыдущей вызываемой функции. Таким образом,
происходит отображение всего бинарного дерева.
При завершении программы необходимо удалить созданные объекты
дерева. Для этого также удобно воспользоваться рекурсивными функциями. По
аналогии введем рекурсивную функцию del_next(), и основную del_tree(), из
которой вызывается функция del_next(). Реализация этих функций приведена
ниже:
void del_next(TREE* node)
{
if(node != NULL)
{
del_next(node->left);
del_next(node->right);
printf("node %s - deleted\n",node->data.name);
free(node);
}
}
void del_tree()
{
if(root != NULL)
{
del_next(root->left);
del_next(root->right);
printf("node %s - deleted\n",root->data.name);
free(root);
}
}
Аргумент функции del_next() используется для перехода к следующим
вершинам дерева. В самой функции выполняется проверка: если следующая
вершина существует, т.е. указатель не равен NULL, то выполняется просмотр
дерева сначала по левой вершине, а затем по правой. При достижении листьев
дерева функции del_next() вызываются с аргументом NULL и не выполняют
никаких действий, поэтому программа переходит к функции printf(), которая
вывод на экран сообщение об имени удаляемой вершины, а затем вызывается
функция free() для освобождения памяти, занятой данным объектом. После
этого осуществляется переход к предыдущей функции del_next() и описанный
процесс повторяется до тех пор, пока не будут удалены все объекты кроме
корневого. Корень дерева удаляется непосредственно в функции del_tree(),
после чего можно говорить об удалении всего дерева.
Использование описанных функций в функции main() реализуются
следующим образом: