Array aus verketteten listen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Array aus verketteten listen

    Hallo C Coder!

    Ich habe hier eine Aufgabe die mich fast zum Wahnsinntreibt und zwar soll eine Adajanzliste in c Geschrieben werden dabei werden untereinander verbundene Knoten in einem Array von verkettetn listen gespeichert. Jeder Knoten
    i stellt in diesem Array ein Element dar. in jedem Element wird die Liste alle seiner Nachbarn gespeichert.

    Ich habe dazu gar keine idee wie kann ich denn so etwas realiseiren habe schon gegoogelt aber für mich nichts hilfreiches gefunden wäre toll wenn mir jemand einen Lösungsansatz oder ein beipspiel zeigen könnte

    ich habe mir überlegt ein Element müsste ungefähr so aussehn

    Quellcode

    1. struct element
    2. {
    3. int nummer;
    4. struct element* vorgänger;
    5. struct element* nachfolger;
    6. }
    8. allerdings ist das falsch da ein Element ja bereits eine liste iste ist oder ?
    10. Danke im Vorraus

  • Hallo Rushh0ur!

    Danke für deine Antwort !

    Nein das Hilft mir leider wenig die Idee die dahinter steht hab ich schon verstanden den link hab auch schon beim googlen gefunden.

    Ich habe ehr mit dem

    Rushh0ur schrieb:

    Nun brauchst du innerhalb jedes Elements noch eine Liste in der steht auf welche Elemente das Element "Zeigt".
    auch wenn es vielleicht einfach ist und die Frage eventuell doof aber ich kann mir da echt nichts daruf zam reimen bzw ich find dafür einfach keinen ansatz!

  • Du hast schon vollkommen richtig angefangen, nur wahrscheinlich gleich zu weit gedacht.
    Bau doch erstmal eine verkettete Liste und teste die ausgiebig, dann hast du alles an der Hand, um auch ein Array von verketteten Listen zu haben.

    Tipp: wenn du einen Startknoten (du hast es element genannt) nimmst, der immer leer ist, macht das die Implementierung einfacher, weil viele Fallunterscheidungen wegfallen.
    Tipp: wenn du in element von int nummer nach zB void *data änderst, hast du mit entsprechenden Casts eine typunabhängige Version -> dann kannst du auch eine verlinkte Liste von verlinkten Listen haben ;)

  • Sorry wenn ich diesen Thread nochmal pushe!

    Ich hatte die letzen Tage keine zeit deshalb konnte ich mich nicht mehr mit beschäftigen hab jetzt zumindest einen Ansatz.

    Also die Aufgabe ist es ein Array aus verkettetn listen zu erstellen:

    Das Array besteht dann aus zwei listen eine mit vollen elementen und eine mit lerren elementen also sprich jedes Array element ist eine liste wenn es leer ist zeigt es auf das nächste leere Arrayelement
    wenn nicht zeigt es auf das nächste besetzte Arrayelement wenn ein neues Listenelement angefordert wird muss dies aus einen leeren Arrayplatz geschehen. das heißt die Liste der Leeren Elemente wird
    verkürzt wenn es neues Element angefordert wird bzw wird sie um eines erweitert wenn ein element wieder freigegeben wird.

    Quellcode

    1. struct LE
    2. {
    3. float value;
    4. struct LE* next;
    5. LE(): value(0.0f), next(0) {}
    6. };
    11. class List
    12. {
    16. private:
    18. LE* first;
    20. LE* last;
    22. LE* leArray;
    25. unsigned leArraySize;
    27. LE* firstEmpty; /*Zeiger auf das erste leere Element*/
    31. LE* newLE( ) /*forder neues element an heißt es sucht leeres element und gibt zeiger auf dieses zurück */
    32. {
    34. LE* neu; /*neuer zeiger*/
    36. if( firstEmpty->next != NULL ) /*wenn firstEmpty->next nicht null ist sind noch weiter leere elemente enthalten */
    37. {
    38. neu = firstEmpty; /*das erste leere element wird in den Zeiger neu geschoben*/
    39. firstEmpty=firstEmpty->next; /*das nächste element auf das das erste leere element zeigt wird neues firstEmpty*/
    41. return neu; /*leeres element wird zurück gegeben*/
    42. }else
    43. {
    45. return NULL; /* wenn firstEmpty Null kein leeres element vorhanden return null*/
    47. }
    49. }
    56. public:
    58. LE* arr ;
    60. List (unsigned size ) /*Konstruktor erstellt array mit list elementen "LE"*/
    61. {
    62. arr = new LE[size]; /*reserviere Speicher für array */
    64. for (int i = 0; i<size; i++) /*Durchlaufe Array und initialsiere jedes mit einem LE */
    65. {
    66. arr[i]= /*wie kann ich initialsieieren*/ 0 ;
    68. }
    70. firstEmpty = arr[0]; // firstEmpty zeiger auf erstes arrayelement setzen
    72. }
    77. List(const List& source);
    78. List(List&& source);
    82. ~List();
    83. int append(float value);
    84. void deleteLE(LE* old);
    87. List& operator=(const List& source);
    88. List& operator =(List&& source);
    91. LE* getFirstEmpty()
    92. {
    93. return List::firstEmpty;
    95. }
    97. void setArraysize(int size)
    98. {
    99. List::leArraySize = size;
    101. }
    102. );
    Alles anzeigen


    So von mir stammt die Funktion newLE() und der Konstruktor list der rest war vorgegeben allerdings habe ich jetzt ein paar fragen :

    1. Wieso sagt er hier :

    Quellcode

    1. if( firstEmpty->next != NULL )


    bezeichenr NULL nicht definiert ?? Benutze Visual studio falls das euch was hilft.

    als nächstes wie kann ich mein array nun mit LE element initialsieren

    wenn ich das ganze so mache

    Quellcode

    1. or (int i = 0; i<size; i++)
    2. {
    3. arr[i]= LE*neu ;
    5. }


    Wird mir geast der typname ist nicht zulässig warum ? es ist doch ein array vom typ LE also darf ich doch da auch solche elemente reinschreiben oder ?

    Als nächstes ist die Frage ist es richtig wenn ich die private funktionen gleich oben deklarier wenn ich sie versuche nach der klasse zu deklarieren sagt er mir das es eine ungültige doppeldekleration ist außerdem versteh ich nicht ganz was ich mit den ganzen zeigen machen soll bzw warum diese private sind ? so komme ich doch ohne set und getter nicht mehr ran ?

    Wäre cool wenn mal jemand drüber schaut und ein paar verbesserungsvorschläge und tipps gibt :)

    Danke im vorraus

    PS: Sorry für den langen post

  • NULL = 0
    Wenn das nächste Element nicht (!=) NULL ist dann exestiert es (zumindest sollte es, wenn korekt gehandhabt, werde jedoch aber aus dem folgend nicht schlau, Sinn?)
    Die funktion newLE stammt von dir und du fragst was du da gemacht hast? Oo

    Die ganzen Variablen sind Privat damit keiner auf die Idee kommt diese in irgendwelcher Weiße zu ändern und diese nicht ins Nirvana geschickt werden.
    Innerhalb der Klasse hast du jedoch vollen zugriff auf diese.

    Deine Variable arr ist eine einfache List von LE structuren.
    Die Reservierung dieser ist mittels new Korrekt.
    Um diese nun zu initialisieren am besten mit memset den Speicherbereich 0en.

    Quellcode

    1. firstEmpty = arr[0];

    Damit erhälst du direkt das 0 Objekt, du brauchst aber die Addresse dieser (???), dann noch nen & davor: &arry[0] oder einfach nur arr -> pointer aufs erste (0) element.

    Mfg Rushh0ur