ESTRUCTURAS Y ALGORITMOS II (I Bimestre Abril Agosto 2011)

ESTRUCTURAS DE DATOS Y ALGORITMOS II

ESCUELA:

NOMBRES:

Ciencias de la Computación

Ing. Danilo Jaramillo H

BIMESTRE: Primer

Orientaciones

• Realizar el trabajo de forma personal

• Utilizar el EVA www.utpl.edu.ec

– Contestar los foros, revisar, ejercicios, evaluaciones resueltas, problemas, Material adicional

• Asesorías con el profesor

– 07 – 2570 275 ext. 2637 (viernes de 8h00-12h00)

– Mail: [email protected]

– Chat msn: [email protected]

– skype: danilo.jaramillo.h

RECURSIVIDADDirecta.

Cuando una función se llama a si misma.

Indirecta

Cuando una función inicial (A) llama a una segunda función (B) y esta función (B) llama a la función inicial (A)

Infinita

cuando no se logra que termine la recursión

RECURSIVIDADint factorial(int n) {

if (n == 1) // caso base

return 1

Else

return n * factorial(n-1)

}

RECURSIVIDADFactorial de 5 = 5 * factorial (4)

Factorial de 4 = 4 * factorial (3)



Factorial de 1 = 1 (caso base)

---------------------

Factorial de 2 = 2 * factorial (1) = 1 2




int sumardigitos_r (int n){if (n == 0) //caso base

return n;else

return (n % 10) + sumardigitos_r (n / 10);}

RECURSIVIDAD#include <string.h>int sumardigitos (int num){int d;

int sum= 0;while (num>0){

d = num % 10;sum = sum + d;num = num / 10;

}return sum;

}

void main (){Int numero=34567;printf("%d \n",sumardigitos(numero)); printf("%d \n",sumardigitos_r(numero));

}

RECURSIVIDADint BusquedaBinaria(int lista[], int inf, int sup, int num) {

Int pos;

if (Inicio > Fin)

return -1;

else {

pos = (Inicio + Fin) / 2;

if (num < lista[pos])

return(BusquedaBinaria(lista, inf, pos - 1, num));

else

if (num > lista[pos])

return(BusquedaBinaria(lista, pos + 1, Fin, num));

else

return(pos);

}

}

ARCHIVOS

• Texto

– cadenas

• Binarios

– Registros, campos

• Organización

– Secuencial

– Directa

– Secuencial Indexada

ARCHIVOS – modificadores de acceso

Modo Modificadores de acceso

a Abre un archivo para añadir.

a+ Añade o crea un archivo para lectura / escritura.

r Abre un archivo lectura.

r+ Abre un archivo para lectura / escritura

w Crea un archivo para escritura.

w+ Crea un archivo para lectura / escritura

rb Abre un archivo para lectura.

r+b Abre un archivo para lectura / escritura.

wb Crea un archivo para escritura.

w+b Crea un archivo para lectura / escritura.

ab Abre un archivo para añadir.

a+b Añade o crea un archivo para lectura / escritura.

TEXTO

BINARIO

ARCHIVOS - funcionesNombre Función

fopen() abre un archivo.

fclose() cierra un archivo.

fputs() escribe una cadena en un archivo

fgets() lee una cadena de un archivo.

fprintf() escribe una salida con formato en el archivo.

rewind() localizador de posición de archivo al inicio del mismo

fseek() busca un byte específico de un archivo.

feof() Devuelve verdadero fin del archivo.

ferror() Devuelve verdadero si se produce un error.

remove() elimina un archivo.

fflush() borra el contenido un archivo.

#include <stdio.h> // librería de trabajo

int main () {

FILE * pArch; //puntero al archivo

pArch = fopen ("mytexto.???","w");

if (pArch!=NULL) {

fputs ("fopen example",pArch);

fclose (pFile); }

return 0;

}

¿Qué tipo de archivo

estamos trabajando?

¿dónde hay error de

sintaxis?

#include <stdio.h> // librería de trabajo

int main () {

FILE * pArch; //puntero al archivo

pArch = fopen ("mytexto.txt","w");

if (pArch!=NULL) {

fputs ("fopen example",pArch);

fclose (pFile); }

return 0;

}

texto

puntero

ARCHIVOS - funcionespf=fopen(archivo,”rb”);

While (!eof(pf)

fwrite(&buf, sizeof(registro),1,pf);

}

Fclose(pf);

ARBOLES

• Estructura dinámica

• Direcciones física de la memoria, puede crecer

raíz

Hojas

Nodos

(padre)

Nivel 0

ARBOL

BINARIO

Nivel 1

Nivel 2

Nivel 3

Profundidad 4

rama

subárbol

árbol binario estructura.

• Cada nodo tiene la siguiente forma:

G

B

A C

H

E

izq info der

NULL

ARBOLES – recorrido

• En orden: izquierda, raíz, derecha

• Pre orden raíz, izquierda, derecha

• Post orden izquierda, derecha, raíz

50

30 70

20 40 60 80

15 3525 45 55 65 75 85

50

30 70

20 40 60 80

15 3525 45 55 65 75 85

• En orden (izquierdo, raíz, derecho) 15,20,25,30,35,40,45,50,55,60,65,70,75,80,86

1

2

3

4

5

6

7

ARBOLES BINARIOS – recorrido• En orden:

15,20,25,30,35,40,45,50,55,60,65,70,75,80,86

• Pre orden:

• 50,30,20,15,25,40,35,45,70,60,55,65,80,75,85

• Post orden:

• 15,25,20,35,45,40,30,55,65,60,75,85,80,70,50

ARBOLES – aplicación expresiones

+

* +

1 2 * 5

3 4

(1* 2) + 3 * 4 + 5

¿Qué tipo de

recorrido se

esta usando?

#include <stdio.h>

#include <stdlib.h>

struct Elemento {

int informacion;

struct Elemento* izq;

struct Elemento* der;

};

typedef struct Elemento Nodo;

Nodo* crearRaiz();

void Insertar(Nodo* Ptr, Nodo** dir, int x);

void PreOrden(Nodo* nodo);

void EnOrden(Nodo* nodo);

void PostOrden(Nodo* nodo);

void dibujar(Nodo* nodo, int nivel);

void Eliminar(Nodo** r, int dato, Nodo **dir);

void Reemplazar(Nodo** act);

void Insertar2(Nodo* Ptr, int x);

Nodo* pRaiz;

int dato;

Nodo* crearRaiz() {

Nodo* pTmp = NULL;

pTmp = malloc(sizeof(Nodo));

printf("Ingrese la informacion de la raiz: ");

scanf("%d", &dato);

dato = 50;

pTmp->informacion = dato;

pTmp->izq = NULL;

pTmp->der = NULL;

return pTmp;

}

void Insertar(Nodo* Ptr, Nodo** dir, int x) {

Nodo* pNuevo = NULL;

if (Ptr == NULL)

{

pNuevo = malloc(sizeof(Nodo));

pNuevo->informacion = x;

pNuevo->izq = NULL;

pNuevo->der = NULL;

*dir = pNuevo;

}

else

{

if (x < Ptr->informacion)

Insertar(Ptr->izq, &(Ptr->izq), x);

else

Insertar(Ptr->der, &(Ptr->der), x);

}

}

void PreOrden(Nodo* nodo)

{

if (nodo)

{

printf("%d, ",nodo->informacion);

PreOrden(nodo->izq);

PreOrden(nodo->der);

}

}

Puntero a puntero

a FFX0 10

ptr FFX1 FFX0

Ptr_ptr FFX2 FFX1

Int a = 10

Int* ptr

……..

ptr = &a

…..

*ptr = 200

int** ptr_ptr_a;

.......

ptr_ptr_a = &ptr_a;

.......

*(*ptr_ptr_a) = 300;

Puntero a puntero#include <stdio.h>main() {

int a = 100; int* ptr_a;int** ptr_ptr_a; ptr_a = &a; *ptr_a = 200; printf("\n\n Valor de a: %d", a); ptr_ptr_a = &ptr_a;*(*ptr_ptr_a) = 300; printf ("\n\n Valor de a: %d", a); printf ("\n\n");

}

PROGRAMA: Estructuras de Datos y Algoritmos II Carrera: Ciencias de la Computación

Fecha: 19 de abril del 2011

Docente: Ing. Danilo Jaramillo H

Hora Inicio: 18h00 Hora Final: 19h00

GUIÓN DE PRESENTACIÓN

Puntos de la Presentación

Intervienen Duración Aprox. en minutos

Material de Apoyo

- Presentación-Objetivos-Orientaciones

Danilo Jaramillo H • 5 minutos Sin material.Sin material.

-Recursividadexplicación y preguntas

Danilo Jaramillo H • 20 minutos Diapositivas 3,4,5,6

Archivos: tipos, instrucción, organizacion

Danilo Jaramillo H *15 7-13

Arboles: recorridos, aplicación

Danilo Jaramillo H *20 14-28

Education

ESTRUCTURAS Y ALGORITMOS II (I Bimestre Abril Agosto 2011)