| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | list2=[] list3=[] classNode(object): def__init__(self,name=None,value=None): self._name=name self._value = value self._left=None self._right = None classHuffmanTree(object): def __init__(self, char_weights): self.a=[Node(part[0],part[1])forpart in char_weights] whilelen(self.a)!=1: self.a.sort(key=lambda node:node._value,reverse=True) c=Node(value=(self.a[-1]._value+self.a[-2]._value)) c._left=self.a.pop(-1) c._right=self.a.pop(-1) self.a.append(c) self.root=self.a[0] self.b=range(10) def pre(self,tree,length): node=tree if(not node): return elif node._name: list1='' fori in range(length): list1+=str(self.b[i]) list2.append(node._name) list3.append(list1) return self.b[length]=0 self.pre(node._left,length+1) self.b[length]=1 self.pre(node._right,length+1) def get_code(self): self.pre(self.root,0) if__name__=='__main__': dic=[] i = raw_input() forj in set(i): dic.append((j,i.count(j))) char_weights=dic tree = HuffmanTree(char_weights) tree.get_code() r='' forl in i: form in range(len(list2)): ifl==list2[m]: r+=str(list3[m]) print r # # abbcccdddd #1101111111010100000 测试用例 为什么和我的不一样，求大佬告知！ |
