3. Zeigerlose Repräsentation eines Rings?

Zeigerlose Repräsentation eines Rings?

  • R

    Hallo,

    ich habe hier eine Aufgabe, die ich leider nicht ganz verstehe (zumal meine C/C++ Kenntnisse arg eingerostet sind). Folgende Aufgabe ist gestellt:

    Ich soll einen Ring (also eine einfache? verkettet Liste, die mit dem letzten Element nicht auf null sondern auf das erste Element zeigt) erstellen. Der Datentyp soll Reihe von Verbund sein (sind damit verschachtelte structs gemeint, bzw. structs mit arrays?). Das Ganze soll dann auch noch zeigerlos dargestellt werden. Als Vorbild kann man sich den geordneten Baum heran ziehen. Die Syntax soll in C sein.

    Über Hilfe wäre ich dankbar, irgendwie kapier ich diese Aufgabe grad überhaupt nicht.

    vg
    Hannes

    0
  • B

    Wie (zur Hölle) sollte das ohne Zeiger gehen?

    Und sind die Aufgaben zufällig für das neue Semester, wo ein C++-Kurs angefangen hat?

    edit: Tut mir Leid für den rauen Ton, aber bin mir grad mit dem Stuhl über meinen Zeh gerollt 😞

    0
  • R

    Outsch .. das mit dem Stuhl tut weh, das kenne ich ;o)
    Die Aufgabe ist für eine Lerngruppe, mit der ich C und C++ lerne. Das Original stammt aus irgend einem C++-Kurs einer mir unbekannten Uni.

    0
  • T

    Mir würden da 2 Dinge einfallen:

    1. Du erstellt einfach ein Array von dem Typ, der im Array sein muss. Deine Zugriffsfunktionen handhaben dann immer die Indizes richtig. Bei 5 Elementen landet einfach ein Zugriff auf Nr. 6 auf der 0 usw.
    2. Du gibst deinem Element einfach eine eindeutige ID und baust dir damit "Pseudo-Zeiger":
    typedef struct foo_t { 
int id; 
... 
int nextElement; // die ID des Nachfolgeelements 
} foo;
    0
  • B

    Aso, cool mit der Lerngruppe! Gut, jedenfalls geht das nicht ohne Zeiger, du meintest ja sogar selber "verkettet Liste, die mit dem letzten Element nicht auf null sondern auf das erste Element zeigt".
    Normalerweise würde man so einen Ring bzw eine einfach-verkettete Liste ja so darstellen:

    struct Node
{
    // Die Daten
    Node* next;
};
    0
  • R

    @this->that: Danke für die Info .. leider bin ich noch nicht so fit um deine Vorschläge umzusetzten. Wäre es möglich, dass Du mir für beide Varianten kurze Beispiele erzeugst mit kleinen Erklärungen? Ich wäre Dir sehr dankbar, in meinem Kopf raucht grad alles 😢

    0
  • T

    Die Frage ist: Darf das ganze Programm keine Zeiger verwenden oder nur der Ring nicht? Und ist mit Zeiger bereits das Konzept eines Zeigers gemeint (also die Referenzierung von irdendwas), weil dann wäre auch der Ansatz mit den IDs nicht erlaubt. Oder sind einfach nur die echten C-Zeiger (sprich T*) verboten?

    0
  • R

    So wie ich die Aufgabe interpretiere, denke ich das keine Zeiger verwendet werden sollen. Es sind also die C Zeiger verboten ...

    In einer Folgeaufgabe muss ich dann eine Funktion schreiben, mit der ich ein beliebiges Element aus dem Ring löschen kann. Dazu braucht man ja eine eindeutig ID für ein Element denke ich.

    0
  • T

    Also ohne Zeiger wird das alles nen ziemlicher Krampf. Aber irgendwie so würde es gehen:

    Du erstellt dir deine Element Struktur, z.B.:

    typedef struct Person_t {
   int id;
   int nextElement;

   char vorname[255];
} Person;

    sowie ein globales Array:

    #define ANZAHL 10
