Dynamische Ringliste

6 Beiträge16.03.2010Archiviert
movco16.03.2010 · Beitrag #20856
Avatar
Mitglied seit: 08.10.2007
Forenbeiträge: 264
Besuche: 1383
Also ich muss eine dynamische Ringliste in C implementieren.
(Ein vereinfachtes Anti-Alising bring ich zammen und bei sowas steh ich an. Schäme mich selbst, aber bevor ichs nicht zusammen bring, frag ich lieber.)
Hab jetzt hier und da über ringbuffer gelesen, wie das mit den 2 Zeigern funktioniert, aber irgendwie hab ich grad ein Problem das umzusetzen.
Die Aufgabe schaut so aus:
Schreiben Sie eine dynamische Ringliste in C (das letzte Element zeigt wieder auf das
erste).
Ein Listenelement besteht aus einem Datenfeld (char*) und einem Zeiger auf das
nächste Element.
Die folgenden Funktionen sollen unterstützt werden:
a) Datenelement erzeugen
b) Sortiertes Einfügen eines neuen Datenelements (nach Datenfeld alphabetisch)
c) Ein gewisses Element finden
d) Ein gewisses Element löschen
e) Den Inhalt der Liste ab einem gewissen Knoten ausgeben

Wie würdet ihr das angehen? Ein simpler Pseudocode wäre hilfreich zu verstehen.

LG
Bene17.03.2010 · Beitrag #20858
Avatar
Mitglied seit: 19.04.2005
Forenbeiträge: 147
Besuche: 2161
Wo genau hast du Probleme?
movco17.03.2010 · Beitrag #20859
Avatar
Mitglied seit: 08.10.2007
Forenbeiträge: 264
Besuche: 1383
Naja wie ich das jetzt aufbauen soll. Versteh net wirklich wie das funktionieren soll mit dem dynamischen Speicher und der Ringliste.
Ich habe meinen Zeiger aufs erste und letzte Element. Jedesmal wenn ich was einfüge wandert der startzeiger nach rechts, und beim löschen eines elementes der endzeiger nach rechts. Aber wozu dann das reservieren von Speicher jedesmal. Dann geht das Array immer weiter und fängt nie bei 0 an. Da hab ich ein Verständnis Problem.

LG
dystopia26.03.2010 · Beitrag #20898
Avatar
Mitglied seit: 31.01.2005
Forenbeiträge: 136
Besuche: 188
Hallo,

"Hab jetzt hier und da über ringbuffer gelesen, wie das mit den 2 Zeigern funktioniert, aber irgendwie hab ich grad ein Problem das umzusetzen. "

Die besagte Ringliste hat nicht mit dem Ringpuffer zu tun.... Bei dir ist wohl eher eine "linked list" gefragt.

Ein Ringpuffer ist z.b. in Multithreaded anwendungen manchmal ganz sinnvoll. Der producer schreibt und verwaltet den write pointer, der consumer liest und verwaltet den read pointer.

pseudocode:

struct verwaltung
{
pointer first;
pointer last;
}

struct element
{
int daten;
pointer next;
}

i=0;
bla = verwalter.first;
while( bla != verwalter.first || i==0 )
{
print "daten: " bla->daten;
bla = bla->next;
i++;
}

Beispiel für einen ringpuffer:

struct ringbuffer
{
int read_pos;
int write_pos;
int data[1024];
}

funktion write:
data[write_pos++]=daten;
if( write_pos == 1023] )
write_pos = 0;

funktion read:
if(read_pos == write_pos)
keine daten vorhanden, funktion beenden
daten = data[read_pos++];
if( read_pos == 1023)
read_pos = 0;





[ Bearbeitet Fr, 26. Mär 2010, 15:47 ]
dystopia26.03.2010 · Beitrag #20899
Avatar
Mitglied seit: 31.01.2005
Forenbeiträge: 136
Besuche: 188
oben rein gepackt...
[ Bearbeitet Fr, 26. Mär 2010, 15:39 ]
movco27.03.2010 · Beitrag #20905
Avatar
Mitglied seit: 08.10.2007
Forenbeiträge: 264
Besuche: 1383
Ich habe es schon gelöst,
aber danke für die Hilfe.