Archive for the ‘C’ Category

Diferencia entre un contador y un acumulador

agosto 19, 2017

En programación es común el uso de contadores y acumuladores, en este post explico la diferencia porque frecuentemente quienes están aprendiendo a programar confunden unos con otros.

Un contador es una variable que se utiliza para contar algo. Normalmente usamos un contador dentro de un ciclo y cambiamos su valor sumándole o restándole una constante, es decir, siempre se le suma o resta la misma cantidad. El caso más utilizado es incrementar la variable en uno.

En el siguiente programa en C se tiene un arreglo de 10 números enteros y se utiliza un ciclo con un contador para ver cuántas veces aparece el número 3.

Programa contador.c
#include <stdio.h>

int main()
{
 int numero = 3;
 int x=0, contador=0;
 int arreglo[10]={3,7,1,2,7,3,5,6,-2,7};
 
 // Recorre el arreglo y cuenta cuántas veces aparece el valor que contiene la variable numero 
 for (x=0; x<10; ++x)
     {
      if (arreglo[x] == numero)
          /* El nuevo valor de la variable contador va a ser igual a su valor actual más uno
             Se puede escribir como preincremento ( ++contador ) o como postincremento ( contador++ )
             pero para que sea bastante evidente, lo escribí de forma explícita ( contador = contador+1 )
          */
          contador = contador+1; 
     }
 
 printf("\n");
 printf("El número %d aparece %d veces en el arreglo\n", numero, contador);
 
 return 0;
}

El siguiente programa en C es un ejemplo de un contador que se va decrementando en uno; simula una cuenta regresiva.

Programa cuenta_regresiva.c
#include <stdio.h>

int main()
{
 int contador=10;
 
 // Imprime los números del 10 al cero
 while (contador >= 0)
       {
        printf("Despegue en %d\n", contador);
        contador = contador-1;
       }
 
 return 0;
}

Un acumulador es una variable que se utiliza para sumar valores. Al igual que el contador, se utiliza normalmente dentro de un ciclo pero cambiamos su valor sumándole una variable, es decir, no siempre se le suma la misma cantidad.

En el siguiente programa, utilizamos el mismo arreglo del programa contador.c, pero ahora no vamos a contar cuántas veces aparece un número x, sino que vamos a sumar todos los valores que aparezcan en el arreglo y que sean mayores a un número determinado.

Programa acumulador.c
#include <stdio.h>

int main()
{
 int mayores_que = 3;
 int x=0, suma=0;
 int arreglo[10]={3,7,1,2,7,3,5,6,-2,7};
 
 // Recorre el arreglo y suma todos los números mayores al valor que contiene la variable mayores_que 
 for (x=0; x<10; ++x)
     {
      if (arreglo[x] > mayores_que)
          /* El nuevo valor de la variable suma va a ser igual a su valor actual más el número 
             que se encuentra en la posición actual del arreglo
          */
          suma = suma+arreglo[x]; 
     }
 
 printf("Todos los números mayores a %d en el arreglo suman %d\n", mayores_que, suma);
 
 return 0;
}
Anuncios

Pasar arreglos a una función en C

noviembre 29, 2012

Por default, los arrreglos en C se pasan a una función como referencia y no como valor. Esto significa que todas las modificaciones que hagamos dentro de la función en C al arreglo que recibimos como parámetro, realmente se realizan en el arreglo original que se utilizó como argumento al momento de llamar a la función.

Al escribir una función en C, la forma de indicar que uno de los parámetros que se va a recibir es un arreglo de una dimensión, es decir de que tipo va a ser el arreglo y el nombre con el cual vamos a manipular dicho arreglo dentro de nuestra función seguido de corchetes que abren y cierran; nuestra función también debe recibir un segundo parámetro que nos indique el tamaño del arreglo, o dicho de otra forma, el número de elementos de los que consta nuestro arreglo, recordemos que como el arreglo se pasa a la función como referencia, lo que esta recibiendo la función en realidad es un apuntador al primer elemento del arreglo, pero no sabe en donde termina el arreglo, por eso es necesario que la función también reciba como parámetro el número de elementos del arreglo.

Por ejemplo, el prototipo de una función en C que va a regresar un entero y va a recibir un arreglo de 10 elementos de tipo entero sería algo asi:

int MiFuncion(int mi_arreglo[], int num_elemetos);

Para llamar a la función anterior, se pone como primer argumento el nombre del arreglo (sin corcehetes) y como segundo argumento el número de elementos del arreglo. Supongamos que tenemos un arreglo de 10 elementos de tipo entero llamado numeros y queremos guardar en una variable llamada “x” el valor que nos regresa la función “MiFuncion” al llamarla pasandole como argumentos el arreglo “numeros”, haríamos algo como esto

x = MiFuncion(numeros, 10);

El siguiente programa solicita al usuario que ingrese 10 números de tipo entero y los almacena en un arreglo; después le pide que introduzca un número para que busque su posición dentro del arreglo..

El programa utiliza una función llamada BuscaNumero que recibe como parámetros el arreglo con los 10 números capturados, el número de elementos del arreglo (en este caso 10) y el número del cual se desea saber su posición dentro del arreglo.. La función regresa -1 si el número que se busca no se encuentra en el arreglo y en caso contrario, regresa la primera posición del arreglo que contiene dicho número.

El programa también utiliza una función llamada MuestraArreglo que no regresa valor alguno, sólo recibe como parámetros el arreglo y el número de elementos. Esta función imprime en pantalla los elementos del arreglo separados por un tabulador.

#include <stdio.h>

int BuscaNumero(int valores[], int tamanio, int busca)
{
int i=0, posicion=-1;

do
  {
   if (valores[i]==busca)
       posicion=i;
   else
       ++i;
  }
while(i<tamanio && posicion<0);

return posicion;
}

void MuestraArreglo(int valores[], int tamanio)
{
 int i=0;

 for (i=0; i<tamanio; ++i)
      printf("%d\t",valores[i]);
 printf("\n");
}

int main()
{
 int x=0, numero=0, posicion=0;
 int ar_numeros[10] = {0};

 printf("Introduzca los 10 numeros enteros que se almacenaran en el arreglo\n");
 for (x=0; x<10; ++x)
     {
      printf("Valor para el elemento [%d]: ", x);
      scanf("%d",&ar_numeros[x]);
     }
 printf("\n");

 printf("Introduzca el número que desea buscar en el arreglo\n");
 scanf("%d",&numero);
 printf("\n");
 MuestraArreglo(ar_numeros,10);

 posicion=BuscaNumero(ar_numeros,10,numero);
 if (posicion != -1)
     printf("El número %d está en la posición %d del arreglo\n",numero, posicion);
 else
     printf("El número %d no está en el arreglo\n",numero);

 return 0;
}

Para pasar a una función un arreglo de dos dimensiones, si debemos indicar el tamaño de la segunda dimensión del arreglo

Ejemplo:int MiFuncion(int mi_arreglo[][5], int num_elemetos);

El siguiente programa le pide al usuario que introduzca 9 números y los almacena en un arreglo de dos dimensiones, en este caso una matriz de 3×3; posteriormente utiliza una función llamada ImprimeMatriz para mostrar como quedaron almacenados los números en la matriz. Dicha función recibe como parámetros, la matriz de 3×3 y el tamaño de la primera dimensión (normalmente la primera dimensión son filas y la segunda dimensión columnas).

#include <stdio.h>

void ImprimeMatriz(int m[][3], int filas)
{
 int i=0,j=0;

 for (i=0; i<filas; ++i)
     {
      for (j=0; j<3; ++j)
          {
           printf("%d ",m[i][j]);
          }
      printf("\n");
     }
}

int main()
{
 int x=0,y=0;
 int matriz[3][3] = {{0},{0},{0}};

 printf("Introduzca los valores para la matriz\n");
 for (x=0; x<3; ++x)
     {
      for (y=0; y<3; ++y)
          {
           printf("Valor para el elemento [%d][%d]: ", x, y);
           scanf("%d",&matriz[x][y]);
          }
      printf("\n");
     }

 printf("Matriz\n");
 ImprimeMatriz(matriz, 3);

 return 0;
}

Implementación de pilas con apuntadores en C

octubre 21, 2011

En este post muestro como implementar las funciones push y pop para el manejo de pilas, y dos problemas clásicos que se pide se solucionen utilizando pilas.

