Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28500 > unrolled thread

Jak przeszukiwać drzewo z przerwami ?

Back to article view | Back to pl.comp.programming

Contents

  Jak przeszukiwać drzewo z przerwami ? Borneq <borneq@antyspam.hidden.pl> - 2016-04-20 05:26 +0200
    Re: Jak przeszukiwać drzewo z przerwami ? "Jordan Szubert" <usenet@joru.us.to> - 2016-04-20 06:03 +0200
      Re: Jak przeszukiwać drzewo z przerwami ? Borneq <borneq@antyspam.hidden.pl> - 2016-04-20 16:08 +0200
        Re: Jak przeszukiwać drzewo z przerwami ? Borneq <borneq@antyspam.hidden.pl> - 2016-04-20 16:36 +0200
        Re: Jak przeszukiwać drzewo z przerwami ? Borneq <borneq@antyspam.hidden.pl> - 2016-04-20 17:00 +0200
          Re: Jak przeszukiwać drzewo z przerwami ? "Jordan Szubert" <usenet@joru.us.to> - 2016-04-20 18:37 +0200
            Re: Jak przeszukiwać drzewo z przerwami ? Borneq <borneq@antyspam.hidden.pl> - 2016-04-21 05:41 +0200

#28500 — Jak przeszukiwać drzewo z przerwami ?

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#

[toc] | [next] | [standalone]

#28501

Dnia 20-04-2016 o 05:26:49 Borneq <borneq@antyspam.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

[toc] | [prev] | [next] | [standalone]

#28502

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)
   }
}

[toc] | [prev] | [next] | [standalone]

#28503

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();

[toc] | [prev] | [next] | [standalone]

#28504

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;
             }
         }

[toc] | [prev] | [next] | [standalone]

#28505

Dnia 20-04-2016 o 17:00:45 Borneq <borneq@antyspam.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

[toc] | [prev] | [next] | [standalone]

#28506

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.

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web