Zwei Queues zu einem Stack

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.

Mike1087

;fricky schrieb:

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*

Was soll das denn sein? Also das hat mit dem was ICH zu Listen gelernt habe so gut wie garnichts zu tun!

Mike1087

µngbd schrieb:

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

Was soll denn das?

Das ist das Hinzufügen eines neuen Listenknotens! Hab ich als Put definiert damit man im Prgramm sich die Schreibarbeit erspart und gleich Put nehmen kann!

Mike1087

Irgendwo ist da ein Fehler! Ich finde Ihn nicht!
Mein Compiler sagt "Zugriffsverletzung" was heist das?

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

typedef struct node *Zeiger;
typedef struct node          //Alias der Liste = NODE
 {                   
  Zeiger next; 
  int zahl;           
 } NODE;

Zeiger p, q, First, Last;   //First=Anker, Last=Zeiger auf das Ende der Liste, q=Zeiger auf ein neues Element, p=Entnahmezeiger

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

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

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

     //Ausgeben der Daten von Queue1

     printf("In Queue 1 wurden folgende Daten geschrieben:");

     for (i=0; i<=N; i++)
     {
         p = First; 
         printf("%5d \n",p->zahl); 
         First = First->next; 
         p->next = NULL; 
         free(p);
     }

    system("Pause");
    return 0;   
}

Mike1087

So! Programm soweit fertig! Nur es kommt halt immernoch diese Fehlermeldung! Wenn mir da einer weiterhelfen könnte wär das echt sehr nett!

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

typedef struct node *Zeiger;
typedef struct node          //Alias der Liste = NODE
 {                   
  Zeiger next; 
  int zahl;           
 } NODE;

Zeiger p, q, First, Last;      //Q1 - First=Anker, Last=Zeiger auf das Ende der Liste, q=Zeiger auf ein neues Element, p=Entnahmezeiger
Zeiger x, y, Erstes, Letztes;  //Q2 - Erstes=Anker, Letztes=Zeiger auf das Ende der Liste, y=Zeiger auf ein neues Element, x=Entnahmezeiger

void main ()                   //Hauptprogramm
{
     int N, i;                 //N=Länge der Liste, i= Laufindex
     First = NULL;

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

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

     while (First->next!=NULL || Erstes->next!=NULL)
     {

       //Umschichten von 1 in 2

        //Anlegen der zweiten queue mit dem ersten Element von q1
        Erstes = (Zeiger) malloc(sizeof(NODE)); Erstes->zahl=First->zahl; Erstes->next = NULL; Erstes=Letztes;
        //Löschen des ersten Elements von q1
        p = First; First = First->next; p->next = NULL; free(p);

        for (i=1; i<=N-1; i++)
        {        
           //Einlesen der Zahl aus dem ersten Element von q1
           y = (Zeiger)malloc(sizeof(NODE)); 
           y->zahl=First->zahl; 
           y->next = NULL; 
           Letztes ->next =y; 
           Letztes = y;

           //Löschen des ersten Elements von q1
           p = First;
           First = First->next;
           p->next = NULL;
           free(p); 
        }
        //Letztes Element von q1
        printf("%5d \n",First->zahl);
        //Löschen des letzten Elements
        p = First;
        First = First->next;
        p->next = NULL;
        free(p); 

       //Umschichten von 2 in 1

        if (Erstes->next!=NULL)
        {
          //Anlegen der ersten queue mit dem ersten Element von q2
          First = (Zeiger) malloc(sizeof(NODE)); First->zahl=Erstes->zahl; First->next = NULL; Erstes=Letztes;
          //Löschen des ersten Elements von q2
          x = Erstes; Erstes = Erstes->next; x->next = NULL; free(x);

          for (i=1; i<=N-1; i++)
          {        
            //Einlesen der Zahl aus dem ersten Element von q2
            q = (Zeiger)malloc(sizeof(NODE)); 
            q->zahl=Erstes->zahl; 
            q->next = NULL; 
            Last ->next =q; 
            Last = q;

            //Löschen des ersten Elements von q2
            x = Erstes;
            Erstes = Erstes->next;
            x->next = NULL;
            free(x); 
          }
          //Letztes Element von q2
          printf("%5d \n",Erstes->zahl);
          //Löschen des letzten Elements
          x = Erstes;
          Erstes = Erstes->next;
          x->next = NULL;
          free(x);
        }
     }

  //Ausgeben des letzten Elements:

      if (Erstes->next=NULL)
      { 
         printf("%5d \n",Erstes->zahl);
         //Löschen des letzten Elements
         x = Erstes;
         Erstes = Erstes->next;
         x->next = NULL;
         free(x);
      }

      if (First->next=NULL)
      { 
         printf("%5d \n",First->zahl);
         //Löschen des letzten Elements
         p = First;
         First = First->next;
         p->next = NULL;
         free(p); 
      }  

      system("Pause");
      return 0;   
}

Jetzt haben wir dir Abhandlungen geschrieben, Links gesucht und zwei fast fertige Lösungen gebaut: und du wirfst immer noch mit dem Spaghetticode um dich. Ich geb's auf.

Mike1087

Was sollen denn die zwei fast fertigen Lösungen sein?

Ich habe nicht alles durchgesehen, aber hier guck mal:

First = (Zeiger) malloc(sizeof(NODE)); First->zahl=1; First->next = NULL; First=Last;

Du setzt First auf 0, damit ist die von malloc zugeteilte Adresse nicht mehr erreichbar.
Außerdem: den Rückgabewert von malloc stets prüfen, und nicht casten.

Mike1087 schrieb:

Was soll das denn sein? Also das hat mit dem was ICH zu Listen gelernt habe so gut wie garnichts zu tun!

das was du wolltest, ein 'simpler code für eine queue', nix mit listen.