54 lines
1.5 KiB
Plaintext
54 lines
1.5 KiB
Plaintext
INSTALL @lib$+"SORTSALIB"
|
|
SortUp% = FN_sortSAinit(0,0) : REM Ascending
|
|
SortDn% = FN_sortSAinit(1,0) : REM Descending
|
|
|
|
Text$ = "this is an example for huffman encoding"
|
|
|
|
DIM tree{(127) ch&, num%, lkl%, lkr%}
|
|
FOR i% = 1 TO LEN(Text$)
|
|
c% = ASCMID$(Text$,i%)
|
|
tree{(c%)}.ch& = c%
|
|
tree{(c%)}.num% += 1
|
|
NEXT
|
|
|
|
C% = DIM(tree{()},1) + 1
|
|
CALL SortDn%, tree{()}, tree{(0)}.num%
|
|
FOR i% = 0 TO DIM(tree{()},1)
|
|
IF tree{(i%)}.num% = 0 EXIT FOR
|
|
NEXT
|
|
size% = i%
|
|
|
|
linked% = 0
|
|
REPEAT
|
|
C% = size%
|
|
CALL SortUp%, tree{()}, tree{(0)}.num%
|
|
i% = 0 : WHILE tree{(i%)}.lkl% OR tree{(i%)}.lkr% i% += 1 : ENDWHILE
|
|
tree{(i%)}.lkl% = size%
|
|
j% = 0 : WHILE tree{(j%)}.lkl% OR tree{(j%)}.lkr% j% += 1 : ENDWHILE
|
|
tree{(j%)}.lkr% = size%
|
|
linked% += 2
|
|
tree{(size%)}.num% = tree{(i%)}.num% + tree{(j%)}.num%
|
|
size% += 1
|
|
UNTIL linked% = (size% - 1)
|
|
|
|
FOR i% = size% - 1 TO 0 STEP -1
|
|
IF tree{(i%)}.ch& THEN
|
|
h$ = ""
|
|
j% = i%
|
|
REPEAT
|
|
CASE TRUE OF
|
|
WHEN tree{(j%)}.lkl% <> 0:
|
|
h$ = "0" + h$
|
|
j% = tree{(j%)}.lkl%
|
|
WHEN tree{(j%)}.lkr% <> 0:
|
|
h$ = "1" + h$
|
|
j% = tree{(j%)}.lkr%
|
|
OTHERWISE:
|
|
EXIT REPEAT
|
|
ENDCASE
|
|
UNTIL FALSE
|
|
VDU tree{(i%)}.ch& : PRINT " " h$
|
|
ENDIF
|
|
NEXT
|
|
END
|