Estructuras primitivas y simples
Estructuras primitivas: No están
compuestas por otras estructuras de datos. Algunos ejemplos son: enteros,
booleanos y caracteres. Otras estructuras de datos se pueden construir de una o
mas primitivas.
Estructuras de datos simples: Se
construyen a partir de estructuras primitivas y son: cadenas, arreglos y
registros.
Estructuras lineales y no lineales
Las estructuras de datos simples
se pueden combinar de varias maneras para formar estructuras mas complejas. Las
dos clases principales de estructuras de datos complejas son las lineales y las
no lineales, dependiendo de la complejidad de las relaciones lógicas que
representan. Las estructuras de datos lineales incluyen pilas, colas y listas
ligadas lineales. Las estructuras de datos no lineales incluyen grafos y
arboles.
-
Estructuras lineales
Una de las estructuras lineales
de datos mas comunes es la pila. Las operaciones que definen una estructura de
datos de tipo pila se presentan para dar paso a la declaración y manipulación
de pilas.
Lista lineal: Es una estructura
de datos formada por un conjunto de elementos ordenados; el numero de elementos
en la lista puede variar. Se puede borrar un elemento o insertar en cualquier
posición de la lista. Asi la lista puede crecer o decrecer al transcurrir el
tiempo.
Pila
Una pila (stack) es un caso
especial de una lista lineal en el cual, la inserción y supresión son
operaciones que solo pueden ocurrir en un extremo de la pila, el cual se
denomina como tope de la pila. Si se meten varios elementos en la pila y
después se sacan de esta, el ultimo elemento en entrar será el primero en
salir. (LIFO: last in first out).
Existen cuatro operaciones
básicas que son validas para el tipo de datos pila:
1. Crear (pila)
2. Está-vacía (pila)
3. Meter (elemento, pila)
4. Sacar (pila)
El operador Crear regresa una
pila vacia con el nombre P. Por definición: Numel (crear(P)) es 0 y Tope
(crear(P)) es nulo.
El operador determina cuando una
pila esta vacia o no. El operando es la pila; el resultado es booleano.
Está-vacía(P) es verdadero si la pila P esta vacia ( si Numel(p) =0) y falso en
caso contrario.
A la operación de añadir un
elemento a la pila se le llama meter a la pila. Meter(E,P), agrega un elemento
E en el tope de la pila P, aumentando de tamaño la pila.
A la operación de remover un
elemento de la pila se le llama sacar de la pila. Sacar(P) remueve un elemento
del tope de la pila P disminuyendo el tamaño de la pila. Si el elemento
extraido debe conservarse se deberá tomar alguna acción antes de la operación
de sacar.
Colas
Es otro caso especial de la
estructura de datos de lista lineal. Mientras que en las pilas se restringe la
adicion y supresión de elementos a través de un solo extremo, llamado tope de
la lista, a las colas se les restringe a que los elementos se supriman por el
frente y se agreguen por atrás.
En una cola la inserción se hace
estrictamente por un extremo de la lista, al cual podemos llamar fondo; la
supresión solo puede hacerse por el otro extremo de la lista, al cual llamamos
frente.
Operaciones de colas
Existen cuatro operaciones
básicas validas para los datos tipo cola:
1. Crear (cola)
2. Está-vacía(cola)
3. Insertar(elemento, cola)
4. Eliminar(cola)
Crear(C) produce una cola vacia
cuyo nombre es C. Por definición:
Numel (crear(C )) es 0
Frente (crear(C )) es indefinido
Fondo (crear(C )) es indefinido.
El operador Esta-vacia (C )
determina si la cola esta o no vacia. El operando es la cola; el resultado es
un valor booleano. Esta-vacia ( C) es verdadero si la cola C esta vacia y falso
en caso contrario.
Insertar (E,C) es el operador que
inserta el elemento E en la cola C. Por definición E es colocado al final de la
cola, el resultado de la operación incrementa la cola. (Fondo es E)
Eliminar ( C), saca el elemento
del frente de la cola C, lo cual produce el decrecimiento de la cola. Si se
debe conservar este primer elemento, se deberá tomar alguna acción antes de la
operación de eliminar.
Listas ligadas
En una línea lineal ligada se
representan elementos unidos mediante nodos. Hay un apuntador para el primer
nodo de la lista, y cada nodo tiene una liga al siguiente nodo. El ultimo nodo
tiene un apuntador NULO, el cual indica que no hay ningún nodo siguiente. Cada
nodo tiene dos secciones: el contenido de datos y el campo del apuntador.
Una lista vacia es aquella que no
contiene nodos. La representación de lista ligada para una lista vacia es solo
un apuntador nulo, al que llamamos “primero”. La operación para crear una lista
vacia es:
Primero := Nulo
Operaciones básicas en una lista ligada
Notacion
Sea P una variable apuntadora,
cuyo valor es una dirección ( la localidad de alguna otra variable). Las
operaciones validas para las variables apuntadoras son las siguientes:
1. Examinar si un apuntador es Nulo
2. Examinar la igualdad con otra variable apuntadora
3. Inicializar con Nulo
4. Asignar a un apuntador la dirección de un nodo.
Estas son las únicas operaciones
que podemos hacer con apuntadores. Denotamos por:
Nodo(P) el nodo apuntado por P;
Info(P) el valor de la porción de información del
nodo apuntado por P;
Sig(P) el valor de la liga del nodo apuntado por
P.
Remocion de nodos
El algoritmo para remover de una
lista ligada el nodo que sigue al apuntado por P, donde Q es un apuntador
auxiliar usado para apuntar al nodo que debe ser removido, es el siguiente:
a) Q:= Sig(P)
b) Sig(P) := Sig(Q)
c) Liberar el espacio del nodo apuntado por Q para
reusarlo.
Insercion de un nodo
El algoritmo para insertar el
contenido de una variable NOMBRE en una lista ligada, de tal forma que siga al
nodo apuntado por P es el que sigue. Nuevamente se utiliza el apuntador
auxiliar Q y otro mas llamado NUEVO.
a) Asignar espacio para el nuevo nodo y hacer que NUEVO
apunte a este.
b) Info(NUEVO) := NOMBRE
c) Q:= Sig(P)
d) Sig(P) := NUEVO
e) Sig (NUEVO) :=Q
ESTRUCTURAS DE DATOS NO LINEALES
En estas estructuras cada
elemento puede tener varios elementos “siguientes”, lo cual introduce el
concepto de estructuras de ramificación. Estas estructuras de datos de
ramificación son llamadas grafos y arboles.
Un grafo es un conjunto de puntos
y un conjunto de líneas, con cada línea se une un punto a otro. Los puntos se
llaman los nodos del grafo, y las líneas se llaman aristas. Un grafo nulo es un
grafo con orden cero.
Una arista esta determinada por
los nodos que conecta. Un grafo esta completamente definido por sus conjuntos
de nodos y aristas. La posición real de estos elementos en la pagina no tiene
importancia. Algunas aristas pueden conectar un nodo a si mismo, a estas aristas se les llama bucles.
Un grafo G se llama grafo simple
si las siguientes condiciones son validas.
1. No tiene ciclos (no existe una arista en E de la forma
(v,v), donde V esta en V)
2. No hay mas de una arista uniendo un par de nodos, esto
es, no existe mas de una arista en E de la forma (v1,v2),
para cualquier par de elementos v y v en VG
Un grafo que no es simple algunas
veces es llamado multígrafo. Encontrara, que a las aristas también se les conoce
como arcos y a los nodos como vértices.
Un grafo conexo es una grafica
que no se puede dividir en dos graficas, sin eliminar por lo menos una de las
aristas.
Trayectorias
Una trayectoria en un grafo es
una secuencia de una o mas aristas que conecta a dos nodos. La longitud de la trayectoria es el numero de
aristas que la componen.
Ciclos
Un ciclo es una trayectoria sobre
la cual se cumple con las siguientes dos condiciones:
1. Ninguna arista puede aparecer mas de una vez en una
secuencia de aristas.
2. El nodo inicial de la trayectoria es el mismo que el
nodo terminal. (P(v,v)).
Un grafo sin ciclos se dice que
es aciclico.
Grafos dirigidos
En el grafo dirigido se les
asigna dirección a las aristas de la grafica. Cada arista del grafo dirigido
incluye una flecha para indicar la dirección.
El grado interno de un nodo en un
grafo es el numero de aristas que terminan en ese nodo; el grado externo de un
nodo, es el numero de aristas que salen de ese nodo. El grado de un nodo es la
suma de sus grados internos y externos.
ARBOLES
Un árbol es un grafo conexo,
simple y aciclico. Un árbol no contiene
ni ciclos ni bucles; existe una sola arista entre cualquier par de
nodos.
Arboles Generales
Un árbol se dice que esta
enraizado si tiene un nodo (llamado raíz), el cual se distingue de los demás
nodos. La raíz del árbol T es denotada por raíz (T).
1. Hay un nodo especialmente designado llamado Raiz
2. Los nodos restantes son particionados en >= 0
conjuntos disjuntos, llamados T1, T2, …, TM tales que, cada Ti es por si mismo
un árbol. Estos conjuntos son llamados subarboles de la Raiz. Un árbol sin
nodos es un árbol nulo.
La raíz de un árbol no esta
simplemente seleccionaa de manera aleatoria; mas bien es un nodo que se distingue
por la propiedad de:
Grado interno (v) = 0
para v = Raiz(T)
La raíz no tiene ramificaciones
de entrada. Debido a que un árbol es un grafo conexo, no puede haber mas de un
nodo con esta propiedad.. Una colección de arboles enraizados se llama bosque.
Arboles Binarios
Un árbol binario es un conjunto
finito de nodos, el cual puede ser vacio o, puede contener un par de arboles
binarios disjuntos, que son llamados subárbol izquierdo y subárbol derecho.
Se dice que dos arboles binarios
son similares si tienen la misma estructura.
Los arboles binarios se
representan frecuentemente por listas ligadas. Cada nodo puede tener tres
campos elementales: un area de información y los apuntadores a los subarboles
izquierdo y derecho.
Estructura de datos y
organización de archivos – Mary E. S. Loomis - 2da edición
