BST- problem z usuwaniem elementów

0

Witam. Mam problem z Binary Search Tree. Otóż kod w większości mam z książki Cormena, jednak usuwanie nie działa poprawnie. Przy usuwaniu całej listy z wyborem losowego elementu usuwa tylko kilka a potem program się crashuje. Zauważyłem jeszcze, że niekiedy przedtem jeszcze usuwa złe elementy. Występuje to tam, gdzie zostaje wyszukany następnik. Nie mam pojęcia jak to naprawić, wielokrotnie porównywałem kod z tym z książki. Na nazwy wskaźników proszę nie zwracać uwagi, szczególnie na prev - nie ma to często związku z jego funkcją.

Oto kod:

 
#include <iostream>
#include <vector>
#include <fstream>
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <algorithm>
#include <windows.h>
using namespace std;

struct element {
int numer;
string imie;
string nazwisko;
};

struct bst {
element* student;
bst* p;
bst* l;
bst* r;

//------------------------------------dodawanie pojedynczego elementu

void dodaj(bst*& bste, element *student) {
    bst *newel = new bst;
    newel->student = student;
    newel->l=NULL;
    newel->r=NULL;
    newel->p=NULL;
    bst *ths= bste;
    bst *prev=NULL;
    while (ths!=NULL)
    {
        prev=ths;
        if (ths->student->numer>newel->student->numer) ths=ths->l;
        else ths=ths->r;
    }
    newel->p=prev;
    if (prev==NULL)
    {
        bste=newel;
    } else if (prev->student->numer>newel->student->numer)
    {
        prev->l=newel;
    } else prev->r=newel;
}


//----------------------------szukanie, zwraca wskaznik

bst szukaj(bst*b, int numer)
{
    if((b==NULL) || (numer==b->student->numer)) return *b;
    if (numer < b->student->numer) {
    return szukaj(b->l, numer); }
    else {
    return szukaj(b->r, numer);}
}

bst *min(bst*b)
{
    while (b->l!=NULL) b=b->l;
    return b;
}

bst *nast(bst*b)
{
    if (b->r!=NULL) return min(b->r);
    bst *prev = b->p;
    while ((prev!=NULL) && (b==prev->r))
        {
            b=prev;
            prev=prev->p;
        }
    return prev;
}

//-------------------------------------usuwanie pojedynczego elementu

void usun(bst*&bs, int numer)
{

    bst *el = NULL;
    el = &szukaj(bs,numer);
    if (el!=NULL) {

    bst *b = NULL;
    bst *prev = NULL;
    if ((el->l==NULL) || (el->r==NULL)) prev=el;
        else prev= nast(el);
    if (prev->l != NULL) { b=prev->l; }
        else { b=prev->r; }
    if (b!=NULL) b->p=prev->p;
    if (prev->p==NULL) {
        bs = b; }
        else {
            if (prev->student->numer==prev->p->l->student->numer) {prev->p->l=b;}
            else  if (prev->student->numer==prev->p->r->student->numer) {prev->p->r = b; }
        }
    if (prev!=el) el->student->numer=prev->student->numer;
    }
}

//------------------- tworzenie calego drzewa z elementow tablicy

void wypelnij(bst*& bste, vector<element> tablica, int inc) {
        for (int i=0; i<inc; i++)
        {
        element *student=new element;
        student->imie=tablica[i].imie;
        student->nazwisko=tablica[i].nazwisko;
        student->numer=tablica[i].numer;
        //cout << tablica[i].numer << tablica[i].nazwisko << endl;
        bste->dodaj(bste, student);

        }
}

};

// ----------------- wczytywanie z pliku do tablicy

void wczytajtab(string load, vector<element> &tablica, int &inc) {
    load+=".txt";
    ifstream dane(load.c_str()) ;
    string ftmp;

    while( !dane.eof())
    {
        element *nowyel = new element;

        getline(dane, ftmp, ' ');
        nowyel->numer = atoi(ftmp.c_str());
        getline(dane, ftmp, ' ');
        nowyel->imie = ftmp;
        getline(dane, ftmp);
        nowyel->nazwisko = ftmp;
        tablica.push_back(*nowyel);
        inc++;
        delete nowyel;
    }
    dane.close() ;
}

// ----------------------- tworzenie tablicy posortowanych liczb naturalnych

void itab(int max, vector<int> &indeksy) {
    for(int j=1;j<=max;j++)
    {
        indeksy.push_back(j);
    }
}

// --------------------------------- MAIN

int main(){

srand(time(NULL));
bst *bste=NULL;

string load;
int inc=0,suma=0;
vector<element> tablica;
vector<int> indeksy;
int wybor;

cin >> load;


	wczytajtab(load,tablica,inc);

    bste->wypelnij(bste, tablica, inc);

        itab(inc,indeksy);
        random_shuffle(indeksy.begin(),indeksy.end());
        for (int i=0;i<inc;i++)
        {
        bste->usun(bste, indeksy[i]);
        }


delete bste;


return 0;
}
0
a.cpp:85:10: error: taking the address of a temporary object of type 'bst' [-Waddress-of-temporary]
    el = &szukaj(bs,numer);
         ^~~~~~~~~~~~~~~~~
a.cpp:159:7: error: use of undeclared identifier 'time'
srand(time(NULL));
      ^
2 errors generated.
0

Po skopiowaniu kodu usunęłem niepotrzebne rzeczy np. liczenie czasu. Zapomniałem wyrzucić linijki srand(time(NULL));. Nie ma to związku z problemem.

Za to nie mam pojęcia o co chodzi z 'taking address of temporary' . Że niby źle się odwołuję? U mnie to figuruje tylko jako warning, więc program się uruchamia.

EDIT:
Naprawiłem funkcję 'szukaj' i pozbyłem się tego błędu.

 bst *szukaj(bst*b, int numer)
{
    if((b==NULL) || (numer==b->student->numer)) return b;
    if (numer < b->student->numer) {
    return szukaj(b->l, numer); }
    else {
    return szukaj(b->r, numer);}
}

I odwołanie w funcji 'usun':

 el = szukaj(bs,numer);

To nic nie zmienia, nadal źle działa.

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