stos i tablica dynamiczna

Odpowiedz Nowy wątek
2012-01-09 15:45
0

Cześć, przygotowuje się do kolokwium i mam takie zadanie:

Zadeklarować klasę zespolona reprezentującą liczbę zespoloną, której części rzeczywista i
urojona przechowywane są wewnątrz klasy za pomocą zmiennych typu double. Zadeklarować
wszelkie potrzebne metody i operatory (patrz niżej), nie definiować metod ani operatorów.
2)
Zadeklarować klasę stos reprezentującą stos liczb zespolonych (LIFO). Dane wewnątrz klasy
mają być przechowywane wewnątrz tablicy dynamicznej (1 pkt.).
Zadeklarować wszelkie potrzebne metody i operatory (patrz niżej), zdefiniować:

  • funkcję składową push, umieszczającą nowy element na stosie (jeżeli rozmiar tablicy jest
    niewystarczający, to należy go podwoić) (1 pkt),

Nie wiem do końca czy poprawnie interpretuję treść zadania, napisałem coś takiego:

class zespolona
{
    double re;
    double im;

public:
    zespolona();
    ~zespolona();

};

class stos
{

protected:

    zespolona *dane; 
    int liczba_el;      //liczba el stosu
    int w;          //wskaznik stosu

public:

    stos(int n);
    ~stos();
    void Push(const zespolona &z);
};

stos::stos(int n)
{
    liczba_el = n;
    w = 0;
    dane = new zespolona[n];
}

void stos::Push(const zespolona &z)
{
    if(w<liczba_el)
        dane[w++] = z;

    else cout << "Stos pełny!" <<endl;
}

Czy to jest poprawne rozumowanie? Jak powinienem zrealizować ten stos?

Pozostało 580 znaków

2012-01-09 15:52
1

Treść zadania wyraźnie mówi, że jeśli nie ma miejsca w tablicy, to stos należy podwoić. Wobec tego:

void stos::Push(const zespolona &z)
{
    if(w >= liczba_el)
    {
        liczba_el *= 2;
        zespolona* tmp = new zespolona[liczba_el];
        memcpy(tmp, dane, liczba_el/2);
        delete[] dane;
        dane = tmp;
    }
    dane[w++] = z;
}

Ponadto po co w konstruktorze podawać rozmiar stosu, jeśli rośnie on dynamicznie? W konstruktorze wystarczy podać liczba_el == 1. Poza tym brakuje deklaracji innych metod. Klasa zespolona jest niekompletna, podobnie ze stosem.

class zespolona
{
    double re_;
    double im_;
public:
    zespolona(double re = 0.0, double im = 0.0) : re_(re), im_(im) {}
    //~zespolona(); destruktor nie jest tu potrzebny
    // konstruktor kopiujacy i operator przypisania sa domyslne

    // dostep
    double re() const { return re_; }
    double im() const { return im_; }
    double& re() { return re_; }
    double& im() { return im_; }

    // operatory
    zespolona operator-() const;

    zespolona& operator+=(const zespolona& rhs);
    zespolona& operator-=(const zespolona& rhs);
    zespolona& operator*=(const zespolona& rhs);
    zespolona& operator/=(const zespolona& rhs);

    zespolona operator+(const zespolona& rhs);
    zespolona operator-(const zespolona& rhs);
    zespolona operator*(const zespolona& rhs);
    zespolona operator/(const zespolona& rhs);

    bool operator==(const zespolona& rhs) const { return re_ == rhs.re_ && im_ == rhs.im_; }
    bool operator!=(const zespolona& rhs) const { return !(*this == rhs); }
};

class stos
{
private:
    int liczba_el;                 //liczba el stosu
    int w;                        //wskaznik stosu
    zespolona *dane; 
public:
    explicit stos(int size = 1) : liczba_el(size), w(0), dane(new zespolona[liczba_el]) {}
    ~stos() { delete[] dane; }
    void Push(const zespolona &z);

    // tego brakuje
    const zespolona& top() const; // throw gdy pusty
    zespolona& top(); // throw gdy pusty
    bool pop(); // zwraca false gdy stos pusty; odpowiednio powinien zmniejszac rozmiar tablicy, gdy count() < capacity() / 2
    bool empty() const { return count() == 0; }
    int count() const { return w; }
    int capacity() const { return liczba_el; }
};

edytowany 5x, ostatnio: rincewind, 2012-01-09 18:19

Pozostało 580 znaków

2012-01-09 16:16
0

Tak wiem, że jest niekompletna, całe zadanie jest bardzo długie a mnie interesują tylko fragmenty.
Nie jestem przekonany tylko co do realizacji tego stosu. Bo tak na prawdę przy odczytywaniu pokażę że to jest stos.Bo tak to tylko wczytuje po kolei wartości do tablicy.

A gdyby była taka treść:

Zadeklarować klasę stos reprezentującą stos liczb zespolonych (LIFO). Dane wewnątrz klasy
mają być przechowywane w liście dwukierunkowej.

To trzeba by zadeklarować typ elementu listy i potem używać go w klasie?


struct q_elem
{
    zespolona t;
    q_elem *next;
    q_elem *prev;
    q_elem(const zespolona &z):t(z), next(NULL), prev(NULL) {};
};

class stos
{

protected:
    q_elem *head;
    q_elem *tail;

public:
    ..

};

Jak to dalej napisać?

Na przykład tak: http://www.snippets.24bytes.com/2010/06/double-linked-list.html Chociaż do stosu wystarczająca w zupełności jest lista jednokierunkowa, w końcu i tak mamy dostęp tylko do ostatnio dodanego elementu, więc wystarczy dokładać do heada i stamtąd usuwać elementy. - rincewind 2012-01-09 16:26

Pozostało 580 znaków

2012-01-09 16:17
1

Ponadto po co w konstruktorze podawać rozmiar stosu, jeśli rośnie on dynamicznie?
Choćby po to, by (kiedy wiemy że będzie milion elementów) od razu podać jego rozmiar, by nie musiał rosnąć co chwilę niepotrzebnie.

edytowany 1x, ostatnio: Azarien, 2012-01-09 16:18
Racja, edytowałem mój kod. - rincewind 2012-01-09 16:19

Pozostało 580 znaków

2012-01-09 17:48
0

Czyli tak to powinno wyglądać? Masz racje ogon w przypadku listy dwukierunkowej i stosu się nie zmienia.

class zespolona
{
    double re_;
    dobule im_;
public:
    zespolona(double re = 0.0, double im = 0.0) : re_(re), im_(im) {}

};

struct q_elem
{
    zespolona t;
    q_elem *next;
    q_elem *prev;
    q_elem(const zespolona &z):t(z), next(NULL), prev(NULL) {};
};

class stos
{

protected:
    q_elem *head;
    q_elem *tail;

public:
    stos():head(NULL) {}
    void push(const zespolona &z);

};

void stos::push(const zespolona &z)
{
    q_elem *qep = new q_elem(z);
    if(head)
    {
        head->prev = qep;
        qep->next = head;
    }
     else
        head = qep;

};

Pozostało 580 znaków

2012-01-09 18:00

Po co wskaźnik prev? Jak mówiłem, wystarcza lista jednokierunkowa. Nawet, jeśli wolisz dwukierunkową, to Twoja implementacja nie jest prawidłowa, bo head nie powinien mieć elementu poprzedzającego (chyba, że to lista w formie pierścienia, co już kompletnie w tym przypadku nie ma sensu).

struct q_elem
{
    zespolona t;
    q_elem *next;
    // q_elem *prev; po co?
    q_elem(const zespolona &z):t(z), next(NULL)/*, prev(NULL)*/ {}
};

class stos
{
    q_elem *head;
    // q_elem *tail; po co?

public:
    stos():head(NULL) {}
    ~stos();
    void push(const zespolona &z);
    bool pop();
};

void stos::push(const zespolona &z)
{
    q_elem *qep = new q_elem(z);
    qep->next = head;
    head = qep;
};

bool stos::pop()
{
    if (head == NULL)
        return false;
    q_elem* tmp = head;
    head = head->next;
    delete tmp;
    return true;
};

stos::~stos()
{
    while (pop());
};

Warto też byłoby trzymać inta określającego rozmiar stosu. W konstruktorze ustawić na 0, inkrementować przy każdym push() i dekrementować przy pop() -- dzięki temu nie ma potrzeby przechodzenia całej listy, żeby sprawdzić jej długość (redukcja z O(n) do O(1)).


edytowany 1x, ostatnio: rincewind, 2012-01-09 18:24

Pozostało 580 znaków

2012-01-09 19:12
0

Ok, chyba już rozumiem. Dzięki za pomoc.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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