Słownik w dzrzewie BST

0

Witam! Mam wielką prośbę, mam program w C: słownik ang-pol w strukturze drzewa BST, ale nie jest mój i nie wiem niektórych rzeczy, a muszę na jutro umieć go wytłumaczyć na zajęciach. Może ma ktoś prostszy niż ten to prszę o wstawienie kodu, a jeśli nie to proszę chociaż ekspertów o wytłumaczenie zaznaczonych fragmentów kodu. Z góry dziękuję.

Oto kod:

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>

struct slowa { //deklaracja struktury zawierającej
char angielskie[30]; //słowa angielskie
char polskie [3][30]; //oraz trzy tłumaczenia polskie
int liczba;
};

struct wezel{
slowa dane;
wezel left;
wezel
right;
};

wezel *r=NULL;
slowa wczytaj() //funkcja typu slowa wczytująca słowo
{ //angielskie i jego tłumaczenia
slowa S; //deklaracja tablicy struktur S typu slowa
int a=1;
S.liczba=0;
printf("Slowo angielskie:"); //podanie słowa angielskiego
scanf("%s",S.angielskie); //i wpisanie go do struktury
while(a!=2){
printf("\n1-Dodaj tlumaczenie\n2-Koniec\nTwoj wybor:");//operacje na słowie
scanf("%d",&a);
if(a!=2){
printf("\nTlumaczenie %d:",S.liczba+1);//podanie tłumaczeń polskich
scanf("%s",&S.polskie[S.liczba]); //i zapisanie do struktury
S.liczba++;
}
};
return S; //zwrot tablicy struktur S
}

wezel search(char ang,wezel *r,wezel *p)
{
wezel
current=r;
p=NULL;
while (current!=NULL)
{
if(strcmp(ang,current->dane.angielskie)==0)
return current;
else if(strcmp(ang,current->dane.angielskie)>0){
p=current;
current=current->right;
}
else {
*p=current;
current=current->left;
}

}

if(current==NULL)return NULL;   

}
int insert(slowa e,wezel *r) //wstawianie słowa do drzewa
{
wezel
wynik,p;
if(
r==NULL) //jeśli drzewo jest puste
{
r=(wezel )malloc(sizeof(wezel));
(r)->dane.liczba=e.liczba;
strcpy((
r)->dane.angielskie, e.angielskie);
for (int i=0;i<e.liczba;i++)
strcpy((*r)->dane.polskie[i], e.polskie[i]);

    (*r)->left=NULL;
    (*r)->right=NULL;

        return 1;
}

        wynik=search(e.angielskie,*r,&p);
        if(wynik!=NULL)return 0;                //jeśli w drzewie znajduje sie
        else                                    //juz taki wyraz
            {
            wezel *nowy=(wezel *)malloc(sizeof(wezel));
            nowy->dane.liczba=e.liczba;
            strcpy(nowy-> dane.angielskie, e.angielskie);
            for (int i=0;i<e.liczba;i++)
                strcpy(nowy-> dane.polskie[i],e.polskie[i]);

            nowy->left=NULL;
            nowy->right=NULL;                 
            if (strcmp(e.angielskie,p->dane.angielskie)<0) p->left=nowy;   //jesli wyrazu nie ma w drzewie
            else p->right=nowy;
            return 1;
            }

}
FILE f;
void preorder (wezel
r)
{
if(r!=NULL)
{
fwrite((char*)&(r->dane),sizeof(slowa),1,f);
preorder(r->left);
preorder(r->right);
}
}

void zapis(char *sciezka) //zapis do pliku
{
f=fopen (sciezka,"wb"); //otwarcie
preorder(r); //zapis
fclose(f); //zamkniecie
}

void odczyt(char *sciezka) //odczyt z pliku
{
f=fopen(sciezka,"rb"); //otwarcie
slowa O;
if (f!=NULL){
while (fread(&O,sizeof(slowa),1,f)==1)
insert(O, &r); //wczytanie
fclose(f); //zamkniecie
}
else printf("ERROR:Blad odczytu lub podana sciezka jest nie prawidlowa!!!\nSprobuj jeszcze raz!!!\n");

}

void wyswietl(wezel *a) //funkcja wyswitlajaca slowo
{
for(int i=0;i<a->dane.liczba;i++)
{
printf("Tlumaczenia %d:%s\n",i+1,a->dane.polskie[i]);
}
}

