СтатьиПрограммированиеDelphi

Компонент TTreeview и динамические структуры

Автор: Blacksus

В данной статье будет рассмотрено хранение данных при помощи динамической структуры и ее наглядное представление при помощи компонента TTreeview. Эта статья может помочь тем, кто собирается использовать в своей программе различные списки, будь то список файлов или что-либо иное.

Во-первых, что такое динамическая структура? Можно сказать, что это набор данных, который формируется по ходу выполнения программы, т.е. в отличие от статических данных, этот набор ограничен только количеством памяти на компьютере, и его размер не нужно задавать заранее. Мы будем рассматривать линейную динамическую структуру, т.к. она наиболее проста в работе и отлично подходит для вывода данных с помощью TTreeview. Эта структура напоминает одномерный массив, но она намного удобнее в работе. И перемещение данных, в ней, не занимает такое количество времени, как в массиве, особенно если данных очень много. При использовании обычного массива, статического или динамического, после удаления любого элемента, не находящегося в конце массива, нужно будет перемещать элементы находящиеся ниже этого элемента, чтобы в нем не было дырок от удаленных элементов. То же самое придется делать и при вставке элемента. При использовании динамической структуры, удаление или вставка элемента в любое место массива занимает столько же процессорного времени, сколько заняла бы эта операция для последнего элемента. Т.е. ничего перемещать не надо.

Для примера возьмем структуру, содержащую записи. Тип этой структуры описывается следующим образом:

type list = record //Запись может содержать произвольные данные и любое их количество a, b, c, d, e, f: string; //Полей может быть любое количество end; ref = ^z; z = record el: list; //элемент next: ref; // ссылка на следующий жлемент структуры end;

Принцип структуры можно наглядно увидеть на рисунке 1.

Рисунок 1 - динамическая структура

Ссылка "Link" всегда указывает на первый элемент структуры. Сама структура состоит из 2-х ячеек. Первая - это ссылка, которая содержит в себе адрес следующего элемента (в нашем примере $0000, $0001, $5945), вторая содержит в себе произвольные данные, в нашем случае это запись (record), которая содержит в себе еще 6 ячеек.

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

На рисунке 2 вы можете увидеть внешний вид примера.

Рисунок 2 - внешний вид примера

Глобальные переменные

var Form1: TForm1; reflist: ref;

Для начала, при запуске программы, нужно инициализировать структуру. Эта процедура представлена ниже:

procedure TForm1.FormCreate(Sender: TObject); var cur: ref; begin new(reflist); cur := reflist; cur^.next := nil; end;

Ниже представлены две функции, которые осуществляют поиск по структуре и определение уровня элемента. Они используются в процедуре добавления элемента.

function TForm1.Search(num:cardinal):ref; //Функция поиска заданного элемента var i: cardinal; cur: ref; begin cur := reflist;//начинаем поиск с первого элемента for i := 1 to num do cur := cur^.next; //перебираем элементы, пока не доходим до нужного номера Result := cur; end; function Tform1.Level(node:TTreenode):integer; //Функция определения уровня элемента begin Result := 0;//по-умолчанию 0 уровень while node.Parent <> nil do begin node := node.Parent; //передвигаемся на 1 уровень выше Inc(Result);//и инкрементируем переменную результата end; end;

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

procedure TForm1.Button1Click(Sender: TObject); var p: integer; newnode, tempnode: TTreeNode; next, cur: ref; begin if treeview1.Selected = nil then //Если нет еще ни одной записи begin cur := reflist; //текущий элемент - начало структуры cur^.next := nil; //следующий элемент - nil cur^.el.a := Edit1.text;//присваивание полям записи значений из полей в программе cur^.el.b := Edit2.text; cur^.el.c := Edit3.Text; cur^.el.d := Edit4.text; cur^.el.e := Edit5.Text; Treeview1.Items.Add(Treeview1.TopItem,cur^.el.a);//на экран, в компонент TTreeview, выводится содержимое поля "a" cur^.el.f := IntToStr(Level(newnode));//полю "f" присваивается номер уровня exit; end; if checkbox1.Checked then //Если нужно создать подпункт begin if Treeview1.Selected.GetLastChild <> nil then //если этот пункт уже имеет подпункты cur := Search(Treeview1.Selected.GetLastChild.AbsoluteIndex) //поиск последнего подпункта этого пункта else cur := Search(Treeview1.Selected.AbsoluteIndex); //иначе поиск самого пункта next := cur^.next; //фиксирование адреса следующего элемента new(cur^.next); //создание нового элемента cur^.next^.next := next; //скрепление текущего элемента и следующего cur^.next^.el.a := Edit1.text; cur^.next^.el.b := Edit2.text; cur^.next^.el.c := Edit3.Text; cur^.next^.el.d := Edit4.text; cur^.next^.el.e := Edit5.Text; newnode := Treeview1.Items.AddChild(Treeview1.selected, cur^.next^.el.a);//на экран, в компонент TTreeview, выводится содержимое поля "a" cur^.next^.el.f := IntToStr(Level(newnode));//полю "f" присваивается номер уровня end else //Если не нужно создавать подпункт begin newnode := Treeview1.Selected; //фиксирование адреса выделенного элемента if newnode.getNextSibling=nil then //Если на этом уровне нет следующей записи begin tempnode := Treeview1.Selected; //временна переменная, с которой начнется поиск while tempnode.HasChildren do tempnode := tempnode.GetLastChild; //поиск последнего подпункта на последнем уровне, это нужно для того, чтобы не нарушить последовательность цепочки cur := Search(tempnode.AbsoluteIndex); next := cur^.next; new(cur^.next); cur^.next^.next := next; cur^.next^.el.a := Edit1.text; cur^.next^.el.b := Edit2.text; cur^.next^.el.c := Edit3.Text; cur^.next^.el.d := Edit4.text; cur^.next^.el.e := Edit5.Text; newnode := Treeview1.Items.Add(newnode,cur^.next^.el.a); cur^.next^.el.f := IntToStr(Level(newnode)); end else //Если на этом уровне есть следующие записи begin newnode := newnode.GetNextSibling; cur := Search(newnode.AbsoluteIndex-1); next := cur^.next; new(cur^.next); cur^.next^.next := next; cur^.next^.el.a := Edit1.text; cur^.next^.el.b := Edit2.text; cur^.next^.el.c := Edit3.Text; cur^.next^.el.d := Edit4.text; cur^.next^.el.e := Edit5.Text; newnode := Treeview1.Items.Insert(newnode,cur^.next^.el.a); cur^.next^.el.f := IntToStr(Level(newnode)); end; end; end;

