Umsetzungsproblem: Verkettete Liste als Klasse

UNeverNo

Verkettete Listen habe ich früher schon einmal in Pascal benutzt, allerdings nicht häufig, von der Theorie bilde ich mir ein es verstanden zu haben. Allerdings bekomme ich die Umsetzung auf das konkrete Problem nicht so richtig hin. Wäre deshalb nett, wenn mir hier geholfen werden würde

class CListe
    {
        long *diff;
        public:
            CListe(void); //Konstruktor
            void SetzeStart(void);
            void SetzeEnde(void);
            float BerechneDiff(void);
            // ~CListe(void); //Destruktor
            CListe *next; //Zeiger auf nächstes Element
    }

Soweit sollte das schon richtig sein. Nun brauche ich noch zwei long-Variablen, die aber nicht zur Liste selbst gehören sollen, sondern nur als Zwischenspeicher dienen sollen. Ich habe allerdings keine Idee wie ich diese aus dem Listen-Konstrukt heraushalte

Die Methode SetzeStart soll der einen long-Variable einen Wert zuweisen, die Methode SetzeEnde der zweiten long-Variable einen Wert und anschließend die Differenz der beiden Werte berechnen und im jeweiligen *diff speichern. In der Methode BerechneDiff sollen alle Diff-Werte addiert und durch die Anzahl dividirt werden, dabei könnte ich die Elemente eigentlich direkt löschen, d.h. der Destruktor fällt weg.
Was muss beim Konstruktor gemacht werden? Ich dachte daran den Anker auf NULL zu setzen.

DocJunioR

static long var1, var2;

und dann musst du noch nen
static long CListe::var1=0;
static long CListe::var2=0;
nach der Klassendeklaration machen.

UNeverNo

Wo muß ich das einfügen? Denn wenn ich es einfach in die Klasse einfüge so hat doch jedes Element diese Variablen, oder?

pumuckl

nein. Schau dir mal im C++-Buch deiner Wahl die Bedeutung von static an. Das sorgt dafür, dass es die entsprechende Variable nur genau einmal pro Klasse gibt.

HumeSikkins

Schau dir mal im C++-Buch deiner Wahl die Bedeutung von static an

Und ein kurzer Blick in unsere FAQ kann auch nicht schaden:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-39472.html
http://www.c-plusplus.net/forum/viewtopic-var-t-is-39471.html

UNeverNo

Ich hab schon in ein paar Büchern/Tutorials gelesen, static aber bisher nur so aufgefaßt, daß der Wert der Variable zwischen den Aufrufen erhalten bleibt

Ich habe es jetzt mal wie vorgeschlagen eingefügt, meine CZeit.h sieht jetzt so aus:

CZeit.h

class CZeit
{
    long *diff;
    static long start, ende;
    public:
        CZeit(void); //Konstruktor
        void SetzeStart(void); //
        void SetzeEnde(void); //
        float BerechneDiff(void); //
        ~CZeit(void); //Destruktor
        CZeit *next; //Zeiger auf nächste Element
};

Allerdings habe ich nun das Problem, dass sich die Static-Variablen nicht mit

static long CZeit::start = 0;

initialisieren lassen, der Compiler liefert mir da

`static' may not be used when defining (as opposed to declaring) a static data member

Caipi

UNeverNo schrieb:

Allerdings habe ich nun das Problem, dass sich die Static-Variablen nicht mit
static long CZeit::start = 0;
initialisieren lassen, der Compiler liefert mir da

`static' may not be used when defining (as opposed to declaring) a static data member

Bei der Definition bzw. der Initialisierung einer Statischen Element-Variablen musst du die static Deklaration weglassen.
D.h.

long CZeit::start = 0;

Caipi

UNeverNo

Danke, das hat mir schon einmal weitergeholfen

Jetzt habe ich das nächste Problem und zwar in der

CZeit.cpp

void CZeit::SetzeEnde(void)        
{
    CZeit *element = new CZeit;
    element->diff = 15;
    element->next = anker;
    anker = element;
}

Ich muß das anker-Element irgendwo definieren

CZeit *anker = 0;

so daß es in allen Methoden verfügbar ist. Wie geht das

edit: Hat sich erledigt

UNeverNo

Das Programm läuft soweit, allerdings funktioniert es nicht richtig. Muß ich mit Referenzen arbeiten (wenn ja, wo und wie, wenn nein woran liegt es dann)?

CZeit.h

class CZeit
{
    long diff; //speichert start-ende ab
    static long start, ende; //zwischenspeicher
    public:
        CZeit(void); //Konstruktor
        void SetzeStart(void); //speichert Startzeit auf start
        void SetzeEnde(void);   //speichert Endzeit auf ende, und Differenz auf element->diff
        float BerechneDiff(void); //summiert alle diff auf, dividiert diese durch anzahl diff, und dient gleichzeitig als destruktor
        CZeit *next; //Zeiger auf nächste Element
};

CZeit.cpp

#include <time.h>
#include <iostream>
#include <Chris/CZeit/CZeit.h>
using namespace std;

long CZeit::start = 0;
long CZeit::ende = 0;
CZeit *anker = 0;

CZeit::CZeit(void)
{
    start = 0;
    ende = 0;
}

void CZeit::SetzeStart(void)
{
    start = clock();
}

void CZeit::SetzeEnde(void)        
{
    ende = clock();
    CZeit *element = new CZeit;
    element->diff = (ende - start);
    element->next = anker;
    anker = element;
}

float CZeit::BerechneDiff(void)
{
    long temp = 0;
    int i = 0;
    CZeit *old;
    while (anker)
    {
        temp = temp + anker->diff;
        old = anker;
        anker = anker->next;
        delete old;
    }    
    return temp / i / CLOCKS_PER_SEC;
}

main.cpp

#include <time.h>
#include <iostream>
#include <Chris/CZeit/CZeit.h>

using namespace std;

int main(void)
{
    CZeit zeitmessung;
    for (int i = 0; i < 10; i++)
    {
        zeitmessung.SetzeStart();
        //Beginn zu testender Algorithmus
        for (int j = 0; j < 5000; j++)
        {
            long k;
            k = j * j * j;
            cout << j << ": " << k << endl;
        }    
        //Ende
        zeitmessung.SetzeEnde();
    }       
    cout << "Durchschnittlich verbrauchte Zeit: " << zeitmessung.BerechneDiff();
    getchar();

    return 0;
}

Danke, ein (letztes?) Mal

Werner Salomon

Hmm - mir ist gar nicht klar wieso Du hier eigentlich die Liste benötigst. Was hälst Du von dieser - ganz anderen Lösung?

#include <iostream>
#include <time.h>

class CUhr
{
public:
    CUhr()
        : m_start( 0 )
        , m_sum( 0 )
        , m_nStopps( 0 )
    {}

    struct Stopper;
    friend Stopper;
    struct Stopper // noncopyable
    {
        explicit Stopper( CUhr& uhr )
            : m_uhr( uhr )
        {
            m_uhr.Start();
        }
        ~Stopper()
        {
            m_uhr.Stopp();
        }
    private:
        CUhr& m_uhr;
    };

    friend std::ostream& operator<<( std::ostream& out, const CUhr& uhr )
    {
        return out << double( uhr.m_sum ) / CLOCKS_PER_SEC / uhr.m_nStopps << " Sek";
    }

private:
    void Start() 
    { 
        m_start = clock(); 
    }
    void Stopp()
    {
        m_sum += clock() - m_start;
        ++m_nStopps;
    }

    clock_t m_start;
    clock_t m_sum;
    int     m_nStopps;
};

int main()
{
    using namespace std;
    CUhr uhr;
    for (int i = 0; i < 10; i++)
    {
        CUhr::Stopper stopper( uhr );
        //Beginn zu testender Algorithmus
        for (int j = 0; j < 5000; j++)
        {
            long k;
            k = j * j * j;
            cout << j << ": " << k << endl;
        }    
        //Ende
    }   // Scope-Ende stoppt die Uhr in ~Stopper      
    cout << "Durchschnittlich verbrauchte Zeit: " << uhr << endl;
    getchar();

    return 0;
}

Gruß
Werner

Werner Salomon

In dem Konstruktor von CZeit

UNeverNo schrieb:

CZeit::CZeit(void)
{
    start = 0;
    ende = 0;
}

setzt Du die statischen Variablen 'start' und 'ende' auf 0. Wenn man einen Konstruktor aufruft, so wie hier:

UNeverNo schrieb:

void CZeit::SetzeEnde(void)        
{
    ende = clock();
    CZeit *element = new CZeit;
    element->diff = (ende - start);
    element->next = anker;
    anker = element;
}

wird 'ende' erst mit der aktuellen Zeit belegt und danach inklusive 'start' wieder auf 0 gesetzt.

An dieser Stelle

UNeverNo schrieb:

float CZeit::BerechneDiff(void)
{
    long temp = 0;
    int i = 0;
    CZeit *old;
    while (anker)
    {
        temp = temp + anker->diff;
        old = anker;
        anker = anker->next;
        delete old;
    }    
    return temp / i / CLOCKS_PER_SEC;
}

hast Du vergessen 'i' in der Schleife zu inkrementieren. Du teilst immer durch 0.

Noch ein Tipp: Initialisieren die Member in der Initalisierungsliste im Konstruktor. Dann wird's einfacher - etwa so:

CZeit::CZeit( long Diff, CZeit* Next )
    : diff( Diff )
    , next( Next )
{}

void CZeit::SetzeEnde()
{
    anker = new CZeit( clock() - start, anker );
}

Gruß
Werner

UNeverNo

Mhh bisher hatte ich es so verstanden, dass ein Konstruktor aufgerufen wird, wenn ein Objekt erzeugt wird, d.h. in meinem Fall

CZeit *anker = 0;

, nicht wenn ich eine Methode aufrufe

Ich habe den Konstruktor jetzt erst einmal ganz herausgenommen, das mit dem i++; hinzugefügt und noch ein Cast hinzugefügt. Dadurch funzt dans Programm nun

Allerdings verstehe ich folgende Zeilen von Dir nicht.

CZeit::CZeit( long Diff, CZeit* Next )
    : diff( Diff )
    , next( Next )
{}

void CZeit::SetzeEnde()
{
    anker = new CZeit( clock() - start, anker );
}

Kannst Du mir das bitte noch einmal etwas näher erläutern? Danke.

Werner Salomon

UNeverNo schrieb:

Mhh bisher hatte ich es so verstanden, dass ein Konstruktor aufgerufen wird, wenn ein Objekt erzeugt wird, d.h. in meinem Fall
CZeit *anker = 0;
, nicht wenn ich eine Methode aufrufe

Das ist kein Konstruktor, sondern eine (statische) Variable. Der Konstruktor wird immer dann aufgerufen, wenn Du ein Objekt der Klasse anlegst. Hier auf dem Heap

CZeit *element = new CZeit;

und hier auf dem Stack

CZeit zeitmessung;

UNeverNo schrieb:

Allerdings verstehe ich folgende Zeilen von Dir nicht.
CZeit::CZeit( long Diff, CZeit* Next )
    : diff( Diff )
    , next( Next )
{}

void CZeit::SetzeEnde()
{
    anker = new CZeit( clock() - start, anker );
}
Kannst Du mir das bitte noch einmal etwas näher erläutern? Danke.

Also die erste Methode ist ein Konstruktor mit zwei Parametern. Ein Objekt der Klasse CZeit hat zwei Member 'diff' und 'next'. Grundsätzlich sollte man es anstreben, die Member einer Klasse in der Initialisierungsliste zu belegen. Die Initialisierungsliste ist die Konstruktion die mit ':' beginnt.

