Bloque de Colores

Problema de Algoritmia Básico: Mejoras a la Solución Básica

Icono de Post February 28 2012 :: Algoritmia, c, Estructuras de datos ::

Este post continua con el problema planteado en este post. Habiendo ya analizado la complejidad de la solución básica , el siguiente paso es tratar de mejorarla proponiendo diferentes estructuras de datos para la función esta_en_lista().

Usar un array

La solución mas inmediata es cambiar la lista pasados por un array. Esta version se puede ver en solucion-array.c.

La gran diferencia entre ambas versiones es la función esta_en_lista(), que ahora nos queda:


int esta_en_lista(int value, char pasados[ MAXINT ]) {	

	if( pasados[value] == 1) return 1;
	pasados[value] = 1;
	return -1;

}

Código en solucion-array.c

Porque es una mejora?

El acceso a un array es siempre O(1). Por consiguiente el costo total del algoritmo seria O(n) * O(1), que es equivalente a O(n).

Cuales son las desventajas?

La desventaja principal es que lo que ganamos en la mejora de la complejidad de la función, lo perdemos en la complejidad espacial. Basicamente porque ahora necesitamos alocar e inicializar memoria para un array del tamaño del mayor int posible en la lista.

La otra desventaja es que es necesario inicializar el array a 0. Lo cual hace que el algoritmo de por si tenga una cota minima de O( MAXINT ), en el caso (esperable) de que la lista sea de tamaño mayor que el MAXINT posible este no es un problema ya que la porción del algoritmo que es O(n) es mayor que el MAXINT, pero si estuvieramos trabajando con un input de listas chicas, la solución anterior podria ser preferible.

En definitiva, esta solución es mas efectiva cuando el mayor int posible es pequeño y la lista es muy larga.

Usar un Binary Search Tree

Esta versión se puede ver en solucion-binary-search-tree.c. El código nos queda:


int esta_en_lista(int value, BSTree *pasados) {	
  BSTree cursor = *pasados;

  //El nodo esta vacio
  if( cursor == NULL) {
    BSTree temp = (BSTree) malloc(sizeof(struct BST_Node));
    temp->value = value;
    temp->right = NULL;
    temp->left = NULL;
    *pasados = temp;
    return -1;
  }

  //El nodo tiene el mismo valor
  if( cursor->value == value ) return 1;

  if( cursor->value < value) {
      //Fijarse en el nodo derecho
      return esta_en_lista(value, &(cursor->right));
   } else {
      //Fijarse en el nodo izquierdo
      return esta_en_lista(value, &(cursor->left));
   }
}

La ventaja inmediata de un Binary Search Tree es que la inserción y la busqueda tienen para un input promedio, complejidad O(log(n)). Esto nos mejoraría el algoritmo, llevandolo a O(n log(n)).

Sigue existiendo, sin embargo, el problema de que en el peor caso posible de una lista ordenada ascendentemente: [1,2,3,4,..]; el binary search tree se comporta exactamente igual que una lista. Esto se puede arreglar usando un Balanced Binary Search Tree, aunque es una estructura de datos un poco compleja para acordarse de su implementación y codificarla en una entrevista.

Soluciones esotéricas

Usar un bit array

Si se quiere tener una performance similar a la de un array pero con un uso menor de memoria, se puede usar un Bit Array, aunque tampoco escala bien a nivel espacio.

Usar un hashtable de binary trees

Esta es la ultima opción que codifique y se puede encontrar en solucion-hashtable-de-binary-search-trees.c. Analizar las ventajas y desventajas de esta solución se las dejo al lector.

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994

Introduction to Algorithms, 2nd Edition; Cormen, Leierson, Rivest, Stein; MIT Press; 2009

Autor: Emiliano Martínez Luque.

Comments Off on Problema de Algoritmia Básico: Mejoras a la Solución Básica

Problema de Algoritmia Básico: Primera Solución

Icono de Post February 28 2012 :: Algoritmia, c, Estructuras de datos, Lógica ::

Este es una serie de posts sobre un ejemplo básico de analisis de algoritmos. Va a constar de 3 partes: Descripción del problema y solución básica, Análisis de complejidad de la solución básica y Posibles mejoras. El codigo de estos posts se puede encontrar aquí .

Hace unos días estuve hablando con un ex-compañero de la facultad sobre una entrevista de trabajo que había tenido en una empresa muy grande de estados unidos. Me comento muy rapidamente y sin muchos detalles sobre el problema que le habían presentado y me resultó interesante como un buen ejercicio de Algoritmia básica.

Descripción del problema

El problema consiste en dado una lista de numeros enteros, remover los duplicados de la lista. Asumí al hacer el codigo, que interesa mantener la estructura de la lista ( O sea dado una lista: [5,3,4,5,3,2]; encontrar la misma lista pero con los duplicados removidos: [5,3,4,2] ).

Obviamente el problema no es solamente solucionar este problema, sino razonar sobre la corrección y eficiencia de la solución encontrada y ademas codificarlo en algun lenguaje ( especificamente C ).

Algunos pasos previos

