A beadandó C megoldása:
// z.c
//
// LZW fa építő
// Programozó Páternoszter
//
// Copyright (C) 2011, Bátfai Norbert, nbatfai@inf.unideb.hu, nbatfai@gmail.com
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//
// Ez a program szabad szoftver; terjeszthetõ illetve módosítható a
// Free Software Foundation által kiadott GNU General Public License
// dokumentumában leírtak; akár a licenc 3-as, akár (tetszõleges) késõbbi
// változata szerint.
//
// Ez a program abban a reményben kerül közreadásra, hogy hasznos lesz,
// de minden egyéb GARANCIA NÉLKÜL, az ELADHATÓSÁGRA vagy VALAMELY CÉLRA
// VALÓ ALKALMAZHATÓSÁGRA való származtatott garanciát is beleértve.
// További részleteket a GNU General Public License tartalmaz.
//
// A felhasználónak a programmal együtt meg kell kapnia a GNU General
// Public License egy példányát; ha mégsem kapta meg, akkor
// tekintse meg a <http://www.gnu.org/licenses/> oldalon.
//
//
// Version history:
//
// 0.0.1, http://progpater.blog.hu/2011/02/19/gyonyor_a_tomor
// 0.0.2, csomópontok mutatóinak NULLázása (nem fejtette meg senki :)
// 0.0.3, http://progpater.blog.hu/2011/03/05/labormeres_otthon_avagy_hogyan_dolgozok_fel_egy_pedat
//
// 0.0.4 http://proghelp.blog.hu/2011/04/18/vedes_c_ben be és //kimeneti fájlkezelés, karakteres állományokra működik, új //részek felkommentezve
// fordítás: gcc szm.c -o szm -lm -std=c99
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>
// bináris fa struktúrája
typedef struct binfa
{
int ertek;
struct binfa *bal_nulla;
struct binfa *jobb_egy;
} BINFA, *BINFA_PTR;
// faelem létrehozása
BINFA_PTR
uj_elem ()
{
BINFA_PTR p;
if (!(p = (BINFA_PTR) malloc (sizeof (BINFA))))
{
perror ("Nncs eleg memoria!");
exit (EXIT_FAILURE);
}
return p;
}
extern void kiir (BINFA_PTR elem, FILE *k);
extern void ratlag (BINFA_PTR elem);
extern void rszoras (BINFA_PTR elem);
extern void szabadit (BINFA_PTR elem);
int
main (int argc, char **argv)
{
// paraméterlista ellenőrzése
if ((argc != 4) || (argv[2][1] != 'o'))
{
printf
("Helyes paramétrlista: ./smbeadando bemeneti_file -o kimeneti_file\n");
return -1;
}
// ki\bemeneti fájlok megnyitása\létrehozása
FILE *be, *ki;
if (!(be = fopen (argv[1], "r")))
{
printf ("Nem sikeult megnyitni a bemeneti fajlt!\n");
return -1;
}
if (!(ki = fopen (argv[3], "w")))
{
printf ("Nem sikeult letrehoznia kimeneti fajlt!\n");
return -1;
}
// bináris fa gyökerének inicializálása
BINFA_PTR gyoker = uj_elem ();
gyoker->ertek = '/';
gyoker->bal_nulla = gyoker->jobb_egy = NULL;
BINFA_PTR fa = gyoker;
unsigned char b;
while ((b = getc (be)) != EOF) // karakterek beolvasása fájl végéig
{
for (int i = 0; i < 8; i++) // b 8 bitjén végiglépése miatt
{
if ((b & 0x80) >> 7 == 0) // b bitmaszkolása ás bitrotálás az aktuálisan vizsgálni kívánt bit miatt
{
if (fa->bal_nulla == NULL)
{
fa->bal_nulla = uj_elem ();
fa->bal_nulla->ertek = 0;
fa->bal_nulla->bal_nulla = fa->bal_nulla->jobb_egy = NULL;
fa = gyoker;
}
else
{
fa = fa->bal_nulla;
}
}
else
{
if (fa->jobb_egy == NULL)
{
fa->jobb_egy = uj_elem ();
fa->jobb_egy->ertek = 1;
fa->jobb_egy->bal_nulla = fa->jobb_egy->jobb_egy = NULL;
fa = gyoker;
}
else
{
fa = fa->jobb_egy;
}
}
b <<= 1; // b rotálása 1-el barra
}
}
fclose (be);
kiir (gyoker, ki);
extern int max_melyseg, atlagosszeg, melyseg, atlagdb;
extern double szorasosszeg, atlag;
fprintf (ki,"Melyseg = %d\n", max_melyseg - 1);
/* Átlagos ághossz kiszámítása */
atlagosszeg = 0;
melyseg = 0;
atlagdb = 0;
ratlag (gyoker);
// atlag = atlagosszeg / atlagdb;
// (int) / (int) "elromlik", ezért casoljuk
// K&R tudatlansági védelem miatt a sok () :)
atlag = ((double) atlagosszeg) / atlagdb;
/* Ághosszak szórásának kiszámítása */
atlagosszeg = 0;
melyseg = 0;
atlagdb = 0;
szorasosszeg = 0.0;
rszoras (gyoker);
double szoras = 0.0;
if (atlagdb - 1 > 0)
szoras = sqrt (szorasosszeg / (atlagdb - 1));
else
szoras = sqrt (szorasosszeg);
fprintf (ki,"Altag = %f\nSzoras = %f\n", atlag, szoras);
fclose (ki);
szabadit (gyoker);
}
// a Javacska ONE projekt Hetedik Szem/TudatSzamitas.java mintajara
// http://sourceforge.net/projects/javacska/
// az atlag() hivasakor is inicializalni kell oket, a
// a rekurziv bejaras hasznalja
int atlagosszeg = 0, melyseg = 0, atlagdb = 0;
void
ratlag (BINFA_PTR fa)
{
if (fa != NULL)
{
++melyseg;
ratlag (fa->jobb_egy);
ratlag (fa->bal_nulla);
--melyseg;
if (fa->jobb_egy == NULL && fa->bal_nulla == NULL)
{
++atlagdb;
atlagosszeg += melyseg;
}
}
}
// a Javacska ONE projekt Hetedik Szem/TudatSzamitas.java mintajara
// http://sourceforge.net/projects/javacska/
// az atlag() hivasakor is inicializalni kell oket, a
// a rekurziv bejaras hasznalja
double szorasosszeg = 0.0, atlag = 0.0;
void
rszoras (BINFA_PTR fa)
{
if (fa != NULL)
{
++melyseg;
rszoras (fa->jobb_egy);
rszoras (fa->bal_nulla);
--melyseg;
if (fa->jobb_egy == NULL && fa->bal_nulla == NULL)
{
++atlagdb;
szorasosszeg += ((melyseg - atlag) * (melyseg - atlag));
}
}
}
//static int melyseg = 0;
int max_melyseg = 0;
void
kiir (BINFA_PTR elem, FILE *k)
{
if (elem != NULL)
{
++melyseg;
if (melyseg > max_melyseg)
max_melyseg = melyseg;
kiir (elem->jobb_egy,k);
// ez a postorder bejáráshoz képest
// 1-el nagyobb mélység, ezért -1
for (int i = 0; i < melyseg; ++i)
fprintf (k,"---");
fprintf (k,"%c(%d)\n", elem->ertek < 2 ? '0' + elem->ertek : elem->ertek,
melyseg - 1);
kiir (elem->bal_nulla,k);
--melyseg;
}
}
void
szabadit (BINFA_PTR elem)
{
if (elem != NULL)
{
szabadit (elem->jobb_egy);
szabadit (elem->bal_nulla);
free (elem);
}
}
