Proghelp

// LG_beadando-LZW_fa.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_hogy
//
// Version history: (Leleszi Gábor)
//
// 0.0.6, fájlkezelés, -o kapcsoló hozzáírása, forrás felkommentezése
// 0.0.9, függvények előrehozatala és prototípusok eltávolítása, hibaüzeneteket kibővítése
// 0.1.0, beszedesebb valtozo nevek hasznalata
//
// Fordítás: gcc LG_beadando-LZW_fa.c -o LZW -lm

#include <stdio.h>                                      // Standard I/O fv-ek
#include <stdlib.h>                    // malloc(), calloc(), free(), exit() fv-eket tartalmazza
#include <math.h>                                      // Alapvető matematikai fv-ek
#include <fcntl.h>                    // Low-level fajlkezeles

/*
   A binfa struktúránk
A "typedef" mindössze anyit jelent a strúktúra előtt, hogy később a struktúrúra való hivatkozás közben egyszerűen a structura_nevével hívatkohatunk, nem pedig struct struktura_nev formában
*/
typedef struct binfa
{
    int ertek;
  struct binfa *bal_nulla;                            // A binfa strukturára egy bal_nulla mutató mutat
  struct binfa *jobb_egy;
} BINFA, *BINFA_MUTATO;            // A binfa struktúra ezekkel a nevekkel hivatkozhatunk

/*
   Faelemek létrehozása
*/
BINFA_MUTATO uj_elem ()            // Ezzel a fv-nyel adunk a fához új elemet a fához
{
  BINFA_MUTATO binfa_mutato;              // BINFA_MUTATO típúsú binfa_mutato változó deklarálása
                                                                        // A BINFA_MUTATO típus az előbbi struktúránk

  if ((binfa_mutato = (BINFA_MUTATO) malloc (sizeof (BINFA))) == NULL)        //A malloc() fv-nyel lefoglalunk a memóriából egy BINFA méretű darabot, ha ez azonban nem sikerűlt, hibaüzivel elszáll a programunk.
  {
        perror ("Nem sikerült lefoglalni a memoriát");
        exit (EXIT_FAILURE);
  }
 
  return binfa_mutato;           // Visszaadjuk az új elem címét
}

/////////// FV-ek kezdete
/*
    a Javacska ONE projekt Hetedik Szem/TudatSzamitas.java mintajara
    http://sourceforge.net/projects/javacska/
    az atlag() hivasakor is inicializalni kell oket, mert a
    rekurziv bejaras hasznalja
*/
int atlagosszeg = 0, melyseg = 0, atlagdb = 0;
void ratlag (BINFA_MUTATO fa)    // Az ratlag fv formális paraméterlistájában megadjuk a fa változót ami BINFA_MUATO típusú
{
  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, mert a
    rekurziv bejaras hasznalja
*/
double szorasosszeg = 0.0, atlag = 0.0;
void rszoras (BINFA_MUTATO 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));
        }
    }
}

    // Kiír fv
int max_melyseg = 0;
void kiir (BINFA_MUTATO elem, FILE * of)
{
  int i;
    
    if (elem != NULL)
    {
      ++melyseg;
    if ((melyseg-1) > max_melyseg)
            max_melyseg = melyseg - 1;
            
        kiir (elem->jobb_egy, of);
        
    for (i=0; i<melyseg-1; ++i)
        fprintf (of, "---");
    fprintf (of, "%c(%d)\n",
                                                         elem->ertek < 2 ? '0' + elem->ertek : elem->ertek,
                                                         melyseg - 1);
        kiir (elem->bal_nulla, of);
        --melyseg;
  }
}

    // Felszabadítjuk a lefoglalt memóriát, különben egyszercsak elfolyik a memória :)
void szabadit (BINFA_MUTATO elem)
{
  if (elem != NULL)
    {
        szabadit (elem->jobb_egy);
        szabadit (elem->bal_nulla);
        free (elem);
    }
}
////////// FV-ek vége

