Introducción a la Programación en C

1 . Introducción

NIVEL DE ABSTRACCIÓN - COMO ATACAR EL PROBLEMA PARA ENCONTRAR UNA SOLUCIÓN
Un problema real requiere de un análisis que depender del mundo real. Este análisis genera un gap semántico que genera una representación del problema en un mundo virtual. A partir de ese punto, se puede definir una solución virtual al problema presentación y que finalmente se puede convertir en la solución real.

El gap semántico (mundo real) trata de reducir a lo mínimo posible a través de la manipulación del abstracto (software) y evitar la manipulación o cambio de hardware. Hacer que haya herramientas que resuelvan problemas y que le den órdenes al hardware para crear las soluciones.
a todo éste proceso se lo denomina “resolución de un problema” y consta de tres etapas bien marcadas:

1.1. Abstracción de Bajo nivel y Alto Nivel

1.2. Pasos En la generación de un programa

C _DevelopmentProcesses.png
Como se hace la traducción de código de fuente a un conjunto de instrucciones para ejecutar?

1 - Código fuente

p1.c
p2.c Estos son módulos.
p3.c

2 - Compilación

p1.obj
p2.obj Archivos objeto
p3.obj

Se codifican todas las sentencia a código máquina, a excepción de las llamadas a bibliotecas

3 - Ligado (linkeo)
Toma los códigos objetos que componían los módulos + bibliotecas y esto termina generando el programa.

1.3. Características Generales del Lenguage C

Una variable se declara de la siguiente manera:

int i = 6; / * this declares a variable ‘i’, and sets it to equal 6 */

/ * this declares the variables ‘i’, ‘test’, ‘foo’, and ‘bar’
note that ONLY ‘bar’ is set to six ! */
int i, test, foo, bar = 6;
BasicsVariable.png
Las variables permiten Bajar el nivel de abstracción ⇒ importante ⇒ no limitarse al hardware. Es una forma de relacionar un nombre con una cantidad de memoria.

1.5. Tipo de variables

Define la cantidad de memoria asociada a una variable y como operar en variables de ese tipo. El lenguaje no define el ancho de la variable, sino que se define de acuerdo a la plataforma en que se esté trabajando.

1.6. Bloques

Los bloques se utilizar para agrupar sentencias en las funciones y definen el ámbito de vida de las variables que se definan dentro de los mismo. Los bloques comienzan con “{“ y terminan con “}”.


int main(void)  
{  
    / * this is a 'block'  */  
    int i  = 5;  
    // este bloque separe  
    {
        / * this is also a 'block,' separate from the last one  */  
        int i  = 6;	  
    }  
    printf(“%d  n”, i);  
    return 0;  
}

1.7. Cuatro tipos básicos

Los tipos básico de C son: char, int, float y double. Con el siguiente código, se usa la función “sizeof” para determinar el tamaño de los tipos de datos (lo que ocupan en memoria).

#include  <stdio.h >

int main(void) {  
	printf("Caracter: %d  n", 	sizeof(char));  
	printf("Entero: %d  n", 	sizeof(int));  
	printf("Flotante: %d  n", 	sizeof(float));  
	printf("Doble: %d  n", 	sizeof(double));  
	return 0;  
}

1.8. Operador SizeOf

El sizeof es un operador especial que te permite determinar el tamaño en memoria de un objeto.
la sintaxis para utilizarlo es la siguiente:

sizeof object
sizeof(type)

Entonces, uno podría hacer algo por el estilo:

size _t size;  
int i;  
size  = sizeof(i);

1.9. Representación de Punto Flotante

Para números con punto flotante hacen falta 4 campos:

  1. Mantisa == > 1 bit
  2. Signo de mantisa
  3. Exponente == > 1 bit
  4. Signo de exponente

| 10000000 | 000000000 (mantisa) | 10000000 | 000000000(exponente) | | :—- | :—- | :—- | :—- |

Siempre es conveniente llevar la representación de los números al menor rango de la “recta” para tener mayor precisión.

1.10. Modificadores de tipos

unsigned short int entero _sin _signo _corto; // unsigned short int = 2 byte = > 0 a 65535
short entero _corto; // short int 2 bytes = > -32767 a +32767
unsigned long entero _sin _signo _largo; // unsigned long int = >

 #define EDAD _JUBILACION _HOMBRE 65  
 #define EDAD _JUBILACION _MUJER 60

La directiva de preprocesador #define permite reemplazar la ocurrencia del nombre de la constante con el valor asignado.
Por convención las constantes se escriben con MAYÚSCULAS.

1.12. Básico de Funciones

Las funciones son la piedra angular de la programación. Una función representa un bloque de código que realizar una tarea bien definida. Una función bien definida permite a un programador utilizarla sin necesidad de entender el comportamiento y/o estructura interno.
La acción de solicitar a una función que haga algo se denomina llamado a función “function call”.
Muchas funciones necesitan que se les indique con qué elementos trabajar. A estos elementos se los denomina argumentos.
Además, en C, todas las funciones “devuelven” un valor: valor de retorno.
Las funciones pueden ser definidas por la librería estándar, por terceros o por nosotros.

1.13. Identación, Nuevas líneas


#include  <stdio.h >

int main(void){ 
int i =0; printf("Hello, World !"); for (i =0; i <1; i ++){ printf("  n"); break; } return 0; }

 #include  <stdio.h >

int main(void)  
{  
int i =0;  
printf("Hello, World !");   
for (i =0; i <1; i ++)  
{   
printf("  n");   
break;  
}  
return 0;  
}

1.14. Comentarios

Los comentarios son una de las herramientas más importantes en la programación. Ayudan a:

//Single Line Comments (added by C99 standard, famously known as c++ style of comments)

  /*  
  Multiple   
  line of  
  comment  
  */

Ejemplo:

 #include  <stdio.h >  
   
/ **  
  * esta función…..  
  * Argumentos:   
  * Retorno: un entero para…. 0 OK, 1 error  
  */  
int main(void)  
{  
    int i =0;                // loop variable.  
   
    printf("Hello, World !");  
   
    for (i =0; i <1; i ++)   
    {  
        printf("  n");  
        break;               //Exits 'for' loop.  
    }  
 

    return 0;  
}

1.15. Primer programa en “C”

Todo programa en “Consta” de las siguientes partes:

//hola _mundo.c

#include  <stdio.h >

int suma(int a, int b);

int main()
{  
	*printf("hola mundo  n");
	*return 0;
}

El pre-procesador se encarga de ejecutar todas las directivas del “ #”. Este símbolo se usa para incluir HEADER files al código que se este ejecutando en ese momento.

 #include  <stdio.h >  
   
int main(void)  
{  
   printf("Hello, world !");  
   // Espera hasta que se ingrese un caracter.  
   getchar();  
   return 0;  
}

1.16. Entrada y Salida de Caracteres

int printf(const char *format,…)

La siguiente es una lista de declaraciones de formato de salida:

int scanf (const char *format,…)

A diferencia del printf, la función scanf requiere de la dirección de memoria donde va a escribir el valor ledo

1.17. Palabras Reservadas en C

auto double int struct
break else long switch
case enum register typedef
char extern return union
const float short unsigned
continue for signed void
default goto sizeof volatile
do if static while

1.18. Proceso de Compilación con GCC

GCC _CompilationProcess.png

Gcc compila archivos fuentes. Internamente, éste proceso se realiza en las siguientes etapas.

“gcc -o hello.exe hello.c” :

  1. Pre-processing: via the GNU C Preprocessor (gcc.exe), which includes the headers ( #include) and expands the macros ( #define).

  2. gcc hello.c > hello.i

  3. The resultant intermediate file “hello.i” contains the expanded source code.
  4. Compilation: The compiler compiles the pre-processed source code into assembly code for a specific processor.

  5. gcc -S hello.i

  6. The -S option specifies to produce assembly code, instead of object code. The resultant assembly file is “hello.s”.
  7. Assembly: The assembler (as.exe) converts the assembly code into machine code in the object file “hello.o”.

  8. as -o hello.o hello.s

  9. Linker: Finally, the linker (ld.exe) links the object code with the library code to produce an executable file “hello.exe”.

  10. ld -o hello.exe hello.o …libraries…

Verbose Mode ( -v)

You can see the detailed compilation process by enabling -v (verbose) option. For example,

gcc -v hello.c -o hello.exe

2 . Estructuras de control de Flujo

2.1. Condiciones y Expresiones

¿Que es una condición? == > Determina un valor lógico de una proposición == > True / False

2.2. Estructuras Secuenciales

sentencia1;
sentencia2;
sentencia3;
.
.
sentencia”n”;

2.3. Estructura if-else

if ( ) { // bloque de código } else { // bloque de código }

int main()
{
// Declaración de variable de tipo entera
int valor;

// Llamado a la función que imprime por el stdio  
*printf("ingrese un valor: ");*

*// Llamado a la función que lee del stdio*   *scanf("%d",&valor);*

// Ciclo de control para verificar si el valor ingresado es par o no
if (valor % 2 )
{
printf(“valor inpar n”);
}
else
{
printf(“valor par n”);
}
// Retorno de la función main()
return 0;
}

2.4. Estructura While

while ( ) { // bloque de código }

Ejemplo:

while((c =getchar()) !=EOF)
{
if (isalpha(c))
{
alpha [c -‘a’ ]++;
break;
}
}

2.5. Estructura Do-While

do
{
// bloque de código

} while ( );

Ejemplo:

do{
if ((n <=m)&&(m%n ==0))
{
mcd =TRUE;
}
else if (m <n)
{
swap(&m,&n); // hago swap
}
else
{
m =m%n;
swap(&m,&n);
}
}while(mcd ==FALSE);

2.6. Estructura For

for( ; ; ) { //bloque de código }

Ejemplo:

// conversión _far _cel.c

int main()
{
int t;

*for (t =TEMP _INICIAL; t <TEMP _FINAL; t  +=DELTA)*  
*{*   *// hay que meterle un coma algo para que devuelva un* 		   *// valor y haga la reasignación de valores a "lf"*  
	*printf("%d C  - > %.2lf F  n",t, 32  + t  * (9/5) );*   
*}*   *}*

3 . Arreglos

Arreglos y Vectores.jpg
Los arreglos son estructuras que permiten agrupar un conjunto de variables del mismo tipo, bajo un nombre, y que permiten ser accedidos (cada elemento) por medio de un índice.
En C, el arreglo más común es el de caracteres:

char cadena [10 ]; // define una cadena de 10 elementos tipo carácter.

if(cadena [i ] == 65 )
{
printf(“La letra en la posición %d es una A”, i)
}

Otro ejemplo es un arreglo de enteros:

#include

int main ()
{
int n [ 10 ]; / * n is an array of 10 integers */
int i,j;

/ * initialize elements of array n to 0 */
for ( i = 0; i < 10; i ++ )
{
n [ i ] = i + 100; / * set element at location i to i + 100 */
}

/ * output each array element’s value */
for (j = 0; j < 10; j ++ )
{
printf(“Element [%d ] = %d n”, j, n [j ] );
}

return 0;
}

3.1. Características de los Arreglos

Un arreglo es una manera de referenciar un grupo de variables con un mismo nombre.

int arreglo [10 ];

“C” no hace chequeos con respecto al índice de los arreglos.
Los sectores de memoria no son todos válidos para lectura o escritura. Por este motivo se debe tener cuidado en el momento de asignación de valores a variables/arreglos, asignándole índices que no estén dentro del campo definido. A esto se lo llama violación de acceso.
Tanto como hay arreglo unidimensionales, también los hay multidimensionales.

int matriz [10 ] [20 ];

Esto en la memoria se representa por filas, o sea, que los arreglos multidimensionales se guardan en memoria de forma continuar.

3.2. Acceder y Recorrer Arreglos

Para acceder a un elemento de un arreglo se utiliza el índice del mismo:

int valor = vector [i ]; // le asigno a la variable “valor” el contenido
// de “vector” en la posición “i”

Advertencia: Intentar acceder a una posición fuera del rango del arreglo, es una violación de acceso.
Para recorrerlos se pueden utilizar cualquier estructura de control de flujo, ejemplo: FOR:

int arreglo [10 ];
int indice = 0;

for(indice = 0; indice < 10; indice ++)
{
printf(“Valor del arreglo en la posición %i”, arreglo [i ]);
}

3.3. Arreglos, Matrices e Inicialización3.3. Arreglos, Matrices e Inicialización3.3. Arreglos, Matrices e Inicialización3.3. Arreglos, Matrices e Inicialización3.3. Arreglos, Matrices e Inicialización

#include

int main(void)
{
int i,j,matrix [3 ] [3 ] = { {1,2,3}, {4,5,6}, {7,8,9} }; for(i = 0; i < 3; i ++)
{
for(j = 0;j < 3; j ++)
{
printf(“%-6d”,matrix [i ] [j ]);
}
printf(“ n”);
}
return 0;
}

3.4. Enum (enumeraciones)

Se trata de constantes de enumeración, donde se define una lista de valores constantes.

enum boolean {NO, YES};

Cada valor de la enumeración tiene asignado un valor entero, comenzando con cero (0), a menos que se define explícitamente el valor deseado.

4 . Más estructuras de control: Break, Continue y GOTO

Ejemplo:

/ * C program to demonstrate the working of goto statement. */
/ * This program calculates the average of numbers entered by user. */
/ * If user enters negative number, it ignores that number and */
/ * calculates the average of number entered before it. */

# include int main(){ float num,average,sum; int i,n;

printf(“Maximum no. of inputs: “);
scanf(“%d”,&n);

for(i =1;i <=n;++i){
printf(“Enter n%d: “,i);
scanf(“%f”,&num);
if(num <0.0)
goto jump; / * control of the program moves to label jump */
sum =sum +num; / * nunca llega a ésta linea */
}

jump:
average =sum/(i -1);
printf(“Average: %.2f”,average);
return 0;
}

4.1. IF Aritmético

Teniendo el siguiente ejemplo:

if (a > b) {
result = x;
} else {
result = y;
}

Se podría escribir de la siguiente forma:

result = a > b ? x : y;

El formato del “if aritmético” es el siguiente:

(expresión)? exp1 : exp2;

si (expresión)? es verdadero = exp1, sino Falso = Exp2

4.2. Sentencia Switch

**switch** ( <expresión >) {	// expresión debe ser un valor entero  
	**case** caso1:  
		sentencias1;  
		**break**;  
	**case** caso2:  
		sentencias2;  
		**break**;  
	.  
	.  
	.  
	**default**:			// es opcional colocar "default"  
		sentenciaN;  
}

Si no se coloca el “break” se ejecutan todos los CASE debajo del que se ejecuto.
Ejercicio: Realizar un programa en C que permita mover el punto “W en 4,3” que se muestra en el siguiente gráfico, hacia los 4 puntos cardinales en forma aleatoria.
par _or7.gif

valor aleatorio X0 Y0
T0 (este) 5 3
T1 (sur) 4 2
T2    
.    
.    
Tn    

Los valores deben ir desde T0 a Tn. Para generar los números aleatorios se deberá usar la siguiente función:

x = rand();

En la línea anterior, el valor del “rand” va a desde 0 – > rand _max.

// coordenadas _RAND _version1.c

int main(){

*int i, direccion;*  
*int x =0;*  
*int y =0;*

*for (i =0; i <N; i +=1){*  
	*direccion  = rand()%4;*  
  
	*switch (direccion){*  
  
		*case ARRIBA:*  
			*y +=1;*  
			*break;*  
		*case ABAJO:*  
			*y -=1;*  
			*break;*  
		*case DERECHA:*  
			*x +=1;*  
			*break;*  
		*case IZQUIERDA:*  
			*x -=1;*  
			*break;*  
	*}*  
	*printf("ent %d  x=%d  y=%d   n",i, x, y );*  
*}*	  
*return 0;*   *}*

Aunque se ejecute 100 veces la posición de Xn e Yn es siempre la misma, esto se debe a que el logaritmo que usa el rand usa un mismo valor inicial (SEED = semilla), y por lo tanto, aunque los números sean distintos, las secuencias que se generan con cada ejecución son iguales. Para evitar esto, el número inicial debería ser distinto y esto se logra con la función “srand” y la semilla para que esta función sea efectiva puede ser el “TIEMPO” (en nuestro caso usaríamos el CLOCK del sistema). O sea que srand == > estaría en función del tiempo. La función que da la hora es la siguiente:

srand (time(NULL));	//  settea una semilla nueva.

Usando la función SRAND de esta manera, se implanta la semilla o SEED como punto de generación de números aleatorios de la función RAND. Ahora el código queda de la siguiente manera:

// coordenadas _RAND _version2.c

#include #include #include

#define ARRIBA 0
#define ABAJO 1
#define DERECHA 2
#define IZQUIERDA 3
#define N 10

int main(){
int i, direccion;
int x =0;
int y =0;

srand(time(NULL));

for (i =0; i <N; i +=1){  
	direccion  = rand()%4;  
  
	switch (direccion){  
  
		case ARRIBA:  
			y +=1;  
			break;  
		case ABAJO:  
			y -=1;  
			break;  
		case DERECHA:  
			x +=1;  
			break;  
		case IZQUIERDA:  
			x -=1;  
			break;  
	}  
	printf("ent %d  x=%d  y=%d   n",i, x, y );  
}	  
return 0;   }

4.3. Continuación de IO de caracteres

//obtener _caracteres.c

int main (){
int c;

*while( (c =getchar())  != EOF)*  
	*putchar(c);*  
*return 0;*   *}*

Esta función no devuelve nada hasta que el buffer no se llene o se fuerce el flujo de datos, o sea, a través del ENTER. O sea que las entradas de caracteres por teclado son “Bufereadas”
Para dirigir entradas en este ejemplo:

copiar < file _name == > c: text2.exe < < .. text2.c

En este ejemplo, desde la línea de comando del DOS, se puede dirigir la salida de un código.

// contar _caracteres.c

int main (){
int nc =0;
while (getchar() !=EOF)
nc ++;
printf(“Hay %d caracteres n”,nc);
return 0;
}

4.4. Expresiones Unarias

Operator Meaning
======== =======
& Address-of; value is the location of the operand
* Contents-of; value is what is stored at the location
- Negation
+ Value-of operator
! Logical negation ( ( !E) is equivalent to (0==E) )
~ Bit-wise complement

Los caracteres de incremento se pueden usar de dos maneras:

Como sufijo: ++v, –v
Como posfijo; v++, v–

Ejemplo:

x=4; x=4;
y= ++x; y=x ++;

4.5. Operadores de Asignación

x += y ⇐⇒ x = x+y;
x -= y ⇐⇒ x = x-y;
x *= y ⇐⇒ x = x *y;
x /= y ⇐⇒ x = x/y;
x %= y ⇐⇒ x = x%y;

// contar _letras.c

int main(void){
int nc=0;
int c;
while ((c=getchar()) !=EOF)
{
if((c !=’ n’) || (c !=’(‘) || (c !=’)’))
{
nc++;
}
/ **
*if(isalpha(c))
nc++;
* /
}
printf(“hay %d letras n”,nc);
return 0;
}

// Ejemplo de texto:
/ **
*hola el.perro
es;azul

// contar _palabras.c
#include #define NO 0 #define SI 1

main()
{
int np =0;
int enpalabra = NO;
int c;

while ((c =getchar()) != EOF){  
	if (c == ' '||c ==','||c ==';'||c =='.'||c =='  n'){  
		if (enpalabra  == SI)  
			np ++;  
		enpalabra =NO;  
	}  
	else  
		enpalabra =SI;  
}  
if (enpalabra  == SI)  
		np ++;  
printf("hay %d palabras  n", np);   }

Una de las lógicas posible es el de tener en cuenta las transiciones entre palabras y no palabras. Para esto elegimos “estado de palabra” para determinar el estado de palabra

// contador _digitos.c

int main(){
int nDigit [10 ];
int c, i;
for (i =0;i <10;i ++) //inicializamos el vector en 0
nDigit [i ]=0;
while((c =getchar()) !=EOF){
if( (c >=’0’) && (c <=’9’))//esta condición busca los dígitos entre el código
nDigit [c -‘0’ ]++;//dentro del [ ] se comprueba cual de los dígitos
} //es y le suma al vector +1 cada vez que coincide
for (i =0;i <10;i ++){
printf(“ %d “,nDigit [i ]);
}
return 0;
}

Ejercicio: Hacer un programa que determine e imprima lo indicado a continuación:
nc // contador de caracteres
nl // contador de líneas
np // contador de palabras

0 hay 31, 1 hay 20, 2 hay 13, Etc.

// contador _nc _nl _np _version1.c

int main () {
int np =0, enPalabra =0;
int c, cantCaracteres =0, cantLineas =0;
int i, condicion =0, numeros [10 ], letras [26 ];

*while ((c =getchar()) !=EOF) {*		  
	*if (condicion ==0) {*  
		*for (i =0;i <=10;i ++)*  
			*numeros [i ]=0;*  
		*for (i =0;i <=26;i ++)*  
			*letras [i ]=0;*  
		*condicion =1;*  
	*}*  
	  
	*//contador de palabras*  
	*if ((c ==' ')||(c =='.')||(c ==';')||(c ==':')||(c ==',') || (c =='  n')) {*  
		*if (enPalabra ==SI) {*  
			*np ++;*  
		*}*  
		*enPalabra =SI;*  
	*}*  
	*else {*  
		*enPalabra =SI;*  
	*}*  
	*//contador de lineas*  
	*if (c =='  n') {*  
		*cantLineas ++;*  
	*}*  
	*//fin contador de lineas*  
	*//fin contador de palabras*  
	  
	*//contador de numeros y letras*  
	*//contador de caracteres*  
	*if (isdigit(c)) {*  
		*numeros [c ]++;*  
		*cantCaracteres ++;*  
	*}*  
	*if (isalpha(c)) {*  
		*letras [c -97 ]++;*  
		*cantCaracteres ++;*  
	*}*  
	*//fin contador de numeros y letras*  
	*//fin contador de caracteres*  
*}*  
*if (enPalabra =SI) {*  
	*np ++;*  
*}*  
*printf("Hay %d palabras  n",np);*  
*printf("Hay %d lineas  n",cantLineas);*  
*printf("Hay %d caracteres  n",cantCaracteres);*  
  
*for (i =0;i <10;i ++) {*  
	*printf("%i : %d  n",i,numeros [i ]);*  
*}*  
*for (i =0;i <26;i ++) {*  
	*printf("%c : %d  n",(i +97),letras [i ]);*  
*}*   *}*

// contador _nc _nl _np _version2.c

int main(){
int nc =0, // contador numero de caracteres
nl =0, // contador numero de líneas
np =0; // contador numero de palabras

*int enPalabra  = NO, int c;*  
  
*// Contadores de números*  
*int cero =0, uno =0, dos =0, tres =0, cuatro =0, cinco =0, seis =0, siete =0, ocho =0, nueve =0;*

*while ((c =getchar()) !=EOF){*  
	*if (isalnum(c))		// función que cuenta caracteres (alfa  + numérico)*  
		*nc ++;*  
	*if (c =='  n')		// función que cuenta los "Enter's"  = líneas de texto*  
		*nl ++;*  
	*if (isdigit(c)){		// función que cuenta solo números (dígitos: 0..9)*  
		*switch (c){*  
			*case 0: cero ++;*  
				*break;*  
			*case 1: uno ++;*  
				*break;*  
			*case 2: dos ++;*  
				*break;*  
			*case 3: tres ++;*  
				*break;*  
			*case 4: cuatro ++;*  
				*break;*  
			*case 5: cinco ++;*  
				*break;*  
			*case 6: seis ++;*  
				*break;*  
			*case 7: siete ++;*  
				*break;*  
			*case 8: ocho ++;*  
				*break;*  
			*case 9: nueve ++;*  
				*break;*  
		*}*  
	*}*   *if ((c ==';') || (c ==',') || (c =='.') || (c ==' ') || (c ==':')||(c =='  n'))*   *{*	   *// función que cuenta la //cantidad de palabras*  
	*if (enPalabra  == SI)*  
			*np ++;*  
		*enPalabra  = SI;*  
*}*  
	*else*  
		*enPalabra  = SI;*  
*}*   *if (enPalabra  == SI)	// Se suma 1 mas por que el contador queda en*    *// la última palabra en// la función anterior pero no la incluye*  
	*np ++;*

*printf("Hay %d lineas  nHay %d caracteres  nHay %d palabras  n", nl, nc, np);*   *printf("Hay %d ceros  nHay %d unos  nHay %d dos  nHay %d tres  nHay %d cuatros  nHay %d cincos  nHay %d seis  nHay %d sietes  nHay %d ocho  nHay %d nueves  n", cero, uno, dos, tres, cuatro, cinco, seis, siete, ocho, nueve);*  
*return 0;*   *}*

// funcion _rand.c

int main(){
int i, delta;
int v [N ];

*for (i =0;i <10;i ++){*  
	*v [i ]=0;*  
*}*  
  
*srand(time(NULL));*  
*delta  = RAND _MAX/N;*  
  
*for (i =0;i <M;i ++){*  
	*v [rand()/delta ]++;*  
*}*  
*for (i =0;i <10;i ++){*  
	*printf("%d  t%d  n",v [i ], i);*  
*}*  
*return 0;*   *}*

El delta significa el numero de divisiones (clases) en que se divide la longitud total de números que van desde 0..RAND _MAX. La división de un número aleatorio (límite=RAND _MAX) por “delta” nos indica en qué clase se encuentra ese número y de ahí que podamos sumar en el vector la cantidad de números que caen en ese intervalo. Si la cantidad de números que se encuentran en cada intervalo es aproximadamente igual, quiere decir que la función RAND es fiable.

4.6. Operadores de Casteo (cast)

float pi = 3.141592;
int truncated _pi = (int)pi; // truncated _pi == 3

// Ejemplo de cast de un entero.

char my _char = ‘A’;
int my _int = (int)my _char; // my _int == 65, which is the ASCII value of ‘A’

4.7. Expresiones Relaciones y de Equivalencia

a < b
1 if a is less than b, 0 otherwise.
a > b
1 if a is greater than b, 0 otherwise.
a <= b
1 if a is less than or equal to b, 0 otherwise.
a >= b
1 if a is greater than or equal to b, 0 otherwise.
a == b
1 if a is equal to b, 0 otherwise.
a != b
1 if a is not equal to b, 0 otherwise

4.8. Expresiones Lógicas

a || b
when EITHER a or b is true (or both), the result is 1, otherwise the result is 0 .
a && b
when BOTH a and b are true, the result is 1, otherwise the result is 0 .
!a
when a is true, the result is 0, when a is 0, the result is 1 .

5 . Funciones

C Functions.jpg
Como ya se indico, un programa en C contiene las siguientes partes:

5.1. Declaración de Funciones (Prototipos)

Información para el compilador, le informa que funciones existen, qué argumentos reciben y que tipo de dato devuelve. También llamado prototipo.

tipo nombre (tipo arg, tipo arg2,.....);

int power(int x, int y);

El uso de los tipo sirve de información al compilador para determinar si se esta usando adecuadamente.

5.2. Definición

Declaración de sentencias que tienen que ser ejecutadas para que la función cumpla con lo que fue creada.

Tipo _dato nombre _funcion (tipo1 arg1, tipo2 arg2, …)
{
sentencia1;
sentencia2;
sentencia3;
return x;
}

// funcion _power _version1.c

int power (int x, int y)
{
int i, p=1;
for (i=0;i <y;i++)
p=p *x;
return p;
}

int main(void)
{
int a, b;

for (a=3; a <7 ; a++)
{
for (b=0;b <4;b++)
{
printf(“%d ^ %d = %d n”, a, b, power(a,b));
}
}
return 0;
}

En este ejemplo se puede observar la la asignación de argumentos posicional. Esto quiere decir que el lenguaje “C” hace el pasaje de argumentos en el mismo orden en los cuales fueron ingresados en la llamada.

// funcion _power _version2.c

int power(int x, int y);

int main()
{
int a, b;

*for (a =0;a <7;a ++)*  
	*for (b =0;b <4;b ++)*  
		*printf("%d ^ %d  = %d  n",a,b,power(a,b));*  
*return 0;*   *}*

int power(int x, int y)
{
int i,
p =1;

*for (i =0;i <y;i ++)*  
	*p =p *x;*  
*return p;*   *}*

5.3. Pasaje de argumentos a funciones

// funcion _permuta _version1.c

void permuta (int , int); // prototipo

// version 1
void permuta (int x, int y)
{
int temp =x;
x =y;
y =temp;
}

main ()
{
int a =10;
int b =20;

*permuta (a,b);*  
*printf("a=%d  tb=%d  n",a,b,);*  
*return 0;*   *}*

Existen 2 convenciones de pasaje de argumentos.

5.4. Pasaje argumentos por valor

Se pasa una copia del valor de las variables que se pasan como argumentos. Como en el ejemplo anterior,cuando termina la ejecución de la función, los valores que se imprimen en el main, son los mismos que se inicializaron en el MAIN.

5.5. Pasaje de argumento por Referencia

Se pasa una referencia (dirección en memoria) de las variables pasadas por argumento a la función.

5.6. Pasaje de Argumento por Descriptor

Esta tercera convención “Pasaje de argumentos por descriptor”, se pasa una serie de datos que describen la variable pasada = Tipo, ancho, dirección de memoria.

| Conclusión: C siempre pasa los argumentos de funciones por Valor. | | :—: |

5.7. Ámbito de vida de Variables (Scope)

main ()
{
int x,y,z………;

}

Toda variable además de tener su tipo, tiene su ámbito, o sea un rango en donde la variable tiene existencia ⇒ su alcance (SCOPE)
Hay tres ámbitos posibles:

5.8. Variable Local / Automática o de stack (pila)

int main (void)
{
int x,y,z….;
}

int f(void)
{
int i =x; // en este caso se produce un error por que X no esta definida en este SCOPE
}

5.8.1. Características:

  1. La variable tiene su alcance dentro del ámbito de las llaves.
  2. Desde donde hasta donde una variable es visible, lo define su SCOPE (alcance)
  3. Otro punto a tener en cuenta es la vida de la variable. En variables automática su vida esta dada por el SCOPE. Vive mientras su alcance este visible.
  4. STACK = El almacenamiento de la variable se crea en un STACK, una región donde uno va creado y destruyendo cosas, como un estante que se llena y se vacía con la declaración y uso de variables (PILA)

  5. Son totalmente locales a las variables que la definen y viven dentro del STACK de acuerdo al llamado.

    5.8.2. Variables globales

Las variables globales son variables que se definen fuera del cuerpo de cualquier función.

#include

int g1, g2;

int f1()
{
Sentencia1;
Sentencia2;
g1 = 5;
Sentencia3;
}

int f2()
{
int i;
Sentencia1;
Sentencia2;
g2 = g1;
Sentencia3;
printf(“g2 =%d”, g2);
}

Si se hace referencia a estas variables desde cualquiera de la funciones, las mismas son visibles y tanto como son visibles también son modificables dentro de cada función y ese nuevo valor pasa a ser global.

5.8.3. Variables Estáticas

Es una mezcla de los otros dos ámbitos. Se define de la siguiente manera:

int f()
{
static int x;
x++;
}

5.8.4. Características

  1. En este caso la variable sólo es visible dentro de este SCOPE.
  2. Su vida, se comporta como una variable global.
  3. La memoria asociada a una variable estática es igual al que variables globales.

// variables _estaticas.c

int contador()
{
static int x =0;
x ++;
return x;
}

main()
{
for (i =0; i <100; i ++)
contador();
}

El valor se va incrementando como si fuera una variable global, pero si se la llama fuera de la función contador, no se podría hacer referencia a los valores obtenido, sino solo llamando a la función contador.
En el caso de las variables estáticas, el compilador se encarga IMPLÍCITAMENTE en inicializar las variables declaradas de esta forma en “0”.

5.9. Funciones Estáticas

Las funciones estáticas son similares a las variables estáticas, donde se utiliza la palabra reservada Static. Esto produce que la locación de memoria asignada a la variable/función sea permanente y que el acceso a ella sea sólo dentro del mismo fuente (la función no puede ser llamada desde fuera del fuente en la cual fue declarada.

static int compare( int a, int b )
{
return (a +4 < b)? a : b;
}

Tabla de Referencia      
Variable Visibilidad Vida Región de Memoria
Local Dentro del SCOPE Se activa y destruyen dentro del SCOPE STACK
Global Dentro del FILE Mientras dure el proceso completo Región estática
Estática Dentro del SCOPE Mientras dure el proceso completo Región estática

Importante: La diferencia esta en que definir variables por valor, gano en “Control de acceso” a esas variables, en cambio por referencia se pierde este control.

Las ventajas y desventajas son la PERFORMANCE. Por valor se tiene que hacer copias de la variable y esto gasta memoria, no en cambio cuando se pasan por referencia, en donde se pasa la dirección de memoria donde esta almacenada la variable.

5.10. Variables Externas

Un programa en C consta de un conjunto de objetos externos, que son variables o funciones. El adjetivo “externo” se emplea en contraste con “interno”, que describe los argumentos y las variables definidas dentro de las funciones.
Debido a que las variables externas son accesibles globalmente, proporcionan una alternativa a los argumentos en funciones y a los valores de retorno para comunicar datos entre funciones. Cualquier función puede tener acceso a variables externas haciendo referencia a ellas solamente por su nombre, si éste ha sido declarado de alguna manera.

//File1.c:

// explicit definition, this actually allocates as well as describing
int GlobalVariable;

// function prototype (declaration), assumes defined elsewhere, normally from include file.
void SomeFunction(void);

int main()
{
GlobalVariable = 1;
SomeFunction();
printf(“%d”,
return 0;
}

//File2.c:

// implicit declaration, this only describes and assumes allocated elsewhere, normally from include
extern int GlobalVariable;

void SomeFunction(void) { // function header (definition)
++GlobalVariable;
}

5.11. Inicialización

Las variables extern y las static se inicializan en CERO.
Los arreglos se pueden declarar e inicializar con valores.

int dias [ ] = {1,2,3,4,5,6,7};

5.12. Recursividad

El lenguajes permite llamar a la misma función, ya sea directa o indirectamente.

Main = f() = g() = h() = hace algo ⇒ indirectamente

main = f() = f() ⇒ directamente

Recursión: n ! = n *(n-1) *(n-2) *…… *1 *0 !

Función recursiva: posee dos partes:

  1. Soluciones triviales: no se basan en la recursión, son resultados concretos. En el caso del factorial se establece que : 0 ! = 1
  2. Soluciones recursivas: en el caso de la recursión = n > 0

Una función recursiva bien implementada debe poseer estas dos soluciones.

// Algoritmo en forma recursiva
#include *int factorial (int n)* *{* *if (n ==0 )* *return 1;* *return (n * factorial(n -1));*

}

int main()
{
int nf;
nf = factorial(3); //devuelve ‘6’
return 0;
}

stack.gif

Cada vez que la función se llama, en el STACK se van anidando nuevas instancias de variables apiladas hasta que se cumple la condición de corte, una vez que pasa esto, la pila se va vaciando devolviendo los valores que habían quedado atascados.

// Algoritmo sin recursión
#include *int factorial (int n)* *{* *int i;* *int f =1;* *for (i =2; i <=n; i ++)* *{* *f =f *i;* *}* *return f;* *}*

int main()
{
int nf;
nf = factorial(3); //devuelve ‘6’
return 0;
}

5.13. Serie de Fibonacci

	  =1 si n==1 || n==2				// solución trivial   fibo(n)			     fibo(n-1)+fibo(n-2)  para todo n >2		// solución recursiva

// Algoritmo Recursivo
// Retorna el valor de fibonaci en la posición especificada:
// 1,1,2,3,5,8,13,21
int fibo (int n)
{
if (n ==1||n ==2 )
return 1;
return (fibo(n -1) + fibo(n -2));
}

|
// Algoritmo iterativo

int fibo(int n)
{
int i;
int n1 =1, n2 =1; aux =0;
if (n ==1 )
return n1;
if (n ==2 )
return n2;
for (i =1; i <nM i ++)
{
aux =n1 +n2;
n1 =n2;
n2 =aux;
}
return aux;
}

5.14. Torres de Hanoi

hanoi.jpg

// Hanoi.c

void hanoi(int n, int A, int B, int C)
{
if (n ==1){
printf(“Mueve el contenido de %c a %c n”, A, C);
}
else{
hanoi(n -1, A , C, B);
hanoi(1, A, B, C);
hanoi(n -1, B, A, C);
}
}

int main()
{
hanoi(3, ‘A’, ‘B’, ‘C’);
return 0;
}

hanoi 2.jpg

5.15. Variables de Hanoi

#include

// variable global para contar la cantidad de movimiento de discos
int nmvs;

void hanoi(int n, int from, int aux, int to) {
if( n == 1 ) {
nmvs ++;
return;
}
hanoi(n -1, from, to, aux);
hanoi(1, from, aux, to);
hanoi(n -1, aux, from, to);
}

int main() {
int i;
for( i = 2; i < 20; i ++ ) {
nmvs = 0; // comienza siempre en cero.
hanoi(i, 1, 2, 3);
printf(“%i nops %d n”, i, nmvs);
}
return 0;
}

hanoi 3.jpg

6 . Punteros

Los punteros son variables capaces de almacenar direcciones de memoria, pero de forma indirecta, por lo tanto, la técnica de usar punteros se llama indirección.
La cantidad de bytes que hacen falta para almacenar la dirección de memoria de una variable depende de la plataforma donde se esté trabajando.
Zeiger.PNG

6.1. Declaración de un puntero

int *a;
int z;
int b =17;

a = &b; // & significa “dirección de..”
z = *a; // * significa “contenido de..”. En este caso, z = a;

Todos los punteros deben ser declarados de un tipo, y así como uno declara un puntero entero, se puede declarar hacia cualquier tipo.
También existe una puntero genérico que es el *void **. El mismo no puede ser referenciado indirectamente.

Ejemplo: int *pointer;

6.2. Para que se usan Punteros

MappedMemory.gif

6.3. Ejemplo de Puntero

puntero.jpg

6.4. Aritmética de Puntero

Con cada tipo de dato, se relaciona un álgebra para el trabajo con ese tipo de datos. Es cuando los operadores, por ejemplo, ** + , - ,/ , *** toma significado al momento de operar sobre variables de tipo entero.

Comparar 2 punteros con los operadores ==, !=, <, >, <= ó >=, el resultado es un valor verdadero o falso.

int a, b, *pia = &a, *pib = &b;
if( pia == pib )
puts(“problemas…”);

Sabiendo esto, y teniendo en cuenta que los punteros son también otro tipo de dato al igual que los INT, DOUBLE, CHAR, etc. también existe un álgebra para los punteros.

int a [10 ];

int  *ptr  = a& [0 ];		// acá estoy asignando la dirección de memoria de a [0 ]

   int y  =  *ptr  + 1;		// apunta al siguiente int desde la posición actual.

| REGLA Nº 1 | PTR + i = puntero | | :—- | :—- |

Si un puntero apunta a una dirección de memoria, entonces “PTR + i”, donde i es un enteros, PTR apunta “i” mas allá, donde multiplica PTR por es el tamaño de la entidad “i” por la cantidad de entidades, o sea, el valor de i.

Ejemplo:
int i =3;
ptr + i = ptr + 3 * (size of (int));

Suma o resta de un entero a un puntero, el resultado es un puntero.

int vec [10 ], *pi = vec, *pi2;
pi2 = pi + 2;
*pi2 = 3;
*(pi + 1) = 7;

| REGLA Nº 2 | PTR1- PTR2= ENTERO | | :—- | :—- |

La resta entre dos punteros da la cantidad de entidades que hay entre dos punteros.

int  *ptr =&a [0 ];   
int  *ptr2 =&a [9 ];  
ptr  - ptr  = 10 entidades

Resta de 2 punteros del mismo tipo. El resultado es un entero con signo (entero de tipo ptrdiff _t).

int n, vec [10 ], *pi = &vec [0 ], *pi2 = &vec [5 ];
n = pi2 - pi;

6.5. Punteros como argumentos

Debido a que C siempre pasa los argumentos por valor (se realiza una copia de los valores de los argumentos), para hacer efectivo el intercambio de valores en una función, sus argumentos deben ser las direcciones de memoria de las variables (argumentos) involucradas.

pic52.gif

// swap.c

void swap(int *pa, int *pb)
{
int tmp = *pa;
* pa = *pb;
* pb =tmp;
}

int main ()
{
int x =3, y = 5;

*swap(&x, &y);*

*printf("X=%d  tY=%d  n", x,y);*  
*return 0;*   *}*

6.6. Apuntadores y arreglos

Cualquier operación que pueda realizarse con punteros, también se puede lograr con arreglos.

int a [10 ];  
int  *pa =&a [0 ];

pic54.gif
Para llegar a la 10 entidad del arreglo se usa = a [i ] (i-enésimo elemento del arreglo)
El equivalente por medio de punteros seria = ** *(pa + i)**

 *(a +0)  = a [0 ]  =  *(pa  + 0)  = pa [0 ]  
 *(a +1)  = a [1 ]  =  *(pa  + 1)  = pa [1 ]  
	.	  
	.  
	.  
 *(a +i)  = a [i ]  =  *(pa  + i)  = pa [i ]   ![pic55.gif][image19]   La relación entre punteros y arreglos es que: "Un arreglo es un puntero constante". Esto quiere decir que al definir int A [10 ], esta variable que llame “a” es un puntero hacia una estructura de 10 entidad de enteros consecutivas y constante, a la cual el compilador le asigna una dirección de memoria la cual no puede modificar.

Ejemplo:

int strlen(char  *ptr)  
{  
	int i=0;  
	while(ptr [i ] !=’  0’)  
		i ++;  
	return i;  
}

// otra opción trabajando directamente sobre punteros.

int strlen(char  *ptr)  
{  
	int i=0;  
	while( *(ptr ++))  
		i ++;  
	return i;  
}

Si nosotros quisiéramos hacer lo siguiente:

int a; // variable entera a
int *px; // puntero a entero px
a =32; // contenido de la variable
px =0; // dirección de memoria a la cual apunta px
*px =25; // asignación de una dirección de memoria nueva (INCORRECTA)

Es este caso saldría una excepción, debido a que “PX” no esta apuntando a una dirección de memoria “valida”. La forma correcta de asignar a PX una dirección válida, sería usando el “&”.
También podría darse el caso de apuntar a elementos que estén fuera de los límites definidos del arreglo, como por ejemplo:

int a [10 ];  
  	a [-5 ]  = 2;		// indice negativo  
a [15 ]  = 122;		// índice sobrepasado.

En ambos casos, el código compila y se ejecuta, pero el resultado puede ser inesperado desde el punto de vista lógico y de funcionamiento del programa.

6.7. Puntero a NULL

Se trata de un valor especial, el cual identifica la dirección de memoria 0 (cero). Este valor es inválido y en realidad es una forma de indicar que no se esta apuntando a nada.
null-pointers-in-C.png

6.8. Punteros Void

Se trata de un elemento que se usa para hacer referencias “genéricas”. Apuntan a un elemento (dirección de memoria) sin saber el tipo del elemento al cual están apuntando.

Void imprimeInt (void *p)
{
int pi = * (int *) p;
printf(“%d”, pi);
}
Void imprimeDobles (void *p)
{
double pp = * (double *) p;
printf (“%lf”, pp);
}

6.9. Arreglos desiguales o Ragged Arrays

Los punteros son útiles cuando se debe tratar con arreglos desiguales, donde se puede pensar como un arreglo multidimensional, en donde el arreglo 1 contiene punteros a cada uno de los arreglos. Cada puntero del arreglo 1 contiene la dirección de memoria donde vive realmente el arreglo “n”.

raggeed array.jpg

Un ejemplo es el main del Estándar:

/ *

mainArgs.png

En este caso, el main esta usando un puntero a punteros para indicar una lista de argumento. Un implementacion conocida por nosotros es:

c: gcc archivo _fuente.c -o nombre _ejecutable.exe

El programa GCC está tomando 3 argumentos, cada uno de los cuales es una cadena de caracteres de longitud variable.
En C, los arreglos multidimensionales son definidos con doble corchete: uno para las columnas y otro para los renglones:

int matriz [ 2 ] [3 ];

Cuando se pasa una matriz como argumento a una función, el número de renglones es irrelevante, punto que se puede entender como un puntero a un arreglo de renglones, entonces es válido hacer:

funcion(int matriz [2 ] [3 ]) // se pasa el elemento columna=2, fila=3
{….}

funcion(int matriz [ ] [3 ])
{….}

funcion(int ( *matriz) [3 ])
{….}

6.10. Inicialización de Arreglos de Punteros

// funciónn que retorna el nombre del mes, según el valor pasado por parámetro
char *mes _del _anio(int n)
{
static char *nombre [ ] =
{
“mes invalido”,
“enero”, “febrero”, “marzo”, “abril”,
“mayo”, “junio”, “julio”, “agosto”,
“septiembre”, “octubre”, “noviembre”, “diciembre”
};

return (n  < 1 || n  > 12) ? nombre [0 ] ; nombre [n ];   }

6.11. Punteros vs Arreglos Multidimensionales

int arreglo _multidimensional [10 ] [10 ];
int *puntero _arreglos [10 ];

Aunque a primera vista parezcan ser lo mismo, en realidad un arreglo multidimensional, en el momento de su declaración, hace al compilador reservar la cantidad de memoria exacta para definir ese arreglo (M x N), y la aritmética que se utiliza para acceder a cada uno de sus elementos es la misma que en matrices: cant _columnas X renglon + indice _columna.

En un arreglo de apuntadores, sólo se inicializan la cantidad de punteros indicados, y para cada puntero se deberá declarar de forma explícita la cantidad de elementos. Entonces se tendrá un arreglo de 10 elementos tipo puntero y para cada elemento, una cantidad X de memoria adicional.
La ventaja con respecto a los arreglos, es que cada elemento de los punteros pueden ser arreglo de longitud variable.

arrayOfarray.gif

Las matrices, o vectores de más de una dimensión, no tienen una equivalencia directa con los punteros.
int *ptr, v [5 ], a [3 ] [3 ];
ptr = &v [1 ]; < < < OK
ptr = v; < < < OK
ptr [4 ] = 8; < < < OK

ptr = a; < < < Error
ptr [1 ] [1 ] = 8; < < < Error

ptr = &a [0 ] [0 ]; < < < OK
ptr [3 *1 +1 ] = 8; < < < OK

6.12. Punteros a punteros

En el lenguaje C, los punteros pueden apuntar a otros punteros. Para esto, se debe agregar un asterisco para cada nivel de desreferencia.

char x;
char *y;
char * *z;
x =’c’;
y =&x;
z =&y;

Suponiendo las siguientes direcciones de memoria para X, Y y Z: 8000, 5000 y 1001:

z es un puntero a un puntero char cuya dirección es 1001 y contenido es 5000
** *z** es un puntero a char cuya dirección es 5000 y contenido es 8000
** * *z** apunta al contenido de un char, cuyo valor es ‘c’ y dirección es 8000 .

6.13. Punteros a Funciones

Los punteros a funciones lo que hace es llamar a una función y pasarle por argumento una función. En éstos casos, los punteros a función hacen que el parámetro sea interpretado “como una variable”.

// prototipos
double ( *f) (double);
double sin(double);

// llamado a la función armatabla, cada una recibe como argumento una función matemática
// de la librería “math.h”.
armatabla (sin , 0 , 10 , 0.2);
armatabla (cos, 0 , 20 , 0.1);
armatabla (tan , 0, 20 , 0.1);

// Definición de la función
void armatabla( double ( *f) (double), double ini, double fin, double delta)
{
while (i <f)
{
printf(“%lf == > %lf n” i, f(i));
i +=delta;
}
}

El puntero a puntero pasa la dirección de memoria de la función que se le pasa por argumento y los demás argumentos los usa en el trabajo interno.

7 . Administración de Memoria

La administración de memoria es uno de los elementos más importantes que provee el lenguaje C. El lenguaje permite obtener, modificar y liberar cantidades de memoria especificada de forma dinámica, o sea, durante la ejecución del programa.
Al proceso de solicitar memoria dinámicamente se le denomina alocación. Siempre es una buena práctica, que si se solicita memoria dinámica, luego de haber sido utilizada, se debe liberara, de lo contrario el memory pool (la cantidad de memoria disponible del proceso, asignada por el sistema operativo) colapsaría, o sea, el proceso se quedaría sin memoria adicional disponible.

7.1. Alocación Estática de Memoria

Los arreglos debe si o si ser dimensionados en el momento de compilación, no se pueden inicializar arreglos en tiempo de ejecución, debido a que el compilador debe alocar la memoria necesaria para inicializar el arreglo. Por lo tanto se debe, o colocar un valor entero en el código o con un DEFINE. éste proceso se denomina “Alocación estática de memoria” y la realiza el compilador.
Para resolver problemas en donde no se conoce el tamaño que puede tener el arreglo, aparece lo que se denomina Alocación Dinámica.
Memory Schema.png

7.2. Alocación Dinámica de Memoria

Este procedimiento permite pedir memoria adicional al Manager (elemento del sistema operativo) en tiempo de ejecución (RUN TIME). Las funciones de la biblioteca disponible son:

#include void *calloc(size _t nmemb, size _t size); void free(void *ptr); // libera la memoria a la cual apunta "ptr" void *malloc(size _t size); // obtiene "size" cantidad de bytes void *realloc(void *ptr, size _t size);

Ejemplos:

// malloc _free.c

#include #include

int main(void)
{
int *pV=NULL;
int sz;

printf(“Ingrese el tamaño: “);
scanf(“%d”, &sz);

pV = (int *) malloc (sz * sizeof(int)); // Nota 1

if (pV ==NULL) // verifica si existió un error
{
puts(“Error de alocacion n”);
exit(EXIT _FAILURE);
}
.
.
.
.
.
// En algún momento se deberá liberar la memoria pedida.
free(pV);
}

NOTA 1: en algunos compiladores, al momento de usar la función MALLOC, la misma retorna la dirección de memoria de un VOID * y si se lo está asignando, como en este caso, a un INT *, se deberá realizar un CASTING para salvar este posible error.

Cuando se usan arreglos o matrices, se tiene conocimiento de las dimensiones de los mismo, ya sea porque se los establece con un DEFINE o con constantes numéricas.

#define M 10
#define N 20

int main(void)
{
int matriz [M ] [N ];
matriz [i ] [j ]=32;
return EXIT _SUCCESS;
}

Pero si no se sabe los valores de puede tomar la matriz, se puede utilizar la alocación dinámica:

int *pM;
int n, m;

printf(“Ingrese M filas: “);
scanf(“%d”, &m);
printf(“Ingrese N columnas”);
scanf(“%d”, &n);

pM = (int *) malloc (m * n * sizeof(int));

assert(pM);

/ * La función assert sirve para chequear la condición de VERDAD del argumento que se le pase.

// para tener la misma notación de una matriz lineal MATRIZ [i ] [j ]

pM [ i * n + j ] = 32;

// Para poder hacer esto, se deberá utilizar un Puntero a Puntero:
// esto es por que pM [i ] [j ] es un INT y pM [i ] es un INT *, por lo tanto pM es un int * *

int pM * *;

// matriz _dinamica.c

#include #include #include

int * *allocMat(int m, int n)
{
int i;
int * *pRet;
pRet = (int *) malloc(m * sizeof(int *));
assert(pRet);

for (i  = 0; i  < m; i ++)  
{  
	pRet [i ]  = (int  *) malloc(sizeof(int)  * n);  
	assert(pRet [i ]);  
}  
return pRet;   }

void freeMat(int * *pM, int m)
{
int i;
for (i = 0; i < m; i ++)
free(pM [i ]);
free(pM);
}

int main(void)
{
int * *pM = NULL;
int i, j, n, m;
printf(“Filas = “);
scanf(“%d”, &m);
printf(“Columnas = “);
scanf(“%d”, &n);

pM  = allocMat(m, n);

if(pM  == NULL)  
{  
	printf("Error en la alocación de memoria  n");  
	return EXIT _FAILURE;  
}  
for (i  = 0; i  < m; i ++)  
	for (j  = 0; j  < n; j ++)  
		pM [i ] [j ]  = 0;

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

freeMat(pM, n);

return EXIT _SUCCESS;   }

NOTA: En los ambientes de desarrollo no se utiliza ASSERT, sino que se chequea si alguno de los resultados fueron NULL, y en tal caso, antes de devolver este valor (NULL) a la función, primero se deberá liberar la memoria y después terminar la función.

8 . Estructuras en C

8.1. Conceptos Básico de Estructuras

Cuando hablamos de variables, distinguimos dos grandes categorías:

  1. Variables escalares (enteros, char, float, etc)
  2. Arreglos (variables de un mismo tipo, referenciadas con un nombre)

Algunas veces uno tiene que trabajar con entidades que tienen varios tipos de datos, por ejemplo los atributos de una persona, nombre, sexo, dni, domicilio, etc. Para poder manejar este tipo de entidades como si fueran una sola entidad, no tratando cada atributo en forma individual, se utilizan lo que se denomina “estructura”.
Una estructura es una colección de una o más variables, de tipos posiblemente diferentes, agrupadas bajo un solo nombre para un manejo conveniente.
Las estructuras ayudan a organizar datos complejos, en especial en programas grandes. Permite manipular a un grupo de variables como si fueran una unidad.
En C se utiliza la palabra reservada struct:

struct nombre // rótulo de la estructura + nombre de la misma
{
tipo1 campo1; // miembros de la estructura.
tipo2 campo2;
.
.
tipon campo”n”;
};

Usando el ejemplo de un punto en ejes cartesianos:

struct point
{
int x;
int y;
};

struct point punto;

8.2. Selector de Campos

Para acceder a cada uno de lo “miembros” de una estructura se utiliza un “.” (punto):

nombre-estructura.miembro

punto.x = 0;
punto.y = 0;

Las estructuras se pueden inicializar, al igual que los arreglos y se pueden anidar:

struct rectangulo
{
struct point punto1;
struct point punto2;
};

Entonces, podemos crear una estructura que representa una pantalla:

struct rectangulo screen; // definición de una pantalla
screen.punto1.x; // obtenemos la esquina inferior izquierda

8.3. Ejemplo más complejo

En el ejemplo clásico de representar a una persona, se podría hacer lo siguiente:

#define NOMBRE _SZ 32
#define MASCULINO 0
#define FEMENINO 1

struct persona{
char nombre [NOMBRE _SZ ];
int edad;
int sexo;
int dni;
};

Entonces se entiende que:

int x; // x es de tipo int

struct pesona p; // p es de tipo struct persona

8.4. Estructuras y Funciones

Las únicas operaciones válidas en estructuras son:

Las estructuras NO SE PUEDEN comparar entre ellas.
En un mismo bloque de código pueden existir variables con el mismo nombre que aquellos definidos dentro de una estructura, debido a que el ámbito de vida de los miembros de una estructura están definidos dentro de las llaves de la misma.
Las estructuras pueden ser pasadas por argumento a funciones, o ser retornadas:

/ * makepoint: crea un punto con los componentes x e y */
struct point makepoint (int x, int y)
{
struct point temp;

temp.x = x;
temp.y = y;

return temp; //retornamos una estructura.
}

/ * addpoint: suma dos puntos */
struct point addpoint(struct point punto1, struct point punto2) // estructuras como argumentos.
{
punto1.x += punto2.x;
punto1.y += punto2.y;

return punto1;
}
Si una estructura grande va a ser pasada a una función, generalmente es más eficiente pasar un apuntador que copiar la estructura completa. Los apuntadores a estructuras somo como los apuntadores a variables:

struct point *pp;

PP es un puntero a una estructura de tipo struct point. entonces *pp es la estructura, y ( *pp).x y ( *pp).y son los miembros de la estructura.
Debido a que los apuntadores a estructuras se usan con tanta frecuencia, se ha proporcionado una notación alternativa para hacer éste tipo de referencias (- >):

pp - >punto1.x;
(pp - >punto1).y;

8.5. Arreglos de Estructuras

Al igual que con los tipos de datos nativos, con las estructuras se pueden definir arreglos:

/ * un arreglo de palabras reservadas en C, que mantiene la cantidad de ocurrencia de

otra forma de escribir lo mismo:

struct key
{
char *word;
int count;
};

struct key keytab [NKEYS ];

8.6. Punteros a Estructuras

Así como se declara una variable persona, también puede declarar un puntero a persona.

Persona _t *ptr = &p;

En este caso también existe un selector de campo que me permite referenciar una estructura por medio de un puntero. Para hacer esto el selector de campo, pasa de ser un simple punto a una (- >).

( *ptr).edad = 17;

es equivalente a:

ptr - >edad = 17;

En el ejemplo que se puso, edad no es un buen elemento de una estructura, puesto que es un dato variable con el tiempo, para eso seria mas conveniente poner : fecha _de _nacimiento.

struct fecha
{
int dia,
mes,
anio;
}fecha _nacimiento;

Esto permite, en lugar de guardar la edad en la estructura principal, colocar la fecha de nacimiento.

struct persona
{
char nombre [NOMBRE _SZ ];
struct fecha _nacimiento *pf _nacimiento;
int sexo;
int dni;
};

Una vez definida las estructuras, se utilizan en forma análoga a los tipos estándar de datos, por lo tanto se pueden declarar arreglos de estructuras, y también punteros a estructuras. Se pueden declarar variables que apunten a estructuras:

Struct fecha _nacimiento *FechaPtr;
Struct fecha _nacimiento Hoy;
FechaPtr = &Hoy;

La referencia a un campo de una estructura a través de un puntero se realiza mediante el operador “- >”.

FechaPtr - > Dia = 15;
FechaPtr - > Mes = “Octubre”;

8.7. Consideraciones

Cuando se ingresan punteros dentro de estructuras es conveniente tener en cuenta, hacia donde apuntan eso punteros, debido a que si no se definen correctamente los datos a los apuntan, puede encontrarse con algún caso de inconsistencia de datos, como por ejemplo, tener una estructura en donde se almacenan nombre de personas con un puntero al nombre (ningún carácter más) y si se tiene una función que destruye algún registro de persona, es muy posible que al borrar el registro de esa persona, otro registro con el mismo nombre quede inutilizable, en el caso de que se usen punteros al nombre.

Strcut persona _t
{
Char *nombre;
Int dni;
};

persona _t crearPersona ( persona _t *p)
{
presonat _t nueva;
nueva.nombre = p - >nombre; // error, esto esta mal.
nueva.dni = p - >dni;

return nueva;   }

/ * Para salvar este problema, hay que alocar memoria para el nombre */

persona _t crearPersona ( persona _t *p)
{
personat _t nueva;

nueva.nombre = (char *) malloc ( srtlen ((p - >nombre) + 1) * sizeof (char));

strcpy(nueva.nombre , p - >nombre);

nueva.dni = p - >dni;

return nueva;
}

/ *Si ahora queremos hacer la misma función de CREAR pero con punteros: */

persona _t *crearPersona ( persona _t *p)
{
personat _t *pnueva;

pnueva  = (persona _t  *) malloc (sizeof (persona _t ) );

nueva.nombre = (char *) malloc ( srtlen ((p - >nombre) + 1) * sizeof (char));

strcpy(nueva.nombre , p - >nombre);

nueva.dni = p - >dni;

return *pnueva;
}

En este caso, se ve que se tuvo que alocar memoria nueva para crear otra persona, de lo contrario, pnueva hubiese sido una variable LOCAL al Scope (a la función) y hubiera retornado cualquier cosa, debido a que esa memoria que utilizan las funciones para variables locales es colocada en un pila, que es constantemente usada.

8.8. Tipos definidos por el usuario (typedef)

Existe una facilidad en C para definir nuevos tipo de datos creados por el usuario:

typedef int Longitud; // Longitud pasa a ser un nuevo tipo de dato.
typedef char * Cadena;

Typedef struct persona persona _t; // entonces a partir de este momento persona _t es un nuevo
// tipo de dato

Persona _t p; // acá el compilador va a reservar tanta memoria como el tipo de
// dato persona _t requiera.

Se debe aclarar que Typedef NO CREA un nuevo tipo de dato, simplemente define un nuevo nombre a un tipo ya existente. Y las propiedades que poseen éstos nuevo tipos son las mismas que si se hubiesen definido explícitamente.

8.9. Uniones

Una unión es una variable que puede contener (en momentos diferentes) objetos de diferentes tipos y tamaños, y el compilador hacer el seguimiento del tamaño y requisitos de alineación.
Una unión es una estructura que agrupa en un mismo espacio de memoria varias variables de tipos distintos, que pueden ser accedidas para un momento dado con un tipo de dato dado.
Las uniones siempre toman como máxima capacidad la de mayor capacidad definida.

union u _tag
{
int integer _val;
float float _val;
char *string _val;
}utype;

;

Es responsabilidad del programador saber el tipo y valor almacenado en un momento dado.

if (utype == INT)
printf(“%d n”, utype.ival);
else if (utype == FLOAT)
printf(“%f n”, utype.fval);
else if (utype == STRING)
printf(“%s n”, utype.sval);
else
printf (“dato incorrecto %d en utype n’’, utype);

Todos los elementos de una “union” tienen un desplazamiento de cero con respecto al primer elemento. La estructura es suficientemente grande para mantener al miembro “más ancho”, y la alineación es la apropiada para todos los tipos de la unión. Están permitidas las mismas operaciones sobre las uniones como sobre las estructuras: asignación o copia como unidad, tomar la dirección, y hacer el acceso a un miembro.
Una unión sólo se puede inicializar con un valor del tipo de su primer miembro, así que la unión descrita anteriormente sólo se puede inicializar con un valor entero.

9 . E/S y Archivos

9.1. Entrada / Salida Estándar

Las operaciones de E/S no son partes del lenguaje C, pero todos los programas deben interactuar con su medio ambiente de muchas formas.
El modelo simple de entrada /salida que define el estándar consiste en un movimiento de flujo de caracteres, hasta encontrar un EOF, o un flujo de byte.
En base a la definición anterior, los archivos se pueden clasificar en dos tipos:

Hasta ahora siempre hemos trabajado con flujo de caracteres, utilizando las funciones scanf y printf:
input-output-management-in-c-programming-2-638.jpg

9.2. Acceso a Archivos

Un Archivo es una entidad que permite almacenar información de manera persistente, que posee un identificador para su posterior referenciación.

La característica fundamental de un archivo es la persistencia (poder ser recuperado posteriormente desde algún tipo de almacenamiento.
No existe el tipo de un archivo. Los archivos pueden no tener tipo (bajo nivel). Ésto es, la extensión define a “alto nivel” (para los usuarios) un tipo, pero la información real almacenada en el archivo no deja de ser un flujo de caracteres/bytes.
El sistema operativo administra el conjunto de archivos de la máquina. Por medio del explorador de Windows, por ejemplo, se puede ver los archivos.

9.3. File System

Un sistema de archivos, es el encargado de determinar cómo se almacenan y recuperar los archivos almacenados en algún dispositivos de almacenamiento. Es el encargado de saber que elementos son los que componen un archivo, proveer a nivel lógico, información para poder describirlo, y define un conjunto de operaciones para poder manipularlo.

Ejemplos de tipos de FileSystem:


De esta manera aparece el ÁRBOL de donde se desplegar los directorios, sub-directorios y archivos. Existe una gestión en cuanto al manejo de archivos. En los archivos, solo se almacenan 1 y 0 . Por ejemplo:

“Hello World”

H ⇒ 72 en ASCII

72 ⇒ 0100 1000 en binario

01001000 01100101 01101100 01101100 01101111 00100000 01010111 01101111 01110010 01101100 01100100

Con esto nos damos cuenta que los archivos no tiene TIPO, simplemente depender de la forma en que se lea el contenido y se le de un formato.

9.4. Stream (flujo)

Es el término utilizado para definir un flujo de datos de 1 y 0 . Un archivo, teclado, monitor es un posible stream. Lo importante es que en un momento dado tengo dos cosas:

“C” nos proveedor un conjunto de funciones que nos permiten manejar STREAM. C provee una estructura llamada FILE (en mayúscula). Define STREAM’s de entrada salida y siempre se administran con Puntero.

/ * Un ejemplo sencillo */
int main(void)
{
int var;
scanf (“%d”, &var); / * usa stdin para escanear un entero del keyboard. */
printf (“%d”, var); / * usa stdout para imprimir los caracteres del entero */
return 0;
}
/ * fin del programa */

C define que el STDIN es el teclado, y el STDOUT y STDERR son salida por monitor.

Todos estos son FILE * (punteros a la estructura FILE). Todas las funciones de administración de archivos son punteros.
Cuando se arranca un programa en C, el medio ambiente del sistema operati­vo es responsable de abrir tres archivos y proporcionar apuntadores de archivo para ellos. Estos archivos son la entrada estándar, la salida estándar y el error estándar; los apuntadores de archivo correspondientes se llaman stdin, stdout y stderr, y están declarados en . Normalmente stdin se conecta al tecla­do y stdout y stderr se conectan a la pantalla, pero stdin y stdout pueden ser redirigidos a archivos o a interconexiones (pipes).

9.5. Abrir Archivos

Como regla importante, antes de poder comenzar a leer y escribir un archivo, primero se tiene que abrir. C provee funciones para abrir archivos, lo cual hace que el programa negocie con el sistema operativo para poder obtener el acceso.
Finalmente, si el archivo se puede abrir, se regresa un puntero de tipo FILE * para poder ser utilizado posteriormente.

#include FILE *fopen(const char *filename, const char *mode); FILE *freopen(const char *filename, const char *mode, FILE *stream);

Siempre se pide permiso al sistema operativo para abrir archivos. Devuelve el FILE * si se da acceso o devuelve NULL si no. FILE es un tipo definido en “stdio.h” basado en una estructura de datos con los miembros necesarios para manejar archivos.
La “ “ es un carácter de escape, hay que tener cuidado al abrir archivos en C por que si se pone:

c: programas hola.exe // toma en realidad “ m” hay que poner “ “ dos barras.

9.6. Modos de Apertura

Un archivo debe abrir con permisos. Para ésto se utiliza el modo de apertura.

“r” ⇒ debe existir y solo lectura
“w” ⇒ sólo escritura, si existe lo sobreescribe
“a” ⇒ sólo escritura, si existe se posiciona al final del archivo
“r+” ⇒ lecto / escritura pero el archivo debe existir
“w+” ⇒ lecto / escritura pero si existe lo sobreescribe
“a+” ⇒ permite leer y escribir, pero si existe se posiciona al final del archivo

Estos son link’s con el sistema operativo. Siempre que se termina de trabajar con archivos, hay que cerrarlos y se hace de la siguiente manera:

9.7. Cierre de Archivos

#include int fclose(FILE *stream);

Esta función devuelve ‘0’ si esta todo OK o sino EOF si no lo pudo cerrar.

9.8. Fin de Archivo (feof)

Esta función sirve para determinar si el cursor dentro del archivo encontró el final (end of file). Existe otra forma de verificar el final del archivo que es comparar el caracter que trae fgetc del archivo con el macro EOF declarado dentro de stdio.h, pero este método no ofrece la misma seguridad (en especial al tratar con los archivos “binarios”). La función feof siempre devolverá cero (Falso) si no es encontrado EOF en el archivo, de lo contrario regresará un valor distinto de cero (Verdadero).
El prototipo correspondiente de feof es:

int feof(FILE *fichero);

9.9. Convenciones

Existen dos tipo de archivos en C: de texto y binarios. La diferencia es el “enter”.
En los diferentes sistemas operativos se representa el Enter de distinta manera. En modo texto opera con la conversión automática del ENTER.

9.10. Ejemplo: Abrir, Escribir y Cerrar Un Archivo

#include

int main(void)
{
FILE *stream;
int i = 100;
char c = ‘C’;
float f = 1.234;

/ * open a file for update */
stream = fopen(“DUMMY.BIN”, “w+”);

/ * write some data to the file */
fprintf(stream, “%d %c %f”, i, c, f);

/ * close the file */
fclose(stream);
return 0;
}

9.11. Manejo de Errores

C no provee construcciones especiales para el manejo de errores. Los mismos deben ser definidos y manejados por el programador.
Generalmente, los mensajes de error se imprimen en pantalla o en la línea de comandos, pero si la salida debe ir a otro programa se utiliza el flujo alternativo: stderr.

#include #include #include

extern int errno ;

int main (int argc, char const *argv [ ])
{
FILE * pf;
int errnum;
pf = fopen (“archivo _no _existente.txt”, “rb”);
if (pf == NULL)
{
errnum = errno;
fprintf(stderr, “Valor de errno: %d n”, errno);
perror(“Error Impreso por perror”);
fprintf(stderr, “Error abriendo el archivo: %s n”, strerror( errnum ));
exit (1);
}
else
{
fclose (pf);
}
return EXIT _SUCCESS;
}

Aquí podemos ver varios elemento nuevos:

Tal como existen funciones de entrada y salida de datos por el estándar in/out (teclado y pantalla), también existen sus equivalentes para trabajo con archivos:

9.12.1. fgets

Esta función está diseñada para leer cadenas de caracteres. Leerá hasta n-1 caracteres o hasta que lea un cambio de línea ‘ n’ o un final de archivo EOF. En este último caso, el carácter de cambio de línea ‘ n’ también es leído.
/ *

Ejempo:
#include #include

int main(void)
{
FILE *archivo;

char caracteres [100 ];

archivo  = fopen("prueba.txt", "r");

if (archivo  == NULL)  
	exit(1);

printf("  nEl contenido del archivo de prueba es   n  n");  
while (feof(archivo)  == 0 )  
{  
	fgets(caracteres, 100, archivo);  
	printf("%s", caracteres);  
}  
getchar();

fclose(archivo);  
return EXIT _SUCCESS;   }

9.12.2. fputs

La función fputs escribe una cadena en un fichero. No se añade el carácter de retorno de línea ni el carácter nulo final. El valor de retorno es un número no negativo o EOFen caso de error. Los parámetros de entrada son la cadena a escribir y un puntero a la estructura FILE del fichero donde se realizará la escritura.

/ *

Ejemplo:

#include #include

int main(int argc, char * *argv)
{
FILE *fp;

char cadena [ ]  = "Mostrando el uso de fputs en un fichero.  n";

fp  = fopen("fichero.txt", "wt");

if (fp  == NULL)  
{  
	printf("Error al abrir/crear fichero  n");  
	exit(1);  
}

fputs(cadena, fp);

fclose(fp);

return EXIT _SUCCESS;   }

9.12.3. fgetc

Esta función lee un caracter a la vez del archivo que esta siendo señalado con el puntero *archivo. En caso de que la lectura sea exitosa devuelve el caracter leído y en caso de que no lo sea o de encontrar el final del archivo devuelve EOF.
El prototipo correspondiente de fgetc es:

char fgetc(FILE *archivo);

Esta función se usa generalmente para recorrer archivos de texto. A manera de ejemplo vamos a suponer que tenemos un archivo de texto llamado “prueba.txt” en el mismo directorio en que se encuentra el fuente de nuestro programa. Un pequeño programa que lea ese archivo será:

#include #include

int main(void)
{
FILE *archivo;
char caracter;

archivo  = fopen("prueba.txt", "r");

if (archivo  == NULL)  
{

	printf("  nError de apertura del archivo.   n  n");  
} else  
{

	printf("  nEl contenido del archivo de prueba es   n  n");

	while (feof(archivo)  == 0 )  
	{  
		caracter  = fgetc(archivo);  
		printf("%c", caracter);  
	}  
}  
fclose(archivo);  
return EXIT _SUCCESS;   }

9.12.4. fputc

Esta función escribe un carácter a la vez del archivo que esta siendo señalado con el puntero *archivo. El valor de retorno es el carácter escrito, si la operación fue completada con éxito, en caso contrario será EOF.
El prototipo correspondiente de fputc es:

int fputc(int carácter, FILE *archivo);

Un ejemplo del uso de fputc en un “fichero.txt”, se escribe dentro del fichero hasta que presionemos la tecla enter.

#include #include

int main(int argc, char * *argv)
{
FILE *fp;

char caracter;

fp  = fopen("fichero.txt", "r+");

printf("  nIntroduce un texto al fichero: ");

while ((caracter  = getchar())  != '  n')  
{  
	fprintf("%c", fputc(caracter, fp));  
}

fclose(fp);

return EXIT _SUCCESS;   }

9.12.5. fread

size _t fread ( void * ptr, size _t size, size _t count, FILE * stream );

Esta función lee un bloque de una “stream” de datos. Efectúa la lectura de un arreglo de elementos “count”, cada uno de los cuales tiene un tamaño definido por “size”. Luego los guarda en el bloque de memoria especificado por “ptr”. El indicador de posición de la cadena de caracteres avanza hasta leer la totalidad de bytes. Si esto es exitoso la cantidad de bytes leídos es (size *count).

PARÁMETROS:

ptr : Puntero a un bloque de memoria con un tamaño mínimo de (size *count) bytes.
size : Tamaño en bytes de cada elemento (de los que voy a leer).
count : Número de elementos, los cuales tienen un tamaño “size”.
stream: Puntero a objetos FILE, que especifica la cadena de entrada.

9.12.6. fwrite

Esta función está pensada para trabajar con registros de longitud constante y forma pareja con fread. Es capaz de escribir hacia un fichero uno o varios registros de la misma longitud almacenados a partir de una dirección de memoria determinada. El valor de retorno es el número de registros escritos, no el número de bytes. Los parámetros son: un puntero a la zona de memoria de donde se obtendrán los datos a escribir, el tamaño de cada registro, el número de registros a escribir y un puntero a la estructura FILE del fichero al que se hará la escritura.
El prototipo correspondiente de fwrite es:

size _t fwrite(void *puntero, size _t tamano, size _t cantidad, FILE *archivo);

9.13. Manejo de Archivos

C provee un conjunto de funciones para navegar archivos. Estas funciones nos permiten posicionarnos dentro de los archivos a través un puntero especial que recorre el contenido.

/ *

Los archivos se tratan como flujos de bytes, por lo tanto, offset y origin cuentan Bytes
Primero el FSEEK recibe un nombre de archivo, luego se mueve desde el inicio tantos bytes como indique el offset (se para sobre ésta posición) y luego se mueve lee tantos bytes como origin lo indique, donde:

origin ⇒ SEEK _SET ⇒ Hacia adelante desde el principio
⇒ SEEK _CUR ⇒ desde donde estas
⇒ SEEK _END ⇒ desde el final tanto lugares hacia atrás como se indique

Devuelve 0 si esta todo OK, distinto si ahi un error.

/ *
*Devuelve la posición actual del puntero dentro del archivo.
*/
long int ftell ( FILE * stream );

Ejemplo: Con el siguiente código se puede saber cuánto pesa un archivo:

fopen (archivo);
fin =fseek (archivo, 0 , SEEK _END);
pesa =ftell (archivo);

9.14. Archivos Binarios

FILE * fopen ( const char * filename, const char * mode );

Al operado R+ le puedo asignar otro símbolo:

t ⇒ para modo texto
b ⇒ para modo binario

Por ejemplo: “r+b”

/ *
*Lee un bloque de datos de un archivo.
*/
size _t fread ( void * ptr, size _t size, size _t count, FILE * stream );

Lee desde un archivo “stream” una “count” cantidad de veces, “size” bytes y al resultado de esa lectura lo almacena en ptr.

/ *
*Escribe un bloque de datos en un archivo.
*/
size _t fwrite ( const void * ptr, size _t size, size _t count, FILE * stream );

Hace lo mismo que la función anterior pero al revés, en lugar de leer, escribe.

10 . Métodos de Ordenamiento

10.1. Concepto

Uno de los procedimientos más comunes y útiles en el procesamiento de datos, es la ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto dado de objetos en una secuencia determinada (patrón de arreglo). El objetivo de este proceso generalmente es facilitar la búsqueda de uno o más elementos pertenecientes a un conjunto.
Como ejemplos de conjunto de datos ordenados tenemos:

La ordenación, tanto numérica como alfanumérica, sigue las mismas reglas que empleamos nosotros en la vida normal. Esto es, un dato numérico es mayor que otro cuando su valor es más grande, y una cadena de caracteres es mayor que otra cuando esta después por orden alfabético.

Los metodos de ordenacion, pueden agruparse en dos grandes grupos:

Veremos solo tres modos de ordenamiento, los más usados, como son:

El método de ordenamiento de burbuja, es un algoritmo que se aplica para poder ordenar una cantidad de datos ya sea de forma ascendente o descendente.
Es el algoritmo más fácil de implementar, pero a cambio pagamos un alto precio en procesamiento, ya que este método evalúa una cantidad los datos muchas veces y en ocasiones innecesariamente (como por ejemplo cuando son iguales).
A estas alturas posiblemente ya se tienen conocimiento de pasos para ordenar datos, como por ejemplo, determinar cual es el mayor o menor de dos números, pues aplicando este método podremos ordenar arreglos, estructuras y cualquier tipo de dato NO atómico (es decir que se pueda dividir)
Gŕaficamente, el algoritmo funciona de la siguiente manera:
Bubble-sort-example-300px.gif
Este método necesita de lo siguiente para implementarse:

/ *

/ *

10.3. Método por Inserción

El ordenamiento por inserción (insertion sort) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.
Insertion-sort-example-300px.gif
void insertSort(int *lista, int cantElementos)
{
int i, j, auxiliar;

for (i  = 1; i  < cantElementos; i ++)  
{  
	auxiliar  = lista [i ];  
	for (j  = i  - 1; j  >= 0 && lista [j ]  > auxiliar; j --)  
	{  
		lista [j  + 1 ]  = lista [j ];  
	}  
	lista [j  + 1 ]  = auxiliar;  
}   }

10.4. Método Quicksort

El método de ordenamiento rápido (quicksort) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Sorting _quicksort _anim.gif

#include #include

void qs(int lista [ ],int limite _izq,int limite _der)
{
int izq,der,temporal,pivote;

izq =limite _izq;  
der  = limite _der;  
pivote  = lista [(izq +der)/2 ];

do{  
    while(lista [izq ]  < pivote && izq  < limite _der)   izq ++;  
    while(pivote  < lista [der ] && der  > limite _izq)   der --;  
    if(izq  <=der)  
    {  
        temporal = lista [izq ];  
        lista [izq ]=lista [der ];  
        lista [der ]=temporal;  
        izq ++;  
        der --;

    }

}while(izq <=der);

if(limite _izq <der){   qs(lista,limite _izq,der);  
}

if(limite _der >izq){   qs(lista,izq,limite _der);  
}   }

void quicksort(int lista [ ],int n)
{
qs(lista,0,n -1);
}

int main(int argc, const char * argv [ ])
{
int i;
int lista [ ] ={100,56,0,1,-45,2,46,5,9,6,67,23,5};
int size = sizeof(lista)/sizeof(int);

printf("Lista Desordenada   n");

for (i =0; i <size; i ++) {  
    printf("%d",lista [i ]);  
    if(i <size -1 )  
        printf(",");  
}

printf("  n");  
quicksort(lista,size);

printf("Lista Ordenada   n");  
for (i =0; i <size; i ++) {  
    printf("%d",lista [i ]);  
    if(i <size -1 )  
        printf(",");  
}

return EXIT _SUCCESS;   }

11 . Métodos de Búsqueda

11.1. Concepto

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.
La variante más simple del problema es la búsqueda de un número en un vector/arreglo.
los métodos de búsqueda más utilizados son:

  1. Búsqueda secuencial
  2. Búsqueda binaria

  3. Búsqueda por dispersión (hash)

    11.2. Búsqueda secuencial

Se utiliza cuando el arreglo no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo.

int busquedaSimple(int arreglo [n ], int n, int dato) {

int i;  
   
for(i =0; i <n; i ++){  
    if(dato ==arreglo [i ]) {  
        return arreglo [i ];  
    }  
}  
   
return  -1;   }

11.3. Búsqueda Binaria (dicotómica)


Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.
Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).
Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.

int busquedaBinaria(int arreglo [ ], int tamanio, int dato)
{
int centro,inf =0,sup =tamanio -1;

while(inf <=sup)
{
centro =(sup +inf)/2;
if(arreglo [centro ]==dato)
return centro;
else if(dato < arreglo [centro ] )
{
sup =centro -1;
}
else
{
inf =centro +1;
}
}
return -1;
}

12 . Tipos Abstractos de Datos (TDA)

12.1. Definición

Es un conjunto de operaciones asociadas directamente a la representación de un tipo de dato.

En el ejemplo del diagrama, tenemos una estructura planet _t que define las características de un “planeta”, y alrededor vemos una capa con funciones asociadas al tipo de dato definido.

Estas funciones definen el conjunto de operaciones permitidas sobre nuestro tipo de dato abstracto. A este conjunto de operaciones se le llama interfaz.

12.2. Separación Interfaz / Implementación

Cuando se usa en un programa, un TDA es representado por su interfaz, la cual sirve como cubierta a la implementación. La idea es que los usuarios de un TDA tengan que preocuparse sólo por la interfaz, pero no por la implementación, ya que esta puede ir cambiando con el tiempo y, si no existiera encapsulación, afectar a los programas que usan el dato. Esto se basa en el concepto de Ocultación de información.

La solidez de un TDA reposa en la idea de que la implementación está escondida al usuario. Solo la interfaz es pública. Esto significa que el TDA puede ser implementado de diferentes formas, pero mientras se mantenga consistente con la interfaz, los programas que lo usan no se ven afectados.

12.3. Caracterización

Un TDA está caracterizado por un conjunto de operaciones (funciones) al cual se denomina usualmente como interfaz pública y representa el comportamiento del TDA; mientras que la implementación como la parte privada del TDA está oculta al programa cliente que lo usa.
Todos los lenguajes de alto nivel tienen predefinidos TDA; que son los tipos denominados simples y las estructuras predefinidas, y estos tienen sus interfaces públicas que incluyen las operaciones como la +, -, *, etc. no se necesita conocer cómo actúan tales operadores sobre la representación interna de los tipos definidos, que además, suele ser una implementación bastante dependiente de la máquina sobre la que trabaje el compilador

12.4. Abstracción


La abstracción, una de las herramientas que más nos ayuda a la hora de solucionar un problema, es un mecanismo fundamental para la comprensión de problemas y fenómenos que poseen una gran cantidad de detalles, su idea principal consiste en manejar un problema, fenómeno, objeto, tema o idea como un concepto general, sin considerar la gran cantidad de detalles que estos puedan tener. El proceso de abstracción presenta dos aspectos complementarios.

  1. Destacar los aspectos relevantes del objeto.
  2. Ignorar los aspectos irrelevantes del mismo (la irrelevancia depende del nivel de abstracción, ya que si se pasa a niveles más concretos, es posible que ciertos aspectos pasen a ser relevantes).

De modo general podemos decir que la abstracción permite establecer un nivel jerárquico en el estudio de los fenómenos, el cual se establece por niveles sucesivos de detalles. Generalmente, se sigue un sentido descendente de detalles, desde los niveles más generales a los niveles más concretos.

12.5. Ejemplo: TDA Persona

int main(int argc, char const *argv [ ])
{
persona _t p;
ingrese _persona (&p);
//tengo que pasar la dirección memoria para que se trabaje directamente sobre la variable.
}

void ingresa _persona(persona _t *ptr)
{
printf(“DNI: “);
scanf(“%d”, &ptr == >dni);

printf("Sexo?  [0 : masculino   1 : femenino ]");  
scanf("%d", &ptr == >sexo);

printf("nombre: ");  
scanf("%s", prt == >nombre);  
.  
.  
.   }

Si hubiera tenido que incluir en la estructura un código postal por ejemplo, y ya hubiera tenido cargada 300 estructuras, seria un problema grande debido a que me vería obligado a entrar en cada estructura y agregar en CP. El sistema seria entonces muy poco mantenible. Si pasa esto es por que se uso adecuadamente la filosofía de los tipos datos abstractos, donde con solo modificar la estructura y las funciones asociadas a ella, ya seria suficiente para modificar todas las estructuras.

Ejemplo: Suponga tener una estructura tipo Persona _t *poblacion. Se debe hacer que *poblacion apunte a N personas, ingresadas por usuario e implementar las siguientes funciones:

13 . Estructuras de Datos en C

13.1. Pilas o Stacks

Una pila o stack es un conjunto ordenado de elementos, que tiene un cierto orden de inserción y de remoción. A éste orden se lo llama: LIFO ⇒ Last in, first out.

Para el tipo de TDA llamado pila, las funciones asociadas son: init, destroy, push, pop, isEmpty. Con estas cinco primitivas se logra manipular una pila. Estos elementos se denominan “interfaz”. Estas son herramientas para el trabajo sobre TDA, y es importante mencionar que son independientes de cómo se definió el TDA (dependencia de la aplicación sobre la pila).
Una implementación posible de un stack es utilizando un arreglo, pero como en realidad, el limitar la pila a un array nos limita a SIZE cantidad de elementos, podríamos creamos una función “GROW = crecer” la cual tiene por finalidad, cada vez que se agote el espacio disponible en la pila, hacerla crecer en SZ byte.

//TDA

typedef struct
{
int *pElements;
int head;
int sz;

}stack _t;

//PROTOTIPOS

stack _t *init _stack(int sz); //crear pila:

void destroy _stack(stack _t *pStack);//para destruirla:

int isEmpty _stack(stack _t *pStack);//para verificar si es vacia:

int push _stack(stack _t *pStack, int e);//para ingresar un elemento:

int pop _stack(stack _t *pStack, int *pE);//para sacar un elemento:

int isFull _stack(stack _t *pStack); //para verificar si esta llena

void print _stack(stack _t *pStack);//imprime la pila

//FUNCIONES
stack _t *init _stack(int sz)
{
stack _t *pS;

pS =(stack _t *)malloc(sizeof(stack _t));  
assert(pS);

pS - >pElements =(int *)malloc(sizeof(int)  * sz);

pS - >head =0;  
pS - >sz =sz;  
return pS;   }

void destroy _stack(stack _t *pStack)
{
free(pStack - >pElements);
free(pStack);
}

int isEmpty _stack(stack _t *pStack)
{
if(pStack - >head ==0 )
{
return 1;
}
else
{
return 0;
}
}

int push _stack(stack _t *pStack, int e)
{
if(isFull _stack(pStack)==1) //est? llena la pila
{
return 0;
}
pStack - >pElements [pStack - >head ]=e;
pStack - >head ++;
return 1;
}

int pop _stack(stack _t *pStack, int *pE)
{
if(isEmpty _stack(pStack)==1 )
return 0;

pStack - >head --;	  
 *pE =pStack - >pElements [pStack - >head ];	  
return 1;   }

int isFull _stack(stack _t *pStack)
{
if(pStack - >head ==pStack - >sz) //est? llena la pila
{
return 1;
}
return 0;
}

void print _stack(stack _t *pStack)
{
int i;
for(i =(pStack - >head -1);i >=0;i –)
{
printf(“%i n”,pStack - >pElements [i ]);
}
getch();
}

Ejemplo de uso de un Stack. Comprobación de una expresión algebraica utilizando una pila:

{ 3 + [ 4 * ( 2 + 5 ) + 4 ] + [ ( 3 + 2 ) + ( 1 + 47 ) ] + 6 }

int isOpen (char *s){
return s == ‘{‘ ||
s == ‘ [’ ||
s == ‘(‘;
}

int isClose (char *s){
return s == ‘}’ ||
s == ‘ ]’ ||
s == ‘)’;
}

int GetPair (char e){
if(e == ‘{‘)
return ‘}’;
if(e == ‘ [’)
return ‘ ]’;
if(e == ‘(‘)
return ‘)’;
if(e == ‘}’)
return ‘{‘;
if(e == ‘ ]’)
return ‘ [’;
if(e == ‘)’)
return ‘(‘;
assert(0); // Si esta funcion busca el par y no lo encuentra,
// entonces no existe, y con esto termina de comprobar.
}

int esValida (char *pExp){
stack _t *pStack = init ();
int ret = 0;
int e;

while ( *pExp)){  
	if (isOpen ( *pExp))  
		push(pStack,  *pExp);  
	if (isClose ( *pExp)){  
		if (isEmpty (pStack))  
			goto salida;  
	pop(pStack, &e);  
	if (getPair( *pExp) !=e)  
		goto salida;  
}  
pExp ++;  
  
if (isEmpty (pStack))  
	ret  = 1;  
  
salida:  
	destroy(pstack);  
	return ret;   }

La función (FILTRAR) filtra la pila obtenida quitando todas la ocurrencias de un cierto número.
La mejor forma para atacar este problema es hacerlo recursivo y para eso hay que buscar la condición trivial y la condición de recursión:

Filtrar (s, e)

Trivial ⇒ done = isEmpty(s)

  Else= x  = pop(s);  
	Filtrar(s,e);  
	If(x !=e){  
		Push(s,x);

void filtrar(stack _t *s, int e){
int x;

if(isEmpty(s))  
	return;  
else   x =pop(s);	// saco el elemento del tope de la pila   filtrar(s, e);   if(x !=e)   {  
	push(s, x);   }   }

Según lo que hemos visto con la primera estructura de datos en C,existen 3 (tres) partes fundamentales en todas las estructuras:

La Estructura Las funciones aplicadas (interfaces) Las Aplicaciones
Definición de los tipos de datos abstractos. Init Destroy Push Pop IsEmpty Esta es la parte lógica del programa. No se tiene un acceso directo a la estructura, únicamente puedo acceder a la estructura a través de las interfaces (funciones aplicadas)

13.2. Colas o Queues

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.


Conjunto de operaciones para el manejo de colas:

En caso de estar vacía, borrar un elemento sería imposible hasta que no se añade un nuevo elemento. A la hora de añadir un elemento podríamos darle una mayor importancia a unos elementos que a otros (un cargo VIP) y para ello se crea un tipo de cola especial que es la cola de prioridad.

13.2.1. Definición de la estructura “Cola”

Typedef struct{
Int head;
Int tail;
Int *elements;
Int allocated _sz;
} queve _t;

13.2.2. Creación de una “Cola”

#define DEFAUL _SZ 1024

Queue _t *create(){

queue _t  *newQ;

newQ  = (queve _t)malloc(sizeof(queve _t));

assert(newQ);

newQ - >head = 0;  
newQ - >tail = 0;  
// hacer los chequeos  
newQ - >elements =(int  *)malloc(sizeof(int)  * DEFAUL _SZ);  
newQ - >allocated _sz  =DEFAUL _SZ;

return newQ;   }

13.3. Colas de Prioridad

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.

13.3.1. Características

Este tipo especial de colas tienen las mismas operaciones que las colas, pero con la condición de que los elementos se atienden en orden de prioridad.
Ejemplos de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad.

Entendiendo la prioridad como un valor numérico y asignando a altas prioridades valores pequeños, las colas de prioridad nos permiten añadir elementos en cualquier orden y recuperarlos de menor a mayor.

13.3.2. Implementación

Hay 2 formas de implementación:

typedef struct {
void * data; // datos
int priority; // prioridad
} q _elem _t;

typedef struct
{
q _elem _t *buffer; // arreglos de elementos
int n; // n = cantidad de elementos inicial
} pri _queue _t;

13.3.3. Tipos

Las operaciones de las colas de prioridad son las mismas que las de las colas genéricas:

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

13.4.1. Operaciones

Las operaciones de las colas circulares son las mismas que las de las colas genéricas:

13.5. Contenedores Genéricos

13.5.1. Contenedores Genéricos Directos

Cuando la entidad a almacenar es la propia el contenedor. Es así porque la memoria de los elementos a usar está definida dentro de los contenedores. “Un contenedor es directo cuando la memoria del contenido es del contenedor”.

typedef struct{
int head;
int tail;
int allocated _sz;

char  *elements;   
int entity _sz;

}queue _t;

Lo importante es notar que como no se sabe el tamaño de la entidad, sólo se inicializa un arreglo de índices. Para hacer esto, la firma de la función init va a tener que cambiar, porque va a tener que alocar: pQ- >elements = “el tamaño de la variable” * entity _sz.

bool put (queve _t *pQ, int * ó char *);

bool get (queve _t *pQ, int * ó char *)

En estas funciones hay que asegurarse que el segundo parámetro que se les pasa a la funciones tenga la capacidad para almacenar un contenedor con el tamaño de la variable.

13.5.2. Contenedores Genéricos indirectos

Se denomina de ésta manera cuando la memoria del elemento esta afuera del contenedor. En lugar de guarda una copia del elemento en el contador, guardo una referencia a la memoria almacenada del elemento (puntero).

typedef struct{
int head;
int tail;
int allocated _sz;
void * *elements;
}

bool put (queue _t *pQ, void *pE);

bool get ( queve _t *pQ, void * *ppE);

En las funciones y contenedores genéricos, el void * *elements es un contenedor de punteros.
Cuando hablamos de los métodos de ordenamiento y que hacer cuando el cliente decide los parámetros de orden y nosotros el criterio de ordenamiento, usamos un puntero a función, la cual se encargaba de determinar los parámetros a usa.

void ordenar (arreglo [ ], int , ( *fun)(…) )
{

}

Entonces, teniendo esto en cuenta, cuando uno genera procedimiento y contenedores de datos, debe hacerlo de forma genérico, con lo cual no importa que tipo de datos se almacenan en la pilas, colas, etc. Por que al fin y al cabo, la forma de utilizar estos tipos de contenedores es la misma.

13.6. Listas o List enlasada

Una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior (simple) o posterior (doble).
El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato autorreferenciado porque contienen un puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio.
Existen diferentes tipos de listas enlazadas: listas enlazadas simples, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares.

Las listas se pueden definir como la primera estructura recursiva, donde definimos “L” como una lista con las siguientes propiedades:

[ ] Si está vacía
L =
e + L1

Ahora definimos el número de elementos de una lista:

		    0 si L  =  =  [  ]   NumElements( L )  = 	

		    1  + NumElements ( L1 ) si L  = e  + l1

			 Falso si L  =  [  ]   EsMiembro( L , e )  =   
			 Verdaderos si L  = { e  + p }	// donde el “+” es semántica

			 EsMiembro( L1, e ) si L  = { X  + L1 }

O sea que devuelve verdadero si la cabeza de la lista es el elemento que estoy buscando, de lo contrario, se llama a la misma función para que recorra la lista en busca de una “cabeza” que sea el elemento buscado.

			 { E  +  [  ] }  Si L  =  =  [  ]   L1  = InsertTail( L , e )  
			 { x , InsertTail( L2, e) }  si L  =  = { x  + L2 }

L1 = InsertHead ( L , e ) = { e + L } si L1 = = L

Nota: En este caso no hay recursion, por que no es necesario recorrer ninguna lista.

				 { e  +  [  ] }  L  =  [  ]   L1  = InsertOrdenado ( L , e )  = 		 { e  + L }  L  =  = { x  + L2} donde x  > e  
				 { x , InsertOrdenado ( L2, e ) } 	donde x  <= e

13.6.1. Operaciones

// TDA
typedef struct
{
  int Contenido;
  struct Lista *Siguiente;
}Lista;

/ * Prototipos de funciones de manipulación                  */

struct Lista *InsertaInicio(struct Lista *L, int Elemento);
struct Lista *InsertaFinal(struct Lista *L, int Elemento);
struct Lista *RemueveInicio(struct Lista *L, int *PElemento);
struct Lista *RemueveFinal(struct Lista *L, int *PElemento);

/ * Implementación de las funciones de manipulación          */

struct Lista *InsertaInicio(struct Lista *L, int Elemento)
{
  struct Lista *NuevoNodo = malloc(sizeof(struct Lista));
  NuevoNodo - > Contenido = Elemento;
  NuevoNodo - > Siguiente = L;
  return NuevoNodo;
}

struct Lista *InsertaFinal(struct Lista *L, int Elemento)
{
if(L == NULL){
L = malloc(sizeof(struct Lista));
L - > Contenido = Elemento;
L - > Siguiente = NULL;
} else{
L - > Siguiente = InsertaFinal(L - > Siguiente, Elemento);
return L;
}
}

struct Lista *RemueveInicio(struct Lista *L, int *PElemento)
{
  struct Lista *NuevaLista;
  if(L == NULL)
    return NULL;
  NuevaLista = L - > Siguiente;
  *PElemento = L - > Contenido;
  free(L);
  return NuevaLista;
}

struct Lista *RemueveFinal(struct Lista *L, int *PElemento)
{
  if(L == NULL)
    return NULL;
  if(L - > Siguiente == NULL)
  {
    *PElemento = L - > Contenido;
    free(L);
    return NULL;
  }
  L - > Siguiente = RemueveFinal(L - > Siguiente, PElemento);
  return L;
}

Existen dos puntos a notar con respecto al trabajo con listas:

Una lista doblemente enlazada es una estructura de datos que consiste en un conjunto de nodos enlazados secuencialmente. Cada nodo contiene dos campos, llamados enlaces, que son referencias al nodo siguiente y al anterior en la secuencia de nodos. El enlace al nodo anterior del primer nodo y el enlace al nodo siguiente del último nodo, apuntan a un tipo de nodo que marca el final de la lista, normalmente un nodo centinela o puntero null, para facilitar el recorrido de la lista. Si existe un único nodo centinela, entonces la lista es circular a través del nodo centinela.

13.7.1. Características

El doble enlace de los nodos permite recorrer la lista en cualquier dirección. Mientras que agregar o eliminar un nodo en una lista doblemente enlazada requiere cambiar más enlaces que en estas mismas operaciones en una lista enlazada simple, las operaciones son más simples porque no hay necesidad de mantener guardado el nodo anterior durante el recorrido, ni necesidad de recorrer la lista para hallar el nodo anterior, la referencia al nodo que se quiere eliminar o insertar es lo único necesario.

13.7.2. Tipos

Existen dos grupos: abiertas o cerradas (anillos). Las listas dobles son muy parecidas a las lista simples con la diferencia, que estas últimas tiene una referencias (puntero) al nodo anterior.
En base a esta diferencia, aparecen las dos topologías descriptas:

Tomando el tema de inserción en Lista Anillos, solo hay que tener en cuenta y tener cuidado cuando hacemos el direccionamiento de los punteros siguiente y anterior de los nodos de la lista.

13.7.3. Implementación

Definición de estructuras doblemente ligadas.

// estructura que maneja los punteros anterior y siguiente.
typedef struct _Chain {
struct _Chain *pPrev;
struct _Chain *pNext;
} Chain _t;

// estructura que representa un nodo
typedef struct{
void *info;
chain _t *freeList;
}list _t;

El campo info generalmente es genérico. Esto es así por que muchas veces es más conveniente tener dentro de la estructura de la información, un campo más que sea justamente la estructura con los punteros a los nodos. Esto produce estructuras mucho más genéricas. El manejo se hace a través de las estructuras de punteros que posee cada estructura de información.
Este tipo de estructuras se usa cuando se tiene un “pool” de aplicaciones de N elementos de información fija (cuyo tamaño se puede modificar)

13.7.4. Operaciones

Un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

13.8.1. Características


Es otro ejemplo de listas definidas recursivamente:

 [  ]   T   
E, t1, t2

Todas las hojas terminales son nodos sin información.

13.8.2. Operaciones

Las operaciones comunes en árboles son:

En el caso de la búsqueda, según la definición dada, no hay un método simple para encontrar un elemento en el árbol. No hay condiciones mínimas de ordenamiento. Si se establece una regla en donde el lado IZQ de un árbol es <= a “x” y el lado derecho > a “X”. A esto se lo llama formar un “diccionario” (estructura ordenada).

	 	False si el árbol es vació   Existe (T, e)	 	True	{e,  _ ,  _ }	 == >  [x, t1, t2 ]  
	  	Existe (T1, e ) si e  <= x  
	  	Existe (T2, e) si e  > x

		{e,  [  ],  [  ]} si el árbol es vació   Inserta (T, e)		{ x, Inserta (T1, e), t2 } si e  <= x   
						{ x, t1, t2}  
		{x, t1, Inserta(T2, e) } si e  > x

Cuando los árboles implementan un diccionario como política de ordenamiento, se los llama “árboles balanceado”. Estos árboles pueden garantizar búsquedas rápidas.
En el Remueve se presentan varias situaciones. En el caso de borrar nodos intermedios con hijos, se debe buscar nodos candidatos dentro del hijo del que se va a eliminar y estos candidatos son el “mayor nodo hoja de los menores” y el “menor nodo hoja de los mayores”.

		 [  ] si el árbol esta vació

		 [  ] si el caso es 			{ e,  [  ],  [  ] }

		    x  
		{ max(t1), remove(t1, x), t2 }	{ e, t1,  [  ] }    Remove ( T , e)  
		    x  
		{ min(t2), t1, remove(t2, x)}	{ e.  [  ], t2 }

		{ x, remote (t1, e), t2}		donde e  < x 	   { x, t1, t2 }  
		{ x, t1, remove (t2, e) }		donde e  > x

		TRUE si el árbol   [  ]   EstaBalanceado(T)	  
		| altura (t1) – altura (t2)|  <= 2   y  EstaBalanceado(t1) y EstaBalanceado(t2)

13.9. Tablas de Hash


Encontrar un mecanismo de búsqueda que no dependa de la cantidad de elementos que posee un contenedor de datos. Sino que cueste lo mismo buscar un elemente en 1/10 que en 1/10000000.

Vector = f (n)

Árbol (diccionario)= f(n)

Función de Hash:

E  = {conjunto de datos (definen una entidad)}

Dentro de este conjunto, se puede generar K (clave) por lo que uno va a buscar.

K(i)  = f (E)

Clave en función de la entidad.

Una función de hash, es una función que aplicada a una clave de una entidad, termina generando un “entero”.

F(k(i))  == > entero
             
    TE   TH    
             
  0 E0        
  1 E1   2    
  2 E2        
  3 E3        
  .          
  .     0 <– j  
  .          
  .          
  .          
n .         m
  .     1 <– k  
  .          
  .          
  .          
  .     n-1    
  .          
  .          
  .          
  n-1 En-1   3 <– h  
             
             
  ( f ( E0) % m ) = h     ( f (juan _pirulo) % n ) = h    

13.10. Colisiones


Una forma de manejar colisiones (situaciones en donde una misma entidad, aplicando la función de hash, genera el mismo indexado para la tabla) es generando lista de colisiones, donde un índice apunte a distintas entidades.

La relación entre “n / m” se llama el factor de carga de la tabla de hash, cuando es razonable este valor da 0,5 aprox. El tema con las tablas de hash es tener una función que distribuya razonablemente bien los valores indexados.

Manejo de archivos:

Opciones de apertura = fopen

FILE *fopen(const char *fname, const char *mode);

Modos:
W == > escritura
R == > lectura
R+== > lec y escritura(pos. Al final de lo existente)
“b”== > para habilitar la lectura en binario (escribe la imagen en memoria de la variable que vaya a almacenar el archivo)
“t” == > modo texto

Opciones de manipulación =

Binarias:
Int Fread(void *destiny, int ent _sz, int ele _qty FILE *fp);
Int Fwrite(void *destiny, int emt _sz, int ele _qty, FILE *fp);

Ambas devuelven la cantidad de elementos que pudieron ser grabadas en el archivo.
Los archivos abiertos en forma binaria tiene la ventaja de tener ACCESO ALEATORIO a traves de la funcion, la cual puede mover el puntero dentro del file.

Fseek(FILE  *, int OFFSET, int origen);

Texto:
Fprintf(FILE *fp, …);
Fscanf(FILE *fp, …);
Fputc(
Fgets(
Fputs(

Opciones de cierre = fclose

Void Fclose(FILE  *fp);

Ejercicio.

Implementar una base de datos.

Debe implementar índices.

14 . Programación Multiheading (hilo de ejecución)

Si uno abre la secuencia de instrucciones de cualquier código que trabaje con funciones (como si se tratase de un acordeón), lo que se nota, es que todas las instrucciones vienen una detrás de la otra, formando de esta manera un “hilo“ de ejecución. Se llama de esta manera debido a que abstractamente se ven como una secuencia continua, una detrás de otra, de instrucciones de código.

Definición de proceso = Es un espacio de direccionamiento y 1 (uno) ó mas hilos de ejecución.

Espacio de direccionamiento = es el espacio de memoria que pueden usar los punteros, por lo general, son espacio de 2GB de memoria virtual.
Cada proceso tiene un espacio de direccionamiento propio, siempre de 2 GB (para el ejemplo de maquinas estándar). Por lo tanto los espacios de direccionamiento son propios de cada proceso. A los sistemas operativos que trabajan de esta manera se los llama “protegidos”.

La memoria virtual, esta divida en secciones mas grande que un byte, llamada paginas, que en maquinas estándar miden aprox. 4KB. Cada pagina puede ser representada de distintas maneras y tener distintos estados, por ejemplo: RAM o de disco (en el caso del disco, este espacio es llamado el “swap del disco”), y los estados son NO USED y RESERVADO.

El “squebler” junta todos los hilos de todos los procesos (sin diferenciarlos) en una pila, cuado el ultimo hilo termina, significa que termino el programa. En principio, el squebler no diferencia entre procesos, pero puede que dependiendo de la prioridad que el sistema operativo le de a un determinado proceso, se procese un hilo ante que otro o no.

Para poder hacer programas que permitan realizar tareas en multiheading, se debe incluir en el código del programa el header fila del sistema operativo que contenga las directivas necesarias para poder ejecutar procesos de esta manera.

#include

Investigar la función: “CreateThread(….,….,….,….,…, ( *f)()”
“Mutex(…,….,…,)”
“CriticalRegions(…,…,…,…,)”

Esta función tiene uno de los argumentos que es precisamente un puntero a una función. La razón de esto es que el procesador de tiempo para la ejecución de la función F

CreateThread

The CreateThread function creates a thread to execute within the address space of the calling process.

HANDLE CreateThread(
LPSECURITY _ATTRIBUTES lpThreadAttributes, // pointer to security attributes
DWORD dwStackSize, // initial thread stack size
LPTHREAD _START _ROUTINE lpStartAddress, // pointer to thread function
LPVOID lpParameter, // argument for new thread
DWORD dwCreationFlags, // creation flags
LPDWORD lpThreadId // pointer to receive thread ID
);

Parameters

lpThreadAttributes
Pointer to a SECURITY _ATTRIBUTES structure that determines whether the returned handle can be inherited by child processes. If lpThreadAttributes is NULL, the handle cannot be inherited.

Windows NT: The lpSecurityDescriptor member of the structure specifies a security descriptor for the new thread. If lpThreadAttributes is NULL, the thread gets a default security descriptor.

dwStackSize
Specifies the initial commit size of the stack, in bytes. The system rounds this value to the nearest page. If this value is zero, or is smaller than the default commit size, the default is to use the same size as the calling thread. For more information, see Thread Stack Size.
lpStartAddress
Pointer to the application-defined function of type LPTHREAD _START _ROUTINE to be executed by the thread and represents the starting address of the thread. For more information on the thread function, see ThreadProc.
lpParameter
Specifies a single 32-bit parameter value passed to the thread.
dwCreationFlags
Specifies additional flags that control the creation of the thread. If the CREATE _SUSPENDED flag is specified, the thread is created in a suspended state, and will not run until the ResumeThread function is called. If this value is zero, the thread runs immediately after creation. At this time, no other values are supported.
lpThreadId
Pointer to a 32-bit variable that receives the thread identifier.

Windows NT: If this parameter is NULL, the thread identifier is not returned.

Windows 95 and Windows 98: This parameter may not be NULL.

Return Values

If the function succeeds, the return value is a handle to the new thread.

If the function fails, the return value is NULL. To get extended error information, call GetLastError.

Windows 95 and Windows 98: CreateThread succeeds only when it is called in the context of a 32-bit program. A 32-bit DLL cannot create an additional thread when that DLL is being called by a 16-bit program.

Remarks

The new thread handle is created with THREAD _ALL _ACCESS to the new thread. If a security descriptor is not provided, the handle can be used in any function that requires a thread object handle. When a security descriptor is provided, an access check is performed on all subsequent uses of the handle before access is granted. If the access check denies access, the requesting process cannot use the handle to gain access to the thread.

The thread execution begins at the function specified by the lpStartAddress parameter. If this function returns, the DWORD return value is used to terminate the thread in an implicit call to the ExitThread function. Use the GetExitCodeThread function to get the thread’s return value.

The CreateThread function may succeed even if lpStartAddress points to data, code, or is not accessible. If the start address is invalid when the thread runs, an exception occurs, and the thread terminates. Thread termination due to a invalid start address is handled as an error exit for the thread’s process. This behavior is similar to the asynchronous nature of CreateProcess, where the process is created even if it refers to invalid or missing dynamic-link libraries (DLLs).

The thread is created with a thread priority of THREAD _PRIORITY _NORMAL. Use the GetThreadPriority and SetThreadPriority functions to get and set the priority value of a thread.

When a thread terminates, the thread object attains a signaled state, satisfying any threads that were waiting on the object.

The thread object remains in the system until the thread has terminated and all handles to it have been closed through a call to CloseHandle.

The ExitProcess, ExitThread, CreateThread, CreateRemoteThread functions, and a process that is starting (as the result of a call by CreateProcess) are serialized between each other within a process. Only one of these events can happen in an address space at a time. This means that the following restrictions hold:

A thread that uses functions from the C run-time libraries should use the beginthread and endthread C run-time functions for thread management rather than CreateThread and ExitThread. Failure to do so results in small memory leaks when ExitThread is called.

Windows CE: The lpThreadAttributes parameter must be set to NULL. The dwStackSize parameter must be zero. Only zero or CREATE _SUSPENDED values are supported for the dwCreationFlags parameter.

CMutex

An object of class CMutex represents a “mutex” — a synchronization object that allows one thread mutually exclusive access to a resource. Mutexes are useful when only one thread at a time can be allowed to modify data or some other controlled resource. For example, adding nodes to a linked list is a process that should only be allowed by one thread at a time. By using a CMutex object to control the linked list, only one thread at a time can gain access to the list.

To use a CMutex object, construct the CMutex object when it is needed. Specify the name of the mutex you wish to wait on, and that your application should initially own it. You can then access the mutex when the constructor returns. Call CSyncObject::Unlock when you are done accessing the controlled resource.

An alternative method for using CMutex objects is to add a variable of type CMutex as a data member to the class you wish to control. During construction of the controlled object, call the constructor of the CMutex data member specifying if the mutex is initially owned, the name of the mutex (if it will be used across process boundaries), and desired security attributes.

To access resources controlled by CMutex objects in this manner, first create a variable of either type CSingleLock or type CMultiLock in your resource’s access member function. Then call the lock object’s Lock member function (for example, CSingleLock::Lock). At this point, your thread will either gain access to the resource, wait for the resource to be released and gain access, or wait for the resource to be released and time out, failing to gain access to the resource. In any case, your resource has been accessed in a thread-safe manner. To release the resource, use the lock object’s Unlock member function (for example, CSingleLock::Unlock), or allow the lock object to fall out of scope.

#include

IPC = Mecanismos de sincronización.

Semáforos. Es un recurso que da el sistema operativo para indicar a un proceso cuando puede realizar una acción.

Ejercicio de empleo de recursos:

Semáforos: Es un objeto de sincronización que tiene dos estados: activo y no-activo. Asociado tiene contadores, los cuales posee dos estado: activo cuando CTN > 0 y NO-ACTIVO= =0.
Igual que lo contenedores de datos, los semáforos poseen operaciones asociadas similares.