Antes de comenzar a trabajar en el problema, me parecio conveniente hacer algunas funciones para poder testear y probar el codigo.

Struct de la lista

La estructura de datos que se va a utilizar en el ejercicio


typedef struct Node *List;
struct Node {
  int value;
  struct Node *next;
};

Función para mostrar la lista

Una función para mostrar la lista por pantalla.


void mostrar_lista(List lista) {
	//Este primer paso es para el pretty print de la lista
	if(lista != NULL) {
		printf("%d", lista->value);
		lista = lista->next;
	}
	while(lista != NULL) {
		printf("-%d", lista->value);
		lista = lista->next;
	}
}

Función para cargar una lista de prueba

Una función que dado un string con una lista de enteros separados por comas, lo parsea a un linked list.

Esta es una versión mejorada sobre la que hice originalmente, esta versión es forgiving con aquellos caracteres que pueden haber sido mal tipeados por el usuario o por input malintencionado, tomando solo los caracteres que representan dígitos ( el string: “1,a2,3b,d4d,xxxx,5,,,,6,a8b0,10” se tranforma en la lista: [1,2,3,4,5,6,80,10] ). La versión original era un poco más simple y no anticipaba malas entradas.


List crear_lista(List lista, char str[2000]) {
	int i=0;
	List rList = lista;

	//Es forgiving, solo lee los digitos y descarta lo demas.
	while( str[i] != '' ) {
		while( str[i] != '' && (str[i] < '0' || str[i] > '9') ) i++;
		if(str[i] == '') break;

		int pre = 0;
	    
		//Calcular el int
		while( str[i] != ',' && str[i] != '' ) {
			if(!(str[i] < '0' || str[i] > '9')) { 
				pre = pre * 10;
				pre = pre + (str[i] - '0');
			} 
			i++; 
		}
	    
		//Crear el nodo nuevo    
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = pre;
		temp->next = NULL;

		//Primera iteracion
		if(lista==NULL) {
			//Agregar nodo a lista
			lista = temp;
			//Lista de retorno
			rList = lista;
		} else {
			//Agregar nodo, mover cursor.
			lista->next = temp;
			lista = lista->next;
		} 
		i++;
	}
	return rList;
}

Ejemplo de uso:


	char str[2000] = "";
	scanf("%s", str);
	lista = crear_lista(lista, str);
	printf("La lista es: n");
	mostrar_lista(lista);

Solución básica

La solución básica consiste de 2 funciones. Una función int esta_en_lista(int value, List *pasados) que dado un entero value y una lista pasados verifica si el valor existe en la lista. Si ya existe devuelve 1, si no, devuelve -1 (podría haber usado constantes TRUE y FALSE como macros y el codigo seria mas bonito) y agrega este valor a la lista pasados en orden ascendente. La lista pasados se pasa por referencia ( efectivamente es un puntero a puntero ) dado que como side effect de la función se modifica esta lista, agregandosele ordenadamente cualquier valor que no pre-existe. O sea, en sucesivas llamadas a la funcion se va creando una lista ordenada de valores. La otra función List * sacar_duplicados(List *lista, List *pasados), recibe 2 punteros a listas, la lista de enteros de la que queremos sacar duplicados y una lista donde se guardan los valores que ya existen en la lista. Esta es la función que devuelve la primer lista con los valores removidos. Esta pensado para ser llamada con pasados siendo una lista vacia.


//Version basica a ser mejorada
//Se pasa un puntero al puntero de lista para hacer los side effects
int esta_en_lista(int value, List *pasados) {

	List rList, prev;

	rList = *pasados;
	prev = NULL;

	if(rList == NULL) {
		//Agregarlo antes
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = value;
		temp->next = *pasados;
		*pasados = temp;
		return -1;
	}

	while(rList != NULL) {
		if(rList->value == value) return 1;
		if(rList->value > value) {
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = value;
			temp->next = rList;
			if(prev==NULL) {
				*pasados = temp;
			} else {
				prev->next = temp;
			}
			return -1;
		}
		prev = rList;
		rList = rList->next;
	}
	//Agregarlo al final
	List temp;
	temp = (List) malloc(sizeof(struct Node));
	temp->value = value;
	temp->next = NULL;
	prev->next = temp;
	return -1;
}



//ESTA ES LA FUNCION QUE IMPORTA EN UN PRIMER PASO
//EN UN SEGUNDO PASO LO QUE IMPORTA ES MEJORAR LA FUNCION ANTERIOR
List * sacar_duplicados(List *lista, List *pasados) {
	//Caso Base
	if( (*lista) == NULL) {
		return lista;
	} else {
	//PASO INDUCTIVO
		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
		} else {
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
		}
	}
}

Se puede testear el programa compilando y corriendo solucion-basica.c .

Razonando sobre la corrección del algoritmo

Primera Parte

