Страницы

Поиск по вопросам

вторник, 31 декабря 2019 г.

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

#бинарное_дерево #cpp 


По заданию требуется реализовать бинарное дерево для хранения и операций с данными
вида: Деталь, Количество, Поставщик(С++). Я составила фрагмент программы нахождения
имени поставщика , который поставляет наибольшее количество деталей
    struct Ttree *Ttree_max (struct Ttree *temp)
    {
        if (temp==NULL)
        return NULL;
        while (temp->right!= NULL) 
        temp= temp-> right;
        return temp;
    }

Однако такой вариант не подходит, необходимо это сделать методом рекурсии, составить
функцию, проверяющую всех поставщиков (Name) методом обхода всего дерева с вызовом
функции подсчета количества деталей (Const) по каждому поставщику(Name). В процессе
подсчета запомнить элемент с наибольшим количеством, а в конце вывести его на экран(Name).
Помогите разобраться.
Вот часть кода программы:
    #include 
    #include 
    #include 
    using namespace std;

    struct Ttree 
{   int Const;      
    char Name[30];      
    char Detal[30];      
    struct Ttree *left;   
    struct Ttree *right;

};
    struct Ttree* add
    (
     Ttree *beg, int Const, char Name[30], char Detal[30]
    )

   {
      if (!beg) 
        {               
           struct Ttree *temp = new Ttree;
          temp->Const = Const;
          strcpy_s(temp->Name, 30, Name);
          strcpy_s(temp->Detal, 30, Detal);

          temp->left = 0;
          temp->right = 0;
          return temp;
        }
     else if ((Const)>(beg->Const)) 
        {                 
          beg->right = add(beg->right, Const, Name, Detal);
          return beg;
        }
     else 
        {        
          beg->left = add(beg->left, Const, Name, Detal);
          return beg;
        }
    }

___....____
    struct Ttree *Ttree_max (struct Ttree *temp)
    {
        if (temp==NULL)
        return NULL;
        while (temp->right!= NULL) 
        temp= temp-> right;
        return temp;
    }


Ответы

Ответ 1


Чтобы найти Name поставщика с максимальным количеством деталей, необходимо запомнить
текущий максимум и пройтись по всему дереву, заменяя максимум при нахождении большего
количества. Это делается примерно так:
#include 
using namespace std;

void find_max(struct TTree *tree, map &strmap, struct Ttree *max)
{
    if (tree == NULL)
        return;
    string str(tree->Name);
    if (strmap.count(str) == 0)
        strmap[str] = tree->Const;
    else
        strmap[str] += tree->Const;
    if (max == NULL)
        max = tree;
    else
    {
        string maxstr(max->Name);
        if (strmap[str] > strmap[maxstr])
            max = tree;
    }
    find_max(tree->right, strmap, max);
    find_max(tree->left, strmap, max);
}

int main(int argc; char **argv)
{
    map names_map;
    struct Ttree *tree;
    fill_tree_initial(tree); // это, я надеюсь, вы реализуете сами
    struct Ttree *max = tree;
    find_max(tree);
    puts(max->Name);
    return 0;
}

Ключевым элементом здесь является map &strmap, которая содержит агрегируемые
значения целочисленного типа по каждому поставщику. Заполнение, конечно, получилось
слегка сумбурным, но хороший стиль программирования требует поступать именно так (мы
не можем гарантировать, что в max не будет нуля).


Ответ 2


@Danatela, набросал на скорую руку.
#include 
#include 
#include 
#include 

struct tnode {
  struct tnode *left, *right;
  void *data;
};

struct tdata {
  char sup_name[20], det_name[30];
  unsigned int amount;
};

typedef int (*bt_cmp)(void *data, void *tree_data);

static void
bt_add (struct tnode *root, struct tnode *t, bt_cmp cmp)
{
  if (cmp(t->data, root->data) > 0) {
    if (root->right)
      bt_add(root->right, t, cmp);
    else
      root->right = t;
  } else {
    if (root->left)
      bt_add(root->left, t, cmp);
    else
      root->left = t;
  }
}

