zadatak sa vezanom listom

[ antonija @ 23.09.2004. 20:07 ] @

Molim vas da mi pregledate u cemu je problem u ovom resenju zadatka sa vezanom listom. Kompajler mi ne javlja gresku nikakvu ali kad se program pokrene onda zablokira:
#include <iostream>
using namespace std;

struct el {
double koef;
struct el *sljedeci;
};

class Polinomi {
private:
struct el *pocetak_liste, *kraj_liste, *novi_element;
int stupanj;
public:
Polinomi() {
pocetak_liste = kraj_liste = novi_element = NULL;
stupanj = 0;
}
Polinomi(int st) {
stupanj = st;
pocetak_liste = kraj_liste;
cout << "Upisite koeficijente: " << endl;
novi_element = (struct el *) malloc(sizeof(struct el));
if (novi_element ==NULL) {
cout << "Nema dovoljno memorije!" << endl;
exit (1);
};
for (int i = 0; i < (st+1); i++) {
cout << i << ". koeficijent: ";
cin >> novi_element->koef;
novi_element->sljedeci = kraj_liste;
if (pocetak_liste == kraj_liste)
pocetak_liste = novi_element;
else {
kraj_liste = novi_element;
};
};
}
Polinomi(struct el *lista) {
int i = 0;
pocetak_liste = (struct el *) malloc(sizeof(struct el));
kraj_liste = (struct el *) malloc(sizeof(struct el));
pocetak_liste = lista;
novi_element = (struct el *) malloc(sizeof(struct el));
if (novi_element ==NULL) {
cout << "Nema dovoljno memorije!" << endl;
exit (1);
};
for (lista = pocetak_liste; lista != kraj_liste ; lista = lista->sljedeci) {
i++;
novi_element->koef = lista->koef;
novi_element = novi_element->sljedeci;
kraj_liste = novi_element;
};
stupanj = i;
}
Polinomi operator+(const Polinomi &a) {
struct el *zbroj = NULL;
if (stupanj <= a.stupanj) {
for (zbroj = pocetak_liste; zbroj != kraj_liste; zbroj = zbroj->sljedeci) {
zbroj->koef = novi_element->koef + a.novi_element->koef;
zbroj->sljedeci = novi_element->sljedeci;
};
for (zbroj = a.novi_element; zbroj != a.kraj_liste; zbroj = zbroj->sljedeci) {
zbroj->koef = a.novi_element->koef;
zbroj->sljedeci = a.novi_element->sljedeci;
};
};
if (stupanj > a.stupanj) {
for (zbroj = a.pocetak_liste; zbroj != a.kraj_liste; zbroj = zbroj->sljedeci) {
zbroj->koef = novi_element->koef + a.novi_element->koef;
zbroj->sljedeci = a.novi_element->sljedeci;
};
for (zbroj = novi_element; zbroj != kraj_liste; zbroj = zbroj->sljedeci) {
zbroj->koef = novi_element->koef;
zbroj->sljedeci = novi_element->sljedeci;
};
};
return Polinomi(zbroj);
}
~Polinomi() {
delete [] pocetak_liste;
delete [] kraj_liste;
delete [] novi_element;
};
};

int main() {
Polinomi *A = new Polinomi;
Polinomi b(3);

return 0;
}

[ dr ZiDoo @ 23.09.2004. 22:49 ] @

Ono ja bi ti stvarno pomogao, ali pliz de napiši fino tabovan code, u code tagovima :D

Usput napiši koji kompajler, jesi uključila debug opcije?

[ antonija @ 24.09.2004. 11:08 ] @

Code:

#include <iostream>
using namespace std;

struct el {
    double koef;
    struct el *sljedeci;
};

class Polinomi {
private:
    struct el *pocetak_liste, *kraj_liste, *novi_element;
    int stupanj;
public:
    Polinomi() {
        pocetak_liste = kraj_liste = novi_element = NULL;
        stupanj = 0;
    }
    Polinomi(int st) {
        stupanj = st;
        pocetak_liste = kraj_liste;
        cout << "Upisite koeficijente: " << endl;
        novi_element = (struct el *) malloc(sizeof(struct el));
        if (novi_element ==NULL) {
            cout << "Nema dovoljno memorije!" << endl;
            exit (1);
        };
        for (int i = 0; i < (st+1); i++) {
            cout << i << ". koeficijent: ";
            cin >> novi_element->koef;
            novi_element->sljedeci = kraj_liste;
            if (pocetak_liste == kraj_liste)
                pocetak_liste = novi_element;
            else {
                kraj_liste = novi_element;
            };
        };
    }
    Polinomi(struct el *lista) {
        int i = 0;
        pocetak_liste = (struct el *) malloc(sizeof(struct el));
        kraj_liste = (struct el *) malloc(sizeof(struct el));
        pocetak_liste = lista;
        novi_element = (struct el *) malloc(sizeof(struct el));
        if (novi_element ==NULL) {
            cout << "Nema dovoljno memorije!" << endl;
            exit (1);
        };
        for (lista = pocetak_liste; lista != kraj_liste ; lista = lista->sljedeci) {
            i++;
            novi_element->koef = lista->koef;
            novi_element = novi_element->sljedeci;
            kraj_liste = novi_element;
        };
        stupanj = i;
    }
    Polinomi operator+(const Polinomi &a) {
        struct el *zbroj = NULL;
        if (stupanj <= a.stupanj) {
            for (zbroj = pocetak_liste; zbroj != kraj_liste; zbroj = zbroj->sljedeci) {
                zbroj->koef = novi_element->koef + a.novi_element->koef;
                zbroj->sljedeci = novi_element->sljedeci;
            };
            for (zbroj = a.novi_element; zbroj != a.kraj_liste; zbroj = zbroj->sljedeci) {
                zbroj->koef = a.novi_element->koef;
                zbroj->sljedeci = a.novi_element->sljedeci;
            };
        };
        if (stupanj > a.stupanj) {
            for (zbroj = a.pocetak_liste; zbroj != a.kraj_liste; zbroj = zbroj->sljedeci) {
                zbroj->koef = novi_element->koef + a.novi_element->koef;
                zbroj->sljedeci = a.novi_element->sljedeci;
            };
            for (zbroj = novi_element; zbroj != kraj_liste; zbroj = zbroj->sljedeci) {
                zbroj->koef = novi_element->koef;
                zbroj->sljedeci = novi_element->sljedeci;
            };
        };
        return Polinomi(zbroj);
    }
    ~Polinomi() {
        delete [] pocetak_liste;
        delete [] kraj_liste;
        delete [] novi_element;
    };
};

int main() {
    Polinomi *A = new Polinomi;
    Polinomi b(3);

    return 0;
}

Je li sad u redu?Ukljucila sam debug opcije!

[ Časlav Ilić @ 24.09.2004. 14:08 ] @

Mislim da je korisnije da ukažem na greške nego da ispravim kôd.

Važnije stvari:

- Podrazumevani konstruktor pravi polinom nultog stepena, dakle mora odmah napraviti jedan element liste, a mogao bi i koeficijent da postavi na 0.

- Elemente liste rezerviši pomoću operatora new. U tom slučaju ne moraš da proveravaš da li je memorija rezervisana, new to radi za tebe.

- Druga dva konstruktora moraju da rezervišu novi element i u svakom ciklusu petlje, a ne samo na početku.

- Članske promenljive novi_element i kraj_liste ne treba da budu članovi, već samo pomoćne promenljive u funkcijama gde su potrebne. Članovi treba da budu samo podaci koji su nezavisni, tj. ne mogu se dedukovati iz drugih članova, i imaju konkretno značenje u klasi, a to je ovde samo pocetak_liste.

- U destruktoru, lista se ne može obrisati operatorom delete [], njime se brišu isključivo promenljive razervisane pomoću new []. Lista se mora brisati u petlji, član po član.

Manje važno:

- Konstruktor koji čita listu sa std. ulaza, ne bi trebalo to da radi, već bi mu trebalo proslediti tok iz koga se čita. Deklaracija bi bila Polinomi (int st, istream& is), u kôdu bi tada umesto cin >> ... stajalo is >> .... Takođe, ne bi trebalo da „laje“ (tj. da se oglašava sa cout << ...), to je na korisniku klase (iliti glavnom programu) da implementira ako želi.

- Operator sabiranja bi trebalo deklarisati kao prijateljsku funkciju, tj. friend const Polinomi operator+(const Polinomi &a, const Polinomi &b). To je zato što se od operatora sabiranje očekuje da proizvede konstantnu vrednost, tj. da operacije tipa (a + b) = c; ne budu dozvoljene. Ako se definiše kao članica, takve operacije postaju moguće.

- U stvari, u ovom slučaju povezanu listu ne bi trebalo ni koristiti :) Jedino je ima smisla koristiti radi učenja, realno bi više odgovarao neki standardni kontejner za koeficijente polinoma, npr. vector<double>.

