Tipo de estructuras1

ESTRUCTURAS LINEALES

LISTAS

Una lista es una colección o secuencia de elementos

dispuestos uno detrás de otro, en la que cada

elemento se conecta al siguiente por un “enlace”.

Los elementos de las listas se denominan nodos y

se componen de dos partes: la primera contiene la

información y la segunda parte es un “enlace”.

Clasificación de las Listas:

• Listas simplemente enlazadas: Cada nodo contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor.

• Listas doblemente enlazadas: Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor.

• Lista circular simplemente enlazada: Una lista enlazada simplemente en la que el último elemento(cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser recorrida de modo circular.

• Lista circular doblemente enlazada: Una lista doblemente enlazada en la que el último elemento se enlaza al primer elemento y viceversa.

Lista Simplemente enlazada

Lista Doblemente enlazada

Lista Circular Simplemente enlazada

Lista Circular Doblemente enlazada

Operaciones en listas enlazadas:

-Insertar elementos en una lista

-Eliminar elementos de una lista

-Recorrido

-Búsqueda

PILAS (Estructuras LIFO (Last-in, first-out))

Una pila es una colección ordenada de elementos a

los que sólo se puede acceder por un único

extremo de la pila. Los elementos de la pila se

añaden o borran de la misma sólo por la parte

superior (cima) de la pila.

Operaciones en una pila:

-CrearPila Inicia

-Insertar (push)

-Quitar (pop)

Las pilas pueden representarse mediante el uso de:

• Arreglos.

• Listas enlazadas.

COLAS (FIFO (First-in, First-out))

Una cola es una estructura de datos cuyos elementos

mantienen un cierto orden, tal que sólo se pueden

añadir elementos por un extremo,final de la cola, y

eliminar o extraer por el otro extremo, llamado

frente.

Operaciones en una cola:

-Inicialización

-Inserción

-Extracción

Cola Lineal: Es un tipo de almacenamiento creado

por el usuario que trabaja bajo la técnica FIFO.

Cola Circular: Son en las cuales existe un

apuntador desde el último elemento al primero de

la cola.

Doble Cola: Es una cola bidimensional en que las

inserciones y eliminaciones se pueden realizar en

cualquiera de los dos extremos de la bicola.

Cola Lineal

Cola Circular

Doble Cola

ESTRUCTURAS NO LINEALES

ARBOLES

Un árbol es una estructura no lineal en la que cada

nodo puede apuntar a uno o varios nodos.

Nodo hijo

Nodo padre

Nodo raíz

Nodo hoja

Características:

-Orden

-Grado

-Nivel

-Altura

Operaciones:

-Añadir o insertar elementos.

-Buscar o localizar elementos.

-Borrar elementos.

-Moverse a través del árbol.

-Recorrer el árbol completo.

Recorridos:

-Pre-Orden

-In-Orden

-Pos-Orden

EJEMPLOS:

GRAFOS

Un grafo es una estructura de datos que consiste en

un conjunto de nodos (también llamados vértices) y

un conjunto de arcos (aristas) que establecen

relaciones entre los nodos.

Se componen de:

-Aristas

-Vertices

-Caminos

Se pueden clasificar en dos grupos: Dirigidos y No

Dirigidos.

Tipos de Grafos:

-Grafo regular

-Grafo bipartito

-Grafo completo

-Grafo nulo

-Isomorfos

REFERENCIAS:

Joyanes Aguilar ,L. (2010). Porgramación en C,C++,Java y UML, McGraw-Hill.

ESTRUCTURA DE DATOS. “Apuntes”. [Fecha de consulta:7 de Octubre 2011].Disponible en: http://upload.wikimedia.org/wikipedia/commons/5/51/APUNTES.pdf

ESTRUCTURAS DE DATOS. [Fecha de consulta:7 de Octubre 2011]. Disponible en: http://c.conclase.net/edd/?cap=007#inicio

GRAFO, Estructura de datos. [Fecha de consulta:7 de Octubre 2011]. Disponible en: http://es.wikipedia.org/wiki/Grafo_(estructura_de_datos)