Ĺadny brzuch
Chodzi mi głównie o implementacje listy. Jestem ofiarą takiego nauczania, że ktoś daje ci kod i każe ci się go uczyć, a ja tego nie rozumiem. Ogólnie umiem napisać tablicowe implementacje wszystkich struktur, ale nie rozumiem działania wskaźnikowej. Zamieszczę kod, którego mam się nauczyć, implementujący listę.
#include <iostream> #include <stdlib.h> using namespace std; class Node { int liczba; Node *next; public: Node (int i) { liczba = i; next = NULL; } int Liczba () { return liczba; } Node * Next () { return next; } void changeNext (Node *n) { next = n; } }; class List { Node *L; public: List () { L = NULL; } ~List () { removeallNode (); } bool emptyList (); // zwraca 1, jesli lista jest pusta void addNode (Node *n); //dodaje wierzchołek n na początek listy void printNode (); //drukuje listę void removeNode (Node *n); //usuwa wierzchołek void removeallNode (); //usuwa całą listę Node *locateNode (int i); //zwraca wskaźnik do wierzchołka zawierającego wartość i }; bool List::emptyList (){ // zwraca 1, jesli lista jest pusta if (L == NULL) return 1; else return 0; } void List::addNode (Node *n){ //dodaje wierzchołek n na początek listy n -> changeNext (L); L = n; } void List::printNode (){ //drukuje listę Node *q; q = L; while (q != NULL) { cout << q -> Liczba() << endl; q = q -> Next(); } } void List::removeNode (Node *n){ //usuwa wierzchołek if (L == n) { L = L -> Next(); delete n; } else { Node *q; q = L; while ((q -> Next() != NULL) && (q -> Next() != n)) q = q -> Next(); if (q -> Next() == n) { q -> changeNext (q -> Next() -> Next()); delete n; } } } void List::removeallNode (){ //usuwa całą listę Node *q; while (L != NULL) { q = L; L = L -> Next (); delete q; } } Node *List::locateNode (int i){ //zwraca wskaźnik do wierzchołka zawierającego wartość i Node *q; q = L; while ((q != NULL) && (q -> Liczba() != i)) q = q -> Next (); return q; } int main () { int wybor, liczba; List lista; do { cout << "****************************\n"; cout << "* Lista pojedynczo wiazana *\n"; cout << "****************************\n"; cout << "\n\n1 - dodawanie liczby do listy\n"; cout << "2 - drukowanie listy\n"; cout << "3 - usuwanie liczby z listy\n"; cout << "4 - usuwanie wszystkich liczb\n"; cout << "5 - szukanie liczby\n"; cout << "0 - wyjscie z programu\n"; cout << "Twoj wybor?\t"; cin >> wybor; switch (wybor) { case 1: cout << "\n\nPodaj liczbe:\t"; cin >> liczba; Node *q; q = new Node (liczba); lista.addNode(q); break; case 2: if (!lista.emptyList()) { cout << "\n\nNa liscie sa:\n"; lista.printNode(); } else cout << "\n\nLista pusta\n"; system ("PAUSE"); break; case 3: cout << "\n\nPodaj liczbe:\t"; cin >> liczba; Node *r; r = lista.locateNode(liczba); if Ĺ˝ lista.removeNodeĹ˝; else cout << "\n\nNie ma takiej liczby na liscie\n"; system ("PAUSE"); break; case 4: lista.removeallNode(); break; case 5: cout << "\n\nPodaj liczbe:\t"; cin >> liczba; Node *s; s = lista.locateNode(liczba); if (s) cout << "Liczba jest na liscie\n"; else cout << "Liczby nie ma na liscie\n"; system ("PAUSE"); break; } system ("CLS"); } while (wybor != 0); return 0; }
I jak byście mi mogli jeszcze objaśnić rolę wskaźników i w ogóle działanie tego sposobu to będę wam ogromnie wdzięczny. Jeszcze takie prośby organizacyjne: przeszukałem google, jeśli gdzieś czytam i nie rozumiem to zwracam się do was do ludzi, bo wam mogę zadawać dowolne pytania a tekstowi w necie nie.
Użytkownik zimbabwe edytował ten post 15 kwiecień 2008, 19:58
A znasz ogólną zasadę działania listy?
Lista (tu jedno-węzłowa, zwana na wiele różnych sposobów, chodzi o to, że można się poruszać po niej tylko w jedną stronę) zawiera:
-daną podaną przez użytkownika
-wskaźnik do kolejnego elementu
W ten sposób tworzy się sekwencja powiązanych elementów o tyle lepsza od tablicy, że aby poukładać w innej kolejności jego zawartość wystarczy tylko zmienić tylko wskaźniki elementów. Tak samo ze wstawianiem elementów pomiędzy inne - wystarczy zmiana jednego wskaźnika i już. Jednak minusem jest to, że aby dostać się do ostatniego elementu listy, należy iterować po wszystkich odczytując wskaźniki Next, aż dojdzie się do ostatniego (funkcja List::locateNode). Nie ma możliwości dostępu do elementów listy po indeksach, jak w tablicy, gdyż elementy listy są luźno poukładane w pamięci i jedyne co je wiąże to właśnie ten wskaźnik.
Wskaźnik to obiekt danego typu wskazujący na inny obiekt. Pozwala na natychmiastowy dostęp do danej, gdyż zawiera bezpośredni jej adres w pamięci. Oznacza się je gwiazdką *
int liczba; to element listy, wartość, którą wpisujemy doń.
Node * next; to wskaźnik typu Node do kolejnego elementu listy.
Implementacja tej listy jest tu klasą Node, nie zawiera jednak ona funkcji do właściwej obsługi listy. (Właściwie jest to pojemnik do przechowywania liczby oraz wskaźnika do jej następcy.) Te funkcje są w klasie List, która, zauważ, zawiera w sobie wskaźnik typu Node*
Pytania?
Użytkownik Lupinek edytował ten post 15 kwiecień 2008, 20:34
Czy za każdym nowym elementem tworzony jest nowy obiekt typu Node. Jak to działa czy my mamy w jednym momencie do dyspozycji jeden element, czy wszystkie?
W kodzie jest kilka błędów, funkcja removeNode powinna być typu bool a nie node i w linijce chyba 120
if Ĺ˝ lista.removeNodeĹ˝;
powinno być:
if (r)lista.removeNode(r);
Tak, jeśli skompilujesz to zobaczysz, że w dowolnym momencie możesz dowolną liczbę dodać, usunąć, usunąć wszystkie, a także wszystkie wypisać.
W tym kodzie występują wskaźniki np. q czy s. Ja dalej do końca nie rozumiem tego kodu, ale już mi trochę rozjaśniliście więc i tak się ciesze. Mógłby mi ktoś wypisać ile wskaźników jest do obsługi listy potrzebne, do czego służą i jak się nazywają w kodzie. Wtedy to już mam nadzieję że zrozumiem do końca.
w zasadzie w teoretycznie wystarczy jeden wskaznik w strukturze wskazujacy na nastepny element (next), ale poniewaz pierwszy element nie ma "rodzica" musi byc dodatkowy wskauzjacy na pierwszy element (L)..
poza tym w kazdej liscie musi byc wskaznik, umozliwiajacy poruszanie sie po jej elementach (q)..
ale to wszytko koledzy Ci wczesniej wyjasnili :>
Jeśli masz gdzieś dostęp do książki Pasja C++ (J. Grębosz), to tam jest wyjaśniona lista jedno- i dwukierunkowa oraz napisana jest z dokładnym tłumaczeniem jej implementacja przez autora.
Dzięki za pomoc, teraz na pewno już wiem jak obsłużyć listę, natomiast do książki Pasja C++ na pewno zajrzę.
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
#include <iostream> #include <stdlib.h> using namespace std; class Node { int liczba; Node *next; public: Node (int i) { liczba = i; next = NULL; } int Liczba () { return liczba; } Node * Next () { return next; } void changeNext (Node *n) { next = n; } }; class List { Node *L; public: List () { L = NULL; } ~List () { removeallNode (); } bool emptyList (); // zwraca 1, jesli lista jest pusta void addNode (Node *n); //dodaje wierzchołek n na początek listy void printNode (); //drukuje listę void removeNode (Node *n); //usuwa wierzchołek void removeallNode (); //usuwa całą listę Node *locateNode (int i); //zwraca wskaźnik do wierzchołka zawierającego wartość i }; bool List::emptyList (){ // zwraca 1, jesli lista jest pusta if (L == NULL) return 1; else return 0; } void List::addNode (Node *n){ //dodaje wierzchołek n na początek listy n -> changeNext (L); L = n; } void List::printNode (){ //drukuje listę Node *q; q = L; while (q != NULL) { cout << q -> Liczba() << endl; q = q -> Next(); } } void List::removeNode (Node *n){ //usuwa wierzchołek if (L == n) { L = L -> Next(); delete n; } else { Node *q; q = L; while ((q -> Next() != NULL) && (q -> Next() != n)) q = q -> Next(); if (q -> Next() == n) { q -> changeNext (q -> Next() -> Next()); delete n; } } } void List::removeallNode (){ //usuwa całą listę Node *q; while (L != NULL) { q = L; L = L -> Next (); delete q; } } Node *List::locateNode (int i){ //zwraca wskaźnik do wierzchołka zawierającego wartość i Node *q; q = L; while ((q != NULL) && (q -> Liczba() != i)) q = q -> Next (); return q; } int main () { int wybor, liczba; List lista; do { cout << "****************************\n"; cout << "* Lista pojedynczo wiazana *\n"; cout << "****************************\n"; cout << "\n\n1 - dodawanie liczby do listy\n"; cout << "2 - drukowanie listy\n"; cout << "3 - usuwanie liczby z listy\n"; cout << "4 - usuwanie wszystkich liczb\n"; cout << "5 - szukanie liczby\n"; cout << "0 - wyjscie z programu\n"; cout << "Twoj wybor?\t"; cin >> wybor; switch (wybor) { case 1: cout << "\n\nPodaj liczbe:\t"; cin >> liczba; Node *q; q = new Node (liczba); lista.addNode(q); break; case 2: if (!lista.emptyList()) { cout << "\n\nNa liscie sa:\n"; lista.printNode(); } else cout << "\n\nLista pusta\n"; system ("PAUSE"); break; case 3: cout << "\n\nPodaj liczbe:\t"; cin >> liczba; Node *r; r = lista.locateNode(liczba); if Ĺ˝ lista.removeNodeĹ˝; else cout << "\n\nNie ma takiej liczby na liscie\n"; system ("PAUSE"); break; case 4: lista.removeallNode(); break; case 5: cout << "\n\nPodaj liczbe:\t"; cin >> liczba; Node *s; s = lista.locateNode(liczba); if (s) cout << "Liczba jest na liscie\n"; else cout << "Liczby nie ma na liscie\n"; system ("PAUSE"); break; } system ("CLS"); } while (wybor != 0); return 0; }
I jak byście mi mogli jeszcze objaśnić rolę wskaźników i w ogóle działanie tego sposobu to będę wam ogromnie wdzięczny. Jeszcze takie prośby organizacyjne: przeszukałem google, jeśli gdzieś czytam i nie rozumiem to zwracam się do was do ludzi, bo wam mogę zadawać dowolne pytania a tekstowi w necie nie.
Użytkownik zimbabwe edytował ten post 15 kwiecień 2008, 19:58
A znasz ogólną zasadę działania listy?
Lista (tu jedno-węzłowa, zwana na wiele różnych sposobów, chodzi o to, że można się poruszać po niej tylko w jedną stronę) zawiera:
-daną podaną przez użytkownika
-wskaźnik do kolejnego elementu
W ten sposób tworzy się sekwencja powiązanych elementów o tyle lepsza od tablicy, że aby poukładać w innej kolejności jego zawartość wystarczy tylko zmienić tylko wskaźniki elementów. Tak samo ze wstawianiem elementów pomiędzy inne - wystarczy zmiana jednego wskaźnika i już. Jednak minusem jest to, że aby dostać się do ostatniego elementu listy, należy iterować po wszystkich odczytując wskaźniki Next, aż dojdzie się do ostatniego (funkcja List::locateNode). Nie ma możliwości dostępu do elementów listy po indeksach, jak w tablicy, gdyż elementy listy są luźno poukładane w pamięci i jedyne co je wiąże to właśnie ten wskaźnik.
Wskaźnik to obiekt danego typu wskazujący na inny obiekt. Pozwala na natychmiastowy dostęp do danej, gdyż zawiera bezpośredni jej adres w pamięci. Oznacza się je gwiazdką *
int liczba; to element listy, wartość, którą wpisujemy doń.
Node * next; to wskaźnik typu Node do kolejnego elementu listy.
Implementacja tej listy jest tu klasą Node, nie zawiera jednak ona funkcji do właściwej obsługi listy. (Właściwie jest to pojemnik do przechowywania liczby oraz wskaźnika do jej następcy.) Te funkcje są w klasie List, która, zauważ, zawiera w sobie wskaźnik typu Node*
Pytania?
Użytkownik Lupinek edytował ten post 15 kwiecień 2008, 20:34
Czy za każdym nowym elementem tworzony jest nowy obiekt typu Node. Jak to działa czy my mamy w jednym momencie do dyspozycji jeden element, czy wszystkie?
W kodzie jest kilka błędów, funkcja removeNode powinna być typu bool a nie node i w linijce chyba 120
if Ĺ˝ lista.removeNodeĹ˝;
powinno być:
if (r)lista.removeNode(r);
Tak, jeśli skompilujesz to zobaczysz, że w dowolnym momencie możesz dowolną liczbę dodać, usunąć, usunąć wszystkie, a także wszystkie wypisać.
W tym kodzie występują wskaźniki np. q czy s. Ja dalej do końca nie rozumiem tego kodu, ale już mi trochę rozjaśniliście więc i tak się ciesze. Mógłby mi ktoś wypisać ile wskaźników jest do obsługi listy potrzebne, do czego służą i jak się nazywają w kodzie. Wtedy to już mam nadzieję że zrozumiem do końca.
w zasadzie w teoretycznie wystarczy jeden wskaznik w strukturze wskazujacy na nastepny element (next), ale poniewaz pierwszy element nie ma "rodzica" musi byc dodatkowy wskauzjacy na pierwszy element (L)..
poza tym w kazdej liscie musi byc wskaznik, umozliwiajacy poruszanie sie po jej elementach (q)..
ale to wszytko koledzy Ci wczesniej wyjasnili :>
Jeśli masz gdzieś dostęp do książki Pasja C++ (J. Grębosz), to tam jest wyjaśniona lista jedno- i dwukierunkowa oraz napisana jest z dokładnym tłumaczeniem jej implementacja przez autora.
Dzięki za pomoc, teraz na pewno już wiem jak obsłużyć listę, natomiast do książki Pasja C++ na pewno zajrzę.