zabezpieczenie przed wrowadzaniem złych danych

0

Napisałem algorytm który m. in. dodaje i usuwana elementy z drzewa BST.
Wszystko ładnie działa, tylko mam problem z zabezpieczeniem przed podawaniem złych danych wejściowych. Chodzi dokładnie o funkcję usuwania pojedynczego elementu. Jak podam do usunięcia element o kluczu którego nie ma w drzewie to wyskakuje segmentation fault, a chce żeby wyskoczył komunikat że podano złe dane. Najprawdopodobniej program wchodzi w nieskończoną pętlę while po wejściu w funkcję usuwanie(). Proszę o pomoc gdyż nie wiem już jak to zrobić bo moje próby okazały się nieskuteczne :(

#include <iostream>
#include <stdio.h>


using namespace std;


struct drzewo
{
   int index;
   int klucz;
   drzewo *lewy,*prawy;
   drzewo *rodzic;
};

drzewo *root;
int z,usuwana_wartosc;

//Dodawanie elementu do drzewa BST 
void dodawanie(int x)
{
   int i=1;
   drzewo *nowy_element;
   nowy_element = new drzewo;
   nowy_element->klucz=x;
   nowy_element->lewy=NULL;
   nowy_element->prawy=NULL;
   if(!root)
   {
        root=nowy_element;
                nowy_element->index=1;
                nowy_element->rodzic=NULL;
        return;
   }
   drzewo *tym=root;
   while ( ( (tym->klucz>x) && (tym->lewy) ) || ( (tym->klucz<x) && (tym->prawy) ) )
   {
        if (tym->klucz>x)
                {
                        tym=tym->lewy;
                        i=2*i;
                }
        else
                {
                        tym=tym->prawy;
                        i=2*i+1;
                }
   }
   if (tym->klucz>x)
   {
        nowy_element->rodzic=tym;
        tym->lewy=nowy_element;
        i=2*i;
   }
   else
   {
        nowy_element->rodzic=tym;
        tym->prawy=nowy_element;
        i=2*i+1;
   }
   nowy_element->index=i;
}

//Usuwanie elementu o kluczu podanym jako parametr
void usuwanie(int x)  //Do dopracowania index
{
    int z=0;
    drzewo *tym=root, *tym2;
    while (tym->klucz!=x)
    {
        if (tym->klucz<x)
        {
            tym=tym->prawy;
            z=1;
        }
        else
        {
            tym=tym->lewy;
            z=2;
        }
    }
    if ((!tym->lewy) && (!tym->prawy))
    {
        switch (z)
        {
            case 0:
                delete tym;
                tym=NULL;
                root=NULL;
                return;
            case 1:
                tym->rodzic->prawy=NULL;
                delete tym;
                tym=NULL;
                return;
            case 2:
                tym->rodzic->lewy=NULL;
                delete tym;
                tym=NULL;
                return;
        }

    }
    else if ((tym->lewy) && (!tym->prawy))
    {
        switch (z)
        {
            case 0:
                tym->lewy->rodzic=NULL;
                root=tym->lewy;
                delete tym;
                tym=NULL;
                return;
            case 1:
                tym->lewy->rodzic=tym->rodzic;
                tym->rodzic->prawy=tym->lewy;
                delete tym;
                tym=NULL;
                return;
            case 2:
                tym->lewy->rodzic=tym->rodzic;
                tym->rodzic->lewy=tym->lewy;
                delete tym;
                tym=NULL;
                return;
        }
    }
    else if ((!tym->lewy) && (tym->prawy))
    {
        switch (z)
        {
            case 0:
                tym->prawy->rodzic=NULL;
                root=tym->prawy;
                delete tym;
                tym=NULL;
                return;
            case 1:
                tym->prawy->rodzic=tym->rodzic;
                tym->rodzic->prawy=tym->prawy;
                delete tym;
                tym=NULL;
                return;
            case 2:
                tym->prawy->rodzic=tym->rodzic;
                tym->rodzic->lewy=tym->prawy;
                delete tym;
                tym=NULL;
                return;
        }
    }
    else if ((tym->lewy) && (tym->prawy))
    {
        tym2=tym;
        tym2=tym2->prawy;
        while (tym2->lewy!=NULL)
        {
            tym2=tym2->lewy;
        }
        usuwana_wartosc=tym2->klucz;
        usuwanie(tym2->klucz);
        tym->klucz=usuwana_wartosc;
        return;
    }
}


int main()
{
    int n=0,n2=0;
    printf("Podaj ilość elementów które chcesz wprowadzić do drzewa: ");
    scanf("%d",&n);
    int *tab = new int[n];
    for (int i=0;i<n;i++)
    {
        scanf("%d",&tab[i]);
        dodawanie(tab[i]);
    }
    printf("Podaj ile elementów chcesz usunąć: ");
    scanf("%d",&n2); 
    int *tab2 = new int[n2];
    if (n2<=n)
    {
        for (int i=0;i<n2;i++)
        {
            scanf("%d",&tab2[i]);   // TUTAJ TRZEBA ZABEZPIECZYĆ PRZED PODAWANIEM ELEMENTU KTÓREGO NIE MA W DRZZEWIE
            usuwanie(tab2[i]);
        }
    }
    else printf("Nie ma tylu elemenetów w drzewie\n");
    delete [] tab;
    delete [] tab2;
    return 0;
}
1

dodaj do while'a

if(tym == NULL) TUTAJ_TO_CO_CHCESZ_ZROBIĆ

najlepiej rzucić wyjątkiem np out_of_index i potem go złapać w głównej funkcji programu i obsłużyć komunikatem
ewentualnie po prostu dać return; i wyjść nic nie robiąc albo zmienić typ funkcji z void na boolean i zwrócić false gdy nie znaleziono elementu

albo najlepiej dodaj funkcję znajdz() zwracającą znaleziony element albo NULL - wtedy po pierwsze możesz kawałek kodu funkcji usuwanie zamienić na wywołanie tej funkcji i poprawić czytelność programu, a po drugie w głównym programie możesz też użyć tej funkcji do walidacji czy element istnieje

0

Napisałem funkcje znajdz

int znajdz(int x)
{
    drzewo * tym=root;
    int p=0;
    while ((tym->klucz!=x) || (tym!=NULL))
    {
        if (tym->klucz<x)
        {
            tym=tym->prawy;
            if (tym->klucz==x) p++;
        }
        else
        {
            tym=tym->lewy;
            if (tym->klucz==x) p++;
        }
    }
    return p;
}

I w mainie zmieniłem na

    int *tab2 = new int[n2];
    if (n2<=n)
    {
        for (int i=0;i<n2;i++)
        {
            scanf("%d",&tab2[i]);
            znajdz(tab2[i]);
            if (znajdz(tab2[i])==1) usuwanie(tab2[i]);
            else printf("Nie ma elemenetu");
        }
    }

I nadal to samo ;/

1

while (tym!=NULL && tym->klucz!=x)

albo lepiej:

bool znajdz(int x)
{
    drzewo * tym=root;
    while (tym != NULL)
    {
        if (tym->klucz == x) return true;
        if (tym->klucz<x)
        {
            tym=tym->prawy;
        }
        else
        {
            tym=tym->lewy;
        }
    }
    return false;
}
    int *tab2 = new int[n2];
    if (n2<=n)
    {
        for (int i=0;i<n2;i++)
        {
            scanf("%d",&tab2[i]);
            if (znajdz(tab2[i])) usuwanie(tab2[i]);
            else printf("Nie ma elemenetu");
        }
    }

choć nie zupełnie o to mi chodziło z propozycją utworzenia nowej funkcji...

0

Segmentation fault ;(

0

Stary jesteś wielki!!!
Zrobiłem tak jak poradziłeś:

bool znajdz(int x)
{
    drzewo * tym=root;
    while (tym -> klucz != x)
    {
        if (tym->klucz<x)
        {
            tym=tym->prawy;
        }
        else
        {
            tym=tym->lewy;
        }
        if(tym == NULL) return false;
    }
    return true;
}
    int *tab2 = new int[n2];
    if (n2<=n)
    {
        for (int i=0;i<n2;i++)
        {
            scanf("%d",&tab2[i]);
            if (znajdz(tab2[i]))
            {
                usuwanie(tab2[i]);
            }
            else
            {
                printf("Nie ma elemenetu");
            }
        }
    }

I śmiga jak należy. Wielkie dzięki i wielki plus dla Ciebie ;)

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.