UNIVERSIDAD DE OCCIDENTE
"TUTOR DE ESTRUCTURA DE DATOS I"
"Departamento de informática"
Página desarrollada por :
TOMASA BENITEZ LÓPEZ Matrícula 9460056
JUANA ARREDONDO PARRA Matrícula 9460142
Asesor :
L.S.C. FERNANDO CAMPOS CAMACHO
Ver el contenido de la materia
ESTRUCTURA DE DATOS I
UNIDAD I
INTRODUCCIÓN A LAS ESTRUCTURAS DE DATOS I
1.1 Definición, importancia y utilidad de las estructuras de datos
1.2 Clasificación de las estructuras de datos
1.3 Operaciones más comunes de las estructuras de datos
1.3.1 Lista de disponibilidades
UNIDAD II
ESTRUCTURAS DE DATOS LINEALES CON ASIGNACIÓN SECUENCIAL
2.1 Arreglos secuenciales
2.2 Pila
2.3 Aplicaciones de pilas
2.4 Cola
2.5 Cola circular
2.6 Doble cola circular
UNIDAD III
ESTRUCTURAS DE DATOS DATOS LINEALES CON ASIGNACIÓN ENCADENADA
3.1 Introducción
3.2 Lista lineal encadenada
3.3 Pilas encadenadas
3.4 Colas encadenadas
3.5 Lista circular encadenada
3.6 Lista circular encadenada con nodo de encabezamiento
3.7 Lista doblemente encadenada
Presentación
1.1 DEFINICIÓN, IMPORTANCIA Y UTILIDAD DE LAS ESTRUCTURAS DE DATOS
CONCEPTO
Es una colección de datos organizada de un modo particular.
Las estructuras de datos pueden ser de dos tipos:
ESTRUCTURAS DE DATOS ESTÁTICAS Y ESTRUCTURAS DE DATOS DINÁMICAS.
ESTRUCTURAS DE DATOS ESTÁTICAS
Son aquellas en las que se asigna una cantidad fija de memoria
cuando se declara la variable.
En grandes ocasiones se necesitan colecciones de datos
que crezcan y reduzcan su tamaño en memoria a medida que el
programa progrese. Esto se logra implementando las estructuras dinámicas.
ESTRUCTURA DE DATOS DINÁMICAS
Son aquellas cuya ocupación en memoria puede aumentar o
disminuir en tiempo de ejecución
IMPORTANCIA Y UTILIDAD DE LAS ESTRUCTURAS DE DATOS
La programación estructurada significa escribir un programa
de acuerdo a las siguientes reglas.
1.-El programa tiene un diseño modular
2.-Los módulos son diseñados de un modo descendente
3.-Cada módulo se codifica utilizando las tres estructuras de control
básicas:
a)Secuencia
b)Selección
c)Repetición
La programacióne estructurada se refiere a un conjunto de
técnicas que aumentan considerablemente la productividad del programa
reduciendo en elevado grado el tiempo requerido para escribir, verificar,
depurar y mantener los programas. Utiliza un número limitado de
estrcuturas de control que minimizan la complejidad de los programas y
por consiguiente reducen los errores y hacen los programas en general
más eficientes.
Regresar al contenido
1.2 CLASIFICACIÓN DE LAS ESTRUCTURAS DE DATOS
ESTRUCTURAS DE DATOS ESTÁTICAS
1.- Simples o primíticas
a) Boolean
b) Char
c) Integer
d) Real
2.- Compuestas
a) Arreglos
b) Conjuntos
c) Strings
d) Registros
e) Archivos
ESTRUCTURA DE DATOS DINAMICAS
1.- Lineales
a) Pila
b) Cola
c) Lista
2.- No lineales
a) Árboles
b) Grafos
Regresar al contenido
1.3 OPERACIONES MÁS COMUNES DE LAS ESTRUCTURAS DE DATOS
DEFINICIONES BÁSICAS
NODO: Está formado por dos campos. Un campo de información que
contiene el valor del elemento (info) y el campo NEXT que es el que
apunta a la dirección del elemento siguiente.
CAMPO DE INFORMACIÓN (INFO):Contiene el elemento actual o
valor del nodo en la lista.
CAMPO DE DIRECCIÓN (NEXT):Contiene la dirección del nodo
siguiente de la lista.
LISTA LINEAL ENCADENADA:Es cuando los elementos fueron
ordenados explícitamente en nodos, es decir, cada elemento contiene dentro
de sí mismo la dirección del elemento siguiente.
list --> [info|next]--> [info|next]--> [info|next]---// (nil)
LIST:Es un puntero externo que apunta hacia el primer nodo de la
lista
NULO:Es el campo de dirección siguiente al último nodo en la
lista, el cual es una dirección no válida. Este puntero nulo es
utilizado para señalar el final de la lista.
LISTA VACIA:Es una lista sin nodos, es decir, el valor del
puntero externo de la lista es el puntero nulo. Se puede especificar así:
List=nil
P Q
List-->[ x | ] --> [ y | ]--// (nil)
INFO(nodo (p))=x
NEXT(nodo (p))=q
INFO(next (p))=y
NEXT(nodo (q))=nil
LISTA LINEAL ENCADENADAEs una estructura dinámica,
donde el número de nodos en una lista puede variar a medida que los
elementos son insertados y removidos, por lo tanto la naturaleza
dinámica de una lista contrasta con la naturaleza estática de un arreglo
que permanece en forma constante.
Regresar al contenido
OPERACIONES MÁS COMUNES EN UNA LISTA LINEAL ENCADENADA
ALGORITMO PARA INSERCIÓN DE NODOS EN UNA LISTA LINEAL
ENCADENADA
P=GETNODE
INFO(P)=X
NEXT(P)=LIST
LIST=P
En donde:
GETNODE es un mecanísmo para traer nodos vacíos.
Ejemplo
ALGORITMO PARA REMOVER DE NODOS EN UNA LISTA LINEAL
ENCADENADA
P=LIST
LIST=NEXT(P)
X=INFO(P)
FREENODE(P)
En donde:
FREENODE es un mecanísmo para eliminar nodos.
Ejemplo
Regresar al contenido
1.3.1 LISTA DE DISPONIBILIDADES
Si observamos claramente notamos que el algoritm de
eliminación no está concluído si no se agrega el mecanismo
freenode(P), pues el nodo P eliminado de la lista encadenada
todavía aparecería ahí, aunque ya no se encuentre dentro de
la lista.
Anteriormente en el algoritmo para inserción existía
un mecanismo denominado getnode del cual obtenemos nodos
vacíos, y el mecanismo de freenode nos sirve para que guarde
nodos vacíos pero eliminados de una lista encadenada, para
cuando deseen ser utilizados.
Podrá pensarse: " si getnode ofrece nodos vacíos,
¿por qué es necesario nodos eliminados que ya fueron usados?,
la realidad es que las computadoras tienenun límite en cuanto
a memoria por lo tanto se deben utilizar los dos mecanismos
de la siguiente forma:
Se utilizará una lista encadenada la cual se denominará
lista de disponibilidades, en ésta lista se guardarán los nodos
disponibles con el mecanismo freenode y con el mecanismo getnode
se removerán de la lista de disponobilidades.
Por lo tanto, cuando ésta lista apunte a nil pasará un
error de sobreflujo (overflow), pues ya se llegó al límite de
la capacidad de nodos (memoria disponible).
La lista de disponobilidades se representará de la
siguiente manera con su campo info vacío.
Avail--> [ | ]-->[ | ]-->[ | ]-->[ | ]--// (nil)
ALGORITMO PARA INSERCIÓN DE NODOS CONSIDERANDO
LISTA DE DISPONIBILIDADES
OPERACIÓN GETNODE
Si avail =nil entonces
"error de overflow "
de lo contrario
P=avail
avail=next(avail)
ALGORITMO PARA REMOVER NODOS CONSIDERANDO LISTA DE DISPONIBILIDADES
OPERACIÓN FREENODE
Next(p)=avail
avail=p
Ejemplo
Regresar al contenido
ALGORITMO PARA INSERCIÓN DE NODOS ENTRE DOS NODOS DETERMINADOS
INSAFTER(P,X)
Q=GETNODE
INFO(Q)=X
NEXT(Q)=NEXT(P)
NEXT(P)=Q
Donde:
INSAFTER(P,X): Representa la operación de inserción de un elemento
x en la lista después de que un nodo es apuntado por p.
Ejemplo
Regresar al contenido
ALGORITMO PARA REMOVER NODOS CONSIDERANDO LISTA DE DISPONIBILIDADES
DELAFTER(P,X)
Q=NEXT(P)
X=INFO(Q)
NEXT(P)=NEXT(Q)
FREENODE Q
Donde:
DELAFTER: Significa un elemento "x" después de que un nodo es apuntado
por P
Ejemplo
Regresar al contenido
BUSQUEDA SECUENCIAL ENCADENADA
F=false
q=nil
p=list
mientras(p <> nil) y (not f)
si info(p)=llave entonces
posición=p
f=true
si no
q=p
p=next(p)
si (not f)entonces
posición=0
Ejemplo
Regresar al contenido
2.1.- ARREGLOS
ARREGLOS UNIDIMENSIONALES
Un array de una dimensión (vector o lista), es un tipo de datos
estructurado compuesto de un número de elementos finitos, tamaño fijo
y elementos homogéneos. Finitos indica que hay un último elemento,
tamaño fijo significa que el tamaño del array debe ser conocido en
tiempo de compilación, homogéneo significa que todos los elementos son
iguales, es decir, del mismo tipo.
Los elementos del array se almacenan en posiciones contiguas
de memoria, a cada una de las cuales se puede acceder directamente.
Supongamos que se desean conservar las puntuaciones de 50 estudiantes
de un examen de informática. Para almacenar éstas puntuaciones o
calificaciones se necesita reservar 50 posiciones en memoria, dar un
nombre al array, y a cada uno de los 50 estudiantes asignarles su
calificación correspondiente, es decir, dar el índice o subíndice del
array.
Arreglos bidimensionales
Arreglos tridimensionales
Regresar al contenido
VECTOR CALIFICACIONES
1 [ 7.5 ]
2 [ 4.75 ]
3 [ 5.25 ]
: [ : ]
: [ : ]
50 [ 6 ]
Formato: type
Nombre_array =array[tipo subíndice]of tipo;
Regresar al concepto
Regresar al contenido
ARRAY BIDIMENSIONAL
Un array bidimensional (tabla o matriz), es un array con dos
índices, al igual que los vectores que deben ser ordinales o tipo
sub_rango.
Para localizar o almacenar un valor en el array se deben
especificar dos posiciones (dos subíndices), uno para la fila y otro
para la columna.
Los elementos se referencían con el formato:
!***************imagen ***************
Type
Tabla=array[1...25, 1...4]of real;
Para conocer el número de filas se necesita restar el límite
inferior a el límite superior más 1.
Var matriz:array[1..3, 1..5]of integer;
fila columna
filas= 3-1+1=3
columnas= 5-1+1=5
El producto del número de filas por el número de columnas es
igual al número de elementos: 3 x 5 = 15 elementos
Arreglos unidimensionales
Arreglos tridimensionales
Regresar al contenido
FORMULA PARA DETERMINAR LA DIRECCION DE UN ELEMENTO
DADO EN UN ARREGLO BIDIMENSIONAL.
Suponiendo que se tiene un arreglo (AR) de dos dimensiones:
Rango 1 Rango 2
Var AR:array[L1...U1, L2....U2] of integer;
Dado éste arreglo se desea conocer la dirección en memoria de un
elemento[i] dado, la fórmula será la siguiente:
Base AR +[(i1-L1)*r2+(i2-l2)]*E_size
Donde:
i1= índice de fila del elemento dado
L2= límite inferior del rango de filas
r2= U2-L2+1
U2= límite superior del rango de columnas
L2= límite inferior del rango de columnas
i2= índice de columna de elemento dado
var AR:array[-3..3, 2..5]of integer;
ar(0,4) esize=1
base AR+[(i1-L1)*r2+(i2-L2)]*E_size
base AR+[(0-(-3))*(5-2+1)(4-2)]*1
base AR+[3*(4)+(2)]*1
base AR+14
b(-3,2) b(-3,3) b(-3,4) b(-3,5)
b(-2,2) b(-2,3) b(-2,4) b(-2,5)
b(-1,2) b(-1,3) b(-1,4) b(-1,5)
b(0,2) b(0,3) b(0,4) b(0,5)
b(1,2) b(1,3) b(1,4) b(1,5)
b(2,2) b(2,3) b(2,4) b(2,5)
Regresar al concepto
Regresar al contenido
ARREGLOS TRIDIMENSIONALES
Son arreglos de más de dos dimensiones.
Por ejemplo:
Var c:array[3..5, 1..2, 1..4]of integer;
!*********** imagen ***************
Arreglos unidimensionales
Arreglos bidimensionales
Regresar al contenido
Para conocer el número de elementos en un arreglo tridimensional
será igual al producto de cada una de las dimensiones.
Ejemplo:
planos filas columnas
Var c:array[3..5, 1..2, 1..4]of integer;
LS-LI+1
Planos = 5-3+1= 3
Filas = 2-1+1= 2
Columnas = 4-1+1= 4
24 elementos
En el lenguaje pascal se pueden tener arreglos de más de 2
dimensiones, ejemplo:
Var
Tri:array[3..5, 1..2, 1..4] of integer;
En este arreglo tridimensional hace referencia en su primer
rango al número de planos, en el segundo al número de filas y en el
tercer rango al número de columnas.
Para conocer el número o rango de cada dimensión la fórmula es
la misma.
Regresar al concepto
Regresar al contenido
2.2.- PILA.-
Es una colección ordenada de elementos en la cual en un
extremo se pueden insertar nuevos elementos y de la cual se pueden
retirar otros, llamada parte superior de la pila.
PILA DE SEIS ELEMENTOS
[ F ]
[ E ]
[ D ]
[ C ]
[ B ]
[ A ]
Operaciones básicas con pilas
Pila vacía
Aplicaciones de pilas
Regresar al contenido
El elemento más alto es f, d es más alto que c,b y a, pero
menor que e y f. Una pila se utiliza para cálculos o para ejecución de
instrucciones, puede implantarse por hardware de diseño especial
o en memoria controladas por programas.
Según la definición de una pila un solo extremo de la pila
puede designarse como parte superior, los nuevos elementos que se
insertan deben colocarse en la parte superior de la pila, en éste
caso la pila se mueve hacia arriba o bien los elementos pueden
ser removidos o eliminados en cuyo caso la pila se mueve hacia
abajo; para designar la parte de arribo o de abajo se debe indicar
cual es la parte superior; PUSH(agregar), POP(eliminar).
OPERACIONES BASICAS DE LAS PILAS
PUSH(s,x) = insertar un elemento x en la pila (stack).
POP(s)= remover un elemento de la pila.
EXPANSIÓN O COGIMIENTO DE PILAS
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ I ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ H ] [ H ] [ H ] [ ] [ J ] [ ] [ K ] [ ]
[ ] [ G ] [ G ] [ G ] [ G ] [G ] [ G ] [ G] [ G ] [ G ]
[ F ] [ F ] [ F ] [ F ] [ F ] [ F ] [ F ] [ F ] [ F ] [ F ]
[ E ] [ E ] [ E ] [ E ] [ E ] [ E ] [ E ] [ E ] [ E ] [ E ]
[ D ] [ D ] [ D ] [ D ] [ D ] [ D ] [ D ] [ D ] [ D ] [ D ]
[ C ] [ C ] [ C ] [ C ] [ C ] [ C ] [ C ] [ C ] [ C ] [ C ]
[ B ] [ B ] [ B ] [ B ] [ B ] [ B ] [ B ] [ B ] [ B ] [ B ]
[ A ] [ A ] [ A ] [ A ] [ A ] [ A ] [ A ] [ A ] [ A ] [ A ]
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j)
B=PUSH(S,G)
C=PUSH(S,H)
D=PUSH(S,I)
E=POP(S)
F=POP(S)
G=PUSH(S,J)
H=POP(S)
I=PUSH(S,K)
J=POP(S)
K
Ir a concepto de pila
Pila vacía
Aplicaciones de pilas
Regresar al contenido
PILA VACÍA
Una pila se denomina vacía cuando ésta contiene un solo
elemento, y el elemento es retirado de la pila, por lo tanto
antes de retirar un elemento es necesario asegurarse que la pila
no esté vacía, esto será con la operación " empty(s) ", si ésta
regresa el valor de verdadero la pila está vacía de lo contrario
retorna un valor de falso.
Otra operación será determinar el elemento superior de la
pila sin retirarlo, esto será con la operación "stacktop(s)".
Es necesario utilizar siempre empty ya que debemos
asegurarnos que la pila está vacía de lo contrario si pedimos que nos
diga cual es el elemento superior (stacktop) nos marcaría un error de
underflow.
Operaciones básicas con pilas
Concepto de pila
Aplicaciones de pilas
Regresar al contenido
2.3.- APLICACIONES DE PILAS
Supongamos que se da una expresión matemática que incluye
varios conjuntos de paréntesis, se desea saber si los préntesis
están embebidos correctamente es decir:
1. Si existe igual número de paréntesis a la izquierda que a la derecha.
2. Cada paréntesis de la derecha esté precedido por el correspondiente
paréntesis de la izquierda.
Entonces podrá decirse que cada paréntesis a la derecha cierra una
posibilidad. Entonces en algún punto particular de la expresión la
cantidad de paréntesis abiertos y que no han sido cerrados en éste
punto se le conocerá como PROFUNDIDAD DE EMBEBIMIENTO.
Regresar al contenido
CONTADOR DE PARÉNTESIS.-
En un punto particular de la expresión, el número de paréntesis
a la izquierda menos el número de paréntesis a la derecha.
Ejemplo:
7 - ( ( X * ( ( X + Y ) / ( J - 3 ) ) + Y ) / ( 4 - 2 . 5 ) )
0 1 2 3 4 3 4 3 2 1 2 1 0
NOTA:para que no exista profundidad de embebimiento el
resultado del contenido del contador debe ser igual a cero.
Se asume que existen tres tipos de separadores diferentes
{},(),[]. Cualquier tipo se separador que se encuentra al final debe
ser igual al del principio. Por consiguiente es necesario tener en
cuenta no solamente cuántos separadores han sido abiertos sino
también de que tipo son.
Una pila se puede utilizar para registrar diferentes tipos
de signos de agrupación; en cualquier momento que se encuentre un
signo abriendo la expresión éste es empujado hacia la pila y cada
vez que se encuentre el correspondiente signo terminal se examina
la pila, si la pila está vacía quiere decir que el signo de agrupación
terminal no tiene correspondiente de apertura. Si la pila no está vacía
retiramos un elemento y revisamos si corresponde al signo de agrupación
terminal, si coincide continuamos si no es así, la hilera no es válida,
cuando llegamos al final de la hilera nos aseguramos de que la pila
esté vacía, de lo contrario quiere decir que se han abierto uno o más
signos pero no se han cerrado, haciendo que la hilera no sea válida.
Operaciones básicas con pilas
Pila vacía
Ir a concepto de pila
Regresar al contenido
ALGORITMO DE APLICACIONES DE PILAS
1. Hacer valid=1
2. Hacer stack=0
3. Si ya se ha leído toda la hilera o valid=0
ir a paso #5
de lo contrario
3a) lee symb "{" siguiente de la hilera
3b) si symb= "(" o symb= "[" o symb= "{" entonces
push (s, symb) ir a paso #3
3c) si symb= ")" o symb= "]" o symb= "}" entonces
si empty(s) entonces
valid=0
de lo contrario
X= pop(s)
Si X <> simbolo de apertura equivalente a symb entonces vali=0
4. Ir a paso # 3
5. Si no empty(s) entonces
Valid=0
6. si valid=1 entonces
escribe "hilera válida"
de lo contrario
escribe hilera no válida
7. Fin.
Ejemplo
Regresar al contenido
ALGORITMO DE PILAS
Hasta ahora para el movimiento de la pilas solamente se han
visto las operaciones PUSH y POP pero se ha tomado en cuenta la
forma de representar una pila correctamente, como son contadores para
el valor de stacktop o bien se han visto pilas de tamaño indefinido.
La pila se ha visto como arreglo pero desafortunadamente son
diferentes, pues el número de elementos en un arreglo es fijo y en una
pila es dinámico cuyo tamaño va cambiando a medida que los elementos
son insertados y removidos, sin embargo aunque un arreglo no puede ser
una pila éste si puede ser un recipiente de ella, en donde tendrá las
siguientes características:
1. Un extremo del arreglo será el fondo fijo de la pila
2. Una parte superior estará cambiando constantement
3. Un campo adicional, el cual durante la ejecución en cualquier
momento llevará registro de la parte superior de la pila
Se tomará en cuenta que la pila tendrá un límite en cuanto a
tamaño; si por ejemplo la pila puede tener de 0 a 100 y el valor de
stacktop igual a 100 la pila estará llena, en cambio si stacktop=0 la
pila estará vacía.
ALGORTIMO PARA RETIRO O SUPRESION DE ELEMENTOS
Si empty(s)=verdadero entonces
Error de underflow
De lo contrario
Pop(s)
Dato=pila(stacktop)
Stacktop=stacktop-1
Ejemplo
Regresar al contenido
ALGORTIMO PARA INSERCION O EMPUJE DE ELEMENTOS
Si stacktop= límite entonces
Error de overflow
De lo contrario
Stacktop=staxktop+1
Push(s)
Pila (stacktop)=dato
Ejemplo
Regresar al contenido
UTILIZACIÓN DE PILAS
Considérese la suma A y B, pensando que la aplicación del
operador "+" a los operandos A y B, se escribirá A+B, esta
representación se denomina entrefijo.
Existen otras dos formas de representar la suma de A + B
utilizando el signo "+", estas son el prefijo y el poistfijo. Los
prefijos PRE y POST se refieren a la posición relativa del operador
con respecto a los operandos.
En la notación de PREFIJO el operador precede a los dos
operandos y en la notación POSTFIJO el operador va después de los
dos operandos.
Consideremos en la expresión a+b*c escrita en entrefijo,
observe que existen dos operadores, se quiere saber cual de estos
se realizará primero, es lógico que por jerarquía se realizaría primero
la multiplicación y posteriormente la suma.
La única regla durante el proceso de conversión es que las
operaciones que tienen relación o jerarquía más alta se convertirá
primero y después de que esta parte de la expresión ha sido convertida
se maneja como operando simple.
El orden de precedencia o jerarquía de los operadores son:
primero el exponente, posteriormente multiplicación y división y por
último la suma y la resta, Cuando dos operadores tienen la misma
precedencia, se sigue el orden de izquierda a derecha, a excepción de
la exponenciación donde se asume un orden de derecha a izquierda.
Ejemplo
Reglas para utilizar pilas
Regresar al contenido
REGLAS
1.- Dar jerarquías o precedencias sin afectar a la expresión
2.- De acuerdo a las jeraquías iniciar las conversiones
3.- Las conversiones se harán de la siguiente manera:
a) El oreden de los operandos no cambia, solo el de los operadores
b) Los paréntesis que aparezacan el la expresión original, no
aparecerán en las conversiones
c) El operador irá precedido de los operandos y operadores que
afecten, esto en el caso del prefijo. En forma contraria
funcionará el postfijo.
En expresiones de postfijo no existen los paréntesis, pero el
orden en que se presentan los operadores determinan el orden actual de
las operaciones al evaluar la expresión, haciendo en este caso que los
paréntesis no sean necesarios.
Al hacer las expresiones de entrefijo a postfijo a simple vista
perdemos la habilidad de observar a los operandos asociados con un
operador, por lo tanto la notación postfija de la expresión original
puede parecer simple si no fuera por el hecho que parece difícil de
evaluar; la solución es la aplicación de un algoritmo para evaluar
expresiones en postfijo.
Regresar a utilización de pilas
Regresar al contenido
ALGORITMO PARA EVALUAR EXPRESIONES EN POSTFIJO
1.- Si no hay más caracteres en la hilera entonces
ir al paso # 5
de lo contrario
2.- Lee Symb
3.- Si Symb = operandos entonces
push(opndstk,symb)
de lo contrario
opnd2=pop(opndstk)
opnd1=pop(opndstk)
valor=resultado de aplicar
symb a opnd1 sobre opnd2
push(opndstk,valor)
4.- ir al paso # 1
5.- Resultado = pop(opndstk)
Donde:
OPNDSTK=PILA DE OPERANDOS
OPND2= PRIMER OPERANDO RETIRADO
OPND1=SEGUNDO OPERANDO RETIRADO
SYMB=SIGUIENTE SIMBOLO A LEER
Ejemplos
Regresar al contenido
2.4COLA
Es una colección ordenada de elementos, a partir de la cual se
pueden eliminar elementos de un extremo llamado FRENTE DE LA COLA y en
la cual se pueden agregar nuevos elementos en el otro extremo llamado
PARTE POSTERIOR O ATRÁS.
FUNCIÓN
Las colas se utilizan en la computadora como un espacio de
almacenamiento reservado temporalmente para contener información ya sea
en la memoria o en sistemas operativos.
ENTONCES, la cola se define como una linea de espera, utiliza
la técnica FIFO (primeras en entrar, primeras en salir).
Cálculo de elementos
Representación de cola
Regresar al contenido
EXISTEN TRES OPERACIONES BÁSICAS QUE PUEDEN SER
APLICADAS A LAS COLAS:
1.- INSERT(q,x)
La cual adiciona un elemento "x" en la parte posterior
de la cola.
2.- X<--remove(q)
La cual retira un elemento del frente de la cola y
coloca en "x" su contenido.
3.- EMPTY (q)
La cual retorna el valor de falso o verdadero
dependiendo si la cola contiene algún elemento o está vacía.
Se utilizará un arreglo para que este contenga los elementos
dela cola, por la tanto al estar insertando elementos existe la
posibilidad de que se presente un sobreflujo si la cola ya está llena.
(A) (B) (C)
[ ] [ ] [ D ] <-- atrás [ C ] <-- atrás o posterior [ C ] <-- atrás [ C ] [ B ] [ B ] <-- frente [ B ] <-- frente [ A ] <-- frente [ ] [ ] A) insert (q,a) b) x="remove(q)" c) insertar (q,x) insert (q,b) x="a" insert (q,c) NOTA:
Llamaremos q front=frente y qrear=atrás
Regresar al concepto
Regresar al contenido
FORMULA PARA DETERMINAR EL NÚMERO DE ELEMENTOS
#ELEMENTOS = (qrear-qfront)+1
4[ ] 4 [ ] 4[ ] 4[ D ]<--qrear 3[ ] 3 [ C ]<--qrear 3[ C ]<--qrear 3[ C ] 2[ ] 2 [ B ] 2[ B ]<--qfront 2[ B ]<--qfront 1[ ] 1 [ A ]<--qfront 1[ ] 1[ ] qrear="0" #ele="3-1+1=3" #ele="3-2+1=2" #ele="4-2+1=3" qfront="1" #ele="0-1+1=0" Inicialmente qrear se ajusta a 0 y qfront a 1 y se considerará que la cola está vacía cada vez que qrear sea menor qfront Si esta cola está diseñada para cuatro elementos y deseamos agregar otro, no sería posible por la característica de la cola, puede existir un momento en que la cola esté vacía y no le puedan insertar elementos. La solución es la de modificar la opción remove de tal manera que cuando se retire un elemento se desplaza toda la cola al principio del arreglo. En este caso el frente ya no se especifica como parte de la cola, porque el frente es siempre el primer elemento del arreglo. Para saber si la cola está vacía, esto sucederá cuando la parte de atrás (qrear), sea igual a 0. Desafortunadamente este método es muy ineficiente para ser satisfactorio. Imaginemos que una cola contiene mil elementos y para remover un elemento sería necesario tener que bajar 999, por lo tanto aparte de que sería muy lento, se pierde el hecho de manipular un solo elemento para ser removido. Otra solución es que la cola tome forma de círculo para su movimiento. 5 [ X ]
4 [ B ] ---> qfornt = 4
3 [ ]
2 [ Z ] <--- qrear="2" 1 [ D ]
Regresar al concepto
Regresar al contenido
2.5 COLA CIRCULAR
Nos podemos imaginar que el primer elemento del arreglo está
inmediatamente después del último.
Esto implica que aún si el último elemento del arreglo que
forma la cola está ocupado, puede insertarse un nuevo valor detrás de
este; como primer elemento del arreglo siempre y cuando ese primer
elemento esté vacío.
EJEMPLO
5[ E ]<-qr 5[ E ]<-qf 5[ E ]<-qf 5[ E ]<-qf 5[ ] 4[ D ] 4[ D ] 4[ ] 4[ ] 4[ ] 3[ C ]<-qf 3[ C ] 3[ ] 3[ ] 3[ ] 2[ ] 2[ ] 2[ ] 2[ G ]<-qr 2[ G ]<-qr 1[ ] 1[ F ] <-qr 1[ F ]<-qr 1[ F ] 1[ F ]<-qf a)inicial b)ins(q,F) c)elim(D,C) d)ins(q,G) e)elim(E) Desafortunadamente con este método es dificil determinar si la cola está vacía, para resolver este problema se debe establecer la conversión en la cual el valor de qfront es el índice del elemento del arreglo que precede al primer elemento de la cola, en lugar de ser el índice del primer elemento en sí. Regresar al contenido
ALGORITMO PARA REMOVER ELEMENTOS DE UNA COLA CON
MOVIMIENTO CIRCULAR
1.- Si no desea remover elementos de la cola entonces
ir al paso #7
de lo contrario
2.- Si empty(q)=true entonces {cuando qrear=qfront}
error de "underflow"
ir al paso # 7
3.- De lo contrario
si qfront=máximo valor de la cola entonces
qfront=1
4.- De lo contrario
qfront=qfront+1
5.- x=dato, remove (qfront)
6.- ir a paso #1
7.- FIN
Ejemplo
Regresar al contenido
ALGORITMO PARA INSERCIÓN DE ELEMENTOS EN UNA COLA CON MOVIMIENTO
CIRCULAR
1.- Si no sesea insertar elementos en la cola entonces
ir al paso # 5
de lo contrario
2.- Si qrear=valor maximo de la cola entonces
qrear=1
de lo contrario
qrear=qrear+1
3.- Si qrear=qfront entonces
"error de overflow"
ir al # 5
de lo contario
insert (qrear,dato)
4.- iar al # 1
5.- FIN
NOTA: Al iniciar cuando la cola está vacía qrear y qfront van a ser
igual al máximo valor del valor del arreglo.
Ejemplo
Regresar al contenido
2.6 DOBLE COLA CIRCULAR
REPRESENTACIÓN
<------<----------<-----------<------------<----------------<--------------->-> [ | A | ]<-->[ | B | ]<-->[ | 1 | ] <-->[ | C | ]<<-->------------------->------------------->----------->--------------->
3.3 PILA ENCADENADA
Se observan las listas encadenadas que de la parte del puntero
externo (list) se accede a la lista, es decir, de ahí mismo se accesa
y remueve nodos, tienen las mismas características, puesto que se
insertan y se remueven elementos de un solo lugar.
Una pila puede ser accesada a través de su elemento superior y
una lista puede ser accesada a través del puntero al primer elemento.
De esta forma se ha descubierto la forma de implementar una pila. Esta
puede estar representada por una lista lineal encadenada donde el
primer nodo de la lista es el elemento superior de la pila.
ALGORITMO PARA EMPUJAR NODOS EN UNA PILA ENCADENADA (PUSH)
P=GETNODE
INF(P)=X
NEXT(P)=S
S=P
Ejemplo
Regresar al contenido
ALGORITMO PARA REMOVER O ELIMINAR NODOS EN UNA PILA
ENCADENADA (PUSH)
Si empty (s)=true entonces
"error de underflow"
de lo contrario
p=s
s=next(p)
x=info(p)
freenode(p)
Ejemplo
Regresar al contenido
3.4COLAS ENCADENADAS
Como se ha visto anteriormente la cola funciona con dos
extremos, una parte de enfrente para eliminación de los elementos
y una parte de atrás para insersión de los elementos.
Una cola encadenada se representará así:
front-->[ x | ]-->[ y | ]-->[ z | ]--// rear
ALGORITMO PARA REMOVER ELEMENTOS EN UNA COLA
ENCADENADA
Si empty (q)=verdadero entonces
"error de undeflow"
de lo contrario
p=front
x=info(p)
front=next(p)
si front=nil entonces
rear=nil
freenode(p)
Ejemplo
Regresar al contenido
ALGORITMO PARA INSERCIÓN DE ELEMENTOS EN UNA COLA
ENCADENADA
P=getnode
info(p)=x
next(p)=nil
si rear=nil entonces
front=p
de lo contario
next(rear)=p
rear=p
Ejemplo
Regresar al contenido
3.5 LISTA CIRCULAR ENCADENADA
Aunque las listas lineales son muy útiles tiene sin
embargoalgunas desventajas, la principal es que dado un
nodo (P), no se puede alcanzar otro nodo que sea poseído
por P.
Supongamos que hacemos un pequeño cambio a la
estructura de la lista lineal de tal manera que el campo next
en el último nodo contiene un puntero que va al primer nodo
en lugar de apuntar a nil.
Representación de lista
Primer nodo Último nodo
- >-> [ A | ]-->[ B | ]-->[ 1 | ]-->[ C | ]------>
------<------------<------------<--------<-----------------
Esta lista tiene la característica que desde cualquier
punto se puede ir hacia otro.
Regresar al concepto
Regresar al contenido
NODOS DE ENCABEZAMIENTO
En algunas ocasiones es deseable mantener un nodo
extra al frente de la lista, este nodo no representa un elemento
en la lista y es llamada nodo de encabezamiento. Tendría sus
dos campos, la porción INFO no es muy utilizado o solo para
hacer referencia a algo especial.
Un nodo de encabezamiento sin información se
representaría:
List--->[ | ]-->[ 8 | ]-->[ 7 | ]--[ 2 | ]--//(nil)
Si deseara que el campo INFO guardará alguna referencia.
List-->[ 3 | ]-->[ 8 | ]-->[ 7 | ]-->[ 2 | ]--//
Hace referencia que la lista está formada por 3 elementos.
Cuando una lista contiene un nodo de encabezamiento y está vacía
se representa asi:
List-->[/////| ]--//
También un campo info de un nodo de encabezamiento
puede contener un puntero este puede apuntar a cualquier otro nodo.
List-->[ | ]-->[ % | ]-->[ * | ]-->[ # | ]--//
Así se puede utilizar una lista como cola pues se maneja
un puntero externo que apunta al primer nodo y en el campo info
del nodo de enabezamiento tienen la dirección del último nodo
evitando así los punteros rear y front.
Regresar al concepto
Regresar al contenido
3.6 LISTA CIRCULAR CON NODO DE ENCABEZAMIENTO
Supongamos que deseamos recorrer una lista circular,
ésto se puede hacer mediante la acción repetitiva de p=next(p),
donde p es inicialmente un puntero al comienzo de la lista,
sin embargo como es lista circular no sabemos cuando se
había recorrido a menos de que exista el puntero list y se
efectúe la condición p=list, otro método de solución es el de
agregar un nodo de encabezamiento, así la porción de info
contendrá información de referencia, es decir no será similar
a la información de nodos que preceden al nodo de
encabezamiento, de ésta forma el puntero p se irá recorriendo
hasta llegar al nodo de encabezamiento.
- >-> [ /////// | ]-->[ | B | ]-->[ | 1 | ]-->[ | C | ]---------->
------<-------------------<-------------------<-----------<----------------
Regresar al concepto
Regresar al contenido
3.7 LISTA DOBLEMENTE ENCADENADA.
A pesar de que las listas lineales y circulares son
bastante eficientes tiene dos desventajas:
1. No se puede atravesar la lista circular o lineal
en dirección contraria.
2. Es necesario buscar el nodo "p" dado para
realizar alguna operación.
Para eliminar estas desventajas existen las listas
doblemente encadenadas, las cuales tienen las
siguientes características:
a) Como cualquier lista encadenada no vacía está formada
por nodos, pero la configuración de estos es diferente.
Contiene tres campos, uno para la información y los dos
restantes funcionan como apuntadores o bien, contienen
la dirección de los dos nodos de ambos lados,
esos dos campos se denominan LEFT y RIGHT.
<---[ LEFT | INFO| RIGHT ]-->
b) Las listas doblemente encadenadas se pueden presentar
en tres formas:
Representación 1
Representación 2
Representación 3
Regresar
Regresar al contenido
1.- LISTA LINEAL DOBLEMENTE ENCADENADA
//--[ | | ]<-->[ | | ]<-->[ | | ]--//
Regresa
2.- LISTA CIRCULAR DOBLEMENTE ENCADENADA
<------<----------<-----------<------------<----------------<----->-> [ | | ]<-->[ | | ]<-->[ | | ] <-->[ | | ]<<-->------------------->------------------->----------->------->
Regresa
3.- lLISTA CIRCULAR DOBLEMENTE ENCADENADA
CON NODO DE ENCABEZAMIENTO
<------<----------<-----------<------------<----------------<--------------->-> [ |//////| ]<-->[ | B | ]<-->[ | 1 | ] <-->[ | C | ]<<-->------------------->------------------->----------->--------------->
Regresa al concepto
PROPIEDAD
Left(Right(P))=P=Right(letf(P))
ALGORITMO PARA ELIMINAR NODOS EN UNA LISTA
DOBLEMENTE ENCADENADA (CIRCULAR)
Si P=0 entonces
error de underflow
de lo contrario
x=Info(P)
q=Left(P)
r=right(P)
right(Q)=r
left(r)=q
freenode(P)
Ejemplo
Regresar al contenido
ALGORITMO PARA INSERTAR NODOS EN UNA
LISTA CIRCULAR DOBLEMENTE ENCADENADA
q=getnode
info(q)=x
r=right(p)
left(r)=q
right(q)=r
left(q)=P
right(P)=q
Ejemplo
Regresar al contenido
***************************************** Ejemplos unidad I **************************************
EJEMPLO PARA INSERTAR NODOS
P=GETNODE
INFO(P)=X
NEXT(P)=LIST
LIST=P
LIST -->[ 4 | ]--> [ 8 | ]-->[ 5 | ]--// (nil)
P
Insertando un nuevo nodo P con contenido LIST-->[ 9 | ]
quedaría:
LIST-->[ 9 | ]-->[ 4 | ]-->[ 8 | ]-->[ 5 | ]--// (nil)
Regresar al algoritmo
Regresar al contenido
EJEMPLO PARA ELIMINAR NODOS
P=LIST
LIST=NEXT(P)
X=INFO(P)
FREENODE(P)
LIST -->[ 9 | ]-->[ 4 | ]--> [ 8 | ]-->[ 5 | ]--// (nil)
P
Removiendo el nodo P con contenido LIST-->[ 9 | ]
quedaría:
LIST-->[ 4 | ]-->[ 8 | ]-->[ 5 | ]--// (nil)
Regresar al algoritmo
Regresar al contenido
ALGORITMO DE INSERCIÓN Y ELIMINACIÓN DE NODOS
En la siguiente lista encadenada se agregará un nodo
con información x, ésto, utilizando la lista de disponibilidades.
Al iniciar las listas tendrían la siguiente estructura.
Avail-->[ | ]-->[ | ]-->[ | ]--//(nil)
List-->[ A | ]-->[ B | ]--//(nil)
Insertando un nodo x quedarían como sigue:
Avail-->[ | ]-->[ | ]--//(nil)
List-->[ x | ]-->[ A | ]-->[ B | ]-->//(nil)
De la lista encadenada anterior se eliminará el
nodo con información x, ésto, utilizando la lista de
disponibilidades.
Al iniciar las listas tendrían la siguiente estructura.
Avail-->[ | ]-->[ | ]-->//(nil)
List-->[ x | ]-->[ A | ]-->[ B | ]--//(nil)
Eliminando el nodo x quedarían como sigue:
Avail-->[ | ]-->[ | ]-->[ | ]--//(nil)
List-->[ A | ]-->[ B | ]-->//(nil)
Regresar al algoritmo
Regresar al contenido
INSERCIÓN DE NODOS ENTRE DOS NODOS
DETERMINADOS
Teniendo la siguiente lista, insertar un nodos
después del nodo con
información "9" con valor de "m" y otro después del
nodo con información "8" con valor de "n"
List-->[ 3 | ]-->[ 9 | ]-->[ 8 | ]-->[ 7 | ]--// (nil)
Después de la inserción del primer nodo:
List-->[ 3 | ]-->[ 9 | ]-->[ m | ]-->[ 8 | ]-->[ 7 | ]--//(nil)
Insertando el nodo "n"
List-->[ 3 | ]-->[ 9 | ]-->[ m | ]-->[ 8 | ]--[ n | ]-->[ 7 | ]--//(nil)
No es posible tratar de insertar un nodo entes
del nodo (P), pues en base a la búsqueda del nodo (P),
que inicia desde el puntero externo, serealiza la operación de
inserción, la solución puede darse a este problema es que
después de insertar el nuevo nodo, se intercambian entre el
nuevo nodo y el nodo (P).
Regresar al algoritmo
Regresar al contenido
REMOVER NODOS CONSIDERANDO LISTA DE
DISPONIBILIDADES
Teniendo la lista:
List-->[ 3 | ]-->[ 9 | ]-->[ 8 | ]-->[ 7 | ]--// (nil)
Eliminando el nodo con información "8" queda
List-->[ 3 | ]-->[ 9 | ]-->[ 7 | ]--//(nil)
Regresar al algoritmo
Regresar al contenido
BUSQUEDA SECUENCIAL ENCADENADA
List-->[ 5 | ]-->[ 7 | ]-->[ 3 | ]-->[ 9 | ]-->[ 8 | ]--// (nil)
llave=p
f=f
posición=4
F=T
Regresar al algoritmo
Regresar al contenido
*********************************** Ejemplos de unidad II ***************************************
Ejemplo: del algoritmo de aplicaciones de pilas
Con el algoritmo anterior resolver la siguiente
expresión:
{ ( X+2 ) * y ]
valid stack symb X Representación en pila
1 0 { ( [ ]
0 ( { [ ]
"hilera no válida" ) [ ( ]
] [ { ]
Regresar al algoritmo
Regresar al contenido
Ejemplo:
RETIRO O SUPRESION DE ELEMENTOS
RETIRAR Z,Y,X INSERTAR Z,Y,X
Dato stacktop stacktop dato stacktop dato
Z 5 5 [ Z ] X 5 [ ]
Y 4 4 [ Y ] X 4 [ n ]
X 3 3 [ X ] X 3 [ m ]
2 2 [ C ] 2 [ C ]
1 [ D ] 1 [ D ]
Regresar a concepto de algoritmo
de pilas
Regresar al algoritmo
Regresar al contenido
Ejemplo:
INSERCION O EMPUJE DE ELEMENTOS
Dato stacktop stacktop dato
M 3
N 4 4 N
3 M
2 C
Regresar al algoritmo
Regresar al contenido
*************************************** Ejemplo 4 unidad II **********************************
UTILIZACION DE PILAS
Ejemplos:
1) a+b
prefijo = +ab
postfijo = ab+
2) [a+(b*c)]-D
prefijo = -+a*bcD
postfijo = abc*+D-
3) [f^(g^h)]+[(x*W)/m]+N
prefijo = ++^f^gh/*xwmN
postfijo = fgh^^xw*m/+N+
Regresar al concepto
Regresar al contenido
EJEMPLO DE EVALUACION DE EXPRESIONES
{[(N*A)/X]/B}
POSTFIJO=NA*X/B/
SYMB OPND2 OPND1 VALOR
N A N N*A
A X N*A N*A/X
* B N*A/X N*A/X/B
X
/
B
/
RESULTADO N * A / X / B
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
[ A ] [ X ] [ B ] [ ]
[ N ] [N*A] [N*A/X] [N*A/X/B]
Regresar al algoritmo
Regresar al contenido
*********************************** Ejemplo 6 unidad II ****************************************
REMOVER ELEMENTOS DE UNA COLA CON MOVIMIENTO
CIRCULAR
6[ C ] 6[ C ] 6[ C ]<-qf 6[ ]<-qf 6[ ] 5[ B ] 5[ B ]<-qf 5[ ] 5[ E ] 5[ ] 4[ A ]<-qf 4[ ] 4[ ] 4[ ] 4[ ] 3[ ] 3[ ] 3[ ] 3[ ] 3[ ] 2[ E ]<-qr 2[ E ]<-qr 2[ E ]<-qr 2[ E ]<-qr 2[ E ]<-qr 1[ D ] 1[ D ] 1[ D ] 1[ E ] 1[ ]<-qf qfront x máximo valor de la cola
3 A 6
4 B
5 C
6 D
1 E
2
Regresar al algoritmo
Regresar al contenido
**************************************** Ejemplo 7 unidad II *************************************
INSERCIÓN DE ELEMENTOS EN UNA COLA CON
MOVIMIENTO CIRCULAR
EJEMPLO: De la siguiente cola, eliminar tres nodos e
insertar E y F
E L I M I N A C I Ó N I N S E R C I Ó N
5[ ]<-qf 5[ ]<-qf 5[ ] 5[ ] 5[ ] 5[ E ] 4[ D ] 4[ D ]<-qr 4[ D ]<-qr 4[ D ]<-qr 4[ D ] <-qr 4[ D ] <--qf 3[ C ] 3[ C ] 3[ C ] 3[ C ] 3[ C ] <--qf 3[ ] 2[ B ] 2[ B ] 2[ B ] 2[ B ]<-qf 2[ ] 2[ ] 1[ A ]<-qr 1[ A ] 1[ A ]<-qf 1[ ] 1[ ] 1[ F ]<--qr "ERROR DE OVERFLOW"
qfront x
5
1 A
2 B
3 C
Regresa al algoritmo
Regresar al contenido
*************************************** Ejemplos de la unidad III ***********************
EMPUJAR NODOS EN UNA PILA ENCADENADA (PUSH)
S------>[ C | ]---//
| ^
v |
P--> [ W | ]
Queda:
S------>[ C | ]--->[ W| ]----//
| ^
v |
P--> [ Z | ]
Queda:
S------>[ C | ]--->[ Z| ]--->[W| ]-//
Regresa al algoritmo
Regresar al contenido
REMOVER O ELIMINAR NODOS EN UNA PILA
ENCADENADA (PUSH)
EJEMPLO:
"x" "x"
P S P S
| "x" | | |
S-//--->[ A | ]--//->[ B| ]-//-->[ C | ]---//
x=A
x=B
Regresa al algoritmo
Regresar al contenido
INSERCIÓN DE ELEMENTOS EN UNA COLA
ENCADENADA
EJEMPLO
Las partes señaladas con "x" se ha eliminado al aplicar algoritmo y
"//" donde se corta la secuencia de la cola
"x" "x"
"x" "x" P front front
front-//-->[ X | ]-//-->[ Y | ]--//->[ Z | ]
/
x=X front--------> =<-----rear x="Y" x="Z"
Regresa al algortimo
Regresar al contenido
ALGORITMO PARA INSERCIÓN DE ELEMENTOS EN UNA
COLA ENCADENADA
Las partes señaladas con "x" se ha eliminado al aplicar algoritmo
"x" "x"
front --->//<-----rear nil P front----->[ M | ]<-----------rear / "x"="P" [ N | ]<-----rear /="P" front----->[ M | ]--->[ N | ]<-----------rear /="</B">
Regresa al algoritmo
Regresar al contenido
ELIMINAR NODOS EN UNA LISTA DOBLEMENTE
ENCADENADA (CIRCULAR)
eleminar el nodo [ | C | ]
<------<----------<-----------<------------<----------------<------------->-> [ | A | ]<-->[ | B | ]<-->[ | C | ] <-->[ | D | ]<-->------------------->------------------->----------->-------------->
Queda:
<------<----------<-----------<------------<----------->-> [ | A | ]<-->[ | B | ]<-->[ | D | ]<-->------------------->------------------->----------
eleminar el nodo [ | A | ]
<------<-------<---------<----------->->[ | B | ]<-->[ | D | ]<-->------>------------->----------
HREF="#ALG5U3">Regresar al algoritmo
Regresar al contenido
ALGORITMO PARA INSERTAR NODOS EN UNA LISTA
CIRCULAR DOBLEMENTE ENCADENADA
<------<----------<-----------<------------<-------------->-> [ | A | ]<-->[ | B | ]<-->[ | C | ] <-<->------------------->------------------->----------->
insertando el nodo [ | 1 | ] despues del nodo con información B
<------<----------<-----------<------------<----------------<--------------->-> [ | A | ]<-->[ | B | ]<-->[ | 1 | ] <-->[ | C | ]<<-->------------------->------------------->----------->--------------->
insertando el nodo [ | 3 | ] despues del nodo con información al principio
<------<----------<-----------<------------<----------------<----------<------------------>-> [ | 3 | ]<-->[ | A | ]<-->[ | B | ] <-->[ | 1 | ]<-->[ | C | ]<<-->------------------->------------------->----------->-------------->------------------>
HREF="#ALG6U3">Regresar al algoritmo
Regresar al contenido