Upload
elvira-gonzalez
View
68
Download
0
Embed Size (px)
Citation preview
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 1/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 1
PILAS
REPRESENTACION DE PILAS
Arreglos Listas
OPERACIONES CON PILAS Insertar un elemento - Push - en la pila. Eliminar un elemento - Pop - en la pila.
Operaciones auxiliares Pila_vacía Pila_llena
Pila _ vacíaEste algoritmo verifica si una estructura tipo pila – PILA – está vacía, asignando a BANDel valor de verdad correspondiente. La pila se implementa en un arreglo unidimensional.TOPE es un parámetro de tipo entero. BAND es un parámetro de tipo booleano
Pila _ vacía (PILA, TOPE, BAND)
Si (tope = o) (verifica si no hay elementos almacenados en la pila) entoncesBand verdadero (la pila está vacía)
SinoBand falso (la pila no está vacía)
Fin si
Pila _llenaEste algoritmo verifica si una estructura tipo pila – PILA – está llena asignando a BANDel valor de verdad correspondiente. La pila se implementa en un arreglo unidimensional deMAX elementos. Tope es un parámetro tipo entero. BAND es un parámetro booleano
Pila _llena (PILA, TOPE, MAX, BAND)
Si (tope = max) entoncesBand verdadero (la pila está llena)
SinoBand falso (la pila está vacía)
Fin si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 2/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 2
INSERTAR Este algoritmo agrega el elemento – DATO – en una estructura tipo pila – PILA – ; si lamisma no está llena actualiza el valor de TOPE, MAX, representa el numero máximo deelementos que puede almacenar pila. Tope es un parámetro tipo entero
Insertar (PILA, TOPE, MAX, DATO)
Llamar Pila _ llena (PILA, TOPE, MAX, BAND)Si BAND = “Verdadero” entonces
Imprimir “desbordamiento” (la pila esta llena)Sino
TOPE TOPE + 1PILA (TOPE) DATO
Fin si
QUITAR Este algoritmo saca un elemento _ dato de una estructura tipo pila_pila, si esta no seencuentra vacía. El elemento que se elimina es el que se encuentra en la posición indicada
por TOPE.
Quitar (PILA, TOPE, DATO)
Llamar a PILA _ VACÍA (PILA, TOPE, BAND)Si BAND = “Verdadero” entonces
Imprimir “Subdesbordamiento_pila vacía)”Sino
DATO PILA (TOPE)TOPE TOPE - 1
Fin si
APLICACIONES DE PILAS Llamadas a subprogramas Recursividad Tratamiento de expresiones aritméticas Ordenación
CONVERSIÓN DE NOTACIÓN INFIJA A POSTFIJA
CONVERSIÓN DE NOTACIÓN INFIJA A PREFIJA
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 3/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 3
EI: expresión infijaEPRE: expresión prefijaConv_Prefija(EI,EPRE)Tope0Mientras EI < > cadena vacía
Tomar el símbolo más a la derecha de EIRecortar la expresiónSi el símbolo es paréntesis derecho entonces
(Insertar el símbolo a la pila)Llamar a Insertar (Pila, Tope, Max, Simbolo)
SinoSi símbolo es paréntesis izquierdo entonces
Mientras (Pila(TOPE), < > Paréntesis derecho entoncesLlamar a Sacar (PILA, TOPE, DATO)
EPRE EPRE + DATOFin mientras(Sacamos el paréntesis derecho de pila y no se agrega a EPRE)Llamar a Sacar (PILA, TOPE, DATO)
SinoSi símbolo es un operando entonces
Agregar símbolo a EPRESino
(Es un operador)
Llamar Pila_vacia (PILA, TOPE, BAND)Mientras (BAND = falso y (la prioridad del operador sea menor que
la prioridad del operador que está en la cima de la Pila))Llamar a Sacar (PILA, TOPE, DATO)EPREEPRE + DATOLlamar a Pila_vacia (PILA, TOPE, BAND)
Fin mientrasLlamar Insertar (PILA, TOPE, MAX, SÍMBOLO)
FinsiFinsi
FinsiFin mientras
Llamar Pila_vacia (PILA, TOPE, BAND)Mientras BAND = falso
Llamar a Sacar (PILA, TOPE, DATO)EPREEPRE + DATOLlamar a Pila_vacia (PILA, TOPE, BAND)
Fin mientrasImprimir EPRE en forma invertida
LA CLASE PILA
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 4/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 4
COLAS
Estructura lineal de datos en las que los elementos se introducen por un extremo y los queya existentes se eliminan por el otro. Se eliminan ene. Mismo orden que fueron insertados,esta características hace que el nombre de la estructura sea (FIFO)
REPRESENTACION DE COLALas pilas y las colas son estructuras de datos estándar en programación. Este tipo deestructuras se puede representar mediante Arreglos Listas
OPERACIONES CON COLAS Insertar un elemento en la cola. Eliminar un elemento en la cola.
Operaciones auxiliares Cola_vacía Cola_llena
Inserta_cola
Este algoritmo inserta elemento dato al final de una estructura tipo cola.FRENTE Y FINAL son los parámetro que indica, respectivamente, el inicio y fin deCOLA. La primera vez FRENTE Y FINAL tiene valor cero, ya que la cola esta vacía.MAX es el máximo número de elemento que puede almacenar la cola
Inserta_cola (COLA, MAX, FRENTE, FINAL, DATO)Si FINAL < MAX entonces - verifica que hay espacio libre -
FINAL FINAL + 1 (actualiza FINAL)
COLA(FINAL) DATOSi FINAL = 1 entonces (se insertó el primer elemento de COLA)
FRENTE 1Fin si
Si noImprimir “desbordamiento - Cola llena”
Fin si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 5/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 5
Elimina_colaEste algoritmo elimina el primer elemento de una estructura tipo cola y la almacena enDATO. FRENTE Y FINAL son los punteros que indican respectivamente el inicio y fin decola
Elimina_cola (COLA, FRENTE, FINAL, DATO)Si FRENTE < > 0 entonces (verifica que la cola no este vacía)DATO = COLA (FRENTE)Si FRENTE = FINAL entonces (verifica si hay un solo elemento)
FRENTE 0FINAL 0 (indica cola vacía)
Si no
FRENTE FRENTE + 1
Fin siSi no
Imprimir desbordamiento cola_vaciaFin si
Cola_vaciaEste algoritmo determina si una estructura de dato tipo cola esta vacía, asignando a BANDel valor de verdad correspondiente.
Cola_vacia (COLA, FRENTE, BAND)
Si FRENTE = 0 entoncesBAND verdadero
Si noBANDfalso
Fin si
Cola _ llenaEste algoritmo determina si una estructura tipo cola esta llena, asignando a BAND el valor de verdad correspondiente, donde MAX es el numero máximo de elemento que puedealmacenar colaCola _ llena (COLA, FINAL, MAX, BAND)
Si FINAL = MAX entoncesBAND verdadero
Si noBAND falso
Fin si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 6/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 6
COLAS CIRCULARES
Inserta_Circular Este algoritmo inserta el elemento DATO al final de una estructura tipo colacircular -COLACIR -.FRENTE y FINAL, son los punteros que indican, respectivamente el inicioy el final de la Cola Circular. MAX, es el número máximo de elementos que puede tener COLACIR .
Inserta_Circular (COLACIR, MAX, FRENTE, FINAL; DATO)Si ((FINAL=MAX) y (FRENTE=1)) o ((FINAL+1)=FRENTE) Entonces.
IMPRIMIR “desbordamiento Cola Llena”Sino
Si (FINAL=MAX) Entonces.FINAL 1
SinoFINAL FINAL + 1
FinsiCOLACIR (FINAL) DATOSi (FRENTE=0) Entonces.
FRENTE 1Finsi
Finsi
Elimina_CircularEste algoritmo elimina el primer elemento de una estructura tipo Colacircular -COLACIR - y lo almacena en DATO. FRENTE y FINAL, son punteros que indican,respectivamente el inicio y el final de la estructura. MAX, es el tamaño de COLACIR .Elimina_Circular (COLACIR, MAX, FRENTE, FINAL, DATO)
Si (FRENTE = 0) Entonces “Verifica si esta vacía”IMPRIMIR “Desbordamiento Cola vacía”
SinoDATOCOLACIR (FRENTE)Si (FRENTE = FINAL) Entonces. “Verifica si hay un solo elemento”
FRENTE0FINAL0
SinoSi (FRENTE = MAX) Entonces.
FRENTE1Sino
FRENTEFRENTE +1Finsi
FinsiFinsi
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 7/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 7
APLICACIONES DE COLAS Colas de impresión (una sola impresora para atender a varios usuarios). Sistemas de tiempo compartido (compartir recursos como CPU y memoria, los
procesos se asignan a una cola de espera, suponiendo que todos tienen una misma prioridad)
LA CLASE COLA
RECURSIVIDAD
Factorial_rec (N)
Si N = 0 entonces
Factorial_rec 1 - (Paso Básico)
Sino
Factorial_rec N* Factorial_rec(N-1) – (llamada paso recursivo)
Fin si
Este algoritmo calcula el factorial de un número N en forma recursiva, donde N es un valor numérico entero, positivo o nulo.
Cuando se realiza una llamada recursiva, se utiliza en forma implícita una estructura tipo pila para almacenar las instrucciones pendientes de ejecutar con todos los valores quetienen la variable o constante en ese momento. Cuando se terminó la ejecución se llega alestado básico, se toma la instrucción que se encuentra en TOPE de la pila y se continúaoperando. Esta acción se repite hasta que la pila queda vacía.
Ejemplos iterativos
Factorial_ite(N)FACT 1Mientras (N > 0)
FACT N * FACT N N – 1
Fin MientrasImprimir FACT
Este algoritmo calcula la factorial de un número N en forma iterativa donde N es un valor numérico entero, positivo o nulo. FACT es una variable de tipo entero.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 8/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 8
Factorial2_ite (N)FACT 1Desde X = 2 hasta N
FACT FACT * X
Fin DesdeImprimir FACTEste algoritmo calcula el factorial de un número N en forma iterativa donde N es un valor numérico entero, positivo o nulo. FACT y X son variables de tipo entero.FIBONACCI
Fibonacci_rec (N)Si (((N = 0) o (N = 1))) entonces
Fibonacci_rec < N – Paso Básico – Sino
Fibonacci_rec < Fibonacci_rec (N - 1) + Fibonacci_rec (N - 2) -llamadasrecursivas
Fin si
Este algoritmo (Fibonacci_rec (N) ) calcula el número Fibonacci correspondiente a N enforma recursiva, donde N es un valor numérico entero, positivo o nulo.
Fibonacci_ite (N)Si ((N= 0) o (N = 1)) entonces
FIBO NSino
FIBA 0FIBB 1X 2
Fin siMientras (X < = N)
FIBO FIBB + FIBAFIBAFIBBFIBBFIBOX X + 1
Fin MientrasImprimir FIBO
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 9/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 9
Recursividad en Árboles. Los árboles son estructuras inherentemente recursivas.Recursividad en Ordenación y Búsqueda.
LISTAS
Las listas son colecciones de elementos llamados nodos; el orden entre éstos se establece por medio de un tipo de dato denominado puntero, apuntadores, direcciones oreferencias a otros nodos.Es importante distinguir entre un dato de tipo apuntador y el dato contenido en la celda alcual éste apunta.La notación P ^D indica que P es un apuntador al nodo D.Crear (P) señala el proceso de asignación de memoria al nodo P.
Quitar (P) señala el proceso inverso, es decir, cuando se libera una posición de memoria apuntada por P.
LISTAS SIMPLEMENTE LIGADAS
OPERACIONES CON LISTAS SIMPLEMENTE LIGADAS Recorrido de la lista. Inserción de un elemento.
Borrado de un elemento. Búsqueda de un elemento.
OPERACIÓN DE INSERSIÓN SIMPLEMENTE LIGADA
• Insertar un nodo al inicio de la lista• Insertar un nodo al final de la lista• Insertar un nodo antes que otro cuya información es X• Insertar un nodo después que otro cuya información es X
No se considera en estos algoritmos que la lista esté vacía, se considerará que la lista en laque se va a insertar ya existe, es decir que ya tiene un nodo.
a) Inserción al inicio de la Lista Simplemente Ligada
Inserta _ Inicio
Este algoritmo agrega un nodo al inicio de una lista simplemente ligada. P es el apuntador
al nodo de la misma y DATO es la información que se almacenará en el nuevo nodo. Q esuna variable de tipo apuntador. INFO y LIGA son los campos de cada nodo de la lista.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 10/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 10
Inserta _ inicio (P, DATO)
Crear (Q)Q^.INFO DATOQ^.LIGA PP Q
b) Inserción al final de una Lista Simplemente Ligada
Inserta _ Final
Este algoritmo inserta un nodo al final de una lista. P es el apuntador al primer nodo de la
lista y DATO es la información que se almacenará en el nuevo nodo. Q y P son variablesde tipo puntero. INFO y LIGA son los campos de cada nodo.
Inserta _ Final (P, DATO)
T PMientras (T^.LIGA <> NIL) – recorre la lista hasta llegar al último elemento –
T T^.LIGAFin Mientras
Crear (Q)Q^.INFO DATOQ^.LIGA NILT^.LIGA Q
c) Inserción de un nodo antes que otro en una Lista Simplemente LigadaInserta _ Antes _ X
Este algoritmo inserta un nodo antes de un nodo dado como referencia en una listasimplemente ligada. P es el apuntador al primer nodo se la lista. DATO indica la
información que se almacena en el nuevo nodo, y X representa el contenido – información – del nodo dado como referencia. Q, X, T son variables de tipo apuntador. INFO, LIGAson los campos de los nodos de la lista. BAND es una variable de tipo entero.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 11/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 11
Inserta _ Antes _ X (P, DATO, X)Q PBAND 1Mientras (Q^.INFO <> X) Y (BAND = 1)
Si (Q^.LIGA <> NIL) entoncesT QQ Q^.LIGA
SinoBAND 0
Fin SiFin Mientras
Si (BAND = 1) entonces
CREAR (X)X^.INFO DATOSi (P = Q) entonces – el nodo dado como referencia es el primero –
X^.LIGA PP X
SinoP^.LIGA XX^.LIGA Q
Fin Si
SinoImprimir “El nodo como referencia no se encuentra en la lista”
Fin Si
d) Inserción de un nodo después que otro en una Lista Simplemente Ligada
Inserta _ Después _ X
Este algoritmo inserta un nodo después de otro nodo dado como referencia en una listasimplemente ligada. P es el apuntador al primer nodo de la lista. DATO indica lainformación que se almacenará en un nuevo nodo, X representa el .contenido – información – del nodo dado como referencia. Q, T son variables de tipo apuntador. INFO,LIGA son los campos de los nodos de la lista. BAND es una variable tipo entero.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 12/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 12
Inserta _ Después _ X (P, DATO, X)Q PBAND 1
Mientras (Q^.INFO<>X) Y (BAND = 1)Si (Q^.LIGA <> NIL) entonces
Q Q^.LIGASino
BAND 0Fin Si
Fin MientrasSi (BAND = 1) entonces
CREAR (T)T^.INFO DATOT^.LIGA Q^.LIGAQ^.LIGA T
SinoImprimir “El nodo dado como referenciado NO se encuentra en la lista”
Fin SiELIMINACIÓN EN LISTAS SIMPLEMENTE LIGADAS Eliminar el primer nodo.
Eliminar el último nodo Eliminar un nodo con información X. Eliminar el nodo anterior al nodo con información X. Eliminar el nodo posterior al nodo con información X.
a) Eliminar el primer nodo de una Lista Simplemente LigadaEste algoritmo permite eliminar el primer nodo de una lista simplemente ligada.P es el apuntador al primer nodo de la lista.Q es una variable de tipo apuntador. INFO, LIGA son los campos de los nodos de la lista
Elimina _ inicio (P)Q ← P ´ (si la lista tuviera solo un elemento entonces a P se le asignaría NIL
que es el valor de Q^.LIGA en caso contrario quedaría con ladirección del siguiente nodo)
P ← Q^.LIGA ´ (Redefine al puntero a inicio de la lista)
Quitar (Q)
b) Eliminar el último nodo de una Lista Simplemente Ligada
Este algoritmo permite eliminar el último nodo de una Lista Simplemente Ligada.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 13/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 13
P es el apuntador al primer nodo de la lista.Q, T son variables del tipo apuntador. INFO,LIGA son los campos de los nodos de la lista.
Elimina_ ultimo (P)Q ← PSi (P^.LIGA= NIL) entonces ´ (se verifica si la lista tiene un solo elemento)
P ← NILSino ´ (no es solo un elemento)
Mientras Q^.LIGA < > NILT ← QQ ← Q^.LIGA
Fin mientrasT^.LIGA ← NIL
Fin si
Quita (P)
c) Eliminar un nodo con información X de una Lista Simplemente LigadaEste algoritmo elimina un nodo con información X de una Lista Simplemente Ligada.P es el apuntador al primer nodo de la lista.Q, T son variables del tipo apuntador. BAND es una variable de tipo entero.INFO, LIGA son los campos de los nodos de la lista.
Elimina_ X (P, X)
Q ← PBAND ← 1Mientras (Q^.LIGA < > X) y (BAND =1)
Si (Q^.LIGA < > NIL) entoncesT ← QQ ← Q^.LIGA
SinoBAND ← 0
Fin siFin mientrasSi BAND = 0 entonces
Imprimir “el elemento con información X no se encuentra en la lista”Sino
Si (P=Q) entonces ´ (se verifica si el elemento a eliminar es el primero)P ← Q^.LIGA
SinoT^.LIGA ← Q^.LIGA
Fin siQuitar (Q)
Fin si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 14/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 14
d) Eliminar el nodo anterior al nodo con información X en una Lista SimplementeLigada
Elimina_antes_ X (P, X)Este algoritmo elimina el nodo anterior al nodo con información X de una ListaSimplemente Ligada.P es el apuntador al primer nodo de la lista.Q, T y R son variables del tipo apuntador. BAND es una variable de tipo entero.INFO, LIGA son los campos de los nodos de la lista.
Si (P^.INFO = X) entoncesImprimir “No existe un nodo que preceda al que contiene información X”
Sino
Q PT PBAND 1Mientras (Q^.INFO < > X) y (BAND = 1)
Si (Q^.LIGA < > NIL) entoncesR TT Q
Q ← Q^.LIGASino
BAND 0Fin si
Fin mientrasSi BAND = 0 entonces
Imprimir “el elemento no se encuentra en la lista”Sino
Si (P^.LIGA = Q) entonces (se verifica si el elemento a eliminar es el primero)
P QSino
R^.LIGA QFin siQuitar (T)
Fin siFin si
LISTAS CIRCULARES
LISTAS DOBLEMENTE LIGADAS
OPERACIONES CON LISTAS DOBLEMENTE LIGADAS
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 15/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 15
• Recorrido de la lista• Inserción de un elemento• Borrado de un elemento
INSERCIÓN EN LISTAS DOBLEMENTE LIGADA
• Al inicio de la lista doblemente ligada• Al final de la lista doblemente ligada• Antes/después de un nodo con información X
a) Inserción al inicio de la lista doblemente ligada
Este algoritmo inserta un nodo al inicio de una lista doblemente ligada. P es el puntador al
primer nodo de la lista y DATO es la información que se almacenará en el nuevo nodo. Qes una variable de tipo apuntador. INFOR, LIGADER, LIGAIZQ son los campos de cadanodo de la lista.
Inserta_princicpio (P, DATO)
Crear (Q)Q^.INFOR DATOQ^.LIGADER PP^.LIGAIZQ Q
Q^.LIGAIZQ NILP Q
b) Inserción al final de la lista doblemente ligada
En este caso el nuevo nodo se coloca al final de la lista doblemente ligada, convirtiéndoseen el último.Este algoritmo inserta un nodo al final de una lista doblemente ligada. F es el puntador alúltimo nodo de la lista y DATO es la información que se almacenará en el nuevo nodo. Q
es una variable de tipo puntero. INFOR, LIGADER, LIGAIZQ son los campos de cadanodo de la lista.
Inserta_final (F, DATO)
Crear (Q)Q^.INFOR DATOF^.LIGADER QQ^.LIGAIZQ FQ^.LIGADER NILF Q
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 16/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 16
c) Inserción de un nodo antes que otro en una lista doblemente ligada
En este caso el nuevo nodo se coloca precediendo a otro dado como referencia.
Este algoritmo inserta un nodo antes que otro dado como referencia, con información X Pes el puntador al primer nodo de la lista y DATO es la información que se almacenará enel nuevo nodo. Q, T y R son variables de tipo puntero. INFOR, LIGADER, LIGAIZQson los campos de cada nodo de la lista.
Inserta_antes_X (P, DATO, X)
Q PMientras ( (Q^:LIGADER < > NIL ) y ( Q^.INFOR < > X )
Q Q^.LIGADER
Fin Mientras
Si ( Q^.INFOR = X ) entoncesCrear T - se crea el nuevo nodo -T^.INFOR DATOT^.LIGADER QR Q^.LIGAIZQQ^.LIGAIZQ TSi ( P = Q ) entonces
P TT^.LIGAIZQ NILSino
R^.LIGADER TT^.LIGAIZQ R
Fin SiSino
Imprimir “El elemento no se encuentra en las lista“Fin Si
ELIMINACIÓN EN LISTAS DOBLEMENTE LIGADA• Eliminar el primer nodo• Eliminar el último nodo• Eliminar el nodo con información X• Eliminar el nodo anterior/posterior con información XPara los casos de borrado de un elemento de la lista, no se considerará que ésta seencuentre vacía.a) Eliminar el primer nodo de una lista doblemente ligada
Consiste en quitar el primer nodo de la lista, cualquiera sea su información, redefiniendo el puntero al inicio de la misma.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 17/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 17
Este algoritmo elimina el primer nodo de una lista doblemente ligada. P y F son losapuntadores al primer y último nodo de la lista, respectivamente.Q es una variable de tipo puntero. INFOR, LIGADER, LIGAIZQ son los campos de cadanodo de la lista.
Elimina_inicio ( P, F )Q PSi (Q^:LIGADER < > NIL ) entonces - verifica si la lista tiene un solo nodo -
P Q^.LIGADER P^.LIGAIZQ NIL
SinoP NILF NIL
Fin SiQuitar (Q)
b) Eliminar el último nodo de una lista doblemente ligada
Este algoritmo elimina el último elemento de una lista doblemente ligada. P y F son losapuntadores al primer y último nodo de la lista, respectivamente.Q es una variable de tipo puntero. INFOR, LIGADER, LIGAIZQ son los campos de cadanodo de la lista.
Elimina_ultimo ( P, F )
Q FSi (Q^:LIGAIZQ < > NIL ) entonces - verifica si la lista tiene un solo nodo -
PF Q^.LIGAIZQP^.LIGADER NIL
SinoF NILP NIL
Fin SiQuitar (Q)
c) Eliminar un nodo con información X
Este algoritmo elimina el nodo con información X de una lista doblemente ligada. P y Fson los apuntadores al primer y último nodo de la lista, respectivamente.Q, T y R son variables de tipo apuntador. INFOR, LIGADER, LIGAIZQ son los campos
de cada nodo de la lista.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 18/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 18
Elimina_X ( P, F, X )
Q PMientras ( (Q^:LIGADER < > NIL ) y ( Q^.INFOR < > X )
Q Q^.LIGADER Fin Mientras
Si ( Q^.INFOR = X ) entoncesSi (( Q = P ) y ( Q = F )) entonces
P NILF NIL
SinoSi ( Q = P ) - es el primero –
P Q^.LIGADER P^.LIGAIZQ NIL
SinoSi ( Q = F ) - es el último –
F Q^.LIGAIZQF^.LIGADER NIL
Sino - es u nodo intermedio -
T Q^.LIGAIZQR Q^.LIGADER T^.LIGADER R R^.LIGAIZQ T
FinsiFinsi
FinsiSino
Imprimir ““El elemento con información X no se encuentra en las lista“Finsi
d) Eliminar el nodo anterior al nodo con información X
Este algoritmo elimina, si se puede, el nodo anterior a aquel que contiene la informaciónX de una lista doblemente ligada. P es el apuntador al primer nodo de la lista. Q, T y R son variables de tipo apuntador. INFOR, LIGADER, LIGAIZQ son los campos de cadanodo de la lista.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 19/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 19
Elimina_antes_X ( P, X )
Q PMientras ( (Q^:LIGADER < > NIL ) y ( Q^.INFOR < > X )
Q Q^.LIGADER Fin Mientras
Si ( Q^.INFOR = X ) entoncesSi ( P = Q ) entonces
Imprimir “No existe nodo anterior al primero“Sino
T Q^.LIGAIZQSi ( P = T ) entonces - es el primer nodo de la lista –
P QP^.LIGAIZQ NIL
SinoR T^.LIGAIZQQ^.LIGAIZQ R R^.LIGADER Q
FinsiQuitar (T)
Finsi
SinoImprimir ““El elemento con información X no se encuentra en las lista“
Finsi
LISTAS DOBLEMENTE LIGADAS CIRCULARES
En las listas doblemente ligadas circulares, el campo liga izquierda del primer nodo de lalista apunta al último, y el campo liga derecha de éste apunta al primero.
Simplemente ligadas circulares
Simplemente ligadasLISTAS
Doblemente ligadas
Doblemente ligadas circulares
LA CLASE LISTA
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 20/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 20
ÁRBOLES
ÁRBOLES BINARIOSOPERACIONES EN ÁRBOLES BINARIOSCrea _ árbol Esta algoritmo crea un árbol en memoria APNODO es una variable de tipo ENLACE –
puntero a un nodo- . La primera vez APNODO se crea en el programa principal.INFO, IZQ, DER son campos del registro NODO.INFO es de tipo carácter. IZQ, DER es de tipo apuntador. Las variables RESP y OTROson de tipo carácter y de tipo ENLACE respectivamente.Crea_ árbol (APNODO)
Leer APNODO^.INFO ` (lee la información y se guarda en el nodo)
Ingresar “existe nodo por la izquierda: SI /NO”, RESP
Si RESP= “SI” entoncesCrea (OTRO) ` (se crea un nuevo nodo)APNODO^.IZQ ← OTRORegresa a crea _ árbol con APNODO^.IZQ ` (llamada recursiva)
SinoAPNODO^.IZQ ← NIL
Fin si
Ingresar “existe nodo por la derecha: SI /NO”, RESP
Si RESP= “SI” entoncesCrea (OTRO) ` (se crea un nuevo nodo)APNODO^.DER ← OTRORegresa a crea _ árbol con APNODO^.DER ` (llamada recursiva)
SinoAPNODO^.DER ← NIL
Fin siPREORDENEste algoritmo realiza el recorrido en preorden de un árbol binario. APNODO es unregistro de tipo ENLACE – puntero a un nodo – INFO, IZQ, DER son campos del registro nodo, INFO es un variable tipo carácter; IZQ,DER, son de tipo puntero.PREORDEN (APNODO)Si (APNODO ≠ NIL) entonces
Visitar el APNODOImprimir APNODO^.INFORegresar a Preorden con APNODO^.IZQ ` (llamada recursiva a preorden con
la rama izquierda del nodo en cuestión)Regresar a Preorden con APNODO^.DER ` (llamada recursiva a preorden
con la rama derecha del nodo en cuestión)Fin si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 21/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 21
Observación:Cabe destacar que el término visitar se puede reemplazar por cualquier otra instrucciónvalida por ejemplo:Imprimir, sumar o comparar la información del nodo. Esta aclaración se aplica también
para los otros tipos de recorrido.
IN ORDEN
Este algoritmo realiza el recorrido in orden de un árbol binario. APNODO es un registrode tipo enlace – puntero a un nodo – INFO, IZQ Y DER son los campos del registro nodo. INFO es una variable de tipocarácter IZQ Y DER son variables del tipo puntero
IN ORDEN (APNODO)
Si APNODO <> NIL entoncesRegresar IN ORDEN con APNODO^.IZQ - llamada Recursiva
a InOrden con la rama izquierda del nodo en cuestión-Visitar el APNODOImprimir APNODO^.INFORegresar a IN ORDEN con APNODO^.DER – Llamada Recursiva
a In Orden con la rama derecha del nodo en cuestión –
Fin Si
POST ORDEN (APNODO)
Este algoritmo realiza el recorrido post orden de un árbol binario. APNODO es un registrode tipo enlace – puntero a un nodo – INFO, IZQ Y DER son los campos del registro nodo. INFO es una variable de tipocarácter IZQ Y DER son variables del tipo puntero
Si APNODO <> NIL entonces
Regresar POSTORDEN con APNODO^.IZQ - llamada Recursiva aPost Orden con la rama izquierda delnodo en cuestión-
Regresar a POST ORDEN con APNODO^.DER – Llamada Recursiva aPost Orden con la rama derecha delnodo en cuestión –
Visitar el APNODOImprimir APNODO^.INFO
Fin Si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 22/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 22
ÁRBOLES BINARIOS DE BÚSQUEDA
Este algoritmo localiza el nodo del árbol binario de búsqueda que contiene la informaciónINFOR, que se esta buscando. APNODO es un parámetro de tipo enlace – la primera vezapunta a la raíz del árbol - . Se asume que el árbol no es vacío
Búsqueda_ABB (APNODO, INFOR)
Si (INFOR < APNODO^.INFO) entoncesSi APNODO^.IZQ = NILL entonces
Imprimir “La información no se encuentra en el árbol”
Sino
Regresar a Búsqueda_ABB (APNODO^.IZQ e INFOR) – llamadarecursiva -
Fin Si
Sino
Si (INFOR > APNODO^.INFO) entoncesSi (APNODO^.DER = NIL) entonces
Imprimir “La información no se encuentra en el árbol “
Sino
Regresar a Búsqueda_ABB (APNODO^.DER e INFOR) – Llamada recursiva –
Fin SiSino
Imprimir “La información está en el árbol “
Fin SiFin Si
Otra forma de escribir el algoritmo de búsqueda es la siguiente (es variante contempla elcaso que el árbol esta vacío)
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 23/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 23
BÚSQUEDA DE UNA INFORMACIÓN EN UN ÁRBOL BINARIO
Este algoritmo localiza el nodo del árbol binario de búsqueda que contiene ciertainformación – INFOR - parámetro de tipo entero APNODO es una variable de tipoENLACE. La primera vez, apunta a la raíz del árbol.
Búsqueda_V1_ABB (APNODO, INFOR)
Si (APNODO <> NILL) entonces
Si (INFOR< APNODO^.INFO) entonces
Regresar a Búsqueda_V1_ABB con APNODO^.IZQ e INFOR – llamadarecursiva –
SinoSi (INFOR > APNODO^.INFO) entonces
Regresar a Búsqueda_V1_ABB con APNODO^.DER e INFOR – llamada recursiva –
Sino
Imprimir “La información se encuentra en el árbol”
Finsi
Fin Si
Sino
Imprimir “La información NO se encuentra en el árbol”
Fin si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 24/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 24
INSERCIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDAEl algoritmo realiza la inserción de un nodo en un árbol binario de búsqueda. APNODO esuna variable de tipo puntero y la primavera vez debe ser distinta de vacía. INFOR es un
parámetro de tipo entero que contiene la información que se quiere insertar en un nuevonodo. Se utiliza además, como auxiliar, la variable OTRO de tipo puntero
Inserción_ABB (APNODO, INFOR)
Si (INFOR < APNODO^.INFO) entonces
Si (APNODO^.IZQ= NILL) entonces
Crear (OTRO)OTRO^.IZQ < NIL
OTRO^.DER < NILOTRO^.INFO < INFOR APNODO^.IZQ < OTRO
SinoRegresar a Inserción_ABB con APNODO^.IZQ e INFOR – llamada
recursiva – Fin Si
Sino
Si (INFOR > APNODO^.INFO) entonces
Si (APNODO^.DER=NILL) entonces
Crear (OTRO) - Se crea un nuevo nodo – OTRO^.IZQ < NILOTRO^.DER < NILOTRO^.INFO < INFOR APNODO^.DER < OTRO
Sino
Regresar a Inserción_ABB con APNODO^.DER e INFOR – llamada recursiva –
Fin SiSino
Imprimir “El nodo ya se encuentra en el árbol”Fin Si
Fin Si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 25/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 25
INSERCIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA CON UNA VARIANTE
El Algoritmo realiza la inserción de un elemento en un árbol binario de búsqueda.APNODO es una variable de tipo ENLACE, la primera vez apunta a la raíz del árbol.INFOR es un parámetro de tipo entero que contiene la información del elemento que sequiere insertar.
Inserción_V1_ABB (APNODO, INFOR)
Si (APNODO <> NILL) entonces
Si (INFOR < APNODO ^.INFO) entonces
Regresar a Inserción_V1_ABB con APNODO^.IZQ e INFOR
– llamada recursiva – Sino
Si (INFOR > APNODO^.INFO) entonces
Regresar a Inserción_V1_ABB con APNODO^.DER e INFOR – llamada recursiva –
SinoImprimir “La información ya se encuentra en el árbol “
Fin si
Fin Si
Sino
Crear (OTRO) - Se crea un nuevo nodo -OTRO^.IZQ < NILOTRO^.DER < NILOTRO^.INFO < INFOR APNODO < OTRO
Fin Si
ELIMINACIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 26/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 26
ORDENACIÓN
ORDENACION INTERNA
Ordenación Quicksort. Ordenación Heapsort (montículo).
ORDENACION EXTERNA
En la actualidad es muy común procesar tales volúmenes de información que los no se pueden almacenar en la memoria principal de la computadora. Estos datos, organizados enarchivos, se guardan en dispositivos de almacenamiento secundarios como cintas, discos,etc. El proceso de ordenar los datos almacenados en varios archivos se conoce como
fusión o mezcla, se entiende por este concepto a la combinación o intercalación de dos amás secuencias ordenadas en una única secuencia ordenada
Se debe hacer hincapié que solo se colocan en la memoria principal de la computadora losdatos que se pueden acceder en forma directa
Por intercalación de archivos se entiende la unión o fusión de dos o más archivos,ordenados de acuerdo a un determinado campo clave, en un solo archivo
Ordenación Externa:
Intercalación de archivos. Ordenación por mezcla directa
ORDENACION INTERNA
ORDENACION POR EL METODO QUICK SORT
El método de ordenación Quick Sort es el más eficiente de ordenación interna.
Es también conocido como el método rápido y de ordenación por partición.
Este algoritmo ordena los elementos del arreglo unidimensional utilizado por el métodorápido de manera recursiva. A es un arreglo unidimensional de N elementos.INI, y FIN representan las posiciones del extremo izquierdo y derecho, respectivamente,del conjunto de elementos a ordenar.
IZQ, DER, POS y AUX son variables de tipo entero. BAND es una variable tipo booleano.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 27/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 27
Rápido_ Recursivo(A, N)Llamar a Reduce _ recursivo (1, N)
Reduce_ Recursivo (INI, FIN)IZQ ← INIDER ← FINPOS ← INIBAND ← VERDADEROMientras BAND = VERDADERO
BAND ← FALSOMientras ([A (POS) ≤ A (DER)] y [POS<>DER])
DER ← DER-1Fin mientras
Si POS < > DER entoncesAUX ← A (POS)A (POS) ← A (DER)A (DER) ← AUXPOS ← AUXMientras ([A (POS) ≥ A (IZQ)] y [POS<>IZQ])
IZQ ← IZQ+1Fin mientrasSi POS < > IZQ entonces
BAND ← VERDADEROAUX ← A (POS)A (POS) ← A (IZQ)A (IZQ) ← AUXPOS ← AUX
Fin siFin si
Fin mientras
Si ([POS-1] INI) entoncesRegresar a Reduce_ Recursivo (INI, [POS-1])
Fin si
Si (FIN> [POS+1]) entoncesRegresar a Reduce_ Recursivo ([POS+1] FIN)
Fin si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 28/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 28
RAPIDO _ ITERACTIVO
Este algoritmo ordena los elementos de un arreglo unidimensional (vector). Utilizando elmétodo rápido (Quick Sort) de manera iterativa. A es una arreglo unidimensional de Nelementos. TOPE, INI, FIN POS son variables de tipo entero. PILA MENOR, PILAMAYOR son arreglos unidimensionales (vectores) que funciona como pilas.
Rápido_ iterativo (A, N)TOPE ← 1PILA MENOR ← 1PILA MAYOR ← NMientras TOPE > 0
INI ← PILA MENOR (TOPE)FIN ← PILA MAYOR (TOPE)
TOPE ← TOPE – 1Llamar a Reduce _ iterativo (INI, FIN, POS)Si INI < (POS – 1) entonces
TOPE ← TOPE + 1PILA MENOR (TOPE) ← INIPILA MAYOR (TOPE) ← (POS – 1)
Fin Si
Si FIN > (POS + 1) entonces
TOPE ← TOPE + 1PILA MENOR (TOPE) ← (POS + 1)
PILA MAYOR (TOPE) ← FINFin Si
Fin Mientras
REDUCE _ ITERATIVO
INI, FIN representan las posiciones de los extremos izquierdo y derecho, respectivamente,de elementos a evaluar. POS es una variable donde se almacenara el resultado de estealgoritmo. IZQ, DER, AUX son variables de tipos enteros. BAND es una variable de tipo
booleano.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 29/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 29
Reduce _ iterativo (INI, FIN, POS)IZQ ← INIDER ← FINPOS ← INIBAND ← VERDADEROMientras BAND= VERDADERO
Mientras ([A (POS) <= A (DER)] y [POS< >DER])DER ← DER-1
Fin MientrasSi POS= DER entonces
BAND ← FALSOSi No
AUX ← A (POS)A (POS) ← A (DER)
A (DER) ← AUXPOS ← DER Mientras ([A (POS) >= A (IZQ)] y [POS< >IZQ])
IZQ ← IZQ+1Fin mientrasSi POS = IZQ entonces
BAND ← FALSOSi No
AUX ← A (POS)
A (POS) ← A (IZQ)A (IZQ) ← AUXPOS ← AUX
Fin siFin si
Fin mientras
ORDENACION POR MONTICULO (Heapsort)
INSERTA _MONTICULO
El algoritmo inserta los elementos en n montículo representado como arreglo.A es un arreglo unidimensional de N elementos. X, K y AUX son variables de tipo entero.
BAND es una variable de tipo booleano. IND es un índice.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 30/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 30
INSERTA_MONTICULO(A,N)DESDE X = Z HASTA N
K XBAND VERDADEROMIENTRAS [ ( K>1 ) Y ( BAND = VERDADERO ) ]
BAND FALSOIND INT( K/2)SI A(K) > A(IND) ENTONCES
AUX A(IND)A(IND) A(K)A(K) AUXK INT(K/2)BAND VERDADERO
FIN SIFIN MIENTRAS
FIN DESDEELIMINA_MONTICULOEl algoritmo elimina la raíz del montículo en forma repetida. A es un arreglounidimensional de N elementos. X, AUX, IZQ, DER, K y APE son variables de tipoentero. BOOL es una variable tipo booleanoELIMINA_MONTICULO(A,N)DESDE X = N HASTA 2 EN PASOS DE -1
AUX A(X)A(X) A(1)IZQ 2
DER 3K 1BOOL VERDADEROMIENTRAS [ ( IZQ < X ) Y ( BOOL = VERDADERO ) ]
MAYOR A(IZQ)AP IZQSI ( MAYOR < A(DER) Y DER <> X )
MAYOR A(DER)AP DER
FIN SI
SI ( AUX < MAYOR ) ENTONCESA(K) A(AP)K A(AP)
SINOBOOL FALSO
FIN SIIZQ K x 2DER IZQ + 1
FIN MIENTRAS
A(K) AUXFIN DESDE
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 31/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 31
MONTICULO
El algoritmo ordena los elementos del arreglo utilizando el método montículo.A es un arreglo unidimensional de N elementos
MONTICULO (A,N)LLAMAR AL ALGORITMO INSERTA _ MONTÍCULO(A,N)LLAMAR AL ALGORITMO ELIMINA _ MONTÍCULO(A,N)
ORDENACION EXTERNA
INTERCALACIÓN DE ARCHIVOS
Analicemos el ejemplo:
F1: 06 – 09 – 18 – 20 – 35F2: 10 – 10 – 25 – 66 - 82 – 87
Supongamos que se tienen dos archivos F1 y F2 ordenados según campo clave determinase debe producir en el archivo F3 la mezcla de ambos archivos F1 y F2Si 06 < 10 si pasa 06 a F3
06 < 10 si pasa 09 a F318 < 10 no pasa 10 a F318 < 16 1618 < 20 1820 < 25 2025 < 35 2535 < 66 si 35
El proceso continua hasta que en uno u otro archivo se detecte su final en tal casose tendrá que copiar la información del archivo no vació al archivo de salida F3. elresultado final de la intercalación de los archivos F1 y F2
Intercalación (F1, F2, F3)
El algoritmo intercala los elementos de dos archivos ya ordenados F1 y F2 yalmacena el resultado en el archivo F3. R1 y R2 son las variables de tipo entero. BAND 1y BAND 2 son variables de tipo BOOLEANA
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 32/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 32
Abrir el archivo F1 en modo lecturaAbrir el archivo F2 en modo lecturaBAND 1 ← verdaderoBAND 2 ← verdaderoMientras (NO EOF (F1) o BAND 1 = falso) y (NO EOF (F2) o BAND 2 = falso)
Si (BAND1 = verdadero) entonces → (Se debe leer R1 de F1)Leer R1 de F1BAND 1 ← falso
Fin siSi (BAND2 = verdadero) entonces → (Se debe leer R2 de F2)
Leer R2 de F2
BAND 2 ← falsoFin siSi (R1 < R2) entonces
Imprimir R1 en F3BAND 1 ← verdadero
SinoImprimir R2 en F3BAND 2 ← verdadero
Fin si
Fin Mientras
→ Verifica si se leyó un elemento de F1 y no se copio en F3Si BAND 1 = Falso entonces
Imprimir R1 en F3Mientras (NO EOF (F1))
Leer R1 en F1Imprimir R1 en F3
Fin mientrasFin si→ Verifica si se leyó un elemento de F2 y no se copio en F3Si BAND 2 = Falso entonces
Imprimir R2 en F3Mientras (NO EOF (F2))
Leer R2 en F2Imprimir R2 en F3
Fin mientrasFin siCerrar archivo F1
Cerrar archivo F2Cerrar archivo F3
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 33/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 33
MÉTODOS DE BÚSQUEDA
Se concluye que la operación de búsqueda se puede llevar a cabo sobre elementosordenados o desordenados. Cabe destacar que la búsqueda es más fácil y ocupa menostiempo cuando los datos se encuentran ordenados.
Los métodos de búsqueda se pueden clasificar en internos y externos, según la ubicaciónde los datos sobre las cuales se realizaran las búsquedas. Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal de la computadora; por ejemplo, almacenados en arreglos, listas ligadas a árboles. Es búsqueda externa si loselementos están en la memoria secundaria; es decir, si hubiera archivos en dispositivocomo cintas y discos magnéticos.
BUSQUEDA INTERNA
Secuencial o lineal Binaria Por transformación de claves Árboles de búsqueda
BUSQUEDA SECUENCIAL
La búsqueda secuencial consiste en revisar elemento tras elemento hasta encontrar el dato
buscado, o llegar al final del conjunto de datos disponible.Primero se tratará sobre la búsqueda secuencial en arreglos y luego en listas enlazadas. Enel primer caso, se debe distinguir entre arreglos ordenados y desordenados.
Esta última consiste, básicamente en recorrer, el arreglo de izquierda a derecha hasta quese encuentre el elemento buscado o se termine el arreglo, lo que ocurra primero.
Normalmente cuando una función búsqueda concluye con éxito, interesa conocer en que posición fue hallado el elemento que se estaba buscando. Esta idea se puede generalizar
para todos los métodos de búsqueda.
A continuación se presenta el algoritmo de búsqueda secuencial de arreglos desordenados.
Secuencial_desordenado
Este algoritmo busca secuencialmente el elemento X en un arreglo unidimensionaldesordenado V, de N componentes.[Z es una variable de tipo entero]
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 34/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 34
Secuencial_desordenado (V, N, X)
Z 1Mientras ((Z ≤ N) y (V(Z) < >X)
Z Z+1
Fin MientrasSi (Z >N) Entonces
Imprimir “La información no esta en el arreglo”Si no
Imprimir “La información se encuentra en la posición”,Fin Si
Secuencial_desordenado_recursivo
Este algoritmo busca secuencialmente, y de forma recursiva, al elemento X en el arreglounidimensional desordenado V, de N componenteZ es un parámetro de tipo entero que inicialmente se encuentra en 1
Secuencial_desordenado_recursivo (V,N,X,I)
Si ( Z >N ) Entonces
Imprimir “La información no se encuentra en arreglo”Si noSi (V[Z]=X) Entonces
Imprimir “La información se encuentra en la posición”, ZSi no
Regresar a Secuencial desordenado_recursivo con V, N, X y Z + 1Fin Si
Fin Si
Secuencial ordenado
Este algoritmo busca secuencialmente el elemento x en un arreglo unidimensionalordenado v, de N componentes. V se encuentra ordenado crecientemente:V[1] ≤V[2] ≤ … ≤ V[N]Z es una variable de tipo entero.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 35/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 35
Secuencial ordenado (V,N,X)Z 1
Mientras ((Z ≤ N) y (X > V [Z]))Z Z +1
Fin MientrasSi ((Z>N) o (X< V[Z])) Entonces
Imprimir “La información no se encuentra en el arreglo”Si no
Imprimir “La información se encuentra en la posición”, ZFin Si
Secuencial Ordenado RecursivoEste algoritmo busca en forma secuencial y recursiva al elemento X en un arreglounidimensional ordenado v, de N componentes. V se encuentra ordenado de manera
creciente: V[1] ≤ V[2] ≤ … ≤ V[N]. Z inicialmente tiene un valor de 1
Secuencial_Ordenado_Recursivo (V,N,X,Z)Si ((Z ≤ N) y ( X > V [Z])) Entonces
Llamar a Secuencial_Ordenado_Recursivo con V, N, X, y Z + 1Si no
Si (( Z > N) o ( X < V [Z])) EntoncesImprimir “La información no se encuentra en el arreglo”
Si no
Imprimir “La información se encuentra en la posición”, ZFin Si
Fin Si
Secuencial_Lista_desordenadaEste algoritmo busca en forma secuencial al elemento X en una lista simplemente ligada,que almacena información que esta desordenada. P es un apuntador al primer nodo de lalista INFO y LIGA son los campos de cada nodo.Q es una variable de tipo apuntador
Secuencial_Lista_desordenada (P, X)
Q PMientras ((Q < > NIL) y (Q^.INFO < > X)
Q Q^.LIGAFin MientrasSi (Q = NIL) Entonces
Escribir “La información no se encuentra en la listaSi no
Escribir “La información se encuentra en la lista”Fin Si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 36/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 36
Si la lista estuviera ordenada se modificaría este algoritmo, incluyendo una condiciónsimilar a la que se escribió en algoritmo 9.3. Estos últimos con el objetivo de disminuir el número de comparaciones.
A continuación se presenta la variante recursiva de este algoritmo de búsquedasecuencial en listas simplemente ligadas desordenadas.
Secuencial_Lista_Desordenada_Recursivo
(Este algoritmo busca de manera secuencial y en forma recursiva al elemento X en unalista simplemente ligada, que almacena información que esta desordenada. P es unapuntador al primer nodo de la lista INFO y LIGA son los campos de cada nodo)
Secuencial_Lista_Desordenada_Recursivo (P, X)
Si ((P < > NIL) y (P^. INFO < > X)) EntoncesRegresar a Secuencial_Lista_desordenada_Recursivo con P^.LIGA y
Si noSi (P = NIL) Entonces
Escribir “La información no se encuentra en la lista”Si no
Escribir “La información se encuentra en la lista”
Fin SiFin Si
BUSQUEDA BINARIA
La búsqueda binaria consiste en dividir el intervalo de búsqueda en dos partes,comparando el elemento buscado con el que ocupa la posición central en el arreglo.Para el caso de que no fueran iguales se redefinen los extremos del intervalo, según elelemento central sea mayor o menor que el elemento buscado, disminuyendo de esta
forma el espacio de búsqueda. El proceso concluye cuando el elemento es encontrado,o cuando el intervalo de búsqueda se anula, es vacío.
El método de búsqueda binaria funciona exclusivamente con arreglos ordenados.
No se puede con listas simplemente ligadas, no podríamos retroceder para establecer intervalo de búsqueda, ni con arreglos desordenados. Con cada interacción del métododel espacio de búsqueda se reduce a la mitad; por lo tanto, el número de comparacionesa realizar disminuye notablemente. Esta disminución resulta significativa cuando masgrande sea el tamaño del arreglo. A continuación se presenta el algoritmo de búsqueda
binaria
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 37/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 37
Binaria
Este algoritmo busca al elemento X en un arreglo unidimensional ordenado V de Ncomponentes.IZQ, CEN y DER son variable de tipo entero. BAN es una variable de tipo booleano
BINARIA (V,N,X)
IZQ 1DER NBAN FALSOCEN INT(N/2)Mientras (IZQ ≤ DER) y (BAN = FALSO))
Si (X = V [CEN]) Entonces
BAN VERDADEROSi no - (se define el intervalo de búsqueda) -
Si (X > V [CEN]) EntoncesIZQ CEN + 1
Si noDER CEN – 1
Fin SiCEN INT ((IZQ + DER)/2)
Fin Si
Fin MientrasSi (BAN = VERDADERO) Entonces
Imprimir “La información no esta en la posición”, CENSi no
Imprimir “La información no se encuentra en el arreglo”Fin Si
Binaria sin Bandera
Este algoritmo busca al elemento X en el arreglo unidimensional ordenado V de Ncomponentes(IZQ, DER, y CEN son variables de tipo entero)
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 38/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 38
BINARIA_SIN_BANDERA (V, N, X)IZQ 1DER NCEN INT(N/2)Mientras (( IZQ ≤ DER) y (X < > V[CEN]))
Si X > V[CEN] EntoncesIZQ CEN + 1
Si noDER = CEN - 1
Fin SiCEN INT ((IZQ + DER)/2)
Fin MientrasSi (IZQ > DER) Entonces
Escribir “La información se encuentra en la posición”, CEN
Fin Si
A continuación se presenta una versión recursiva de este algoritmo de búsqueda binaria
Binaria Recursivo
Este algoritmo busca al elemento X en el arreglo unidimensional ordenado V de Ncomponentes. IZQ ingresa inicialmente al algoritmo con el valor de 1. DER, por otra
parte, ingresa con el valor de N
CEN es una variable de tipo entero
BINARIA_RECURSIVO (V, IZQ, DER, X)
Si ( IZQ ≥ DER) EntoncesEscribir X, “No se encuentra en el arreglo”
Si noCEN INT ((IZQ + DER)/2)Si (X = V[CEN]) Entonces
Escribir “El dato buscado se encuentra en la posición”, CENSi no
Si (X > V[CEN]) EntoncesRegresar a Binaria_Recursivo con V, CEN – 1, X
Fin SiFin Si
Fin Si
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 39/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 39
FUNCIÓN HASH POR MODULO: DIVISIÓNLa Función Hash por modulo (división) consiste tomar el residuo de la división de la claveentre los números de los componentes del arreglo, Suponer por ejemplo que se tiene de“N” elemento y “K” es la clave del dato a buscar.
La Función Hash que defina por la siguiente fórmula:
H (K) = (K MOD. N) + 1
En esta formula se observa el residuo de la división se le suma uno, esta ultima con elobjetivo de obtener un valor comprendido entre 1 y N. Para lograr mayor uniformidad enla distribución es importante que “N” sea un número primo o divisible entre el mismonumero. Por lo tanto si “N” no es un número primo, se debe considerar el número primo
más cercano.
Ejemplos: suponer que “N” es igual a 100 es el tamaño del arreglo y las direcciones que sedeben asignar a los elementos (al guardarlo o recuperarlo) son los números del 1 al 100,considerar además, K 1 = 7259 y K 2 = 9359 son las dos claves a que se la deben asignar
posiciones en el arreglo.
Si aplicamos la formula con N = 100 para calcular las direcciones correspondientes a K 1 yK 2 obtenemos una colisión como H (K 1) = H (K 2) y K 1 ≠ K 2, se está ante una colisión que
se debe resolver porque a los dos elementos le corresponde una misma dirección.
Observar, sin embargo, que si se aplica la fórmula con un numero primo cercano a “N”, elresultado cambiaria.
H (K 1) = (7259 mod. 97) = 82.H (K 2) = (9359 mod. 97) = 48.Con “N” = 97 se ha eliminado la colisión.
ENCADENAMIENTO
El método de encadenamiento consiste en que cada elemento del arreglo tenga unapuntador a una lista ligada, la cual seguirá generando y almacenara los valores quecolisiona.
Es el método mas eficiente debido al dinamismo propio de las listas cualquiera sea elnumera de colisiones que se presentes ser puede resolver sin inconvenientes.
Como desventaja del método de encadenamiento se menciona que el hecho de que ocupa
espacio adicional de la tabla y que exige el manejo de las listas ligadas, Además si laslistas crecen demasiado se perderá la facilidad de acceso directo del método Hash.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 40/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 40
A continuación se muestra la estructura de datos necesarios para resolver colisiones
V
80
43 1354 10425 3556
Solución de colisiones con arreglo anidados
a) Arreglos anidados. b) Tabla con H (K)
Solución de Colisiones por Encadenamiento
K H (K)25435635541380
104
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 41/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 41
Este algoritmo busca el dato con clave K en el arreglo unidimensional V de N elementos.Resuelve las colisiones por medio de encadenamiento en las listas ligadas. SIG e INFO sonlos campos de cada nodo de la lista. D es una variable de tipo entero. Q es una variable detipo puntero.
Encadenamiento (V, N, K)
D H (K) - genera Dirección-Si ((V (D) <> vacío) y (V (D) = K) entonces
Imprimir “La información esta en la posición”, DSino
Q V (D). SIG -apuntador a la lista-Mientras ((Q<> vacío) Y (Q^.INFO <>K)
Q Q^.SIG
Fin_MientrasSi (Q = vacío) entonces
Imprimir “ La información no se encuentra en la lista”Sino
Imprimir “ La información se encuentra en la lista”Fin sí
Fin sí
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 42/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 42
GRÁFICAS
Introducción
Antes hemos estudiado las estructuras de datos tipos árboles, en donde cada nodo oelemento puede tener como máximo un nodo que le precede o raíz. Si embargo, en la práctica existen problemas o situaciones en que la información que se debe almacenar nocorresponde con una estructura de este tipo. Para estos problemas se necesita de unaestructura en la cual se puedan representar otras relaciones entre los datos o componentesde la misma. En esta sección estudiaremos las gráficas.
Las gráficas son estructuras de datos no lineales donde cada componente puede tener unoo más predecesores y sucesores. En una gráfica se distinguen dos elementos: los nodos,mejor conocidos como vértices, y los arcos, llamados aristas, que conectan un vértice conotro. Los vértices almacenan información y las aristas representan relaciones entre dichainformación.
Estas estructuras tienen aplicaciones en diferentes dominios, entre ellos transporte, -terrestre, aéreo y marítimo-, redes de computadoras, mapas-, ubicación geográfica devarias ciudades-, asignación de tareas, etc. Considere por ejemplo, la gráfica de la figura7.1 donde se observan alguna de las principales capitales sudamericanas y la conexiónentre ellas. En este caso los vértices representan a las ciudades, mientras que las aristas a
las carreteras o algún otro medio de conexión entre ellas.
Algunas aristas están etiquetadas, el valor que aparece en ellas constituye la distancia queexiste entre las ciudades. En general, una etiqueta en la arista que une, por ejemplo, losvértices i y j se usa para representar el costo de ir del vértice i al vértice j.
En la figura 7.2 se presentas dos ejemplos de graficas. La primera a) tiene cuatro vértices(a, b, c, d ) y cinco aristas ((a ,b), (b, c), (c, d), (d, a), (b, d)); mientras que la segunda b)tiene seis vértices (a, b, c, d, e, f) y seis aristas ((a, b), (b, c), (c, d), (d, a), (d, e), (e, f)).
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 43/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 43
DEFINICION DE GRÁFICAS
Una gráfica G consta de dos conjuntos: V (G), A(G). El primero lo integra elementosllamados nodos o vértices; el segundo, arcos o aristas. Por lo tanto, podemos denotar unagrafica G como:
Figura 7.1
Ejemplo de gráfica.
G = (V, A)
Donde V representa el conjunto de vértices de G y A representa el conjunto de aristas de G.Si no se hace ninguna especificación, los conjuntos V y A son finitos.
Cada arista esta identificada por un único par de nodos del conjunto de vértices, que puedeo no estar ordenado. Una arista que va desde el vértice u al v se denota mediante unaexpresión a= (u, v), donde u y v son vértices adyacentes y los extremos de de a. En estecaso, u y v están conectados por a i se dice que a es incidente de u y v.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 44/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 44
Figura 7.2Elementos de una gráfica.
CONCEPTOS BÁSICOS DE GRÁFICAS
A continuación se presentas algunos de los conceptos más importantes relacionados con lateoría de graficas:
Grado de un vértice: El grado de un vértice v, escrito como grado (v), es elnúmero de aristas que contiene a v; es decir, que tienen a v como extremo. Si elgrado(v) = O (v no tiene aristas), se dice que v es un nodo aislado.
Lazo o bucle: Un lazo o bucle es una arista que conecta a un vértice consigo
mismo, es decir, a= (u, u).
Camino: Un camino P de longitud n se define como la secuencia de n vértices quese debe seguir para llegar al vértice v, --origen—al vértice v --destino—
ⁿ
P = ( v , ….., V )
¹ ⁿDe tal modo que v , es adyacente a v para i = 1, 2……, n – 1
i + ı
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 45/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 45
Camino cerrado: El camino p es cerrado si el primero y último vértices soniguales; es decir, si v1 = vn´
Camino Simple: El camino es simple si todos sus nodos son distintos, conacepción del primero y del último, que pueden ser iguales; es decir, P es simple si
v1’ v2’ …, son distintos.
Ciclo: Un ciclo es un camino simple cerrado de longitud 3 o mayor. Un ciclo delongitud K se llama K-ciclo.
Gráfica conexa: Se dice que una grafica es conexa si existe un camino simpleentre cualesquiera dos de sus nodos.
Gráfica árbol: Se dice que una gráfica G es de tipo árbol o árbol libre si G es unagráfica conexa sin ciclos.
Gráfica completa: Se dice que una gráfica es completa si cada vértice v de G esadyacente a todos los demás vértices de G. Una grafica completa de n vérticestendrá n (n-1)/2 aristas.
Gráfica etiquetada: Se dice que una gráfica G está etiquetada si sus aristas tienenasignado un valor. Es decir, si cada arista a tiene un valor numérico no negativoc(a), llamado costo, peso o longitud de a, entonces G tiene peso o está etiquetada.En este caso, cada camino P de G tendrá asociado un peso o longitud que será lasuma de los pesos de las aristas que forman el camino P.
Multigráfica: Una gráfica se denomina multigráfica si al menos dos de susvértices están conectados entre si por medio de dos aristas. En este caso, las aristasreciben el nombre de aristas múltiples o paralelas.
Subgráfica: Dada la gráfica G = ( V, A), G’= (V’, A’) se denomina subgráfica deG si V’ ≠ , V’ V y A’ A, donde cada arista de A’ es incidente con vértices dev’
Gráfica 7.3Conceptos de gráficas.
5/10/2018 ResumenEstrDatos (1) - slidepdf.com
http://slidepdf.com/reader/full/resumenestrdatos-1 46/46
Prof. Jamie Gill UNIVERSIDAD COLUMBIA Octubre/2008
Recopilación de material de Estructura de Datos 46
Luego de observar la figura 7.3 se pueden realizar las siguientes afirmaciones:
a) Todos los vértices tienen cuatro grados.
b) Un camino P para llegar del nodo A al nodo D puede ser A- B- C- D. Otros puedenser A- E- D o A- D.
c) El camino A- C- D- A es un camino cerrado, el A- C- D no lo es.
d) El camino A- C- D- A es un camino simple, el A- C- B- D- C no lo es.
e) El camino A- C- D- A es un ciclo.
f) Es una gráfica conexa, pues todos los nodos tienen al menos un camino a otronodo.
g) Es una gráfica completa, pues todos los nodos se conectan con los demás.
Luego observa la figura 7.4 se pueden realizar las siguientes afirmaciones:
a)
La gráfica de la figura 7.4ª, existe un lazo o bucle en el vértice d. Es decir, a = (d,d).
b) La gráfica de la figura 7.4b, es una multigráfica, ya que hay dos aristas que unenlos vértices c y d . Es decir, la aristas a1 = (c, d) y a2 = (c, d) son aristas múltipleso aristas paralelas.