[ antonija @ 24.09.2004. 20:13 ] @

Hvala na pomoci!Ja se nadam da sad nece bit nekih problema.Ja, nazalost, moram koristiti vezanu listu jer mi tako zadatak nalaze!Pozdrav!

[ antonija @ 25.09.2004. 19:43 ] @

Opet imam problema sa istim zadatkom. Kako da deklarisem objekt razreda polinomi koristeci konstruktor Polinomi(int st, istream &is)? I kompajler mi javlja internal compiler error kod friend const Polinomi operator+ koji je ovako definiran:

Code:

    friend const Polinomi operator+(const Polinomi &a, const Polinomi &b) {
        struct el *zbroj = new struct el;
        if (b.stupanj <= a.stupanj) {
            for (zbroj = b.pocetak_liste; zbroj != NULL; zbroj = zbroj->sljedeci) {
                zbroj->koef = b.pocetak_liste->koef + a.pocetak_liste->koef;
                zbroj->pot = b.pocetak_liste->pot;
                struct el *zbroj = new struct el;
                zbroj->sljedeci = b.pocetak_liste->sljedeci;
                b.pocetak_liste = b.pocetak_liste->sljedeci;
                a.pocetak_liste = a.pocetak_liste->sljedeci;
            };
            for (zbroj = a.pocetak_liste; zbroj != NULL; zbroj = zbroj->sljedeci) {
                zbroj->koef = a.pocetak_liste->koef;
                zbroj->pot = a.pocetak_liste->pot;
                a.pocetak_liste = a.pocetak_liste->sljedeci;
                struct el *zbroj = new struct el;
                zbroj->sljedeci = a.pocetak_liste->sljedeci;
            };
        };
        if (b.stupanj > a.stupanj) {
            for (zbroj = a.pocetak_liste; zbroj != NULL; zbroj = zbroj->sljedeci) {
                zbroj->koef = b.pocetak_liste->koef + a.novi_element->koef;
                zbroj->pot = b.pocetak_liste->pot;
                a.pocetak_liste = a.pocetak_liste->sljedeci;
                b.pocetak_liste = b.pocetak_liste->sljedeci;
                struct el *zbroj = new struct el;
                zbroj->sljedeci = a.pocetak_liste->sljedeci;
            };
            for (zbroj = b.pocetak_liste; zbroj != NULL; zbroj = zbroj->sljedeci) {
                zbroj->koef = b.pocetak_liste->koef;
                zbroj->pot = b.pocetak_liste->pot;
                b.pocetak_liste = b.pocetak_liste->sljedeci;
                struct el *zbroj = new struct el;
                zbroj->sljedeci = b.pocetak_liste->sljedeci;
            };
        };
        return Polinomi(zbroj);
    }

Zasto? I sve sam ostalo popravila kako ste mi rekli.Makla sam *novi_element i *kraj_liste.

[ Časlav Ilić @ 26.09.2004. 09:24 ] @

Popričekaj malo sa sabiranjem, da vidimo kako sada ostalo u klasi izgleda. Opet se tu izgleda pojavljuje nešto nepotrebno, kakva je to promenljiva pot u strukturi el?

Ako te baš zanima za sabiranje, kompilator se buni (premda na malo čudan način, koji je to kompilator?) zato što pokušavaš da promeniš članice pocetak_liste, a objekti su deklarisani kao konstantne reference, a možda i zbog još nečeg. Ima tu još pun kofer problema, ali o tom potom.

[ Časlav Ilić @ 26.09.2004. 09:27 ] @

Citat:

Kako da deklarisem objekt razreda polinomi koristeci konstruktor Polinomi(int st, istream &is)?

Npr. ovako:

Code:
int st = 5;
cout << "Unesite " << st << " koeficijenata polinoma:" << endl;
Polinomi a(st, cin);

[ antonija @ 26.09.2004. 14:57 ] @

Asistent mi je rekao da koristim vezanu listu u kojoj cu da spremam parove(koeficijent, potencija) kao clanove polinoma i zato sam ubacila jos pot.

Code:

struct el {
    double koef;
    int pot;
    struct el *sljedeci;
};

class Polinomi {
private:
    struct el *pocetak_liste;
    int stupanj;

Je li to dobro?

[ Časlav Ilić @ 26.09.2004. 16:01 ] @

A, tako. Dobro je u smislu da efikasnije koristi memoriju, ali će onda biti teže uraditi sabiranje i druge operatore. Zaboravih ranije da kažem da treba dodati i kopirajući konstruktor, Polinomi (const Polinomi& a);, inače će biti problema.

Olakšala bi sebi posao ako bi prvo, nezavisno od klase Polinomi, napisala i isprobala sledeće tri funkcije (kasnije bi postale privatne članice klase), datim redom:

- void dodaj_posle (struct el *const tekuci_el, struct el *const novi_el), koja u listu dodaje novi element (novi_el) odmah posle tekućeg (tekuci_el).

- void ispisi (const struct el *const prvi_el, ostream &os), koja ispisuje listu čiji je prvi član prvi_el, na dati izlazni tok.

- struct el * obrisi (struct el *tekuci_el), koja briše element liste tekuci_el i vraća pokazivač na prvi sledeći element liste.

Nekakav probni primer bi bio:

Code:
#include <iostream>

using namespace std;

struct el {
    double koef;
    int pot;
    struct el *sljedeci;
};

void dodaj_posle (struct el *const tekuci_el, struct el *const novi_el) {
    //...
}

void ispisi (const struct el *const prvi_el, ostream &os) {
    //...
}

struct el * obrisi (struct el *tekuci_el) {
    //...
}

int main ()
{
    struct el *prvi_el = NULL;
    struct el *novi_el = NULL;
    struct el *zadnji_el = NULL;

    // Konstruisemo novi element.
    novi_el = new struct el;
    novi_el->koef = 0.5; novi_el->pot = 1; novi_el->sljedeci = NULL;
    // Dodajemo prvi element u listu.
    dodaj_posle(prvi_el, novi_el);
    // Pamtimo koji je zadnji element u listi.
    zadnji_el = novi_el;

    // Jos jedan novi element.
    novi_el = new struct el;
    novi_el->koef = 2.5; novi_el->pot = 3; novi_el->sljedeci = NULL;
    // Dodajemo novi element posle trenutno zadnjeg elementa u listi.
    dodaj_posle(zadnji_el, novi_el);
    zadnji_el = novi_el;

    // I jos jedan.
    novi_el = new struct el;
    novi_el->koef = 7.5; novi_el->pot = 6; novi_el->sljedeci = NULL;
    dodaj_posle(zadnji_el, novi_el);
    zadnji_el = novi_el;

    // Pokazivac novi_el nam vise nije potreban, i zato ga postavljamo na NULL.
    novi_el = NULL;

    // Ispisujemo listu.
    ispisi(prvi_el, cout); // Trebalo bi da ispise: 0.5*x^1 + 2.5*x^3 + 7.5*x^6

    // Brisemo zadnji element u listi.
    zadnji_el = obrisi(zadnji_el); // Funkcija ce vratiti NULL, koje pamtimo u
                                   // zadnji_el, kako bi znali da vise ne
                                   // pokazuje na kraj liste.
    ispisi(prvi_el, cout); // Trebalo bi da ispise: 0.5*x^1 + 2.5*x^3

    // Brisemo prvi element u listi.
    prvi_el = obrisi(prvi_el); // Funkcija ce vratiti pokazivac na prvi sledeci
                               // element, i to je novi prvi element liste.
    ispisi(prvi_el, cout); // Trebalo bi da ispise: 2.5*x^3

    // Brisemo i zadnji element.
    prvi_el = obrisi(prvi_el) // prvi_el ce dobiti NULL, posto vise elemenata
                              // i nema.
    ispisi(prvi_el, cout); // Ne bi trebalo nista da ispise.

    return 0;
}

Usput, za šta je ovaj zadatak, pošto polako postaje nezgodan — nadam se da nije žurba da se završi :)

[ antonija @ 28.09.2004. 12:21 ] @

Ovaj zadatak mi je za ispit i trebao bi bit gotov ovaj tjedan.Napravila sam ono sto ste mi rekli ali i tu javlja nekakvu gresku i to kod metode dodaj_posle:

Code:

void dodaj_posle (struct el *const tekuci_el, struct el *const novi_el) {
    if (novi_el != NULL) {
        novi_el->sljedeci = tekuci_el->sljedeci;
        tekuci_el->sljedeci = novi_el;
    };
}

void ispisi (const struct el *const prvi_el, ostream &os) {
    const struct el *isp;
    for (isp = prvi_el; isp != NULL; isp = isp->sljedeci) {
        cout << isp->koef << "x^" << isp->pot;
        if (isp->sljedeci != NULL)
            cout << "+";
    };
}

struct el *obrisi (struct el *tekuci_el) {
    struct el *test, *temp, *start;
    int redni_br = 0;
    for (test = tekuci_el; test != NULL; test = test->sljedeci) {
        redni_br++;
        temp = test->sljedeci;
        if (test->koef == tekuci_el->koef && test->pot == tekuci_el->pot && redni_br == 1) {
            start = temp;
            tekuci_el = NULL;
        };
        if (temp->koef == tekuci_el->koef && temp->pot == tekuci_el->pot) {
            test->sljedeci = test->sljedeci->sljedeci;
            temp = NULL;
        };
    };
    return(test);

[ filmil @ 28.09.2004. 13:08 ] @

Citat:

Napravila sam ono sto ste mi rekli ali i tu javlja nekakvu gresku i to kod metode dodaj_posle:

Pomozi ljudima da ti pomognu. Napiši koja je greška u pitanju, da ne nabadaju po mraku.

[ antonija @ 28.09.2004. 13:29 ] @

Kad pokrenem program pise:
The instruction at "neki broj" referenced memory at "neki drugi broj".The memory could not be read.Sto to znaci?

[ blaza @ 28.09.2004. 15:05 ] @

To znaci da tvoj program pokusava da cita sadrzaj memorije van bloka kome ima pravo da pristupa. Najcesce se radi o upotrebi pointera koji ne pokazuje na nista validno. Mozda pointer nije inicijalizovan, ili se koristi nakon dealokacije objekta na koji je pokazivao.
Hint: dangling pointer

[ Časlav Ilić @ 28.09.2004. 17:12 ] @

U funkciji dodaj_posle problem je u nepokrivenom slučaju kada je tekuci_el postavljen na NULL, tj. na početku dodavanja u listu. U tom smislu, i ja sam napravio grešku zadavši da je funkcija bez povratnog tipa, trebalo bi da vrati pokazivač na novododati element. Tako ispravljena funkcija je:

Code:
struct el * dodaj_posle (struct el *const tekuci_el, struct el *const novi_el) {
    if (novi_el != NULL && tekuci_el != NULL) {
        novi_el->sljedeci = tekuci_el->sljedeci;
        tekuci_el->sljedeci = novi_el;
    }
    return novi_el;
}

a prvi njen poziv u glavnom programu je (ostali ostaju isti):

Code:
    ...
    // Dodajemo prvi element u listu.
    prvi_el = dodaj_posle(prvi_el, novi_el); // Pamtimo pocetak liste.
    ...

Funkcija ispisi izgleda kao da je u redu.

Za funkciju obrisi možda nisam bio dovoljno jasan: pokazivač tekuci_el pokazuje baš na onaj element koji treba da se izbaci, ne moraš da ga tražiš po koeficijentu. Ne zaboravi i da oslobodiš zauzet prostor za njega (pomoću delete) pošto ga isključiš iz liste. Takođe, potpuno sam smetnuo sa uma da lista nije dvostruko povezana, pa ćeš morati da funkciji proslediš i početak liste, tj. zaglavlje treba da glasi struct el * obrisi (struct el *prvi_el, struct el *tekuci_el). Uz ovu izmenu pozivi u glavnom programu će biti:

Code:
    // Brisemo zadnji element u listi.
    zadnji_el = obrisi(prvi_el, zadnji_el);
    ...
    // Brisemo prvi element u listi.
    prvi_el = obrisi(prvi_el, prvi_el);
    ...
    // Brisemo i zadnji element.
    prvi_el = obrisi(prvi_el, prvi_el);
    ...

Ako ovo sa brisanjem već izgleda komplikovano, čini mi se da neće ni biti potrebno ako ne moraš da implementiraš ništa više osim sabiranja (i oduzimanja). U tom slučaju, možeš da napišeš samo funkciju void obrisi_listu (struct el *prvi_el) koja će obrisati celu listu. Tada bi onaj gore glavni program, posle prvog ispisa liste, od brisanja imao samo:

Code:
    ...
    // Ispisujemo listu.
    ispisi(prvi_el, cout); // Trebalo bi da ispise: 0.5*x^1 + 2.5*x^3 + 7.5*x^6

    // Brisemo listu...
    obrisi_listu(prvi_el);
    prvi_el = NULL; // i prvi_el postavljamo na NULL, posto je lista obrisana.

    return 0;
}