Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Lista jednokierunkowa uporządkowana - Pytanie o implementacje

Ostatnio zmodyfikowano 2014-07-10 22:32
Autor Wiadomość
kitsss
Temat założony przez niniejszego użytkownika
Lista jednokierunkowa uporządkowana - Pytanie o implementacje
» 2014-07-10 12:50:45
W celach dydaktycznych stworzyłem listę jednokierunkową uporządkowaną(trzyma dane w uporządkowanym rosnącym ciągu), która posiada funkcje: Wyświetlenie swojej poprawnej zawartości, Pobranie najmniejszego elementu (wraz z równoczesnym usunięciem go z listy), Wkładanie na listę nieograniczonej ilości liczb. Jest zabezpieczona przed różnymi sytuacjami, np. chęć usunięcia z listy większej ilości elementów, niż się w niej znajduje itp. Jak testowałem wszystko działa prawidłowo. I mam pytanie, z racji tego że zaimplementowałem samemu cały kod, tak jak zamierzałem, by się czegoś nauczyć, chciałbym wiedzieć, czy ten kod jest w miarę prawidłowy(bo funkcje swoje spełnia na pewno) - czyli, czy: dało się w wielu miejscach kodu napisać go czytelniej/mniej złożenie, czy użyłem jakiś ,,niezalecanych sposobów'', mówiąc w skrócie, chcąc dążyć do coraz lepszej jakości różnego rodzaju pisanych programów, chciałbym wiedzieć czym on od odbiega od dobrego, wzorcowego sposobu zaimplementowania takiej listy jednokierunkowej uporządkowanej. Jakby ktoś mógł spojrzeć byłbym bardzo wdzięczny i na pewno by mi to pomogło. Z góry dziękuje ;]  


C/C++
#include <iostream>
#include <cstdlib>

using namespace std;

class List_Orderliness
{
    float key; // Wartosc
    List_Orderliness * next; // Nastepnik
    List_Orderliness * previous; // Poprzednik
    bool Empty; // Czy lista jest pusta
   
public:
    void Print(); // Wyswietlenie zawartosci listy.
    void Add( float x ); // Dodanie i automatyczne poprawne umiejscowienie elementu na liscie
    List_Orderliness(); // Konstruktor
    float Take_First(); // Pobranie z listy pierwszego elementu - czyli wartosci zawsze najmniejszej
};

List_Orderliness::List_Orderliness() // Konstruktor domniemany
{
    key = 0;
    next = 0;
    previous = 0;
    Empty = 1;
}

void List_Orderliness::Add( float x ) // Dodanie i automatyczne poprawne umiejscowienie elementu na liscie
{
    if( next == 0 && previous == 0 && Empty == 1 ) // Gdy lista jest pusta.
    {
        key = x;
        Empty = 0;
        return;
    }
   
    List_Orderliness * new_argument = new List_Orderliness;
    List_Orderliness * wsk = this;
    List_Orderliness * wsk_backup = this;
   
    while( true )
    {
        if( wsk_backup->next == 0 ) // Gdy mamy doczynienia z ostatnim elementem listy (lub jedynym)
        {
            wsk_backup->next = new_argument;
            wsk_backup = wsk_backup->next;
            wsk_backup->key = x;
            wsk_backup->previous = wsk;
            break;
        }
       
        wsk = wsk->next; // wsk wskazuje na kolejny element
       
        if( wsk_backup->key > x ) // Jesli poprzedni element jest wiekszy od wartosci wkladanej na liste
        {
            wsk->previous = new_argument;
            new_argument->next = wsk;
            new_argument->key = wsk_backup->key;
            new_argument->previous = wsk_backup;
            wsk_backup->next = new_argument;
            wsk_backup->key = x;
            break;
        }
       
        if( x <= wsk->key ) // Jesli wstawiana wartosc jest mniejsza lub rowna nastepnemu elementowi
        {
            wsk->previous = new_argument;
            wsk_backup->next = new_argument;
            new_argument->previous = wsk_backup;
            new_argument->next = wsk;
            new_argument->key = x;
            break;
        }
       
        if( x > wsk->key ) // Jesli wstawiana wartosc jest wieksza niz nastepny element
        {
            if( wsk->next == 0 )
            {
                wsk->next = new_argument;
                new_argument->previous = wsk;
                new_argument->key = x;
                break;
            }
            else
                 wsk_backup = wsk;
           
        }
    }
}

void List_Orderliness::Print() // Wyswietlenie zawartosci listy.
{
    cout << "===============================" << endl;
    List_Orderliness * wsk = this;
    if( this->Empty == 1 )
    {
        cout << "Lista jest pusta." << endl;
        cout << "===============================" << endl;
        return;
    }
    for( int i = 1;; i++ )
    {
        cout << "Element " << i << " = " << wsk->key << endl;
        if( wsk->next == 0 )
             break;
       
        wsk = wsk->next;
    }
    cout << "===============================" << endl;
}

float List_Orderliness::Take_First() // Pobranie z listy pierwszego elementu - czyli wartosci zawsze najmniejszej.
{
   
    float tmp = this->key;
    if( Empty == 1 )
    {
        cout << "Lista jest pusta, zwracam 0." << endl;
        return 0.0;
    }
   
    if( this->next == 0 ) // Prawda - znaczy ze mamy doczynienia z ostatnim elementem na liscie.
    {
        this->key = 0;
        Empty = 1;
        return tmp;
    }
    else
    {
        List_Orderliness * wsk = this->next;
        if( wsk->next == 0 ) // Prawda - znaczy, ze mamy doczynienia z przedostatnim skladnikiem na liscie.
        {
            this->key = wsk->key;
            this->next = wsk->next;
            delete wsk;
            return tmp;
        }
        else
        {
            List_Orderliness * wsk2 = this->next;
            this->key = wsk->key;
            this->next = wsk->next;
            wsk = wsk->next;
            wsk->previous = this;
            delete wsk2;
            return tmp;
        }
    }
}

int main()
{
    List_Orderliness obiekt;
   
    obiekt.Add( 3 );
    obiekt.Add( 4 );
    obiekt.Add( 5 );
    obiekt.Add( 10 );
    obiekt.Add( 6 );
    obiekt.Add( 6 );
    obiekt.Add( 6 );
    obiekt.Add( 2 );
    obiekt.Add( 3 );
    obiekt.Add( 1 );
    obiekt.Add( 6 );
    obiekt.Add( 3.6 );
    obiekt.Add( - 2 );
    obiekt.Add( - 3.33390 );
    obiekt.Add( 10000 );
    obiekt.Add( - 10000 );
    obiekt.Add( 13 );
   
    obiekt.Print();
   
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
    obiekt.Take_First();
   
    obiekt.Print();
   
    obiekt.Add( 54 );
    obiekt.Add( 324 );
    obiekt.Add( 1 );
    obiekt.Add( - 666 );
   
    obiekt.Print();
   
    system( "PAUSE" );
    return 0;
P-113584
Monika90
» 2014-07-10 16:08:30
O tym jak projektować i implementować typy danych w C++ można napisać kilka książek. I zdaje się że już ktoś te książki napisał, więc zainteresuj się istniejącą literaturą, bo samemu daleko nie zajdziesz. Społeczności C++ dojście do tego jak prawidłowo używać C++ zajęło z 20 lat.

Ale kilka uwag Ci mogę napisać:
0. Nazwa klasy. List_Orderliness - co to w ogóle znaczy? Moze lepiej OrderedList albo SortedList?
1. Komentarze
// Konstruktor // Konstruktor domniemany
 niczego nie wnoszą.
2. Jeżeli to jest lista jednokierunkowa, to dlaczego są tam wskaźniki next i previous?
3. Nie uważasz że lepiej byłoby podzielić to na dwie klasy: SortedList i Node?
4. Po co jest składowa Empty?
5. Dlazego operacja Print nie ma atrybutu const, czyżby drukowanie modyfikowało listę?
6. Jak użytkownik klasy może sprawdzić ile jest elementów w liście, albo czy lista jest pusta?
7. W jaki sposób to zarządza pamiecią, nie widzę destruktora, konstruktora kopiującego, itp.
8. Składowa Empty jest typu bool, a prównujesz ją z liczbami całkowitymi - dlaczego?
9. Dlaczego to nie jet szablon?
P-113587
kitsss
Temat założony przez niniejszego użytkownika
» 2014-07-10 17:51:41
1 - Ok, przyjąłem
2 - Racja, zbędne jest previous
3 - Nie bardzo wiem jakie funkcje ma pełnić i czym jest klasa Node.
4 - By było prościej mi zaimplementować kod, mówi czy lista jest pusta.
5 - Racja, a drukowanie nie modyfikuje listy.
6 - Przy metodzie print wyświetlana jest ilość elementów, jednakże można prosto napisać kolejną metode np. How_Many zwracającą ilość elementów
7 - Jeśli pobieramy jakiś element, jego wartość jest zwracana a komórka w której był usuwana (wcześniej przed tym organizowane są odpowiednie połączenia sąsiedztwa) A gdzie i po co mam tu użyć destruktora kopiującego?
8 - Nie porównuje nigdzie zmiennej bool z liczbami całkowitymi, chyba że mowa o przyrównaniu do 1 lub 0, gdzie myślałem, że są równoważnym zapisem true oraz false.

Bardzo dziękuje za cenne wskazówki, poczytam o nich w najbliższym czasie. Monika90, polecasz jakieś konkretne zestawienia z literatury o której wspominałaś?
Dodam tylko, że z książek jedynie czytałem symfonie c++ (doszedłem mniej więcej do połowy książki - Dziedziczenie, w te wakacje mam zamiar ją dokończyć)
i programowania uczę się niecały rok, więc nie chciałbym była zbyt trudna na moim etapie programowania.

Dzięki wielkie za poświęcony czas!
P-113591
Monika90
» 2014-07-10 22:32:16
3 - Nie bardzo wiem jakie funkcje ma pełnić i czym jest klasa Node.
Node to węzeł w liście, jego rolą jest przechowywać dane i wskazywać na następny węzeł, jeśli następny istnieje. Przykład:
C/C++
struct Node
{
    float data;
    Node * next;
};

class List
{
public:
   
private:
    Node * first = nullptr;
};
List::first to wskaźnik do pierwszego węzła albo nullptr jeżeli lista jest pusta.

8 - Nie porównuje nigdzie zmiennej bool z liczbami całkowitymi, chyba że mowa o przyrównaniu do 1 lub 0, gdzie myślałem, że są równoważnym zapisem true oraz false.
Mowa o tym
if( this->Empty == 1 )
, wystrczyłoby to zapisać tak:
if( this->Empty )
P-113600
« 1 »
  Strona 1 z 1