Estructuras de datos

1. ESTRUCTURAS DE DATOS I
Conocer, comprender y analizar Conocer, comprender y analizar
algunos de los principales tipos de algunos de los principales tipos de
estructuras de datosestructuras de datos

2. Estructuras de Datos: Conceptos
Conjunto de datos de tipos iguales o Conjunto de datos de tipos iguales o
diferentes que se relacionan entre si y que diferentes que se relacionan entre si y que
se pueden operar como un todo.se pueden operar como un todo.
Entero, Real, Carácter, Lógico
Datos Simples
Hacen referencia a un único valor a la vez en memoria
Datos Estructurados
Se refieren a un grupo de casillas de memoria
Estáticos
Dinámicos
Arreglos, Registros,
Archivos, Cadenas
Listas, Arboles, Grafos

3. Estructuras de Datos: Implementación
Para implementar alguna estructura de datos, Para implementar alguna estructura de datos,
primero es necesario tener muy claro cómo va a primero es necesario tener muy claro cómo va a
ser el manejo de memoria.ser el manejo de memoria.
La diferencia entre estructuras estáticas y La diferencia entre estructuras estáticas y
dinámicas es el manejo de memoria.dinámicas es el manejo de memoria.
EstáticaEstática
Durante la ejecución
del programa el
tamaño de la
estructura no cambia
DinámicaDinámica
Durante la ejecución
del programa el
tamaño de la
estructura puede
cambiar

4. Estructuras de Datos
Tema: Memoria Estática
Subtema: Conceptos de Arreglos
Definición: Colección finita, homogenea y ordenada de Definición: Colección finita, homogenea y ordenada de
elementos. elementos. FinitaFinita: Porque todo arreglo tiene un límite. : Porque todo arreglo tiene un límite.
HomogeneaHomogenea: Porque todos los elementos son del mismo tipo. : Porque todos los elementos son del mismo tipo.
OrdenadaOrdenada: Porque se puede determinar cuál es el enésimo : Porque se puede determinar cuál es el enésimo
elemento.elemento.
Un arreglo tiene dos partes: Componentes e índicesUn arreglo tiene dos partes: Componentes e índices
C
1
C
2
....C
n
i
0
i
1
i
n
Componentes
Índices
ComponentesComponentes: Hacen referencia a los elementos que forman el : Hacen referencia a los elementos que forman el
arreglo.arreglo.
ÍÍndicesndices: Permiten referirse a los componentes del arreglo en : Permiten referirse a los componentes del arreglo en
forma individual.forma individual.

5. Estructuras de Datos
Tema: Memoria Estática
Subtema: Arreglos Unidimensionales
Son los arreglos más simples y constan de un solo Son los arreglos más simples y constan de un solo
índice, tambien se llaman índice, tambien se llaman vectoresvectores..
Notación: Podría ser de diferentes maneras. Por ej:Notación: Podría ser de diferentes maneras. Por ej:
Array [0...9] de enteros: VectorArray [0...9] de enteros: Vector
Vector: xVector: x
1443....4
x
0
x
1
x
9
Componentes
Índices
X hace referencia a todo el vector, mientras que xX hace referencia a todo el vector, mientras que x
00, ,
o xo x
11 hace referencia los elementos en forma hace referencia los elementos en forma
individualindividual

6. Estructuras de Datos
Tema: Memoria Estática
Subtema: Arreglos Unidimensionales
Los arreglos se almacenan en forma adyacente, así que su Los arreglos se almacenan en forma adyacente, así que su
representación en memoria es:representación en memoria es:
X
0
,Dirección z; X
1
,Dirección z+1; X
n
,Dirección z+n
Cada elemento del arreglo se puede procesar como si fuera una Cada elemento del arreglo se puede procesar como si fuera una
variable simple.Ej:variable simple.Ej:
Suma Suma + x[2]
X[2] 15
i 3
X[i] 15
X[i+2] 15
Sobre los vectores se pueden realizar las siguientes operaciones: Sobre los vectores se pueden realizar las siguientes operaciones:
LecturaLectura//Escritura, Asignación, Actualización(ins, eli, Mod), Escritura, Asignación, Actualización(ins, eli, Mod),
Ordenamiento y Búsqueda.Ordenamiento y Búsqueda.

7. Estructuras de Datos
Tema: Memoria Estática
Subtema: Arreglos Bidimensionales
Estos arreglos constan de dos índices, tambien se llaman Estos arreglos constan de dos índices, tambien se llaman
matricesmatrices..
Notación: Podría ser de diferentes maneras. Por ej:Notación: Podría ser de diferentes maneras. Por ej:
Array [0...2, 0...2] de enteros: MatrizArray [0...2, 0...2] de enteros: Matriz
Matriz: MMatriz: M
344390
012
Componentes
Indices
83241
56753
0
1
2
Operaciones:Operaciones: Lectura, Lectura,
Escritura, Asignación.Escritura, Asignación.

