Hi,

ich will einen neuen Datentyp "Queue" in C schreiben und hab so manche probleme.
Irgendwie schaffe ich es die Elemente des Queues nacheinander auszugeben. Auch die Speicherallokation beim dynamischen Array klappt nicht wirklich. Kann mir jemand weiterhelfen?

Quellcode: http://codepad.org/OulOyLQN

na, das sieht doch ein Blindermit nem Holzauge:
q = (Queue *) realloc (*q, sizeof(q*)*2);

sizeof(q*) hast du bestimmt nicht gemeint. Vrmtl eher sowas wie sizeof(*q) :-)

und realloc (*q, …) sieht auch komisch aus. Muesste bestimmt realloc (q, …) sein.

Wenn ich das richtig sehe, dann wirst du mit realloc so immer noch nicht glücklich.

sizeof(*q) wird dir nämlich die Größe des Elementes an der Stelle wo der Pointer hinzeigt geben. Und dort ist ein struct vom Typ Queue, dessen Größe sich ja nicht ändert, auch wenn das in einem alloziiertem, größeren Speicherbereich liegt. Was du vermutlich machen möchtest ist etwas wie:

q = (Queue *) realloc (q, 2 * q->queuesize * sizeof(*q));

Ja sehe schon, danke. Beim Kompilieren gabs keine Fehler. Ich weiss irgendwie nicht wie man den Queue jetzt printet.

/* print the contents of <*q> on screen */
void queue_print(const Queue *q)
{
int i;
for(i = q->enqueueindex+1; i <= q->dequeueindex; i++)
{
//printf("%d", i);
printf("%d \n", q->queuespace);
}
}

gibt er die falschen Sachen aus. Im struct ist queuespace als unsigned long int definiert. Kann es daher kommen?
Meine idee war, nur die Elemente auszugeben, die vorhanden sind, und nicht die unbelegten Plätze.

Moment, queuespace ist als int* definiert.
Wo du bei großen oder negativen Werten in Probleme kommst ist, dass dein i ein int ist, die Indizes aber unsigned longs.
Aber all das ist m.E. gar nicht das Problem hier, sondern, dass du noch nicht verstanden hast wie die Queue funktionieren soll.

Es gibt einen Struct. Dieser enthält ein int Array Queuespace. Queuespace wird bei Bedarf vergrößert. Du hast aber versucht den Speicher des gesamten Queue Objektes zu realloziieren. Ich sehe weder ein malloc, noch ein realloc für den Speicher deiner Queue-Elemente in Queuespace, d.h. du schreibst die ganze Zeit in irgendwelche Speicherbereiche und liest auch wieder aus denen heraus wo irgendwelche anderen Daten liegen.

Noch ein Detail:

free(q->queuespace);

Hier möchtest du free[](q->queuespace); nutzen. Die [] sorgen dafür, dass nicht nur das Element auf das der Pointer queuespace zeigt freigegeben wird, sondern der gesamte Speicher des Arrays.

Hier möchtest du free[](q->queuespace); nutzen. Die [] sorgen dafür, dass nicht nur das Element auf das der Pointer queuespace zeigt freigegeben wird, sondern der gesamte Speicher des Arrays.

Du verwechselst C mit C++. In C++ gibt es eine Unterscheidung zwischen delete und delete[], in C gibt es dagegen nur free.

@Vollkorn: Könntest du vllt ein Beispiel geben? Wie ich es verstanden habe weist malloc einen festen Speicher zu, und realloc erweitert diesen Speicher (z.B. bei Listen).
Wo soll realloziert werden? Ist mein malloc für die Queue richtig?

Dein struct besteht aus 5 Variablen, in queue_new initialisierst Du aber nur 4 davon. Da fehlt noch sowas wie:
queue->queuespace = malloc(queuesize * sizeof(Queueelement));

/* The following function resizes the queue by doubling the space reservoir  */
void queue_double_size(Queue *q)
{
// Vorhandener Speicher des Queues wird verdoppelt
q = (Queue *) realloc (*q, sizeof(q*)*2);
// Zu beachten ist, dass die Elemente nach hinten verschoben werden muessen
// damit keine "Loch" entsteht
}

Danke. Hab meinen Fehler eingesehen. Muss ich den Queue reallozieren. Ist das so richtig oder zusätzlich noch den queuespace reallozieren?

Korrektur:

/* The following function resizes the queue by doubling the space reservoir  */
void queue_double_size(Queue *q)
{
// Vorhandener Speicher des Queues wird verdoppelt
q = (Queue *) realloc (q, 2 * q->queuesize * sizeof(*q));  // korrigiert
// Zu beachten ist, dass die Elemente nach hinten verschoben werden muessen
// damit keine "Loch" entsteht
}

Du musst ausschließlich q->queuespace realloziieren (was für ein Wort), nicht q selber! Du brauchst ja nicht plötzlich mehr Variablen in q, die 5 reichen nach wie vor aus. (Eine Veränderung von q würde der Aufrufer auch gar nicht bemerken, weil der Zeiger ja per Wert übergeben wird.)

Das obige habe ich durch:

q = realloc (q->queuespace, 2 * sizeof(*q->queuespace));

ersetzt. Richtig so?

Korrektur: q->queuespace = realloc (q->queuespace, 2 * sizeof(*q->queuespace));

Nein, sizeof(*q->queuespace) ist gleich sizeof(int), damit wirst Du nicht glücklich werden. Wozu hast Du denn die Variable queuesize?
q->queuesize *= 2; q->queuespace = realloc(q->queuespace, q->queuesize * sizeof(Queueelement));

Ok danke. Die neuen Speicherplätze werden jetzt hinten drangehängt richtig? Wenn ja, dann muss ich doch alle Elemente nach hinten verschieben und zwar ab queuesize-1?

Hm, könnte sein. Wieso fängt Deine Queue überhaupt hinten an und nicht vorne?

Du verwechselst C mit C++. In C++ gibt es eine Unterscheidung zwischen delete und delete[], in C gibt es dagegen nur free.

Oh, danke. Bin ja eher C++-Mensch und habe dann aus der Hüfte geschossen :/

@anonym: Genau das was Fred dir gerade erklärt hat meinte ich auch :)

Hmmm. Dachte, dass es besser wäre wegen dem FIFO-Charakter, sonst entstehen vorne die "Löcher" wenn man "dequeuen" möchte.

Löcher entstehen so oder so, egal ob Du vorne oder hinten anfängst. Das ganze soll ein zyklisches Array sein, oder?

zirkuläres Array sollte identisch zu zyklisches Array denke ich. Hab aber keine Ahnung was damit gemeint ist.

Mal doch mal auf, wie das Array aussehen soll, wenn Du 5 Elemente einfügst und anschließend 3 entfernst. Wo stehen dann die verbliebenen 2 Elemente?

Und dann füg mal so viele Elemente ein, dass Du über den Rand hinausläufst und am anderen Rand wieder anfängst. Das ist ein zyklisches/zirkuläres/whatever Array.

queue = queue_new(5);
queue_enqueue(queue, 1);
queue_enqueue(queue, 2);
queue_enqueue(queue, 3);
queue_enqueue(queue, 4);
queue_enqueue(queue, 5);

Array = [5 4 3 2 1]

queue_dequeue(queue);
queue_dequeue(queue);

Array [5 4 3]

queue = queue_new(5);
queue_enqueue(queue, 1);
queue_enqueue(queue, 2);
queue_enqueue(queue, 3);
queue_enqueue(queue, 4);
queue_enqueue(queue, 5);

Array = [5 4 3 2 1]

queue_dequeue(queue);
queue_dequeue(queue);
queue_dequeue(queue);

Array [5 4]

Arrays werden nicht auf magische Weise kleiner. Das hat immer noch die Größe 5, aber Du benutzt nur einen Ausschnitt daraus.

[5 4 x x x]

Jetzt füg bitte noch mal das Element 6 ein.

Ja richtig gar nicht bedacht. Wenn es vollläuft dann man etwas entfernt, müssen alle elemente um die anzahl der gelöschten Elemente-1 verschoben werden.

Nein, bei einem zirkulären Array brauchst Du nichts zu verschieben! Ansonsten hätte dequeue ja lineare Komplexität. Du klebst die beiden Enden einfach gedanklich aneinander und hast dann einen Kreis.

Ich sehe gerade, das hast Du in den Zeilen 105 bis 115 und 130 bis 136 ja auch schon korrekt implementiert.

Ach so. Ich bin davon ausgegangen wenn es leer ist. Das deckt ja auch das was du meintest ab.

Wenn ich mit den Werten im main fülle wird wegen dem zyklischen Array alte quesize-1 gefüllt und nicht die neue qeuesize-1…