✔ Sortierte Eingabe in doppelt Verkettete Liste einlesen.

D

Davicito

Erfahrenes Mitglied
Hab in den letzten Themen "wie funktionieren doppelt Verkettete Liste": http://www.tutorials.de/c-c/375840-wie-funktionieren-doppelt-verkettete-liste.html

eine nun funktionierende Liste erstellt bekommen.

Meine Frage ist, wie kann ich nun die Strings sortiert in die Liste füllen.
Mein Ansatz dazu sieht folgendermaßen aus:

Java: 
node* suche(node* list, void* pvalue, bool (*cmp)(void*, void*))
{
	node* vorne = list -> right ;
	node* hinten = vorne -> right ;
	while(vorne != NULL)
	{
		if (cmp(vorne -> content, pvalue) == true)
		{	
			if (hinten == NULL)
			{	
				return vorne ;
			}
			else
			{
				// In der Liste weitergehen
				vorne = hinten ;
				hinten = hinten -> right ;
			}
		}
		else
		{
			return vorne ;
		}
	} ;
	return NULL ;
}



node* sort(node* list, void* neuer_String, void* (*set)(void*), int counter, bool (*cmp)(void*, void*))
{
	node* neu_Elem = (node*) malloc(sizeof(node));
	// Überprüfen, ob Speicher übergeben worden ist	
	if(neu_Elem == NULL)
	{
		printf("\n Listenelement konnte nicht angelegt werden, da kein Speicher vorhanden ist! \n");
		exit(1);
	}
	//String / Wort an die Funktion "copySting" übergeben, um Speicher für den Zeiger "content" zu besorgen
	void* tmpchar = set(neuer_String);
	node* vor = suche(list, neuer_String, cmp);
	
	neu_Elem -> content    = tmpchar;
	neu_Elem -> lineCounter = counter;

        // Was wird hier genau gemacht?
	neu_Elem -> left       = list;                             
	neu_Elem -> right      = list -> right;		
	list -> right-> left   = neu_Elem;  
	list -> right          = neu_Elem;
	
	return neu_Elem;
}

Das funktionier leider nur nicht!! und ich bin schon mehr als ratlos, weil ich immer noch nicht verstanden habe, wie ich die Zeiger meiner Liste neu setzten muss, da ich die Zeilen 47 -50 nicht verstehe und diese aus dem Beispiel : http://perlgeek.de/de/artikel/doppelt-verkettete-listen so übernommen habe.

Bei meiner anhaengfunktion klappt das ja. Müsste doch bei meiner sortierungsfunkzion genauso klappen. Oder?

Gruß.
 
Zuletzt bearbeitet:
Hi

zuerst ein prinzipieller Fehler:
Die Vergleichsfunktion, die du bei suche und sort übergibst, hat ein bool als Returnwert.
Für Suchen würde es schon reichen (ist gleich/ist nicht gleich)
Für das Sortieren musst du aber wissen, ob String 1 zuerst kommt/String 2 zeurst kommt/beide gleich sind.
Drei Werte.
zB: Irgendwas kleiner 0 (wie -1 zB.) bedeutet String 1 vor String 2
Irgendwas größer 0 bedeutet String 2 vor String 1
0 bedeutet, dass sie gleich sind -> egal, was zuerst kommt.
Da wird ein bool nicht mehr reichen. Nimm int.
Die Funktion strcmp gibt übrigens gleich passende Werte nach dem Schema oben zurück (zum Stringvergleich).

Dann die Suche...gleich die ersten zwei Zeilen kommen mir seltsam vor.
Warum ist vorne right?

Zum Zeitpunkt von suche muss die Liste noch nicht sortiert sein, oder?
Dann:
-Vergleichst du zuerst list mit pvalue.
-Gehst dann immer weiter nach links (und vergleichst jedes Element), bis du bei NULL ankommst.
-Gehst dann von list aus immer weiter nach rechts (und vergleichst jedes Element), bis du bei NULL ankommst.

C++: 
node* suche(node* list, void* pvalue, int (*cmp)(void*, void*))
{
    node* aktuell;
    aktuell=list;
    while(aktuell != NULL)
    {
        if (cmp(aktuell-> content, pvalue) == true) return aktuell;
        aktuell=aktuell->left;
    }
    aktuell=list;
    while(aktuell != NULL)
    {
        if (cmp(aktuell-> content, pvalue) == true) return aktuell;
        aktuell=aktuell->right;
    }
    return NULL ;
}

Wenn die Liste immer sortiert ist, kannst du dir das zum Suchen zu Nutze machen:
-Je nachdem, ob list größer/kleiner als der Suchwert gewertet wird, musst du nur noch links/rechts suchen
-Wenn zB list kleiner als pvalue ist, musst du nur immer right gehen.
-Solltest du dabei auf pvalue kommen: gefunden
-Sollte zuerst ein Wert auftauchen, der größer als pvalue ist, findest du es sicher nicht mehr und kannst aufhören.
-Die letzten drei Zeilen gelten natürlcih auch umgekehrt (größer-kleiner umgedreht)

C++: 
node* suche(node* list, void* pvalue, int (*cmp)(void*, void*))
{
    int i;
    if(list==NULL)return NULL;
    i=cmp(list->content,pvalue);

    if(i==0)return list;
    else if (i<0)
    {
        while(list->right!=NULL)
        {
            list=list->right;
            i=cmp(list->content,pvalue);
            if(i==0)return list;
            else if (i>0)return NULL;
        }
    }
    else if (i>0)
    {
        while(list->left!=NULL)
        {
            list=list->left;
            i=cmp(list->content,pvalue);
            if(i==0)return list;
            else if (i<0)return NULL;
        }
    }

    return NULL ;
}

Zur sort-Funktion...wo nimmst du nur immer diesen counter her?
Jetzt gibts sogar noch einen lineCOunter...und eine counter-Variable, die übergeben wird...
Und sollte das nicht eher sorted_add heißen?
Du willst ja was einfügen...

Prinzip:
Vergleich list mit dem neuen Wert.
Wenn gleich: Einfügen nach list.
Wenn list kleiner als Neu
{
Immer weiter nach rechts gehen
Wenn du einer Wert größer als Neu findest: Vor diesem einfügen
Wenn du auf NULL triffst: Als letztes Element anhängen
}
Wenn list größer als neu
{
Immer weiter nach links gehen
Wenn du einer Wert kleiner als Neu findest: Nach diesem einfügen
Wenn du auf NULL triffst: Als erstes Element einfügen
}

Gruß
 
Zuletzt bearbeitet:
Hi ... der counter dient zum Zeilenzählen einer textdatei und hängt das dem betreffenden wort der Liste an

Java: 
char buffer[SIZE];
	FILE* file;
	char splitt[] = ",;.:!?><#'’+*~´`^?[]{}()/\%&$§=|öäüÖÜÄß\n "; //Definition der Trennzeichen	
	char* wort;
	int counter = 0;
	
	
	// Überprüfung, ob eine Textdatei übergeben wurde.
	if(argc > 1 && (file = fopen(argv[1], "r")) != NULL)
	{
		// Gesamten Textinhalt auslesen, bis zum Textendezeichen.
		while(fgets(buffer, SIZE, file) != NULL)
		{					
			counter++;
				
			// Wörter einlesen	    		
			wort = strtok(buffer, splitt);
			
			// Wörter solange einlesen, wie Wörter über Buffer übergeben 	werden.			
			while(wort != NULL)
			{			    	
				//anhaengen(aktl_Elem, wort, copyString, counter);//, copyZahl);				
				sort(aktl_Elem, wort, copyString, counter, compare);	
				wort = strtok(NULL, splitt);		    					
			}
			//printf("%i ", counter);			    		
		}
		fclose(file);
	}

Aber was ich nicht verstehe ist:
Java: 
...
neu_Elem -> left       = list;    // Wird hier eine Liste an Zeiger lings angehängt?
neu_Elem -> right      = list -> right;		// Dann Zeiger rechts der Liste  an einen Zeiger rechts? 
list -> right-> left   = neu_Elem;  // ...neues Element an die Zeiger rechts und llinks verwiesen?
list -> right          = neu_Elem;  //und dann neues Element an Zeiger rechts angehängt?
...

...ich verstehe nur Bahnhof!! ^^ ich möchte diese Zeilenanweisungen verstehen können, was da im Einzelen genau passiert.

Ich habe einen Struct meiner Liste in einer Headerdatei definiert, welches auf sich selbst zeigt. Das heißt also, dass es kein NULL rechts vom letzten Element und auch kein NULL links vom ersten Element gibt:

Java: 
// aus der Liste.h
typedef struct node
{
	struct node* right; // Zeiger auf das Nachfolgerelement
	struct node* left;  // Zeiger auf das Vorgängerelement
	void* content;      // Für den Dateninhalt
	int lineCounter;	
} node;
...
//aus der Liste.c
node* init_Liste()
{
	node* n = (node*) malloc(sizeof(node));
	n -> right   = n;
	n -> left    = n;
	n -> content = NULL;
	n -> lineCounter = 0;
		
	return n;
}

Liebe Grüße.
 
Zuletzt bearbeitet:
Also eine rotierende Liste...bei der ist eben dann Schluss, wenn du wieder am Anfangselement ankommst.

Und die Erklärung zu den vier Codezeilen hab ich schon oben geschrieben
 
genau ^^.

Ich kann Deine Erklärung leider nicht herauslesen! Kannst Du mir das vielleicht nochmal etwas anders schildern, weil ich immer nur größer oder kleiner oder gleich irgendetwas lese. aber das hat ja etwas mit der Sortierung zu tun. Ich hab ja auch eine auskommentierte Funktion anhängen, die die gleichen Zeilenanweisungen besitzt, die ich nicht verstehe. und da wird ja nichts sortiert. sondern nur hinten angefühgt.

Wenn Du so lieb wärest, mir das Zeile für Zeile zu erklären, was da genau passiert, wäre ich Dir sehr dankbar.

Hier nochmal der Auszug
Java: 
...
neu_Elem -> left       = list;    // Wird hier eine Liste an Zeiger lings angehängt?
neu_Elem -> right      = list -> right;     // Dann Zeiger rechts der Liste  an einen Zeiger rechts? 
list -> right-> left   = neu_Elem;  // ...neues Element an die Zeiger rechts und llinks verwiesen?
list -> right          = neu_Elem;  //und dann neues Element an Zeiger rechts angehängt?
...
 
So...nicht lachen, hab kein ordentliches Grafikprogramm.
Bilder sind der Reihenfolge nach durchnummeriert. 1 bis 4.
Irgendwie sind die Bilder verkehrt drin, das letzte unten ist also Nummer 1.
 

Anhänge

  • 1.JPG
    1.JPG
    16 KB · Aufrufe: 7
  • 2.JPG
    2.JPG
    12,7 KB · Aufrufe: 6
  • 3.JPG
    3.JPG
    11,8 KB · Aufrufe: 8
  • 4.JPG
    4.JPG
    11,4 KB · Aufrufe: 9
Ah das hat mir schon sehr weiter geholfen!
also mit anderen Worten: list ist immer der Kopf meiner gesamtliste den ich ansprechen muss um meine Zeiger für ein neues Element anzuhängen.

Java: 
1. neu -> left = list;            //bedeutet, das zuerst mein linker Zeiger von "neu" auf den Listenkopf gesetzt wird und dann
2. neu -> right = list -> right;  //der linke Zeiger auf die rechte Seite meines listenkopfes zeigt.
3. list -> right -> left = neu;   //Danach bekommt das neue Element den Zeiger von der Liste ausgehend, recht, den Zeiger  auf das neue Element gesetzt.
4. list -> right = neu;           //Und zu guter Letzt auch von der Liste aus, den Zeiger rechts auf das neue Element gesetzt.

...also ich muss schon sagen... hut ab vor den Menschen, die das auf Anhieb verstehen. Also alleine wäre ich nicht darauf gekommen!

Vielen Dank Dir nochmal******!

Liebe Grüße.
 
Zuletzt bearbeitet:
Davicito hat gesagt.:
also mit anderen Worten: list ist immer der Kopf meiner gesamtliste den ich ansprechen muss um meine Zeiger für ein neues Element anzuhängen.
Zum Vergrößern anklicken....
Naja, was ist denn bei einer rotierenden Liste der Kopf?
(Hat ein Kreis einen Anfang?)
list ist das Element, das vor dem neuen sein soll.
Das neue wird also nach list eingefügt.
Welches von den dreien das ist, kannst du mit ein paar list=list->right bzw. left selber beeinflussen.

Davicito hat gesagt.:
1. neu -> left = list; bedeutet, das zuerst mein linker Zeiger von "neu" auf den Listenkopf gesetzt wird und dann
2. neu -> right = list -> right; der linke Zeiger auf die rechte Seite meines listenkopfes zeigt.
3. list -> right -> left = neu; Danach bekommt das neue Element den Zeiger von der Liste ausgehend, recht, den
Zeiger auf das neue Element gesetzt.
4. list -> right = neu; Und zu guter Letzt auch von der Liste aus, den Zeiger rechts auf das neue Element gesetzt.
Zum Vergrößern anklicken....

1 und 2: Ja, zuerst muss das Neue Element einmal wissen, was in Zukunft links/rechts von ihm sein wird (wenn fertig eingefügt ist).
Da neu zwischen list und list->right reinkommen soll, ist list von neu aus gesehen links und das, was zurzeit list->right ist, ist auch rechts von neu.

3: Jetzt weiß neu zwar über seine Nachbarn bescheid, die wissen aber noch nichts von ihm.
Deshalb kommt man mit list->right weiterhin zu dem, was vorher schon right war, und noch nicht zu neu.
Diesem list->right wird jetzt gesagt, das links nicht mehr list, sondern neu ist.

4: Und zu guter Letzt teilt man list auch noch mit, dass rechts jetzt neu ist.

Von list aus immer rechts weiter ist jetzt zuerst neu und erst dann das "alte rechte".
Von dort wieder links zurück kommt man zuerst zu neu, dann wieder zu list.
So solls ja auch sein.

Gruß
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück