Lista kolejka stos pomoc przy implementacji c++


(Kasiek131b) #1

Witam,


(Dimatheus) #2

nokia_18 , zapoznaj się, proszę, z tym tematem i stroną, a następnie - korzystając z przycisku Edytuj (na dole pierwszego posta po prawej stronie) i opcji Użyj pełnego edytora - popraw tytuł wątku tak, by mówił konkretnie o problemie. Poprawnie zatytułowany wątek zwiększa szansę na uzyskanie szybkiej pomocy. Zignorowanie tej prośby będzie skutkować przeniesieniem tematu do kosza.

Pozdrawiam,

Dimatheus


(KamilDz) #3

 

Kolejka to taka lista w której dodajesz element na końcu, a usuwasz i pobierasz tylko z początku.

Stos to taka lista na której odkładasz elementy na końcu, i pobierasz i usuwasz też z końca.

Zdaje się, że temat dobrze opisał Grębosz w Pasji C++. Książka przestarzała więc do nabycia tylko w wersji pirackiej, lub bibliotece. 

 

Czy rozumiesz wskaźniki? Bo bez tego nie da się pojąć listy. Czy rozumiesz referencje?

Lista się składa z struktur/obiektów które zawierają jakieś dane i wskaźnik na kolejny element tego typu. W tym programie za to robi struktura node.

Proszę obejrzeć rysunki z https://en.wikipedia.org/wiki/Node_(computer_sciencehttps://pl.wikipedia.org/wiki/Lista. Ogólnie polecam Wikipedię, choć widać, że edytorzy mają problemy komunikacyjne. 

 

Lista polega na: Tworzymy wiele elementów node. Pierwszy element we wskaźniku wskazuje na drugi element, drugi element we wskaźniku wskazuje na trzeci element, trzeci element w swoim wskaźniku wskazuje na NULL (co oznacza koniec listy). Żeby odczytać całą listę potrzebujemy tylko dostępu do pierwszego elementu (bo resztę dostaniemy z wskaźników).

AddS - dodawanie do listy. Tworzy nowy obiekt node. Kopiuje do niego wartość int. Jego wskaźnik ustawia tak by wskazywał na dawny pierwszy obiekt. I oznacza że ten element jest pierwszy obiekt (początkiem listy).

DelS to usuwanie. Usuwa pierwszy element i jako pierwszy oznacza drugi element.

 

Nie wiem w czym jest problem w Twoim zrozumieniu. Najprawdopodobniej w słabej znajomości C++. Spróbuj zrozumieć idee listy bez funkcji i referencji. Na tym przykładowym programie:

#include <iostream>
using namespace std;

struct node{
int val;
node*next;
};

int main()
{
    //tworzymy trochę obiektow node i 'kopiujemy' do nich wartosci int (liczbowe)
    node *p1= new node;
     p1->val=10;
    node *p2= new node;
     p2->val=15;
    node *ptrzy= new node;
     ptrzy->val=40;
    node *p4= new node;
     p4->val=20;

    //teraz używając wskaźników dowiązujemy jeden obiekt do drugiego itd
    p1->next=p2;
    p2->next=ptrzy;
    ptrzy->next=p4;
    p4->next=NULL; //tak oznaczamy obiekt ostatnii.

    //Jako początek listy oznaczamy obiekt p1
    node *poczatek=p1;

    //teraz usuwamy pierwszy element listy.
    node *tymczasowy=poczatek->next; //zapamiętujemy wskaźnik na drugi element listy
    delete poczatek; //usuwamy pierwszy element listy
    poczatek= tymczasowy; // jako pierwszy element oznaczamy drugi element listy.


    //teraz wyswietlamy listę.
    node *x=poczatek; // x bedzie nam sluzyl do chodzenia po liscie.
    cout << x->val<<"->"; //wyswietlamy wartosc inta
    x = x->next; // bierzemy kolejny obiekt
    cout << x->val<<"->";
    x = x->next; // bierzemy kolejny obiekt
    cout << x->val<<"->";
// x = x->next; // to wskazuje na NULL wiec wyswietlenie moze
// cout << x->val<<"->";


    //dodamy jeszcze jeden element na początku.
    node *p0= new node;
    p0->val=-2;
    p0->next=poczatek; //do p0 dowiązujemy resztę listy od początkowego element.
    poczatek= p0; // jako pierwszy element oznaczamy p0

    //teraz wyswietlamy listę, cztery pierwsze pozycje. Oczywiscie lepiej to robic w pętli.
    cout <<endl<< "nowa lista"<<endl;
    x=poczatek; //
    cout << x->val<<"->"; //wyswietlamy wartosc inta
    x = x->next; // bierzemy kolejny obiekt
    cout << x->val<<"->";
    x = x->next; // bierzemy kolejny obiekt
    cout << x->val<<"->";
    x = x->next; // bierzemy kolejny obiekt
    cout << x->val<<"->";




    int a; cin>> a;

}

Czy wszytko jest jasne?