Monografias.com > Ingeniería
Descargar Imprimir Comentar Ver trabajos relacionados

Estructuración de datos y aplicación en Ingeniería de Sistemas




Enviado por Angel Echeverry



  1. Introducción
  2. Concepto de datos
    estructurados
  3. Estructuras de datos
    estáticas
  4. Estructuras dinámicas de datos no
    lineales
  5. Conclusiones
  6. 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.

Monografias.com

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:

Monografias.com

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 campos

  • Referencia, que es el enlace al
    siguiente [4]nodo

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

Figura 6- [6]Simbolo
Tierra

Representación de
[7]null en un nodo

Monografias.com

Figura 7 – Representación null
en un nodo

Representación de la
Referencia:

Monografias.com

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 lista

  • Inserción, consiste en anexar un nodos a la
    lista de nodos

  • Eliminar, consiste en la eliminación de un
    nodo que pertenece a la lista

  • Busqueda, 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

Monografias.com

Figura 9 – [10]Diagrama
de Venn

Representación de árbol
Mediante círculos y flechas (nodo y aristas)

Monografias.com

Figura 10 – Nodos y
Aristas

Representación de árbol
Mediante paréntesis anidados

Monografias.com

Figura 11 – Paréntesis
anidados

Representación de árbol
Mediante Nodos

Monografias.com

Elementos de un árbol

Monografias.com

Figura 12 – Elementos de un
árbol

  • Raíz: Nodo que no presenta
    antecesor

  • Rama: [11]arista que
    conecta dos nodos

  • Antecesor: 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 descendientes

  • Padre: antecesor inmediato de un
    nodo

  • Hijo; 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

Monografias.com

Figura 13 – [12]Nodo de
un árbol

  • Representación mediante
    nodos

Monografias.com

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.

Monografias.com

Figura 15 – Grafo

Un grafo es un par G = (V, E),
donde:

  • V es un conjunto de puntos de nombre
    nodos

  • E es un conjunto de pares de nodos de
    nombre enlaces o arcos

  • Un 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
    Floyd

  • En 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

Monografias.com

Figura 16 – Grafos Dirigidos – No
Dirigidos

El conjunto de vértices es V = { A,
B, C, D, E }

Grafos no dirigidos

Monografias.com

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

Monografias.com

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.

Monografias.com

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.

Monografias.com

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
    anteriormente

  • Grafo No dirigidos detallados
    anteriormente

  • Grafos 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:

Monografias.com

Figura 21 – Grafo
Regular

  • Grafos cíclicos

Si un vértice llega al mismo
vértice el grafo es cíclico.

Monografias.com

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

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter