Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
21.06.2012, 12:45 Uhr
~Zel24
Gast

Moin moin

Ich habe meine doppelt verkettete Liste und möchte dort über die Konsole Zahlen eingeben und diese DIREKT sortiert in die Liste einfügen.

Bisher sieht meine Methode so aus:

C++:

void DLink::insertSorted(DLink* newDLink, int iNumber) {

    if(this->suc != NULL ){ //1.
        this->suc->pre = newDLink;
    }

    newDLink->suc = this->suc;//2.
    newDLink->pre = this; //3.
    this->suc = newDLink; //4.
}

bisher werden die eingegebenen Zahlen einfach nur hinten angehängt^^

Jemand einen Vorschlag, wie ich das angehe?

Gruß Zel

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
22.06.2012, 10:50 Uhr
TOSHMAX

Dir wird wohl nicht viel mehr übrig bleiben als die Liste nach dem ersten Element zu durchsuchen, das >= dem Einzufügenden ist und dann dort das neue einzufügen. Das ist aber alles andere als performant, gerade bei größeren Listen.

Für Übungszwecke kannst du das Versuchen umzusetzen, aber für spätere Einsätze solltest du dir std::set und std::multiset genauer ansehen. Die sind eigentlich genau auf dieses Vorhaben ausgelegt.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
22.06.2012, 12:45 Uhr
ao

(Operator)

Hi,

das API finde ich etwas merkwürdig. Ich hätte sowas hier erwartet:

C++:

void DLink::insertSorted (int iNumber)

und die Funktion erzeugt selber einen neues List-Item, füllt den Inhalt und hängt es ein. Das ist die komfortabelste Variante - die Applikation muss sich um nichts kümmern.

Oder so:

C++:

void DLink::insertSorted (DLink * newDLink)

falls der Anwender freifliegende List-Items samt Inhalt selbst erzeugen soll - ich kann mir Situationen vorstellen, wo die Applikation und nicht die Containerklasse die Kontrolle über das Speichermanagement haben muss.

Aber beides hineinzureichen - wozu soll das gut sein?

Zur Performance: Stimmt, es gibt leistungsfähigere Strukturen, wenn es darum geht, Daten sortiert abzulegen. Aber ich schätze, es ist eine Übung, und es ist OK, wenn man einen Schritt nach dem anderen macht.

Dieser Post wurde am 22.06.2012 um 12:47 Uhr von ao editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
23.06.2012, 21:28 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

Zitat:

Aber beides hineinzureichen - wozu soll das gut sein?

vermutlich eine C Anbahnung
--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
24.06.2012, 21:12 Uhr
~Zel24
Gast

okay... dann muss ich die also einzeln vergleichen^^

Wie würdet ihr mir empfehlen, da durchzugehen?

Also im Grunde fehlt mir eine Schleife, wie ich von vorne bis hinten durchgehe und einzeln überprüfe:
<< eingegebene Zahl größer als die Zahl an der Position in der Kette, an der ich gerade bin? >>
Da hak ich gerade...^^

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
25.06.2012, 08:51 Uhr
ao

(Operator)

Na ja, du fängst am Anfang an (an this->suc) und hangelst dich an den suc-Zeigern entlang bis zum Ende (vermutlich erkennbar an suc == 0).

Und für den Vergleich müssten wir die Definition von DLink kennen.

Übrigens verwendest du, soweit ich sehe, nur eine einzige Klasse, nämlich DLink. Wenn DLink die Liste ist, dann brauchst du noch eine weitere Klasse, die einen Knoten in der Liste darstellt, z.B. DLinkNode. Denk mal drüber nach, dann wird dir auffallen, dass Liste und Knoten verschiedene Dinge sind, und dass du irgendwann einen Knoten im Hirn kriegst, wenn du beides mit demselben C++-Objekt abbilden willst.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
25.06.2012, 13:27 Uhr
~Zel24
Gast

C++:

void DLink::insertSorted(int iNumber) {

        DLink* newDLink = new DLink(iNumber);

        if(this->suc != NULL){ //1.
            cout << "Debug1" << endl;
            this->suc->pre = newDLink;

        }
        cout << "Debug2" << endl;
        while(newDLink != NULL) {

            cout << "Debug3" << endl;

            if(this->iContent > iNumber) { // Bedingung? fehlt: << this->zuVergleichenderWert > newDLink->zuVergleichenderWert (iNumber) >>
                cout << "Debug4" << endl;

                newDLink->suc = this->suc; //2.
                newDLink->pre = this; //3.
                this->suc = newDLink; //4.
                return;

            }

            if(true) { // Bedingung fehlt: << this->suc->zuVergleichenderWert > newDLink->zuVergleichenderWert (iNumber) >>

                newDLink->suc = this->suc; //2.
                newDLink->pre = this; //3.
                this->suc = newDLink; //4.
                return;
                cout << "Debug5" << endl;
            }
            cout << "Debug6" << endl;
            newDLink = newDLink->suc;

        }

}

Mein Versuch hier nochmal...^^ Ich hak halt jetzt bei den Bedinungen - wenn ich die Bedingungen hätte, meint ihr, das würde so funktionieren?^^

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
27.06.2012, 13:51 Uhr
TOSHMAX

Du bringst hier ziemlich viel durcheinander. Bspw. solltest du bevor du den neuen Knoten erstellst, erst mal den finden, vor den er eingefügt werden soll. Zum Beispiel so (vorausgesetzt die Liste ist bereits sortiert):

C++:

void DLink::insertSorted(int iNumber)
{
    DLink* cur = this->suc;
    while(cur != NULL) {
        if(cur->iContent >= iNumber) {
            // cur ist das erste Element größer-gleich iNumber
            // also iNumber hier vor cur einfügen!
            return;
        }

        cur = cur->suc;
    }

    // es wurde kein größeres Element gefunden
    // iNumber hier ans Ende der Liste anhängen
}

Aber wie ao schon sagt:
Eine Liste die ihren eigenen Anfang darstellt ist sehr verwirrend und macht alles nur unnötig kompliziert. Du solltest also unbedingt über das Design nachdenken.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (GNU/Linux, *NIX, *BSD und Co) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: