Huffman-Baumschule

nullplan002

Hi all,
ich weis, dass das von Seiten der Programmiersprache nicht hierhergehört, aber wohin denn dann? Das Thema stimmt jedenfalls:
Allso, ich habe mit Pascal schonmal einen Typ für einen binären Baum vorbereitet:

type
  leer = boolean;
  pbaum = ^tbaum;
  tbaum = record
    p : longword;
    if leer then ( bt : byte; ) else ( a, b: pbaum);
  end;

Eigentlich klar: Jeder Knoten hat eine Wahrscheinlichkeit, die vollen haben zwei Kinder, die leeren haben ein Zeichen. So, wie baue ich den Baum jetzt aufgrund einer Liste auf, die wie folgt erstellt wurde:

var
  i: integer;
  baum : tbaum;
  hlparr : array [0 .. 255] of longword = 0;
  bla: file of byte;

begin
  assign (bla, paramstr(1));
  reset (bla);
  repeat
    read(bla, i);
    inc(hlparr[i]);
  until eof(bla);
end.

Ich habe da nämlich momentan überhaupt keinen Plan. Ich dachte zunächst daran ein array of tbaum zu erstellen und bei allen Elementen den Diskriminator leer auf true zu setzen. Dann weise ich allen Elementen ihr Byte und ihre Wahrscheinlichkeit zu. Soweit klar. Doch wie kann ich dann zwei Elemente nach den Huffmanregeln zusammenhängen? Mir fiele nur etwas wie:

arr[n+1].leer := false;
arr[n+1].a := @arr[1]; {n = Anzahl der Blätter} 
arr[n+1].b := @arr[2];

ein, aber dann weis ich nicht, wie viele Elemente das Array braucht?
Tschö,
nullplan

CStoll

Es ist schon eine Weile her, daß ich mit Pascal gearbeitet habe - aber gab es dort nicht auch die Möglichkeit, Heap anzufordern? (analog zu new/delete)

nullplan002

Das heißt hier: new(p:pointer); und dispose(p:pointer); Rate mal, was die machen. Bei zuwenig Speicher wird nil zurückgegeben (nil = pointer to nowhere). Dispose macht einen RTE wenn der Pointer nicht auf den Heap zeigt. Wenn du sonst noch Fragen hast: Man kann sie dir hier (new) oder hier (dispose) vermutlich beantworten.
Tschö,
nullplan

CStoll

Hey, du willst in Pascal programmieren, nicht ich

(und was ich oben sagen wollte war: statt dir eine feste Arraygröße vorzugeben, solltest du lieber deinen Speicher per new anfordern, wie du ihn gerade brauchst.)

nullplan002

Danke für die Anregung.
Tschö,
nullplan