einfache verkettete Liste

  • C

Es gibt 13 Antworten in diesem Thema. Der letzte Beitrag () ist von Gonger96.

    einfache verkettete Liste

    Hey, ich versuch grad selber eine einfache verkettete Liste zu machen und hab jetzt Probleme dabei ein Element der "Liste" hinzuzufügen.

    Mein Code:

    VB.NET-Quellcode

    1. struct Daten
    2. {
    3. int Wert;
    4. struct Daten *next;
    5. };
    6. typedef struct Daten* PointerDatas;
    7. typedef struct Daten voidDatas;
    8. void insert(PointerDatas list_Element,voidDatas pElement);
    9. int main(int argc, char *argv[]) {
    10. PointerDatas list_Elements = (PointerDatas)calloc(1,sizeof(voidDatas));
    11. voidDatas einElement = {1};
    12. voidDatas zweitesElement = {2};
    13. voidDatas drittesElement = {3};
    14. insert(list_Elements,einElement);
    15. insert(list_Elements,zweitesElement);
    16. insert(list_Elements,drittesElement);
    17. printf("%i",list_Elements->next->Wert);
    18. return 0;
    19. }
    20. void insert(PointerDatas list_Element,voidDatas pElement)
    21. {
    22. pElement.next = list_Element->next;
    23. list_Element->next = &pElement;
    24. }


    Meine Überlegungen:

    /* Element eins wird hinzugefügt
    1. Element -> next = NULL;
    list_Element -> next = 1. Element;
    Element zwei wird hinzugefügt
    2. Element -> next = 1. Element;
    list_Element -> next = 2. Element;
    Element drei wird hinzugefügt
    3. Element -> next = 2. Element;
    list_Element -> next = 3. Element;
    */


    Doch am Ende kommt immer das zuletzt eingefügte Element raus, also egal ob ich list_Elements->next->Wert aufrufe oder list_Elements->next->next->Wert.
    Was ist an meinen Überlegungen falsch?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RushDen“ ()

    Deine insert-Funktion ist semantisch falsch. Beim einfügen eines Elements musst du zunächst das letzte vorhandene Element suchen. Da dieses Element nicht immer das zweite, dritte, ... ist, sondern sich dynamisch verändert, benötigst du eine Schleife, die die next-Zeiger durchgeht. Momentan hängst du alles an den Nachfolger des ersten Elements an - deine Liste kann also niemals länger als 3 Elemente werden und das dritte Element wird immer überschrieben. So eine Liste ist eine gute Übung, aber ganz so einfach ist sie dann doch nicht. Lies am besten folgendes: de.wikipedia.org/wiki/Liste_%28Datenstruktur%29. Dort gibt es auch Beispielcode für die Standardoperationen.

    Außerdem: Du vergisst, Speicher freizugeben. Beginne erstmal mit einfachen Datenstrukturen und lass die pseudo-cool benannten void-typedefs weg. Das kommt später. Beispiel:

    C-Quellcode

    1. struct Node {
    2. int value;
    3. struct Node *next;
    4. }
    5. void insert(Node* list, int value) {
    6. /* Node suchen */
    7. /* neue Node erstellen */
    8. /* Wert schreiben */
    9. /* Node anhängen */
    10. }
    Gruß
    hal2000

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „hal2000“ ()

    Ich weiß nicht, was du da so im Sinn hattest, aber so sollte das etwa aussehen:
    Spoiler anzeigen

    C-Quellcode

    1. public class CustomLinkedListNode<T>
    2. {
    3. public T Value { get; private set; }
    4. internal CustomLinkedList<T> List { get; set; }
    5. public CustomLinkedListNode<T> Previous { get; internal set; }
    6. public CustomLinkedListNode<T> Next { get; internal set; }
    7. public CustomLinkedListNode(T value)
    8. {
    9. Value = value;
    10. }
    11. }
    12. public class CustomLinkedList<T> : IEnumerable<T>
    13. {
    14. CustomLinkedListNode<T> firstNode;
    15. CustomLinkedListNode<T> lastNode;
    16. public T First
    17. {
    18. get { return firstNode != null ? firstNode.Value : default(T); }
    19. }
    20. public T Last
    21. {
    22. get { return lastNode != null ? lastNode.Value : default(T); }
    23. }
    24. public void InsertFirst(CustomLinkedListNode<T> node)
    25. {
    26. if (node == null)
    27. throw new ArgumentNullException("node");
    28. if (node.List != null)
    29. throw new InvalidOperationException("This node is already part of another list.");
    30. if (firstNode != null)
    31. {
    32. firstNode.Previous = node;
    33. node.Next = firstNode;
    34. }
    35. else
    36. {
    37. lastNode = node;
    38. }
    39. node.List = this;
    40. firstNode = node;
    41. }
    42. public CustomLinkedListNode<T> InsertFirst(T item)
    43. {
    44. var node = new CustomLinkedListNode<T>(item);
    45. InsertFirst(node);
    46. return node;
    47. }
    48. public void InsertLast(CustomLinkedListNode<T> node)
    49. {
    50. if (node == null)
    51. throw new ArgumentNullException("node");
    52. if (node.List != null)
    53. throw new InvalidOperationException("This node is already part of another list.");
    54. if (lastNode != null)
    55. {
    56. lastNode.Next = node;
    57. node.Previous = lastNode;
    58. }
    59. else
    60. {
    61. firstNode = node;
    62. }
    63. node.List = this;
    64. lastNode = node;
    65. }
    66. public CustomLinkedListNode<T> InsertLast(T item)
    67. {
    68. var node = new CustomLinkedListNode<T>(item);
    69. InsertLast(node);
    70. return node;
    71. }
    72. public bool Remove(CustomLinkedListNode<T> node)
    73. {
    74. if (node == null || node.List != this) return false;
    75. if (node.Previous != null) node.Previous.Next = node.Next;
    76. if (node.Next != null) node.Next.Previous = node.Previous;
    77. if (node == firstNode) firstNode = node.Next;
    78. if (node == lastNode) lastNode = node.Previous;
    79. node.Previous = null;
    80. node.Next = null;
    81. node.List = null;
    82. return true;
    83. }
    84. public IEnumerator<T> GetEnumerator()
    85. {
    86. CustomLinkedListNode<T> node = firstNode;
    87. while (node != null)
    88. {
    89. yield return node.Value;
    90. node = node.Next;
    91. }
    92. }
    93. System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    94. {
    95. return GetEnumerator();
    96. }
    97. }
    Ist jetzt C#, sollte sich aber gut nach C++ übertragen lassen.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Artentus“ ()

    Ups, C, nicht C++, mein Fehler. :rolleyes:

    @RushDen
    Tut mir leid, in dem Fall kannst du dann die Generics mit void-Pointern umsetzen bzw. einfach nen konkrete Typen nemen, Templates gibts ja nur in C++. Und die Funktionen kannst du dann natürlich nicht in ne Klasse packen, aber ich trau dir zu, dass du das hinkriegst. Die LinkedListNode lässt sich als Struktur darstellen, das kannst du so übernehmen.
    So habs:

    VB.NET-Quellcode

    1. struct Node
    2. {
    3. int value;
    4. struct Node *next;
    5. };
    6. void insert(struct Node* list,int val);
    7. struct Node* ElementList;
    8. int main(int argc, char *argv[]) {
    9. ElementList = malloc(sizeof(struct Node));
    10. insert(ElementList,5);
    11. insert(ElementList,3);
    12. printf("%i",ElementList->next->next->value);
    13. return 0;
    14. }
    15. void insert(struct Node* list, int val) {
    16. /* Node suchen */
    17. /* neue Node erstellen */
    18. struct Node* newNode = (struct Node *)malloc(sizeof(struct Node));
    19. /* Wert schreiben */
    20. newNode->value = val;
    21. /* Node anhängen */
    22. newNode->next = list->next;
    23. list->next = newNode;
    24. }


    Wusste jetzt nicht genau, wann ich den Speicher freigeben soll.
    Müsste ich dafür am Ende von main() durch alle Elemente durchlaufen und anschliessend den Speicher freigeben?
    Jau, pass aber auf, dass du nicht den Next-Pointer mit löscht, bevor das nächste Element nicht schon gelöscht ist. Aber ich würde auch die Node-Pointer beim Insert zurückgeben, anders lässt sich auch kein Remove implementieren (dafür ist btw. auch die Previous-Eigenschaft).
    Also einfach den zurückgegebenen Pointer halten und am ende freigeben?:

    VB.NET-Quellcode

    1. int main(int argc, char *argv[]) {
    2. ElementList = malloc(sizeof(struct Node));
    3. struct Node* pointer = insert(ElementList,5);
    4. printf("%i",ElementList->next->value);
    5. free(pointer);
    6. return 0;
    7. }
    8. struct Node* insert(struct Node* list, int val) {
    9. /* neue Node erstellen */
    10. struct Node* newNode = (struct Node *)malloc(sizeof(struct Node));
    11. /* Wert schreiben */
    12. newNode->value = val;
    13. /* Node anhängen */
    14. newNode->next = list->next;
    15. list->next = newNode;
    16. return newNode;
    17. }
    Da musst du aufpassen. Du musst die Node erst Removen, bevor du den Speicher freigeben kannst, weil sonst Referenzen ins Nichts zeigen und du somit nicht mehr korrekt auf die Liste zugreifen kannst. Für die Remove-Operation brauchst du aber die Previous-Eigenschaft, siehe meinen Code, ansonsten kannst du die Elemente nicht mehr korrekt neu verketten.
    Ich habe nicht viel Erfahrung mit C, mein Vorgehen wäre aber wie folgt: Das letzte Element nehmen, dieses disposen und dann mit der Node davor das gleiche machen, quasi rekursiv (vor dem Befreien der Node aber die Adresse zu der Node davor merken). Das Ganze machst machst du dann so lange, bis du das erste Element ebenfalls disposed hast (erkennst du daran, dass die "Folge-Node" dann ein Nullpointer ist, sofern du den auch auf 0 gesetzt hast).



    Kleine Anmerkung zu @Artentus:' Antwort:

    Wenn man schon in einer anderen Programmiersprache eine Antwort postet, sollte man sich da auf das Wesentliche konzentrieren. Generics, Iterators und OOP gibt es in C nicht (ich gehe mal nicht davon aus, dass der TE mit C11 arbeitet). Die Antwort ist deshalb recht überladen mit Kram den man überhaupt nicht braucht, um zu verstehen, wie man die LinkedList in C implementiert, auch, wenn die C#-Implementierung schön sein mag.

    Du hättest übrigens - wenn du schon C# benutzt, um vorgehen in C zu erklären - selbst in C# structs mit Pointen verwenden können. Das wäre dann zumindest näher an dem, was der Thread behandelt.

    Edit:
    Übrigens geht es um eine einfach verkettete Liste, nicht um eine doppelte (@Artentus).
    Von meinem iPhone gesendet

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „nikeee13“ ()

    So, das ist jetzt C-Style:
    Spoiler anzeigen

    C-Quellcode

    1. public class CustomLinkedListNode
    2. {
    3. public int Value { get; private set; }
    4. public CustomLinkedListNode Previous { get; internal set; }
    5. public CustomLinkedListNode Next { get; internal set; }
    6. public CustomLinkedListNode(int value)
    7. {
    8. Value = value;
    9. }
    10. }
    11. public static class CustomLinkedList
    12. {
    13. public static void Insert(CustomLinkedListNode first, CustomLinkedListNode node)
    14. {
    15. CustomLinkedListNode lastNode = first;
    16. while (lastNode.Next != null)
    17. lastNode = lastNode.Next;
    18. lastNode.Next = node;
    19. node.Previous = lastNode;
    20. }
    21. public static CustomLinkedListNode Insert(CustomLinkedListNode first, int item)
    22. {
    23. var node = new CustomLinkedListNode(item);
    24. Insert(first, node);
    25. return node;
    26. }
    27. public static void Remove(CustomLinkedListNode node)
    28. {
    29. if (node.Previous != null) node.Previous.Next = node.Next;
    30. if (node.Next != null) node.Next.Previous = node.Previous;
    31. node.Previous = null;
    32. node.Next = null;
    33. }
    34. public static int[] EnumList(CustomLinkedListNode first)
    35. {
    36. var list = new List<int>();
    37. CustomLinkedListNode node = first;
    38. while (node != null)
    39. {
    40. list.Add(node.Value);
    41. node = node.Next;
    42. }
    43. return list.ToArray();
    44. }
    45. }
    Die ListNode kann man in C# nicht zu ner Struct machen, weil das sonst ne zyklische Struktur zur Folge hat, weil man ja keine Pointer auf Structs halten kann.

    Man muss die Liste doppelt verketten, weil man ansonsten nicht ordentlich daraus entfernen kann (Remove würde dann in O(n) statt in O(1) liegen).

    Artentus schrieb:

    Man muss die Liste doppelt verketten, weil man ansonsten nicht ordentlich daraus entfernen kann (Remove würde dann in O(n) statt in O(1) liegen).
    Muss man nicht. Es geht hier in erster Linie um die Operationen, die auf einfach verketteten Listen als allgemeine Datenstruktur möglich sind und wie sie richtig implementiert werden. Performancebetrachtungen sind dabei zweitrangig. Und übrigens ist Remove auch in doppelt verketteten Listen O(n), weil man von der Worst-Case-Laufzeit ausgeht, denn O gibt die obere Grenze an. Die liegt bei n/2 (sortierte Liste, Element in der Mitte soll entfernt werden, lineare Suche) und ist damit O(n) mit Faktor 1/2. Wenn die Operation RemoveLast ist hast du natürlich recht, weil dann die Suche wegfällt.

    Artentus schrieb:

    So, das ist jetzt C-Style:
    Wie bitte? Ich sehe da Klassen, Eigenschaften, Zugriffsmodifizierer, dynamische Typisierung und objektorientierten Methodenzugriff. Sorry, aber das ist auf keinen Fall C-Style. Das Einzige, was du gerade tust, ist einen Anfänger zu verwirren, der C programmieren will (nicht, C++, nicht C#). Bist du sicher, dass du den Unterschied kennst?
    Gruß
    hal2000