Lo primero que habria que considerar es si la función esta_en_lista() es correcta. No voy a hacer un análisis muy formal, pero supongamos los posibles casos:

  • pasados es una lista vacia: Se ejecuta el primer if: if(rList == NULL) , se crea un nodo nuevo que se agrega a pasados y se devuelve -1.
  • pasados no es una lista vacia y el valor existe en la lista:, se ejecuta el primer if y devuelve falso, se ejecuta la sentencia: while(rList != NULL) , se itera por todos los nodos hasta que se encuentra el nodo en el que pre-existe el valor, se llega a la condición: if(rList->value == value) y se devuelve 1.
  • pasados no es una lista vacia, el valor no existe en la lista y es menor a cualquier valor de la lista: se llega al while, en la primera iteración se llega a la condición: if(rList->value > value), se crea el nuevo nodo, se le agrega el resto de la lista como nodo hijo y se evalua la condición: if(prev==NULL), como prev fue inicializado a NULL y es la primera iteración, se asigna este nuevo nodo a pasados y se devuelve -1.
  • pasados no es una lista vacia, el valor no existe en la lista y esta entre medio de 2 valores de la lista: se llega al while, se itera por los nodos hasta que se llega a la condición: if(rList->value > value), se crea el nuevo nodo, se le agrega el resto de la lista como nodo hijo y se evalua la condición: if(prev==NULL), como prev esta apuntando al nodo pàdre del actual, se asigna este nuevo nodo como hijo de prev y se devuelve -1.
  • pasados no es una lista vacia, el valor no existe en la lista y es mayor a cualquier valor de la lista: se llega al while, se itera por los nodos hasta que se recorre toda la lista y se sale del while, se crea el nuevo nodo, se le agrega null como nodo hijo y se evalua la condición, se asigna este nuevo nodo como hijo de prev (que en este momento es el ultimo nodo de la lista) y se devuelve -1.

Razonar sobre la corrección del valor que devuelve (1 o -1) es trivial. Asi como razonar que no agrega un valor que ya existe.

Lo que es importante ver es que si se llama a la función con una lista ordenada y un valor que no existe en la misma, por los 3 ultimos casos (y el primero siendo estrictos, ya que una lista vacia es una lista ordenada), a esta lista se le agrega el valor en orden.

Segunda parte

Asumiendo que la función anterior es correcta y que la función esta_en_lista() devuelve un valor correcto y asi mismo que en sucesivas llamadas a la lista pasados se guardan en esta todos los elementos anteriores, podemos razonar sobre la función sacar_duplicados() que es la que nos importa.

La función es recursiva, por lo que para pensar sobre su corrección alcanza con hacer induccion para demostrar que la función retorna la misma lista sin duplicados. Voy a hacer un esquema del razonamiento que nos llevaria a una demostracion.

Paso base

El paso base es que la lista esta vacia. En ese caso se retorna una lista vacia, como una lista vacia es una lista sin duplicados, no hay nada más que demostrar. El codigo que soporta este caso es:


	//Caso Base
	if( (*lista) == NULL) {
		return lista;
	} 

Paso Inductivo

Ahora tenemos que demostrar que si llamamos a la funcion con una lista con n elementos sin duplicados entonces llamando a la función con la lista con n+1 elementos tambien se retorna una lista sin duplicados.

Para razonar sobre esto alcanza pensar que en el caso en que se llama a la función con (n+1) elementos, se llega a la siguiente porción de codigo:


		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
		} else {
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
		}

Analizemos los dos casos:

  • Si el valor (n+1) ya existe en la lista, se devuelve la lista hasta n. Como por la hipótesis inductiva, la lista hasta n es una lista sin duplicados y se devuelve esta, la lista que se devuelve en la llamado con n+1 elementos es así mismo una lista sin duplicados.
  • Si el valor (n+1) no existe en la lista, se devuelve la lista hasta n mas el elemento n+1. Como por la hipótesis inductiva, la lista hasta n es una lista sin duplicados y por asunción de caso el elemento nuevo no existe en la lista hasta n, la lista que se devuelve en la llamado con n+1 elementos es una lista sin duplicados.

Por exhaustación de casos, se comprueba que se cumple el paso inductivo.

Algunas observaciones sobre el algoritmo

El proximo paso y va ser el siguiente post es analizar la complejidad del algoritmo y despues buscar formas de mejorarlo. Como observaciones basicas se puede ver que llamando a la función sacar_duplicados() con una lista con n elementos, se itera (recursivamente) por cada uno de los n elementos de la lista, por otro lado la lista pasados va creciendo con cada llamado a esta_en_lista() que tiene un elemento nuevo y en todo caso de que este elemento sea mayor a cualquiera de los j elementos anteriores de pasados, esta_en_lista() itera por cada uno de los j elementos de pasados. Es pensando en estos temas que vamos a encarar el siguiente post.

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994

Autor: Emiliano Martínez Luque.

Comments Off on Problema de Algoritmia Básico: Primera Solución

Usando linked lists para trabajar con polinomios

Icono de Post August 13 2009 :: c, Estructuras de datos ::

Uno de las cosas fascinantes del Mathematica y ( ahora del wolfram alpha ) es como resuelve y además simplifica expresiones matemáticas (por ejemplo: derivando funciones y dando cada uno de los pasos). Se usa de esta manera la computadora no para hacer cálculos numéricos ( que arrojen como resultado un número ) sino para computación simbólica ( cálculos que arrojan como resultado una expresión matemática ).

La pregunta es como una maquina que guarda resultados en memoria en forma de expresiones binarias ( esencialmente números, aunque pueden representar otra cosa ) para hacer esto. La respuesta es que la representación de formulas matemáticas puede ser realizada a través de diferentes estructuras de datos y es manipulando estas estructuras que se pueden realizar estos cómputos.

Como un ejemplo básico de esto acá va un ejemplo sacado de C & Data Structures sobre como se pueden hacer operaciones sobre polinomios.

Una estructura de datos para guardar un polinomio y las funciones para llenarlo y mostrarlo.



# include <stdio.h>

# include <stdlib.h>

struct pnode

   {

      int exp;

      int coeff;

      struct pnode *link;

   };

struct pnode *insert(struct pnode *p, int e,int c) {

   struct pnode *temp;

   temp = p;

   if(p==NULL) {

      p=(struct pnode *)malloc(sizeof(struct pnode));

      if(p==NULL) {

         printf("Error de alocación de memorian");

         exit(0);

      }

      p-> exp = e;

      p->coeff = c;

      p-> link = NULL;

   } else {

        //Si tienen el mismo exponente se suman los coeficientes en vez de agregar un nodo.

       if(p->exp == e) {

            p->coeff = p->coeff + c;

       } else {

            p->link = insert(p->link, e, c);

       }

   }

   return (p);

}



void printpoly ( struct pnode *p ) {

      printf("The polynomial isn");

      while (p!= NULL) {

        if(p->exp != 1) {

            printf("%dx^%dt", p->coeff, p-> exp);

        } else {

            printf("%dxt", p->coeff);

        }

        p = p-> link;

      }

      printf("n");

}

Nota: en la función de insertar si un nuevo termino tiene el mismo exponente que uno anterior se lo suma en vez de agregarlo. Esto es una de las modificaciones al código del libro.

Ordenando el polinomio



/* a function to sort a list */

struct pnode *sortpoly(struct pnode *p)

{

   struct pnode *temp1,*temp2,*max,*prev,*q;

   q = NULL;

   while(p != NULL) {

      prev = NULL;

      max = temp1 = p;

      temp2 = p -> link;

      while ( temp2 != NULL ) {

         if(max -> exp < temp2 -> exp) {

            max = temp2;

            prev = temp1;

         }

         temp1 = temp2;

         temp2 = temp2-> link;

      }

      if(prev == NULL) {

            p = max -> link;

       }  else {

            prev -> link = max -> link;

       }

       max -> link = NULL;

        if( q == NULL) {

            q = max;

        } else {

            temp1 = q;

            while( temp1 -> link != NULL) {

                temp1 = temp1 -> link;

            }

            temp1 -> link = max;

        }

    }

    return (q);

}

Una Función para sumar 2 polinomios



/* A function to add two polynomials */

   struct pnode *polyadd(struct pnode *p, struct pnode *q)

   {

      struct pnode *r = NULL;

      int e;

      int c;

      while((p!=NULL) && (q != NULL)) {

            //p mayor exponente que q

            if(p->exp > q->exp) {

                r = insert(r,p->exp,p->coeff);

                p = p->link;



            //q mayor exponenete que p

            } else if(p->exp < q->exp) {

                r = insert(r,q->exp,q->coeff);

                q = q->link;



            //mismo exponente

            } else {

                c = p->coeff + q->coeff;

                e = q->exp;

                r = insert( r, e,c);

                p = p->link;

                q = q->link;

            }

      }

   //Lo que quede de ambos polinomios

    while(p != NULL) {

        r = insert( r, p->exp,p->coeff);

        p = p->link;

    }

    while(q!=NULL) {

        r = insert( r, q->exp,q->coeff);

        q = q->link;

    }

   return(r);

}

Una función para multiplicar polinomios.

Teniendo una función insertar que sume los términos del mismo exponente y una función de suma es muy fácil agregar una función que multiplique polinomios.



struct pnode *polymult(struct pnode *p, struct pnode *q) {

    struct pnode *r, *r2, *temp;

    r = NULL;

    temp = q;

    while(p != NULL) {

        temp = q;

        while(temp != NULL) {

            r = insert(r, (temp->exp + p->exp), (temp->coeff * p->coeff));

            temp = temp->link;

        }

        p = p->link;

    }

    return r;

}

Probando el programa