int delate(slowa e,wezel *r,char usuwany){
wezel wynik,p,pomoc;
wynik=search(usuwany,(
r),&p);
if(wynik->left==NULL && wynik->right==NULL){
printf("oooooo");
if(wynik==(r)){
printf("tararaa");
free(
r);
(*r)=NULL;
return 1;

    }
    else if(strcmp(wynik->dane.angielskie,p->dane.angielskie)>0){
        printf("2 warunek");
        free(wynik);
        wynik=NULL;
        p->right=NULL;
        return 1;
    }
    else if(strcmp(wynik->dane.angielskie,p->dane.angielskie)<0){
        printf("3 warunek");
        free(wynik);
        wynik=NULL;
        p->left=NULL;
        return 1;
    }
}
else if(wynik->left==NULL || wynik->right==NULL){
        if(wynik->right==NULL){
    printf("ssssssss11");
            if(wynik==(*r)){
            printf("cccccc11");
            (*r)=(*r)->left;
            free(wynik);
            return 1;
        }
        else {
            p->left=wynik->left;
            free(wynik);
            return 1;
        }
    }
    if(wynik->left==NULL){
        if(wynik==(*r)){
            (*r)=(*r)->right;
            free(wynik);
            return 1;
        }
        else {
            p->right=wynik->right;
            free(wynik);
            return 1;
        }
    }
}
else if(wynik->left!=NULL && wynik->right!=NULL){
    printf("zzzzzz");
    int l=rand()%1;
    if(l==0){
        wezel *temp=wynik->left,*pomocnik=wynik;
        while(temp->right!=NULL){
            pomocnik=temp;
            temp=temp->right;
        }
        if(wynik==*r){
            strcpy((*r)->dane.angielskie,temp->dane.angielskie);
            (*r)->dane.liczba=temp->dane.liczba;
            for(int i=0;i<(*r)->dane.liczba;i++)
                strcpy((*r)->dane.polskie[i],temp->dane.polskie[i]);
            if(temp->left!=NULL)pomocnik->right=temp->left;
            free(wynik);
            free(temp);
            return 1;
        }
        else{
            strcpy(wynik->dane.angielskie,temp->dane.angielskie);
            wynik->dane.liczba=temp->dane.liczba;
            for(int i=0;i<wynik->dane.liczba;i++)
                strcpy(wynik->dane.polskie[i],temp->dane.polskie[i]);
            if(temp->left!=NULL)pomocnik->right=temp->left;
            free(temp);
            return 1;
        }
    }
    if(l==1){
        wezel *temp=wynik->right, *pomocnik=wynik;
        while(temp->left!=NULL){
            pomocnik=temp;
            temp=temp->left;
        }
        if(wynik==*r){
            strcpy((*r)->dane.angielskie,temp->dane.angielskie);
            (*r)->dane.liczba=temp->dane.liczba;
            for(int i=0;i<(*r)->dane.liczba;i++)
                strcpy((*r)->dane.polskie[i],temp->dane.polskie[i]);
            if(temp->right!=NULL)pomocnik->left=temp->right;
            free(wynik);
            free(temp);
            return 1;
        }
        else{
            strcpy(wynik->dane.angielskie,temp->dane.angielskie);
            wynik->dane.liczba=temp->dane.liczba;
            for(int i=0;i<wynik->dane.liczba;i++)
                strcpy(wynik->dane.polskie[i],temp->dane.polskie[i]);
            if(temp->right!=NULL)pomocnik->left=temp->right;
            free(temp);
            return 1;
        }
    }
}

}

int menu()
{
int z;
printf("\n1-Dodaj\n");
printf("2-Usun\n");
printf("3-Znajdz\n");
printf("4-Zapisz\n");
printf("5-Wczytaj\n");
printf("6-Koniec\n");
scanf("%d",&z);
return z;
}

int main()
{

wezel *p,*wynik;    
char ang[30],usuwany[30];
int z;
slowa S;
char sciezka[100];
do 
{
    z=menu();
    switch(z)
    {
        case 1: S=wczytaj();insert(S,&r);break;
        case 2: printf("Podaj slowo do usuniecia:");
        scanf("%s",usuwany);

        wynik=search(usuwany,r,&p);
        if (wynik==NULL) printf ("Brak takiego slowa !!!\n");
        else delate(S,&r,usuwany);

        break;
        case 3:printf("Znajdz tlumaczenie slowa:");
        scanf("%s",ang);
        wynik=search(ang,r,&p);
        if (wynik==NULL) printf("Brak tlumaczen slowa !!!\n");
        else wyswietl(wynik);
        break;
        case 4:printf("Podaj sciezke pliku do zapisu:");
        scanf("%s",sciezka);
        zapis(sciezka);
        break;
        case 5:printf("Podaj sciezke pliku do odczytu:");
        scanf("%s",sciezka);
        odczyt(sciezka);
        break;
    }
}while (z!=6);
return 0;

}

0

// skoro robisz to na drzewie to definiując tą strukturę definijesz węzeł w drzewie, czyli punkcik z którego
// wychodzą kolejne gałęzie
struct wezel{                  
        slowa dane;               // aby mieć dostęp do słów 
        wezel *left;               // wskaźnik na element po lewej stronie od węzła  
        wezel *right;            // wskaźnik na element po prawej stronie od węzła
};
wezel *search(char *ang,wezel *r,wezel **p)          
{                                                    
        wezel *current=r;      // wskaźnik na aktualną pozycję w drzewie
        *p=NULL;                 // jakiś wskaźnik pomocniczy
        while (current!=NULL)  // dopóki aktualna pozycja jest różna od NULL czyli jest co przeglądać
        {
                if(strcmp(ang,current->dane.angielskie)==0)  // jeśli znalazł słówko to zwraca wskażnik na                                    
                                                                                   // aktualną pozycję
                        return current;
                else if(strcmp(ang,current->dane.angielskie)>0){ // jeśli nie to przechodzimy do elementu po prawej stronie
                        *p=current;
                        current=current->right;
                }
                else {
                        *p=current;
                        current=current->left;  // przechodzimy do elementu po lewej stronie od węzła
                }

        }

        if(current==NULL)return NULL;        // jeśli current = NULL to znaczy, że jest to już koniec drzewa
}
int insert(slowa e,wezel **r)                           //wstawianie słowa do drzewa
{
    wezel *wynik,*p;
        if(*r==NULL)                                        //jeśli drzewo jest puste
        {
                *r=(wezel *)malloc(sizeof(wezel));      // alokacja pamięci
                (*r)->dane.liczba=e.liczba;               // uzupełanianie zmiennych
                strcpy((*r)->dane.angielskie, e.angielskie);  // jw.
        for (int i=0;i<e.liczba;i++)
        strcpy((*r)->dane.polskie[i], e.polskie[i]);   // jw.

                (*r)->left=NULL;    // tworzenie końcowych elementów drzewa o wartości NULL
                (*r)->right=NULL;

                        return 1;
        }

                        wynik=search(e.angielskie,*r,&p);
                        if(wynik!=NULL)return 0;                //jeśli w drzewie znajduje sie
                        else                                    //juz taki wyraz
                                {
                                wezel *nowy=(wezel *)malloc(sizeof(wezel));   // znowu alokacja pamięci
                                nowy->dane.liczba=e.liczba;                        // uzupełanianie pól struktury
                                strcpy(nowy-> dane.angielskie, e.angielskie);  // uzupełanianie pól struktury
                                for (int i=0;i<e.liczba;i++)
                                        strcpy(nowy-> dane.polskie[i],e.polskie[i]);  // uzupełanianie pól struktury

                                nowy->left=NULL;    // tworzenie końcowych elementów drzewa
                                nowy->right=NULL;                                  
                                if (strcmp(e.angielskie,p->dane.angielskie)<0) p->left=nowy;   //jesli wyrazu nie ma w drzewie
                else p->right=nowy;
                                return 1;
                                }

}

Tyle zdążyłem, a teraz musze do pracy spadać ....

0

Dzięki resztę sam większość jakoś doSZEDŁem, trochę pościemniałem i dostałem 15/16 pkt.

0

A jeszcze tak z ciekawości zapytam czy dałoby się to napisać prościej, tzn. skrócić trochę kod nie tracąc obecnej funkcjonalności?

0

aXe jeśli możesz to wyślij na melika plik *.ccp [email protected]

0

Po co mam ci wysyłać na meila jak masz cały program w tym poście :-D Wystarczy tylko kopiuj i wklej uŻyć

0

na pewno dalo by sie szalenie skrocic, jesli bys uzyl kontenera i algorytmow z STL, drzewa binarne i zoptymalizowane na nie algorytmy sa juz zrobione

0

Robiłem tak ale się nie da wyskakuje 1 błąd ".cpp(309) : fatal error C1010: unexpected end of file while looking for precompiled header directive
Error executing cl.exe." Co ci zależy mi go wysłać?

0

Wylacz w opcjach kompilatora (visual?) opcje 'use precompiled headers' - to bedzie hulac.

0

A gdzie ta opcja jest? Używam M Visual c++ 98!

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0