Zwei Queues zu einem Stack

Mike1087

So gut wie garnichts weil mir mein Compiler immer nur Fehlermeldungen ausspuckt!

Mike1087

Mir würde ja der Quellcode von einem Programm wo ein Queue erstellt wird schon reichen!

Mike1087

Soweit bin ich:
Und es ist irgendwie ein Fehler drin!

#include <stdio.h>
#include <stdlib.h>

//  Knoten für lineare Liste

 typedef struct node 
  {
     struct node *next;       // Zeiger auf den nächsten Knoten
     int key;                 // Knotennummer
	 int zahl1;               // Gespeicherte Zahl
  }

//  Hauptprogramm

 int main(void)
 {
    int i; 
    node *Queue1 = NULL;      // Initialisierung: "Queue1" ist der Anker des 1. Queues

    for (i = 1; i <= 6; i++)
     {
     printf("\nBitte geben sie die %i. Integerzahl ein:",zahlINT);

     // Neuen Knoten einfügen
     node *new_node = (node *) malloc ( sizeof( node )); // Speicher für neuen Knoten reservieren
     new_node->next = NULL;                              // Zeiger initialisieren
     new_node->key = i;                                  // Knoten Zählen
     scanf("%i", &zahl1);                                 // Zahl Einlesen
    };

    system("Pause");
    return 0;  
 }

Und es ist irgendwie ein Fehler drin!

Wird wohl daran liegen, dass in Zeile 29 zahl1 nicht bekannt ist. Aber warum sagst du uns das nicht gleich? Ich bin doch kein Compiler.

Mike1087

Gibt es ne Möglichkeit zwei Funktionen (Put und Get) zu erstellen und dann im Hauptprogramm nur noch mit Put und Get zu arbeiten? Wäre doch am elegantesten! WIe könnte man das realisieren?

Mike1087 schrieb:

Gibt es ne Möglichkeit zwei Funktionen (Put und Get) zu erstellen und dann im Hauptprogramm nur noch mit Put und Get zu arbeiten? Wäre doch am elegantesten! WIe könnte man das realisieren?

Mach dir eine eigene *.c-Datei, die die Listenverwaltung für die Queue erledigt, und mach dort alles bis auf die beiden Funktionen static . Dann kann keiner mehr drauf zugreifen ohne die Datei zu verändern.

node *new_node = (node *) malloc ( sizeof( node ));
// free() kommt nie

Ist dir schon der Speicher ausgegangen?

Mike1087

Das Programm hat ja noch nicht funktioniert!
Aber du scheinst echt Ahnung zu haben!
Ich stell mir das so vor, dass ich im Hauptprogramm für das füllen der Queue nur noch so ein Code hab:

for (i = 1; i <= 6; i++)
  { 
  Queue1 = Put(Queue1, i );
  };

Folgende Vorschläge:

1.) Statt

Queue1 = Put(Queue1, i );

Wäre mir lieber:

Put(Queue1, i);

Den ganzen Zauber soll die Put-Funktion erledigen und vor dem Anwender verstecken. Ist aber letztlich Geschmacksache.

2.) Mach dir folgende Funktionen:

- NewQueue()
um eine neue leere Queue zu erzeugen (falls du dich später entscheiden solltest, dass eine leere Queue anders repräsentiert wird als durch NULL). Rcükgabetyp sollte ein Zeiger auf Queue sein.

- Put()
zum Reinschieben in die Queue, aber (siehe oben) vielleicht so, dass man keine Zuweisung mehr machen muss. Typ sollte void sein (oder besser int, damit man an der Rückgabe erkennen kann, ob ein Fehler passiert ist). Da wird ein malloc() drin stecken.

- Push()
zum Rausholen. Typ ist in deinem Fall int weil du eine Queue von int's anlegen willst. Da wird ein free() drin stecken.

- DestroyQueue()
zum Freigeben einer Queue die keiner mehr braucht. Da wird für jedes Element in der Queue ein free() drin stecken (oder noch mehr, falls du die Repräsentation änderst).

Aber du scheinst echt Ahnung zu haben!

Schleimen wird schon helfen? Aber im Ernst: ich bin schon lange genug hier unterwegs, da schnappt man manches auf. Die, die's mir beigebracht haben, sind aber teilweise auch noch hier unterwegs.

ich schrieb:

- Push()
zum Rausholen ...

Ich meinte natürlich Get() und nicht Push().

Mike1087

Das sollte jetzt nicht direkt schleimen sein!
Ich versuch mal mein Glück!
Also die Put Funktion müsste in etwa so aus sehen oder?

int Put(int)
{
int i=1
node *new_node = (node *) malloc ( sizeof( node )); // Speicher für neuen Knoten reservieren
new_node->next = NULL;                              // Zeiger initialisieren
new_node->key = i;                                  // Knoten Zählen
new_node->zahl = i;                                 // Zahl Speichern
i++
}

Mike1087 schrieb:

Das sollte jetzt nicht direkt schleimen sein!

Bitte mich nicht zu ernst nehmen.

Ich versuch mal mein Glück!
Also die Put Funktion müsste in etwa so aus sehen oder?
...

In etwa, ja. Der key-Member ist ziemlich sicher unnötig.

Auch hast du vergessen, den next-Zeiger des letzten Elements auf das neue zu setzen. Da macht es dann Probleme, wenn die leere Queue NULL ist, weil da drin kein Zeiger ist, den man setzen könnte. Deshalb könnte man die Repräsentation ändern. ZB indem man eine neue Struktur queue einführt, in der ein Zeiger auf node ist (den Anfang der Queue -- oder das Ende?), und eine zweite Struktur node (wie bisher), die einen Knoten der Liste bedeutet. Aber das geht sicher auch anders.

Ich geh jetzt schlafen, vielleicht träum ich ja davon, wie man am besten eine Queue baut. Aber googlen bringt sicher grössere Erfolgschancen.

Mike1087

Okay! wär echt cool wenn dir da mehr zu einfallen würde! Ich komm nämlich garnicht klar mit dem Zeug!

mittels zwei Schlangen kann die Funktionalität eines
Stapels realisiert werden: Dazu müsste man die Reihenfolge der gespeicherten
Elemente „umdrehen“, damit das älteste Element einer Schlange zum jüngsten
Element einer anderen Schlange wird. Da Schlangen, also FIFO-Speicher, aber
die Reihenfolge der gespeicherten Elemente in der Ausgabe beibehalten, besteht
zunächst keine Möglichkeit diese „umzudrehen“. Wenn man nun eine der beiden
Schlangen stets leer hält und dort das neuste Element einträgt, leert man
anschliessend die andere Schlange und fügt die Elemente in die erste Schlange
ein. Damit wird das neuste Element stets das erste eingefügte Element in dieser
Schlange sein und somit nach aussen als zuletzt eingefügtes Element wieder als
erstes ausgelesen werden.

So und jetzt nur noch in Code meißeln! Have fun!!!

Okay! wär echt cool wenn dir da mehr zu einfallen würde! Ich komm nämlich garnicht klar mit dem Zeug!

Ich hab nicht von Queues geträumt. Machs doch einfach so:
http://www.go4expert.com/forums/showthread.php?t=1279
oder so:
http://lispmachine.wordpress.com/2009/05/13/queue-in-c/
oder so:
http://www.c.happycodings.com/Data_Structures/code24.html
oder so:
http://www.daniweb.com/code/snippet216330.html
oder ...

Mike1087

Erstmal danke! Aber der Code ist viel zu komplex! Um das zu kapieren bräuchte ich sicher drei Wochen oder so! Ich muss allerdings das Programm bis Montag feritg haben! Also wenn das hier noch irgend ein Programmiergott sieht! Wär es nicht möglich ein simplen code zum erstellen einer Queue zu posten?
LG
Micha

Mike1087 schrieb:

Wär es nicht möglich ein simplen code zum erstellen einer Queue zu posten?

Ich bin doch nicht der Messias. Aber wenn du Fragen zu C hast, werd ich sie mir ansehen.

Mike1087

Okay findet jemand vll den Fehler hier in diesem Programm?

#include <stdio.h>
#include <stdlib.h>
#define Put    q = (Zeiger)malloc(sizeof(NODE)); q->next = NULL; q->zahl=i+2; Last ->next =q;
#define Get    q = First; printf("%5d",q->zahl); First = First->next; q->next = NULL; free(q);

typedef struct node *Zeiger;
typedef struct node
 {                   
  Zeiger next; 
  int zahl;           
 } NODE;

Zeiger q, First, Last;

void main ()
{
     int N, i;
     First = NULL;

     printf("Listenlaenge:"); // Abfragen wie lang die Liste wird
     scanf("%d",&N);

     //Füllen von Queue1
     First = (Zeiger) malloc(sizeof(NODE)); First->zahl=1;
     q=First;
     for (i=0; i<=N; i++)
     {
         Put
     }
     q->next = NULL;
     for (i=0; i<=N; i++)
     {
         Get
     }

    system("Pause");
    return 0;   
}

#define Put    q = (Zeiger)malloc(sizeof(NODE)); q->next = NULL; q->zahl=i+2; Last ->next =q;

Was soll denn das?

Mike1087 schrieb:

Also wenn das hier noch irgend ein Programmiergott sieht! Wär es nicht möglich ein simplen code zum erstellen einer Queue zu posten?

auf doof:

#define SIZE <beliebiges hier einsetzen>

unsigned char mem[SIZE];
int r, w;

int put (unsigned char v)
{
    if ((w+1)%SIZE == r)
        return -1;  // voll
    mem[w=(w+1)%SIZE] = v;
    return 0;
}

int get (void)
{
    if (w == r)
        return -1;   // leer
    return mem[r=(r+1)%SIZE];
}

^^geht bestimmt noch etwas einfacher, darfst mich aber trotzdem 'gott' nennen *fg*

ich schrieb:

Ich bin doch nicht der Messias.

Vielleicht ein bisschen. Ich hab die halbe Nacht den Böhm-Garbage-Collector getestet, und nachdem der nun läuft, wollte ich wissen, wie kurz man ohne die lästigen free()'s diese Queue-Geschichte machen kann. Kürzer wird's wahrscheinlich nicht ordentlich gehen, wenn man unlimitierte Queues machen will (sonst könnte man Arrays nehmen und sich die Arbeit mit den Listen sparen -- das wäre viel einfacher):

#include <stdio.h>

/* der Garbage Collector erspart mir die free()'s */
#include <gc.h>

/* Typ für die Daten in der Queue */
typedef int data_t;

/* Ein Knoten */
typedef struct node {
    data_t data;
    struct node *next;
} node_t;

/* Eine ganze Queue */
typedef struct queue {
    node_t *front;    /* Anfang */
    node_t *rear;     /* Ende */
} queue_t;

/* Die Queue ist leer, wenn front- und rear-Zeiger NULL sind */
#define is_empty(q) (q->front == NULL)

queue_t *new_queue()
{
    /* Fehlerbehandlung von malloc() ausgespart */
    queue_t *q = GC_malloc(sizeof(queue_t));
    /* Die neue Queue ist leer */
    q->front = q->rear = NULL;
    return q;
}

int put(queue_t *q, data_t what)
{
    if (is_empty(q))
    {
        /* Queue ist leer -> front und rear der leeren Queue auf den neuen Knoten setzen
           Fehlerbehandlung von malloc() ausgespart */
        q->front = q->rear = GC_malloc(sizeof(node_t));
        q->front->data = what;
    }
    else
    {
        /* Queue ist nicht leer -> neuen Knoten ans Ende anhängen
           Fehlerbehandlung von malloc() ausgespart */
        node_t *new_rear = GC_malloc(sizeof(node_t));   /* neuer Knoten */
        new_rear->data = what;
        new_rear->next = NULL;      /* nach dem Ende kommt nichts mehr */
        q->rear->next = new_rear;   /* das alte Ende ist nicht mehr das Ende */
        q->rear = new_rear;         /* der neue Knoten ist das neue Ende */
    }
    return 0;
}

data_t get(queue_t *q)
{
    /* Fehlerbehandlung (falls die Queue leer ist) ausgespart */
    data_t value = q->front->data;  /* vordersten Wert holen und aufheben */
    q->front = q->front->next;      /* der nächste Knoten ist der neue Anfang */
    return value;
}

int main(void)
{
    /* das ganze testen */
    queue_t *q;
    int i;

    q = new_queue();
    for (i = 1; i <= 10; i++)
        put(q, i * 100);
    while (!is_empty(q))
        printf("da war %d\n", get(q));

    return 0;
}

Aber bedenke, dass ich zwei wesentliche Dinge weggelassen habe, nämlich die manuelle Speicherverwaltung und die Fehlerbehandlungen. Musst dir also noch überlegen, was schiefgehen könnte, und wo man Speicher freigeben muss.