Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Не работают типовые алгоритмы построения деревьев (взяты с сайтов)  (Прочитано 3856 раз)
0 Пользователей и 1 Гость смотрят эту тему.
eugrita
Помогающий

ru
Offline Offline

« : 18-12-2009 11:26 » 

Не работают типовые алгоритмы построения деревьев в программах под C (не C++). Обе взяты с сайтов.
Tree2.c (с небольшими модификациями под С - с comp-science.narod.ru/Progr/BinTree.htm
Tree1.c (в 2х вариантах подC и под С++) с сайта khpi-iip.mipk.kharkiv.edu/library/datastr/book_sod/kgsu/din_0041.html
в Tree1.c, Tree1.cpp валится на *Tree = NULL; //в посылке закомментирован
и на *p==NULL в void Search
Такое впечатление, что данный тип данных не может сравниваться с NULL
1. Программы Tree1.c,  Tree1.cpp не срабатывают при выполнении на  операторе *Tree = NULL, а также при его отмене на операторе  *p==NULL в void Search
2. Программы Tree2.c не срабатывают при выполнении на  операторе  if (A->inf < vsp->inf)
при этом A->inf =5 а vsp->inf не определено!!! несмотря на выполненное  присваивание vsp = T;
Компилятор Borland C++ Builder v.6 под Windows
------------------------------
Код:
//Tree1.c
#include <stdlib.h>
//khpi-iip.mipk.kharkiv.edu/library/datastr/book_sod/kgsu/din_0041.html
struct node
    {
        int Key; // Ключ вершины.
        int Count; // Счетчик количества вершин с одинаковыми ключами.
        struct node *Left; // Указатель на "левого" сына.
        struct node *Right; // Указатель на "правого" сына.
    };
void Search (int x, struct node **p);

void Search (int x, struct node **p)
// Поиск вершины с ключом x в дереве со вставкой (рекурсивный алгоритм).
// *p - указатель на корень дерева.
{
  if (*p==NULL)
  { // Вершины с ключом x в дереве нет; включить ее.
    *p = (struct node *) malloc (sizeof(struct node));
    (**p).Key = x; (**p).Count = 1;
    (**p).Left = (**p).Right = NULL;
  }
  else //Поиск места включения вершины.
    if (x<(**p).Key) //Включение в левое поддерево.
       Search (x,&((**p).Left));
    else if (x>(**p).Key) //Включение в правое поддерево.
           Search (x,&((**p).Right));
         else (**p).Count = (**p).Count + 1;
}

void main()
{ // Постр бинарного дерева. *Tree - указатель на корень дерева.
   struct node **Tree;
   int el[]={5,4,7,2,3,10,8,9,6,-2,20,-5,12,-15,0};
   int i;
 // *Tree = NULL; // Построено пустое бинарное дерево.
  for (i=0;i<=14;i++)
     { Search (el[i],Tree); }
  getch();
}
-----------------------------------------------
//Tree2.c
#include <stdlib.h>
//comp-science.narod.ru/Progr/BinTree.htm
struct BTree
{
  int inf;
  struct BTree *L; struct BTree *R;
};

struct BTree* InsIter(struct BTree *T,int x)
{/* Итеративный вар добавл эл в дерево, C++ */
 struct BTree *vsp, *A;
  A = (struct BTree *) malloc(sizeof(struct BTree));
  A->inf=x; A->L=0; A->R=0;
  if (!T)
    T=A;
  else         {
  vsp = T;
  while (vsp != NULL)
   {
    if (A->inf < vsp->inf)
    if (!vsp->L)
      {vsp->L=A; vsp=A->L;}
   else vsp=vsp->L;
   else if (!vsp->R)
       {vsp->R=A; vsp=A->R;}
        else vsp=vsp->R;
   }//while
                }
return T;
}

void main()
{
  struct BTree **T;
   int el[]={5,4,7,2,3,10,8,9,6,-2,20,-5,12,-15,0};
   int i;
 // *T = NULL;
  for (i=0;i<=14;i++)
     { InsIter(T,el[i]); }
}
« Последнее редактирование: 18-12-2009 16:45 от eugrita » Записан
eugrita
Помогающий

ru
Offline Offline

« Ответ #1 : 18-12-2009 17:35 » 

Попытался работать с компилятором Dev 4.9.9.2
Указанные выше операторы пропускает, т.е. программа выполняется
Так как она ничего не выводит на печать, добавил рекурсивную процедуру печати
Код:
void TreePrint(node **p)//печать
{
  if (*p==NULL)
          return;
  printf("%i\n",(**p).Key);
  TreePrint(&(**p).Left) ;  TreePrint(&(**p).Right) ;
}
наверное можно было и так написать
void TreePrint(node *p)
{
  if (p==NULL)
          return;
  printf("%i\n",p->Key);
  TreePrint(p->Left) ;  TreePrint(p->Right) ;
}
печатает 0 в конце же валится
« Последнее редактирование: 18-12-2009 18:55 от Sel » Записан
Sands
Помогающий

ua
Offline Offline

« Ответ #2 : 20-12-2009 00:00 » 

1) По поводу проблемм с Tree1.c. Думаю, это связано с тем, что Tree обьявляется как
Код:
struct node **Tree;
то есть, указатель на указатель, а потом в ячейку, на которую он указывает, пытаются внести NULL. Но, по идее, этот указатель не указывает никуда, ибо он не проинициализирован.
Варианты исправления:
либо выделить память под один элемент типа node*, либо изменить обьявление на
Код:
struct node *Tree = NULL;
а в функцию Search передавать не Tree а &Tree.

2) Относительно Tree2.c.
Функция InsIter обьявляется как
Код:
struct BTree* InsIter(struct BTree *T,int x)
но потом в функции main() в нее вместо BTree* пытаются передать BTree**. Наверное, из-за этого все и валится.
« Последнее редактирование: 20-12-2009 06:52 от Sel » Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines