einfach verkettet listen

[hame]

hallo,

kann mir jemand von euch ein gutes buch bzw ein gutes tutorial zum thema "verkettete liste" empfehlen, wo der ablauf bzw das schema dargestellt wird. Hilfreich wäre auch ein paar beispiele.

danke schonmal im vorraus.

[VaNaTiC]

Guckst Du hier: Liste (Datenstruktur) ? Wikipedia

Das sollte für eine einfach verkettete Liste reichen.

Bücher gibts übrigens verdammt viele, aber ich kenne keins, was nur Listen behandelt. Es geht vielmehr um Algorithmen, Datenstrukturen und später dann Automaten, ...

Meine 2 alten Bücher aus der Sekundarstufe 2 waren von Klett. Und die sind auch heute noch prima

Bearbeitet 11. Dezember 2009 von VaNaTiC

[konsti4u]

Verkettete Listen und andere Objekte macht man in C mit structs, structs sind eig. Verbunddatentypen, naja hier ein Beispiel.

Verkettete Listen bestehen ja eig nur aus Listenelementen (Nodes) die immer auf den nächsten zeigen. Wenn ein Node auf keinen zeigt, so hat man das Ende der Liste erreicht.

Node -> Node -> Node -> NULL

Bsp für ein Listenelement welches eine Zahl speichert, und einen Zeiger auf das nächste Listenelement.

struct node {

	int data;

	struct node* next;

};


/* Head-Zeiger IMMER auf das erste Element der Liste */

struct node* head = NULL;


int insertElement(int data) {


        struct node *neu;


	/* Erstelle das zum Einfügen bereite neue Element */

        neu =(struct node*)malloc(sizeof(struct node));    

        if(neu == NULL){

			perror("Malloc failed");

			return -2;

	}

	neu->next=NULL;	

 	neu->data = data;



/* Falls noch kein Element da, wird neu das erste Element */

        if(head == NULL) {

                head=neu;

                return data;

        }


/*Ansonsten füge es ganz hinten ein */

/* Alle Werte durchgehen und ggf einfügen. */  

	pt = head;  /*Laufzeiger zeigt auf Kopf */

        while(pt->next != NULL)   pt = pt.next;


         pt.next = neu;

         return data;

}

//Zur Schreibweise:

pt->next ist das gleiche wie: (*pt).next

Bearbeitet 11. Dezember 2009 von konsti4u

[TDM]

Google hat mich angespuckt.

Artikel | Einfach verkettete Listen in C

[hame]

was bedeutet: ->? hab damit noch nicht gearbeitet. ist das so etawas wie ein zeiger?

haha. ich sollte vlt. vorher lesen und dann schreiben ^^

Bearbeitet 11. Dezember 2009 von hame

[hame]

@konsti4u, danke!

hat er mir für den Anfang sehr viel fürs Verständis von verkettete listen gebracht. ich hab dann nur noch eine frage wenn ich eine liste sortieren soll, muss ich dann immer über jedes element gehn und dann es aussortieren und dann wieder neu sortieren? z.b wenn ich eine liste nach ungeraden und gerade zahlen sortiere?

[konsti4u]

Also eine sortierte Liste ist nicht schwer, du musst einfach die Elemente von Anfang an sortiert einfügen :-)

z.B: Aufsteigend sortierte Liste:

1. Erstes Element immer einfügen (head auf neu)

neu->NULL

2. Falls das neue Element kleiner als das erste, dann lasse neu auf erste zeigen und das neue das erste werden (head auf neu)

neu->alt_neu->NULL

3. Ansonsten gehe durch die Liste bis man NULL erreicht und prüfe jeweils ob das neue Element < nächste Element, wenn ja, dann tu das neue element auf das nächste zeigen und das derzeitige element auf das neue.

derzeitig->neu->next

4. Man muss es ganz hinten anfügen

letzte->neu->NULL

Falls Probleme kann ich auch dafür ein Code-schnippsel schreiben, oder am besten frag erst :-)

[hame]

danke für den tipp erstmal.

also wir schreiben ende januar eine klausur in c und da werden halt höchstwahrscheinlich listen dran kommen, es ist halt so das wir vorgegebene struktur haben und eine liste die z.B zahlen enthält und und diese liste sollen wir dann absuchen und eine in eine neue liste kopieren z.b in die erste hälfte die geraden und in der zweiten hälfte die ungerade zahlen. da wollt ich halt wissen wie man das am besten angeht da ich mich mit listen noch nicht so viel auseinander gesetzt haben. aber ich werde es erstmal alleine versuchen die aufgaben zu lösen. wenn ich dann hilfe brauche wende ich mich gerne wieder dem forum ^^.