Person personen[ANZAHL];

    Jetzt kannst du dir die Funktionen init(), createPerson(), deletePerson() und printPersonen() schreiben. In init() iterierst du einfach über das Array personen und setzt alle ids und nextElement auf -1. Eine id von -1 heißt, dass es kein gültiges Element ist und nextElement=-1 heißt, dass das Element auf kein andres zeigt (NULL-Zeiger quasi).

    In createPerson suchst du dir den 1. freien Slot im Array und setzt die id auf den Arrayindex. nextElement setzt du auf die id des ältesten, gültigen Elements (dazu wirst du einen globalen Index brauchen).

    DeletePerson setzt die id des zu löschenden Elements A auf -1 und weist nextElement von dem Element B, das auf A "zeigt", A.nextElement zu. Die Zeiger werden quasi umgebogen.

    printPersonen() iteriert über das Array und sucht das erste Element mit id != -1. Das gibst du dann aus und schaust, ob nextElement != -1. Falls ja, ist nextElement das nächste Arrayelement, dass du auf id!=-1 untersuchst (sprich: personen[personen[i].nextElement].id).

    Alles sehr eklig^^

    0
  • C

    wie wäre ein array mit zB N = 10 Einträgen, einem Startindex start und der Länge l. Die Ring-Konstruktion ergibt sich durch die Modulo-Operation

    Dann könnte ich jederzeit auf das i-te Element zugreifen durch

    array[(start+i) % N]

    eingefügt wird durch

    array[(start + (l++)) % N] = item

    gelöscht am Start durch simples

    start++

    und am Ende

    l--

    sicherstellen muss ich nur noch, dass l < N und i < l.

    0
  • T

    Und wie löschst du Elemente?

    0
  • C

    notfalls durch umkopieren der nachfolgenden stellen, aber mM nach muss ein Ring ein beliebiges Löschen nicht unterstützen 😕
    halt nur am anfang oder am ende

    0
  • ?

    mach doch ein einfach ein array von listenelementen, die einen index statt zeiger beinhalten. das kann doch nicht so schwer sein 😕

    0
  • T

    ein ring hat weder ende, noch anfang. zugriff auf einen ring erfolgt immer über ein beliebiges element. elemente bieten methoden, ihren vor- und nachgänger zu liefern. jedes beliebige element eines ringes kann gelöscht werden. enthält ein ring nur ein element, liefern dessen vor- und nachgängermethode das element selbst.

    bei verzicht auf zeiger halte ich die implementierung durch ein (globales) array am sinnvollsten. dabei kann man durchaus einen ring mit einer maximalgröße von z.b. 10 elementen implementieren. die größe dynamisch anzupassen würde nur unnötig viel code erzeugen, der für die übung nicht interessant ist.

    0
  • R

    @this->that: Danke, das hab ich schon mal kapiert. Eine simple Umsetzung könnte wie folgt aus sehen (hoffe ich):

    struct Node
{
    int Index;
    int nextIndex;
    char Title[255];
};

int count = 0;

int main(void)
{
   struct Node nodes[9];
   nodes[count].Index = count;
   nodes[count].nextIndex = count;
   strcpy(nodes[count].Title, "Node 1");
   count++;

   ...
}

    Das Snippet in main() muss man natürlich als Funktion notieren etc. Wäre es so korrekt? Dann fehlt noch die Abfrage ob das letzte Element gefüllt wurde und in diesem Fall dann nextIndex auf 0 setzen (zum ersten Element). Wie macht man dies am Besten in C?

    @crashterpiece: Wie würde den ein kleines komplettes Beispiel zu Deiner Lösung aussehen?

    Äh .. wie gesagt ich bin frisch in C/C++ ;o)

    0
Anmelden zum Antworten