25.09.2012, 19:07 | #1 (permalink) |
404
Регистрация: 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; } |
25.09.2012, 19:07 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
В похожих темах обычно много интересных советов Бинарные файлы, язык Си Задание на деревья Двоичные деревья - Pascal |
27.09.2012, 07:04 | #3 (permalink) |
404
Регистрация: 10.01.2010
Сообщений: 1,749
Записей в дневнике: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 3868
|
Блин, еще раз:
не работает именно итеративный метод и именно он нужен по лабораторке. Где-то при вызове процедуры косяк, а где не вижу. |
05.10.2012, 11:07 | #5 (permalink) |
404
Регистрация: 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; } } Переработанный исходник в аттаче: |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|