Ich hol' mal bißchen weiter aus. Stell Dir folgende Klasse vor.

class Klasse1
{
public:
    Klasse1();  // Konstruktor
    std::string m_txt; // Member
};

Angenommen im Konstruktor von Klasse1 soll der Member 'm_txt' belegt werden. Also

Klasse1::Klasse1()
{
    m_txt = "irgendwas";
}

Zu dem Zeitpunkt zu dem 'm_txt = ' aufgerufen wird, muss m_txt bereits ein vollständig initialisiertes Objekt sein, sonst geht die Zuweisung in die Hose. Also muss vorher implizit ein (Default-)Konstruktor von std::string aufgerufen worden sein, da std::string kein trivialer Typ ist - es wird hier dynamisch Speicher verwaltet.
Angenommen die Designer von std::string hätten entschieden, dass sie quasi auf Verdacht 8 Byte Speicher allokieren. Dann würde man bei der Zuweisung von "irgendwas" diesen wieder verwerfen und mindestens 10 Byte allokieren, damit 'irgendwas\0' reinpasst. Das wäre dann ziemlich imperformant erst 8 Byte allokieren, dann wieder löschen für nichts.
Schlauer wäre es doch, dem Member 'm_txt' schon vor (!) seiner Geburt den String mitgeben zu können, damit er von vornherein weiß, wieviel Speicher er anlegen muss. Also besser:

Klasse1::Klasse1()
    : m_txt( "irgendwas" )
{}

Hier wird jetzt nicht implizit der Default-Konstruktor von std::string, sondern explizit der Konstruktor aufgerufen, der ein Literal als Parameter aufnimmt. Dieser Konstruktor kann jetzt die Länge des Strings feststellen, allokiert passend Spiecher, rein mit dem String und alles ist gut. Kein Weg war vergebens .

Das und auch die Tatsache, dass alle Member 'vernünftige' Werte annehmen sollte, bevor (!) das '{' des Konstruktors erreicht wird, sind der Grund für die Initialisierungsliste.

Der Ausdruck

anker = new CZeit( clock() - start, anker );

macht jetzt genau das selbe wie

ende = clock();
    CZeit *element = new CZeit;
    element->diff = (ende - start);
    element->next = anker;
    anker = element;

Die Variable 'ende' wird wie eine lokale Variable benutzt, einmal mit clock() beschrieben und anschließend nur einmal benutzt und danach nie wieder, also kann man sie weglassen.

CZeit *element = new CZeit;
    element->diff = (clock()- start);
    element->next = anker;
    anker = element;

Die Initialisierung der Member 'diff' und 'next' habe ich in den (neuen) Konstruktor verschoben (s.o.). Daher brauche (darf) ich es später nicht mehr tun.

CZeit *element = new CZeit( clock()- start, anker );
    anker = element;

Ja - und jetzt sieht man das die lokale Variable 'element' auch nur einmal beschrieben und benutzt wird, also kann man sie auch weglassen.

anker = new CZeit( clock()- start, anker );

Gruß
Werner

Werner Salomon

Ah - ich sehe gerade, dass nicht nur die Leute die Fragen haben, vorher die FAQ lesen sollten, sondern auch jemand der antwortet.
siehe auch hier http://www.c-plusplus.net/forum/viewtopic-var-t-is-39484.html

UNeverNo

Ich sehe, daß Du Dich schon etwas länger mit C++ befaßt

Ich beginne so langsam Deinen Code zu verstehen, danke für die Erläuterungen.

Das mit ende hatte ich gemacht, um genauere Werte zu bekommen, denn ich dachte mir wenn ich z.B. [cpp]diff = clock() - start;[/code] code, diese Aktion auch schon wieder Zeit verbraucht, kann mich natürlich auch irren