PDF de programación - ESTRUCTURA DE DATOS

Rafael Enrique Cuadro Estrada

ESTRUCTURA DE DATOS

Estructuras de datos es la forma de organizar un conjunto de datos elementales con el objetivo
de facilitar su manipulación. Son objetos que contienen objetos.

Podemos decir que estructura de datos son colecciones de datos que se organizan de una
forma específica, organizada dependiendo de lo que se necesite.









Rafael Enrique Cuadro Estrada

DEFINICIONES DE VARIABLES

Variable: es una entidad donde podemos almacenar datos y posteriormente utilizarlos para
realizar operaciones, una variable como su nombre lo indica tiene un valor cambiante. Las
variables surgieron como alternativa ya que es más fácil manipular los datos mediante estas
que ir cambiando los valores directamente en las celdas de memoria como se hacía
anteriormente en lenguaje ensamblador.

Variables de clase: este tipo de variables son instanciadas de una clase y al ser instanciadas
heredan sus atributos.

Variable de Referencia: este tipo de variables son aquellas que apuntan a una dirección de un
objeto.

Cabe destacar que en la memoria se destacan tres (3) partes muy importantes al ejecutar las
variables inicializadas o declaradas como lo son:

Head: es un espacio donde se encuentran las variables a las cuales se les asigna la posición
de memoria obtenidas por el Stack.

Stack: el Stack es una zona de la memoria en la que se almacenan objetos y variables
primitivas durante la ejecución, (excepto String). La posición donde se almacenaron los datos
se le pasa al head.

Pool: es una zona en la que se almacenan String, y que al igual que en el Stack, la posición
donde se almacenaron los datos se le pasa al head.


Head

Stack

MEMORIA







LENGUAJE DE PROGRAMACIÓN

Pool



Un lenguaje de programación es un lenguaje diseñado para describir el conjunto de acciones
consecutivas que un equipo debe ejecutar. Por lo tanto, un lenguaje de programación es un
modo práctico para que los seres humanos puedan dar instrucciones a un equipo.

 El primer lenguaje de programación fue el Binario.
 Siguió el lenguaje Nemotécnico, que es el lenguaje ensamblador. Es un lenguaje de

nivel medio, se utilizan Palabras como “Sum” para sumar.

 Y luego el lenguaje de alto nivel, visto en nuestros días.



Técnicas de programación: Es la forma que se utiliza para programar.

 Técnica del Espagueti.
 Técnica estructurada.
 Técnica modular.
 Técnica orientada a objetos.

Rafael Enrique Cuadro Estrada

Las estructuras de datos se presentan en gran variedad de acuerdo a varios criterios entre los
cuales encontramos:

Por el recorrido para el acceso a los datos:

 Lineales: presentan los datos unidos en una sola secuencia, su uso es de propósito

general, sobre todo cuando no hay dependencia en sus datos.

 No Lineales: debido a que los datos se encuentran unidos entre por varias secuencias,

generalmente se usan cuando hay dependencia entre un dato y otros.

Por la flexibilidad en su crecimiento:

 Estáticas: porque una vez definidas no pueden cambiar, se usan cuando el volumen

de operaciones sobre sus datos es bajo.

 Dinámicas: porque crecen o decrecen de acuerdo a los requerimientos (Búsqueda,

Inserción y Eliminación) de las operaciones que en este caso serían considerables.

ESTRUCTURAS ESTATICAS Y DINAMICAS

Estructuras Estáticas: son aquellas en las que el tamaño ocupado en memoria se define
antes de que el programa se ejecute, y no puede modificarse dicho tamaño durante la
ejecución del programa.

Su principal característica es que ocupan solo una casilla de memoria, por lo tanto una variable
simple hace referencia a un único valor a la vez. Dentro de este grupo de datos encontramos:
Simples: Char, Integer, Real, Boolean. Compuestas: String, Arreglos, Registros.

En un arreglo todo debe estar de forma contigua.

Estructuras Dinámicas: son una colección de elementos llamados nodos que están conectados
entre sí por enlaces de apuntador (referencias a objetos). Un Nodo es una estructura de datos
que contiene dos campos, un campo que almacena el dato (dato primitivo u objeto) y otro
campo denominado enlace que almacena la referencia al próximo nodo.







Rafael Enrique Cuadro Estrada

De acuerdo a la solución requerida las estructuras de datos se clasificadas en:

 Arreglos: estructuras estáticas, las más veloces en el acceso a sus datos por la
distribución contigua de sus elementos, pero con la desventaja de la rigidez en su
tamaño, su uso es de propósito general.

Un arreglo puede definirse como un grupo o una colección finita, homogénea y ordenada de
elementos. Un Arreglo es una zona de almacenamiento contiguo, que contiene una serie de
elementos del mismo tipo.

Ejemplos:





 Listas enlazadas: estructura dinámica, La distribución esparcida de sus elementos la
hace más lenta en el acceso a los datos que los arreglos, pero tiene la ventaja de
poder crecer y decrecer de acuerdo a los requerimientos de almacenamiento, también
tiene uso de propósito general.

Las listas enlazadas permiten almacenar información en posiciones de memoria que no sean
contiguas. Estas listas para almacenar la información, contienen elementos llamados nodos.
Estos nodos poseen dos campos uno para almacenar la información o valor del elemento y otro
para el enlace que determina la posición del siguiente elemento o nodo de la lista.






Una Lista enlazada es un conjunto lineal de objetos de una clase llamada Nodo. Una lista
Enlazada se accesa por medio de una referencia al primer nodo de la lista, generalmente
llamado cab. Los nodos subsiguientes se accesan por medio del campo de enlace que está
almacenado en cada nodo. Por convención el enlace del último nodo de la lista se establece a
null para marcar el final de la lista.










Rafael Enrique Cuadro Estrada

Para insertar o eliminar información no es necesario realizar un desplazamiento, para esto las
listas cuentan con punteros o enlaces que contienen la posición o dirección del otro nodo de la
lista. Por esta razón no es necesario que los elementos de la lista se almacenen en posiciones
contiguas.



Cuando en una lista enlazada no hay ningún elemento quiere decir que la lista está vacía,
además existe un puntero de cabecera para acceder al primer nodo de la lista y un puntero
nulo para determinar el último elemento (nodo) de la lista. Cuando utilizamos listas enlazadas
podemos realizar las siguientes operaciones:




 Podemos añadir información a la lista insertando un nuevo nodo en un determinado

lugar dentro de la lista.

 Podemos eliminar un nodo específico dentro de la lista que contenga información.
 Podemos recuperar la información almacenada en un nodo específico o encontrar la

posición de un determinado nodo que contenga alguna información específica.


Clasificación

Las listas enlazadas se clasifican en:


 Listas enlazadas simples.
 Listas doblemente enlazadas.
 Listas circular simple.



Listas Enlazadas: las listas enlazadas son unos conjuntos de elementos llamados nodos en
los que cada uno tiene un valor o dato y una dirección que lo enlaza con el siguiente.

Ejemplo:





Listas Doblemente Enlazadas: en las listas enlazadas podemos hacer los recorrido en ambas
direcciones, ya que cada nodo posee una dirección que apunte al anterior y otra al siguiente
nodo que lo acompaña.







Rafael Enrique Cuadro Estrada

Lista Circular Simple: La lista circular es una especie de lista enlazada simple o doblemente
enlazada, pero que posee una característica adicional para el desplazamiento dentro de la lista,
“ésta no tiene fin” para que la lista sea sin fin, el puntero siguiente del último elemento apuntará
hacia el primer elemento de la lista en lugar de apuntar al valor NULL, como hemos visto en el
caso de listas enlazadas simples o doblemente enlazadas
En las listas circulares, nunca se llega a una posición en la que ya no sea posible desplazarse.
Cuando se llegue al último elemento, el desplazamiento volverá a comenzar desde el primer
elemento.




Implementación de una clase Lista







Operaciones en listas enlazadas:

Se dan en listas simples y dobles, en ellas se realizan las siguientes operaciones.

1. Insertar: al inicio, al final, antes de, después de.

2. Eliminar: al inicio, al final, antes de, después de.

3. Buscar para: consultar, modificar, eliminar.

4. Ordenar.













Rafael Enrique Cuadro Estrada

Inserción al Inicio simple

P= new Nodo(dato,dir);

Inserción al Inicio Doble

If (p!=null){
p.setAnt(new NodoDoble(x,null,p));
p=p.getAnt();
}else{
p=new NodoDoble(x,null,null);
}


Inserción al Final simple

if(q!=null){
q.setSig(new Nodo(x,null);
q=q.getSig();
}else
p=q=new Nodo(x,null);
}

Inserción al Final doble

if(q!=null){
q.setSig(new NodoDoble(x,q,null);
q=q.getSig();
}else
p=q=new NodoDoble(x,null,null);
}



Insertar antes de:

 Nodo r = p

Nodo s= null;

while (r! = null && r. getDector()!=x) {

s = r;

r = r.getsig ();

}





if (p!=null){

if(s!= null){

s.setsig(new nodoDoble(y,s,r));

r.setAnt (s.getsig());

} else {

Rafael Enrique Cuadro Estrada

p.setAnt(new nodoDoble(x, null, null));

p=p.getAnt();

}

}

}

Eliminar



if (p! = null) {

r. set sig (new Nodo (y, r. get si()))

if (r == q) {

q = q.getSig();

}

else

system.out.println ("La lista se encuentra