Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > C/C++/С#


Ответ
 
Опции темы Опции просмотра
Старый 25.09.2012, 19:07   #1 (permalink)
Fenix
404
 
Аватар для Fenix
 
Регистрация: 10.01.2010
Сообщений: 1,749
Записей в дневнике: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 3868
По умолчанию Бинарные деревья

Доброго времени суток! Собственно прошу указать на ошибку (что-то идиотское упускаю)
Ошибка в том, что после выполнения процедуры итеративного построения случайного дерева поиска затирается адрес корня дерева.
vertex *AddVertex - процедура итеративного построения
//create BST - после этого комментария идет косячный блок

В работоспособности процедуры построения уверен на 95%.
За ранее спасибо!

Код:
/*** sapd - lab_2 ***/
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

struct vertex //структура дерева
            {
             vertex *left;
             vertex *right;
             int data;
            } *root,*sroot, *sroot1 ;   
int array[SIZE];

//create tree 
vertex *IDSP(int L, int R) 
{
 int i;      
 vertex *r;
 if(L>R) return NULL;
 else 
 {
  i=(L+R)/2;
  r=new vertex;
  r->data=array[i];
  r->left=IDSP(L,i-1);
  r->right=IDSP(i+1,R);
  return r;
 }
}

//create binare search tree
vertex *AddVertex(int data, vertex *root)
{
 vertex **p;
 p=&root;
 while(*p!=NULL)
 {
  if(data<(*p)->data) p=&((*p)->left);
  if(data>(*p)->data) p=&((*p)->right);
  else break;
 }
 if(*p==NULL)
 {
  *p=new vertex;
  if((*p)==NULL)   
  {
   printf("Error 0x42! Not enought memory!\n");
  }
  (*p)->data=data;
  (*p)->right=NULL;
  (*p)->left=NULL;
  //printf("%4d",(*p)->data);
 }
}

vertex *AddVertexRec(int data, vertex *&p) 
{
 if(!p) 
 {
  p=new vertex;
  if(p==NULL)   
  {
   printf("Error 0x42! Not enought memory!\n");
  }
  p->data=data;
  p->left=NULL;
  p->right=NULL;
 }
 else 
 { 
  if(data<p->data) AddVertexRec(data,p->left);
  else 
   if(data>p->data) AddVertexRec(data,p->right);
 }
}

//detour
void Detour(vertex *p)
{
 if(!p) return;
 Detour(p->left);
 printf("%4d",p->data);
 Detour(p->right);
} 


//size
int Size(vertex *p)
{
 if(!p) return 0;
 return 1+Size(p->left)+Size(p->right);
}

//max
int max(int a, int b) 
{
 if(a>b)return a;
 return b;
}

//height 
int Height(vertex *p)
{
 if(!p)return 0;
 return 1+max(Height(p->left),Height(p->right));
}

//midheight
float MidHeight(vertex *p, int layer)
{
 if(!p) return 0;
 return layer+MidHeight(p->left,layer+1)+MidHeight(p->right,layer+1); 
}



//MAIN
int main()
{
//create array 
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=array[i-1]+rand()%10;
  printf("%4d",array[i]);
 }
 
//create IBST 
 printf("\n");
 root=IDSP(0,SIZE-1);
 printf("tree:\n");
 Detour(root);
 printf("\ntree size: %4d",Size(root));          
 printf("\ntree height: %4d",Height(root));
 float Mheight=MidHeight(root,1)/Size(root);
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 
 
//create BST rec
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=rand()%100;
  printf("%4d",array[i]);
 }
 printf("\n");
 printf("tree:\n");
 sroot=NULL;
 for(int i=0;i<SIZE;i++)
  AddVertexRec(array[i],sroot);  
 Detour(sroot);
 printf("\ntree size: %4d",Size(sroot));          
 printf("\ntree height: %4d",Height(sroot));
 Mheight=MidHeight(sroot,1)/Size(sroot); 
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 

//create BST
 printf("\n");
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=rand()%100;
  printf("%4d",array[i]);
 }
 printf("\n");
 printf("tree:\n");
 sroot1=NULL;
 for(int j=0;j<SIZE;j++)
  AddVertex(array[j],sroot1);  
 Detour(sroot1);
 printf("\ntree size: %4d",Size(sroot1));          
 printf("\ntree height: %4d",Height(sroot1));
 Mheight=MidHeight(sroot,1)/Size(sroot1); 
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 
 
 printf("\nProgramm complite successfull.Stop 0x00\n");
 system("PAUSE");       
 return 0;
}
Исходник в аттаче.
Вложения
Тип файла: zip lw_2.zip (1.3 Кб, 4 просмотров)
Fenix вне форума   Ответить с цитированием

Старый 25.09.2012, 19:07
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

В похожих темах обычно много интересных советов

Бинарные файлы, язык Си
Задание на деревья
Двоичные деревья - Pascal

Старый 26.09.2012, 23:08   #2 (permalink)
Gruvi
VIP user
 
Аватар для Gruvi
 
Регистрация: 10.03.2011
Сообщений: 766
Записей в дневнике: 1
Сказал(а) спасибо: 10
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 3453
По умолчанию

Эмм а ты попробуй обратный выход сделать через рекурсию. обычно все бинарные деревья строятся на рекурсии.
Gruvi вне форума   Ответить с цитированием
Старый 27.09.2012, 07:04   #3 (permalink)
Fenix
404
 
Аватар для Fenix
 
Регистрация: 10.01.2010
Сообщений: 1,749
Записей в дневнике: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 3868
По умолчанию

Блин, еще раз:
не работает именно итеративный метод и именно он нужен по лабораторке.
Где-то при вызове процедуры косяк, а где не вижу.
Fenix вне форума   Ответить с цитированием
Старый 01.10.2012, 18:26   #4 (permalink)
Fenix
404
 
Аватар для Fenix
 
Регистрация: 10.01.2010
Сообщений: 1,749
Записей в дневнике: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 3868
По умолчанию

HEEEEEELLP!
Fenix вне форума   Ответить с цитированием
Старый 05.10.2012, 11:07   #5 (permalink)
Fenix
404
 
Аватар для Fenix
 
Регистрация: 10.01.2010
Сообщений: 1,749
Записей в дневнике: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 3868
По умолчанию

Всем большое спасибо за помощь! Разобрался в проблеме.
Исправлена процедура AddVertex:
Код:
void AddVertex(int data, vertex *&root)
{
 vertex **p;
 p=&root;
 while((*p)!=NULL)
 {
  if(data<(*p)->data) p=&((*p)->left);
  else
   if(data>(*p)->data) p=&((*p)->right);
   else
    if(data==(*p)->data) break;
 }
 if((*p)==NULL)
 {
  *p=new vertex;
  if((*p)==NULL)   
  {
   printf("Error 0x42! Not enought memory!\n");
  }
  (*p)->data=data;
  (*p)->right=NULL;
  (*p)->left=NULL;
  
 }
}
Красным выделены изменения в коде.
Переработанный исходник в аттаче:
Вложения
Тип файла: zip lw_2.zip (1.3 Кб, 5 просмотров)
Fenix вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 15:57.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.