El siguiente archivo contiene la implementación de las funciones push y pop para ser utilizadas con caracteres

//Archivo pila_char.h
#include <stdio.h>
#include <stdlib.h>

typedef struct nodo_s
{
 char dato;
 struct nodo_s *siguiente;
} nodo_t;

typedef nodo_t *ptrNodo;
typedef nodo_t *ptrPila;

/*
    Agrega un nodo al inicio de la lista ligada
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
void push(ptrPila *pila, char x)
{
 // Crea un nuevo nodo
 ptrNodo nodo;
 nodo = (ptrNodo)malloc(sizeof(nodo_t));
 if (nodo != NULL)
    {
     nodo->dato = x;
     // El apuntador nodo->siguiente va a apuntar al primer nodo de la lista ligada
     nodo->siguiente = *pila;
     // pila va a apuntar al nuevo nodo, con esto hacemos que el nuevo nodo sea ahora el primer nodo de la lista ligada
     *pila=nodo;
    }
}

/*
    Elimina el primer nodo de la lista ligada
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
char pop(ptrPila *pila)
{
 // Crea un nuevo nodo
 ptrNodo nodo;
 char x;
 
 // El nuevo nodo va a apuntar al primer nodo de la lista ligada
 nodo = *pila;
 x = (*pila)->dato;
 // Ahora el segundo nodo de la lista ligada va a ser el primero
 *pila = (*pila)->siguiente;
 // Borra el primer nodo de la lista ligada
 free(nodo);
 // Regresa el valor que contenía el nodo que se eliminó
 return x;
}

/*
    Regresa 1 si no hay nodos en la lista ligada y cero en caso contrario
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
int pila_vacia(ptrPila *pila)
{
 return (*pila == NULL ? 1:0);
}

/*
   Muestra los datos de los nodos
*/ 
void nodos_pila(ptrNodo nodo)
{
 if (nodo == NULL)
     printf("La pila está vacia\n");
 else
     {
      while (nodo != NULL)
            {
             printf("%c\n",nodo->dato);
             nodo = nodo->siguiente;
            }
      printf("\n");
     }
}

El siguiente es un programa de ejemplo que permite analizar una cadena y determinar si los paréntesis o corchetes están balanceados, las funciones están hechas de tal forma que podemos agregar también llaves, etc. ya que sólo hay que indicar cuál es el caracter que abre y cuál es el caracter que cierra.

// Archivo pila_parentesis.c

#include <stdio.h>
#include "pila_char.h"

int verifica_balance(char expresion[], char cabre, char ccierra);

int main()
{
 char cadena[]="2*[x+q(3s-2)]/[((x+1)*x+(s-2))]";
 int i=0;
 
 // Muestra la cadena
 printf("La cadena a analizar es la siguiente:\n\n");
 while (cadena[i] != '\0')
       {
        printf("%c", cadena[i]);
        i++;
       }
 
 printf("\n\n");
 // Verifica si los paréntesis están balanceados
 if (verifica_balance(cadena, '(', ')') == 1)
     printf("Los paréntesis están balanceados\n");
 else
     printf("Los paréntesis NO están balanceados\n");
 
 // Verifica si los corchetes están balanceados
 if (verifica_balance(cadena, '[', ']') == 1)
     printf("Los corchetes están balanceados\n");
 else
     printf("Los corchetes NO están balanceados\n");
 
 return 0;
}

int verifica_balance(char expresion[], char cabre, char ccierra)
{
 int x=0, balanceados=1;
 ptrPila pila = NULL;
 
 // Recorre la cadena
 while (expresion[x] != '\0' && balanceados == 1)
       {
        // Si el elemento coincide con el caracter que abre, lo ingresa en la pila
        if (expresion[x]==cabre)
            push(&pila, expresion[x]);
        else
            // Si el elemento coincide con el caracter que cierra, lo saca de la pila
            if (expresion[x]==ccierra)
               {
                /* Si la pila está vacía, significa que los caracteres no están balanceados
                   porque se encontró un caracter que cierra sin que exista antes un caracter que abre
                */
                if (pila_vacia(&pila) != 1)
                    pop(&pila);
                else
                    balanceados = 0;
               }
        x++;
       }
 
 /* Si balanceados = 1 pero la pila no está vacía, los caracteres no están balanceados
    porque quedaron caracteres que abren sin tener su caracter que cierra
 */ 
 if (balanceados == 1 && pila_vacia(&pila) != 1)
     balanceados = 0;

 // Se asegura de dejar la pila vacia
 while (pila_vacia(&pila) != 1)
        pop(&pila);
 
 return balanceados; 
}