////////// MAIN
int main (int argc, char *argv[])
{
  unsigned char buffer;                                                       // buffer változó deklarálása, ami nem előjeles char típusú, pontosan 1 byte-nyi terülten tárolódik
  int i, egy_e;

  BINFA_MUTATO gyoker = uj_elem ();
    gyoker->ertek = '/';                                                       // A gyoker megkapj kezdő értékéűl a /-t
  gyoker->bal_nulla = gyoker->jobb_egy = NULL;        // A gyoker bal_nulla és jobb_egy pointerének NULL-raa állítása
  BINFA_MUTATO fa = gyoker;                        // A fa mindig oda mutat ahol éppen állunk

  if (argc != 4 || argv[2][0] != '-' || argv[2][1] != 'o')        // printf("0:%s 1:%s 2:%s 3:%s\n", argv[0], argv[1], argv[2], argv[3]);
// Többek között a -o kapcsoló vizsgálata. Ha kikommenteljük az előző printf-t láthatjuk mi is van az argv-ben
    {
      printf ("\nHasznalat: %s INPUT_FILE -o OUTPUT_FILE\n\n", argv[0]);
      return -1;
  }

  int inputfile = open (argv[1], O_RDONLY);    // open:  megnyit vagy létrehoz egy fájlt írásra vagy olvasásra. man open
    
  FILE *outputfile;
  outputfile = fopen (argv[3], "w");
 
  if (!outputfile)
  {
        printf("Nem sikerült létrehozni a kimeneti fájlt!\n");
    return -1;
  }

  while ( read (inputfile, (void *) &buffer, sizeof(unsigned char)) )    // man read: read (be, *buffer, buffer_meret)
  {
        for (i=0; i<8; i++)                                // Vizsgáljuk a buffer 8 bitjét
        {
             egy_e = buffer & 0x80;                    // egy_e = a buffer bitjei és a hexadecimális 80-nak a bitjei közt vett és művelet eredményével
                                                                                                                     /*
                 0x80 binárisan: 10000000
                 A bufferben pedig az éppen vizsgált karakterek bitjei vannak, összesen 8 bit,
                    mert 1 db. unsigned char az 1 byte méretű                                                                                                                 */
          
          if ((egy_e >> 7) == 1)        // Az egy_e változó bitjet tolja el 7-tel jobbra, és vizsgálja, hogy az ott elhelyezkedő bit egyenlő-e 1-gyel?
                                                                                                              // Az egy_e változó értéke 10000000, vagy 00000000 lehet Ha 7-tel eltoljuk, akkor az első bitet vizsgáljuk. Theát 1-rt vagy nullát.
        {
            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;
                }
           }
               
          else
        {
                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;
                }
           }
                
          buffer <<= 1;        // Eltoljuk eggyel balra a buffer aktuális értékét, így már a következő bitet vizsgáljuk a bufferben
        }
    }

  fprintf (outputfile, "\n");
  kiir (gyoker, outputfile);

  fprintf (outputfile, "melyseg=%d\n", max_melyseg);   // Kiírjuk a kimeneti fájlba a melyseget


  //////////////// Átlagos ághossz kiszámítása
  atlagosszeg = 0;
  melyseg = 0;
  atlagdb = 0;
  ratlag (gyoker);
  atlag = ((double) atlagosszeg) / atlagdb;
  //////////////// Átlagos ághossz kiszámítása vége


  //////////////// Á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);
  ///////////////// Ághosszak szórásának kiszámítása vége


  fprintf (outputfile, "atlag=%f\nszoras=%f\n", atlag, szoras); // Kiírjuk a kiszámolt atlag-ot és szoras-t a kimeneti fájlba

  szabadit (gyoker);                 // meghívjuk a szabadit() fv-t és átadjuk neki a gyokeret, ezzel azt felszabadítjuk.
  close (inputfile);                    // Lezárjuk -az alacsony szintű fájlkezeléssel megnyitott  - fájlt
  fclose (outputfile);                 // Lezárjuk -a magaszinten kezelt- fájlt

  printf ("\nA célobjektum  létrejött, neve: %s\n\n", argv[3]);
 
  return 0;
}


http://data.hu/get/3789879/LG_beadando-LZW_fa.c