Du bist nicht angemeldet.

Werbeanzeige

1

09.07.2017, 16:22

Insertion-Sort Schwierigkeiten!

Hallo Leute,

ich stecke gerade was, alphabetisch sortiert einfügen in eine einfach verkettete Liste, angeht, recht in der Klemme und zwar:

Wir haben eine Aufgabenstellung von der Übungsleitung bekommen, wo wir Buchstabe für Buchstabe in eine Konsole eingeben und diese Buchstaben sollen in eine Leere Liste von Anfang an, alphabetisch sortiert in die Liste eingefügt werden und ich komme da einfach nicht weiter :(

Ich muss das "Insert" morgen abgeben und ich habe es die ganze Zeit versucht, aber iwie will es nicht in meinen Kopf. :dash: :dash:

Ich erbitte um Eure Hilfe ^^

Das ist mein bislang geschriebener Code in Delphi:

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//first = ^TNode; //Zeiger auf einen Knoten(TNode);
//value = der zuvergleichende und anschließend richtig einsortierte Buchstabe
procedure insert(var first: PNode; Value: string);
var
  newNode, tmp, current: PNode;
begin
  if first = nil then
    add(first, Value)    //a

  else
  begin
    add(first, Value); //b-->a

    // code-logic...
    while (current <> nil) and (Value < current^.Value) do
    begin
      // ich muss mir den vorigen Zeiger auch merken!
      tmp := newNode;
      newNode^.Next := current^.Next;
      current^.Next := tmp;
    end;
  end;
end;


Liebe Grüße

JP

P.s "add(..)" fügt ein Element ganz vorne an die Liste an!
und es wird zwar ein "string" übergeben, aber es kommen immer nur Buchstaben rein!

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »JungleProgger« (09.07.2017, 16:43)


TrommlBomml

Community-Fossil

Beiträge: 2 143

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

2

09.07.2017, 16:58

Wenn ich deinen Code richtig verstehe, hast du schon in Zeile 12 ein Problem: Du fügst im else-Zweig direkt ein Element an, das ist falsch. Du musst im Else-Zweig vor dem ersten Element, was größer gleich ist, ein neuen Node erzeugen und zwischen deinem aktuellen nächsten Element einfügen, das muss wohl in dem Bereich 18-20 passieren :)

Tobiking

1x Rätselkönig

  • Private Nachricht senden

3

09.07.2017, 17:04

Du machst es dir vermutlich schwerer als es sein muss. Du fügst dein Element vorne ein und versuchst es so lange zu verschieben bis es passt. Warum suchst du nicht einfach die Stelle an die das Element muss und fügst es genau da an?

Und dabei machst du es dir einfacher wenn du in der Bedingung nicht current.value anschaust, sondern current.next.value. Die Bedingung ist dann nämlich ein Element früher nicht mehr erfüllt und du hast kein Problem mehr dir das vorherige Element zu merken.

4

09.07.2017, 17:06

Hmm, also ich sage nur kurz was ich mit dem Code versuchen will:

Standardmäßig werden alle neuen Elemente ERSTMAL ganz vorne angehängt, egal ob < oder >.

Dann ab dem 2.Item geht das vergleichen und das dazugehörige Swapen erst los.

Und Du meinst, dass das so kein guter Weg ist?

5

09.07.2017, 17:09

@Tobiking

Also meinst du sowas:

Quellcode

1
2
3
4
current := first;

while current^.Next^.Value < übergeben_value do
  current := current^.Next;


Meinst du das so?? :O

BlueCobold

Community-Fossil

Beiträge: 10 859

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

6

09.07.2017, 17:12

Warum suchst du nicht einfach die Stelle an die das Element muss und fügst es genau da an?
So sollte es bei einem Insertion-Sort auch sein. Sonst ist es kein Insertion-Sort, sondern ein Insert-and-Sort, was irgendwie den Zweck verfehlt. Allerdings ist ein Insertion-Sort auf einer linked-List auch ziemlicher Käse, denn eigentlich würde man ja möglichst Binary Search nutzen, um die Einfügeposition möglichst effizient zu finden und das geht bei einer linked-List nicht.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

7

09.07.2017, 17:16

@Tobiking

Kannst du pseudo-Code posten, irgendwie habe ich einen Brett vor dem Kopf ://

Tobiking

1x Rätselkönig

  • Private Nachricht senden

8

09.07.2017, 17:48

@Tobiking

Also meinst du sowas:

Quellcode

1
2
3
4
current := first;

while current^.Next^.Value < übergeben_value do
  current := current^.Next;


Meinst du das so?? :O

Ja, wobei du natürlich erst prüfen musst ob es current.Next auch gibt bevor du auf Value zugreifst.

Nach der Schleife ist dann in current das Element an das dein neues Element angehängt werden muss.

9

09.07.2017, 18:10

Hmm ok ich versuche das mal jetzt so:

Achso und die Liste muss alphabetisch aufsteigend sortiert sein, also A oben und Z unten, halt egal wie ich es in der Konsole eingebe das muss so sortiert rauskommen^^

10

09.07.2017, 18:58

Ich verstehe es einfach nicht... :dash: :dash: :dash:

Der Code will klappt manchmal ja, manchmal nein :((

Bitte Bitte Hilfe, weil ich sonst durchfalle wenn der nicht geht morgen und ich aber den vorzeigen muss :(

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
procedure insert(var First: PNode; toCompare: string);
  var
    tmp, nextBuffer, current: PNode;
  begin
    if First = nil then
      add(First, toCompare)    //d-->b-->

    else
    begin
      current := First;

      {
        * Laufe durch alle Knoten, solange die Bedingung: (Value > current^.Value) gilt
        * Erstelle einen Neuen Knoten
        * Dann lasse current^.Next auf new zeigen und new^.Next auf current^.Next zeigen
      }

      {Laufe durch alle Knoten, solange die Bedingung: (Value(d) > current^.Value(b)) gilt}
      while (current^.Next <> nil) and (current^.Next^.Value < toCompare) do
        current := current^.Next;

      {Erstelle einen Neuen Knoten}
      New(tmp);
      tmp^.Value := toCompare;
      tmp^.Next := nil;

      if First^.Next = nil then
      begin
        tmp^.Next := current;
        current^.Next := nil;
        First := tmp;
      end

      else
      begin
        if current^.Value > toCompare then
        begin
          current^.Next := tmp;
        end

        else
        begin
          nextBuffer := current^.Next;
          current^.Next := tmp;
          tmp^.Next := nextBuffer;
          //first := current;
        end;
      end;
    end;
  end;


P.s Sobald ich irgendwie mehr als 6 Elemente habe, verkackt es :wacko: :wacko:

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »JungleProgger« (09.07.2017, 19:04)


Werbeanzeige