-
1. Data: 2016-04-20 05:26:49
Temat: Jak przeszukiwać drzewo z przerwami ?
Od: Borneq <b...@a...hidden.pl>
Większość operacji na drzewie robi się rekurencyjnie. Tak jak na
przykład wypisanie wszystkich znalezionych ciągów.
Wypisz(root) woła Wypisz(1), Wypisz(2)...
Ale teraz chcę zrobić coś takiego:
Control+F ma znaleźć pierwsze wystąpienie ciągu, (np. przeszukiwanie w
rejestrach lub jakimkolwiek innym drzewie z danymi) i stanąć na
znalezionym węźle, niezależnie jak zagłębiony.
Naciskając F3 zaczynamy od tego węzła i dalej szukamy.
Chyba trzeba zrobić sztuczny stos na liście (wektorze, chodzi mi ogólnie
C++, a zwłaszcza teraz o C#) zamiast rekurencji.
Jak to wykonać? W C#
-
2. Data: 2016-04-20 06:03:02
Temat: Re: Jak przeszukiwać drzewo z przerwami ?
Od: "Jordan Szubert" <u...@j...us.to>
Dnia 20-04-2016 o 05:26:49 Borneq <b...@a...hidden.pl> napisał(a):
> Większość operacji na drzewie robi się rekurencyjnie. Tak jak na
> przykład wypisanie wszystkich znalezionych ciągów.
> Wypisz(root) woła Wypisz(1), Wypisz(2)...
> Ale teraz chcę zrobić coś takiego:
> Control+F ma znaleźć pierwsze wystąpienie ciągu, (np. przeszukiwanie w
> rejestrach lub jakimkolwiek innym drzewie z danymi) i stanąć na
> znalezionym węźle, niezależnie jak zagłębiony.
> Naciskając F3 zaczynamy od tego węzła i dalej szukamy.
> Chyba trzeba zrobić sztuczny stos na liście (wektorze, chodzi mi ogólnie
> C++, a zwłaszcza teraz o C#) zamiast rekurencji.
> Jak to wykonać? W C#
w C# kompilator zrobi za ciebie sporo roboty:
public class Node : IEnumerable<Node> {
public string Name;
public List<Node> Children = new List<Node>();
public IEnumerator<Node> GetEnumerator() {
yield return this;
foreach(var c in Children) {
foreach(var e in c) {
yield return e;
}
}
}
System.Collections.IEnumerator
System.Collections.IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
}
IEnumerator<Node> lastSearch = null;
Node ControlF(Node root, string needle) {
{
var td = lastSearch as IDisposable;
if(td != null) {
td.Dispose();
}
}
lastSearch = root.Where(n => n.Name == needle).GetEnumerator();
if(lastSearch.MoveNext()) {
//has at least one result
return lastSearch.Current;
} else {
//nothing found
return null;
}
}
Node F3() {
if(lastSearch == null) {
return null;
}
if(!lastSearch.MoveNext()) {
//no more results
return null;
} else {
return lastSearch.Current;
}
}
//nie testowalem, moga byc bledy
--
Jordan Szubert
skype:jordanszubert
-
3. Data: 2016-04-20 16:08:37
Temat: Re: Jak przeszukiwać drzewo z przerwami ?
Od: Borneq <b...@a...hidden.pl>
W dniu 20.04.2016 o 06:03, Jordan Szubert pisze:
> w C# kompilator zrobi za ciebie sporo roboty:
A czy taki pseudocod chodzenia po drzewie będzie równoważny
rekurencyjnemu przechodzeniu w głąb?
iter_search(root)
{
node : =root;
nr_child := 0;
while(true)
{
Akcja(node);
while (nr_child>=node.Count)
{
node := node.Parent
nr_child := Pop();
if (Stack_empty) return;
}
node := node.Childs[nr_child];
Push(nr_child+1)
}
}
-
4. Data: 2016-04-20 16:36:16
Temat: Re: Jak przeszukiwać drzewo z przerwami ?
Od: Borneq <b...@a...hidden.pl>
W dniu 20.04.2016 o 16:08, Borneq pisze:
> node := node.Parent
> nr_child := Pop();
> if (Stack_empty) return;
if (Stack_empty) return;
node := node.Parent
nr_child := Pop();
-
5. Data: 2016-04-20 17:00:45
Temat: Re: Jak przeszukiwać drzewo z przerwami ?
Od: Borneq <b...@a...hidden.pl>
W dniu 20.04.2016 o 16:08, Borneq pisze:
> W dniu 20.04.2016 o 06:03, Jordan Szubert pisze:
> A czy taki pseudocod chodzenia po drzewie będzie równoważny
> rekurencyjnemu przechodzeniu w głąb?
pseudocod jest zły:
trzeba:
private void IterativeSearchNode(TreeNode treeNode, string text)
{
Stack<int> stack = new Stack<int>();
TreeNode node = treeNode;
int nr = 0;
while (true)
{
if (node.Text.Contains(text))
textBox1.AppendText(textBox1.Lines.Count() + 1 + ":
" + node.Text + "\n");
while (nr >= node.Nodes.Count)
{
if (stack.Count==0) return;
nr = stack.Pop();
node = node.Parent;
nr++;
}
stack.Push(nr);
node = node.Nodes[nr];
nr = 0;
}
}
-
6. Data: 2016-04-20 18:37:44
Temat: Re: Jak przeszukiwać drzewo z przerwami ?
Od: "Jordan Szubert" <u...@j...us.to>
Dnia 20-04-2016 o 17:00:45 Borneq <b...@a...hidden.pl> napisał(a):
> W dniu 20.04.2016 o 16:08, Borneq pisze:
>> W dniu 20.04.2016 o 06:03, Jordan Szubert pisze:
>> A czy taki pseudocod chodzenia po drzewie będzie równoważny
>> rekurencyjnemu przechodzeniu w głąb?
>
> pseudocod jest zły:
> trzeba:
> private void IterativeSearchNode(TreeNode treeNode, string text)
> {
> Stack<int> stack = new Stack<int>();
> TreeNode node = treeNode;
> int nr = 0;
> while (true)
> {
> if (node.Text.Contains(text))
> textBox1.AppendText(textBox1.Lines.Count() + 1 + ":
> " + node.Text + "\n");
> while (nr >= node.Nodes.Count)
> {
> if (stack.Count==0) return;
> nr = stack.Pop();
> node = node.Parent;
> nr++;
> }
> stack.Push(nr);
> node = node.Nodes[nr];
> nr = 0;
> }
> }
to wygląda jak kod który znajduje wszystkie wystąpienia od razu, i
przerabia je na tekst w textboxie;
mój kod generuje enumerator który można wznawiać i pauzować bez problemu;
czyta tylko tyle danych ile trzeba a nie wszystkie od razu, i używa
kompilatora C# do pisania nudnego kodu
--
Jordan Szubert
skype:jordanszubert
-
7. Data: 2016-04-21 05:41:12
Temat: Re: Jak przeszukiwać drzewo z przerwami ?
Od: Borneq <b...@a...hidden.pl>
W dniu 20.04.2016 o 18:37, Jordan Szubert pisze:
> mój kod generuje enumerator który można wznawiać i pauzować bez
> problemu; czyta tylko tyle danych ile trzeba a nie wszystkie od razu, i
> używa kompilatora C# do pisania nudnego kodu
Nie zrozumiałem, jak będę miał trochę czasu to wkleję go do
rzeczywistego programu i zobaczę jak działa.