Doppelt verkettete Liste sortieren?

[Fragender_Johnny]

Wir haben hier das Problem, dass wir doppelt verkettete Liste aus Objekte, welchen CD-Alben darstellen sollen, und diese nach ihrem Ranking (int Wert) sortieren sollen. Problem ist, dass das vertauschen, die Liste zerstört.

So sieht unser Code bis jetzt aus:

 public void SORTBY_RATING()
  {
    Album album1 = head;
    Album album2 = album1.next;
    Album temp;
    boolean getauscht;
    
    if(album1.next==null)
    {
      System.out.println("Keine Sortierung, da nur ein Album !");
      return;
    }

   while(album2!=null)
   {
   getauscht=false;
   System.out.println("*****"); //wurde von einem Moderator zensiert!
     while (album2!=null && album1.bewertung < album2.bewertung)
    {
    System.out.println("*****"); //wurde von einem Moderator zensiert!

    album1.next=album2.next;
    if(album2.next!=null)
      {
      album2.next.prev =album1; //!!! evtl null
      }

    album2.prev= album1.prev;
    if(album1.prev!=null)
      {
      album1.prev.next=album2;
      }

      album2.next=album1;
      album1.prev=album2;
      album2=album1.next;
      getauscht=true;
    }
     if(getauscht==false)
     {
     album2=album2.next;
     album1=album2;
     }
   }
  }

Wäre für jeden Tipp dankbar!

MFG

Dieser Beitrag wurde von L-ectron-X am 07.06.2007 um 10:09 Uhr editiert/zensiert.
Bitte Forumreglen beachten!

 

[SlaterB]

male doch auf einen Blatt Papier rum,
kleistere dein Programm mit System.out.println zu, um zu sehen, was in einem speziellen Testfall ganz genau passiert,
das ist eine so schön einfache übersichtliche Sache, später wirst du ganz andere Probleme haben..

-------

die erste Zeile ist schon das Ende vom Lied:
album1.next=album2.next;

was vorher in album1.next war, ist für immer verloren,
die Variable ist überschrieben..

 

[Fragender_Johnny]

sitz grad noch an der uni und muss das teil morgen haben, kann mir bitte jemand den code editieren das er funzt! Wär sehr wichtig! Vielen vielen Dank schonma!

MFG

 

[Gast]

Erstens: Schämst du dich nicht sowas zu posten? (Siehe Zeile 17 u. 20)
Zweitens: nimm doch einfach eine ArrayList und schreib dir einen entsprechenden comparator oder implementier comparable.Oder darfst du das nicht verwenden...

 

[nebulo]

Es scheint zwar inzwischen niemanden mehr zu interessieren. Aber eigentlich sollten sämtlich in-place Sortierverfahren also auch Bubble-Sort kein Problem darstellen.

Ich verstehe nicht was das Problem ist.

Wenn noch Interesse besteht bitte konkret nachfragen was das Problem ist. Wer hier ohne nachzudenken nach einer Lösung will wird selten eine bekommen!

 

[k.]

hm, komischerweise müssen wir das selbe machen, haben aber bis zum 13.6. dafür zeit. sogar die Namen stimmen überein....
erstmal: SORTBY_RATING soll ein Integer sein (Stichwort "static final").
an den while schleifen zum passenden durchlauf bastel ich auch noch, aber hier mal meine swap-methode, die 2 albümer die nebeneinander liegen vertauscht

/**
	 * Tauscht zwei benachbarte Albümer aus
	 * @param a1 Album das nach hinten rutscht
	 * @param a2 Album das nach vorne kommt
	 */
	public void swap( Album a1, Album a2 )
	{
		Album a1vorgaenger = a1.getPrev();
		Album a2nachfolger = a2.getNext();
		
		a1.setPrev( a2 );
		
		if (a2nachfolger == null)
		{
			a1.setNext( null );
			tail = a1;
		}
		else
		{
			a1.setNext( a2nachfolger );
			a2nachfolger.setPrev( a1 );
		}
		
		if (a1vorgaenger == null)
		{
			a2.setPrev( null );
			head = a2;
		}
		else
		{
			a1vorgaenger.setNext( a2 );
			a2.setPrev( a1vorgaenger );
		}
		
		a2.setNext( a1 );
	}

ansonsten viel spaß noch beim tüfteln....

 

[railbird]

komischerweise muss ich genau das gleiche auch machen. hab auch bis 13.6. zeit

 

[Guest]

Dito

Aber auch bei mir läuft noch nicht Alles ....

Hat jemand z.B. eine Idee wo der Haken hier ist bzw. was falsch ist, der gute algorithmus verfällt manchmal , nicht immer in eine scheinbare endlosschleife...

public void setSortMode(int Sort){
   ListNode n = head;
   actSort = Sort;
    ListNode temp;

     if (actSort == 1){
      unsorted = true;

      while (unsorted && n!= null){
           while (n.next != null){
              while(n.Inhalt.compAlb_I(n.next.Inhalt, n.Inhalt)){
                   temp = n;
                   n = n.next;
                   n.next = temp;
                }
             n = n.next;
                  //Zeiger auf nächstes Album
            }
        unsorted =false;
       }
     }
    if (actSort == 2){
      unsorted = true;

      while (unsorted && n != null){

          while (n.next != null){
               while (n.Inhalt.compAlb_B(n.next.Inhalt, n.Inhalt)){
                   temp = n;
                   n = n.next;
                   n.next = temp;
                }
                n = n.next;   //Zeiger auf nächstes Album
            }
        unsorted = false;
       }
    }


  }

 

[SlaterB]

Tipp: verwende nur eine Schleife und mache in der Mitte

compare = 0;
if (actsort = ..)
compAlb_I
else
compAlb_B

--------

> temp = n;
> n = n.next;
> n.next = temp;

temp.next ist dann der Vorgänger von temp, nämlich n, wie es schon immer war?