Algoritmo Colas Eliminacion
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Algoritmo Colas Eliminacion as PDF for free.
More details
- Words: 548
- Pages: 6
Colas Doblemente Colas Encadenadas Encadenadas
Comience I <= V PRUEB-COL-NG(NG, VACIA) Si (VACIA) Entonces I <= F Sino P <= *NG.ENLA Si (*P.ENLA= NG) Entonces DATO <= *P.INFO Sino P <= *P.ENLA DATO <= *P.INFO Fin-Si Fin-Si Termine ALGORITMO INSER-CC-NG(NG,DATO,I) Precondición: Apuntador NG válido. El contenido INFO del último nodo de la cola es DATO. Este nodo es el que sigue al nodo guía en la cola circular. Comience ASIGNA-NODO(Q,DATO,I) Si (I) Entonces PRUEBA-CC-NG(NG,VACIA) Si (VACIA) Entonces *NG.ENLA<= Q *Q.ENLA<= NG Sino P <= *NG.ENLA UC <= P Mientras (*P.ENLA<> NG) Ejecute P <= *P.ENLA Fin-Mientras *P.ENLA <= UC *Q.ENLA <= ENLA(*UC) *UC.ENLA <= NG *NG.ENLA <= Q Fin-Si Sino Fin-Si Termine
2.5 Doble Cola Esta estructura es una cola bidimensional en que las inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la bicola. Gráficamente representamos una bicola de la siguiente manera:
Existen dos variantes de la doble cola: • •
Doble cola de entrada restringida. Doble cola de salida restringida.
La primer variante sólo acepta inserciones al final de la cola, y la segunda acepta eliminaciones sólo al frente de la cola
ALGORITMOS DE ENTRADA RESTRINGIDA
Algoritmo de Inicialización F < -- 1 A <-- 0
Algoritmo para Insertar Si A=máximo entonces mensaje (overflow) en caso contrario A <--A+1 cola[A]<-- valor
Algoritmo para Extraer Si F>A entonces mensaje (underflow) en caso contrario mensaje (frente/atrás) si frente entonces x <-- cola[F]
F <-- F+1 en caso contrario x <-- cola[A] A <-- A-1
ALGORITMOS DE SALIDA RESTRINGIDA
Algoritmo de Inicialización F <--1 A <-- 0
Algoritmo para Insertar Si F>A entonces mensaje (overflow) en caso contrario mensaje (Frente/Atrás) si Frente entonces cola[F] <--valor en caso contrario A <-- A+1 cola[A] <--valor
Algoritmo para Extraer Si F=0 entonces mensaje (underflow) en caso contrario x <--cola[F] F <-- F+1
void eliminar (AVLTree ** t, int x); /* elimina x del árbol en un tiempo O(log(n)) peor caso. Precondición: existe un nodo con valor x en el árbol t. */ int eliminar_min (AVLTree ** t); /* Función auxiliar a eliminar(). Elimina el menor nodo del árbol *t devolviendo su contenido (el cual no se libera de memoria). Se actualizan las alturas de los nodos. Precondición: !es_vacio(*t) */
void eliminar (AVLTree ** t, int x) {
AVLTree *aux; if (x < raiz (*t)) eliminar (&(*t)->izq, x); else if (x > raiz (*t)) eliminar (&(*t)->der, x); else {
/* coincidencia! */ if (es_vacio (izquierdo (*t)) && es_vacio (derecho (*t))) {/* es una hoja */ free (*t); (*t) = vacio(); } else if (es_vacio (izquierdo (*t))) {/* subárbol izquierdo vacio */ aux = (*t); (*t) = (*t)->der; free (aux); } else if (es_vacio (derecho (*t))) {/* subárbol derecho vacio */ aux = (*t); (*t) = (*t)->izq; free (aux); } else /* caso más complicado */ { (*t)->dato = eliminar_min (&(*t)->der); }
} balancear (t); actualizar_altura (*t); }
int eliminar_min (AVLTree ** t) { if (es_vacio (*t)) { fprintf (stderr, "No se respeta precondición de eliminar_min()\n"); exit(0); } else { if (!es_vacio (izquierdo (*t))) { int x = eliminar_min (&(*t)->izq); balancear (t); actualizar_altura (*t); return x; } else {
AVLTree *aux = (*t); int x = raiz (aux); *t = derecho (*t); free (aux); balancear (t); actualizar_altura (*t); return x; }
}
}
Eliminación gaussiana básica
http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap5/57.html http://www.itlp.edu.mx/publica/tutoriales/estru1/25.htm http://es.tldp.org/Tutoriales/doc-programacion-arboles-avl/htmls/x235.html http://www.uv.es/~diaz/mn/node29.html
Comience I <= V PRUEB-COL-NG(NG, VACIA) Si (VACIA) Entonces I <= F Sino P <= *NG.ENLA Si (*P.ENLA= NG) Entonces DATO <= *P.INFO Sino P <= *P.ENLA DATO <= *P.INFO Fin-Si Fin-Si Termine ALGORITMO INSER-CC-NG(NG,DATO,I) Precondición: Apuntador NG válido. El contenido INFO del último nodo de la cola es DATO. Este nodo es el que sigue al nodo guía en la cola circular. Comience ASIGNA-NODO(Q,DATO,I) Si (I) Entonces PRUEBA-CC-NG(NG,VACIA) Si (VACIA) Entonces *NG.ENLA<= Q *Q.ENLA<= NG Sino P <= *NG.ENLA UC <= P Mientras (*P.ENLA<> NG) Ejecute P <= *P.ENLA Fin-Mientras *P.ENLA <= UC *Q.ENLA <= ENLA(*UC) *UC.ENLA <= NG *NG.ENLA <= Q Fin-Si Sino Fin-Si Termine
2.5 Doble Cola Esta estructura es una cola bidimensional en que las inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la bicola. Gráficamente representamos una bicola de la siguiente manera:
Existen dos variantes de la doble cola: • •
Doble cola de entrada restringida. Doble cola de salida restringida.
La primer variante sólo acepta inserciones al final de la cola, y la segunda acepta eliminaciones sólo al frente de la cola
ALGORITMOS DE ENTRADA RESTRINGIDA
Algoritmo de Inicialización F < -- 1 A <-- 0
Algoritmo para Insertar Si A=máximo entonces mensaje (overflow) en caso contrario A <--A+1 cola[A]<-- valor
Algoritmo para Extraer Si F>A entonces mensaje (underflow) en caso contrario mensaje (frente/atrás) si frente entonces x <-- cola[F]
F <-- F+1 en caso contrario x <-- cola[A] A <-- A-1
ALGORITMOS DE SALIDA RESTRINGIDA
Algoritmo de Inicialización F <--1 A <-- 0
Algoritmo para Insertar Si F>A entonces mensaje (overflow) en caso contrario mensaje (Frente/Atrás) si Frente entonces cola[F] <--valor en caso contrario A <-- A+1 cola[A] <--valor
Algoritmo para Extraer Si F=0 entonces mensaje (underflow) en caso contrario x <--cola[F] F <-- F+1
void eliminar (AVLTree ** t, int x); /* elimina x del árbol en un tiempo O(log(n)) peor caso. Precondición: existe un nodo con valor x en el árbol t. */ int eliminar_min (AVLTree ** t); /* Función auxiliar a eliminar(). Elimina el menor nodo del árbol *t devolviendo su contenido (el cual no se libera de memoria). Se actualizan las alturas de los nodos. Precondición: !es_vacio(*t) */
void eliminar (AVLTree ** t, int x) {
AVLTree *aux; if (x < raiz (*t)) eliminar (&(*t)->izq, x); else if (x > raiz (*t)) eliminar (&(*t)->der, x); else {
/* coincidencia! */ if (es_vacio (izquierdo (*t)) && es_vacio (derecho (*t))) {/* es una hoja */ free (*t); (*t) = vacio(); } else if (es_vacio (izquierdo (*t))) {/* subárbol izquierdo vacio */ aux = (*t); (*t) = (*t)->der; free (aux); } else if (es_vacio (derecho (*t))) {/* subárbol derecho vacio */ aux = (*t); (*t) = (*t)->izq; free (aux); } else /* caso más complicado */ { (*t)->dato = eliminar_min (&(*t)->der); }
} balancear (t); actualizar_altura (*t); }
int eliminar_min (AVLTree ** t) { if (es_vacio (*t)) { fprintf (stderr, "No se respeta precondición de eliminar_min()\n"); exit(0); } else { if (!es_vacio (izquierdo (*t))) { int x = eliminar_min (&(*t)->izq); balancear (t); actualizar_altura (*t); return x; } else {
AVLTree *aux = (*t); int x = raiz (aux); *t = derecho (*t); free (aux); balancear (t); actualizar_altura (*t); return x; }
}
}
Eliminación gaussiana básica
http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap5/57.html http://www.itlp.edu.mx/publica/tutoriales/estru1/25.htm http://es.tldp.org/Tutoriales/doc-programacion-arboles-avl/htmls/x235.html http://www.uv.es/~diaz/mn/node29.html
