Servicios y procesos. Servicios en C (III). FIFO

Las PIPE en principio solo sirven para comunicaciones padre – hijo, por lo que para comunicarnos entre procesos independientes necesitamos otro tipo estructura.

Esta son los FIFO, archivos que ya no se crean en el proceso padre, sino que lo genera el sistema operativo. Es un ente que genera el SO y que podrá ser utilizado por diversos procesos estén o no emparentados.

Es decir, los mecanismos de comunicación no tienen que estar necesariamente emparentados.

Se llama FIFO porque es una cola (first in, first out).

Para operar con ellos en C usaremos comandos de ficheros de bajo nivel (write, open…)

El comando que permite crear una FIFO se mknod, al igual que la función de C que permite generarlas en ese lenguaje.

En Linux, el comando para generar un FIFO sigue esta estructura:

mknod [opciones] nombreFichero p

Con el parámetro mode indicamos los permisos que tendrá nuestro FIFO.

Una vez generado podemos comprobarlos haciendo un ls-l

Hecho esto, y sabiendo que funciona como una pila, podemos meterle información para que lo vaya leyendo otro proceso que acceda al FIFO.

Vamos a introducirle el contenido de visualizar los directorios, con un ls, para luego visualizar por pantalla su contenido con un cat.

En C podemos programar nuestros procesos para que mientras uno crea y está a la escucha para leer el FIFO, otro introduzca información en él y sea leído por el primero.

Para ello usaremos la función mknod (tiene el mismo nombre que el comando usado para generar el fichero).

La función mknod tiene la siguiente estructura:

int mknod (const char *pathname, mode_t modo, dev_t dev);

Donde:

• Pathname: Nombre del dispositivo
• Modo: Especifica tanto los permisos de uso como el tipo de nodo que se creará
• Dev: Debe ser una combinación (utilizando OR bit a bit) de uno de los tipos de fichero que se enumeran a continuación.
• S_IFREG
• S_IFCHR
• S_IFBLK
• S_IFIFO – Para crear un FIFO

El código para la creación y lectura de un FIFO es el siguiente

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

int main(void){
     
     int fp;
     int p, bytesLeidos;
     char saludo[] = "Un saludo!!!\n", buffer[10];
     
     p = mknod("FIFO3", S_IFIFO|0666, 0); // Permiso de lectura y escritura
     
     if (p == -1){
          printf("Ha ocurrido un error \n");
          exit(0);
     }
     
     while(1){
          fp = open("FIFO3", 0);
          bytesLeidos = read(fp, buffer, 1);
          printf("Obteniendo información... \n");
          while(bytesLeidos != 0){
                printf("%s", buffer);
                bytesLeidos = read(fp, buffer, 1); // lee otro byte
          }
          close(fp);
     }
     
     return 0;
}

Y el programa para escribir en el FIFO:

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

int main(){
     
     int fp;
     char saludo[] = "Un saludo!!!\n";
     fp = open("FIFO3", 1); // Abre el fichero FIFO ya creado
     
     if(fp == -1){
          printf("Error al abrir el fichero...\n");
          exit(1);
     }
     
     printf("Mandando información al FIFO...\n");
     write(fp, saludo, strlen(saludo)); // Manda al FIFO fp la cadena de texto saludo con los caracteres contados por strlen
     
     close(fp);
     return 0;
}

Para comprobar el funcionamiento compilamos y ejecutamos primero el programa para la lectura (es el que crea el FIFO) y se mantiene a la espera.

Mientras, abrimos otra terminal y lanzamos el programa para escribir en el FIFO.

Podremos ver el desarrollo en tiempo real, siendo algo tal que así

Al mostrar el texto por pantalla lo vemos de esta forma porque uno trabaja en ASCII y otro en UNICODE, pero para hacernos una idea de que se comunican correctamente sirve.

Ejercicio. Creamos tres procesos que van a interactuar con un FIFO. Uno de ellos va a meter números al FIFO, y los otros dos estarán para leerlos. Un proceso de lectura deberá sacar por pantalla los números pares y el otro se encargará de los impares.

Sigue leyendo

Servicios y procesos. Procesos en C (II). PIPE

PIPE

Las PIPE (tuberías) son un mecanismo para poner en comunicación los procesos padre e hijo.

Se comporta como un falso fichero en el que ambos pueden leer y escribir.

Conceptualmente hablando, tendremos dos procesos, padre e hijo. Entre ellos se creará una tubería que emplearán para leer y escribir.

Para ello usaremos un array de enteros de dos posiciones. El [0] será de lectura, y el [1] de escritura. Es bidireccional pero sólo puede usarse en uno de los dos sentidos.

Si necesitamos una comunicación que circule en los dos sentidos, habrá que crear dos PIPE, uno para cada dirección.

Para poder utilizar este método de comunicación deberemos cargar la librería unistd, y tener en cuenta que se escribe como los ficheros, usando la función write y read.

Veamos un código de ejemplo para pillar la idea.

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

void main(){

     int fd[2];
     char buffer[30];
     pid_t pid;

     //#include<unistd.h>
     // int pipe(int fd[2]);
     // fd[0] contiene el descriptor para lectura

     pipe(fd); // Se crea el PIPE
     pid = fork();

     switch(pid){
     
          case -1: // Error
                printf("No se ha podido crear un hijo \n");
                exit(-1);
                break;
          case 0: // Hijo
                close(fd[0]); // Cierra el descriptor que no va a usar. El de lectura
                printf("El hijo escribe en el PIPE... \n");
                write(fd[1], "Hola papi", 10);
                break;
          default: // Padre
                close(fd[1]); // Cierra el descriptor de escritura
                wait(NULL); // Espera a que finalice el hijo
                printf("El padre lee el PIPE \n");
                read(fd[0], buffer, 10);
                printf("\t Mensaje leido: %s \n", buffer);
     }
}

En el código podemos ver que después de la declaración de cada proceso, tenemos una lína que reza:

close(fd[1]);

Con esto lo que hacemos es cerrar la parte de la tubería que no vamos a utilizar. Me explico, si el que escribe es el hijo, en su lado cerraremos la posición cero, y si el padre es el que va a leer, cerraremos la posición 1. Así conseguiremos algo más de seguridad en nuestro programa. Es una práctica recomendable, aunque es verdad que nuestro código funcionará exactamente igual sin hacerlo.

Ejercicio. Haz tres procesos (padre, hijo y nieto) que se comuniquen entre ellos a través de PIPEs.

Solución.

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

void main(){

     int fd1[2], fd2[2];
     char buffer[30], buffer2[30];

     pid_t pid, pidNieto;

     pipe(fd1);
     pipe(fd2);

     pid = fork();

     switch(pid){

          case -1: // Error
                printf("Ha habido un error \n");
                exit(-1);
                break;
          case 0: // Hijo
                close(fd1[0]);
                printf("Escribe el padre: \n");
                write(fd1[1], "El padre dice hola", 20);

                //Creación de nieto
                pidNieto = fork();

                switch(pidNieto){
                     case -1: // Error
                          printf("Ha habido un error \n");
                          exit(-1);
                          break;
                     case 0:
                          close(fd2[0]);
                          printf("Escribe el nieto \n");
                          write(fd2[1], "Soy el nieto", 13);
                          break;
                     default:
                          close(fd2[1]);
                          wait(NULL);
                          printf("El padre lee \n");
                          read(fd2[0], buffer2, 13);
                          printf("Mensaje leído: %s", buffer2);
                          break;
                }
                break;
          default: // Padre
                close(fd1[1]);
                wait(NULL); // Espero que finalice el nieto
                printf("\nEl abuelo lee: \n");
                read(fd1[0], buffer, 20);
                printf("Mensaje leído: %s \n", buffer);
                break;
     }

}

Sigue leyendo

Servicios y procesos. Procesos y C (I)

¿Qué es un proceso?

Proceso = Programa en ejecución

Cada una de las CPU se tienen que compartir a ratos con todos los procesos cargados en la memoria RAM.

Cuando un programa usa la CPU y sale, hay que hacer una especie de instantánea para guardar el contador de procesos pendientes, donde se ha quedado, etc.

Esto se conoce como el BCP (bloque de control de procesos). Es una tabla del sistema operativo que guarda la información de la situación de como se había quedado el programa en el momento de finalizar su tiempo en la CPU y dejar espacio a otro proceso.

Estados del proceso

Un proceso puede estar en la CPU, es decir, estará en ejecución.

Puede ser que esté cargado en la RAM, preparado para que el SO le de paso a la CPU. Estará listo.

O puede ser que esté esperando a utilizar los recursos que otro proceso ha cogido y hasta que no finalice el sistema operativo no le va a dejar continuar. Entonces estará bloqueado.

La contienda es como se llama a la pugna que hacen los procesos listos para conquistar la CPU.

Hay distintos modos de realizar la asignación de la contienda. Entre otros:

è Round-Robin. Método circular

è Por prioridades. Es decir, el antivirus tendrá más prioridad que la calculadora, por ejemplo. O el Word al estar tecleando conseguirá más prioridad de la ventana activa para no dar sensación de lentitud o ir a saltitos… Pero esto tiene varios problemas, como la inacción. Es decir, si mientras P1 (proceso 1) está en ejecución por ganar a la P2 pero entra P3 que tiene mayor prioridad, saldrá P1 y ganará la contienda P3.

è Por tiempos. Mayor prioridad el que menor tiempo estimado tiene para terminar.

Eso sí, al programar no podremos controlar los métodos de ordenación de la contienda. No podemos garantizar que los procesos vayan a coger la CPU en el momento que vayamos a querer.

Procesos en los SSOO

Para ver los procesos en Windows, iremos al Administrador de Tareas à Procesos

Para verlos desde la línea de comandos, en CMD escribiremos tasklist. Además al hacerlo por línea de comandos veremos el PID, el identificador del proceso.

En Ubuntu podemos verlo en la terminal con el comando ps.

Si hacemos ps –f también aparecerá el PPID, el identificador del proceso padre.

Con ps –AF aparecen todos los procesos lanzados en el sistema.

PID y procesos en C

Vamos a realizar las primeras prácticas con los procesos, los PID y los PPID en el lenguaje C. Para ello hemos instalado un entorno VitaLinux que trae ya incorporado el compilador gcc, pero podéis utilizar cualquier herramienta de vuestra elección que os permita trabajar programando en C.

EXECL

Execl sirve para ejecutar comandos del sistema y cualquier programa. Los argumentos son (const char *fichero, cons char *arg0, …, char *argN, (char*)NULL).

Devolverá -1 si hay condición de error.

Veamos un código de ejemplo

#include <stdio.h>
#include<unistd.h>

void main(){
     printf(“Los archivos del directorio son: \n”);
     execl(“/bin/ls”, “ls”, “-l”, (char *)NULL);
     printf(“ERROR!!!”);
}

Aquí estaremos haciendo un ls –l para ver todos los archivos del directorio desde donde ejecutemos este programa.

System

A diferencia de execl, system ejecutará sólo comandos del sistema, como podemos ver abajo. Vamos a ver el siguiente programa para hacernos una idea.

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

void main(){
     system(“ls –l > ficSalida”);
     printf(“FIN”);
}

Lo que hace el código es guardar el resultado de un ls –l de la carpeta actual del PATH a un fichero salida.

PID

En la arquitectura cliente – servidor tenemos dentro de un servidor web un proceso que está escuchando, en listen. Le hacen una petición y este proceso crea un hijo que sirva la página web al cliente. Una vez finalizada la tarea, el hijo sale de la memoria al finalizar su tarea. Durante todo la ejecución, el proceso padre se ha mantenido activo permaneciendo a la escucha de otras peticiones.

Vamos a ver un programa que nos muestre los identificadores del proceso actual y de su padre.

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

void main(){
     pid_t id_pactual, id_padre;
     
     id_pactual = getpid();
     id_padre = getppid();

     printf(“PID actual: %d \n”, id_pactual);
     printf(“PID padre: %d \n”, id_padre);
}

Analicemos este código.

• La línea de declaración pid_t nos indica el tipo de variable que será, una que nos sirva para almacenar el número de proceso que tenemos.
• La función getpid() devuelve el id del proceso actual
• Y la función getppid() devuelve el id del padre del proceso actual.

Ahora ya sabemos ver los id de los procesos, pero… ¿cómo se crean los procesos hijos?

Para eso tenemos la instrucción fork(), que es la encargada de crear un proceso hijo. Es decir, una copia exacta del proceso padre, pero a partir de ahora independientes.

Estos dos procesos, junto con todos los del sistema, entrarán en la contienda por la puja de la CPU independientemente. Y por tanto el control de tiempo también será independiente.

Para poder diferenciar uno de otro lo conseguimos con el valor devuelto por fork(). Con un ejemplo se verá más claro.

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

void main(){

     pid_t pid, hijo_pid;

     pid = fork(); // Aquí crea el proceso hijo
     
     if (pid == -1){
          printf(“Ha habido un error”);
          exit(-1);
     }
     if(pid == 0){
          // Nos encontramos dentro del proceso hijo
          printf("soy el proceso hijo \n\t Mi PID es %d. El PID de mi padre es: %d. \n", getpid(), getppid());
     }
     else{
          hijo_pid = wait(NULL);
          printf("Soy el proceso padre: \n\t Mi PID es %d. El PID de mi padre es: %d. \n\t Mi hijo %d terminó. \n", getpid(), getppid(), pid);
     }
}

Hay varios puntos que comentar. El primero es que como ya hemos dicho, los procesos pese a estar en un mismo programa, tanto el hijo como el padre son independientes en el momento de ejecutar fork().

Si nos devuelve un valor igual a 0, sabremos que estamos tratando con el hijo, mientras que cualquier otro valor que no indique una condición de error nos hará saber que está funcionando el padre.

Dentro del padre tenemos la línea

hijo_pid = wait(NULL);

Con ésta línea indicaremos que va a esperar a la finalización del proceso hijo, y la variable pid guardará el PID del padre.

¿Ha quedado claro? Atrevámonos con un ejercicio sencillico.

Ejercicio. Coged un proceso, cread una variable y guardad un valor. 7, por ejemplo. El proceso crea un hijo que le suma 5, y el padre le resta 5. Visualiza por pantalla el resultado de ambas operaciones así como el PID y el PPID de ambos procesos.

Solución.

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

void main(){
     pid_t pid, hijo;
     int n = 7;

     pid = fork();

     if (pid == -1){
          printf(“Error \n”);
          exit(-1);
     }
     if (pid == 0){
          n = n + 5;
          printf("Soy el hijo. Valor de n = %d.\n Proceso %d, padre %d \n\n", n, getpid(), getppid());
     }
     else{
          n = n – 5;
          printf("Soy el padre. Valor de n = %i.\n Proceso %d, padre %d \n\n", n, getpid(), getppid());
     }

}

