VPF::конструктор и деструктор бинарного дерева

lenarano

Дата 13.5.2015, 13:26 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Ребята, помогите с конструктором и деструктором для моего дерева.
Значения для дерева ключ и строка берутся из файла. Я так понимаю, что мне нужно просто сделать так, что бы в начальных значениях был не "мусор".
Тут в заголовочном файле вроде все правильно

Код


//TreeNode.h
#pragma once
#ifndef __TREENODE_H__
#define __TREENODE_H__
#include <iomanip>
#include <string>


class TreeNode 
{  private:
    int key; 
    std::string polinom;
    TreeNode *leftPtr,*rightPtr;
    public:
   TreeNode();
   ~TreeNode(); 
   void show(TreeNode *&Tree);
   void add_node(int x,std::string p,TreeNode *&MyTree);
   bool is_palindrome(const std::string &word);
};
#endif

А вот тут нужна помощь, как правильно написать конструктор и деструктор

Код


//TreeNode.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include <cctype>
#include "TreeNode.h"


TreeNode::TreeNode() : key(0),leftPtr(0),rightPtr(0),polinom(" ") {} //конструктор
TreeNode::~TreeNode() 
{
    delete ;//???
} 


void TreeNode::show(TreeNode *&Tree) //Функция обхода
{    if (Tree!=NULL) 
{
    show(Tree->leftPtr);
    std::cout<<Tree->key; 
    std::cout<<" ";
    std::cout<<Tree->polinom;
    std::cout<<"\n"; 
    show(Tree->rightPtr); 
}
}
void TreeNode::add_node(int x,std::string p,TreeNode *&MyTree) //Функция добавления звена в дерево
{...//...}

Добавлено через 13 минут и 26 секунд
Я в интернете нашла только такие варианты

Код


Node(int v_usel):usel(v_usel),pr(0),pl(0){}

Но я так понимаю, что мне они не подходят , из-за того, что я добавляю все из файлов. Нашла, что в таких случаях можно обойтись без конструктора. Главное, что бы значения указателей и полей были проинициализированы 0. Но я знаю, что преподаватель будет их требовать(((

lenarano

Дата 13.5.2015, 13:44 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Вот на всяких случай, что я делаю в main

Код


//KodTreeNode.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include "TreeNode.h"


int main()
{  
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    TreeNode *Tree=NULL;  
    TreeNode Derevo();
    std::ifstream imput_fail_key;
    std::ifstream imput_fail_stroki;
    imput_fail_key.open("key.txt", std::ios::in);
    imput_fail_stroki.open("stroki.txt", std::ios::in);
    if (!imput_fail_key.is_open()||!imput_fail_stroki.is_open()) // если файл не открыт
        std::cout << "Файл не может быть открыт!\n"; // сообщить об этом
    std::cout << "Вывод содержимого файла key.txt и файла stroki.txt. \n";
    while(!imput_fail_key.eof()&&!imput_fail_stroki.eof())
    {  
        int k;
        std::string line;
        imput_fail_key>> k; // считали число из файла
        getline(imput_fail_stroki, line);// считали строку из файла
        std::cout << k << " " <<line<< std::endl;// напечатали это число и слово
        Derevo.add_node(k, line.substr(0, 20), Tree);//возвращает 20 символов строки line начиная с позиции 0
    }
    std::cout << std::endl;
    std::cout << "Исходное дерево:\n";
    imput_fail_key.close();
    imput_fail_stroki.close();
    Derevo.show(Tree); 
    std::cout << "Реализуем функцию, которая оставит в дереве только полиндромы:\n";
    /*(до тех пор пока встречаются строки в TreeNode.polinom)
    if(is_palindrome.polinom возвращает 1)
    оставляем в дереве
    else (удаляем)
    Вывод дерева.*/

    std::cin.get();
    return 0;
}

При том как у меня сейчас написан конструктор, ругается на эти строчки
Derevo.show(Tree); //Derevo().show(Tree); ?
Derevo.add_node(k, line.substr(0, 20), Tree);

Еще хотела спросить, насколько нужна вот эта строчка в main.
TreeNode *Tree=NULL;

lenarano

Дата 13.5.2015, 14:10 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Вот эта функция работает, как деструктор-удаляет все. Может ее просто втавить в сам деструктор?

Код


 void cleanup (TreeNode *Tree) // Удаление всех узлов дерева в обходе с отложенной выборкой
  { if(!Tree) return;
     if(Tree->leftPtr)
             { cleanup(Tree->leftPtr);
       Tree->leftPtr = 0;
    }
    if(Tree->rightPtr != 0 )
    { cleanup(Tree->rightPtr);
       Tree->rightPtr = 0;
    }
    delete Tree;
  }

lenarano

Дата 13.5.2015, 14:31 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

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

feodorv

Дата 13.5.2015, 16:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

У Вас есть два разных типа объектов - само дерево и узел этого дерева. При наивном программировании, конечно, можно объединить эти два объекта в один гибридный, но тогда и возникают разные проблемы, в том числе и с конструктором/деструктором.

Для объекта типа дерево определяется указатель на корень дерева и методы по добавлению/удалению узла:

Код


class Tree
{
  private:
    Node *root;
    void cleanup( Node *node );
  public:
    Tree() : root(0) {}
    ~Tree() { cleanup( root ); }
    void add( Node *node );
};

А для объекта типа узел - данные узла (которые должны быть разрушены в деструкторе) и указатели на левого и правого потомка:

Код


class Node
{
  private:
    Node *left, *right;
  public:
    int key; 
    std::string polinom;
    Node() : key(0), left(0), right(0) {}
    Node( int k, const std::string &p) : key(k), polinom(p), left(0), right(0) {}
    ~Node() { left = right = 0; }
}

Так потихоньку можно будет и к шаблонам перейти...

Это сообщение отредактировал(а) feodorv - 13.5.2015, 16:33

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 14.5.2015, 00:32 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Начала делать и у меня полезли такие ошибки(( В основном в //TreeNode.cpp. Мое дерево, объявленное дружественным не видит элементы узла. Уверена, что перепутала параметры в функциях. Сама буду разбираться долго Может укажете на ошибки?

/

Код


/TreeNode.h
#pragma once
#ifndef __TREENODE_H__
#define __TREENODE_H__
#include <iomanip>
#include <string>

class Tree //Дерево
{
private:
    Node *root;
    void cleanup( Node *node );
    public:
    Tree(){};
    ~Tree() {};
    void add( Node *node );
    void show(Tree *&MyTree);
    void add_node(int x,std::string p,Tree *&MyTree);
    friend bool is_palindrome(const std::string &stroka);
};

class Node//Узел
{
private:
    Node *leftPtr, *rightPtr;
public:
    int key; 
    std::string polinom;
    Node(){};
    Node( int k, const std::string &p){};
    ~Node(){};
    friend class Tree;
};


#endif

Код


//TreeNode.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include <cctype>
#include "TreeNode.h"


  Tree::Tree() : root(0) {}
  Tree::~Tree() { cleanup( root );}
  Node::Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node::Node( int k, const std::string &p) : key(k), polinom(p), leftPtr(0), rightPtr(0) {}
  Node::~Node() { leftPtr = rightPtr = 0; }


void Tree::show(Tree *&MyTree) //Функция обхода
{    if (MyTree!=NULL) 
{
    show(MyTree->leftPtr);
    std::cout<<MyTree->key; 
    std::cout<<" ";
    std::cout<<MyTree->polinom;
    std::cout<<"\n"; 
    show(MyTree->rightPtr); 
}
}
void Tree::add_node(int x,std::string p,Tree *&MyTree) //Функция добавления звена в дерево
{static int count=1;
if(count<=10)
{if (NULL==MyTree)  //если дерево пустое
{
    MyTree=new Tree(); 
    MyTree->key=x;
    MyTree->polinom=p;
    MyTree->leftPtr=MyTree->rightPtr=NULL;
    count++;
}
if (x<MyTree->key)   
{    if (MyTree->leftPtr!=NULL) add_node(x,p,MyTree->leftPtr); 
else 
{
    MyTree->leftPtr=new Tree;  
    MyTree->leftPtr->leftPtr=MyTree->leftPtr->rightPtr=NULL; 
    MyTree->leftPtr->key=x;
    MyTree->leftPtr->polinom=p;
    count++;
}
}
if (x>MyTree->key)   
{
    if (MyTree->rightPtr!=NULL) add_node(x,p,MyTree->rightPtr); 
    else 
    {
        MyTree->rightPtr=new Tree;  
        MyTree->rightPtr->leftPtr=MyTree->rightPtr->rightPtr=NULL; 
        MyTree->rightPtr->key=x; 
        MyTree->rightPtr->polinom=p; 
        count++;
    }
}
if (MyTree->key == key) // если ключ повторяется
{ 
    MyTree->key = key;
    MyTree->polinom = p;
}
}
}
bool is_palindrome(const std::string &stroka)
{
    for (size_t i = 0; i < stroka.length()/2; ++i)
    {
        if (tolower(stroka[i]) != tolower(stroka[stroka.length() - i - 1]))
            return false;
    }
    return true;
}


  void Tree::cleanup (Node *node) // Удаление всех узлов дерева в обходе с отложенной выборкой
  { if(!node) return;
     if(node->leftPtr)
             { cleanup(node->leftPtr);
       node->leftPtr = 0;
    }
    if(node->rightPtr != 0 )
    { cleanup(node->rightPtr);
       node->rightPtr = 0;
    }
    delete node;
  }

feodorv

Дата 14.5.2015, 02:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 14.5.2015, 00:32

)

Сама буду разбираться долго

Я бы сделал так:

Код


#include <Windows.h>
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <cctype>

class Node
{
private:
  Node *leftPtr, *rightPtr;

public:
  Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node( int k, const std::string &p) : key(k), polinom(p), leftPtr(0), rightPtr(0) {}
  ~Node() { leftPtr = rightPtr = 0; }

  int key;
  std::string polinom;

  bool is_palindrome();
  void show();

  friend class Tree;
};

void Node::show()
{
  std::cout << key << " " << polinom << " " << is_palindrome() << std::endl;
}

bool Node::is_palindrome()
{
  size_t length = polinom.length();

  if( length == 0 ) return false;

  for( size_t i = 0; i < length/2; ++i)
    if( tolower(polinom[i]) != tolower(polinom[length-i-1]) )
      return false;

  return true;
}

class Tree
{
private:
  Node *root;
  int count;

  void cleanup( Node *node );
  void show_recursive( Node *node );

public:
  Tree() : root(0), count(0) {}
  ~Tree() { cleanup( root ); root = 0; count =0; }

  bool add( Node *node );
  void show();
};

void Tree::cleanup( Node *node )
{
  if( node != 0 )
  {
    cleanup( node->leftPtr );
    cleanup( node->rightPtr );
    delete node;
  }
}

void Tree::show_recursive( Node *node )
{
  if( node != NULL )
  {
    show_recursive( node->leftPtr );
    node->show();
    show_recursive( node->rightPtr );
  }
}

void Tree::show()
{
  show_recursive( root );
}

bool Tree::add( Node *node )
{
  if( count >= 10 ) return false;

  Node *parent = 0, *current = root;

  while( current != NULL )
  {
    parent = current;
    if( node->key == current->key ) return false;

    if( node->key < current->key )
      current = current->leftPtr;
    else
      current = current->rightPtr;
  }

  if( parent == 0 )
    root = node;
  else if( node->key < parent->key )
    parent->leftPtr = node;
  else
    parent->rightPtr = node;

  count++;
  return true;
}

int main( void )
{
  const int keys[20] = { 1, 11, 121, 56765, 2773, 297792, 1220, 5250525,
    10901901, 1092801, 9080, 8778, 70707, 7867, 55555, 1010101, 98, 89, 0, 23 };

  Tree tree;

  for( int i = 0; i < 20; ++i)
  {
    char buf[128];
    sprintf( buf, "%d", keys[i]);

    std::string p( buf );
    Node *node = new Node( keys[i], p);

    if( !tree.add( node ) ) delete node;
  }

  tree.show();
}

Это сообщение отредактировал(а) feodorv - 14.5.2015, 02:14

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 14.5.2015, 03:31 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Спасибо большое, стало понятней. Вот как получилось.

Код


//Tree.h
#pragma once
#ifndef __TREE_H__
#define __TREE_H__
#include <iomanip>
#include <string>


class Node//Узел
{
private:
    Node *leftPtr, *rightPtr;
public:
    Node();//конструктор
    Node( int k, const std::string &p);//конструктор с параментами
    ~Node(); //деструктор

    int key; 
    std::string polinom;

    bool is_palindrome();
    void show();

    friend class Tree;
};

class Tree //Дерево
{
private:
    Node *root;
    int count;

    void cleanup( Node *node );
    void show_recursive( Node *node );
public:
    Tree();
    ~Tree();

    bool add( Node *node );
    void show();

};


#endif

Код


//Tree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include <cctype>
#include "TreeNode.h"


  Node::Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node::Node( int k, const std::string &p) : key(k), polinom(p), leftPtr(0), rightPtr(0) {}
  Node::~Node() { leftPtr = rightPtr = 0; }
  Tree::Tree() : root(0), count(0) {}
  Tree::~Tree() { cleanup( root ); root = 0; count =0; }


 void Tree::cleanup( Node *node )
{
  if( node != 0 )
  {
    cleanup( node->leftPtr );
    cleanup( node->rightPtr );
    delete node;
  }
}

 void Node::show()
{
  std::cout << key << " " << polinom << " " << is_palindrome() << std::endl;
}


void Tree::show_recursive( Node *node )
{
  if( node != NULL )
  {
    show_recursive( node->leftPtr );
    node->show();
    show_recursive( node->rightPtr );
  }
}

void Tree::show()
{
  show_recursive( root );
}

bool Tree::add( Node *node )
{
  if( count >= 10 ) return false;
  Node *parent = 0, *current = root;
  while( current != NULL )
  {
    parent = current;
    if( node->key == current->key ) return false;
    if( node->key < current->key )
      current = current->leftPtr;
    else
      current = current->rightPtr;
  }
  if( parent == 0 )
    root = node;
  else if( node->key < parent->key )
    parent->leftPtr = node;
  else
    parent->rightPtr = node;
  count++;
  return true;
}

bool Node::is_palindrome()
{
  size_t length = polinom.length();
  if( length == 0 ) return false;
  for( size_t i = 0; i < length/2; ++i)
    if( tolower(polinom[i]) != tolower(polinom[length-i-1]) )
      return false;
  return true;
}

У меня вопрос по main. По заданию я должна открыть 2 файла. Один с числами(которые будут как ключи) и один со строками(часть из них будут полиндромами). Ввести эти данные в дерево причем строка была не более 20 символов. Делала я это с помощью этой функции.

Код


Derevo.add_node(k, line.substr(0, 20), Tree);//возвращает 20 символов строки line начиная с позиции 0

А теперь как?

Код


//KodTree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include "TreeNode.h"


int main()
{  
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    
    Tree Wood();
    std::ifstream imput_fail_key;
    std::ifstream imput_fail_stroki;
    imput_fail_key.open("key.txt", std::ios::in);
    imput_fail_stroki.open("stroki.txt", std::ios::in);
    
    std::cout << "Вывод содержимого файла key.txt и файла stroki.txt. \n";
    while(!imput_fail_key.eof()&&!imput_fail_stroki.eof())
    {  
        int k;
        std::string line;
        imput_fail_key>> k; // считали число из файла
        getline(imput_fail_stroki, line);// считали строку из файла
        std::cout << k << " " <<line<< std::endl;// напечатали это число и слово
        Wood.add_node(k, line.substr(0, 20), Tree);//возвращает 20 символов строки line начиная с позиции 0
    }
    std::cout << std::endl;
    std::cout << "Исходное дерево:\n";
    imput_fail_key.close();
    imput_fail_stroki.close();
    Wood.show(); 
    std::cout << "Реализуем функцию, которая оставит в дереве только полиндромы:\n";
    /*(до тех пор пока встречаются строки в Tree)
    if(is_palindrome возвращает 1)
    оставляем в дереве
    else (удаляем)
    */
    Wood.show(); 
    std::cin.get();
    return 0;
}

feodorv

Дата 14.5.2015, 05:37 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 14.5.2015, 03:31

)

Tree Wood();

Это у Вас объявление функции (без параметров, возвращающую экземпляр класса Tree), а не переменной. Наверное, Вы хотели сказать:

Код


Tree Wood;

Цитата(lenarano @ 14.5.2015, 03:31

)

А теперь как?

В моём коде в main все есть. Только для подстроки можно написать так:

Код


std::string p = line.substr(0, 20);
Node *node = new Node( k, p);
if( !tree.add( node ) ) delete node;

Конечно, цикл по добавлению в дерево можно было бы и прервать при достижении 10 добавленных узлов. Чего зря данными раскидываться. Но это как уж Вам будет виднее...

Цитата(lenarano @ 14.5.2015, 03:31

)

else (удаляем)

Ох. Нас ещё ждёт развлечение по удалению узлов дерева smile

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 14.5.2015, 12:51 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Добавила функцию удаление узла. Вроде правильно.

Код


//Tree.h
#pragma once
#ifndef __TREE_H__
#define __TREE_H__
#include <iomanip>
#include <string>


class Node//Узел
{
private:
    Node *leftPtr, *rightPtr;
public:
    Node();//конструктор
    Node( int k, const std::string &p);//конструктор с параментами
    ~Node(); //деструктор

    int key; 
    std::string polinom;

    bool is_leaf() const;
    Node* destroy(Node *node );
    bool is_palindrome();
    void show();

    friend class Tree;
};

class Tree //Дерево
{
private:
    Node *root;
    int count;

    void cleanup( Node *node );
    void show_recursive( Node *node );
public:
    Tree();
    ~Tree();

    bool add( Node *node );
    void show();
    void add_node(int x,std::string p,Node *node);

};


#endif

Код


//Tree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include <cctype>
#include "TreeNode.h"


  Node::Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node::Node( int k, const std::string &p) : key(k), polinom(p), leftPtr(0), rightPtr(0) {}
  Node::~Node() { leftPtr = rightPtr = 0; }
  Tree::Tree() : root(0), count(0) {}
  Tree::~Tree() { cleanup( root ); root = 0; count =0; }


 void Tree::cleanup( Node *node )
{
  if( node != 0 )
  {
    cleanup( node->leftPtr );
    cleanup( node->rightPtr );
    delete node;
  }
}

 void Node::show()
{
  std::cout << key << " " << polinom << " " << is_palindrome() << std::endl;
}


void Tree::show_recursive( Node *node )
{
  if( node != NULL )
  {
    show_recursive( node->leftPtr );
    node->show();
    show_recursive( node->rightPtr );
  }
}

void Tree::show()
{
  show_recursive( root );
}

bool Tree::add( Node *node )
{
  if( count >= 10 ) return false;
  Node *parent = 0, *current = root;
  while( current != NULL )
  {
    parent = current;
    if( node->key == current->key ) return false;
    if( node->key < current->key )
      current = current->leftPtr;
    else
      current = current->rightPtr;
  }
  if( parent == 0 )
    root = node;
  else if( node->key < parent->key )
    parent->leftPtr = node;
  else
    parent->rightPtr = node;
  count++;
  return true;
}

bool Node::is_palindrome()
{
  size_t length = polinom.length();
  if( length == 0 ) return false;
  for( size_t i = 0; i < length/2; ++i)
    if( tolower(polinom[i]) != tolower(polinom[length-i-1]) )
      return false;
  return true;
}

bool Node::is_leaf() const
    {
        return (leftPtr == rightPtr) && (leftPtr == NULL);
    }

Node* Node::destroy(Node *node )
{
    if( node ->is_leaf() )//    дерево состоит из одной вершины
    {
        delete node; 
        return 0;
    }
    else
    if( node->leftPtr == 0 )//    левое поддерево пусто
    {
        Node* r = node->rightPtr;//    сохраняем указатель на правое поддерево
        *node = *r;//    копируем состояние узла находящегося справа
        r->leftPtr = 0;//    удаляем узел
        r->rightPtr = 0;
        delete r;
    } 
    else//    левое поддерево не пусто
    {    //    ищем узел являющийся самым правым в левом поддереве
        Node *c = node->leftPtr;//    самый правый узел
        Node *p = node->leftPtr;//    родитель самого правого узла 
        while( c->rightPtr )//    двигаемся по правой ветви левого поддерева
        {
            p = c;
            c = c->rightPtr;
        }
        p->rightPtr = c->leftPtr;//    левое поддерево самого правого узла становиться правым поддеревом родителя
        c->leftPtr = NULL;//    рвем отношение
        node->key = c->key;//    переносим ключ
        node->polinom = c->polinom;//    переносим ключ
        delete c;//    удаляем самый правый узел
    }
    return node;
}

Код


//KodTree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include "TreeNode.h"


int main()
{  
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    
    Tree Wood;
    std::ifstream imput_fail_key;
    std::ifstream imput_fail_stroki;
    imput_fail_key.open("key.txt", std::ios::in);
    imput_fail_stroki.open("stroki.txt", std::ios::in);
    
    std::cout << "Вывод содержимого файла key.txt и файла stroki.txt. \n";
    while(!imput_fail_key.eof()&&!imput_fail_stroki.eof())
    {   int k;
        std::string line;
        imput_fail_key>> k; // считали число из файла
        getline(imput_fail_stroki, line);// считали строку из файла
        std::cout << k << " " <<line<< std::endl;// напечатали это число и слово
        std::string p = line.substr(0, 20);
        Node *node = new Node( k, p);
        if( !Wood.add( node ) ) delete node;
    }
    std::cout << std::endl;
    std::cout << "Исходное дерево и проверка на полиндромность:\n";
    imput_fail_key.close();
    imput_fail_stroki.close();
    Wood.show(); 
    std::cout << std::endl;
    std::cout << "Реализуем функцию, которая оставит в дереве только полиндромы:\n";
    /*(до тех пор пока встречаются строки в Tree)
    if(is_palindrome возвращает 1)
    оставляем в дереве
    else (удаляем)
    */
    Wood.show(); 
    std::cin.get();
    return 0;
}

Я правильно понимаю, что сейчас нужно реализовать еще одну функцию типа обхода дерева, но добавить в неё, что если не полиндром, но удаляем этот узел?

lenarano

Дата 14.5.2015, 13:50 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Еще хотела спросить. У нас сейчас есть функция bool Node::is_palindrome(), которая читает только слова, т.е. если есть фраза-перевертыш с пробелами, то она возвращает 0. Я создала функцию, которая убирает пробелы из фраз.

Код


void Node::remove_spaces()
{
  size_t length = polinom.length();
  for(int i = 0; i < length; i++)
  {
    if(polinom[i] == ' ') polinom.erase(i,1);
  }
}

А как ее сейчас совместить с нашей bool Node::is_palindrome(), или нужно было просто добавить как-то этот кусок кода в bool Node::is_palindrome().

feodorv

Дата 14.5.2015, 14:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 14.5.2015, 12:51

)

Добавила функцию удаление узла. Вроде правильно.

Опять же, для наивного программирования за основу взять можно. Но.

Вы удаляете узел из дерева. Не из узла. Почему Node::destroy(Node *node )? Зачем возвращаемое значение? Что Вы потом с ним делать будете?
Родительский узел тоже претерпевает изменения при удалении дочернего узла (у него меняется или rightPtr, или leftPtr). Где эти изменения в коде?
А если удаляемый узел есть root, Вам не кажется, что член класса Tree::root надо подправить?
Вы хотите удалить именно узел node. Почему вместо него из дерева удаляется другой узел в случае leftPtr != 0 && rightPtr != 0?

Что означает это сравнение?

Цитата(lenarano @ 14.5.2015, 12:51

)

return (leftPtr == rightPtr) && (leftPtr == NULL);

Зачем эта функция?

Цитата(lenarano @ 14.5.2015, 12:51

)

void add_node(int x,std::string p,Node *node);

???

Цитата(lenarano @ 14.5.2015, 12:51

)

Да!

Цитата(lenarano @ 14.5.2015, 13:50

)

Так вы невозвратимо испортите изначальную строку. Можно поменять алгоритм определения палиндрома, а можно в функции is_palindrome() создать локальную переменную типа std::string, в неё скопировать первоначальный polinom, в ней же удалить пробелы, и для неё же применить уже имеющийся алгоритм. Тогда никаких remove_spaces() (да ещё и сделанных с ошибками) не понадобиться...

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 14.5.2015, 15:05 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Цитата

Что означает это сравнение?
Цитата(lenarano @ 14.5.2015, 12:51 Найти цитируемый пост)
return (leftPtr == rightPtr) && (leftPtr == NULL);

я этот алгоритм нашла в нете, просто пробовала адаптировать к моему куску кода. Переделала:
void Tree::destroy(Node *node ). А можно ваш вариант этой функции, но закоментированный, чтобы я могла понять алгоритм удаления узла.

Цитата

А если менять просто алгоритм, то что нужно добавить?Те варианты, которые я использовала влияли на саму строку.

lenarano

Дата 14.5.2015, 15:57 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Решила поменять алгоритм нахождения полинома. Для того, чтобы не испортить строчку написала так const std::string& stroka. В принципе работает, но считает полиндромом только тогда, когда написано так "а луна канула" и не работает, когда так "А луна канула". Хотя вроде функцию tolower использую. Можно было бы конечно все фразы в файле переписать на строковые буквы. Но все же почему ошибка?

Код


bool Node::is_palindrome(const std::string& stroka)
{
    for(int i=0, j=stroka.size()-1; i < j;)
    {
        if(stroka[i] == ' ')
        {
            ++i;
            continue;
        }
        if(stroka[j] == ' ')
        {
            --j;
            continue;
        }
        if( tolower(stroka[i]) != tolower(stroka[j]) )
        return false;
        ++i;
        --j;
    }
    return true;
}

feodorv

Дата 14.5.2015, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 14.5.2015, 15:57

)

Решила поменять алгоритм нахождения полинома.

Цитата(lenarano @ 14.5.2015, 15:57

)

Хотя вроде функцию tolower использую.

Эх, в виндах все с этим не просто. tolower не отрабатывает на русских буквах, так как не выставлена локальная кодировка. Теоретически, setlocale должна помочь, но как она сочетается с SetConsole*() - без понятия.

Цитата(lenarano @ 14.5.2015, 15:05

)

А можно ваш вариант этой функции, но закоментированный

Я же говорил, что готовится развлечение smile

А как-нибудь более самостоятельно попробовать справиться с заданием?

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »