www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Algorithmen und Datenstrukturen" - Liste sortieren
Liste sortieren < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Liste sortieren: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Liste sortieren: Antwort
Status: (Antwort) fertig Status 
Datum: 12:04 Di 21.10.2014
Autor: sijuherm

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 []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.

Bezug
                
Bezug
Liste sortieren: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]


Bezug
                        
Bezug
Liste sortieren: Antwort
Status: (Antwort) fertig Status 
Datum: 11:07 Do 23.10.2014
Autor: sijuherm

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.

Bezug
                                
Bezug
Liste sortieren: Frage (überfällig)
Status: (Frage) überfällig Status 
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?

Bezug
                                        
Bezug
Liste sortieren: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:20 Di 28.10.2014
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de