witam mam program drzewo BST w C ktory rysuje drzewo dodaje/usuwa elementy laczy dwa podrzewa w jedno-balansuje musze zbadac jak zmienia sie wysokosc drzewa i potrzebna do tego mi jest do tego funkcja czasowa Oto kod drzewa(troszke zamotany pewnie zamiast root powinno byc drzewo itd niestety slabo znam C i funkcjonowanie drzew bst wiec jesli ktos moze troszke ten kod poprawic bede wdzieczny)- ale dziala i kompiluje sie on w putty gcc nazwaprog.c -lm -lncurses. zalaczam tez program ktory posiada taka funkcje czasowa lecz jak mowilem jestem slaby z c i nie wiem jak to razem skleic chodzi mi o stworzenie z tych 2 drzewa bst z funkcja czasu z gory dzieki za pomoc
drzewo bst
#include<stdio.h>
#include<stdlib.h>
#include<curses.h>
#include<math.h>
#include<setjmp.h>
#include<signal.h>
#include<sys/types.h>
typedef struct wezel * root;
typedef struct wezel
{
char d;
int licznik;
root lewy, prawy;
} wezel;
char selectN(root ,int);
void wstaw (root *, char);
void lew_rot(root *);
void pr_rot(root *);
void balansuj(root *);
void wstaw_pr (root *, char );
void usun_pr (root *);
void wyswietl(root);
void destroy(root);
int wys_drzewa(root);
void generuj(root *);
sigjmp_buf env;
void redraw(int sig)
{
endwin();
refresh();
siglongjmp(env, 1);
}
main()
{
int wysokosc,rzad,kolumna;
char d='f';
char sel='.';
char w='.';
root glowa=NULL;
sigset_t oset;
signal(SIGWINCH,redraw);
sigprocmask(0,NULL,&oset);
initscr();
cbreak();
noecho();
raw();
generuj(&glowa);
sigsetjmp(env,1);
switch(d)
{
case 'l':
lew_rot(&glowa); break;
case 'r':
pr_rot(&glowa); break;
case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':
sel=selectN(glowa,(int)d-'0'); break;
case 'b':
balansuj(&glowa); break;
case 'w':
wstaw(&glowa,(w=97+rand()%25));break;
case 'k':
wstaw_pr(&glowa,(w=97+rand()%25));break;
case 'u':
usun_pr(&glowa); break;
default: break;
}
wyswietl(glowa);
getmaxyx(stdscr,rzad,kolumna);
mvprintw(rzad-2,0,"'spacja': koniec,'l': rotacja lewa,'r': rotacja prawa,\
'b': balansowanie \n 'w': wstawianie 'k': wstaw l. w. do korzenia 'u': usuwanie");
mvprintw(rzad-4,0,":::%c:::",sel);
mvprintw(rzad-6,0,":::%c:::",w);
refresh();
while((d=getch())!=' ');
endwin();
destroy(glowa);
}
typedef struct qwezel * qroot;
struct qwezel
{
root d;
qroot next;
} qwezel;
struct queue
{
qroot glowa;
qroot ogon;
}queue;
void generuj(root *glowa)
{
int rzad,kolumna,j=0,i,wysokosc;
char d;
getmaxyx(stdscr,rzad,kolumna);
srand(time(NULL));
while(j++<50)
{
for (i=0;i<10;i++)
{
d=97+rand()%25;
wstaw(glowa, d);
}
wysokosc=wys_drzewa((*glowa));
printw("%d\n",wysokosc);
refresh();
if(pow(2,(double)wysokosc)<2*kolumna+2)return;
else if(j!=999){destroy((*glowa));*glowa=NULL;}
}
}
void wstaw (root *h, char d)
{
if (*h == NULL)
{
*h =(root) malloc(sizeof(wezel));
(*h)->lewy=NULL;
(*h)->prawy=NULL;
(*h)->d=d;
(*h)->licznik=1;
return;
}
(*h)->licznik+=1;
if (((*h)->d)>d) wstaw(&((*h)->lewy),d);
else wstaw(&((*h)->prawy),d);
}
int wys_drzewa(root h)
{
int wysokosc=-1,l=0,p=0;
if (h==NULL) return wysokosc;
return ((l=wys_drzewa(h->lewy))>(p=wys_drzewa(h->prawy))) ? l+1 : p+1;
}
void destroy(root h)
{
if (h==NULL)return;
destroy(h->lewy);
destroy(h->prawy);
free(h);
}
void wypisz(root h,int y,int x,int poziom)
{
if(h==NULL)return;
poziom/=2;
x=x+3;
wypisz(h->lewy,y-poziom,x,poziom);
mvprintw (x,y, "%c", h->d);
mvprintw (x+1,y, "%d", h->licznik);
wypisz(h->prawy,y+poziom,x,poziom);
}
void wyswietl(root h)
{
int rzad,kolumna,wysokosc;
clear();
getmaxyx(stdscr,rzad,kolumna);
wysokosc=wys_drzewa(h);
if(pow(2,(double)wysokosc)>1+kolumna/2){mvprintw(0,0,"Za duze drzewo do narysowania");return;}
wypisz(h,kolumna/2,0,pow(2,(double)wysokosc));
refresh();
}
void lew_rot(root *h)
{
int t;
root tmp;
if (*h==NULL) return;
if ((*h)->prawy==NULL)return;
tmp=(*h)->prawy->lewy;
(*h)->prawy->lewy=*h;
*h=(*h)->prawy;
(*h)->lewy->prawy=tmp;
(*h)->licznik=(*h)->lewy->licznik;
(*h)->lewy->licznik = 1;
(*h)->lewy->licznik += ((*h)->lewy->lewy !=NULL) ? (*h)->lewy->lewy->licznik : 0;
(*h)->lewy->licznik += ((*h)->lewy->prawy !=NULL) ? (*h)->lewy->prawy->licznik : 0 ;
}
void pr_rot(root *h)
{
root tmp;
if (*h==NULL) return;
if ((*h)->lewy==NULL)return;
tmp=(*h)->lewy->prawy;
(*h)->lewy->prawy=*h;
*h=(*h)->lewy;
(*h)->prawy->lewy=tmp;
(*h)->licznik=(*h)->prawy->licznik;
(*h)->prawy->licznik = 1;
(*h)->prawy->licznik += ((*h)->prawy->lewy !=NULL) ? (*h)->prawy->lewy->licznik : 0;
(*h)->prawy->licznik += ((*h)->prawy->lewy !=NULL) ? (*h)->prawy->prawy->licznik : 0 ;
}
char selectN (root h,int k)
{
int l;
if (h==NULL) return -1;
l= (h->lewy==NULL) ? 0 : h->lewy->licznik ;
if (k<l+1) return selectN(h->lewy,k);
if (k>l+1) return selectN(h->prawy,k-l-1);
return h->d;
}
root search(root h, char d)
{
if (h==NULL) return NULL;
if (d<h->d) return search(h->lewy, d);
if (d>h->d) return search(h->prawy, d);
if (d==h->d) return h;
}
void partR (root *h,int k)
{
int l;
if ((*h)==NULL) return;
l= ((*h)->lewy==NULL) ? 0 : (*h)->lewy->licznik ;
if (k<l+1){ partR(&(*h)->lewy,k);pr_rot(h); }
if (k>l+1){ partR(&(*h)->prawy,k-l-1);lew_rot(h); }
}
void balansuj (root *h)
{
if (*h==NULL) return;
partR(h,(1+(*h)->licznik)/2);
balansuj(&(*h)->lewy);
balansuj(&(*h)->prawy);
}
void wstaw_pr (root *h, char d)
{
if (*h == NULL)
{
*h =(root) malloc(sizeof(wezel));
(*h)->lewy=NULL;
(*h)->prawy=NULL;
(*h)->d=d;
(*h)->licznik=1;
return;
}
(*h)->licznik+=1;
if (((*h)->d)>d)
{ wstaw_pr(&((*h)->lewy),d); pr_rot(h); }
else
{wstaw_pr(&((*h)->prawy),d); lew_rot(h); }
}
void usun_pr (root *h)
{
root tmp;
if (*h==NULL) return;
if ((*h)->prawy==NULL) { tmp=*h; *h=(*h)->lewy; free(tmp); return;}
if ((*h)->lewy==NULL) { tmp=*h; *h=(*h)->prawy; free(tmp); return;}
partR(h,2+(*h)->lewy->licznik);
tmp=(*h)->lewy;
(*h)->licznik-= 1;
(*h)->lewy=(*h)->lewy->lewy;
free(tmp);
}
prog z f czasowa
#include<stdint.h>
#include<sys/times.h>
#include<unistd.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
__inline__ uint64_t rdtsc()
{
uint32_t lo, hi;
__asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
return (uint64_t)hi << 32 | lo;
}
void shellsort(int *,int);
void randomgen(int *, int);
main()
{
int *t;
int i,n,r;
unsigned long long cykle;
clock_t time;
printf("Podaj rozmiar tablicy: ");
fflush(stdout);
scanf("%d",&n);
t=(int*)calloc(4,n);
randomgen(t,n);
#ifdef TEST
for(i=0;i<n;i++)
printf("%d\n",t[i]);
printf("\n");
#endif
time=clock();
cykle=rdtsc();
shellsort(t,n);
cykle=rdtsc()-cykle;
time=clock()-time;
#ifdef TEST
printf("\n");
for(i=0;i<n;i++)
printf("%d\n",t[i]);
#endif
printf ("\nCzas dzialania, funkcja clock: %.10f\n",(double)( (time + 0.0) / CLOCKS_PER_SEC));
printf("\nIlosc cykli procesora, funkcja rdtsc: %lld\n",cykle);
}
void randomgen(int *t, int n)
{
int i;
srand(time(NULL));
for(i=0;i<n;i++)
t[i]= (int) ((double)n * (rand() / (RAND_MAX + 1.0)));
return;
}
void shellsort(int *t,int n)
{
int i,p,temp,gap;
for(gap=1;gap<(n/4);gap=4*gap+1);
for(;gap>0;gap=gap/4)
{
for(i=gap;i<n;i++)
{
p=i;temp=t[i];
for (;(p-gap>=0)&&(temp<t[p-gap]);t[p]=t[p-gap],p-=gap);
t[p]=temp;
}
}
}