VPF::[C++] Разместить int и char - Форум программистов

byNet

Дата 24.11.2005, 18:18 (ссылка)

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

Загрузка ...

Шустрый

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

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

Помогите разобраться. Например мне надо размести ть в двоич. дереве на каждый лепесток
int , и char; тоесть int -дата а сhar - имя. Я лично думую вырозить это через структуру.
Затем как происходит занос этого в двоч. дерево. И сортировка. Если можно предоставьте код пример.

Void

Дата 24.11.2005, 19:27 (ссылка)

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

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

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

К примеру так:

Код

#include <iostream>
#include <string>
#include <functional>

template <class Key, class Value, class Comparer = std::less<Key> >
class Node {
    Key key;
    Value data;
    const Comparer &cmp;
    Node *left, *right;
public:
    Node(Key key, Value data, const Comparer &cmp = Comparer()) :
        key(key), data(data), cmp(cmp), left(NULL), right(NULL) { }
    ~Node() {
        if (left)
            delete left;
        if (right)
            delete right;
    }
    const Key &get_key() const {
        return key;
    }
    const Value &get_data() const {
        return data;
    }
    void set_data(const Value &data) {
        this->data = data;
    }
    void insert(const Key &key, const Value &data) {
        if (cmp(key, this->key)) // if key less than current node key
            if (!left) // it goes to the left subtree
                left = new Node(key, data);
            else
                left->insert(key, data);
        else if (cmp(this->key, key)) // otherwise
            if (!right) // to the right subtree
                right = new Node(key, data);
            else
                right->insert(key, data);
        else // node with specified key already exists
            return; // do nothing
    }
    template <class Function>
    void iterate(const Function &f) const {
        if (left)
            left->iterate(f);
        f(key, data);
        if (right)
            right->iterate(f);
    }
};

void print_node(const std::string &key, int data) {
    std::cout << '(' << key << ", " << data << ")\n";
}

int main() {
    Node<std::string, int> root("hello", 1);
    root.insert("world", 2);
    root.insert("test", 3);
    root.iterate(print_node);
}

Вывод:

Цитата

(hello, 1)
(test, 3)
(world, 2)

Реализацию методов insert и iterate можно улучшить, переделав хвостовую рекурсию в итерацию.

Это сообщение отредактировал(а) Void - 24.11.2005, 20:20

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

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Chaos A.D.

Дата 24.11.2005, 19:29 (ссылка)

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

Загрузка ...

Бывалый

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

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

Извини, что не помог тебе в твоем аналогичном посте, хотя и пообещал. Времени в обрез, сессия как никак... На счет твоего вопроса - заюзай std::pair<int, char>. А для поиска можно написать функтор.

опередили...

Это сообщение отредактировал(а) Chaos A.D. - 24.11.2005, 19:30

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

Надо смеяться над тем, что тебя мучит, иначе не сохранишь равновесия, иначе мир сведет тебя с ума...Ken Kesey - One Flew Over The Cocoo's Nest

byNet

Дата 25.11.2005, 10:01 (ссылка)

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

Загрузка ...

Шустрый

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

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

Спасибо большое за помощь е сли у кого есть ище какие нибудь варианты.
Если можно покожите пример как выглядит на С.

B3cK

Дата 26.11.2005, 16:08 (ссылка)

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

Загрузка ...

Новичок

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

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

Код


//////////////////////////////////////////////////////////////////////////////    
//    
//  Dynamic structures (binary tree)    
//  (c) Johna Smith, 1996    
//    
//  Method description:    
//               *    
//            /     \    
//           *       *    
//         /   \   /   \    
//        *     * *     *    
//    
//   From current element X left element is less than X and right element    
// is greater than X. All elements in the must be different.    
//    
//////////////////////////////////////////////////////////////////////////////    
#include <stdio.h>    
#include <alloc.h>    
#include <conio.h>    
#include <math.h>    
struct item    
{    
  int element;    
  item *left;    
  item *right;    
};    
item *tree; // base element of the list    
// this function searches element in the tree and returns 0 if element wasn't    
// found and 1 - if element was found, result is address of element    
char Search(int element, item** result)    
{    
  item *p,*q;    
  char found=0;    
  p=tree;    
  if (tree!=NULL)    
  do    
  {    
    q=p;    
    if (p->element==element) found=1;    
    else    
    {    
      q=p;    
      if (element<p->element) p=p->left;    
      else p=p->right;    
    }    
  }    
  while (!found && p!=NULL);    
  *result=q;    
  return found;    
}    
// this function adds an element to the tree    
void Add(int element)    
{    
  item *r,*s;    
  if (Search(element,&r)==0)    
  {    
    s=(item*)malloc(sizeof(item));    
    s->element=element;    
    s->left=NULL;    
    s->right=NULL;    
    if (tree==NULL) tree=s; // if tree is empty make s=top of the tree    
    else    
    {    
      if (element<r->element) r->left=s;    
      else r->right=s;    
    }    
  }    
}    
// this is auxulary function for Remove procedure    
void Del(item **r, item **q)    
{    
  item *tmp;    
  if ((*r)->right==NULL)    
  {    
    (*q)->element=(*r)->element;    
    *q=*r;    
    *r=(*r)->left;    
  }    
  else Del(&((*r)->right),q);    
}    
// this function removes element with value 'element' from the tree    
void Remove(int element, item **d)    
{    
  item *q;    
  if (*d==NULL)    
  printf("There is not element %d in the tree.\n",element);    
  else    
  if (element<(*d)->element) Remove(element, &((*d)->left)); else    
  if (element>(*d)->element) Remove(element, &((*d)->right)); else    
  {    
    // element found    
    q=*d;    
    if (q->right==NULL) *d=q->left; else    
    if (q->left==NULL) *d=q->right; else    
    Del(&(q->left),&q);    
    free(q);    
  }    
}    
// this function prints the tree    
void printtree(item *t, int offset=40, int depth=2)    
{    
  gotoxy(offset,depth);    
  cprintf("%d",t->element);    
  if (t->left!=NULL) printtree(t->left,offset-pow(2,6-depth),depth+1);    
  if (t->right!=NULL) printtree(t->right,offset+pow(2,6-depth),depth+1);    
}    
void main(void)    
{    
  item *tmp;    
  // creating tree    
  Add(100);    
  Add(20);    
  Add(120);    
  Add(15);    
  Add(50);    
  Add(130);    
  Add(30);    
  Add(55);    
  Add(28);    
  Add(35);    
  Add(60);    
  Add(33);    
  // printing tree    
  clrscr();    
  printf("Press a key to delete element 50...\n");    
  printtree(tree);    
  getch();    
  clrscr();    
  Remove(50,&tree);    
  printtree(tree);    
  gotoxy(1,20);    
  // searching    
  cprintf("Element 20 is%s found",(Search(20,&tmp)?"":"n't"));    
  printf("\nElement 25 is%s found\n",(Search(25,&tmp)?"":"n't"));    
  // removing all elements    
  Remove(100,&tree);    
  Remove(20,&tree);    
  Remove(120,&tree);    
  Remove(15,&tree);    
  Remove(35,&tree);    
  Remove(130,&tree);    
  Remove(30,&tree);    
  Remove(55,&tree);    
  Remove(28,&tree);    
  Remove(33,&tree);    
  Remove(60,&tree);    
}

byNet

Дата 12.12.2005, 12:21 (ссылка)

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

Загрузка ...

Шустрый

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

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

Спасибо всем за помощь

byNet

Дата 14.12.2005, 13:17 (ссылка)

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

Загрузка ...

Шустрый

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

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

Да.... а может кто поможет мне в решении такой задачки(проблемы) если можно без STL.
вот уже месяц над ней мозги дур.

В файловой системе справочник файлов организован в виде упорядоченного двоичного дерева. Каждому узлу соответствует некоторый файл, в узле содержится имя файла и дата последнего обращения к нему. Написать программу, которая удаляет из дерева все файлы (узлы), обращение к которым было до даты введенной с клавиатуры.

Если кто может помогите на С или С++.

Заранее благодарен

podval

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

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

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

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

Модератор: Теме перенесена из раздела "Алгоритмы"

_hunter

Дата 14.12.2005, 15:04 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 8564
Регистрация: 24.6.2003
Где: Europe::Ukraine:: Kiev

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

есть она тут уже smile

http://forum.vingrad.ru/index.php?showtopic=71956

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

Tempora mutantur, et nos mutamur in illis...

byNet

Дата 16.12.2005, 15:28 (ссылка)

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

Загрузка ...

Шустрый

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

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

Код


#include <stdio.h>
#include <iostream.h>
#include <iostream>
#include <conio.h>
#pragma hdrstop
struct Node{
int Data;
std::string Name;
Node *leftPtr,*rightPtr;
};
void add(int,char *,Node **);
void outv(Node *);
void outu(Node *);
void outtr(Node *,int,int,int);
void del(Node **,int );
//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{ int dat,d;
  char *nam=new char(sizeof(char));
 Node *root=NULL;
   for (int i=0;i<10;i++)
   { cout<<"Data file: ";
     cin>>dat;
     cout<<"Name file: ";
     cin>>nam;
      add(dat,nam,&root); }
      cout<<"Vozrastanie:"<<endl;
       outv(root);
      cout<<endl<<"Ubyvanie:"<<endl;
       outu(root);
       clrscr();
      cout<<endl<<"Derevom:"<<endl;
      outtr(root,1,80,7);
      cout<<"Delete all file do daty: ";
      cin>>d;
        del(&root,d);
        clrscr();
        cout<<endl<<"Derevom:"<<endl;
      outtr(root,1,80,7);
        getch();
        return 0;
}

void add(int a,char *b,Node **ptr)
{int c;
 if (!*ptr){
 if((*ptr= new Node)==NULL)
 {cout<<"Memory don't have!Exit..."<<endl;
 return;}
 (*ptr)->Data=a;
 (*ptr)->Name=b;
 (*ptr)->leftPtr=(*ptr)->rightPtr=NULL;
 }
  else
   { c=((*ptr)->Data)-a;
     if (c>0) add(a,b,&((*ptr)->leftPtr));
     else if (c<0) add(a,b,&((*ptr)->rightPtr));
      else cout<<"Element: "<<a<<" duble!"<<endl;}
}

void outv(struct Node *ptr)
{
if(ptr->leftPtr) outv(ptr->leftPtr);
cout<<ptr->Data<<' ';
cout<<ptr->Name<<' ';
if(ptr->rightPtr) outv(ptr->rightPtr);
}

void outu(struct Node *ptr)
{
if (ptr->rightPtr) outu(ptr->rightPtr);
cout<<ptr->Data<<' ';
cout<<ptr->Name<<' ';
if (ptr->leftPtr) outu(ptr->leftPtr);
}

void  outtr(Node *ptr,int lb,int rb,int r)
{if(ptr)
 {gotoxy((lb+rb)/2,r);
 cout<<ptr->Data<<' '<<ptr->Name<<endl;
 outtr(ptr->leftPtr,lb,(lb+rb)/2,r+1);
 outtr(ptr->rightPtr,(lb+rb)/2,rb,r+1);
}
}

void del(Node **ptr,int d)
{if(!*ptr)
{cout<<"Files do date are not found!"<<endl;return;}
if (d<(*ptr)->Data) del(&(*ptr)->leftPtr,d);
else if(d>(*ptr)->Data) del(&(*ptr)->rightPtr,d);
else
{Node *lt,*rt;
lt=(*ptr)->leftPtr;rt=(*ptr)->rightPtr;
delete *ptr;
*ptr=rt;
while (*ptr)
ptr=&(*ptr)->leftPtr;
*ptr=lt;
}
}
//------------------------

Помогите как лучше реализовать поиск и удаления по такой критерии:
Мне надо удалить все поддеревья число которово до числа введенного с
клавиатуры..

Жду....Заранее благодарен

_hunter

Дата 16.12.2005, 16:29 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 8564
Регистрация: 24.6.2003
Где: Europe::Ukraine:: Kiev

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

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

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

Tempora mutantur, et nos mutamur in illis...

byNet

Дата 19.12.2005, 11:18 (ссылка)

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

Загрузка ...

Шустрый

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

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

Если не трудно приведи код Спасибо

byNet

Дата 21.12.2005, 17:03 (ссылка)

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

Загрузка ...

Шустрый

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

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

_hunter Если нетрудно приведи код

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