В этой процедуре edit1-edit5 некоторые поля, в роли этих полей может выступать любое строковое значение. Сheckbox1 - показывает, отмечен ли пункт "Подпункт", это нужно для того, чтобы создавать вложенные записи. Процедура search нужна для поиска текущей записи в структуре, она описана выше. Процедура level узнает, на каком уровне находится элемент, она описана выше. Это нужно для того, что правильно выстроить структуру на экране при чтении из файла.
В самом начале процедура проверяет, есть ли хоть одна запись в структуре, если нет, то производится запись и выход из процедуры.
Если были произведены уже какие-либо записи, то программа проверяет, отмечен ли пункт "Подпункт", если он отмечен, то запись производится как подпункт, т.е. на следующем уровне. Если этот пункт не отмечен, то запись будет добавлена на этом же уровне.
Далее процедура проверяет, есть следующая за ней запись на этом уровне.

Все эти проверки обусловлены тем, что в различных условиях процедура должна по-разному добавлять данные в TTreeview.

Возможно, у Вас возникнет вопрос, как же можно использовать линейную структуру для работы с многоуровневым списком. Дело в том, что компонент TTreeview позволяет использовать сквозную нумерацию элементов. Т.е., если посмотреть на рисунок 2, то на 0 уровне находится 3 объекта, на 1 уровне 3 объекта, и на 2 уровне 2 объекта. Последний элемент находится на 0 уровне и в пределах уровня имеет номер 3, но если использовать сквозную нумерацию, то он будет иметь номер 8. Поэтому в структуре нам не нужно отображать уровни, достаточно линейности.

Следующая процедура служит для удаления выбранного элемента:

procedure TForm1.Button2Click(Sender: TObject); var select, p: integer; child: TTreenode; last, cut, prev, temp: ref; begin child := Treeview1.Selected; //фиксирование текущего элемента while child.HasChildren do child := child.GetLastChild; //поиск последнего подпункта на последнем уровне last := Search(child.AbsoluteIndex); //поиск адреса последнего элемента в структруе temp := Search(Treeview1.Selected.AbsoluteIndex); //поиск адреса текущего элемента в структуре prev := nil; //предполагаем,что предыдущего элемента нет if Treeview1.Selected.AbsoluteIndex<>0 then prev := search(Treeview1.Selected.AbsoluteIndex-1); //поиск адреса предыдущего элемента в структуре repeat cut := temp; //фиксируем адрес текущего элемента в структуре temp := temp^.next; //фиксируем адрес следующего элемента dispose(cut); //удаляем элемент until temp = last^.next; //пока не дойдем до адреса следующего за удаляемым элемента if prev <> nil then prev.next := temp else reflist := temp; Treeview1.selected.Delete; //удаляем элемент с экрана из TTreeview end;

Данная процедура находит выделенный объект в структуре и удаляет его. Но простого удаления мало, этой операцией вы как бы удаляете одно звено из цепи, но для нормальной работы нужно скрепить 2 звена, которые держались за удаляемый элемент. Именно этим и занимается данная процедура. Сначала она находит элементы, которые располагаются по краям удаляемого, затем скрепляет их и удаляет выделенный, чтобы цепочка не прерывалась. Наглядное представление работы процедуры можно увидеть на рисунке 3.

Рисунок 3 - удаление элемента из структуры

Следующие 3 процедуры осуществляют перемещение элементов в списке, в пределах своего уровня:

procedure Tform1.СopyNode(node1,node2:TTreeNode); var child, temp: TTreeNode; begin child := node1.getFirstChild; //фиксирование первого подпункта while child <> nil do //пока есть подпунты begin temp := TreeView1.Items.AddChild(node2, child.Text); if child.getFirstChild <> nil then copynode(child,temp); child := node1.GetNextChild(child); end; end;

Вышеописанная процедура копирует выделенный элемент и все его вложения на новое место, выше или ниже выделенного.

procedure TForm1.NodeUp(Tree:TTreeview); var node, node2, prevnode: TTreeNode; select, p: integer; last, prev, pprev, cur, temp: ref; begin if Tree.Selected = Tree.Items.Item[0] then //если элемент является верхним на 0 уровне, то выход из процедуры exit; node := Tree.Selected.Parent; //фиксирование элемента уровнем выше if node <> nil then if node.getFirstChild=Tree.Selected then //если элемент является верхним на любом другом уровне, то выход из процедуры exit; node := Tree.Selected; while node.HasChildren do node := node.GetLastChild; //поиск последнего подпункта на последнем уровне cur := Search(Tree.Selected.AbsoluteIndex); //поиск адреса текущего элемента last := Search(node.AbsoluteIndex); //поиск адреса последнего подпункта prevnode := Tree.Selected.getPrevSibling; //фиксирование предыдущего элемента на этом уровне temp := Search(prevnode.AbsoluteIndex); //поиск адреса предыдущего элемента на этом уровне if prevnode.AbsoluteIndex <> 0 then //если элемент является верхним на 0 уровне begin prev := Search(prevnode.GetPrev.AbsoluteIndex); //поиск адреса предыдущего элемента, относительно предыдущего элемента на этом уровне prevnode := Tree.Selected.getPrev; //фиксирование предыдущего элемента, относительно выделенного элемента pprev := Search(prevnode.AbsoluteIndex); //поиск адреса предыдущего элемента, относительно выделенного элемента prev^.next := cur; //перестановка ссылок pprev^.next := last^.next; last^.next := temp; end else begin prevnode := Tree.Selected.getPrev; //фиксирование предыдущего элемента, относительно выделенного элемента pprev := Search(prevnode.AbsoluteIndex); //поиск адреса предыдущего элемента, относительно выделенного элемента reflist := cur; //изменение начального адреса структуры pprev^.next := last^.next; //перестановка ссылок last^.next := temp; end; node2 := Tree.Items.Insert(Tree.Selected.getPrevSibling, Tree.Selected.Text); copynode(Tree.Selected,node2); Tree.Selected.Delete; end;

Вышеописанная процедура перемещает элемент вверх, путем копирования его на новое место и перестановки звений в структуре.

procedure TForm1.nodedown(Tree:TTreeview); var node, node2, nextnode, prevnode: TTreeNode; select, p: integer; last, prev, next, nnext, cur: ref; begin if Tree.Selected = Tree.Items.Item[Tree.Items.Count-1] then exit; node := Tree.Selected.Parent; if node <> nil then if node.getlastChild = Tree.Selected then exit; if Tree.Selected.getNextSibling = nil then exit; Tree.Items.BeginUpdate; node := Tree.Selected; while node.HasChildren do node := node.GetLastChild; cur := Search(Tree.Selected.AbsoluteIndex); last := Search(node.AbsoluteIndex); nextnode := Tree.Selected.getNextSibling; next := Search(nextnode.AbsoluteIndex); node := nextnode; while node.HasChildren do node := node.GetLastChild; nnext := Search(node.AbsoluteIndex); prevnode := Tree.Selected.getPrev; if prevnode <> nil then begin prev := Search(prevnode.AbsoluteIndex); prev^.next := next; end else reflist := next; last^.next := nnext^.next; nnext^.next := cur; node := Tree.Selected.Parent; if node <> nil then begin node := node.getlastChild; node := node.GetPrevSibling; end; if (nextnode.AbsoluteIndex <> Tree.Items.Count-1)and(node <> Tree.Selected) then begin node2 := Tree.Selected.getNextSibling; node2 := Tree.Items.insert(node2.getNextSibling, Tree.Selected.Text); end else node2 := Tree.Items.add(Tree.Selected.getNextSibling, Tree.Selected.Text); CopyNode(Tree.Selected, node2); Tree.Selected.Delete; Tree.Items.EndUpdate; end;

Вышеописанная процедура перемещает элемент вниз и переставляет звенья в структуре. Эта процедура не содержит комментариев, т.к. она делает то же самое, что и предыдущая процедура, но перемещает элемент вниз.

Как видите, тут приведены основные процедуры для работы с многоуровневыми списками на основе динамической структуры. С помощью данного примера можно обрабатывать списки, содержащие огромное количество информации, за минимальное время. Обратите внимание, что перемещение элемента с неограниченно большим количеством вложений, в структуре, все равно займет столько же операций, сколько и добавление элемента в конец структуры, т.е. простое изменение ссылок. В случае с массивом пришлось бы перемещать каждый элемент в отдельности.

Исходный код примера можно скачать тут, а программу тут.