Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Listen

  • 1
  • 2

Werbeanzeige

Anonymous

unregistriert

1

05.01.2005, 20:01

Listen

Könnte mir bitte jemand ein gutes Tut zum Thema Listen posten oder mir gleich erklären?!! ???

DragonMaster

Community-Fossil

Beiträge: 1 603

  • Private Nachricht senden

2

06.01.2005, 01:39

Tut's kenne ich keine. Aber Listen sind proppe einfach.

Man hat eine Struktur die zwei Dinge enthält. Einmal die Adresse der Daten die die Liste speichern soll, dann einen Pointer auf selbige Struktur. Welcher die Adresse des nächsten Listen-Elementes enthält.

C-/C++-Quelltext

 
1
2
3
4
5

struct ListEntry
{
   void* data_;
   ListEntry* next_; // Adresse des nächsten Listenelementes

};

Etwa so. Dann noch ein paar Funktionen wie add oder remove und fertig. Die Liste enthält dann ein Startobjekt (das erste in der Liste) dieses hält dann die Adresse zum zweiten Objekte, das wiederum die Adresse zum 3ten Element enthält, usw. Das Letzte Element speichert für next_ einfach NULL und marckiert so das Ende der Liste.
Wichtig! Ich übernehme keinerlei Verantwortung für eventl. Datenverlust oder Schäden am Rechner ;D

helium

Treue Seele

Beiträge: 180

Wohnort: NRW, Burscheid (nahe Köln)

  • Private Nachricht senden

3

06.01.2005, 18:12

Etwas abstrakter:
Eine Liste ist entweder eine leere Liste oder eine Liste bestehend aus einem Wert und einer weiteren Liste.

Der Wert kann wie in DragonMasters Beispiel ein void-Zeiger sein. In C++ aber sehr unüblich statdessen würde man ein Template verwenden. In Java würde man Object verwenden. Da du keine Angaben zur Sprache gemacht hast, ist es jetzt schwer genauere Beispiele zu bringen.

Steven77

Alter Hase

Beiträge: 515

Wohnort: Münster - Gievenbeach

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

4

11.01.2005, 17:09

Templated Linked-List

Da "Gast" ja am liebsten ein richtiges Tutorial haben würde, kann er wahrscheinlich wenig mit den abstrakten Informatiker-Definitionen anfangen ;) , aber helium hat natürlich vollkommen Recht!

Ich bin gerade auf'er Arbeit und habe nichts zu tun ;) , deshalb schreibe ich hier mal kurz eine doppeltverkettete Liste hin, die ich mal programmiert habe (oder zumindest so viel, wie davon jetzt noch auf die Schnelle in meinem Brain verfügbar ist).

Doppeltverkettet deshalb, weil man dann in beide Richtungen navigieren kann und beim Löschen den jeweiligen Vorgängerknoten nicht immer explizit mitschlören muss.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

template <class T> class CLinkedList  
{
    typedef struct SNode
    {
        T*      data;
        SNode*  next;
        SNode*  prev;
    } TNode;

//

// Konstruktor / Destruktor

//

public:
    inline CLinkedList()    { m_pHead = m_pTail = m_pCurrent = NULL; m_nCount = 0; }
    inline ~CLinkedList()   { RemoveAll(); }

//

// Attribute

//

private:
    TNode*  m_pHead;
    TNode*  m_pTail;
    TNode*  m_pCurrent;
    int     m_nCount;

//

// Operationen

//

public:
    T*      AddHead(T* obj);
    T*      AddTail(T* obj);

    bool    IsMember(T* obj);

    T*      GetHead();
    T*      GetNext();
    T*      GetTail();
    T*      GetPrev();

    T*      Remove(bool bDelObj = false);
    void    RemoveAll(bool bDelObj = false);

//

// Inline-Methoden

//

public:
    T*      Add(T* obj)     { return AddTail(obj); }

    int     GetCount()      { return m_nCount; }

};

template <class T>
T* CLinkedList <T> ::AddHead(T* obj)
{
    m_pCurrent = (TNode*) calloc(1, sizeof(TNode));
    if (m_pCurrent == NULL)
        return NULL;

    if (m_pHead)
    {
        m_pHead->prev = m_pCurrent;
        m_pCurrent->prev = NULL;
        m_pCurrent->next = m_pHead;
        m_pCurrent->data = obj;
        m_pHead = m_pCurrent;
    }
    else
    {
        m_pHead = m_pTail = m_pCurrent;
        m_pCurrent->prev = NULL;
        m_pCurrent->next = NULL;
        m_pCurrent->data = obj;
    }

    m_nCount++;
    return obj;
}

template <class T>
bool CLinkedList <T> ::IsMember(T* obj)
{
    m_pCurrent = m_pHead;
    while (m_pCurrent)
    {
        if (m_pCurrent->data == obj)
            return true;

        m_pCurrent = m_pCurrent->next;
    }

    return false;
}

template <class T>
T* CLinkedList <T> ::GetHead()
{
    m_pCurrent = m_pHead;
    if (m_pCurrent)
        return m_pCurrent->data;
    return NULL;
}

template <class T>
T* CLinkedList <T> ::GetNext()
{
    if (m_pCurrent)
    {
        m_pCurrent = m_pCurrent->next;
        if (m_pCurrent)
            return m_pCurrent->data;
    }
    return NULL;
}

template <class T>
T* CLinkedList <T> ::Remove(bool bDelObj)
{
    if (m_pCurrent == NULL)
        return NULL;

    if (bDelObj)
        delete m_pCurrent->data;

    if (m_pHead == m_pTail)
    {
        m_pHead = m_pTail = NULL;
    }
    if (m_pCurrent == m_pHead)
    {
        m_pHead = m_pHead->next;
        m_pHead->prev = NULL;
    }
    else if (m_pCurrent == m_pTail)
    {
        m_pTail = m_pTail->prev;
        m_pTail->next = NULL;
    }
    else
    {
        m_pCurrent->prev->next = m_pCurrent->next;
        m_pCurrent->next->prev = m_pCurrent->prev;
    }

    TNode* pNode = m_pCurrent;
    m_pCurrent = m_pCurrent->next;
    free(pNode);
    m_nCount--;

    if (m_pCurrent)
        return m_pCurrent->data;
    return NULL;
}

template <class T>
void CLinkedList <T> ::RemoveAll(bool bDelObj)
{
    while (m_pHead)
    {
        m_pCurrent = m_pHead;
        if (bDelObj)
            delete m_pCurrent->data;

        m_pHead = m_pHead->next;
        free(m_pCurrent);
    }

    m_pHead = m_pTail = m_pCurrent = NULL;
    m_nCount = 0;
}


Die Methoden, die ich weggelassen habe, sind analog zu den aufgeführten Methoden zu implementieren, logisch.

Ich weiß nicht, ob dieser absolut unkommentierte Code weiterhelfen kann, aber es soll eigentlich auch nur ein Anreiz sein. Zumal aufgrund des Klasseninternen Attributs "m_pCurrent" keine parallelen Zugriffe bzw. Iterationen möglich sind, mal ganz zu schweigen von einer einheitlichen Schnittstelle via Iterator-Objekt oder sonstiges.

Dave

Alter Hase

Beiträge: 757

Wohnort: Berlin

  • Private Nachricht senden

5

11.01.2005, 17:39

man brauch keine doppelt verkettete liste zum löschen. bei ner einfachverketteten muss man den vorgänger auch nicht "mitschleppen" oder extra suchen. wenn man nen knoten löschen will, tauscht man einfach den datenzeiger des zu löschenden knotens mit dem seines nachfolgers und löscht dann den nachfolger.

Till

Alter Hase

Beiträge: 378

Wohnort: Lincoln College, Oxford

Beruf: Student

  • Private Nachricht senden

6

11.01.2005, 18:03

Also falls es dir nichts ausmacht, englische Tutorials zu lesen:

Tutorial 1
Tutorial 2

Beide englisch aber beide sehr ausführlich!
DOMINVS ILLVMINATIO MEA
---
Es lebe unmanaged Code!
---
>> Meine Uni <<

Steven77

Alter Hase

Beiträge: 515

Wohnort: Münster - Gievenbeach

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

7

11.01.2005, 19:54

Zitat

man brauch keine doppelt verkettete liste zum löschen.

Ja, da hast Du Recht. Der "Kniff" war mir nicht bewusst. Man lernt halt nie aus ;)

Aber je nach Anforderung kann eine doppeltverkettete Liste auch mal ganz nützlich sein.

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

8

11.01.2005, 20:10

Wenn die Instanzen nicht nur Zeiger sondern Mengen von Vars beinhalten ;).

helium

Treue Seele

Beiträge: 180

Wohnort: NRW, Burscheid (nahe Köln)

  • Private Nachricht senden

9

11.01.2005, 21:34

@Steven77: Geil. Als ich dein Avatar gesehen habe habe ich gleich nochmal Commander Keen ausgepackt und gezockt. 8)

-----------

C-/C++-Quelltext

 
1
2

    inline CLinkedList()    { m_pHead = m_pTail = m_pCurrent = NULL; m_nCount = 0; } 
    inline ~CLinkedList()    { RemoveAll(); }


Wenn du etwas in der Klasse definierst, ist es eh inline. Das expliziete inline hat keinen Effekt. Wenn du deinen Compiler umbedingt zu einer Expansion zwingen willst solltest du lieber mal die Compiler-Doku studieren und sowa, wie __attibute__((always_inline)) oder __force_inline verwenden.

Außerdem ist es üblich Member über die Initialisieurngsliste zu initialisieren.


Ansonsten sieht der Code so aus, als würdest du für die MFC programmieren. Die haben da ja so ein C-Präfix, weil es beim erscheinen der MFC noch keine Namensräume gab. (Auch sonst folgst du genau dem dort üblichen Namensschema.)
In einem allgemeinen Beispiel für einen Neuling finde ich das nicht ganz so gut.

Und dann Noch das calloc: Gibt es dafür einen Grund? Ich habe schon Compiler gesehen, bei denen das Allokieren kleiner Objekte (wie SNode/TNode) mit new deutlich schneller war, als mit *alloc, jedoch noch nie andersherum, höchsten gleichschnell.
Das Null-Setzen kanns doch nciht sein, denn dafür hättest du ja auch mal eben nen kleinen C'tor spendieren können.

typedef bei structs ist in C++ nicht mehr nötig.

C-/C++-Quelltext

 
1
2
3

struct Foo{ ... };

Foo foo; // geht wunderbar



OK, bevor ich mich da jetzt in irgendwas reinsteigere höre ich jetzt lieber auf.


@Admin: Wenn man über den C++ Code Knopf fährt, erscheint als Text: "C++ Code anzeigen: [ cpp ]Code[ /code ] (alt+c)"

DragonMaster

Community-Fossil

Beiträge: 1 603

  • Private Nachricht senden

10

11.01.2005, 21:55

Danke helium, werds weiterleiten
Wichtig! Ich übernehme keinerlei Verantwortung für eventl. Datenverlust oder Schäden am Rechner ;D

Werbeanzeige

  • 1
  • 2