Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
26.11.2011, 22:31 Uhr
~Yeah1000
Gast

hallo leute,
ich hoffe ich hab mich nicht zu blöd angestellt bei der suche ob dieses thema hier schonmal besprochen wurde.

ich hab folgende aufgabe und bräuchte hilfe oder anregungen wie ich das realisieren könnte:

Werden Daten mittels einer einfach verketteten Liste verwaltet, so sind Sortiervorgänge in der Regel nur mit großem Zeitaufwand zu realisieren. Sollen die Listenelemente nach unterschiedlichen Kriterien sortiert werden, so ist dies nur durch Vervielfachung der Daten selbst möglich. Ein Ausweg bietet das Anlegen von Indexlisten. Hierbei werden nur Verweise auf die Datensätze in der geforderten Reihenfolge angelegt. Die Indexlisten sind in der Regel Felder mit einer Anzahl an Elementen, die der Anzahl der Datenelemente entsprechen. Der Inhalt dieser Feldelemente sind die Verweise auf die Daten selbst. Jedes Datum besitzt jedoch die Eigenschaft, dass ein Vergleich auf größer, kleiner und gleich auf dieses Datum ausgeführt werden kann.
Es ist eine Verwaltungsstruktur in Form einer Basisklasse zu entwickeln, die einerseits die Daten in Form einer verketteten Liste aufnehmen kann und andererseits bis zu drei Indexlisten zur Festlegung der Reihenfolge entsprechend einer Sortierregel beinhaltet. Die Basisklasse soll folgende Funktionen unterstützen:
− Verwaltung der verketteten Liste
− Einfügen eines Elementes an die Liste
− Löschen eines Elementes aus der Liste
− Indizierung aufsteigend
− Indizierung absteigend
− Zugriff auf die Daten über Indexliste

Hinweise zur Modellierung und Umsetzung
Für den Nachweis der Funktionalität soll eine Listenklasse abgeleitet werden, die als Daten Texte enthält. Über ein Textobjekt soll die Liste mit mindestens 10 Werten gefüllt werden. Die Indizierung nach größten und kleinsten Wert ist durchzuführen. Der Listeninhalt ist über den Indexzugriff auszugeben. Der Zugriff auf die Daten über die Indexlisten könnte in folgender Form möglich sein: z.B. Datum = MyList.Index. Aufsteigend(5); MyList ist hier ein Objektname. Andere Formen sind ebenfalls denkbar.

die verkettete Liste hab ich bereits fertiggestellt:

C++:

class Liste
{
    private:
        ListElement* first;

    public:
        //Konstruktor
        Liste()
        {
            first = NULL;
        }

        //Destruktor
        virtual ~Liste()
        {
            delete first;
        }

        // fügt einen neuen Wert am Ende ein:
        void add( string sTempData )
        {
            // Wenn die Liste noch leer ist, dann einfach ein
            // Element an den Anfang setzen:
            if( first == NULL )
            {
                first = new ListElement( sTempData );
            }
            else
            {
                // Suche nach dem letzten Element:
                ListElement* last = first;
                while( last -> getNext() != NULL )
                {
                    last = last -> getNext();
                }
                // letztes hat jetzt keinen Nachfolger mehr.
                // Das wird geändert:
                last -> add( sTempData );
            }
        }

        // sucht nach einem Wert, und liefert true, wenn der gesuchte Wert
        // enthalten ist:
        bool searchforValue( string sTempData )
        {
            // Leere Liste?
            if( first == NULL )
            {
                return false;
            }
            else
            {
                return first -> searchforValue( sTempData ) != NULL;
            }

        }

};// class Liste

class ListElement
{
    private:
    string sData;
    ListElement* next;

    public:
    //Konstruktor
    ListElement( string sTempData )
    {
        sData = sTempData;
        next = NULL;
    }

    //Destruktor
    virtual ~ListElement()
    {
        delete next;
    }

    //Anfügen eines neuen Elements
    void add( string sTempData )
    {
        next = new ListElement(sTempData);

        next -> next = NULL;
    }

    //Einlesen des Textes
    string getData()
    {
      return sData;
    }

    void setNext( ListElement *next_neu )
    {
      next = next_neu;
    }

    ListElement* getNext()
    {
      return next;
    }

    // sucht nach einem Wert, und liefert das ListenElement
    // (falls gefunden), oder NULL.
    ListElement* searchforValue( string sTempData )
    {
        // Schleife notfalls über alle Elemente:
        ListElement* currentElement = this;
        do
        {
            if( currentElement -> getData()==sTempData )
            {
                return currentElement;
            }

            currentElement = currentElement -> getNext();
        }
        while( currentElement -> getNext()!=NULL );

        // wenn alle Elemente nicht paßten, dann ist die Suche
        // fehlgeschlagen:
        return NULL;
    }


};// class ListElement

void main()
{
    string sData;
    Liste MyList;

    std::cout << "Geben Sie bitte die Elemente die Sie in die verkettete Liste schreiben moechten an!\n";

    for(int i = 0; i < 10; i++)
    {
        std::cout << "Geben Sie das "<< i+1 <<". von maximal 10 Elementen an!\n";
        std::cin >> sData;

        MyList.add(sData);
    }

}

mit fehlt nur jetzt der Plan wie ich am besten die Indexlisten realisieren könnte. angefangen hab ich erstmal so:

C++:

class IndexList
{
    public:
        IndexList(Liste MyList);
        ~IndexList();
        virtual string Aufsteigend(int Index);
        virtual string Absteigend (int Index);

};

class IndexListAlphabetical : public IndexList
{
    public:
        IndexListAlphabetical();
        ~IndexListAlphabetical();

};

class IndexListNumerical : public IndexList
{
    public:
        IndexListNumerical();
        ~IndexListNumerical();
};

nur wie krieg ich das jetzt hin dass die indexlisten mit den pointern gefüllt und gleichzeitig sortiert werden? ich würde mich sehr freuen wenn mir jemand helfen könne.

danke schonmal im voraus.

Yeah1000

Profil || Private Message || Suche

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

001
27.11.2011, 05:05 Uhr
0xdeadbeef
Gott
(Operator)

Mir ist nicht ganz klar, was man da mit Vererbung soll; Compositing passt eigentlich deutlich besser. Aber was soll's.

Das Prinzip einer Indexliste ist eigentlich ziemlich simpel. Du hast deine verkettete Liste, und neben der verketteten Liste hast du einen Index. Dieser ist schlicht ein Array von Zeigern, die auf die Listenelemente zeigen. Es ist etwas schwierig, das in ASCII darzustellen, aber ich tu mal mein Bestes:

Code:

+---+   +---+   +---+   +---+   +---+
| 3 |-->| 1 |-->| 4 |-->| 5 |-->| 2 |--> NULL
+---+   +---+   +---+   +---+   +---+
  ^       ^       ^       ^       ^
  |       |       |       |       |
  +-+     |   +---+       |       |
    |     |   |           |       |
    |     |   |   +-------+       |
  +-------+   |   |               |
  | | +---------------------------+
  | | |       |   |
  | +-|---+   |   |
  |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   | Index
+---+---+---+---+---+

Auf die Weise kann man, ohne seine Objekte in der Gegend herumschieben zu müssen, später das drittkleinste Element schnell und einfach auslesen - über Arrayzugriff in den Index halt.

Den Index kann man dann behandeln wie jedes andere sortierte Array. Wird ein neues Element in die Indexliste gebracht, dann wird es an die verkettete Liste einfach angehängt und ein Zeiger auf den Listenknoten an der richtigen Stelle in den Index eingefügt. Die richtige Stelle ist eine, die die Sortierung nicht verletzt; diese lässt sich über eine binäre Suche in O(log(N)) finden, denn der Index ist ja immer sortiert.

Das Entfernen eines Objektes läuft analog: der betroffene Zeiger muss aus dem Index entfernt werden, danach wird das Objekt aus der Liste gelöscht.

Caveat: Es darf nicht passieren, dass die Objekte in der Liste an der Indexstruktur vorbei geändert werden, sonst ist der Index plötzlich nicht mehr sortiert und das alles fliegt böse auseinander. Also nie nicht-konstante Referenzen zurückgeben!

Mehrere Indices zu unterstützen ist ziemlich simpel - du musst dann halt mehrere Arrays verwalten und jede Operation, die du vorher auf einem Index gemacht hast, in allen durchführen. Es ändert sich dann lediglich die Vergleichsfunktion. Wenn ihr Funktionszeiger schon gehabt habt, wäre das eine gute Möglichkeit, sie einzusetzen, um deinen Prof zu beeindrucken. In der Praxis würde man im Zweifel std::(tr1::)function benutzen, aber in Lehrmaterial findet man das eher selten.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 27.11.2011 um 05:15 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

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

Seiten: > 1 < [ C / C++ (WinAPI, Konsole) ]

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: