estructuras datos
DESCRIPTION
Tipos de EstructurasTRANSCRIPT
DISEÑO DE ESTRUCTURA DE DATOS
Karim Guevara Puente de la Vega
2015
Agenda
Introducción
Revisión de técnicas
Gestión de memoria
Programación Modular
Programación Orientada a Objetos
Tipos de Datos Abstractos
Patrones de Diseño
2
Introducción
Las estructuras de datos se utilizan para organizar los
datos con el fin de recuperar la información tan rápido
como sea posible.
Además de la idea representada por una estructura de
datos, los algoritmos utilizados para su gestión (e
implementación) también son importantes.
Enfoque incremental de como diseñar estructuras de
datos centradas en su aplicación
Objetivo: elegir soluciones eficientes y flexibles que
hagan que el sw sea más fácil de mantener y escalar.
3
Revisión
Existen técnicas de diseño de estructura de datos que
pueden ser clasificadas de acuerdo a varios criterios:
Dinamismo, protección de datos, encapsulación,
abstracción de datos, etc.
Dinamismo:
Uso de memoria estática vs. Memoria dinámica
4
Dinamismo
Variables estáticas
Variables dinámicas
Revisión
Protección de datos:
Prominente con la llegada de la POO.
Variables globales, variables en espacios de nombres,
miembros de clases public, miembros protected y private.
5
Data protection
None
Free access
Global variables
Variables into namespace
public members
Partially protected
protected members
Full protected private
members
Revisión
Encapsulación:
Variables globales y funciones en donde no se usa
encapsulación de datos.
Clases, contienen miembros, métodos e incluyen clases y
estructuras anidadas.
Cuando la clase es más compleja, es necesario tener una
vista parcial de ella. La interfaces proveen estas técnica de
acceso parcial a la clase.
Desde un punto de vista de alto nivel, podemos ver que los
namespace tiene niveles de encapsulamiento alto.
• Un namespace contiene variables globales, funciones
globales, clases, estructuras e inclusive namespace anidados.
6
Revisión
Encapsulación:
7
Encapsulación
Variables Funcione
s
Atributos
Métodos
Estructures Clases
Interfaces namespace X
• Variables
• Funciones
• Estructuras
• clases
namespace y
• Variables
• Funciones
• Estructuras
• clases
namespace A Estructuras
clases
Revisión
Abstracción: Técnicas inflexibles, diseño de estructuras de datos para un tipo
especifico de datos.
También se puedes diseñar estructuras de datos para tipos abstractos
de datos utilizando templates.
• template, reduce el mantenimiento de código.
Si el tipo de dato debe ser conocido en tiempo de ejecución, se usa otras
técnicas (no templates)
8
Abstracción de Datos
Técnicas inflexibles
Técnicas flexibles
Tiempo ejecución
void * y
punteros a funciones
Tiempo compilación
templates
Gestión de memoria
Un componente que encapsule un vector:
de tamaño fijo, global
• Solución simple en términos de código
Dinámico, global
9
Vectores de tamaño fijo
gpVect: vector de tamaño fijo, que almacene los elementos
de tipo integer
gnCount: variable global, para controla el número de
elementos en el vector.
Se requiere algunas funciones
10
int gpVect[100]; // Buffer to save the elements
int gnCount = 0; // Counter to know the number of elements used
void Insert(int elem) {
if( gnCount < 100 ) // we can only insert if there is space
gpVect[gnCount++] = elem; // Insert the element at the end
}
Vectores de tamaño fijo
Ventajas
No se requiere tiempo adicional para gestionar la memoria
(alloc, malloc, new, free, delete)
Desventajas:
Falta de flexibilidad
No es posible utilizar este código para más de un vector en
el mismo sistema, ni para más de un tipo de datos.
• Duplicar el mismo código y cambiar el tipo
11
Vectores dinámicos y variables
Punteros, manejo de memoria dinámica
12
int *gpVect = NULL; // Dynamic buffer to save the elements int
gnCount = 0; // Counter to know the number of used elements int
gnMax = 0; // Variable containing the size of the allocated
// memory
void Insert(int elem) {
if( gnCount == gnMax ) // There is no space at this moment for elem
Resize(); // Resize the vector before inserting elem
gpVect[gnCount++] = elem; // Insert the element at the end of the
sequence
}
Vectores dinámicos y variables
13
void Resize() {
const int delta = 10; // Used to increase the vector size
gpVect = (int *) realloc(gpVect, sizeof(int) * (gnMax + delta));
gnMax += delta; // The Max has to be increased by delta
}
Vectores dinámicos y variables
14
void Resize() {
const int delta = 10; // Used to increase the vector size
int *pTemp, i;
pTemp = new int[gnMax + delta]; // Alloc a new vector
for(i = 0 ; i < gnMax ; i++) // Transfer the elements
pTemp[i] = gpVect[i]; // we can also use the function memcpy
delete [ ] gpVect; // delete the old vector
gpVect = pTemp; // Update the pointer
gnMax += delta; // The Max has to be increased by delta
}
Vectores dinámicos y variables
Ventajas
Más flexible que la anterior
El espacio de memoria asignado será siempre igual o un
poco mayor al que requiera el usuario
Desventajas:
Esta basada en el uso de varibales globales, solo es
posible un vector por programa
• Falta de flexibilidad
Comparado con la solución anterior, es necesrio tiempo
extra para el manejo de la memoria.
15
Programación modular
Una posible solución que permite la coexistencia de dos o
mas vectores en el mismo sistema es enviar parámetros por
referencia (p.e. gpVect, gnCount y gnMax) a la función
Insert().
16
void Insert(int *& rpVect, int& rnCount, int& rnMax, int elem){
if( rnCount == rnMax ) // Verify the overflow
Resize(rpVect, rnMax); // Resize the vector before inserting elem
rpVect[rnCount++] = elem; // Insert the element at the end of the sequence
}
void Resizet(int *& rpVect, int& rnMax) {
const int delta = 10; // Used to increase the vector size
rpVect = (int *) realloc(rpVect, sizeof(int) * (rnMax + delta));
rnMax += delta; // The Max has to be increased by delta
}
Programación modular
En general, diferentes funciones pueden necesitar diferentes
parámetros aunque pertenezcan al mismo grupo y trabajar con el
mismo grupo de datos.
Si se requiere «n» parámetros?... Agruparlos en una struct.
Esta técnica permite acceder a m_pVect, m_nCount y m_nMax a
través de un único parámetro adicional (un puntero a la estructura).
17
struct Vector {
int*m_pVect, // Pointer to the buffer
m_nCount, // Control how many elements are actually used
m_nMax, // Control how many are allocated as maximum
m_nDelta; // To control the growing
};
Programación modular
18
void Insert (Vector *pThis, int elem) {
if( pThis->m_nCount == pThis->m_nMax ) // Verify the overflow
Resize(pThis); // Resize the vector before inserting elem
// Insert the element at the end of the sequence
pThis->m_pVect[pThis->m_nCount++] = elem;
}
void Resize (Vector *pThis) {
pThis->m_pVect = (int *) realloc(gpVect, sizeof(int) *
(pThis->m_nMax + pThis->m_nDelta));
// The Max has to be increased by delta
pThis->m_nMax += pThis->m_nDelta;
}
Programación modular
Ventajas:
Es posible tener más de un vector por programa,
definiendo variables locales que serán pasados a las
funciones.
Además de la flexibilidad, no necesitamos un número
variable de parámetros adicionales. Es importante, ya que
reduce el mantenimiento.
Desventajas:
No hay protección de datos.
19
Programación Orientada a Objetos
Note que lo anterior es lo suficientemente cercano a la
Programación Orientada a Objetos, ¿ por qué?...
Se ha encapsulado los datos m_pVect, m_nCount,
m_nMax y m_nDelta en la estructura Vector.
Al enviar esta estructura como parámetro a todas las
funciones que trabajan en torno a Vector, se tiene el mismo
principio utilizado por las clases en C++
20
Programación Orientada a Objetos
21
// Class CVector definition
class Cvector {
private:
int *m_pVect, // Pointer to the buffer
m_nCount, // Control how many elements are actually used
m_nMax, // Control how many are allocated as maximum
m_nDelta; // To control the growing
void Init(int delta); // Init our private variables, etc
void Resize(); // Resize the vector when occurs an overflow
public:
CVector(int delta = 10); // Constructor
void Insert(int elem); // Insert a new element
// More methods go here
};
void CVector::Insert(int elem) {
if( m_nCount == m_nMax ) // Verify the overflow
Resize(); // Resize the vector before inserting elem
m_pVect[m_nCount++] = elem; // Insert the element at the end
}
Programación Orientada a Objetos
Ventajas
Existe protección de datos. Sólo las funciones autorizadas
pueden acceder a los datos.
Desventajas
Si se necesita tener dos vectores utlizando diferentes tipos,
se debe de tener dos clases diferentes con el mismo
codigo, excepto por las declaraciones de tipo.
22
Tipos de Datos Abstractos
Requerimiento: «usuario necesita alguna caja negra que
encapsule una estructura de datos vector»…. Pero no
se especifico el tipo de elementos a insertar.
Es decir, la caja negra debe ser utilizada
independientemente del tipo de datos.
Primer intento para resolver esto, es incluir una
declaración typedef global.
23
Tipos de Datos Abstractos
Permite reducir costos de mantenimiento del código en caso
se necesite otro tipo como float, double, etc.
Sin embargo, si el usuario necesita dos o más vectores de
diferentes typos en el mismo sistema este código no se
podría utilizar.
24
typedef int Type;
class CVector {
private:
Type*m_pVect; // Pointer to the buffer
...
public:
void Insert(Type elem); // Insert a new element
...
};
Tipos de Datos Abstractos
Existen los templates, que permiten la parametrización del
tipo de elementos.
25
template <typename Type> class CVector {
private:
Type*m_pVect; // Pointer to the buffer
int m_nCount, // Control how many elements are actually used
m_nMax, // Control the number of allocated elements
m_nDelta; // To control the growing
void Init(int delta); // Init our private variables, etc
void Resize(); // Resize the vector when occurs an overflow
public:
CVector(int delta = 10); // Constructor
void Insert(Type elem); // Insert a new element
// ...
};
Tipos de Datos Abstractos
26
// Class CVector implementation
template <typename Type> CVector<Type>::CVector(int delta) {
Init(delta);
}
template <typename Type> void CVector<Type>::Insert(Type
&elem) {
if( m_nCount == m_nMax ) // Verify the overflow
Resize(); // Resize the vector before inserting elem
m_pVect[m_nCount++] = elem; // Insert the element at the end
}
Patrones de diseño
Un patrón es una solución recurrente a un problema estándar. Cuando
los patrones relacionados se juntan, forman un «lenguaje» que
proporciona un procedimiento para la resolución ordenada de los
problemas por medio del desarrollo de software.
Tanto los patrones y los lenguajes de patrones ayudan a los
desarrolladores a comunicar aspectos arquitecturales, a aprender
nuevos paradigmas de diseño o estilos arquitecturales de resolver un
problema.
Una estructura de datos robusta debe siempre proveer algunos
mecanismos que ejecuten algunas operaciones sobre los datos que
contiene. Standard Template Library (STL).
STL implementa muchos contenedores para las más comunes estructuras
de datos usando templates: listas enlazadas, vector, queue
Todas tienen un tipo de dato definido internamente llamado iterator.
27
Patrones de diseño
28
#include <vector> // without .h
#include <list>
#include <iostream>
using namespace std;
template <typename Container> void Write(Container &ds, ostream &os)
{
Container::iterator iter = ds.begin();
for( ; iter != ds.end() ; iter++ )
os << *iter << "\n";
}
int main(int argc, char* argv[]) {
list<float> mylist;
vector<float> myvector;
for( int i = 0 ; i < 10 ; i++ ) {
mylist .push_back( i );
myvector.push_back(i+50);
}
Write(mylist, cout);
Write(myvector, cout);
return 0;
}