Einfach verkettete Listen

Schnelle objektorientierte, kompilierende Programmiersprache.
schlafmütze
Beiträge: 67
Registriert: Mi Mär 11, 2009 6:48 pm

Einfach verkettete Listen

Beitrag von schlafmütze » So Jun 14, 2009 6:52 pm

Ich habe gerade ein Problem mit mit dem Thema verkettete Listen.
Ich habe hier in Mein Buch ein Programm der Stück für Stück erweitert werden muss bis zum Ende des Buches bis es ein fähiges Programm geworden ist.
Bin mittlerweile ziemlich weit mit dem Buch bis zum Thema Einfach verkettete Listen und das Programm was sich jetzt noch erweitern soll heißt Lagerverwaltungsprogramm. Das Programm soll ich jetzt mit dynamische Datenstrukturen weiter verbessern

An manchen Zeilen verstehe ich es wirklich nicht, zusätzlich habe ich lange überlegt bin aber nicht drauf gekommen ist aber von ein Anfänger zu erwarten oder ? :lol:

Jetzt muss ich ein Element hinzufügen.

Hier ist der Code für das Programm:

Code: Alles auswählen

struct lagerverwaltung
    {
       long artikelnummer;
       char artikelbezeichnung[100];
       int anzahl_artikel;
       struct lagerverwaltung *next;
    };
struct lagerverwaltung *first = NULL;

void read_lagerverwaltung(void)
{
  long an;
  char at[100];
  int aa;
  printf("Artikelnummer      : ");
  scanf("%ld",&an); fflush(stdin);
  printf("Artikelbezeichnung : ");
  fgets(at, sizeof(at), stdin);
  printf("Anzahl d. Artikel : ");
  scanf("%d",&aa);
  insert_lagerverwaltung(an,at,aa);
}
void insert_lagerverwaltung(long art_nr,  char art_tit[], int anz_art)                 HIER VERSTEHE ICH ES ICH NOCH (ES WERDEN ALLE DATEN EINGELSEN

                                                                                                        
{
struct lagerverwaltung *lager_ptr;
if(first == NULL)
{
first = (struct lagerverwaltung *) malloc(sizeof(struct lagerverwaltung));
if(first == NULL)
 {
   printf("Speicherplatzmangel!!!\n");
   exit(0); /* Programm beenden */
 }
else
 {
    first->artikelnummer = art_nr;

strcpy(first->artikelbezeichnung, art_tit);
first->anzahl_artikel = anz_art;
first->next = NULL;           ICH VERSTEHE DEN SINN DIE ZEILE NICHT
    }

}

AB HIER
else
  {
   lager_ptr=first;
   while(lager_ptr->next != NULL)
   lager_ptr = lager_ptr->next;
   lager_ptr->next=(struct lagerverwaltung *) malloc(sizeof(struct lagerverwaltung));
   if(lager_ptr->next == NULL)
 {
   printf("Speicherplatzmangel!!!\n");
   exit(0); /* Programm beenden */
 }
else
 {       
        lager_ptr = lager_ptr->next;
        lager_ptr->artikelnummer = art_nr;
        strcpy(lager_ptr->artikelbezeichnung,
        art_tit);
        lager_ptr->anzahl_artikel = anz_art;   BIS HIER PASSIERT DAS GLEICHE
        lager_ptr->next = NULL;  UND WIEDER VERSTEHE ICH DEN SINN DIE ZEILE NICHT.
      }
   }
  printf("\nNeuer Artikel hinzugefuegt\n\n");
}



Ich könnte das Buch an den ich gerade arbeite auch als PDF hochladen wenn es die Diktatoren hier zulassen. ;) (nicht ernst gemeint )
Bitte um Hilfe
Danke im voraus

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Einfach verkettete Listen

Beitrag von cloidnerux » So Jun 14, 2009 6:59 pm

