Clase 13mod - Algoritmos iterativos/recursivos para listas ligadas PDF

Preview

Summary

Algoritmos iterativos/recursivos para listas ligadas...

Description

Contenido

Listas ligadas, ejemplos de algoritmos iterativos

Crear listas de forma recursiva

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

1

´ requiere memoria, incorrecto Funcion

incorrecto. ¿ Que´ olvide en este c´ odigo? Codigo ´ 1 t y ped ef s t r u c t TNODE{ 2 i nt label ; 3 d ou bl e x , y ; 4 s t r u c t TNODE ∗next ; 5}NODE; 6 7 t y ped ef NODE∗ NODEPTR; 8 9NODEPTR cr eateN od e ( i n t l a b e l , do uble x , do u bl e y ) 10{ 11 NODEPTR nnode ; 12 nnode= m all o c ( s i z e o f (NODE) ) ; 13 nnode−>l a b e l = l a b e l ; 14 nnode−>x= x ; 15 nnode−>y= y ; 16 r e t u r n nnode ; 17}

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

2

´ correcto para requerir memoria Codigo

1 t y ped ef s t r u c t TNODE{ 2 i nt label ; 3 d ou bl e x , y ; 4 s t r u c t TNODE ∗next ; 5}NODE; 6 7 t y ped ef NODE∗ NODEPTR; 8 9NODEPTR cr eateN od e ( i n t l a b e l , do uble x , do u bl e y ) 10{ 11 NODEPTR nnode ; 12 nnode = (NODEPTR) m a ll o c ( s i z e o f (NODE) ) ; 13 nnode−>l a b e l = l a b e l ; 14 nnode−>x= x ; 15 nnode−>y= y ; 16 nnode−>n ext =NULL ; 17 r e t u r n nnode ; 18}

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

3

Crear lista, incorrecto

Codigo ´ incorrecto. 1 t y ped ef s t r u c t TNODE{ 2 i nt label ; 3 d ou bl e x , y ; 4 s t r u c t TNODE ∗next ; 5}NODE; 6 7 t y ped ef NODE∗ NODEPTR; 8 i n t main ( i n t ar gc , c har ∗ar g v [ ] ) 9{ 10 i nt label ; 11 d ou bl e x , y ; 12 NODEPTR r o o t ; 13 do 14 { 15 s c anf ( ”%d % l f %l f ” , &l a b e l , &x , &y ) ; 16 i f ( label ) 17 r o o t =c reate Nod e ( l a b e l , x , y ) ; 18 } w h i l e ( l a b e l ) ; 19 r et ur n 0; 20}

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

4

Crear lista, correcto

1 i n t main ( i n t ar gc , c har ∗ar g v [ ] ) 2{ 3 4 i nt label ; 5 d ou bl e x , y ; 6 NODEPTR r o o t =NULL ; / / / Hay que i n d i c a r que no hay nada 7 do 8 { 9 s c anf ( ”%d % l f %l f ” , &l a b e l , &x , &y ) ; 10 i f ( label ) { 11 i f ( root ){ 12 NODEPTR n ex t = r o o t ; 13 w h i l e ( nex t−>nex t ) 14 next = nex t−>nex t ; 15 nex t−>n ext = cre ate Nod e ( l a b e l , x , y ) ; 16 } el s e 17 r o o t =c reate Nod e ( l a b e l , x , y ) ; / / Pr i m er nodo 18 } 19 } w h i l e ( l a b e l ) ; 20 21 r et ur n 0; 22}

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

5

Remover lista

1 v o i d r em o ve Lis t (NODEPTR r o o t ) 2{ 3 NODEPTR n ex t = r o o t ; 4 w h i l e ( nex t !=NULL) 5 { 6 i f ( next−>nex t ! = NULL) { 7 w h i l e ( nex t−>nex t−>nex t !=NULL) 8 next = nex t−>nex t ; 9 f r e e ( n ex t−>nex t ) ; 10 p r i n t f ( ” L:%p\n ” , next−>nex t ) ; 11 nex t−>n ext =NULL ; 12 n ex t = r o o t ; 13 }els e{ 14 f r e e ( nex t ) ; 15 p r i n t f ( ” L:%p\n ” , nex t ) ; 16 n ex t =NULL ; 17 } 18 19 } 20}

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

6

Remover lista

1 v o i d r em o ve Lis t (NODEPTR r o o t ) 2{ 3 NODEPTR n ex t = r o o t ; 4 w h i l e ( nex t !=NULL) 5 { 6 i f ( next−>nex t ! = NULL) { 7 w h i l e ( nex t−>nex t−>nex t !=NULL) 8 next = nex t−>nex t ; 9 f r e e ( n ex t−>nex t ) ; 10 p r i n t f ( ” L:%p\n ” , next−>nex t ) ; 11 nex t−>n ext =NULL ; 12 n ex t = r o o t ; 13 }els e{ 14 f r e e ( nex t ) ; 15 p r i n t f ( ” L:%p\n ” , nex t ) ; 16 n ex t =NULL ; 17 } 18 19 } 20}

Se puede borrar la lista tambien ´ comenzando desde el primer nodo, y moviendo el root. S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

6

Recordatorio: algoritmos recursivos

Comentamos que los elementos para generar un algoritmo recursivo son: 1. Un caso base. 2. Una llamada a si mismo (con un caso mas simple). 3. Cambiar el estado y moverse en direccion del caso base.

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

7

Impresion de una lista de numeros ´

Supongamos que tenemos una lista simplemente ligada de (enteros). Los elementos de un metodo ´ de impresion ´ numeros ´ de la lista ser´ıa: 1. Caso base: lista vac´ıa (apuntador en NULL). 2. Cambiar el estado y moverse en direccion ´ de caso base: genero un lista mas pequena. ˜ 3. Una llamada a si mismo: si la lista no esta vac´ıa el metodo ´ se debe de llamar a si mismo con la lista mas ´ pequena. ˜

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