El siguiente archivo contiene la implementación de las funciones push y pop para ser utilizadas con enteros

// Archivo pila_int.h

#include <stdio.h>
#include <stdlib.h>

typedef struct nodo_s
{
 int dato;
 struct nodo_s *siguiente;
} nodo_t;

typedef nodo_t *ptrNodo;
typedef nodo_t *ptrPila;

/*
    Agrega un nodo al inicio de la lista ligada
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
void push(ptrPila *pila, int x)
{
 // Crea un nuevo nodo
 ptrNodo nodo;
 nodo = (ptrNodo)malloc(sizeof(nodo_t));
 if (nodo != NULL)
    {
     nodo->dato = x;
     // El apuntador nodo->siguiente va a apuntar al primer nodo de la lista ligada
     nodo->siguiente = *pila;
     // pila va a apuntar al nuevo nodo, con esto hacemos que el nuevo nodo sea ahora el primer nodo de la lista ligada
     *pila=nodo;
    }
}

/*
    Elimina el primer nodo de la lista ligada
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
int pop(ptrPila *pila)
{
 // Crea un nuevo nodo
 ptrNodo nodo;
 int x=0;
 
 // El nuevo nodo va a apuntar al primer nodo de la lista ligada
 nodo = *pila;
 x = (*pila)->dato;
 // Ahora el segundo nodo de la lista ligada va a ser el primero
 *pila = (*pila)->siguiente;
 // Borra el primer nodo de la lista ligada
 free(nodo);
 // Regresa el valor que contenía el nodo que se eliminó
 return x;
}

/*
    Regresa 1 si no hay nodos en la lista ligada y cero en caso contrario
    *pila es el apuntador que apunta al primer nodo de la lista ligada (la cima de la pila)
*/
int pila_vacia(ptrPila *pila)
{
 return (*pila == NULL ? 1:0);
}

void nodos_pila(ptrNodo nodo)
{
 if (nodo == NULL)
     printf("La pila está vacia\n");
 else
     {
      while (nodo != NULL)
            {
             printf("%d\n",nodo->dato);
             nodo = nodo->siguiente;
            }
      printf("\n");
     }
}

Como ejemplo, el clásico programa para hacer operaciones aritméticas en notación postfix

// Archivo pila_postfixexpr.c

#include <stdio.h>
#include "pila_int.h"

int main()
{
 char cadena[]="45+72-*5/";
 int i=0, num1=0, num2=0, result=0;
 ptrPila pila = NULL;
 
 // Muestra la cadena
 printf("La cadena a analizar es la siguiente:\n\n");
 while (cadena[i] != '\0')
       {
        printf("%c", cadena[i]);		
        i++;
       }
 
 i=0;
 printf("\n\n");
 // Recorre la cadena
 while (cadena[i] != '\0')
       {
        // Si el elemento no es un operador, lo ingresa en la pila
        if (cadena[i]!='+' && cadena[i]!='-' && cadena[i]!='*' && cadena[i]!='/')		   
            push(&pila, ((int)cadena[i])-48);   // El código ASCII de 0 es 48
        else
             {
              num2=pop(&pila);
              num1=pop(&pila);
              switch (cadena[i])
                     {
                      case '+':
                               result = num1+num2;
                               printf("suma %d + %d = %d\n",num1, num2, result);
                               push(&pila, result);
                               break;
                      case '-':
                               result = num1-num2;
                               printf("resta %d - %d = %d\n",num1, num2, result);
                               push(&pila, result);
                               break;
                      case '*':
                               result = num1*num2;
                               printf("multiplica %d * %d = %d\n",num1, num2, result);
                               push(&pila, result);
                               break;
                      case '/':
                               result = num1/num2;
                               printf("divide %d / %d = %d\n",num1, num2, result);
                               push(&pila, result);
                               break;
                     }			 
              }
        i++;
       }

 if (pila_vacia(&pila)!=1)
    {
     printf("\n\nLos elementos en la pila son los siguientes;\n\n");
     // Muestra los elementos que están en la pila
     nodos_pila(pila);
    }
 
 return 0;
}