int main()

   {

         int e;

         int n,i, c;

         struct pnode *poly1 = NULL ;

         struct pnode *poly2=NULL;

         struct pnode *result;

         printf("Enter the terms in the polynomial1 n");

         scanf("%d",&n);

         i=1;

         while ( n-- > 0 )

         {

      printf( "Enter the exponent and coefficient of the term number %dn",n);

               scanf("%d %d",&e,&c);

               poly1 = insert ( poly1,e,c);

         }

        printf("Enter the terms in the polynomial2 n");

         scanf("%d",&n);

         i=1;

         while ( n-- > 0 )

         {

      printf( "Enter the exponent and coefficient of the term number %dn",n);

               scanf("%d %d",&e,&c);

               poly2 = insert ( poly2,e,c);

         }

         poly1 = sortpoly(poly1);

         poly2 = sortpoly(poly2);

         printf("The polynomial 1 isn");

         printpoly ( poly1 );

         printf("The polynomial 2 isn");

         printpoly ( poly2 );

         result = polyadd(poly1,poly2);

         printf("The result of addition isn");

         printpoly ( result );

         result = polymult(poly1, poly2);

         printf("The result of multiplication isn");

         printpoly ( result );

         return 0;

   }

Resultados


Enter the terms in the polynomial1 
5
Enter the exponent and coefficient of the term number 4
5 5
Enter the exponent and coefficient of the term number 3
4 4
Enter the exponent and coefficient of the term number 2
3 3
Enter the exponent and coefficient of the term number 1
2 2
Enter the exponent and coefficient of the term number 0
1 1
Enter the terms in the polynomial2 
2
Enter the exponent and coefficient of the term number 1
2 2
Enter the exponent and coefficient of the term number 0
1 1
sdfsdfThe polynomial 1 is
The polynomial is
5x^5	4x^4	3x^3	2x^2	1x	
The polynomial 2 is
The polynomial is
2x^2	1x	
The result of addition is
The polynomial is
5x^5	4x^4	3x^3	4x^2	2x	
The result of multiplication is
The polynomial is
10x^7	13x^6	10x^5	7x^4	4x^3	1x^2	

Pensando en todo esto es interesante en como en MathML se usan estructuras arboreas ( MathML esta basado en XML ) para representar expresiones matematicas y las implicaciones que puede tener a futuro para la automatización de determinado tipo de calculos.

Referencias

C & Data Structures, Deshpande, Kakde; Charles River Media, 2004

Autor: Emiliano Martínez Luque.

Comments Off on Usando linked lists para trabajar con polinomios

Analizando los punteros de una linked list

Icono de Post August 10 2009 :: c, Estructuras de datos ::

Uno de los temas que es difícil de entender en C es el tema de los punteros y como se relacionan con las estructuras de datos. Lo difícil ( o por lo menos fue difícil para mi que venia de lenguajes dinámicos ) es entender que los punteros guardan direcciones a memoria y a que a partir de esto se puede hacer el entrelazamiento de diferentes estructuras apuntadas. Voy a usar los ejemplo de linked list de C & Data Structures para mostrar como se da esto.

Primero creamos la estructura y una función para insertar elementos en la misma:

struct node {

   int data;

   struct node *link;

};



/*Insert en versión recursiva */

struct node *insert(struct node *p, int n) {

   if(p==NULL) {

      p=(struct node *)malloc(sizeof(struct node));

      if(p==NULL) {

        printf("Allocation Errorn");

         exit(0);

      }

      p-> data = n;

      p-> link = NULL;

   } else {

       p->link = insert(p->link,n);

    }

      return(p);

}

Nota: Se hace la búsqueda del ultimo nodo para insertar en forma recursiva.

Luego hago una función para mostrar la lista:

void printnode( struct node *p) {

    printf("Memory Space: %pt Value: %d t Link: %ptn",p, p-> data, p-> link);

}



void printlist ( struct node *p ) {

      printf("The data values in the list aren");

      while (p!= NULL) {

         printnode(p);

         p = p-> link;

      }

}

La función printnode, muestra primero la dirección de memoria de la estructura, después su valor y finalmente la dirección de memoria a la que apunta, de esta manera podemos ver como se enlazan los nodos dentro de la lista.

Agregando y borrando nodos.

   /* a function which inserts a newly created node after the specified

node */

    //node_no empieza en 0 como en los arrays

   struct node * newinsert ( struct node *p, int node_no, int value ) {

      struct node *temp, * temp1;

      int i;

      temp = p;



      for(i=0; i<node_no && temp->link != NULL; i++) {

            temp = temp->link;

      }

        if(i != node_no ) {

            printf("Se pide insertar en un nodo mayor a la cantidad existente, se agrega tras el ultimo nodo existente.n");

        }

        temp1 = ( struct node * )malloc ( sizeof ( struct node ));

        if ( temp1 == NULL ) {

            printf( " Cannot allocate n");

            exit (0);

        }

        temp1->data = value;

        temp1->link = temp->link;

        printf("The newly created node to be inserted is:n");

        printnode(temp1);

        temp->link = temp1;

        return(p);

   }



   struct node * erasenode( struct node *p, int node_no) {

        struct node *temp, *prev;

        int i;

        temp = p;

        if(node_no == 0) {

            temp = p->link;

            free(p);

            p = temp;

        } else {

            i = 0;

            while(i<node_no && temp->link != NULL) {

                prev = temp;

                temp = temp->link;

                i++;

            }

            if(i != (node_no)) {

                printf("Se pide borrar un nodo que no existe.n");

                exit(0);

            }

            prev->link = temp->link;

            free(temp);

        }

        return(p);

   }

Corriéndolo en el main:

int main()

{

      int n;

      int x;

      struct node *start = NULL ;

      printf("Enter the nodes to be created n");

      scanf("%d",&n);

      while ( n-- > 0 )

      {

              printf( "Enter the data values to be placed in a noden");

         scanf("%d",&x);

         start = insert ( start,x);

      }

      printf("The created list isn");

      printlist ( start );

      start = newinsert(start, 2, 7);

      printlist (start);

      start = erasenode(start, 2);

      printlist ( start );

      return 0;

}

Resultado en pantalla:

Enter the nodes to be created 
5
Enter the data values to be placed in a node
5
Enter the data values to be placed in a node
4
Enter the data values to be placed in a node
3
Enter the data values to be placed in a node
2
Enter the data values to be placed in a node
1
The created list is
The data values in the list are
Memory Space: 0x81a5008	 Value: 5 	 Link: 0x81a5018	
Memory Space: 0x81a5018	 Value: 4 	 Link: 0x81a5028	
Memory Space: 0x81a5028	 Value: 3 	 Link: 0x81a5038	
Memory Space: 0x81a5038	 Value: 2 	 Link: 0x81a5048	
Memory Space: 0x81a5048	 Value: 1 	 Link: (nil)	
The newly created node to be inserted is:
Memory Space: 0x81a5058	 Value: 7 	 Link: 0x81a5038	
The data values in the list are
Memory Space: 0x81a5008	 Value: 5 	 Link: 0x81a5018	
Memory Space: 0x81a5018	 Value: 4 	 Link: 0x81a5028	
Memory Space: 0x81a5028	 Value: 3 	 Link: 0x81a5058	
Memory Space: 0x81a5058	 Value: 7 	 Link: 0x81a5038	
Memory Space: 0x81a5038	 Value: 2 	 Link: 0x81a5048	
Memory Space: 0x81a5048	 Value: 1 	 Link: (nil)	
The data values in the list are
Memory Space: 0x81a5008	 Value: 5 	 Link: 0x81a5018	
Memory Space: 0x81a5018	 Value: 4 	 Link: 0x81a5058	
Memory Space: 0x81a5058	 Value: 7 	 Link: 0x81a5038	
Memory Space: 0x81a5038	 Value: 2 	 Link: 0x81a5048	
Memory Space: 0x81a5048	 Value: 1 	 Link: (nil)	

Se ve aca como en la primera corrida los nodos estan ubicados uno tras otro en la memoria, pero al agregar un nuevo nodo se salta en el tercer nodo ( en este caso, Memory Space: 0x81a5028 Value: 3 Link: 0x81a5058 ) se salta al agregado ( Memory Space: 0x81a5058 Value: 7 Link: 0x81a5038 ) y del agregado al que antes existia contiguamente ( Memory Space: 0x81a5038 Value: 2 Link: 0x81a5048 ). Algo similar ocurre cuando se borra un nodo.

Revirtiendo y ordenando la lista.

/* a function to sort reverse list */

struct node *reverse(struct node *p) {

   struct node *prev, *curr;

   prev = NULL;

   curr = p;

   while (curr != NULL) {

      p = p-> link;

      curr-> link = prev;

      prev = curr;

      curr = p;

   }

   return(prev);

}



/* a function to sort a list */

struct node *sortlist(struct node *p)

{

   struct node *temp1,*temp2,*min,*prev,*q;

   q = NULL;

   while(p != NULL) {

      //Encontrar el menor de la lista p

      prev = NULL;

      min = temp1 = p;

      temp2 = p -> link;

      while ( temp2 != NULL ) {

              if(min -> data > temp2 -> data) {

                     min = temp2;

                     prev = temp1;

            }

         temp1 = temp2;

         temp2 = temp2-> link;

      }



      //Cambiar el link en la lista p del previo al menor al siguiente del menor

      if(prev == NULL) {

             p = min -> link;

      } else {

             prev -> link = min -> link;

      }



      //Agregar el menor a q

      min -> link = NULL;

      if( q == NULL){

            q = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q as a first node*/

       } else {

            temp1 = q;

            /* traverses the list pointed to by q to get pointer to its last node */

            while( temp1 -> link != NULL) {

                         temp1 = temp1 -> link;

            }

            temp1 -> link = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q at the end of list pointed by q*/

      }

   }

   return (q);

}

Vemos la impresión en pantalla de como quedan ordenados los nodos:

The sorted list is
The data values in the list are
Memory Space: 0x8c03048	 Value: 1 	 Link: 0x8c03038	
Memory Space: 0x8c03038	 Value: 2 	 Link: 0x8c03018	
Memory Space: 0x8c03018	 Value: 4 	 Link: 0x8c03008	
Memory Space: 0x8c03008	 Value: 5 	 Link: 0x8c03058	
Memory Space: 0x8c03058	 Value: 7 	 Link: (nil)	
The reversed list is
The data values in the list are
Memory Space: 0x8c03058	 Value: 7 	 Link: 0x8c03008	
Memory Space: 0x8c03008	 Value: 5 	 Link: 0x8c03018	
Memory Space: 0x8c03018	 Value: 4 	 Link: 0x8c03038	
Memory Space: 0x8c03038	 Value: 2 	 Link: 0x8c03048	
Memory Space: 0x8c03048	 Value: 1 	 Link: (nil)	

Referencias

C & Data Structures, Deshpande, Kakde; Charles River Media, 2004

Autor: Emiliano Martínez Luque.

Comments Off on Analizando los punteros de una linked list

Definición de estructura de datos recursiva

Icono de Post August 10 2009 :: Estructuras de datos ::

A recursive data structure is a data structure that has the same form regardless of the size of the data.

Como ejemplo: linked list, arbol binario, etc.

P S Deshpande, O G Kakde: C & Data Structures

Iterando por una matriz cuadrada recursivamente

Icono de Post June 5 2009 :: Algoritmia, Estructuras de datos, Java, Lógica ::

En otro ejercicio de la facultad se me pedía sumar todos los valores individuales de una matriz cuadrada a través de un algoritmo recursivo. Mi resolución en Java fue la siguiente:


	public static int sumaMatriz(int arr2[][], int m, int n) {
		if( (m == n) && (m == 0) ) return arr2[m][n];
		if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
		if(m > n) {
			if(n > 0) {
				return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b
			} else {	
				return arr2[m][n];
			}
		} else { //n > m
			if(m > 0) {
				return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c
			} else {
				return arr2[m][n];
			}
		}
	}

Me interesa este ejercicio para pensar de otra forma sobre corrección de programas. La pregunta es si el algoritmo es correcto y después de pensarlo un poco llegue a la conclusión de que lo era. Por lo pronto para hacer una demostración formal debería usar inducción estructural pero este post trata más bien sobre trabajo previo a una demostración, lo que en How to Prove it llaman scratchwork. O sea el razonamiento a través del cual se llega a una demostración.

