13/02/2014

1

ALGORITMOS Y ESTRUCTURA DE

DATOS

LISTAS, PILAS y COLAS

Listas: descripcin lgica

LISTA = coleccin de elementos homogneos entre los que existe una relacin lineal Cada elemento de la lista, a excepcin del primero, tiene

un nico predecesor

Cada elemento de la lista, a excepcin del ltimo, tiene un nico sucesor

Nodos y enlaces

Listas: descripcin lgica

Orden de nodos afecta a la funcin de acceso Segn orden de insercin Segn clave

EjemploLista de calificaciones ::= + {}::= + + + + +

Listas: descripcin lgica

Listas Arrays Listas son flexibles y permiten cambio de implementacin

Operaciones Insertar, Borrar, Modificar, etc.

Tipos de listas Simples

Ordenadas Pilas

Colas Doblemente enlazadas (LDE)

Circulares

REALIZAR EL PROGRAMA QUE INGRESE A UNA LISTA ENLAZADA NUMEROS

ENTEROS. EL PROGRAMA DEBE TERMINAR DE INGRESAR NUMEROS CUANDO

SE INGRESE CERO, LUEGO SE DEBERA IMPRIMIR LOS NUMEROS DE LA LISTA..

REALIZAR EL PROGRAMA QUE INGRESE A UNA LISTA ENLAZADA NUMEROS ENTEROS. EL PROGRAMA DEBE TERMINAR DE INGRESAR NUMEROS CUANDO SE INGRESE CERO, LUEGO SE DEBERA IMPRIMIR LOS NUMEROS DE LA LISTA.CON LA CANTIDAD DE DIVISORES

13/02/2014

2

EJERCICIO REALIZAR EL PROGRAMA QUE INGRESE A UNA ESTRUCTURA

DINAMICA LISTA LOS DATOS DE LOS ALUMNOS DE UN COLEGIO: CODIGO, APELLIDOS Y NOMBRES, AO DE ESTUDIOS, SEXO, EXAMEN PARCIAL, EXAMEN FINAL, PROMEDIO DE PRCTICA. SE PIDE IMPRIMIR UN REPORTE QUE INCLUYA A LOS DATOS DE ENTRADA EL PROMEDIO DE CADA ALUMNO Y AL PIE DEL REPORTE IMPRIMIR LA CANTIDAD DE ALUMNOS APROBADOS Y DESAPROBADOS POR AO DE ESTUDIO Y SEXO A LA VEZ.

7

SOLUCION

8

9

La pila (stack) es una estructura ordenada de elementos en la que se pueden insertar o remover elementos por un extremo llamado la cima de la pila (stack top).El apuntador de pila (stack pointer) seala al elemento de la cima.La pila puede carecer por completo de elementos, en tal caso se le llama pila vaca. En una pila vaca el apuntador de pila seala a NULL. Una pila

Cima de la pila

Apuntador de pila

LA PILA

Las operaciones bsicas de la pila son:Apilar (push(s, i)) - inserta un nuevo elemento a la pila.Desapilar (pop(s)) - remueve el elemento de la cima de la pila.

ABCD

Pila antes de Push(s, E)

ABCD

Pila despus de Push(s, E)

E

ABCD

Pila antes de i Pop(s)

ABC

Pila despus de i Pop(s)

i=D

OPERACIONES BSICAS EVOLUCIN DE UNA PILA

13/02/2014

3

La funcin EMPTY(S) es verdadera si la pila est vaca.La operacin STACKTOP(S), que es equivalente a un POP seguido de un PUSH.

I = POP(S);PUSH(S,I);

determina el valor del elemento de la cima sin removerlo.

OTRAS OPERACIONES

REALIZAR EL PROGRAMA QUE INGRESE A UNA ESTRUCTURA DE DATOS DINAMICA PILA N NUMEROS ENTEROS. SE PIDE CALCULAR E IMPRIMIR ATRAVES DE UN REPORTE LOS NUMEROS DE LA PILA Y SU FACTORIAL CORRESPONDIENTE. EL CALCULO DEL FACTORIAL DEBERA HACERSE MEDIANTE UNA FUNCION RECURSIVA.

Colas Cola = coleccin ordenada de elementos homogneos en la que slo se pueden

aadir elementos por el final y se eliminan por el principio (frente) filosofa FIFO

Definicin ::= + + {} ::= ::= ( | NULL) ::= ::= + < informacion > ::= {}

TAD Cola: operaciones

desencolar(nombreCola) informacionExtraccin de nodos

encolar(nombreCola, valorInfo)Insercin de nodos

colaVacia(nombreCola) Booleano

colaLlena(nombreCola) Booleano

Comprobacin del estado

crearCola (nombreCola)Creacin de cola

asignarInfo(referenciaNodo, valorInformacion)

asignarEnlace(referenciaNodo, valorEnlace)

Modificacin de los nodos

info(referenciaNodo) Informacion

siguiente(referenciaNodo) Enlace

Acceso a los nodos

cabecera(nombreCola) informacionAcceso a la cabecera*

* Opcional: Accede a la cabecera sin eliminarla

REALIZAR EL PROGRAMA QUE INGRESE A UNA ESTRUCTURA DE DATOS DINAMICA COLA NOMBRES DE PERSONAS Y LUEGO LOS IMPRIMA EN PANTALLA. EJERCICIOS

1.- REALIZAR EL PROGRAMA QUE INGRESE A UNA LISTA ENLAZADA LOS DATOS DE LOS ARTICULOS DE UN ALMACEN:

- CODIGO, - DESCRIPCION, - TIPO DE ARTICULO (PRUEDE SER ALFA, BETA O GAMMA), - PRECIO UNITARIO, - CANTIDAD.

SE PIDE IMPRIMIR UN REPORTE QUE INCLUYA A LOS DATOS DE ENTRADAS EL IMPORTE DE CADA ARTICULO, ASI COMO AL PIE DE REPORTE SE DEBERA IMPRIMIR EL TOTAL DE IMPORTE POR TIPO.

13/02/2014

4

EJERCICIOS2.- REALIZAR EL PROGRAMA QUE INGRESE A UNA ESTRUCTURA DINAMICA LISTA LOS DATOS DE LOS ALUMNOS DE UN COLEGIO:

- CODIGO, - APELLIDOS Y NOMBRES, - AO DE ESTUDIOS, - SEXO, - EXAMEN PARCIAL, - EXAMEN FINAL, - PROMEDIO DE PRCTICA.

SE PIDE IMPRIMIR UN REPORTE QUE INCLUYA A LOS DATOS DE ENTRADA EL PROMEDIO DE CADA ALUMNO Y AL PIE DEL REPORTE IMPRIMIR LA CANTIDAD DE ALUMNOS APROBADOS Y DESAPROBADOS POR AO DE ESTUDIO Y SEXO A LA VEZ.

EJERCICIOS3.- REALIZAR UN PROGRAMA QUE INGRESE LAS CITAS DE LOS PACIENTES DE UNA CLINICA ESTOS DEBEN ESTAR EN ESTRUCTURA DINAMICA LISTA LOS DATOS DE LOS PASCIENTES SON:

- CODIGO PACIENTE, - APELLIDOS Y NOMBRES, - ESPECIALIDAD ATENDERSE(PUEDE SER

0 - ODONTOLOGIAP - PEDIATRIAM - MEDICINA GENERALU - UROLOGIA

- DIA, - TURNO ( MAANA, TARDE O NOCHE)SE PIDE IMPRIMIR LOS PACIENTE QUE SACARON CITA EL DIA, EL TURNO Y LA ESPECIALIDAD