Модераторы: bsa

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> удаление поддерева 
V
    Опции темы
xvr
Дата 30.3.2010, 21:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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



Неправильно - у класса Vector не определен copy конструктор (и оператор присваивания). Без них конструкция  Vector<T> buf=*this; из erase сделает совсем не то, что было нужно
Что делает resize совсем не понятно, явно только что не resize вектора  smile 
PM MAIL   Вверх
toxx
Дата 30.3.2010, 21:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



xvr
Вы имели ввиду вот это?:
Код

template <class T>
class Vector
{
    T* V;
    int n;
public:
    Vector(int=0);
    Vector(const Vector&);
    int size(){return n;}
    int begin(){return 0;}
    int end(){return n;}
    void resize(int);
    Vector& erase(int);
    ~Vector(){delete[] V;}
    T& operator[](int i){return V[i];}
};

Код

template <class T>
Vector<T>::Vector(const Vector& Vect)
{
    n=Vect.n;
    V=new T[n];
    for(int i=0;i<n;i++)
        V[i]=Vect.V[i];
}


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


Это сообщение отредактировал(а) toxx - 30.3.2010, 21:23
PM MAIL   Вверх
bsa
Дата 30.3.2010, 22:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

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



Цитата(toxx @  30.3.2010,  21:16 Найти цитируемый пост)
А без этого тоже неплохо работало, а в чем разница с этим конструктором копирования и без него?

стандартный конструктор скопирует указатель V и счетчик n. Таким образом, когда вызовется деструктор одного из объектов он освободит ОБЩУЮ память, поэтому, когда вызовется второй деструктор, произойдет попытка повторного освобождения, что приведет к краху программы.
PM   Вверх
toxx
Дата 30.3.2010, 22:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(bsa @ 30.3.2010,  22:09)
Цитата(toxx @  30.3.2010,  21:16 Найти цитируемый пост)
А без этого тоже неплохо работало, а в чем разница с этим конструктором копирования и без него?

стандартный конструктор скопирует указатель V и счетчик n. Таким образом, когда вызовется деструктор одного из объектов он освободит ОБЩУЮ память, поэтому, когда вызовется второй деструктор, произойдет попытка повторного освобождения, что приведет к краху программы.

И всеже никак не пойму у меня функция удаления
Код

void deleteT(Tree *root,int level)
{
    Tree* pv=root,*prev=root;
    Tree* pTree;
    int dLevel,dItem;
    if(level==dLevel)
    {
        root->Trees.erase(dItem);
        //root->count--;
    }
    if(root)
    {
        for(int i=0;i<prev->Trees.size();i++)
        {
            if(root->count%2!=0) 
            {
                dLevel=level-1;
                dItem=i+1;
                cout<<dItem<<endl;
            }
            else deleteT(root->Trees[i],level+1);
        }
    }
}

Есть метод у вектора удаления произвольного элемента массива
Код

Vector<T>& Vector<T> ::erase(int k)
{
    k-=1;
    Vector<T> buf=*this;
    for(int i=0;i<n;i++)
    {
        if(i!=k)V[i]=buf[i];
        else 
        {
            V[i]=buf[i+1];
            k++;
        }
    }
    n-=1;
    V=new T[n];
    for(int i=0;i<n;i++)
        V[i]=buf[i];
    return *this;
}

Опятьже я ищу уровень где нечетное число листьев 
Код

dLevel=level-1;

Потом номер этого элемента
Код

dItem=i+1;

потом удаляю когда рекурсия дошла до уровня нужного
Код

if(level=dLevel)
    {
        root->Trees.erase(dItem);
        //root->count--;
    }


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

Это сообщение отредактировал(а) toxx - 31.3.2010, 09:53
PM MAIL   Вверх
xvr
Дата 31.3.2010, 09:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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



Цитата(toxx @  30.3.2010,  22:53 Найти цитируемый пост)
как xvr говорил я сделал, но это не решение задачи, как я понял.
Тогда озвучте ПОЛНУЮ постановку задачи, ибо для того, что было озвучено это является решением


PM MAIL   Вверх
toxx
Дата 31.3.2010, 09:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(xvr @ 31.3.2010,  09:45)
Цитата(toxx @  30.3.2010,  22:53 Найти цитируемый пост)
как xvr говорил я сделал, но это не решение задачи, как я понял.
Тогда озвучте ПОЛНУЮ постановку задачи, ибо для того, что было озвучено это является решением

Код

Думаю из дерева нужно сделать что-то типа этого:
http://www.imagepost.ru/?v=88/tt_2.jpg

Думаю т.к.  у 2 нечетное кол-во нужно удалить ветку 2-5
аналогично 4-6-7-8
Поддеревом как я понимаю нужно считать всё кроме корня т.е. 2,3,4


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

PM MAIL   Вверх
xvr
Дата 31.3.2010, 14:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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



Цитата(toxx @  31.3.2010,  09:57 Найти цитируемый пост)
Вот такая постановка задачи

В таком случае это делается так (делаю на vector<>, на массив переделайте сами, если надо)
Код

class Tree {
 vector<Tree*> Trees;

public:
 ~Tree()
  {
   for(size_t i=0;i<Trees.size();++i) delete Trees[i];
  }

 void remove_odd()
  {
   for(size_t i=0;i<Trees.size();)
    if (Trees[i]->Trees.size()&1) {delete Trees[i]; Trees.erase(Trees.begin()+i);}
    else ++i;
  }
};



PM MAIL   Вверх
toxx
Дата 31.3.2010, 17:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(xvr @ 31.3.2010,  14:34)
Цитата(toxx @  31.3.2010,  09:57 Найти цитируемый пост)
Вот такая постановка задачи

В таком случае это делается так (делаю на vector<>, на массив переделайте сами, если надо)
Код

class Tree {
 vector<Tree*> Trees;

public:
 ~Tree()
  {
   for(size_t i=0;i<Trees.size();++i) delete Trees[i];
  }

 void remove_odd()
  {
   for(size_t i=0;i<Trees.size();)
    if (Trees[i]->Trees.size()&1) {delete Trees[i]; Trees.erase(Trees.begin()+i);}
    else ++i;
  }
};


Интересно,но это работает!Полунедельная проблема решена!Спасибо это делает то чего не делает моя процедура.
В связи с этим кодом родились вопросы:
1.Почему вы используете size_t? вместо int(в дефайне unsigned int)
2.Как работает resize у vector'a, хочу попробовать хотябы чтонить близкое сделать.
3.В чем недостатки моего erase? потомучто если тоже самое запускать, но вместо вектора использовать мой вектор ошибки памяти...
erase:
Код

Vector<T>& Vector<T> ::erase(int k)
{
    k-=1;
    Vector<T> buf=*this;
    for(int i=0;i<n;i++)
    {
        if(i!=k)V[i]=buf[i];
        else 
        {
            V[i]=buf[i+1];
            k++;
        }
    }
    n-=1;
    V=new T[n];
    for(int i=0;i<n;i++)
        V[i]=buf[i];
    return *this;
}

resize
Код

void Vector<T>::resize(int k)
{
    delete[] V;
    n=k;
    V=new T[n];
    for(int i=0;i<n;i++)
        V[i]=0;
}


Это сообщение отредактировал(а) toxx - 31.3.2010, 17:47
PM MAIL   Вверх
bsa
Дата 31.3.2010, 18:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

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



Цитата(toxx @  31.3.2010,  17:44 Найти цитируемый пост)
Почему вы используете size_t? вместо int(в дефайне unsigned int)
size_t специально предназначен для хранения размеров областей памяти. Так же как и ptrdiff_t предназначен для хранения смещений указателей. Если интересно, поищи в интернете, чем это обусловлено и какая выгода.
Кстати, size_t на 32-х битных машинах обычно uint32_t, а на 64-х битных - uint64_t. Как ты думаешь, почему?
PM   Вверх
toxx
Дата 31.3.2010, 18:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(bsa @ 31.3.2010,  18:09)
Цитата(toxx @  31.3.2010,  17:44 Найти цитируемый пост)
Почему вы используете size_t? вместо int(в дефайне unsigned int)
size_t специально предназначен для хранения размеров областей памяти. Так же как и ptrdiff_t предназначен для хранения смещений указателей. Если интересно, поищи в интернете, чем это обусловлено и какая выгода.
Кстати, size_t на 32-х битных машинах обычно uint32_t, а на 64-х битных - uint64_t. Как ты думаешь, почему?

Думаю из-за разрядности системы, как я понимаю в 32-битных и 64-битных системах один и тот же тип
занимает разное количество памяти в битах.верно?щас ищу про size_t и ptrdiff_t...
PM MAIL   Вверх
bsa
Дата 1.4.2010, 10:17 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

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



Цитата(toxx @  31.3.2010,  18:14 Найти цитируемый пост)
как я понимаю в 32-битных и 64-битных системах один и тот же тип
занимает разное количество памяти в битах.верно?
Например размер указателей различается, а размеры char, short и int нет. Размер long зависит от платформы (в 64-х битных *nix он 64 бита, а в Win64 - 32 бита, если не ошибаюсь)

PM   Вверх
xvr
Дата 1.4.2010, 14:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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



Цитата(bsa @  1.4.2010,  10:17 Найти цитируемый пост)
Например размер указателей различается, а размеры char, short и int нет.
Размер int может отличаться. Например Intel сомпилятор под Linux 64 имеет ключ -ilp64, который делает int,long и void* все по 64 бита (еще есть -ilp32, который их всех делает по 32)

На некоторых DSP процессорах char 2х байтовый  smile 


PM MAIL   Вверх
toxx
Дата 1.4.2010, 15:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Судя по статье есть смысл использовать
size_t и ptrdiff_t если ты переносишь приложения на 64х битные системы, а так написано, что на моей 32х битной
ничего не будет  заметно...

Это сообщение отредактировал(а) toxx - 1.4.2010, 15:15
PM MAIL   Вверх
bsa
Дата 1.4.2010, 15:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

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



Цитата(toxx @  1.4.2010,  15:14 Найти цитируемый пост)
на моей 32х битной
ничего не будет  заметно...
Мой отец в таких случаях всегда говорит: "Делай хорошо, плохо само получится". Не известно, каким местом жизнь потом повернется.  smile 
PM   Вверх
toxx
Дата 2.4.2010, 16:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Проверил функцию вашу функцию xvr
Сначала у меня сложилась видимость что всё верно делает, потом сегодня я сел опять проверять, но только 
уже на других данных(увеличил количество уровней дерева до 3х, до этого проверял на одном уровне,
и увидел что если на 1м уровне 3 поддерева на втором у каждого дерева еще по 3 поддерева
и на третьем уровне еще под 1 поддереву у каждого) и понял что функция вызывается смотрит что у
второго уровня 3 поддерева и удаляет весь первый уровень не смотря на то, что есть еще 3й уровень.
Опять добавил рекурсию... менял условия, но опять ничего не выходит.
Функция remove_odd() написанная вами и рисунок дерева которое я вводил 
мой erase()
Код

Vector<T>& Vector<T> ::erase(int k)
{
    if(k>=n||k<0) 
    {
        cout<<"index out of range"<<endl;
        return *this;
    }
    Vector buf=*this;
    n--;
    delete V;
    V=new T[n];
    for(int i=0;i<n;i++)
    if(i!=k)(*this)[i]=buf[i];
    else 
    {
        (*this)[i]=buf[i+1];
        k++;
    }
}

Код

struct Tree
{
    int d;
    int count;
    Vector<Tree *> Trees;
    void remove();
    ~Tree();
};
void Tree::remove()
{
    for(int i=0;i<Trees.size();)
    if (Trees[i]->Trees.size()%2!=0)
    {
        delete Trees[i];
        Trees.erase(i);    
    }
    else i++;
}

И как я ей пользуюсь:
Код

void deleteT(Tree *root,int level)
{
    if(root)
    {
        for(int i=0;i<root->Trees.size();i++)
        {
            if(root->count%2!=0) 
            {
                root->remove();
            }
            else deleteT(root->Trees[i],level+1);
        }
    }
}


До этого я просто в main() написал root->remove(); и понял, что это ошибка только сегодня(тестируя, всегда на 1 уровне дерева)
Код

int main()
{
    Tree* root=first(10);
    insert(root);
    cout<<"DO DELETE"<<endl;
    print(root,0);
    root->remove();
    cout<<"POSLE DELETE"<<endl;
    print(root,0);
    return 0;
}

Вроде бы уже всё что нужно есть, а не удаляется если уровней больше одного...прошу еще раз посмотреть.

Это сообщение отредактировал(а) toxx - 2.4.2010, 16:27
PM MAIL   Вверх
Страницы: (3) Все 1 [2] 3 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

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


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

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


 




[ Время генерации скрипта: 0.0650 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.