Tipos abstractos de datos



Descargar 11,15 Kb.
Fecha de conversión24.03.2017
Tamaño11,15 Kb.

TIPOS ABSTRACTOS DE DATOS

  • Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables sobre ellos
  • Los lenguajes procedimentales no contemplan encapsulamiento, razón por la cual la representación (datos) no es exclusiva de la implementación (operaciones)
  • TIPOS ABSTRACTOS DE DATOS
  • Los lenguajes modulares proveen encapsula-miento, exclusividad de la implementación sobre la representación, pero no instanciación
  • Los lenguajes orientados a objetos proveen encapsulamiento, exclusividad de la implemen-tación sobre la representación e instanciación
  • STACKS (PILAS)
  • Un stack es un TAD de comportamiento LIFO, con las operaciones create, push, pop y empty
  • En un stack sólo se puede acceder a uno de sus extremos, el cual se denomina top
  • La operación push pone un elemento en el top del stack y la operación pop saca el elemento situado en el top del stack
  • LA CLASE STACK
  • #define MAX 10
  • typedef int Base;
  • typedef Base Vector[MAX];
  • class Stack {
  • private:
  • Vector v;
  • int top;
  • public:
  • Stack();
  • bool Empty();
  • void Push(Base);
  • Base Pop();
  • };
  • LA CLASE STACK
  • Stack::Stack() {
  • top = -1;
  • }
  • bool Stack::Empty() {
  • return top == -1;
  • }
  • void Stack::Push(Base e) {
  • v[++top] = e;
  • }
  • Base Stack::Pop() {
  • return v[top--];
  • }
  • LA CLASE STACK
  • Ejercicio
  • Implementar la función Ultimo(S), que elimina y retorna el último elemento existente en un stack S.
  • Base Ultimo(Stack &S) {
  • if(!S.Empty()) {
  • Base x = S.Pop();
  • if(!S.Empty()) {
  • Base y = Ultimo(S); S.Push(x); return y;
  • }
  • else return x;
  • }
  • else return 0;
  • }
  • QUEUES (COLAS)
  • LA CLASE COLA
  • #define MAX 10
  • typedef int Base;
  • typedef Base Vector[MAX];
  • class Cola {
  • private:
  • Vector v;
  • int front;
  • int rear;
  • public:
  • Cola();
  • bool Vacia();
  • void Agregar(Base);
  • Base Extraer();
  • };
  • LA CLASE COLA
  • Cola::Cola() {
  • front = 0;
  • rear = 0;
  • }
  • bool Cola::Vacia() {
  • return front == rear;
  • }
  • void Cola::Agregar(Base e) {
  • rear = (rear+1)%MAX;
  • v[rear] = e;
  • }
  • Base Cola::Extraer() {
  • front = (front+1)%MAX;
  • return v[front];
  • }
  • LA CLASE COLA
  • Ejercicio
  • Refleja es una cola con los mismos elementos de una cola Directa, pero en orden inverso. Implementar la función Reflejar(R, D), que concluya con las versiones Directa y Refleja de una cola.
  • void Reflejar(Cola &R, Cola &D) {
  • if(!R.Vacia()) {
  • Base x = R.Extraer();
  • D.Agregar(x);
  • Reflejar(R,D);
  • R.Agregar(x);
  • }
  • }
  • PRIORITY QUEUES
  • Una cola de prioridad es una cola cuyos elementos tienen asociada una prioridad que determina el orden en que son extraídos
  • Una prioridad es un número entre 1 y p, donde 1 es la prioridad más alta
  • En una cola de prioridad, se puede agregar un elemento de cierta prioridad, o bien, extraer el elemento de máxima prioridad
  • HEAPS
  • El heap es el caso más notable de cola de prioridad y se define como un árbol binario con todos sus niveles completos excepto, generalmente, el último donde todos los nodos están ajustados a la izquierda
  • Cada nodo en un heap tiene mayor prioridad que sus descendientes, de manera que el elemento de prioridad máxima se encuentra siempre en la raíz del árbol
  • HEAPS
  • Los elementos se ingresan por nivel, de izquierda a derecha
  • Después de un ingreso se debe reparar la eventual alteración de la propiedad de heap
  • Debido a la forma de organización del árbol, se puede usar un arreglo para representarlo. Basta con numerar los nodos consecutiva-mente por nivel, de arriba hacia abajo y de izquierda a derecha
  • HEAPS
  • Representación de árbol
  • 5
  • 15
  • 25
  • 40
  • 10
  • 20
  • 30
  • 35
  • 45
  • 55
  • 60
  • Entran
  • Salen
  • HEAPS
  • Numeración de nodos
  • 1
  • 3
  • 7
  • 4
  • 2
  • 5
  • 6
  • 10
  • 8
  • 9
  • HEAPS
  • Representación de arreglo
    • El padre de un elemento v[i] es v[j], con j=i/2
    • Un elemento v[j] tiene hijos v[i] y v[i+1], con i= 2*j
  • 0 1 2 3 4 5 6 7 8 9 10
  • 5 10 15 40 20 30 25 45 55 35
  • Salen
  • Entran
  • v :
  • #define MAX 10
  • typedef int Base;
  • typedef struct Elemento {
  • int p;
  • Base info;
  • };
  • typedef Elemento Vector[MAX];
  • LA CLASE HEAP
  • class Heap {
  • private:
  • Vector v;
  • int n;
  • void Subir();
  • void Bajar();
  • public:
  • Heap();
  • bool Vacio();
  • void Agregar(Elemento);
  • Elemento Extraer();
  • };
  • LA CLASE HEAP
  • void Heap::Subir() {
  • if(n > 1) {
  • int i=n, k=i/2;
  • v[0].p = v[n].p;
  • v[0].info = v[n].info;
  • while (v[k].p > v[0].p && k > 0) {
  • v[i].p = v[k].p;
  • v[i].info = v[k].info;
  • i = k; k = i/2;
  • };
  • v[i].p = v[0].p;
  • v[i].info = v[0].info;
  • }
  • }
  • LA CLASE HEAP
  • void Heap::Bajar() {
  • int k=1, i=2*k, fin=0;
  • v[0].p = v[1].p; v[0].info = v[1].info;
  • while (k <= n/2 && !fin) {
  • if (i < n)
  • if (v[i+1].p < v[i].p)
  • i = i+1;
  • if (v[0].p > v[i].p) {
  • v[k].p = v[i].p; v[k].info = v[i].info;
  • k = i; i = k*2;
  • }
  • else fin = 1;
  • }
  • v[k].p = v[0].p; v[k].info = v[0].info;
  • }
  • LA CLASE HEAP
  • Heap::Heap() {
  • n = 0;
  • }
  • bool Heap::Vacio() {
  • return (n == 0);
  • }
  • void Heap::Agregar(Elemento e) {
  • v[++n].p = e.p;
  • v[n].info = e.info;
  • Subir();
  • }
  • LA CLASE HEAP
  • Elemento Heap::Extraer() {
  • Elemento e = v[1];
  • v[1].p = v[n].p;
  • v[1].info = v[n--].info;
  • Bajar();
  • return e;
  • }
  • LA CLASE HEAP
  • Ejercicio
  • Implementar la función Impares(H), que elimina todos los elementos de ordinalidad par existentes en un heap H, es decir, los elementos segundo, cuarto, sexto, etc.
  • void Impares(Heap &H) {
  • if(!H.Vacio()) {
  • Elemento e1 = H.Extraer();
  • if(!H.Vacio())
  • Elemento e2 = H.Extraer();
  • Impares(H);
  • H.Agregar(e1);
  • }
  • }


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal