TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un...
-
Upload
pilar-carmona-zuniga -
Category
Documents
-
view
230 -
download
0
Transcript of TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un...
![Page 1: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/1.jpg)
TIPOS ABSTRACTOSDE DATOS
![Page 2: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/2.jpg)
2
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)
![Page 3: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/3.jpg)
3
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
![Page 4: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/4.jpg)
4
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
![Page 5: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/5.jpg)
5
LA CLASE STACK
#define MAX 10typedef int Base;typedef Base Vector[MAX];class Stack { private: Vector v; int top; public: Stack(); bool Empty(); void Push(Base); Base Pop();};
![Page 6: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/6.jpg)
6
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--];}
![Page 7: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/7.jpg)
7
LA CLASE STACK
EjercicioImplementar 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;}
![Page 8: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/8.jpg)
8
QUEUES (COLAS)
Una cola es un TAD de comportamiento FIFO, con las operaciones crear, agregar, extraer y vacía
En una cola sólo se puede acceder a uno de extremos, denominado rear, para agregar un elemento y al otro, denominado front, para extraer un elemento
![Page 9: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/9.jpg)
9
LA CLASE COLA
#define MAX 10typedef int Base;typedef Base Vector[MAX];class Cola { private: Vector v; int front; int rear; public: Cola(); bool Vacia(); void Agregar(Base); Base Extraer();};
![Page 10: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/10.jpg)
10
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];}
![Page 11: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/11.jpg)
11
LA CLASE COLA
EjercicioRefleja 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); }}
![Page 12: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/12.jpg)
12
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
![Page 13: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/13.jpg)
13
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
![Page 14: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/14.jpg)
14
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
![Page 15: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/15.jpg)
15
HEAPS
Representación de árbol
5
15
2540
10
20 30
3545 55 60 Entran
Salen
![Page 16: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/16.jpg)
16
HEAPS
Numeración de nodos
1
3
74
2
5 6
108 9
![Page 17: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/17.jpg)
17
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 :
![Page 18: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/18.jpg)
18
LA CLASE HEAP
#define MAX 10typedef int Base;typedef struct Elemento { int p; Base info;};typedef Elemento Vector[MAX];
![Page 19: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/19.jpg)
19
LA CLASE HEAP
class Heap { private: Vector v; int n; void Subir(); void Bajar(); public: Heap(); bool Vacio(); void Agregar(Elemento); Elemento Extraer();};
![Page 20: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/20.jpg)
20
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; }}
![Page 21: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/21.jpg)
21
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;}
![Page 22: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/22.jpg)
22
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();}
![Page 23: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/23.jpg)
23
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;}
![Page 24: TIPOS ABSTRACTOS DE DATOS. 2 Un Tipo Abstracto de Dato (TAD) es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables.](https://reader036.fdocumento.com/reader036/viewer/2022081511/5665b4961a28abb57c9269ad/html5/thumbnails/24.jpg)
24
LA CLASE HEAP
EjercicioImplementar 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); }}