static int cmp_amount (void *data, void *tree_data) {
  struct tdata *p = (struct tdata *)data, 
    *q = (struct tdata *)tree_data;

  return p->amount - q->amount;
}

static int cmp_sup (void *data, void *tree_data) {
  struct tdata *p = (struct tdata *)data, 
    *q = (struct tdata *)tree_data;

  return strcmp(p->sup_name, q->sup_name);
}

static int cmp_detail (void *data, void *tree_data) {
  struct tdata *p = (struct tdata *)data, 
    *q = (struct tdata *)tree_data;

  return strcmp(p->det_name, q->det_name);
}

struct tdata *
get_record ()
{
  struct tdata s, *r;
  char str[LINE_MAX];

  fputs("Enter supplier, detail, amount : ", stdout);
  while (fgets(str, LINE_MAX, stdin)) {
    if (sscanf(str, "%s %s %u", s.sup_name, s.det_name, &s.amount) == 3) {
      r = (struct tdata *)malloc(sizeof(*r));
      memcpy(r, &s, sizeof(*r));
      return r;
    }
    puts("Invalid input, try again");
  }

  return 0;
}

static void
add_tree (struct tnode **root, struct tdata *sup, bt_cmp cmp)
{
  struct tnode *p = (struct tnode *)calloc(1, sizeof(*p));
  p->data = (void *)sup;
  if (*root)
    bt_add(*root, p, cmp);
  else
    *root = p;
}

static void 
pri_tree (struct tnode *t, int level)
{
  if (t) {
    pri_tree(t->left, level + 1);
    int i;
    for (i = 0; i < level; i++)
      fputs("  ", stdout);
    struct tdata *d = (struct tdata *)t->data;
    printf ("%s %s %u\n", d->sup_name, d->det_name, d->amount);
    pri_tree(t->right, level + 1);
  }
}

static void 
find_max (struct tnode *t, struct tdata **dmax)
{
  if (t) {
    find_max(t->left, dmax);
    find_max(t->right, dmax);
    struct tdata *d = (struct tdata *)t->data;
    if (d->amount > (*dmax)->amount)
      *dmax = d;
  }
}

int
main (int ac, char *av[])
{
  struct tdata *sup;
  struct tnode *atree = 0, *dtree = 0;

  while(sup = get_record()) {
    add_tree(&atree, sup, cmp_amount);
    add_tree(&dtree, sup, cmp_detail);
  }
  puts("");
  if (!atree)
    return 0;

  puts ("amount tree");
  pri_tree(atree, 0);

  puts ("detail tree");
  pri_tree(dtree, 0);

  struct tdata *mxsup = (struct tdata *)atree->data;

  struct tnode *t = atree;
  while (t->right) { // amount tree
    mxsup = (struct tdata *)t->right->data;
    t = t->right;
  }
  printf ("atree: %s supplier is max: %d\n", mxsup->sup_name, mxsup->amount);

  mxsup = (struct tdata *)dtree->data;
  find_max(dtree, &mxsup); 
  printf ("dtree: %s supplier is max: %d\n", mxsup->sup_name, mxsup->amount);

  return puts("") == EOF;
}

Очевидно, что find_max и pri_tree можно тоже реализовать через обобщенную функцию,
скажем, tree_travers с callback-ами для обработки каждого посещаемого узла.
Аналогично можно делать и функцию удаления дерева и данных его узлов для освобождения
памяти (здесь я их не писал).
Сейчас подробнее некогда, появлюсь в воскресенье вечером
UPDATE
@LHh,
Код для построения дерева суммарных поставок каждым поставщиком
и поиска поставляющего максимальное количество деталей.
struct sumsup { // дерево суммарных поставок по поставщикам
  struct sumsup *left, *right;
  char *name; // указатель на имя в узле дерева поставок
  int  sum;
};