Diese Thema wurde schon mehrfach angesprochen: http://forum.proggen.org/viewtopic.php?f=21&t=527
Vom Prinzip her ist es das gleiche.
Eine Liste hat folgende Funktionsweise: Jedes elment hat einen pointer auf das nächste Element.
Wenn es (noch) kein nächstes gibt ist es ein NULL pointer.
Wenn du ein Element hinzufügen willst, allokierst du Speicher und setzt im letzten Element den Pointer für das nächste Elemnt auf den Speicher dne du Alkoiert hast. Dort liegt denn das nächste elment.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8859
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Einfach verkettete Listen

Beitrag von Xin » So Jun 14, 2009 7:11 pm

schlafmütze hat geschrieben:Jetzt muss ich ein Element hinzufügen.

Ich könnte das Buch an den ich gerade arbeite auch als PDF hochladen wenn es die Diktatoren hier zulassen. ;) (nicht ernst gemeint )
Ich habe vermutlich die Frage überlesen... was ist das Problem.

Die Lösung findet sich eventuell hier: http://www.proggen.org/doku.php?id=c:list:start - wenn nicht... gut zu wissen, dann muss ich das wohl erweitern ;-)

Mit freundlichen Grüßen,
Dein Diktator
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

schlafmütze
Beiträge: 67
Registriert: Mi Mär 11, 2009 6:48 pm

Re: Einfach verkettete Listen

Beitrag von schlafmütze » So Jun 14, 2009 7:18 pm

Es sind eigentlich nur zwei Zeilen die ich im Programm nicht richtig nachvollziehen kann. :|
Die Lösung findet sich eventuell hier: http://www.proggen.org/doku.php?id=c:list:start - wenn nicht... gut zu wissen, dann muss ich das wohl erweitern ;-)
Ich werde mir es mal durchlesen


Dein Diktator
:lol:

nufan
Wiki-Moderator
Beiträge: 2558
Registriert: Sa Jul 05, 2008 3:21 pm

Re: Einfach verkettete Listen

Beitrag von nufan » So Jun 14, 2009 7:27 pm

Hier dein Code kommentiert und schön eingerückt (das nächste Mal bitte selber machen):

Code: Alles auswählen

struct lagerverwaltung
{
  long artikelnummer;
  char artikelbezeichnung[100];
  int anzahl_artikel;
  struct lagerverwaltung *next;        // Zeiger auf nächstes Element
};

struct lagerverwaltung *first = NULL;  // Zeiger auf das erste Element einer Liste; Liste leer --> Zeiger zeigt auf NULL


void read_lagerverwaltung(void)
{

  long an;
  char at[100];
  int aa;

  printf("Artikelnummer      : ");
  scanf("%ld",&an);                 // Eingabe der Artikelnummer
  fflush(stdin);

  printf("Artikelbezeichnung : ");
  fgets(at, sizeof(at), stdin);     // Eingabe der Artikelbezeichnung

  printf("Anzahl d. Artikel : ");
  scanf("%d",&aa);                  // Eingabe der Anzahl an Artikel

  insert_lagerverwaltung(an,at,aa);  // in Liste einfügen

}


void insert_lagerverwaltung(long art_nr,  char art_tit[], int anz_art)                 
{

  struct lagerverwaltung *lager_ptr;

  if(first == NULL)                 // prüfen ob Liste leer
  {

    // neues Element ist erstes Element in der Liste

    first = (struct lagerverwaltung *) malloc(sizeof(struct lagerverwaltung));      // Speicher für einen Artikel reservieren

    if(first == NULL)       // Speicher konnte nicht allokiert werden
    {
      printf("Speicherplatzmangel!!!\n");
      exit(0); /* Programm beenden */
    }

      else                  // Speicher konnte allokiert werden
      {

        first->artikelnummer = art_nr;       // zuvor eingelesene Werte zuweisen
        strcpy(first->artikelbezeichnung, art_tit);  // -"-
        first->anzahl_artikel = anz_art;     // -"-
				
        first->next = NULL;       // Neues Element ist erstes Element in der Liste und hat deshalb keinen Nachfolger, der Zeiger wird auf NULL gesetzt

      }

  }

    else       // Es gibt bereits Elemente in der Liste
    {
	  
       lager_ptr=first;      // Hilfszeiger auf das erste Element
		  
       while(lager_ptr->next != NULL)      // ans Ende der Liste gehen
          lager_ptr = lager_ptr->next;
		  
       lager_ptr->next=(struct lagerverwaltung *) malloc(sizeof(struct lagerverwaltung));   // Speicher für neues Element allokieren

       if(lager_ptr->next == NULL)          // Speicher konnte nicht allokiert werden
       {
         printf("Speicherplatzmangel!!!\n");
         exit(0); /* Programm beenden */
       }
		  
         else
          {       
				
            lager_ptr = lager_ptr->next;     // der Hilfszeiger zeigt aufs letzte Element
					
            lager_ptr->artikelnummer = art_nr;        // eingelesene Werte zuweisen
            strcpy(lager_ptr->artikelbezeichnung, art_tit);  // -"-
            lager_ptr->anzahl_artikel = anz_art;   // -"-
					
            lager_ptr->next = NULL;  // neues Element wird am Ende der Liste eingefügt und hat deshalb keinen Nachfolger
		  
          }
	  
    }
  
  printf("\nNeuer Artikel hinzugefuegt\n\n");

}



"next" zeigt immer auf das nächste Element einer Liste. Gibt es keinen Nachfolger zeigt es auf NULL.


EDIT: Deine Tabs haben den Editor ein bisschen durcheinander gebracht...

schlafmütze
Beiträge: 67
Registriert: Mi Mär 11, 2009 6:48 pm

Re: Einfach verkettete Listen

Beitrag von schlafmütze » So Jun 14, 2009 8:52 pm

Code: Alles auswählen

struct lagerverwaltung *first = NULL;  // Zeiger auf das erste Element einer Liste; Liste leer --> Zeiger zeigt auf NULL
Welche Liste und was für ein erstes Element und wie soll der wissen welche Element der erste ist ?

Code: Alles auswählen

 insert_lagerverwaltung(an,at,aa);          void insert_lagerverwaltung(long art_nr,  char art_tit[], int anz_art) 
Das sind doch zwei gleiche Funktionen. :?: :?:

Code: Alles auswählen

if(first == NULL)                 // prüfen ob Liste leer


Welche Liste ?

Ich bin jetzt echt völlig durcheinander. :shock:
Die ganze insert lagerverwaltung verstehe ich jetzt nicht mehr. :oops: :|

nufan
Wiki-Moderator
Beiträge: 2558
Registriert: Sa Jul 05, 2008 3:21 pm

Re: Einfach verkettete Listen

Beitrag von nufan » So Jun 14, 2009 9:14 pm

schlafmütze hat geschrieben:Welche Liste und was für ein erstes Element und wie soll der wissen welche Element der erste ist ?
Du erstellst in deinem Programm eine Liste aus Artikeln. Jeder Artikel hat einen eigenen Speicherblock. Eine Liste besteht aus mehreren Speicherblöcken. Jeder Speicherblock hat einen Zeiger auf den nächsten Speicherblock.
Das erste Element ist der erste Artikel den du in deine Liste aufnimmst. Der Kopfzeiger (in deinem Fall "first") deiner Liste zeigt auf ihn.

schlafmütze hat geschrieben:

Code: Alles auswählen

    insert_lagerverwaltung(an,at,aa);          void insert_lagerverwaltung(long art_nr,  char art_tit[], int anz_art) 
Das sind doch zwei gleiche Funktionen. :?: :?:
Ja. Und...?
Der linke Teil ist der Aufruf und der rechte Teil ist der Funktionskopf. Du übergibst die Artikelnummer, -bezeichnung und -anzahl.
schlafmütze hat geschrieben:Welche Liste ?
Jene die du in deinem Programm anlegst?!

schlafmütze hat geschrieben:Die ganze insert lagerverwaltung verstehe ich jetzt nicht mehr. :oops: :|
Die insert-Funktion fügt einen Artikel in die Liste ein. Ich gehs nochmal gaaaanz langsam Schritt für Schritt durch...:

Code: Alles auswählen

void insert_lagerverwaltung(long art_nr,  char art_tit[], int anz_art)                 
Funktionskopf. Du übergibst zuvor eingelesene Werte (wurden in "read_lagerverwaltung" eingegeben). Das sind die Artikelnummer, eine Artikelbezeichnung und die Anzahl.

Code: Alles auswählen

  struct lagerverwaltung *lager_ptr;
Du legst einen Hilfszeiger für die Liste an.

Code: Alles auswählen

  if(first == NULL)
Du prüfst ob die Liste leer ist.

Wenn ja:

Code: Alles auswählen

    first = (struct lagerverwaltung *) malloc(sizeof(struct lagerverwaltung));
Speicher für den ersten Artikel reservieren.

Code: Alles auswählen

    if(first == NULL)       // Speicher konnte nicht allokiert werden
    {
      printf("Speicherplatzmangel!!!\n");
      exit(0); /* Programm beenden */
    }
Diesen Teil kannst du genauso gut weglassen. Er prüft ob der Speicher richtig reserviert werden konnte. "Speicherplatzmangel" ist bei diesem Programm sowieso unwahrscheinlich...

Code: Alles auswählen

      else
      {

        first->artikelnummer = art_nr;   
        strcpy(first->artikelbezeichnung, art_tit); 
        first->anzahl_artikel = anz_art;  
            
        first->next = NULL; 

      }
So. Wir haben jetzt Speicher für das neue Element. Also können wir die übergebenen Werte zuweisen. Du fügst die Artikel immer am Ende der Liste ein. Da der Artikel aber der erste ist, ist das ein Spezialfall. Das erste Element hat anfangs logischerweise keinen Nachfolger, deshalb wird sein next-Zeiger auf NULL gesetzt.


Wenn nein:

Code: Alles auswählen

       lager_ptr=first; 
Hilfszeiger wird auf den ersten Artikel gesetzt.

Code: Alles auswählen

       while(lager_ptr->next != NULL)
          lager_ptr = lager_ptr->next;
Du suchst nach dem letzten Artikel in der Liste. Die Schleife läuft so lange, bis du bei einem Artikel bist, der keinen Nachfolger hat, also bist du beim letzten Artikel.

Code: Alles auswählen

       lager_ptr->next=(struct lagerverwaltung *) malloc(sizeof(struct lagerverwaltung));
Du reservierst Speicher für den Nachfolger des letzten Artikels.

Code: Alles auswählen

       if(lager_ptr->next == NULL)      
       {
         printf("Speicherplatzmangel!!!\n");
         exit(0); /* Programm beenden */
       }
Siehe oben.

Code: Alles auswählen

         else
          {       
            
            lager_ptr = lager_ptr->next;
               
            lager_ptr->artikelnummer = art_nr;    
            strcpy(lager_ptr->artikelbezeichnung, art_tit); 
            lager_ptr->anzahl_artikel = anz_art; 
               
            lager_ptr->next = NULL; 
       
          }
Du rückst den Zeiger auf den soeben reservierten Speicher. Danach wieder die übergebenen Werte zuweisen. Du fügst den Artikel am Ende der Liste ein, deshalb hat dieser Artikel keinen Nachfolger --> der Zeiger wird auf NULL gesetzt.


Verständlich?
Wenn nicht solltest du vielleicht das ganze Kapitel noch einmal im Tutorial nachlesen.

schlafmütze
Beiträge: 67
Registriert: Mi Mär 11, 2009 6:48 pm

Re: Einfach verkettete Listen

Beitrag von schlafmütze » So Jun 14, 2009 11:18 pm

Hier dein Code kommentiert und schön eingerückt (das nächste Mal bitte selber machen):
Tut mir leid werde ich nächstes mal sicher tun.


Ich dank dir für die Perfekte Erklärung wunderbar und wie gesagt ich entschuldige ich mich das du es nochmal erklären musstest.
Naja den Aufwand mach nicht jeder und nochmals super vereinfacht und erklärt. :)
Hab alles verstanden.

mfg schlafmütze

schlafmütze
Beiträge: 67
Registriert: Mi Mär 11, 2009 6:48 pm

Re: Einfach verkettete Listen

Beitrag von schlafmütze » So Jun 28, 2009 2:34 pm

Nun hab ich paar Tage pause gemacht und wollte das Programm kompilieren ich habe ständig nach den Fehler gesucht aber irgendwie finde ich es nicht.

Hier ist der Quellcode

Code: Alles auswählen

#include <stdio.h>

int main()

{

struct lagerverwaltung
{
    long artikelnummer;
    char artikelbezeichnung[100];
    int anzahl_artikel;
    struct lagerverwaltung *next;
};

struct lagerverwaltung *first = NULL;

void read_lagerverwaltung(void)
{
  
   long an;
   char at[100];
   int aa;

   printf("Artikelnummer      : ");
   scanf("%ld",&an); 
   fflush(stdin);

   printf("Artikelbezeichnung : ");
   fgets(at, sizeof(at), stdin);

   printf("Anzahl d. Artikel : ");
   scanf("%d",&aa);

   insert_lagerverwaltung(an,at,aa);

}

void insert_lagerverwaltung(long art_nr, char art_tit[], int anz_art)
{
      
      	struct lagerverwaltung *lager_ptr;
     	
     	
     	 if(first == NULL)
   	      {
     	
     	       first = (struct lagerverwaltung *) malloc(sizeof(struct lagerverwaltung));

     	       if(first == NULL)
      	        {
                printf("Speicherplatzmangel!!!\n");
                exit(0); /* Programm beenden */
                }

     	        else
      	        {
                                  first->artikelnummer = art_nr;
                                  strcpy(first->artikelbezeichnung, art_tit);
    	                          first->anzahl_artikel = anz_art;
    	
       	
    	                          first->next = NULL;
  	         }
         }


        else
  	{
     
     	             lager_ptr=first;
     	
    	             while(lager_ptr->next != NULL)
                          lager_ptr = lager_ptr->next;
    	
     	             lager_ptr->next=(struct lagerverwaltung *)malloc(sizeof(struct lagerverwaltung));

     	             
                     if(lager_ptr->next == NULL)
      	             {
                       printf("Speicherplatzmangel!!!\n");
                       exit(0); /* Programm beenden */
      	             }
     	                      
                             else
      	                       {
        
                                   lager_ptr = lager_ptr->next;

                                  lager_ptr->artikelnummer = art_nr;
                                  strcpy(lager_ptr->artikelbezeichnung, art_tit);
                                  lager_ptr->anzahl_artikel = anz_art;


                                  lager_ptr->next = NULL;
                                }
                     }
  	printf("\nNeuer Artikel hinzugefuegt\n\n");
}







und hier der Fehler

Code: Alles auswählen

verkettetelisten.c: In Funktion »insert_lagerverwaltung«:
verkettetelisten.c:47: Warnung: Unverträgliche implizite Deklaration der eingebauten Funktion »malloc«
verkettetelisten.c:51: Warnung: Unverträgliche implizite Deklaration der eingebauten Funktion »exit«
verkettetelisten.c:56: Warnung: Unverträgliche implizite Deklaration der eingebauten Funktion »strcpy«
verkettetelisten.c:86: Warnung: Unverträgliche implizite Deklaration der eingebauten Funktion »malloc«
verkettetelisten.c:90: Warnung: Unverträgliche implizite Deklaration der eingebauten Funktion »exit«
verkettetelisten.c:101: Warnung: Unverträgliche implizite Deklaration der eingebauten Funktion »strcpy«
verkettetelisten.c: In Funktion »main«:
verkettetelisten.c:108: Fehler: expected declaration or statement at end of input
Die Oberen sind nur Warnung aber da unten ist ein Fehler . :?:

Bitte um Hilfe

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8859
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Einfach verkettete Listen

Beitrag von Xin » So Jun 28, 2009 2:41 pm

Du definierst aber nicht alles in der main()?!?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten