Advanced Search

Question: Graph Theory Shannon-Fano Algo implementation

Question:Graph Theory Shannon-Fano Algo implementation

maplenoob 189 Maple
student graphtheory
May 24 2008
1
<p>hi,</p>
<p>i tried to write a maple procedure that creates a prefix free tree based on the algorithmen of Shannon-Fano. the theory how the algorithm works is easy but for translating that into a maple procedure causes me headaches.</p>
<p>right now im stuck in the part where i have to split the characters i got until i only have one left. i suppose until that point my procedure might be ok but i how do i continue now? i lack the maple know-how to get further now....and i suppose i did already things wrong because i don't know how to save my nodes</p>
<p>here is my current attempt: ( i assume that the incoming list is sorted )</p>
<p>SF := proc(L::list)<br />
local i, # Length of list<br />
      t, # for list length mod 2 = 0 t is zero otherwise 1<br />
    tL1, # splitted List, part 1<br />
    tL2; # splitted List, part 2<br />
<br />
i := nops(L);  <br />
<br />
if (i > 1) then    #More then 1 element in list<br />
<br />
if ((i mod 2) = 0) then #Can you split the list in 2 equal parts<br />
t := 0;<br />
else<br />
t := 1;<br />
fi;<br />
<br />
for k from 1 to ((nops(L)+t)/2) by 1 do   #Copy Part 1 of List in "sub"-list<br />
tL1 := tL1 + L[k]  <br />
od;<br />
<br />
SF(tL1); #Rekursiv for the first part<br />
<br />
for q from (((nops(L)+t)/2)+1) to nops(L) by 1 do   #Copy Part 2 of List in "sub"-list<br />
tL2 := tL2 + L[k]  <br />
od;<br />
<br />
SF(tL2); #Rekursiv for the second part<br />
<br />
<br />
fi;<br />
end;<br />
<br />
i have to save the results of the rekursion step bevor to know the nodes of my leafs......can someone help me and give me clue how to continue or a better way for implementing this?<br />
 </p>
Please Wait...