- Introducción
- Concepto de datos
estructurados - Estructuras de datos
estáticas - Estructuras dinámicas de datos no
lineales - Conclusiones
- Bibliografía
Introducción
La mayor parte de la información útil en
la práctica, no aparece en forma de datos simples aislada
de otro tipo de datos, al contrario, aparece de forma
estructurada y organizada. Las enciclopedias, diccionarios,
revistas, libros en general, son colecciones de datos que
serían complejos por no decir imposibles de leer si no
hicieran parte de una organización lógica con
determinadas reglas.
El agrupar la información y poner en ella una
estructura facilita su acceso, administración y hace
aún más importante y relevante su contenido. Por
ello la importancia de la escogencia de una estructura de datos
frente a otra, ya que en el momento de la programación es
decisivo el algoritmo a utilizarse para la resolución de
determinado problema recordando siempre la
ecuación:
"PROGRAMACION = ESTRUCTURA DE DATOS +
ALGORITMOS"
En el desarrollo de este ensayo, tendremos la
oportunidad de ver las ventajas de estructurar la
información de acuerdo a reglas básicas
establecidas. Se presentará la forma de
catalogación de los datos en estructuras estáticas
y dinámicas, así como las estructuras no lineales y
estudiaremos la teoría de colecciones de objetos
denominada Grafos. .
Concepto de datos
estructurados
Un dato simple no supone ningún tipo de
estructura diferente a los bits, no obstante se presentan algunas
operaciones propias de cada tipo que les da de alguna manera una
caracterización. Una estructura de datos se define como
una colección de datos de tipo simple que se caracteriza
por su organización y las operaciones que se
efectúan entre ellos. Esto significa que formalmente
podremos expresar mediante un conjunto de reglas, las operaciones
y relaciones que se pueden ejecutar sobre los datos.
Un dato de tipo estructurado es una Entidad con un
identificador que se constituye por datos de otro tipo de acuerdo
con las reglas que definen las estructuras de datos, como por
ejemplo: una cadena se forma con una sucesión de
caracteres, una [1]matriz se forma por datos
simples organizados en filas y columnas y, un archivo se compone
de registros y los anteriores por campos que se componen de datos
simples.
Figura 1 – Arreglo
Matricial
Estructuras de datos
estáticas
Arreglo
Es una colección ordenada y homogénea de
elementos del mismo tipo y agrupados bajo el mismo nombre de una
variable. Los arreglos son utilizados como contenedores que
almacenan tipos de datos que se relacionan entre si, como por
ejemplo los números reales y los números enteros,
entre otros.
Hay tres tipos de arreglos, los Unidimensionales
(vectores), los bidimensionales (matrices) y los de tres o
más dimensiones (multidimensionales).
Arreglos Unidimensionales
Un arreglo unidimensional conocidos como vectores
requieren de subíndice para direccionarse.
Arreglo Bidimensional
Arreglo bidimensional o matriz requiere de
los dos índices para el acceso a los datos.
Arreglo Multidimensional
Es un dato de tipo estructurado el cual se
compone por n dimensiones y es necesario, para hacer referencia a
cada componente, la utilización de n índices, uno
para cada dimensión.
Características de un
arreglo
Dimensión, es la longitud y/o cantidad total
de datos que lo conforman.Indización, indica la posición de cada
uno de los elementos dentro de la estructura.Tipo, define el tipo de datos que se
almacenarán en el arreglo. Cuando no se sabe con
seguridad si los datos serán del mismo tipo para todas
las posiciones se utiliza la clase
[2]Object.
Vectores
Son estructuras estáticas de datos
que permiten agrupar datos de un mismo tipo, llamadas
también arreglos unidimensionales.
Representación
Gráfica
Los vectores se presentan en forma de fila
o columna de la siguiente manera:
Figura 2
-[3]Representación Gráfica –
Vectores
ESTRUCTURA DINÁMICAS DE
DATOS
Las estructuras de datos dinámicas son una
colección de elementos denominados nodos en donde la
estructura puede aumentar o disminuir durante la ejecución
de un programa. Las estructuras de datos dinámicas
están clasificadas en:
PRIMERA CLASIFICACIÓN
Estructuras de datos dinámicas lineales, como
lo son las listas enlazadas, las colas, las pilas, las listas
dobles, las listas circulares
SEGUNDA CLASIFICACIÓN
Estructuras de datos no lineales, como lo son los
árboles y los grafos
ESTRUCTURAS DE DATOS DINÁMICAS
LINEALES
Las estructuras de datos dinámicas lineales
están conformadas por las listas, las cuales a su vez son
una colección de elementos organizados en forma secuencial
que pueden disminuir o aumentar el número de elementos que
las integra, esto mediante las operaciones con nodos que pueden
ser insertar y/o eliminar.
Listas Enlazadas
Son estructuras dinámicas de datos
compuestas por un conjunto de elementos del mismo tipo
denominados nodos e interconectados entre sí a
través de una o más referencias.
Representación gráfica de
Nodo
La representación gráfica de
Nodo es un rectángulo conformado por dos campos como
mínimo:
Dato (información), puede ser
uno o varios camposReferencia, que es el enlace al
siguiente [4]nodo
Figura 3 – Representación
Gráfica de Nodo
El dato puede ser informativo: código,
identificación, dirección, nombres, apellidos,
teléfono, correo, etc., en [5]Java
corresponden a datos de tipo "int, char, long, doublé";
objetcts tipo String.
Figura 4 – Datos dento de Nodo –
Lista
La referencia puede tomas únicamente dos valores
únicamente: null (sin direccionamiento) o, la referencia
del segundo nodo.
La referencia es también conocida como enlace,
link, sigue¿iente nodos, próximo, sig.
Figura 5 – Analogía Dato –
Referencia
Tipos de Listas Enlazadas
Una lista enlazada es una secuencia de nodos
interconectados entre si y pueden ser de los siguientes
tipos:
Enlazadas simples.
Doblemente enlazadas.
Enlazadas y circulares.
Enlazadas doblemente circulares
Representación Gráfica de una
Lista
En la siguiente figura se evidencia la
interconexión o enlace del primer nodo con el segundo, el
segundo con el tercero y así continúa hasta el
último nodo.
Ya que el último nodo no tiene
enlace alguno hacia otro nodo, se le da el valor de null, el cual
se puede representar: (.) punto, (^) circunflejo, ()
línea inclinada o, el símbolo de tierra en
electrónica.
Figura 6- [6]Simbolo
Tierra
Representación de
[7]null en un nodo
Figura 7 – Representación null
en un nodo
Representación de la
Referencia:
Figura 8 – [8]La
Referencia de un nodo
Operaciones entre listas
enlazadas
Entre listas enlazadas se pueden realizar
las siguientes operaciones:
Recorrido, consiste en visitar los nodos que
conforman la listaInserción, consiste en anexar un nodos a la
lista de nodosEliminar, consiste en la eliminación de un
nodo que pertenece a la listaBusqueda, consiste en visitar cada nodo tomando al
campo de referencia como el enlace al nuevo nodo a visitar y
para realizar la búsqueda es necesario recorrer desde
el prier hasta el último nodo
Estructuras
dinámicas de datos no lineales
Las estructuras dinámicas de datos no lineales
están conformadas por árboles y grafos. A
continuación abordaremos los fundamentos de teoría
de árboles, más adelante entraremos en detalle con
la descripción y teoría de
[9]Grafos.
Árboles
Un árbol es una estructura de datos no lineal con
jerarquía aplicada a una colección de objetos
llamados nodos, en donde uno de ellos se conoce como raíz
y de él se genera una relación de parentesco entre
los otros nodos dando lugar a los términos padre, hijo,
etc. Puesto en otras palabras, un árbol es una
colección de nodos interconectados por aristas.
Características de los
árboles
Son estructuras de datos no-lineales,
ya que a cada elemento le pueden seguir varios nodos
(elementos).Es una estructura jerárquica que
se aplica sobre una colección de elementos de nombre
"nodos", en donde uno de ellos es llamado
raíz.La jerarquía representada en la
relación de parentesco entre los nodos es de padre,
hijo, hermano, antecesor, sucesor, ancestro, etc.Se utiliza en la representación
de fórmula matemáticas, secciones de un libro,
numeración de capítulos, organización de
información y árboles
genealógicos.Son jerárquicos ya que sus
componentes están a diferente nivel.Son dinámicas porque su
tamaño, contenido y forma pueden cambiar durante la
ejecución, ya que el árbol puede ser
vacío, con una raíz y sub
árboles.
A continuación se presenta algunas
de las representaciones gráficas de los
árboles:
Representación de árbol
mediante diagrama de Venn
Figura 9 – [10]Diagrama
de Venn
Representación de árbol
Mediante círculos y flechas (nodo y aristas)
Figura 10 – Nodos y
Aristas
Representación de árbol
Mediante paréntesis anidados
Figura 11 – Paréntesis
anidados
Representación de árbol
Mediante Nodos
Elementos de un árbol
Figura 12 – Elementos de un
árbol
Raíz: Nodo que no presenta
antecesorRama: [11]arista que
conecta dos nodosAntecesor: un nodo X es el antecesor de
un nodo Y si por las ramas de X se puede llegar a
Y.Sucesor: un nodos A es sucesor de un
nodo B si por las ramas de A se puede llegar a B.Grado de un nodos: número de
descendientes directos de un nodo.Grado del árbol: el mayor grado
entre los nodos que lo componen.Nodo interno: el que al menos tiene un
nodo hijo o descendiente.Nodo hoja (externo): no tiene
descendientes o nodo hijo, es grado 0.Descendiente directo: hijo
Descendientes: hijo, nieto,
bisnieto…Subárbol: árbol
conformado por un nodos y descendientesPadre: antecesor inmediato de un
nodoHijo; descendientes
inmediatos.Descendiente de un nodo: cualquier
sucesor de cualquier nodo.Hermano de un nodo: otro nodo al que le
corresponde el mismo padre.Generación: conjunto de nodos
los cuales tienen profundidad igual.Hoja: nodo sin sucesores, sin
hijos.Rama: es cualquier camino presente en
el árbol
Arbol Binario
Es un conjunto de elementos que puede estar vacío
ó estar formado por una raíz con dos árboles
binarios disjuntos llamados subárbol izquierdo y
subárbol derecho respecto a la raíz. Sus
aplicaciones son variadas debido a que se les puede usar para
representar una estructura en la cual es posible tomar decisiones
con dos opciones en distintos puntos.
Representaciónes de árbol
binario en la memoria
Representación gráfica de
un nodo de un árbol
Figura 13 – [12]Nodo de
un árbol
Representación mediante
nodos
Figura 14 – Mediante
nodos
Operaciones de un árbol
Recorrer árbol
Preorden
Inorden
Postorden
Inserción nodo
Grafos
Estructura de datos no lineal que se utiliza para
representar las relaciones no siempre jerárquicas entre
objetos de datos.
La teoría de los grafos estudia las propiedades
de colección de objetos a los que se les llama nodos o
vértices conectados por vínculos denominados
enlaces, los cuales a su vez, puede no tener ninguna
orientación.
En la siguiente figura, los círculos corresponden
a los nodos o vértices y las líneas que los unen o
enlaces son las [13]aristas.
Figura 15 – Grafo
Un grafo es un par G = (V, E),
donde:
V es un conjunto de puntos de nombre
nodosE es un conjunto de pares de nodos de
nombre enlaces o arcosUn enlace {n,m} se puede denotar
nm
Generalmente los grafos se clasifican en
dirigidos y no dirigidos, dependiendo de si las aristas
están orientadas o no y entre grafos con etiquetas o no en
función de si las aristas tienen o no tienen
información asociada.
Algunas Aplicaciones de los
Grafos
En Internet, al visitar una
página y hacer click en algún enlace, visto
como grafo, los vértices son los sitios y sus aristas
son los enlaces.Con la teoría de Grafos es
posible resolver problemas planteados en síntesis de
circuitos secuenciales, contadores o sistemas de
apertura.Los Grafos pueden ser útiles en
la modelación de trayectos en rutas de buses por
calles de una ciudad para obtener rutas óptimas
aplicando algoritmos como el [14]Algoritmo de
FloydEn administración de proyectos
se utiliza la técnica de PERT en la que se modelan
utilizando grafos se optimizan los tiempos para concretar
actividades.
Grafos Dirigidos
Los elementos tienen asociada una
dirección
Figura 16 – Grafos Dirigidos – No
Dirigidos
El conjunto de vértices es V = { A,
B, C, D, E }
Grafos no dirigidos
Figura 17 – Grafos – Aristas –
Arcos
La arista es un par de vértices (v,w) si el par
está ordenado se dice que el grafo es dirigido o
dígrafo.
Adyacencia
Se dice que un vértice es adyacente
a otro si existe una arista que los una y la adyacencia puede
ser:
Adyacencia desde
Adyacencia hasta
Figura 18 – Grafos –
Adyacencia
Los vértices A y B son
adyacentes, A es adyacente a B y B es adyacente a C y C es
adyacente a D
Camino
Secuencia de vértices que cada uno
es adyacente al anterior.
Figura 19 – Grafos –
Camino
Camino Simple
Si al partir de cualquier vértice se puede
recorrer la estructura del grafo sin repetir algún
vértice, arco o arista. Es el grafo cuyos vértices
son todos distintos excluyendo posiblemente el primero y el
último, por ej., iniciando de D hasta E o partiendo de E
hasta D.
Peso o Costo
Las aristas pueden conectar datosy uno de
ellos puede ser el peso o costo asociado a esa arista para
determinar el costo de recorrer el camino.
Figura 20 – Grafos – Peso o
costo
Longitud del camino
Es el número de aristas con que
cuenta el grafo. Por ej., del vértice A al F hay dos
aristas.
Coste de un camino
La suma de los pesos de sus aristas. Por
e., el costo para llegar del vértice A al F puede
ser:
7 + 9 = 16 o 1 + 2 + 9 = 12
Es de anotar que a veces el camino m[as
corto no es el m[as económico.
Tipos de grafos
Como hemos visto un grafo es un conjunto de
nodos unidos por arcos que tienen posiblemente una
dirección y se clasifican en:
Grafos Dirigidos detallados
anteriormenteGrafo No dirigidos detallados
anteriormenteGrafos regulares
Se presentan cuando todos los
vértices presentan el mismo grado y el grado de un
vértice corresponden al número de aristas que
inciden en el mismo vértice:
Figura 21 – Grafo
Regular
Grafos cíclicos
Si un vértice llega al mismo
vértice el grafo es cíclico.
Figura 22 – Grafo
Cíclico
Conclusiones
La asignatura aporta al ingeniero la capacidad para
desarrollar ideas lógicas y a identificar el proceso de
desarrollo de aplicaciones enfocado en la resolución de
problemas.
Los conceptos de arreglos nos permite ubicar y
clasificar los tipos de datos con el objeto de definir variables
que nos permiten almacenar números fijos de datos de
acuerdo a lineamientos de estructuras de datos estáticas o
por lo contrario, cuando se necesita almacenar cantidades de
datos no determinadas nos podemos basar en lineamientos de
estructuras de datos dinámicas.
Los datos se encuentran generalmente catalogados
jerárquicamente, sin embargo a través de los
conceptos de árbol podemos estructurar y nombrar cada
jerarquía haciendo aprovechando la organización ya
establecida para definir una organización detallada donde
confluyen capacidades cada vez más grande de datos, lo que
nos lleva al concepto de BIG DATA, en donde si bien existen
catalogadas grandes cantidades de información, la
administración, catalogación y gestión se
hacen perentorias, ya que la información es el tesoro
más grande para cualquier empresa, corporación o
individualidad.
Bibliografía
Title: Fundamentos de programacio´n
Author: Corbi´ Bellot, Antonio Date: 1999 eBook Academic
Collection (EBSCOhost) – AIU
CAIRÓ, O. & Guardati, S. (2006).
Estructuras de Datos. Tercera
edición.McGraw-Hill.
VILLALOBOS, JORGE, Introducción a
las Estructuras de Datos, Prentice Hall. 2008
http://ece.uprm.edu/~jrosado/oldexams/4102/calc/Matrices.htm
– Matrices Complejas, consulta realizada Octubre 07 de
2014
KRUSE. Robert L Estructuras de datos y
programas. Editorial: Prentice Hall (México).
http://www.monografias.com/trabajos10/esda/esda,
Estructuras de Datos, consultado Obtubre 07 de 2014
Autor:
Angel Alberto Echeverry
Castano
NOMBRE DEL CURSO: DATA & INFORMATION
STRUCTURE
FECHA: Marzo 27 de 2014LUGAR: Bogotá
D.C., Colombia
ATLANTIC INTERNATIONAL
UNIVERSITY
[1] Matriz: Arreglo rectangular de
números y su tamaño está dado por m x n
donde m =fila y n = columna
[2] Object: elemento de programación
Java utilizado para almacenar en las posiciones de un arreglo
el tipo de dato que se necesite.
[3] Regresentación Gráfica de
Vectores – Filas – Columnas
[4] Nodo: Colección de datos simples y
su referencia hacia otro nodo
[5] Java – Lenguaje de
programación estructurado con base en objetos
[6] Simbolo Tierra – En
electrónica este símbolo significa que el
circuito está aterrizado
[7] Null: representa ausencia de valor – fin
de lista
[8] Referencia de nodo: la
representación de la referencia de un nodo es una
flecha
[9] Grafos: Estructuras de datos no lineal
representada para representar relaciones no jerárquicas
entre objetos de datos
[10] Diagrama de Venn: esquemas de
graficación utilizados en la teoría de
conjuntos
[11] Arista: línea o flecha que
interconecta dos nodos representados en un árbol
[12] Nodo de un árbol –
representación gráfica en memoria
[13] Arista: línea o flecha que
referencian dos nodos en un grafo
[14] Algoritmo de Floyd: algoritmo de
análisis sobre grafos que permite encontrar el camino
mínimo en grafos dirigidos ponderados