// сделаем новый узел дерева суммарных поставок по поставщикам
// скорректируем текущий максимум (если новый поставщик сразу MAX)
struct sumsup *
make_sup (struct tdata *d, char **mxname, int *max)
{
  struct sumsup *r = (struct sumsup *)calloc(1, sizeof(*r));
  r->name = d->sup_name;
  if ((r->sum = d->amount) > *max) {
    *max = r->sum;
    *mxname = r->name;
  }

  return r;
}

// рекурсивный обход дерева поставок
void 
max_sum (struct tnode *t, struct sumsup **ps, char **mxname, int *max) 
{
  if (t) {
    if (!*ps) { // init
      *ps = make_sup((struct tdata *)t->data, mxname, max);
      // это нужно для правильной обработки корня дерева суммарных поставок
      // т.к. он будет найден в начале обработки дерева 
      // и эта поставка не должна удваиваться
      *max = (*ps)->sum = 0;
    }
    int r;
    char *nm = ((struct tdata *)t->data)->sup_name;
    struct sumsup *p = *ps; // дерево суммарных поставок по поставщикам

    // итеративный поиск в дереве суммарных поставок по поставщикам
    while (r = strcmp(nm, p->name)) {
      if (r < 0) {
        if (p->left)
          p = p->left;
        else {
          // и достраивание этого дерева
          p->left = make_sup((struct tdata *)t->data, mxname, max);
          break;
        }
      } else {
        if (p->right)
          p = p->right;
        else {
          // если такого поставщика в нем еще нет
          p->right = make_sup((struct tdata *)t->data, mxname, max);
          break;
        }
      }
    }
    if (!r) // или увеличение суммы поставок найденного поставщика
      if ((p->sum += ((struct tdata *)t->data)->amount) > *max) {
        *max = p->sum;
        *mxname = nm;
      }

    max_sum(t->left, ps, mxname, max);
    max_sum(t->right, ps, mxname, max);
  }
}

void 
del_sumtree (struct sumsup *t)
{
  if (t) {
    del_sumtree(t->left);
    del_sumtree(t->right);
    free(t);
  }
}

void 
del_tree (struct tnode *t, int data)
{
  if (t) {
    del_tree(t->left, data);
    del_tree(t->right, data);
    if (data)
      free(t->data);
    free(t);
  }
}

А это код в конец main() для вызова построения дерева сумм поставок по
всем поставщикам и поиска максимума
  struct sumsup *sumtree = 0;
  char *mxsupname = 0;
  int   maxsum;

  max_sum(atree, &sumtree, &mxsupname, &maxsum);
  printf("greatest: %s (%d)\n", mxsupname, maxsum);

  del_sumtree(sumtree);
  del_tree(atree, 0);
  del_tree(dtree, 1);

UPDATE 2
@LHh, пожалуй, вот такой код построения дерева суммарных поставок выглядит более
логичным (и к тому же он короче).
// рекурсивный обход дерева поставок
void 
max_sum (struct tnode *t, struct sumsup **ps, char **mxname, int *max) 
{
  if (t) {
    struct sumsup *p;

    if (p = *ps) { // дерево суммарных поставок по поставщикам уже существует
      int r;
      char *nm = ((struct tdata *)t->data)->sup_name;

      // итеративный поиск в дереве суммарных поставок по поставщикам
      while (r = strcmp(nm, p->name)) {
        if (r < 0) {
          if (p->left)
            p = p->left;
          else {
            // и достраивание этого дерева
            p->left = make_sup((struct tdata *)t->data, mxname, max);
            break;
          }
        } else {
          if (p->right)
            p = p->right;
          else {
            // если такого поставщика в нем еще нет
            p->right = make_sup((struct tdata *)t->data, mxname, max);
            break;
          }
        }
      }
      if (!r) // или увеличение суммы поставок найденного поставщика
        if ((p->sum += ((struct tdata *)t->data)->amount) > *max) {
          *max = p->sum;
          *mxname = nm;
        }
    } else // создаем корень дерева поставок
      *ps = make_sup((struct tdata *)t->data, mxname, max);

    max_sum(t->left, ps, mxname, max);
    max_sum(t->right, ps, mxname, max);
  }
}

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

Автор: на
Ярлыки: , ,

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)