Make your own free website on Tripod.com
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