8. Estructuras de Datos
Tema: Memoria Estática
Subtema: Registros(Estructuras)
Un registro es una colección de datos, que pueden ser de diferentes Un registro es una colección de datos, que pueden ser de diferentes
tipos. Cada uno de sus elementos se llama tipos. Cada uno de sus elementos se llama CampoCampo..
Notación: Podría ser de diferentes maneras. Por ej:Notación: Podría ser de diferentes maneras. Por ej:
Tipo registro: DomicilioTipo registro: Domicilio
Entero: CalleEntero: Calle
Entero: NumeroEntero: Numero
Cadena: CiudadCadena: Ciudad
Fin TipoFin Tipo
Domicilio: dirDomicilio: dir
El acceso a los campos se hace así: El acceso a los campos se hace así:
variable_registro.id_campovariable_registro.id_campo..
Por Ej: dir.Calle, dir.Numero, dir.Ciudad.Por Ej: dir.Calle, dir.Numero, dir.Ciudad.
NumeroCiudadCalle
Domicilio

9. Estructuras de Datos
Tema: Memoria Estática
Subtema: Arreglos y Registros
Se pueden presentar las siguientes Se pueden presentar las siguientes
combinaciones:combinaciones:
I.I.Arreglos de RegistrosArreglos de Registros: Cada elemento : Cada elemento
del registro es un arreglo.del registro es un arreglo.
Tipo registro: Tipo registro: ClienteCliente
CadenaCadena: : NombreNombre
CadenaCadena: : TeléfonoTeléfono
RealReal: : SaldoSaldo
Fin TipoFin Tipo
Array [0...Array [0...22] de ] de ClienteCliente: : VectorVector
Vector
NTSNTSNTS
0 1 2
Notación:Notación:
Vector[0].NombreVector[0].Nombre

10. Estructuras de Datos
Tema: Memoria Estática
Subtema: Arreglos y Registros
II.II.Registro AnidadoRegistro Anidado: Por lo menos un : Por lo menos un
campo del registro es de tipo registro.campo del registro es de tipo registro.
Tipo registro: DomicilioTipo registro: Domicilio
Entero: CalleEntero: Calle
Entero: NumeroEntero: Numero
Cadena: CiudadCadena: Ciudad
Fin TipoFin Tipo
Tipo registro: Tipo registro: ClienteCliente
CadenaCadena: : NombreNombre
DomicilioDomicilio: : DirecciónDirección
RealReal: : SaldoSaldo
Fin TipoFin Tipo
Cliente
DirecciónDirección
CllNumCiu
Nombre Saldo
Notación:Notación:
Cliente.NombreCliente.Nombre
Cliente.Dirección.CalleCliente.Dirección.Calle

11. Estructuras de Datos
Tema: Memoria Estática
Subtema: Arreglos y Registros
III.III.Registro con ArreglosRegistro con Arreglos: Por lo menos un : Por lo menos un
campo del registro es un array.campo del registro es un array.
Array [0...Array [0...22] de ] de RealReal::VectorVector
Tipo registro: Tipo registro: EstudianteEstudiante
CadenaCadena: : NombreNombre
Cadena: CódigoCadena: Código
VectorVector: : NotasNotas
Fin TipoFin Tipo
Estudiante
NotasNotas
Nombre Código
Notación:Notación:
Estudiante.NombreEstudiante.Nombre
Estudiante. Notas[0]Estudiante. Notas[0]

12. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Apuntadores
Las variables contienen valores especificos, Las variables contienen valores especificos,
las variables apuntador contienen direcciones las variables apuntador contienen direcciones
de memoria de otras variables.de memoria de otras variables.
2
cont
29DC
ptrcont
La variable “ptrcont” La variable “ptrcont”
contiene la dirección contiene la dirección
de memoria de la de memoria de la
variable “cont”variable “cont”
Las variables apuntador estan asociadas a un tipo de dato. Las variables apuntador estan asociadas a un tipo de dato.
Por ej. Si el valor de cont es entero la variable apuntador Por ej. Si el valor de cont es entero la variable apuntador
ptrcont ptrcont debedebe ser de tipo entero. ser de tipo entero.

13. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Apuntadores
OperadoresOperadores: Una variable apuntador responde a dos operadores:: Una variable apuntador responde a dos operadores:

Operando de Dirección(&)Operando de Dirección(&): Que devuelve la dirección de su : Que devuelve la dirección de su
operando. Por ej:operando. Por ej:
Entero Y, *ptryEntero Y, *ptry
YY 55
PtryPtry&Y&Y

Operando de Indirección(*)Operando de Indirección(*): Que devuelve el alias de su operando. : Que devuelve el alias de su operando.
Por ej:Por ej:
Entero Y, *ptryEntero Y, *ptry
YY 55
PtryPtry&Y&Y
Escribir(*Ptry)Escribir(*Ptry)

14. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Asignación de Memoria
Es el proceso por el cual a una estructura, Es el proceso por el cual a una estructura,
sea cual fuere, se le coloca a apuntar una sea cual fuere, se le coloca a apuntar una
variable del mismo tipo y sobre ese variable del mismo tipo y sobre ese
apuntador se reserva o se libera memoria de apuntador se reserva o se libera memoria de
acuerdo a si la estructura crece o decrece.acuerdo a si la estructura crece o decrece.

15. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Conceptos de Listas
Una lista es una colección de elementos, generalmente, Una lista es una colección de elementos, generalmente,
llamados llamados nodosnodos..
En gral un nodo tiene 2 partes:En gral un nodo tiene 2 partes:

Un campo de info que será del tipo de datos que se Un campo de info que será del tipo de datos que se
quiera almacenar en la lista.quiera almacenar en la lista.

Un campo de tipo apuntador que se utiliza para Un campo de tipo apuntador que se utiliza para
establecer un enlace con otro nodo de la lista. Si es el establecer un enlace con otro nodo de la lista. Si es el
ultimo nodo su valor es ultimo nodo su valor es nullnull. Ya no es necesario que los . Ya no es necesario que los
nodos se guarden en forma contigua.nodos se guarden en forma contigua.
ptrcont
5. 7. null

16. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Operaciones con Listas
CrearCrear: Define el primer elemento de la lista.: Define el primer elemento de la lista.
InsertarInsertar: Que coloca nuevos nodos al principio o al : Que coloca nuevos nodos al principio o al
final del nodo dado.final del nodo dado.
RecorrerRecorrer: Que “visita” o “atiende” todos o algunos : Que “visita” o “atiende” todos o algunos
de los nodos de la lista bajo un criterio dado.de los nodos de la lista bajo un criterio dado.
EliminarEliminar: Que borra un nodo dado. Se puede : Que borra un nodo dado. Se puede
eliminar el 1º nodo, el ultimo, el que tenga un info eliminar el 1º nodo, el ultimo, el que tenga un info
x o el anterior o posterior al que tenga una info x.x o el anterior o posterior al que tenga una info x.

17. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Tipos de Listas
Simplemente EncadenadaSimplemente Encadenada
ptrcont
5.7.null
CircularCircular
ptrcont
5. 7.
Doblemente EncadenadaDoblemente Encadenada
ptrcont
7.null.5..
null
Circular Doblemente Circular Doblemente
EncadenadaEncadenada
ptrcont
7..5..

18. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Listas de Acceso Restringido
PilasPilas: : Lista de elementos a la cuál se puede Lista de elementos a la cuál se puede
insertar o eliminar elementos únicamente por uno insertar o eliminar elementos únicamente por uno
de sus extremos.de sus extremos.
Los elementos se eliminan en forma inversa a los Los elementos se eliminan en forma inversa a los
que se insertaron, es decir, el ultimo elemento que que se insertaron, es decir, el ultimo elemento que
ingresa es el primero que se elimina(LIFO).ingresa es el primero que se elimina(LIFO).
Se pueden representar con arreglos o listas.Se pueden representar con arreglos o listas.
ptrcont
5.7.null

19. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Listas de Acceso Restringido
ColasColas: Lista de elementos en la que el : Lista de elementos en la que el
primero en entrar es el primero en primero en entrar es el primero en
salir(FIFO).salir(FIFO).
Se pueden representar con arreglos o Se pueden representar con arreglos o
listas.listas.

20. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Arboles
Son la estructura no-lineal más importante en Son la estructura no-lineal más importante en
computación.computación.
No-lineal porque a cada elemento(nodo) le No-lineal porque a cada elemento(nodo) le
pueden seguir varios elementos(nodos).pueden seguir varios elementos(nodos).
Los arboles AVL(balanceados) son las mejores Los arboles AVL(balanceados) son las mejores
estructuras para trabajar con memoria principal.estructuras para trabajar con memoria principal.
Los arboles B y los BLos arboles B y los B
++
son las mejores son las mejores
estructuras para trabajar en memoria secundaria.estructuras para trabajar en memoria secundaria.

21. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Conceptos de Arboles
Es una estructura jerárquica aplicada sobre una Es una estructura jerárquica aplicada sobre una
colección de elementos llamados colección de elementos llamados nodosnodos. Uno de los . Uno de los
cuales es llamado cuales es llamado raízraíz. .
Además se crea una relación de parentesco entre los Además se crea una relación de parentesco entre los
nodos de forma que hay términos como padre, hijo, nodos de forma que hay términos como padre, hijo,
hermano, antecesor, sucesor, ancestro, etc. Para definir hermano, antecesor, sucesor, ancestro, etc. Para definir
un árbol se necesita recursión.un árbol se necesita recursión.
Se utilizan para representar formulas matemáticas, Se utilizan para representar formulas matemáticas,
organizar información, árboles genealógicos, organizar información, árboles genealógicos,
enumeración de capítulos y secciones de un libro, etc. enumeración de capítulos y secciones de un libro, etc.

22. Estructuras de Datos
Tema: Memoria Dinámica
Subtema: Representación de Arboles
Diagramas de VennDiagramas de Venn : :
A
B
D
I JK
E
C
G
H
L
F
Anidación de paréntesisAnidación de paréntesis : :

(A(B(D(I),E,F(J,K)),C(G,H(L))))(A(B(D(I),E,F(J,K)),C(G,H(L))))