Problem mit linearer Liste (sortierter Eintrag der Werte)
-
Hallo zusammen,
ich stehe vor folgendem Problem. Im Moment trage ich Zahlen so wie sie in einer Dateistehen in eine Liste ein. Das funktioniert auch prima. Nun wollte ich die Zahlen so in die Liste eintragen, dass sie am Ende sor´tiert in der Liste stehen. Wenn man am Ende die Liste durchläuft und diese ausliest und ausgibt sollen die Zahllen steigend sortíert sein. Allerdings bekomme ich es absolut nicht hin. Wie gesagt, das unsortierte Eintragen geht klasse, aber ich weiß nicht, ich die Werte sortiert in die Liste eintragen kann, also wie ich überprüfen kann, ob der gerade einzufügende Wert kleiner ist,als ein bereits in der Liste eingetragener Wert, weil er dann ja vor diesem eingefügt werden soll. Meinen bisherigen Code habe ich unten mal angehängt.
Ich habe in dem Code unten mal versucht an der Stelle, an der festgestellt wird, dass der gerade einzufügende Wert größer als der bereits in der liste eingetragene Wert ist, eine Meldung auszugeben. Leider geht das nur wenn ich z.B. 1 4 6 als einzutragene Werte habe, weil es erst anspricht,w enn zwischen der 4 (bereits eingetragen) und der 6 (soll gerade eingetragen werden) unterschieden wird. Ich hoffe, dass ich mein Problem einigermaßen beschrieben habe. Wäre toll, wenn mir jemand helfen könnte.void Liste(FILE *datei) { long int input; struct LISTE *anfang; struct LISTE *zeiger; anfang NULL; fseek( datei, 0, SEEK_SET ); while(!feof(datei)) { fscanf(datei, "%i", &input); if(anfang == NULL) { anfang= malloc(sizeof(LISTE)); anfang->next= NULL; zeiger= anfang; zeiger-> value= input; zeiger-> next= NULL; } else { zeiger= anfang; while(zeiger-> next != NULL && zeiger != NULL) { if(input > zeiger->value) { zeiger= zeiger-> next; printf("test\n"); fclose(datei); ausgabe(anfang); getchar(); exit(0);} } zeiger-> next= malloc(sizeof(*zeiger)); zeiger= zeiger-> next; } zeiger-> value= input; zeiger-> next= NULL; } fclose(datei); ausgabe(anfang); }
-
1. ist das keine lineare Liste, sondern eine verkettete Liste.
2. hab ich das Gefühl, dass du es noch nicht so ganz verstanden hast.Vielleicht solltest du dir das mal bildlich vorstellen. Du hast also drei Werte 1, 6 und 4 (z. B. in dieser Reihenfolge) in deiner Datei stehen. So nun liest du den ersten Wert ein und beginnst deine Liste (ein Listeneintrag hat die Eigenschaft value und die Eigenschaft next; der Listeneintrag ist unten durch [] dargestellt und die Eigenschaften sind durch einen | getrennt):
anfang -> [1|NULL]Nun gehts weiter beim nächsten Wert in der Datei, also bei 6:
anfang -> [1|NULL] [6|NULL] <--- zeigerNun musst du noch die 6 in deine Liste bringen. Du stellst fest, dass 6 größer als 1 ist und dass 1 das letzte Element der Liste ist, also hängst du es hinten dran (die Eigenschaft next vom ersten Listenelement zeigt nun auf das neue Listenelement mit value 6):
anfang -> [1|next] \---> [6|NULL] <--- zeigerAls letztes kommt nun die 4 als Wert:
anfang -> [1|next] \----> [6|NULL] [4|NULL] <--- zeigerNun musst du feststellen wo die 4 hingehört. Ganz klar zwischen 1 und 6 ;). Der erste Schritt ist, dass du die 6 hinter die 4 hängst:
anfang -> [1|next] [4|next] <--- zeiger \------------\------> [6|NULL]Was auffällt ist, dass nun 1 und 4 auf 6 zeigen. Aber 1 soll ja auf 4 zeigen, also machen wir das auch so ;):
anfang -> [1|next] \------> [4|next] <--- zeiger \-----> [6|NULL]Ich hoffe das war so verständlich.
Also mach dir nochmal Gedanken drüber und überarbeite deinen Quellcode.
-
Hallo zusammen,
vielen Dank erst einmal für die Hilfe. Ich habe mich selbst nochmal intensiv damit beschäftigt. Ich meine, ich bin schon ein Stück weiter. Leider bin ich mal wieder an einer Stelle angekommen, an der ich nicht weiter komme. Ich habe einer Version, die alles einfach hinten an die Liste anhängt. Das funktioniert auch. Mit der Unten stehenden Version, versuche ich einen Wert mitten in die Liste einzutragen oder am Anfang. Wenn in der Liste z.B. 1 2 3 5 6 7 steht und die 4 eingetragen werden soll, soll die ja vor die fünf. Leider habe ich nun Das Problem, dass das auch fast klappt. Wenn ich die wieder ausgebe, erhalte ich 1 2 4 -84215... 6 7. Das einfügen klappt ja irgendwie, aber die pointer auf das nächste, hier 5. Element stimmt irgendwie noch nicht.
Sieht vielleicht jemand wo der Fehler ist?Grüße
typedef struct LISTE{ long int value; struct LISTE *next; }LISTE; void losgehts(FILE *in) { long int num struct LISTE *erst; struct LISTE *zeig; struct LISTE *neu_zeig; erst= NULL; fseek( in, 0, SEEK_SET ); while(!feof(in)) { fscanf(in, "%i", &num); if(erst == NULL) { erst= malloc(sizeof(LISTE)); zeig= erst; zeig-> value= num; zeig-> next= NULL; } else { zeig= erst; while(zeig->next != NULL && num > zeig->next->value) zeig= zeig->next; if(zeig->next !=NULL) { neu_zeig= malloc(sizeof(LISTE)); neuzeig->next= zeig->next; zeig->next=neu_zeig; } if(zeig->next == NULL) { zeig-> next= malloc(sizeof(*zeig)); zeig= zeig->next; zeig-> value= num; zeig-> next= NULL; } } zeig-> value= num; } fclose(in); ausgabe(erst); }
-
Soweit ich sehe (aber es ist schon ein bisschen spät
) hast du lediglich vergessen im
if(zeig->next!=NULL)
den Wert zu setzen.Du biegst die Zeiger zwar richtig, aber kein
neu_zeig->value=num;
ist zu finden...
-
Hallo,
Wow, ich glaube das wars. Beschwören möchte ich das um diese Uhrzeit nicht mehr, aber es scheint so. Nur wenn ich gleich am Anfang in der Liste was eintragen will, aslo vor dem 1. Listenelement, dann macht es murx, dann bekomm ich z.B. 1 0 2 3 4 anstatt 0 1 2 3 4. Mal sehen, das dürfte aber auch nciht mehr viel sein.
Vielen Dank und ein frohes Fest wünsche ich.
-
ABeginner schrieb:
Nur wenn ich gleich am Anfang in der Liste was eintragen will, aslo vor dem 1. Listenelement
Klar. Dein Algo beginnt ja bei erst->next->value mit dem Suchen.
Folglich wird das erste Element immer übersprungen...