Primero que nada hagamos un poco de debugging con un caso simple de una matriz de 3x3. Para esto agregamos lo siguiente al código anterior:


	public static int sumaMatriz(int arr2[][], int m, int n) {
		if( (m == n) && (m == 0) ) return arr2[m][n];
		System.out.println(n + " " + m);
		if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
		if(m > n) {
....
....

Y testeamos la función llamándola con:


public class TP4 {

	public static void main (String[] args) {
		int[][] arr2;
		arr2 = new int[3][3];
		arr2[0][0] = 1;
		arr2[0][1] = 2;
		arr2[0][2] = 2;
		arr2[1][0] = 4;
		arr2[1][1] = 2;
		arr2[1][2] = 3;
		arr2[2][0] = 4;
		arr2[2][1] = 7;
		arr2[2][2] = 8;
		System.out.println("Ej9:");
		System.out.println( TP4.sumaMatriz(arr2,2 ,2));
	}
}

Lo que muestra por consola es:


Ej9:

2 2
2 1
2 0
1 1
1 0
0 0
0 1
1 2
0 2

33

Podemos ver que todos los elementos de la matriz fueron accedidos y que el resultado es el correcto. Ahora imaginémonos el árbol de las llamadas de función.

Vemos que los elementos de la diagonal principal hacen 3 llamados más, al próximo elemento de la diagonal principal, y a los dos elementos con m o n decrementados en uno. Mientras que los elementos que no están en la diagonal principal hacen un solo llamado.

Razonamiento (Informal) sobre la corrección del Algoritmo

Consideremos una matriz cuadrada de grado m, tal que m sea mayor que 5 (esto es por claridad para hacer este ejercicio) y concentrémonos en los últimos 5x5 casilleros del limite inferior derecho, que es donde comienza el algoritmo.

Primer paso toma el elemento en m x m:

A partir de esto se realiza la llamada recursiva:


if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a

De la que se desprenden los siguientes 3 pasos.

El caso b:


return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b

De nuevo el caso a:


if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a

Y finalmente el caso c:


				return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c

Hemos llegado a llenar una matriz de 3x3, pero esto no nos demuestra nada, ahora lo interesante es saber que pasa cuando continua el algoritmo en los pasos siguientes y aquí es donde esta el truco.

Lo interesante es que las 3 posibles llamadas recursivas garantizan la siguiente:

  • Por el caso a, desde una llamada de la función desde un casillero en la diagonal principal, no se llamara a la función en ningún casillero que este en la misma linea o columna de los elemento de donde han sido llamados por un casillero en la diagonal principal anterior.También por el caso a, la iteración a través de elementos de la diagonal principal eventualmente cubrirá todos los elementos de la diagonal principal de la matriz.

  • Por el caso b, desde una llamada de la función desde un casillero en una columna que no sea en la diagonal principal, siempre continuara por esa misma columna hasta completarla.

  • Por el caso c, desde una llamada de la función desde un casillero en la fila que no sea en la diagonal principal, siempre continuara por esa misma fila hasta completarla.

A partir de esto podemos inferir que el algoritmo pasa por todos los elementos de cualquier matriz cuadrada.

Importante

Quiero recalcar que esto es un razonamiento, a partir del cual por inducción estructural podría construirse una demostración, pero en términos de lógica formal no es una demostración. Igual, no deja de ser un razonamiento valido, lo cierto es que en la programación como practica es importante poder pensar si lo que se esta haciendo es correcto y si los programas que uno hace cumplen con las necesidades que uno tiene, pero también es cierto que sería completamente Overkill el tener que hacer una demostración formal de cada programa que uno hace. Lo importante es tener herramientas para poder razonar y pensar sobre como se programa.

Autor: Emiliano Martínez Luque.

Comments Off on Iterando por una matriz cuadrada recursivamente

Implementación de una Cola ( Quee ) sobre un array

Icono de Post March 13 2009 :: c, Estructuras de datos ::

Esta es una variación de la implementación en el libro C & Data Structures de una cola ( FIFO ) construida sobre un array. Me intereso esa estructura de datos por 2 cosas. Primero, el hecho de que la estructura de datos era más que el array donde se guardaban los datos, necesitándose una serie de variables asociados para usarlo y segundo el uso de la aritmética mod( n ) para moverse entre las posiciones del array.

Sin embargo, existen una serie de errores en la implementación del ejemplo y además considerando que se utilizan un conjunto de variables para definir el funcionamiento de la estructura, lo lógico sería agrupar todas estas variables dentro de un struct de C. Así que esta es mi implementación, que además fue un buen ejercicio para repasar la sintaxis de punteros y de structs en C:


#include <stdio.h>
#include <stdlib.h>
#define MAX 10 /* The maximum size of the queue */

struct ca {
	int cola[ MAX ];
	int fin;
	int frente;
	int num_elems;
};
typedef struct ca cola_array;


void insert( cola_array *carr, int value ) {
	if(carr->frente == carr->fin && carr->num_elems > 0) {
		printf("Cola Llenan");
	} else {
		carr->cola[ carr->fin ] = value;
		carr->fin = ( carr->fin + 1) % MAX;
		carr->num_elems ++;
	}
}

int delete( cola_array *carr ) {
	int temp;
	if( carr->num_elems == 0 ) {
		printf("Cola Vacian");
		return -1;
	} else {
		temp = carr->cola[ carr->frente ];
		carr->frente = ( carr->frente + 1) % MAX;
		carr->num_elems--;
		return temp;
	}
}

void listar( cola_array *carr ) {
	int x;
	if( carr->num_elems == 0 ) {
		printf("Cola Vacia");
	} else {
		printf("Numero de Elementos: %dt Frente: %dt Fin: %dn", carr->num_elems, carr->frente, carr->fin);
		for( x = 0; x < carr->num_elems; x++) {
			printf("%dt", carr->cola[ ( x + carr->frente ) % MAX  ]);		
		}
	}
	printf("n");
}

int main()
{
	int menu, value;
	cola_array carr;
	carr.fin = carr.frente = carr.num_elems = 0;
	do {
		printf("Seleccione:n");
		printf("1. Insertarn");
		printf("2. Borrarn");
		printf("3. Listarn");
		printf("4. Salirn");
		scanf("%d", &menu);
		switch(menu) {
			case 1: 
				printf("Valor a Insertar (Mayor o Igual que 0): n");
				scanf("%d", &value);
				insert( &carr, value);
			break;
			case 2: 
				value = delete( &carr );
				if(value >= 0) {
					printf("Valor borrado: %d n", value);
				}
			break;
			case 3:
				listar( &carr );
			break;
			case 4: 
				return(0);
			break;
			default:
				printf("Opcion no Valida.n");
			break;
		}
	} while( menu != 4 );
	return(0);
}

La parte que me gusto hacer es:


		for( x = 0; x < carr->num_elems; x++) {
			printf("%dt", carr->cola[ ( x + carr->frente ) % MAX  ]);		
		}

Y en particular ( x + carr->frente ) % MAX por el uso de la aritmética mod( n ) que me hizo recordar al concepto de clases de equivalencias de Algebra.

Explicación

Supongamos que la cola tiene 5 elementos (sobre un máximo de 10), pero como la cola ya se estuvo utilizando quedaron ubicados los 2 primeros en las posiciones 8 y 9 del array y los 3 últimos en las posiciones 0 a 2. El loop va a iterar a x de 0 a 4, cuando x este en 0 ( x + carr->frente ) % MAX va a equivaler a 8, cuando este en 1 a 9; pero cuando llegue a 2, ( x + carr->frente ) equivale a 10 y 10 % MAX equivale a 0.

Esto es así porque en la 0/10, 10/10, 20/10.. etc, tienen exactamente el mismo resto, 0; de la misma manera que 1/10, 11/10, 21/10.. etc tienen todos resto 1. ( La operación % establece clases de equivalencia sobre N). Lo que permite moverse circularmente sobre el array.

Autor: Emiliano Martínez Luque.

Comments Off on Implementación de una Cola ( Quee ) sobre un array