8

struct

9

FUNCION( RAIZ )

NODO 0 DATOS LINK

NODO 1 DATOS LINK

NODO 2 DATOS LINK

NODO 3 DATOS LINK

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

NULL

struct

10

FUNCION( RAIZ ) NODO 0 DATOS LINK

NODO 1 DATOS LINK

NODO 2 DATOS LINK

NODO 3 DATOS LINK

Si RAIZ no es NULL RAIZ=RAIZ->LINK FUNCION( RAIZ )

NODO 1 DATOS LINK

NODO 2 DATOS LINK

NODO 3 DATOS LINK

NULL

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

NULL

struct

11

FUNCION( RAIZ ) NODO 1 DATOS LINK

NODO 0 DATOS LINK

NODO 2 DATOS LINK

NODO 3 DATOS LINK

Si RAIZ no es NULL RAIZ=RAIZ->LINK FUNCION( RAIZ )

NODO 1 DATOS LINK

NODO 2 DATOS LINK

NODO 3 DATOS LINK

NULL

Si RAIZ no es NULL RAIZ=RAIZ->LINK FUNCION( RAIZ )

NODO 2 DATOS LINK

NODO 3 DATOS LINK

NULL

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

NULL

struct

12

FUNCION( RAIZ ) NODO 1 DATOS LINK

NODO 0 DATOS LINK

NODO 2 DATOS LINK

NODO 3 DATOS LINK

Si RAIZ no es NULL RAIZ=RAIZ->LINK FUNCION( RAIZ )

NODO 2 DATOS LINK

NODO 1 DATOS LINK

NODO 3 DATOS LINK

NULL

Si RAIZ no es NULL RAIZ=RAIZ->LINK FUNCION( RAIZ ) NODO 3 NODO 2 DATOS DATOS LINK LINK Si RAIZ no es NULL RAIZ=RAIZ->LINK FUNCION( RAIZ )

NULL

NODO 3 DATOS NULL LINK Si RAIZ no es NULL RAIZ=RAIZ->LINK FUNCION( RAIZ ) NULL (APLICAR CASO BASE)

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

NULL

´ recursiva para sumar Ejemplo funcion

1 t y ped ef s t r u c t ESTRUCTURA{ 2 i n t d at o ; 3 s t r u c t ESTRUCTURA ∗ p t r ; 4}DATO; 5 t y ped ef DATO∗ PTRDATO; 6 i n t suma (PTRDATO r o o t ) 7{ 8 i n t sum= 0 ; 9 i f ( r o o t ! = NULL) { 10 sum=suma ( r o o t−>p t r ) + r o ot −>dat o ; 11 r e t u r n sum ; 12 } 13 r e t u r n sum ; 14} 15 16 i n t main ( ) 17{ 18 PTRDATO r o o t = l e e l i s t a ( ) ; 19 p r i n t f ( ” Suma de l o s e lemento s=%d\n\n ” ,suma ( r o o t ) ) ; 20 b o r r a l i s t a ( r o o t ) ; 21 r e t u r n 0 ; 22}

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

13

Tarea 7 En el archivo leon.txt que subir ´e a moodle, existen un conjunto de puntos estrat ´egicos del municipio de le´on guanajuato. El archivo contienen las siguientes columnas etiqueta, identificador de municipio, identificador de regi´ on, latitud, longitud, rural/urbana. Se desea recorrer todos estos puntos de la forma mas barata. Lo que deben entregar en la tarea es: programa Generar una lista donde cada nodo sea un punto con la informaci´ on relevante para determinar la longitud total del recorrido. programa Cambiar el orden de la lista con respecto de la etiqueta de manera aleatoria. programa Imprimir un archivo de texto donde se imprima el orden (de las etiquetas) en que se deben de recorrer los puntos. reporte Incluya en su reporte una gr ´afica del recorrido y la distancia total del recorrido. del programa Verifique que la distancia este bien calculada, despu´es de recorrer todos los puntos se tiene que regresar al punto inicial. La lista de indices/etiquetas impresos de la salida de su programa pueden leerla en R, octave, matlab, etc. y verificar que los calculos dentro de su programa sean correctos. Si el c ´alculo de la distancia es incorrecto, el porgrama est ´a MAL, es mejor verificarlo. ◮ Realice el programa con funciones iterativas y con funciones recursivas. Que NO deben entregar en la tarea: ◮ Algoritmo que calcula la menor distancia, o que aproxime la menor distancia, eso es el bonus, su programa de tarea, solo debe de leer los datos, crear la lista, aleatorizar la lista, calcular la distancia e imprimir las etiquetas correspondientes a la lista aleatorizada. S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

14

BONUS

BONUS. Proponga una manera de encontrar la menor distancia posible en a lo mas 15 min de c´ omputo con un procesador i7. La mejor distancia encontrada (sin bugs en el programa ni chanchuyos) tendr´ a lo equivalente a 1 tarea. La segunda mejor 0.6 tarea, y la tercera mejor 0.3 tareas. A considerarse en la primera parte del curso. La forma de medir ser´ a: ejecutar 3 veces el programa y tomar el mejor de las distancias obtenidos. El BONUS debe someterse a mas tardar el lunes siguiente a las 23:55, envien el/los archivos con los datos de entrada para hacer 3 ejecuciones (se verificar´a que el programa funcione con otros datos de entrada, pero sus datos de entrada ser´an tomados en cuenta para las ejecuciones que compitan).

S. Ivvan Valdez — Clase 13. Algoritmos iterativos/recursivos para listas ligadas

15...