Funciones básicas para listas simplemente ligadas en C

agosto 9, 2011

En este post voy a poner un archivo de cabecera que hice para poder crear programas que utilicen listas simplemente ligadas, contiene las funciones básicas y está diseñado para manejar enteros, pero es muy fácil hacer la implementación de un archivo de cabecera que acepte otro tipo de datos (char, etc.).

La estructura básica es la siguiente


typedef struct nodo_s
{
 int dato;
 struct nodo_s *siguiente;
} nodo_t;

Implementé una función para crear un nodo con el valor que contendrá el campo llamado dato, una función para insertar un nodo, para eliminar un nodo, para saber si la lista está vacía y una función que muestra todos los nodos de la lista.


// Archivo listasimple_int.h

#include <stdio.h>
#include <stdlib.h>

typedef struct nodo_s
{
 int dato;
 struct nodo_s *siguiente;
} nodo_t;

typedef nodo_t *ptrNodo;
typedef nodo_t *ptrLista;

/*
Crea un nuevo nodo y en el campo dato almacena el valor que recibe como parámetro
regresa el nodo recien creado
*/
ptrNodo crea_nodo(int valor)
{
 ptrNodo nuevo_nodo = (ptrNodo)malloc(sizeof(nodo_t));
 if (nuevo_nodo != NULL)
    {
     nuevo_nodo->dato = valor;
     nuevo_nodo->siguiente = NULL;
    }

 return nuevo_nodo;
}

/*
Agrega a la lista que recibe como parámetro, un nodo enseguida del nodo que recibe como parámetro
Si el nodo que recibe como parámetro es NULL, significa que se desea insertar el nodo al inicio de la lista
*/
void inserta_despues(ptrLista *lista, ptrNodo nodo, int valor)
{
 ptrNodo nuevo_nodo = crea_nodo(valor);

 if (nodo != NULL)
    {
     /* El apuntador nuevo_nodo->siguiente va a apuntar a la misma dirección a donde apunta
        el apuntador "siguiente" del nodo que recibe como parámetro
     */
     nuevo_nodo->siguiente = nodo->siguiente;
     /* El apuntador "siguiente" del nodo que recibe como parámetro va a apuntar al nodo recien creado
        con esto, el nodo recien creado se ha insertado adelante del nodo que se recibe como parámetro
     */
     nodo->siguiente = nuevo_nodo;
    }
 else
    {
     // Si la lista no está vacía, hace que el apuntador "siguiente" del nuevo nodo apunte al primer elemento de la lista
     if (*lista != NULL)
         nuevo_nodo->siguiente = *lista;
     // Hace que la lista apunte hacia el nuevo nodo para que sea el primer nodo de la lista
     *lista = nuevo_nodo;
    }
}

/*
  Elimina el nodo que se encuentra enseguida del nodo que recibe como parámetro
  Si el nodo que recibe como parámetro es NULL, y la lista no está vacía,
  significa que se desea borrar el primer nodo de la lista
*/
int elimina_despues(ptrLista *lista, ptrNodo nodo)
{
 int x=0;
 ptrNodo borrar_nodo = NULL;

 if (nodo != NULL)
    {
     if (nodo->siguiente != NULL)
        {
         /* El apuntador borrar_nodo va a apuntar a la misma dirección a donde apunta
            el apuntador "siguiente" del nodo que recibe como parámetro
         */
         borrar_nodo = nodo->siguiente;
         /* El apuntador "siguiente" del nodo que recibe como parámetro va a apuntar al nodo que está
            a continuación del que se va a borrar
         */
         nodo->siguiente = borrar_nodo->siguiente;
        }
    }
 else
     {
      // Si la lista no está vacia, significa que quiere borrar el primer nodo de la lista
      if (*lista != NULL)
         {
          borrar_nodo = *lista;
          *lista = borrar_nodo->siguiente;
         }
     }

 /* Si el apuntador "siguiente" del nodo que recibe como parámetro apunta a NULL, significa que el apuntador
    que se recibió como parámetro es el último de la lista, por lo tanto, no hay nodo siguiente
    Otro caso por el cual borrar_nodo puede ser null, es que la lista esté vacía, y también es imposible hacer la eliminación de un nodo
 */
 if (borrar_nodo != NULL)
    {
     x=borrar_nodo->dato;
     free(borrar_nodo);
    }
 else
     printf("Borrado prohibido\n");

 return x;
}

/*
  Regresa 1 si no hay nodos en la lista ligada y cero en caso contrario
  *lista es el apuntador que apunta a la lista ligada
*/
int lista_vacia(ptrLista *lista)
{
 return (*lista == NULL ? 1:0);
}

/*
  Muestra los datos de los nodos
*/
void nodos_lista(ptrNodo nodo)
{
 if (nodo == NULL)
     printf("La lista está vacia\n");
 else
     {
      while (nodo != NULL)
            {
             printf("%d",nodo->dato);
             nodo = nodo->siguiente;
             if (nodo != NULL)
                 printf(" -> ");
            }
      printf("\n");
     }
}

A continuación muestro un programa muy sencillo para que sirva de ejemplo de cómo utilizar este archivo de cabecera, el programa pide al usuario que vaya insertando números enteros y los va insertando en orden en una lista simplemente ligada; cuando el usuario no quiera introducir más números, debe introducir el número cero. Después, el programa da opción a borrar un número de la lista.


//      ordena_listasimple.c
//
//      Hecho por Salomón Rincón Torres <rtmex@yahoo.com>
//

#include <stdio.h>
#include "listasimple_int.h"

int main()
{
 int numero=0, insertado=0, encontrado=0;
 ptrLista lista = NULL;
 ptrNodo nodo = NULL;

do
  {
   insertado = 0;
   printf("Este programa recibe números y los va insertando en orden ascendente en una lista simplemente ligada\n");
   printf("Vaya introduciendo los números (introduzca cero para salir del programa)\n");
   scanf("%d", &numero);

   if (numero!=0)
      {
       if (lista_vacia(&lista) == 1)
           inserta_despues(&lista, NULL, numero);
       else
           {
            nodo = lista;
            if (numero <= nodo->dato)
                // Inserta el número al inicio de la lista
                inserta_despues(&lista, NULL, numero);
            else
                while (nodo != NULL && insertado == 0)
                      {
                       if (numero > nodo->dato)
                          {
                           if (nodo->siguiente != NULL)
                              {
                               if (numero > nodo->siguiente->dato)
                                   nodo = nodo->siguiente;
                               else
                                   {
                                    inserta_despues(&lista, nodo, numero);
                                    insertado = 1;
                                   }
                              } /* if */
                           else
                               {
                                inserta_despues(&lista, nodo, numero);
                                insertado = 1;
                               }
                          } /* if */
                      } /* while */
           } /* else */
       printf("\n\nLos elementos en la lista son los siguientes;\n\n");
       // Muestra los elementos que están en la lista
       nodos_lista(lista);
      } /* if */
  }
while (numero!=0);

printf("\n\nLa lista quedó con los siguientes elementos:\n\n");
// Muestra los elementos que están en la lista
nodos_lista(lista);

if (lista_vacia(&lista) != 1)
   {
    printf("\nDato a borrar\n");
    scanf("%d", &numero);

    nodo = lista;
    if (nodo != NULL)
        // Verifica si el número que se desea borrar es el primero de la lista
        if (nodo->dato == numero)
            elimina_despues(&lista, NULL);
        else
            {
             while (nodo != NULL && encontrado == 0)
                   {
                    if (nodo->siguiente != NULL)
                       {
                        if (nodo->siguiente->dato==numero)
                            encontrado = 1;
                       }
                    if (encontrado == 0)
                        nodo = nodo->siguiente;
                   }
             if (encontrado == 1)
                 elimina_despues(&lista, nodo);
            }

    printf("\n\nLa lista final quedó con los siguientes elementos:\n\n");
    // Muestra los elementos que están en la lista
    nodos_lista(lista);
   }
return 0;
}