Hej cześć i czołem.
Zacząłem implementować sobie drzewo binarne i raczej algorytm dodawania jest poprawny na 90%, ale z wyszukiwaniem są jakieś problemy. znalazłaby się jakaś pomocna duszyczka, która pomogłaby mi szukać błędu?
OPIS ALGORYTMU PRZESKAKUJACEGO PO KOMORKACH:
Jak dziala algorytm wyszukujacy odpowiednie komorki?
ustawiamy wartosci na:
poprzedni_przeskok=1;
komorka =0;
[kod]
Jezeli poprzedni wynik dal wiekszy{
jezeli aktulny wynik dal wiekszy:
poprzedni_skok*=2;
jezeli aktulny wynik dal mniejszy:
poprzedni_skok=2*poprzedni_skok-1;
}
Jezeli poprzedni wynik dal mniejszy{
jezeli aktulny wynik dal wiekszy:
poprzedni_skok=2*poprzedni_skok+1;
jezeli aktulny wynik dal mniejszy:
poprzedni_skok*=2;
}
komorka+=poprzedni_skok;
[/kod]
!!!!UWAGA!!!!UWAGA!!!!
przy pierwszym porównaniu zakładamy, że poprzedni wynik dal wiekszy.
przy podaniu malej ilosci komorek/poziomow program czesto sie wysypuje, poniewaz przekraczamy tablice
KOD:
#include <iostream>
#include <conio.h>
#include <math.h>
#include <string>
using namespace std;
void wpakuj_to_gdzies(string, string[]); //dodaje stringa do podanej tablicy
int szukaj(string, string[]); //szuka stringa w podanej tablicy, zwraca nr komorki w tablicy lub -1, jezeli go nie znajdzie
int main()
{
string szuk_wyr;
string wyraz; //bedzie to na bierzaco wprowadzany wyraz
int n;
int dlugosc_tab=1;
bool wybor;
cout << "Tworzenie drzewa (wersja easy - na tablicy statycznej)..."<<endl;
cout << "Wybierz:"<<endl;
cout << "0 - ilosc poziomow drzewa"<<endl;
cout << "1 - ilosc elementow"<<endl;
cin>>wybor;
cout<<endl<<"podaj ilosc: ";
cin>>n;
//wyliczanie dlugosci tablicy
if(wybor==0){
for(int i=1;i<n;i++){
dlugosc_tab+=pow(2,i);
}
}
else if(wybor==1){
{
int i=1;
while(dlugosc_tab<=n){
dlugosc_tab+=pow(2,i);
i++;
}
}
}
string * tablica = new string[dlugosc_tab];
cout<<endl<<"podaj szukany wyraz: ";cin>>szuk_wyr;
int nr_wyrazu=1;
cout<<"wygenerowana dlugosc tablicy to:"<<dlugosc_tab<<endl;
cout<<"co petle uzyta jest funkcja getch(), nacisnik ESC, aby przerwac dodawanie"<<endl;
cout<<"podczas dodawania wiekszej ilosci znakow moze to irytowac"<<endl;
cout<<"ale pozwala na zakonczenie dodawania przed wypelnieniem tablicy w calosci"<<endl;
while(nr_wyrazu<=dlugosc_tab){
if(getch()==27)break;
cout<<"podaj "<<nr_wyrazu<<". wyraz: ";cin>>wyraz;
wpakuj_to_gdzies(wyraz, tablica);
nr_wyrazu++;
}
cout<<szukaj(szuk_wyr,tablica);
getch();
return 0;
}
//Ww = "wkladana wartosc" itp
void wpakuj_to_gdzies(string wyr, string tab[]){
int porownaj=0;
int poprzedni_skok=1;
bool prawda=false;
bool poprzednia_wieksza=true;
while(!prawda){
if(tab[porownaj]==""||tab[porownaj]==wyr){ //jezeli pole jest puste lub rowne aktualnie Ww, tzn ze znaleziono miejsce dla naszego wyrazu
prawda=true;
tab[porownaj]=wyr;
}
else if(poprzednia_wieksza){
if(wyr.compare(tab[porownaj])==1){//Ww wiekszy
poprzedni_skok*=2;
poprzednia_wieksza=true;
}
else if(wyr.compare(tab[porownaj])==-1){//Ww mniejszy
poprzedni_skok=2*poprzedni_skok -1;
poprzednia_wieksza=false;
}
}
else if(!poprzednia_wieksza){
if(wyr.compare(tab[porownaj])==1){//Ww wiekszy
poprzedni_skok=2*poprzedni_skok+1;
poprzednia_wieksza=true;
}
else if(wyr.compare(tab[porownaj])==-1){//Ww mniejszy
poprzedni_skok*=2;
poprzednia_wieksza=false;
}
}
porownaj+=poprzedni_skok;
}
}
int szukaj(string wyr, string tab[]){
int porownaj=0;
int poprzedni_skok=1;
bool prawda=false;
bool poprzednia_wieksza=true;
while(!prawda){
if(tab[porownaj]==""){ //jezeli pole jest puste lub rowne aktualnie Ww, tzn ze znaleziono miejsce dla naszego wyrazu
return -1;
}
if(wyr.compare(tab[porownaj])==0)return porownaj;
else if(poprzednia_wieksza){
if(wyr.compare(tab[porownaj])==1){//Ww wiekszy
poprzedni_skok*=2;
poprzednia_wieksza=true;
}
else if(wyr.compare(tab[porownaj])==-1){//Ww mniejszy
poprzedni_skok=2*poprzedni_skok -1;
poprzednia_wieksza=false;
}
}
else if(!poprzednia_wieksza){
if(wyr.compare(tab[porownaj])==1){//Ww wiekszy
poprzedni_skok=2*poprzedni_skok+1;
poprzednia_wieksza=true;
}
else if(wyr.compare(tab[porownaj])==-1){//Ww mniejszy
poprzedni_skok*=2;
poprzednia_wieksza=false;
}
}
porownaj+=poprzedni_skok;
}
return -1;
}