Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (GNU/Linux, *NIX, *BSD und Co) » d-näres Heapsort - BubbleDown

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 <
000
13.08.2014, 22:44 Uhr
MissMarshall



Guten Abend,

ich soll ein d-näres Heap programmieren und stecke nun seit fast eine Woche mit dem Code fest. Problem ist die BubbleDown-Funktion.

Bin gerade im 2. Semester Informatik und hatte zuvor noch nie programmiert. Selbst zu Schulzeiten nicht. Bin also blutige Anfängerin. Der Code ist nicht gerade optimal oder sehr 'schön'. Und leider auch nicht wirklich funktionsfähig. Nun will ich das Ding aber zum Laufen bringen und wäre wirklich um jede kleinste Hilfestellung dankbar!


C++:
inline void BubbleDown( T A[], const uint N, uint p, const uint D )
{
  typedef typename T::key_type K;
  /// TODO Anfang
  
    int k = 1;
    int child = (p * D) + k;
    int minChild = child;
    
    int maybeChild;
    
    
    int count = 0;
    bool done = false;
    
    while(!done && (p <= ((N-2)/D)))
    {
        
        
        for(int i=1; i<=D; ++i) // Kinder zählen <-- wahrscheinlich klappt so nicht...
        {
            child = (p * D) + i;
            count ++;
        }
        
        if(count = D) // 1. Fall: p hat genau D Kinder
        {
            for(k = 2; k <= D; ++k) // Index des kleinsten Kindes finden
            {
                maybeChild = child;
                
            if(A[maybeChild].Key() < A[minChild].Key())
            {
                minChild = maybeChild;
            }
                
            }
            
            if(A[p].Key() <= A[minChild].Key()) // Probe, ob wirklich kleiner als p
                done = true;
            
            else // falls ja: Tausche beide
            {
                swap(A[p], A[minChild]);
                
                p = minChild; // p ist nun eine Ebene tiefer
            }
            
            }
        
        
        if(count < D)
        {
            maybeChild = count;
            
            while(maybeChild > 1)
            {
                if(A[maybeChild].Key() < A[minChild].Key())
                {
                    minChild = maybeChild;
                }
                    --maybeChild;
                }
            if(A[p].Key() <= A[minChild].Key())
                done = true;
            
            else
            {
                swap(A[p], A[minChild]);
                done = }false;
            }
            }
        
  
  /// TODO Ende
}

 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
15.08.2014, 23:12 Uhr
Hans
Library Walker
(Operator)


Hi,
äh was soll ein "d-näres Heap" sein?
Findet sich denn in Eurem Skript oder einem Algorithmen Lehrbuch kein Beispiel dazu?

Hans,
der gerade auch keine Ahnung hat...
--
Man muss nicht alles wissen, aber man sollte wissen, wo es steht. Zum Beispiel hier: Nachdenkseiten oder Infoportal Globalisierung.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
16.08.2014, 10:51 Uhr
FloSoft
Medialer Over-Flow
(Administrator)


das einzige was ich zu diesem thema gefunden habe ist das hier:

www.zib.de/krumke/Teaching/Data/algo-skript.pdf (seite 16ff)
--
class God : public ChuckNorris { };
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 <     [ C / C++ (GNU/Linux, *NIX, *BSD und Co) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: