• Lunes 9 de Diciembre de 2019, 16:16

Autor Tema:  Huffman  (Leído 1741 veces)

daryl_10

  • Nuevo Miembro
  • *
  • Mensajes: 2
    • Ver Perfil
Huffman
« en: Martes 9 de Octubre de 2012, 22:35 »
0
Hola comunidad

Les comento, en la facu me pidieron q programe el algoritmo de comprecion "Huffman" y decidí hacerlo en C#, como no encontre una sección especifica para este lenguaje, coloque el post en este sector, sepan disculpar si no es el correcto...

Empece ayer a realizarlo y me quede en la parte de generación del árbol, una ves ya leido todos los caracteres distintos con sus correspondientes frecuencias y ordenados como Huffman lo demanda, el tema es que hace mucho q no programo con arboles en C# y según tengo pensado debería andar bien función "generar_ arbol" pero se queda en un bucle infinito en el segundo While, las demás funciones andan bien... quisiera saber si me pueden dar una mano? se lo agradecería

Les muestro lo que llevo realizado

namespace huffman
{
    class Nodo
    {
        int frecuencia;
        char dato;
        Nodo hijo_izquierdo, hijo_derecho, derecha;

        public Nodo(int frecuencia, Nodo hijo_izquierdo, Nodo hijo_derecho, Nodo derecha)
        {
            this.frecuencia = frecuencia;
            this.hijo_izquierdo = hijo_izquierdo;
            this.hijo_derecho = hijo_derecho;
            this.derecha = derecha;
        }

        public Nodo(char dato, Nodo derecha)
        {
            this.dato = dato;
            frecuencia = 1;
            this.derecha = derecha;
        }

        public char Dato
        {
            get { return dato; }
            set {dato = value; }
        }

        public int Frecuencia
        {
            get { return frecuencia; }
            set { frecuencia = value; }
        }

        public Nodo Derecha
        {
            get { return derecha; }
            set { derecha = value; }
        }

        public void acum_frecuencia()
        {
            frecuencia ++;
        }
    }

    class Program
    {
        public void leer(Nodo nod, string cadena)
        {
            Nodo ant = nod;
            bool b;

            for (int i = 1; i < cadena.Length; i++)
            {
                b = true;
                Nodo aux = nod;

                while ((b) && (aux != null))
                {
                    if (aux.Dato == cadena)
                    {
                        aux.acum_frecuencia();
                        b = false;
                    }

                    if (b)
                    {
                        ant = aux;
                        aux = aux.Derecha;
                    }
                }

                if (aux == null)
                    ant.Derecha = new Nodo(cadena, null);
            }
        }

        public void ordenar(Nodo nod)
        {
            Nodo aux2 = nod;
            Nodo temp;
            Nodo ant = nod;

            while (aux2 != null)
            {
                temp = aux2;

                while (temp.Derecha != null)
                {
                    temp = temp.Derecha;
                    if (aux2.Frecuencia > temp.Frecuencia)
                    {
                        char daux = aux2.Dato;
                        int faux = aux2.Frecuencia;

                        aux2.Dato= temp.Dato;
                        aux2.Frecuencia = temp.Frecuencia;

                        temp.Dato = daux;
                        temp.Frecuencia = faux;
                    }
                }

                aux2 = aux2.Derecha;
            }
        }

        public void generar_arbol(Nodo nod)
        {
            Nodo aux = nod;

            int frec_acum;

            while (aux != null)
            {
                Nodo temp = aux.Derecha;

                frec_acum = aux.Frecuencia + temp.Frecuencia;

                Nodo nuevo = new Nodo(frec_acum, aux, temp, temp.Derecha);
                aux = nuevo;

                if (aux.Frecuencia >= aux.Derecha.Frecuencia)
                {
                    Nodo primer_lugar = aux.Derecha;
                    temp = primer_lugar;

                    while (aux.Frecuencia >= temp.Frecuencia)
                    {
                        aux.Derecha = temp.Derecha;
                        temp.Derecha = aux;
                    }
                    aux = primer_lugar;
                }

            }
        }

        public void mostrar(Nodo nod)
        {
            Nodo aux2 = nod;

            while (aux2 != null)
            {
                Console.WriteLine(aux2.Dato + " " + aux2.Frecuencia);
                aux2 = aux2.Derecha;
            }

            Console.ReadKey();
        }

        static void Main(string[] args)
        {
            string prueba = "ata la jaca a la estaca";

            Program p= new Program();
            Nodo nod = new Nodo(prueba[0], null);

            p.leer(nod, prueba);
            p.ordenar(nod);
            p.generar_arbol(nod);

            p.mostrar(nod);
        }
    }
}

Desde ya muchas gracias y espero su respuesta