Scala 99 - 01.07.2010 -02.07.
==03==
def findMe(l:List[Int], i:Int):Int = { if(i==0) l.head else findMe(l drop 1,i-1) }
==04==
l.foldLeft(0) {(a,b) => a+1 }
==05==
def myRev[A](l:List[A]):List[A] = l.foldLeft([List[A]()) { (a,c) => c :: a}
===14==
l.foldLeft(Nil.asInstanceOf[List[Int]]) {(c,a) => (a :: a :: c) }
==15==
def consmore (l:List[Int], count:Int, element:Int):List[Int] = if(count==0) l else consmore(element::l,count-1, element)
==28==
ll=List[List[Int]] = List(List(1, 2), List(1, 2, 3), List(4, 5), List(5), List(3, 4, 5), List(7), List(1, 2, 3, 4, 5), List(1, 2, 3, 4))
val r1=ll.foldLeft(List[(Int,Int)]()) { (a,b) => (b.length,ll indexOf b) :: a}
val r2= r1 sortWith ((t1,t2)=> t1._1 > t2._1)
val finalResult=r2.foldLeft(List[List[Int]]()) { (a,b) => ll(b._2) :: a }
==50==
class Knoten(val h:Int, val zeichen:Char){
def this(h:Int) = this(h,’1′);
private var kante:Knoten = null
private var kantenWert: Int = -1
def getKante() = kante
def setKante(k:Knoten, kw: Int) = {kante = k; kantenWert = kw}
def hasKante() = kante != null
def isLeaf() = !zeichen.isDigit
def getCode() = kantenWert
override def toString() = h+” kante:”+nn(kante)
def nn(k:Knoten) = if (k == null) “” else k.h
}
import scala.collection.mutable.HashMap
def findFreq(s:String):HashMap[Char,Int] = {
val r=new HashMap[Char,Int];
s.distinct.foreach(x=> r+= (x -> (s count(y => y==x)) ) );
r
}
val list1=((for {b <- fr; fre =b._2; element=b._1 } yield new Knoten(fre,element)).toList) sortWith (sortKnoten)
def transform(l:List[Knoten]):List[Knoten] = {
val step=l filter(! _.hasKante) take 2
if(step.size > 1){
val k=new Knoten(step(0).h+step(1).h)
step(0).setKante(k,0);
step(1).setKante(k,1);
transform(((k::l) sortWith (sortKnoten)))
}else
l
}
def getP(c:Knoten, fillMe:String):String = {
if(c.getCode!= -1) //Wurzel
getP(c.getKante, fillMe+c.getCode.toString)
else
fillMe.reverse
}
val resAnzeige=(list1a filter (_.isLeaf) map(x => x.zeichen+”:”+getP(x,”") ))
Das Verfahren konstruiert einen binären Baum mit einer Knoten¬markierung p und einer Kanten-markierung h.
Algorithmus Huffman
Eingabe: Text t
Ausgabe: Binärer Baum mit einer Knoten¬markierung p und einer Kanten¬markierung h
Methode:
1. erzeuge für jedes Zeichen x, das im zu codierenden Text t vorkommt, einen Knoten und markiere den
Knoten mit der Häufigkeit, mit der x im Text vorkommt;
2. wiederhole solange es mehr als einen Knoten gibt, zu dem keine Kante hinführt
a. suche zwei Knoten u und v mit minimaler Markierung p(u) bzw. p(v), zu denen noch keine Kante hinführt;
b. erzeuge einen neuen Knoten w und verbinde w mit u und v. Markiere die eine Kante mit 0, die andere mit 1. Markiere den Knoten w mit p(u) + p(v);
Nach Konstruktion dieses Baumes ergibt sich für jedes Zeichen x die Codierung c(x) als Folge der Kanten¬markierungen auf
dem Pfad von der Wurzel zu dem Blatt, das zu x gehört.
11
/ \
/ 7
/ / \
/ 3 \
/ / \ \
4 1 2 4
I M P S
link1
link2
ref
P50