4. Lineare Liste

Lineare Liste

  • N

    Hi,

    mein Problem grade ist, dass ich in C eine Lineare Liste programmieren muss und das ganze igrendwie nicht hinbekomme. Ich hab vorher mit Java gearbeitet und da hats auch geklappt, nur in C bin ich mit den Pointern noch nicht so vertraut.

    Also ich habe eine Struktur:

    struct list{
   char content;
   list* next;
}

    und jetzt will ich eine Funktion schreiben, die am Ende ein neues Element einfügt. Also ungefähr so:

    list a, n;
while(???){
   a = a.next;   (???)
}
a.next = n;

    Also das ist jetzt nur ein Auszug auf meienm Code, aber in Java hätte es so funktioniert. Probleme hier sind
    - in der Schleifenbedingung weiß ich nicht, wie ich das letzte Element "bemerke". In Java konnte ich if(a.next == null) abfrage, um das letzte zu erkennen. Hier scheint das nicht so zu gehn.

    - Und das (a = a.next) aus Java gibt in C auch eine Fehlermeldung.

    Ich weiß, dass ich keine Erfahrung mit Pointer habe, also wäre ich dankbar, wenn mir jemand helfen könnte.

    0
  • D

    Noskro schrieb:

    Und das (a = a.next) aus Java gibt in C auch eine Fehlermeldung.

    Ist ja auch ein Zeiger, also musst du mit a->next darauf zugreifen.

    Poste doch bitte mal exemplarisch deinen Code, mit dem du die Liste anlegen möchtest.

    0
  • N

    Also ich hab jetzt aus meinem Programm den betreffenden Teil rauskopiert, und der übersichtkeitshalber leicht modifiziert.
    Aber der Teil stellt genau das Problem dar, dass ich habe. Ich habe eine Struktur und will Elemente mit den Inhalten von 'a' bis 'z' erstellen.
    Natürlich geht es auch einfacher, indem ich immer ein Element hinzufüge, aber mein Problem beinhaltet, dass ich jedes mal am Ende der Liste ein Element hinzufügen muss.

    #include "stdafx.h"

struct list{
	list* next;
	char content;
}start;

void newelement(char c){
	list add;

	while(add.next != null){   //!!!!!!!!!!
	      add = add.next;      //!!!!!!!!!!
	}
	add.content = c;

}

int _tmain(int argc, _TCHAR* argv[]){

	for(char c = 'a'; c<= 'z'; c++)
		newelement(c);
	return 0;
}

    Die beiden Zeilen, die Probleme machen, sind glaube ich gut zu erkennen. Ich denk mir, dass die Abfrage gegebn 'null' so nicht geht, nur, dass ihr versteht was ich meine, habe ich auf Java-Hilfsmittel zurückgegriffen, anstatt die Bedingung leer zu lassen.

    0
  • D
     

    #define NULL 0

struct list{
    list* next;
    char content;
} *start;

void newelement(char c){

	// Zeiger zum traversieren
	list* current = start;

	// ans Ende der Liste laufen
    while(current->next != NULL)
	{
		current = current->next;
    }

	current->content = c;
}

int main(int argc, char* argv[]){

	// künstliche abbruchbedingung schaffen
	start->next = NULL;

    for(char c = 'a'; c<= 'z'; c++)
        newelement(c);
    return 0;
}

    In C/C++ zeigt ein ungültiger Zeiger nicht automatisch auf NULL, wie in Java. In ANSI C gibt es auch IMHO keine 'NULL'. Deswegen hab ich es selbst definiert und es explizit zugewiesen (in main).

    Dieser Code fügt aber keine neuen Elemente an, sondern ändert immer nur den Inhalt des letzten Elements.

    0

  • Noskro schrieb:

    Natürlich geht es auch einfacher, indem ich immer ein Element hinzufüge, aber mein Problem beinhaltet, dass ich jedes mal am Ende der Liste ein Element hinzufügen muss.

    Dafür würde sich die Unterscheidung in Liste und Node empfehlen, so dass Du die Liste fragen könntest, wer die letzte Node ist.

    Noskro schrieb:

    Die beiden Zeilen, die Probleme machen, sind glaube ich gut zu erkennen. Ich denk mir, dass die Abfrage gegebn 'null' so nicht geht, nur, dass ihr versteht was ich meine, habe ich auf Java-Hilfsmittel zurückgegriffen, anstatt die Bedingung leer zu lassen.

    In dem Code stecken viele Fehler, sowohl in Java als auch in C. Ich kommentiere mal ein wenig

    #include "stdafx.h"

struct list{
	list* next;
	char content;
}start;

void newelement(char c){
	list add;                                /* Diese Variable ist lokal, das heißt, nachdem Du sie mit add.content =.. beschrieben hast, verschwindet sie wieder.
                                                  C oder Java, was immer diese Funktion macht - es interessiert niemanden, sobald sie verlassen wird. */

	while(add.next != null){   //!!!!!!!!!!  /* Deine lokale Variable ist nicht initialisiert, also steht da Murks drin, das würde in Java
                                                  funktionieren, aber Du bist halt in C. Da steht nicht NULL in .next drin, sondern irgendwas. 
                                                  Der C-Compiler kann ja nicht wissen, dass Du da gerne eine NULL drin stehen hättest. */
	      add = add.next;      //!!!!!!!!!!  
	}
	add.content = c;
                                               /* An dieser Stelle wird die Variable add wieder vernichtet. */
}

int _tmain(int argc, _TCHAR* argv[]){

	for(char c = 'a'; c<= 'z'; c++)
		newelement(c);
	return 0;
}

    Willst Du Speicher haben, musst Du das auch in Java sagen. In C++ nehme man wie in Java 'new', in C sieh Dich nach malloc() um.

    Bitte beachte, dass Java "Referenzen" das gleiche sind wie in C Zeiger.
    Aus Java

    list

    wird in C/C++

    list *

    Schreibst in C/C++ nur 'list' hast das Objekt direkt in der Hand und keine Referenz darauf. Wenn Du in C++ echte Referenzen benutzt, ist das wieder etwas anderes (ungefähr das, Java verspricht, aber nicht hält, und vermutlich der Grund, warum man Pointer in Java dann "Referenz" genannt hat...).

    Willkommen im Dschungel ^^.

    struct List * MyList;

struct List * newelement(list * begin, char c)
{
  list * item = malloc( sizeof( struct list ) );

  if( begin )
  {
    while( begin->next )
      begin = begin->next;       // ->  hier wird mit Zeigern gearbeitet :-)

    begin->next = item;
  }

  item->next = NULL;          // Sorgt dafür, dass das Ende gefunden werden kann.

  return item;
}

int main(int argc, char * argv[])
{
  MyList = newelement( NULL, 'a' );       // Hier rächt sich der Designfehler, dass eine Liste etwas anderes als ein Element ist.

  for(char c = 'b'; c<= 'z'; c++)
    newelement(MyList, c);

  /* Sternchen */

  return 0;
}

    Der Code oben sollte Dein Problem lösen. Also den Segmentation Fault....
    In meinen Augen ist das Programm weiterhin fehlerhaft, denn nur, weil es funktioniert, ist es nicht richtig.

    Unterscheide Deine Datentypen besser, eine Liste ist kein Element der gleichen Liste.

    Im Dschungel gibt's leider auch keine Müllabfuhr, also entsorge Deinen Müll bitte selber.
    In C und C++ musst Du die Speicherverwaltung selber in die Hand nehmen: mit delete in C++ oder free() in C.
    Bei /* Sternchen */ sollte also noch eine Schleife rein, die Deinen Müll mit free() wieder entsorgt.

    0

  • DarthZiu schrieb:

    #define NULL 0

struct list{
    list* next;
    char content;
} *start;

int main(int argc, char* argv[]){
   
	// künstliche abbruchbedingung schaffen
	start->next = NULL;

    for(char c = 'a'; c<= 'z'; c++)
        newelement(c);
    return 0;
}

    In C/C++ zeigt ein ungültiger Zeiger nicht automatisch auf NULL, wie in Java. In ANSI C gibt es auch IMHO keine 'NULL'. Deswegen hab ich es selbst definiert und es explizit zugewiesen (in main).

    Dieser Code fügt aber keine neuen Elemente an, sondern ändert immer nur den Inhalt des letzten Elements.

    Die Umschreibung künstliche Abbruchbedingung gefällt mir... start ist nicht initialisiert, also führt "start->Next = NULL;" direkt mit der ersten Anweisung zum Abbruch des Programms.
    Aber gut, dass Du selber auf ungültige Zeiger hingewiesen hast... SCNR 😉

    0
  • D

    Xin schrieb:

    start ist nicht initialisiert, also führt "start->Next = NULL;" direkt mit der ersten Anweisung zum Abbruch des Programms.

    Hab ja nicht geschrieben, dass das so lauffähig ist. 🙂 Habs nur schnell hingeplottet.

    0

  • DarthZiu schrieb:

    Xin schrieb:

    start ist nicht initialisiert, also führt "start->Next = NULL;" direkt mit der ersten Anweisung zum Abbruch des Programms.

    Hab ja nicht geschrieben, dass das so lauffähig ist. 🙂 Habs nur schnell hingeplottet.

    Ich glaube, das verwirrt unseren C-Anfänger aber noch etwas, wenn er das ausprobiert.

    Mir fiel da noch was auf, dass die Noskros Gedanken vielleicht etwas zu entwirren hilft:

    Noskro schrieb:

    Und das (a = a.next) aus Java gibt in C auch eine Fehlermeldung.

    In der Liste steht als Datentyp für 'next' "list *". Du versuchst "list *" auf ein Element vom Typ "list" zu packen. Das sind unterschiedliche Datentypen!

    Das ist etwa so, als würdest Du einen Ort mit einem Straßenschild gleichsetzen. Das eine ist der Ort, das andere nur ein Zeiger, dass man da lang fahren muss. Es sind also unterschiedliche Objekte (in einem einen leben Leute, das andere steht alleine in der Landschaft rum) und unterschiedliche Datentypen (Ort, Zeiger auf Ort). Das passt eben nicht.
    Du willst Dich von Ort zu Ort hangeln (also von Referenz zu Referenz, weil Du willst ja nicht für jeden Test eine Million Leute umsiedeln um zu gucken, ob hinter diesem Ort noch einer wohnt - die Leute müssen ja dann auch umsiedeln, damit sie noch hinter dem Ort wohnen können, hinter den Du gucken willst 😉 )
    Statt die Orte einzeln in Dein Blickfeld umzusiedeln, guckst Du einfach zum 'nexten' Ort rüber.

    Du arbeitest also mit Zeigern (Ortschildern, "list *") statt mit Orten ("list").

    Das vielleicht als kleine Gedankenstütze, was den den kleinen Unterschied("*") da ausmacht... Pointer ersparen vielen Orten überflüssige Umsiedlungen. 😉

    Übrigens, wenn ich 'list' oder 'struct List' schrieb ist in C 'struct list' gemeint... ich schreibe meine Datentypen grundsätzlich groß und arbeite in C++, wo kein struct mehr erforderlich ist.

    0
Anmelden zum Antworten