Liste sortieren < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:59 Di 21.10.2014 | | Autor: | evinda |
Hallo!!!
Es wird eine einfach verbundene unsortierte Liste gegeben. Könntet ihr mir erklären, wie man die Technik von Insertion Sort anwenden kann, um die Liste zu sortieren?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo evinda!
Kannst du vielleicht näher erläutern, was genau dir unklar ist? Das Verfahren an sich oder ein einzelner Schritt? Das Verfahren ist sicherlich in deinen Vorlesungsunterlagen beschrieben, auf ![[]](/images/popup.gif) Wikipedia gibt es auch ein leicht zu verstehendes Beispiel.
Du hast deine ursprüngliche Liste L1, die von vorne nach hinten durchgegangen wird und für jedes Element die Position in der neuen (sortierten) Liste L2 bestimmt wird, indem L2 ebenfalls von vorne nach hinten durchgegangen wird und mit dem aktuellen einzusortierenden Wert verglichen wird. L2 wächst dabei bei jeder Iteration um 1 Element an. D.h. du hast anfangs nur das erste Element aus Liste L1 drin, nach dem ersten Durchlauf wird das 2. Element von L1 einsortiert. Entweder vor oder nach dem 1. Eintrag, je nach dem ob es größer oder kleiner ist und ob du auf- oder absteigend sortierst. Durch die einfache Verkettung musst du allerdings aufpassen, wie das neue Element eingefügt wird, damit du dir deine Liste nicht zerschießt. Kannst dir ja mal überlegen, wie man das machen sollte und dich melden, falls es dir nicht klar ist.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:06 Mi 22.10.2014 | | Autor: | evinda |
Also wir wollen das letzte Element von [mm] L_1 [/mm] bei der ersten Position von [mm] L_2 [/mm] platzieren, das vorletzte Element von [mm] L_1 [/mm] bei der zweiten Position von [mm] L_2 [/mm] und so weiter?
Ich habe folgendes bisher versucht:
pointer [mm] q=L_1,p=L_2;
[/mm]
while (q!=NULL)
q=q->next;
p=q;
Nach diesen Befehlen, enthält [mm] L_2, [/mm] bei der ersten Position, das letzte Element von [mm] L_1, [/mm] oder nicht?
Wie kann ich weitermachen? [mm] :\
[/mm]
|
|
|
| |
|
Das ist ja jetzt ne andere Frage. Damit ist Insertion Sort wohl verstanden und erledigt?
Zu der neuen Frage möchte ich gleich mal vorweg nehmen, dass meine C-Kenntnisse etwas eingestaubt sind und bitte eventuelle Syntaxfehler zu verzeihen. Ich setze mal deinen Code in Code-Tags, Klammern hab ich ergänzt.
| 1: | pointer q=L1, p=L2;
| | 2: | while (q!=NULL) {
| | 3: | q=q->next;
| | 4: | }
| | 5: | p=q;
|
Müsste hier in Zeile 5 nicht p->next = q stehen? Wie gesagt, verstaubte C-Kenntnisse...
Ja, damit kommst du zum letzten Objekt der Liste L1. Du musst nun anschließend den Zeiger auf das letzte Objekt auf NULL setzen und deine Schleife erneut durchlaufen. Das realisierst du entweder mit einer weiteren while-Schleife drumherum oder mit einer passenden for-Schleife. Dabei wird allerdings deine Liste L1 zerstört und es ist recht ineffizient.
Ich würde das anders machen, indem ich L2 von hinten aufbaue. Dazu brauchst du aber eine temporäre Variable, dafür reicht dir auch nur ein Schleifendurchlauf. Hier mal dein Code mit Hinweisen, wie das funktioniert:
| 1: | pointer q=L1, p=L2;
| | 2: | while (q!=NULL) {
| | 3: | // 1. Speichere p temporär
| | 4: |
| | 5: | // 2. Lass p auf aktuelles Objekt in Liste L1 zeigen
| | 6: |
| | 7: | // 3. Verknüpfe p mit Liste L2 (mittels temporärer Variable)
| | 8: |
| | 9: | q=q->next;
| | 10: | }
|
Da nicht ersichtlich ist, ob es irgendwelche Einschränkungen bei der Umsetzung gibt, musst du entscheiden, welches Verfahren du anwendest.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:25 Fr 24.10.2014 | | Autor: | evinda |
Der Professor hat uns gesagt, dass wir keine zweite Liste benutzen sollen. Wie kann ich die Elemente der gegebenen Liste sortieren, ohne eine neue zu benutzen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Di 28.10.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
