MetaProg

Description: Разработка и отладка приложений. Упор на 3D-графику.

dyvniy M
Topic author, Администратор
Администратор
Avatar
dyvniy M
Topic author, Администратор
Администратор
Age: 36
Reputation: 1
Loyalty: 1
Posts: 3088
Joined: Wed, 10 Oct 2012
With us: 6 years 6 months
Профессия: Программист
Location: Россия, Москва
ICQ Website Skype VK

#67by dyvniy » Sat, 23 Jun 2018, 15:57:48

Оказывается парсить инфоксную запись в дерево не сложнее, чем строить из дерева.
http://pascal.net.ru/Алгоритмы на графах и деревьях
Вот что у меня получилось на питоне:

Code: Select all

class Tree:
    L = None
    R 
= None
    data 
= None
    def __init__
(self, d=None):
        self.data = d
    def print
(self, t, level=0):
        if t.L:
            self.print(t.L, level + 1)
        print(str(level) + ' ' + str(t.data))
        if t.R:
            self.print(t.R, level + 1)
def read(s):
    return s.pop()
def parce(s):
    a = []
    for w in s:
        a.insert(0, w)
    return infix(a)
def infix(s):
    c = read(s)
    if c == '(':
        p = Tree()
        p.= infix(s)
        p.data = read(s)
        p.= infix(s)
        read(s) # '>'
    else:
        p = Tree(c)
    return p
#t = infix([')', 2, '+', 3, '('])
= parce('(2+(3*(4-5)))')
t.print(t

Тут главное чтобы присутствовали все скобки.
Без них работать не будет.
Думаю с префиксной и постфиксной записью ещё проще.
Отсюда, переделано
http://pascal.net.ru/Алгоритмы на графах и деревьях
Image

dyvniy M
Topic author, Администратор
Администратор
Avatar
dyvniy M
Topic author, Администратор
Администратор
Age: 36
Reputation: 1
Loyalty: 1
Posts: 3088
Joined: Wed, 10 Oct 2012
With us: 6 years 6 months
Профессия: Программист
Location: Россия, Москва
ICQ Website Skype VK

#68by dyvniy » Wed, 11 Jul 2018, 16:57:51

Бинарные деревья - это просто
https://habr.com/post/267855/
Image

dyvniy M
Topic author, Администратор
Администратор
Avatar
dyvniy M
Topic author, Администратор
Администратор
Age: 36
Reputation: 1
Loyalty: 1
Posts: 3088
Joined: Wed, 10 Oct 2012
With us: 6 years 6 months
Профессия: Программист
Location: Россия, Москва
ICQ Website Skype VK

#69by dyvniy » Tue, 17 Jul 2018, 14:29:39

Драйвера сетевух, неофициальные.
https://www.ath-drivers.eu/atheros-wireless-drivers.html
Image

dyvniy M
Topic author, Администратор
Администратор
Avatar
dyvniy M
Topic author, Администратор
Администратор
Age: 36
Reputation: 1
Loyalty: 1
Posts: 3088
Joined: Wed, 10 Oct 2012
With us: 6 years 6 months
Профессия: Программист
Location: Россия, Москва
ICQ Website Skype VK

#70by dyvniy » Thu, 19 Jul 2018, 18:55:09

Сортировка двоичным деревом.
Идеальна для потоков.
Требует 4н памяти.
https://ru.wikipedia.org/wiki/Сортировка_с_помощью_двоичного_дерева
Spoiler
Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например из файла, сокета или консоли).

Содержание
1 Алгоритм
2 Эффективность
3 Примеры реализации
4 См. также
Алгоритм
1. Построение двоичного дерева.

2. Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.

Эффективность
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)). Соответственно, для n объектов сложность будет составлять O(n log(n)), что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n), что может привести к общей сложности порядка O(n²).

При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.

Примеры реализации
В простой форме функционального программирования на Haskell данный алгоритм будет выглядеть так:

data Tree a = Leaf | Node (Tree a) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x (Node t y t') | x <= y = Node (insert x t) y t'
insert x (Node t y t') | x > y = Node t y (insert x t')

flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node t x t') = flatten t ++ [x] ++ flatten t'

treesort :: Ord a => [a] -> [a]
treesort = flatten . foldr insert Leaf
Реализация на C++14:

Code: Select all

#include <memory>
#include <cassert>
#include <algorithm>

#include <vector>
#include <iostream>

using namespace std;

// класс, представляющий бинарное дерево
class BinaryTree
{
protected:
  
// узел бинарного дерева
  
struct BinaryTreeNode
  
{
    
shared_ptr<BinaryTreeNodeleftright// левое и правое поддерево
    
int key// ключ
  
};

  
shared_ptr<BinaryTreeNodem_root// корень дерева
  
protected:
  
// рекурсивная процедура вставки ключа
  // cur_node - текущий узел дерева, с которым сравнивается вставляемый узел
  // node_to_insert - вставляемый узел
  
void insert_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const shared_ptr<BinaryTreeNode>& node_to_insert)
  {
      
assert(cur_node != nullptr);
      
// сравнение
      
bool insertIsLess node_to_insert->key cur_node->key;
      if(
insertIsLess)
      {
        
// вставка в левое поддерево
        
if(cur_node->left == nullptr)
          
cur_node->left node_to_insert;
        else
          
insert_recursive(cur_node->leftnode_to_insert);
      }
      else
      {
        
// вставка в правое поддерево
        
if(cur_node->right == nullptr)
          
cur_node->right node_to_insert;
        else
          
insert_recursive(cur_node->rightnode_to_insert);
      }
  }

public:
  
void insert(int key)
  {
    
shared_ptr<BinaryTreeNodenode_to_insert(new BinaryTreeNode);
    
node_to_insert->key key;

    if(
m_root == nullptr)
    {
        
m_root node_to_insert;
        return;
    }

    
insert_recursive(m_rootnode_to_insert);
  }

public:
  
typedef function<void(int key)> Visitor;

protected:
  
// рекурсивная процедура обхода дерева
  // cur_node - посещаемый в данный момент узел
  
void visit_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const Visitorvisitor)
  {
    
assert(cur_node != nullptr);

    
// сначала посещаем левое поддерево
    
if(cur_node->left != nullptr)
      
visit_recursive(cur_node->leftvisitor);

    
// посещаем текущий элемент
    
visitor(cur_node->key);

    
// посещаем правое поддерево
    
if(cur_node->right != nullptr)
      
visit_recursive(cur_node->rightvisitor);
  }

public:
  
void visit(const Visitorvisitor)
  {
    if(
m_root == nullptr)
      return;
    
visit_recursive(m_rootvisitor);
  }
};

int main()
{
  
BinaryTree tree;
  
// добавление элементов в дерево
  
vector<intdata_to_sort = {1027314732};
  for(
int value data_to_sort)
  {
    
tree.insert(value);
  }
  
// обход дерева
  
tree.visit([](int visited_key)
  {
    
cout<<visited_key<<" ";
  });
  
cout<<endl;

  
// результат выполнения: 2 3 7 7 10 14 32
  
return 0;
}
 

Пример создания бинарного дерева и сортировки на языке Java:

Code: Select all

// Скомпилируйте и введите java TreeSort
class Tree {
   public 
Tree left;            // левое и правое поддеревья и ключ
   
public Tree right;
   public 
int key;

   public 
Tree(int k) {        // конструктор с инициализацией ключа
      
key k;
   }

/*  insert (добавление нового поддерева (ключа))
    сравнить ключ добавляемого поддерева (К) с ключом корневого узла (X).
    Если K>=X, рекурсивно добавить новое дерево в правое поддерево.
    Если K<X, рекурсивно добавить новое дерево в левое поддерево.
    Если поддерева нет, то вставить на это место новое дерево
*/
   
public void insertTree aTree) {
     if ( 
aTree.key key )
        if ( 
left != null left.insertaTree );
        else 
left aTree;
     else
        if ( 
right != null right.insertaTree );
        else 
right aTree;
   }

/*  traverse (обход)
    Рекурсивно обойти левое поддерево.
    Применить функцию f (печать) к корневому узлу.
    Рекурсивно обойти правое поддерево.
*/
   
public void traverse(TreeVisitor visitor) {
      if ( 
left != null
            
left.traversevisitor );

      
visitor.visit(this);

      if ( 
right != null 
            
right.traversevisitor );
   }
}

interface 
TreeVisitor {
  public 
void visit(Tree node);
};

class 
KeyPrinter  implements TreeVisitor {
  public 
void visit(Tree node) {
      
System.out.println" " node.key );
  }
};

class 
TreeSort {
  public static 
void main(String args[]) {
     
Tree myTree;
     
myTree = new Tree);       // создать дерево (с ключом)
     
myTree.insert( new Tree) );  // присоединять поддеревья
     
myTree.insert( new Tree) );
     
myTree.traverse(new KeyPrinter());
  }
Image


Forum name: Программирование (под Desktop и Android)
Description: Разработка и отладка приложений. Упор на 3D-графику.

Quick reply


Enter the code exactly as it appears. All letters are case insensitive.
Confirmation code
:) ;) :hihi: :P :hah: :haha: :angel: :( :st: :_( :cool: 8-| :beee: :ham: :rrr: :grr: :* :secret: :stupid: :music: View more smilies
   

Return to “Программирование (под Desktop и Android)”