Sigue leyendo

Programación. Manual completo del módulo

Por fin puedo decirlo. Ha sido un año trabajando duro, pero he conseguido aprobar el módulo (bueno, el curso completo, que coño) de programación, y lo que es aún más importante, aprender y no poco.

Durante todo el curso he estado realizando un manual exclusivamente de este módulo, tanto teoríco como práctico. Si quieres descargartelo puedes visitar la sección de descargas de este blog (pulsa aquí o navega por el menú habilitado para ello).

Cualquier duda, mejora, consulta, corrección, etc. agradecería un comentario en la propia entrada de la descarga.

Espero que le podaís sacar partido. Saludos

Sigue leyendo

Programación. Punteros en C (IV)

Introducción a los árboles

Un árbol es una de las EDD más utilizadas para resolver multitud de problemas (y muy utlizadas también en juegos).

Es una EDD no lineal.

Un árbol se define recursivamente así: o es vacío o consiste en un nodo que contiene datos y punteros hacia otros árboles.

Idea gráfica del concepto de árbol

Un caso concreto. Árbol binario

Cada nodo tiene como máximo dos hijos.

Esto hace que la implementación sea más sencilla (cada nodo incluye dos punteros para apunter a cada uno de los hijos, el izquierdo y el derecho):

struct nodo {

       struct info elemento;

       struct nodo *izda;

       struct nodo *dcha;

};

struct nodo *arbol;

Implementación de un árbol general

Un árbol en general no tiene limitado el número de hijos que puede tener cada nodo, y por lo tanto no puedo establecer a priori un número de punteros en la estructura para apuntar a los hijos.

Una posible forma de hacerlo sería teniendo una lista de punteros a los hijos almacenada en cada nodo, junto con la información que guarda cada nodo.

Es decir, para implementar un árbol general, haríamos uso de otra EDD.

Operaciones habituales con árboles

è Inserción

è Eliminación

è Búsqueda

è Recorrido

·         Inorden. Primero se recorre el subárbol izquierdo, luego se lee el valor del nodo y finalmente se recorre el subárbol derecho.

·         Preorden. Primero se lee el valor del nodo y después se recorren los subárboles.

·         Postorden. Se recorren primero el subárbol izquierdo y el derecho y después se lee el valor del nodo.

Inorden: 15 – 35 – 38 – 43 – 44 – 46 – 50 – 69 – 70 – 75 – 81 – 90

Preorden: 50 – 35 – 15 – 43 – 38 – 46 – 44 – 75 – 69 – 70 – 90 – 81

Postorden: 15 – 38 – 44 – 46 – 43 – 35 – 70 – 69 – 81 – 90 – 50

Aplicaciones de los árboles

Se utilizan en problemas que involucran jerarquía (por ejemplo, miembros de una familia), ramificación (como  los árboles de juegos, que involucran tomar la mejor decisión de las posibles, tras analizar todas las consecuencias) y clasificación y búsqueda eficiente.

Sigue leyendo

Programación. Punteros en C (III)

Particularizando en la EDD lista

Hay dos casos especiales de listas que vamos a estudiar con más detalle: pilas y colas.

Son listas en las que hemos restringido las operaciones que pueden hacerse para conseguir de ellas un comportamiento concreto.

Pilas

Tipo especial de lista en las que las inserciones y los borrados de los elementos se realizan sólo por un extremo que se denomina cima de la pila.

El concepto es muy similar a una pila de platos o papeles: yo puedo dejar sobre todo lo que hay, o coger sólo el elemento que hay encima de todo (en la cima), pero no puedo coger elementos de en medio o de la parte de abajo.

La pila es una estructura LIFO (Last In, First Out): el último en enterar es el primero en salir.

Operaciones sobre una pila

Cuatro operaciones posibles:

è Inicializar

è Comprobar si la pila está vacía

è Push (meter)

è Pop (sacar)

Implementación: Como una lista pero restringiendo las operaciones posibles

Funcionamiento de una pila

Aplicaciones de las pilas

Llamadas a subprogramas: Durante la ejecución de un programa, se guarda en la pila de ejecución las funciones que se van llamando para poder retomar luego de manera adecuada al punto de llamada.

Evaluación de expresiones en notación postfija.

Esta notación permite expresar la prioridad de las operaciones en una expresión sin necesidad de hacer uso de paréntesis.

Consiste en colocar primero los dos operandos que participan en la operación y posteriormente el signo.

La forma de evaluarlas es, cuando aparece un número se mete en la pila, cuando se ve un operador, se saca de la pila los operandos necesarios y se efectúa la operación metiendo el resultado en la pila.

Evaluación de expresiones en notación postfija: Ejemplo

è ((3+4)+((1+2)*3))-9

è 3 4 + 1 + 2 + 3 * + 9 -

Sigue leyendo

Programación. Punteros en C (II)

Estructura de datos

Una estructura de datos es una colección de datos organizados de determinada manera.

Ejemplo: Entero real, vector (de…), registro, matriz, fichero (de…), lista, cola, árbol…

Si tengo que trabajar con varios datos iguales en memoria, a veces un vector se queda demasiado grande, o demasiado pequeño.

Si yo tengo un fichero de datos y quiero pasarlo a memoria para trabajar con él, si uso un vector me puede ocurrir que sea insuficiente en cuanto al tamaño, o que esté desperdiciando la mayor parte de él.

Tipos de estructuras de datos

ED Estáticas

• Una vez definidas no pueden cambiar
• El contenido puede variar, pero no la estructura
• Tamaño fijo, ya sea mediante
• Variables estáticas (tamaño fijado en compilación)
•  Variables dinámicas (tamaño fijado en ejecución)

ED Dinámicas

• Podemos cambiar la estructura en cualquier momento
• Tamaño aumenta y disminuye según se va ejecutando el programa y varían las necesidades

¿Estructuras estáticas?

Inconvenientes de las estructuras estáticas (como vector):

• El tamaño no puede aumentar ni disminuir. Hay que predecir el tamaño exacto.
• Reorganizar la lista de elementos implica mover muchos elementos. Es costoso.
• Si tenemos una lista de elementos ordenados y queremos insertar uno manteniendo el orden:
• Con vector:
• Primero tenemos que disponer de espacio para el nuevo elemento (y puede ser que no tengamos)
• Segundo tenemos que desplazar todos los elementos que están después de él en el orden para mantenerlo.
• Con una EDD:
• Siempre podemos insertar un nuevo elemento (salvo limitación de recursos)
• Podemos insertar cualquier posición, con coste bajo

Tipos de EDD

Lineales. Que aumentan su tamaño en una única dimensión:

• Listas
• Pilas
• Colas

No lineales. Que aumentan su tamaño en varias dimensiones:

• Árboles
• Grafos

Uso de las EDD

Las EDD no están directamente soportadas por el lenguaje. Tenemos que programarlas nosotros.

• Definir las estructuras de datos necesarias
• Implementar las funciones y procedimientos que realicen las operaciones sobre estructuras de datos que hemos definido

El tipo de datos lista

Concepto. Secuencia finita de cero o más elementos de un tipo determinado.

a1, a2, an (n>=0)

Cada ai es del tipo de los elementos de la lista.

n: Longitud de la lista

Si n=0 lista vacía

Si n>=1 a1 es el primer elemento y an es el último elemento.

Dado un elemento ai, decimos que ai precede o es predecesor de ai+ y que ai sucede o es sucesor de ai-1.

Operaciones sobre una lista

Inicializar

Insertar (al principio, final o en una determinada posición)

Eliminar

Recorrer la lista

Tamaño

Recuperar (información de una posición concreta)

Localizar (posición a partir de información)

Copiar (de una lista a otra)

…

Implementación del tipo de datos lista

La lista nos la implementamos nosotros, así que lo hacemos como queramos de acuerdo con nuestras necesidades.

Una opción posible es implementarla como una lista enlazada

Lista enlazada

Cada elemento de la lista se almacena en un nodo, que es una estructura.

Los nodos se identifican por su posición, que es una dirección de memoria, a la que algo apuntará.

Los nodos contienen un elemento de la lista y la posición del siguiente nodo.

El nodo que contiene el último elemento de la lista tiene NULL en el campo “siguiente nodo”.

La lista es un puntero al primer elemento

Definición de la lista

struct info {

       /* Rellenar con toda la información que contenga un elemento de la lista

}

struct nodo {

       struct info elemento;

       struct nodo *siguiente;

}

struct nodo lista*

Inicializar lista

lista=NULL;

Insertar el principio

void insertarPrincipio (struct nodo **L, struct info *X) {

       struct nodo *tmp;

       tmp=(struct nodo *) malloc (sizeof(struct nodo));

       tmp->elemento=*X;

       tmp->siguiente=*L;

}

Insertar al final de la lista

void insertarFin (struct nodo **L, struct info *x){

       struct nodo *tmp;

       struct nodo *aux;

       tmp=(struct nodo *)malloc(sizeof(struct nodo));

       tmp->siguiente=NULL;

       if(*L==NULL) /* Lista vacía */

            *L=tmp;

       else { /* Lista con información */

            aux=*L;

            while (aux->siguiente !=NULL)

                        aux=aux->siguiente;

       aux->siguiente=tmp;

       }

}

Insertar en posición concreta (tras nodo determinado apuntado por p)

void insertarPos (struct nodo **L, struct nodo *p, struct info *x) {

       struct nodo *tmp;

       tmp=(struct nodo *)malloc (sizeof(struct nodo));

       tmp->elemento=*x;

       if (L==NULL){ /* Lista vacía */

            tmp->siguiente=NULL;

            *L=tmp;

       }

       else {

            tmp->siguiente=p->siguiente;

            p->siguiente=tmp;

       }

}

Eliminar el elemento apuntado por p

void eliminar (struct nodo **L, struct nodo *p) {

       struct nodo *tmp;

       if (*L==p) /* Eliminar el primer elemento */

            *L=p->siguiente;

       else {

            tmp=*L;

            while (tmp->siguiente!=p)

                        tmp=tmp->siguiente;

            /* tmp apunta al anterior */

            tmp->siguiente=p->siguiente;

       }  

       free(p);

}

Calcular el tamaño de una lista

Mi solución:

int tamagno (struct nodo **L) {

       struct nodo *tmp;

       int contador=1;

       tmp=*L;

       if (*tmp==NULL)

            return 0;

       else {

            while (tmp->siguiente!=NULL) {

                        contador++

            }

       }

       return contador;

}

Solución del profesor:

int tamagno (struct nodo **L) {

       int n;

       struct nodo *tmp;

       tmp=*L;

       n=0;

       while (tmp!=NULL) {

            n++;

            tmp=tmp->siguiente;

       }

       return (n);

}

Comentario sobre tamagno

Las EDD nos las creamos nosotros y podemos decidir implementarlas de muy diversas formas.

Si se va a utilizar de forma intensiva la función tamagno, se puede modificar la implementación para hacer que esta función sea más eficiente (ya que tener que recorrer cada vez que es llamada todos los elementos no resulta especialmente eficiente).

Podríamos, por ejemplo, guardar explícitamente información sobre el número de elementos, de tal manera que la lista en vez de ser un único puntero al primer elemento, sería un struct que tendría el número de elementos además del puntero al primer elemento.

En caso de optar por esta implementación, tendríamos que asegurarnos que esa información se actualiza adecuadamente cada vez que se inserta o borra un elemento, en las correspondientes funciones.

Localizar (el primer elemento de la lista, que tiene un campo entero igual a uno fijado)

struct nodo *localizar(struct nodo**L, int x) {

       struct nodo *tmp;

       tmp=*L;

       while ((tmp!=NULL) && ((tmp->elemento).campo_x!=x))

            tmp=tmp->siguiente;

       return tmp;

}

C realiza una evualuación cortocircuitada. Es decir, si en el anterior while, por ejemplo, no se cumple la primera condición, no continúa examinando la segunda.

De otro modo, el anterior código reventaría porque si fuera NULL intentaría leer el siguiente elemento pasado NULL, dando un fallo de segmentación.

Ejemplo de utilización

main() {

       struct info c;

       struct nodo *Lista;

       struct nodo *p;

       Lista=NULL;

       c.campo_x=5;

       insertarPrincipio(&Lista, &c);

       c.campo_x=12;

       insertarFin(&Lista, &c);

       /* Ver contenido */

       p=Lista;

       while (p!=NULL){

            printf(“%d”,(p->elemento).campo_x);

            p=p->siguiente;

       }

       p=Lista; /* Apunta a “5” */

       p=p->siguiente; /* Apunta a “12” */

       c.campo_x=56;

       /* Voy a insertar tras “12” */

       insertarPos(&Lista, p, &c);

       p=Lista; /* Apunta a 5 */

       p=p->siguiente; /* Apunta a 12 */;

       /* Voy a eliminar “12” */

       eliminar(&Lista, p);

}

Listas ordenadas

Si necesitamos una lista ordenada tenemos dos alternativas:

è Manejar una lista genérica y ordenarla cuando haga falta (usando algoritmos similares que para ordenar vectores). Se puede ofrecer una operación de ordenación.

è Mantener una lista ordenada siempre. Modificaciones necesarias:

·         Insertar. Ya no hay que indicar la posición. La función deberá encargarse de insertar en la posición adecuada.

·         Localizar. Podemos detener la búsqueda cuando encontremos un elemento mayor que el que buscamos.

Para llevar a cabo lo anterior, hay que tener en cuenta que mecanismo vamos a utilizar.

Ejemplo de aplicación de las listas

Almacenar un polinomio. En este caso podría ser útil una lista de estructura del siguiente tipo:

struct info {

       int exponente;

       float coeficiente;

}

Sigue leyendo

Programación. Punteros en C

Punteros en C

Los punteros es algo que cada lenguaje de programación trata de una forma específica, aunque lo que se puede en uno, normalmente se suele poder hacer en otro de una u otra manera.

Es por ello, que al ser algo específico del lenguaje de programación, que vamos a verlo para el caso específico de C, aunque algunas cosas podrían ser generalizables a otros lenguajes (pero muchas no)

Variables estáticas y dinámicas

En general, al programar, puedo hacer uso de dos tipos de variables:

è Estáticas: La memoria que utilizan se reserva en tiempo de compilación. Ventaja: Su sencillez

è Dinámicas: La memoria se reserva en tiempo de ejecución. Ventajas: Flexibilidad (estoy definiendo una matriz de cualquier tamaño) y permiten la creación de estructuras de datos dinámicas (que es un mecanismo más complejo que el visto hasta ahora con las estructuras estáticas).

int *matriz

…

matriz=malloc(sizeof(int)*5*5);

Para utilizar variables dinámicas es preciso disponer de un mecanismo para acceder a la memoria del ordenador. Ese mecanismo es precisamente el uso de punteros.

Concepto de puntero

Cuando tengo una variable, hay tres datos que están relacionados en ella:

è Tipo: Directamente relacionado con el tamaño del espacio que se reserva en memoria para ella

è Valor que contiene

è Dirección: Ubicación en memoria

Un puntero es una variable que almacena la dirección de memoria de otra variable. Es como una flecha que apunta a otra variable.

Punteros: dos operadores

è Operador dirección (&): Nos devuelve la dirección de una variable

è Operador contenido o indirección (*): Nos permite acceder al contenido de una variable a la que está apuntando un puntero

Declaración de punteros

Hay que indicar el tipo de la variable a la que apuntará, el nombre del puntero, y utilizar el símbolo * para indicar que es un puntero.

Ejemplo:

int valor;

int *puntero;

puntero=&valor;

valor=5;

*puntero=5; /* Las dos instrucciones hacen lo mismo */

Más sobre punteros

¿Cuál es la diferencia?

puntero=5; /* Modifico a donde apunta el puntero */

*puntero=5; /* Modifico el valor de la variable a la que apunta el puntero */

Hay que inicializar los punteros para que apunten a una dirección de memoria antes de utilizarlos.

int *puntero;

*puntero=7;

¿Dónde apunte el puntero? ¿Qué estoy modificando? Exacto, no lo sé ni yo, así que esto al sistema operativo no le va a gustar y seguro que se enfada (abortándome el programa).

Valor NULL: Es un puntero que se usa para indicar que un puntero no apunta a ningún sitio:

int *puntero=NULL;

¿Qué operaciones puedo hacer con datos apuntados? Las mismas que con el correspondiente tipo de datos.

Operaciones básicas con punteros

Asignación:

è Hacer que el puntero apunte a una dirección de memoria

è p1=p2; Ojo, p1 pasa a contener la dirección de memoria contenida en p2.

è Implicaciones:

·         Los vectores hay que copiarlos componente a componente

·         Si copiamos el puntero, no hemos copiado la variable

Comparación:

è Ver si dos punteros apuntan al mismo lugar

è p1==p2 no es lo mismo que *p1==*p2;

Suma, resta:

è Se utiliza para recorrer estructuras de datos.

è p1++ (apuntará al siguiente carácter de una cadena)

Inicialización del valor de un puntero

Tengo dos operaciones:

è Asignar la dirección de otra variable del  programa:

int valor;

int *puntero;

puntero=&valor;

è Pedir al sistema memoria para una variable nueva:

Es precisamente la opción empleada para utilizar variables dinámicas. C ofrece funciones para obtener memoria del sistema operativo de forma dinámica y liberarla cuando ya no es necesaria

Generación y destrucción de variables dinámicas

#include<stdlib.h> /* necesario para asignación dinámica de memoria */

…

struct fecha {

       int dia;

       int mes;

       int agno;

};

struct fecha *pFecha;

…

pFecha=(struct fecha *) malloc (sizeof(struct fecha));

if (pFecha==NULL){

       printf(“No hay suficiente memoria \n”);

}

else {

       …

       free(pFecha);

       …

};

…

Malloc y Free

pFecha=(struct fecha *) malloc (sizeof(struct fecha));

Malloc reserva los bytes que indiquemos en el parámetro que le pasamos (Precisamente para ello usamos la función sizeof pasándole como parámetro el tipo correspondiente. Así reservamos espacio justo para una variable de ese tipo).

Malloc devuelve un puntero genérico (o NULL si no hay memoria suficiente).

Tras llamar a malloc hay que hacer una conversión explícita de tipos para convertir ese puntero genérico en un puntero específico al tipo de datos que estamos manejando (en este caso en un puntero a struct fecha).

free(pFecha);

Free libera la memoria a la que apunta el puntero que le pasamos como parámetro.

Liberará más o menos memoria en función del tipo de datos del que sea el puntero que le pasamos.

Paso de parámetros por referencia a una función

Los punteros entre otras cosas dan soporte para poder pasar parámetros por referencia a una función:

…

float perim, area;

circulo(radio, &perim, &area);

…

void circulo (float r, float *p, float *a){

       *p=2*Pl*r;

       *a=Pl*r*r;

}

Si la función llamara a otra función y hubiera que pasar de nuevo “a” por referencia, no habría que poner “&” delante de “a”, ya que “a” es ya un puntero y por tanto una dirección.

Punteros y vectores

char *p, c, v[5]; /* Definimos un puntero a caracter, un caracter, y un vector de 5 caracteres */

c=*p; /* Asigno a c lo apuntado por p */

p=&c; /* Asigno a p la dirección de c */

/* Al definir un vector v[5] se queda guardada la dirección inicial del vector en la constante v */

p=v;

p=&v[0]; /* Esta línea y la anterior son equivalentes */

/* Del mismo modo p+4 es exactamente lo mismo que &p[4] */

/* Y *(v+4) equivale a v[4] */

Recorriendo vectores con punteros

Le estaríamos sumando a p 1:

char *p:

p=p+1;

Le estaríamos sumando a p 4:

int *p;

p=p+1; /*Sí, uno vale por cuatro */

Es decir, estás sumando unidades de datos, no bytes

Aclarando un poco las cosas

int vector[4];

El compilador reserva cuatro enteros consecutivos en memoria.

Almacena en la variable vector la dirección del primer elemento del vector.

Acceso a los elementos:

vector[0]         *(vector)

vector[1]         *(vector+1)

vector[2]         *(vector+2)

vector[3]         *(vector+3)

La variable vector es como un puntero, con la única diferencia de que se ha reservado además espacio para sus componentes.

Paso de vectores como parámetros

Cuando pasamos un vector a un función, lo estamos pasando implícitamente por referencia, ya que un vector y un puntero, a fin de cuentas, es lo mismo (o casi).

Como parámetro actual ponemos la variable del vector (que como acabamos de ver no es más que un puntero).

Como parámetro formal, hasta ahora hemos hecho apaños ya que no sabíamos muy bien lo que eran los punteros ni su relación con los vectores, pero a partir de ahora basta con poner un puntero al tipo de que sean las componentes del vector. Dentro de la función podré acceder a las “componentes de ese puntero” sin ningún problema.

Recordar que al ser un paso por referencia y al estar psaando punteros, todos los cambios que haga en el vector quedarán hechos en el vector original.

Recordar que al ser un paso por referencia y al estar pasando punteros, todos los cambios que haga en el vector quedarán hecho en el vector original.

Recordar además que existe un motivo importante para que un vector se pase siempre por referencia, y es que de hacerse por valor se estarían duplicando las necesidades de memoria.

Paso de parámetros. Ejemplo

main(){

       char cadena[50];

       char nueva[50];

       …

       quitarEspacios(cadena, nueva);

       /* cadena y nueva son ya direcciones */

}

void quitarEspacios (char *origen, char *destino) {

       …

       destino[3]=origen[7];

       …

}

Punteros y matrices

Es la misma idea que cuando hemos hablado de vectores y punteros.

Una matriz es un puntero al primer elemento más una reserva de espacio para todos los elementos.

¿Cómo se almacena una matriz en C? Por filas. El orden de los elemento en memoria es el siguiente (suponiendo matriz de 3x3):

m[0][0]

m[0][1]

m[0][2]

m[1][0]

m[1][1]

m[1][2]

m[2][0]

m[2][1]

m[2][2]

¿Puedo hacer esto?

#define FILAS 3

#define COLUMNAS 3

…

int matriz[FILAS][COLUMNAS];

mifuncion(matriz);

…

void mifuncion(int *m){

       …

       m[1][0]=…

       …

}

No. Motivo: Cuando quiero pasar una matriz como parámetro a una función tengo que pasar además del puntero, las dimensiones de esa matriz ya que el puntero no tiene ninguna información acerca de cuantas columnas tiene la matriz y por tanto no sabe dónde terminan las filas.

Cuando he puesto m[1][0], sintácticamente es correcto, pero el compilador en ese punto como no sabe cómo de larga es una fila (es decir, cuantas columnas tiene la matriz), no tiene ni idea de a que componente de la matriz tiene que acceder porque no sabe cuanto desplazarse en memoria.

Es decir, existe m[1][0], m[0][2]… ¿y m[0][1000]? ¿O paramos en m[0][29]? Si no sé como de larga es una fila, no sé dónde está almacenado en memoria la componente [1][0] y por tanto no puedo acceder así a los elementos guardados en una matriz.

¿Cómo lo hago entonces? Pasando puntero (m), número de filas (f) y número de columnas (c).

El acceso a la componente [1][0] se hace como (m+c*1+0), o como m[c*1+0] (sí, accediendo a la matriz como si fuera un vector, menudo lio, jeje. Bienvenidos a C).

Paso de matrices como parámetros

#define FILAS 3

#define COLUMAS 3

…

int matriz[FILAS][COLUMNAS];

mifuncion(matriz,FILAS,COLUMNAS);

…

void mifuncion(int *m, int f, int c){

       …

       (m+c*2+1)=…

       /* Equivalente a m[2][1] o a m[c*2+1] */

       …

}

Punteros y registros

->: Operador especial para acceder a los campos de un registro que es apuntado por un puntero.

Ejemplo de uso:

struct fecha{

       int dia;

       int mes;

       int agno;

};

struct fecha hoy;

struct fecha *phoy;

phoy=&hoy;

/* A continuación, 3 formas de hacer lo mismo */

hoy.dia=28;

(*phoy).dia=28;

phoy.>dia=28;

Punteros y cadenas de caracteres

Recordar que en C una cadena de caracteres no es más que un vector de caracteres que termina en ‘\0’ (para indicar dónde termina la información útil que hay en ella).

Por tanto las cadenas de caracteres se tratan exactamente igual que los vectores.

Pese a ello hay algunas funciones para hacer las cosas más sencillas (que no es necesario emplear para nada). De ellas las básicas son strcat(concatenar), strcmp(comparar), strcpy(copiar) y strlen(tamaño útil de la cadena). Las demás rara vez se usan.

Sigue leyendo