UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS

Universidad del Perú, DECANA DE AMÉRICA

FACULTAD DE INGENIERÍA DE SISTEMAS E INFORMÁTICA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA DE SISTEMAS

CURSO:
ESTRUCTRA DE DATOS

PRESENTADO POR:
LUZMILA ELISA PRÓ CONCEPCIÓN

ESCUELA ACADÉMICO PROFESIONAL DE

INGENIERÍA DE SISTEMAS

ABRIL 2018
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

INTRODUCCIÓN A LA ESTRUCTURA DE DATOS

CONTENIDO:

 Definición de estructura de datos

 Clasificación de la estructura de datos
 Operaciones con estructura de datos
 Definición de lenguaje y pseudocódigo
 Formalismo y abstracción de problemas y soluciones
 Análisis de Pre Condiciones (entrada)
 Análisis de Post Condiciones (salida)
 Archivos secuenciales: Noción de archivos secuenciales. Acciones
primitivas de acceso. Algoritmos Básicos. Ejemplos.
 Concepto de Algoritmia: manejo de secuencias.

Introducción a la estructura de Datos

Definición de Estructura de Datos (ED)

Son una forma de organizar los datos según métodos de acceso.

Se le define también como un modelo matemático o lógico de una organización
particular de datos.
La estructura de datos no es un objeto pasivo sino que dependerá de las
operaciones que se han de ejecutar sobre ellas. La elección de un algoritmo y
de la Estructura de datos está estrechamente vinculada a la búsqueda de formas
de ahorrar tiempo y espacio de memoria mediante una elección adecuada.
Para construir o desarrollar una aplicación se realiza según los siguientes pasos:
(1) formulación del problema, (2) especificación de la solución, hasta (3) la
implantación de un programa.
Durante este proceso se evalúan las estructuras de datos más adecuados y los
algoritmos correspondientes.

Objetivos de la ED

Descripción lógica y matemática de la estructura.

Implantación de las estructuras de datos de un computador.
Análisis cuantitativo de la estructura que incluye el cálculo de la memoria
necesaria para su almacenamiento y el tiempo necesario para optimizarla.

2
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Clasificación de la estructura de datos

La estructura de datos según algunos criterios se clasifica en:

 ED Lineales:
o Archivos secuenciales
o Arreglos
o Listas Enlazadas
o Pilas
o Colas

 ED No Lineales:
o Grafos
o Árboles

Las estructuras de datos lineales (ED Lineales) son aquellas en las que sus
elementos se encuentran en secuencia lineal, de tal forma que para cada
elemento, excepto el último elemento siempre existe un sucesor y para todo
excepto el primer elemento existe un antecesor.
Las estructuras de datos no lineales (ED No Lineales) son estructuras de datos
complejas pero facilitan su desarrollo o aplicación a los problemas se basan en
las estructuras de datos lineales.

La clasificación, teniendo en cuenta la permanencia en la memoria:

 ED Físicas:
o Filas: permanecen en almacenamiento secundario
o Arreglos: permanecen en almacenamiento principal

 ED Abstractas:
o Listas, Pilas y Colas (almacenamiento principal)
o Árboles y Grafos (almacenamiento principal)

Las estructuras de datos físicas son aquellas que tienen existencia física propia
en almacenamiento. Las estructuras abstractas pueden construirse e
implementarse en base a las estructuras físicas o lineales como son los arreglos,
filas secuenciales, listas enlazadas, pilas, y colas.

La clasificación, teniendo en cuenta el tamaño o longitud de la estructura:

 ED Estáticas:
o Arreglos

 ED Dinámicas:
o Listas, Pilas y Colas
o Árboles y Grafos

3
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Las estructuras de datos estáticas no cambian de longitud durante la ejecución

del programa, mientras que las dinámicas varían en tamaño.

Utilidad de las estructuras de datos

Es muy conveniente utilizar en el desarrollo de problemas un Modelo Formal

pues una vez formalizado puede buscarse las soluciones respectivas en función
del modelo preciso y determinar módulos que puedan reutilizarse.

Ejemplo:
Un Vector es una ED Física de tipo Estática y Lineal, mientras que los árboles
son No Lineales, dinámicas y abstractas.

Operaciones con estructuras de datos

Los datos contienen una estructura de datos (ED) que se procesa mediante
operaciones.

Creación: consiste en definir la ED para su posterior utilización.

Recorrido: Consiste en recorrer cada elemento de la ED por única vez.
Búsqueda: Consiste en la localización de un elemento determinado de la ED.
Inserción: Consiste en añadir un elemento en una posición determinada de la
ED.
Eliminación: Consiste en eliminar un elemento de la ED.
Ordenación: Consiste en clasificar los elementos de la ED, de acuerdo a un
orden lógico.
Mezcla: Consiste en ordenar 2 ED en una tercera.

4
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Resolución de problemas

Dado un problema presentado en el mundo real para ello existen una o más
soluciones.
Un algoritmo es una solución (una idea) que surge como respuesta a un
problema.
La resolución de un problema sigue las siguientes fases:

Problema  Algoritmo  Pseudocódigo  Programa

Esta solución puede ser presentada en forma algorítmica como una secuencia
finita de pasos.
El algoritmo existe en nuestra memoria por tanto es algo subjetivo.
Para poder trasladar al mundo informático una solución se requiere presentarla
en forma objetiva en un lenguaje que abstraiga subjetividades. Por lo tanto, un
algoritmo debe presentarse en forma objetiva y para lo cual se utilizará
herramientas de comunicación como los denominados Pseudocódigos o los
Diagramas de Flujo.
A partir del Pseudocódigo o Diagrama de Flujo podemos construir los programas
que finalmente servirán para ejecutar en el computador.

Especificación de un problema

Programar una solución no solo es codificar el programa. Es también hallar una

solución (o algoritmo) y especificar la solución y luego implementarla a la
solución.
Especificar equivale a hacer la pregunta:
¿Qué hace el programa?
No interesan detalles de cómo sería el programa
Implementar consiste en responder a la pregunta:
¿Cómo se consigue la función pretendida?

La especificación de un algoritmo puede orientarse a dos tipos de usuarios:

Usuarios del algoritmo:
La especificación para este tipo de usuario debe incluir todo lo necesario
para el uso correcto de los programas, así como las obligaciones del
usuario cuando invoque o llame al algoritmo.
Implementador del algoritmo (programador):
La especificación para este tipo de usuario debe incluir las restricciones
que el implementador debe considerar en el programa.

5
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Una solución mal especificada producirá un programa que no satisface el

requerimiento del programa planteado.

Un algoritmo (programa): es una secuencia finita de pasos (instrucciones) para

resolver el problema. Se puede asociar a cada paso un estado.
Se denomina estado inicial al estado antes de que inicie la ejecución del
algoritmo, mientras el estado final es el estado en el que el problema está
resuelto.

Pre Condición y Post Condición

La técnica de Pre/Post Condición se basa en considerar un algoritmo como una

caja negra en la que se nos permite observar los parámetros de entrada y los de
salida.
El algoritmo funciona como una máquina de estados finitos, en la que el estado
inicial está descrito por el valor de los parámetros de entrada y después de hacer
una transición por los demás estados en un tiempo que no es relevante para la
especificación, se llega al estado final en el que los parámetros de salida
contienen los resultados esperados.
El programa se especifica mediante 2 aserciones:
Pre condición: Condición de los datos de entrada.
Post condición: Condición de los datos de salida.

La Pre condición especifica los requisitos de los datos de entrada para que
funcione correctamente.
La Post condición establece las características de los resultados en función de
los datos de entrada.

Si A es la Pre condición, B es la Post condición y P es el algoritmo, entonces la

notación {A}P{B} representa la especificación de P, y se lee:
Si P comienza su ejecución en un estado descrito por la precondición A,
P termina y lo hace en un estado descrito por B.

Ejemplo:

Realizar la especificación de un algoritmo para hallar el cociente por

defecto y el módulo de dos enteros:

Entrada: a: dividendo
b: divisor
Salida: q: cociente
r: modulo

6
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

La especificación de la interface es la siguiente:

FUN divide(a,b:entero) DEV(q,r:entero)

La Pre condición debe considerar lo siguiente:

1: excluye los estados en la que el dic visor es cero
2: sumando el resto y el producto del cociente por el divisor debe dar el
dividendo

En el algoritmo a especificar puede estar las siguientes:

Pre condición: A≡{B≠0}

B≡{a=b*q+r}

Una implementación que satisface A y B sería:

P: q=0
r=a

El algoritmo no calcula lo esperado. Indica que no se especificó bien el algoritmo.

Otra especificación mejorada:

Pre condición: A≡{(a≥0)˄(b≥0)}

Post condición: A≡{(a=b*q+r)˄(r≥0)˄(r<b)}

a y b existen, son dos números naturales que satisfacen los requerimientos para
q y r.

7
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Abstracción

El concepto de abstracción se aplica a múltiples situaciones diferentes como por

ejemplo el aprendizaje.
La abstracción permite concentrarse en lo general y no en el detalle, esto
simplifica el análisis y lo centra en lo más relevante.

Clases de abstracción:

 De procedimientos
 De abstracción de datos

La abstracción cumple un rol muy importante en el análisis y diseño de sistemas

informáticos. Permite determinar la estructura de los sistemas que se van a
implementar y tener una mejor visión de su funcionamiento real.

Ejemplo:
Supongamos que se quiere hallar el área del triángulo, se lee la base y la
altura, se calcula el área y luego se muestra el área.

Se abstrae el hecho de que tanto la base como la altura sean de tipo real
o entero y se les considera como números.

En ED realizaremos abstracción de soluciones algorítmicas a los problemas.

Modularidad

Modularidad es el otro concepto clave en Algorítmica.

La modularidad permite separar la solución del problema en unidades
funcionales, permitiendo mediante la abstracción que se determinen los
procesos u operaciones necesarias para dar solución a un problema.
La modularidad ofrece ventajas como la reutilización de módulos ya construidos.

8
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Tipos de datos, Estructura de datos (ED) y

Tipos Abstractos de datos (TDA)

Estos tres conceptos son conceptos diferentes.

Tipo de datos: Es un conjunto de valores que puede tomar una variable definida
de ese tipo

Ejemplo:
Si declaramos: Int A
Estamos definiendo la variable A de tipo entero, es decir que A puede tomar
cualquier valor del conjunto de los enteros.

Tipos de datos (básico): Varían de un lenguaje a otro.

Estructura de Datos: Es un conjunto de variables que pueden ser de distintos

tipos conectados entre sí de diversas formas.
Ejemplo:
Los apuntadores en las Listas.
La estructura de datos tiene una existencia física propia en donde predomina el
concepto de celda o recipiente que son referenciados por Direcciones o Índices
(arreglos o archivos).

Tipo Abstracto de Datos (TDA): Es un modelo matemático abstracto, junto con

las operaciones definidas sobre este modelo, que tienen que ser implementados
sobre otra estructura.
Un TDA puede encapsular tanto los tipos de datos como las operaciones,
generando un nuevo tipo de dato (TDA) que puede tratarse como un tipo de dato
primitivo.

Algoritmo

Un algoritmo es una solución a un problema que se define como una secuencia

finita de pasos perfectamente definidos que conducen a la solución de un
problema.
Algoritmo viene del siglo IX: alkowarizmi
Algoritmia: es el estudio de algoritmos. Es la ciencia que permite evaluar el efecto
de diferentes factores externos sobre algoritmos existentes, de tal forma que se
pueda seleccionar el que más se ajuste a los requerimientos particulares.

9
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Características del algoritmo

Finito: Debe ser finito, sino no tendría un final.

Entrada: Tiene 0 a más entradas.
Salida: Tiene por lo menos una Salida.
Definido: Si se ejecuta 2 veces debe producir el mismo efecto o resultado.
Natural: Debe ser escrito en lenguaje natural (humano), está orientado hacia la
persona, no hacia la máquina.

Un algoritmo es una solución a un problema que al codificarlo en algún lenguaje

de programación es un programa. Cada paso del algoritmo corresponde a una
instrucción del programa.
Programa: Es una secuencia de instrucciones que se suministra al computador
para que se ejecute alguna de las siguientes funciones:

 Recibir datos
 Ejecutar cálculos
 Almacenar datos
 Tomar decisiones de carácter lógico
 Proporcionar resultados

Pseudocódigo: Es la escritura que permite pasar del algoritmo (Idea) a un

código entendible por el mundo informático.
El pseudocódigo debe ser independiente de la máquina en la que se ejecutará
el programa. Esto significa que el programador debe expresar su idea en
lenguaje natural sin tener que ver ningún lenguaje de programación.

Esquema de un pseudocódigo

Acción nombre_acción(lista de parámetros)

Inicio
Secuencia de tratamientos
Fin

Acciones y funciones

La lógica del diseño de algoritmos consiste en resolver un problema dividiendo

en partes o subproblemas de forma que cada una de estas partes tenga una
solución específica.

La solución mayor corresponde a un algoritmo, las soluciones parciales

corresponden a subalgoritmos.

Algoritmo es una secuencia de pasos y al ser dividido en módulos es decir que

serán un subconjunto de pasos o módulos del algoritmo mayor.

10
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Modulo también es denominado subprograma respecto del programa principal.

En programación, cada uno de estos módulos es llamado Acción o Función.

Acciones

Llamados procedimientos en la mayoría de los lenguajes de programación.

Acción nombre_acción(lista de parámetros)
Inicio
Secuencia de tratamientos
Fin
Funciones
Función Nombre_Función (lista de parámetros)
Inicio
Secuencia de Tratamientos
Retornar (valor de Retorno)
Fin

En una función el valor de retoro regresa en el nombre de la función. Como el

nombre de la función es único, por tanto solo puede retornar un valor.
En una acción o procedimiento, estos pueden no devolver resultados como
variables en la lista de parámetros, por otro lado los valores de retorno no tiene
relación con el nombre del procedimiento.
Las funciones pueden utilizarse en expresiones de asignación, de comparación
o aritméticas.
Además pueden considerarse como variable, cuyo valores dependen de los
argumentos que se le sean pasados o transferidos. Estas se utilizan cuando se
quiere identificar claramente el resultado de la función. En el caso de las
acciones, estos no puede utilizarse en expresiones de asignación, de
comparación o aritméticas, a lo sumo una acción devuelve una variable que
puede ser utilizada en expresiones de asignación, de comparación o aritméticas.

Predicado

Predicado es una función que devuelve un resultado booleano, es decir devuelve

dos valores que puede ser Verdadero o Falso.
Este valor es devuelto en el nombre de la acción.
Predicado nombre_predicado (lista de parámetros)
Inicio
Secuencia de Tratamientos
Retornar (valor de retorno)
Fin

Ejemplo:

11
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Acción Verifica () Predicado primo (X)

Inicio Inicio
Leer N //si X es primo
Si (Primo(N)) Retornar Verdad
Escribir N, “es primo” //si no es primo
Sino Retornar Falso
Escribir N, “no es primo” Fin
Fin Si
Fin
El Predicado primo (X) recibe como parámetros la variable X. Verifica el valor de
X, devolviendo Verdad, y si no X no es primo, devolverá Falso.

La Acción Verifica: Escribe el mensaje N “es primo”, o N “no es primo”

dependiendo del valor de retorno del Predicado primo (X).

Ejemplo:
Función Suma (x,y) Acción ASUM (x,y,z)
Inicio Inicio
S=x+y z=x+y
Retornar(S)z Fin
Fin

Acción SUMA ()
Inicio
Leer n1
Leer n2
Escribir FSUM (n1, n2) //Escribe el valor de retorno
de la función FSUMA
ASUMA (n1, n2, n3) //Llama a la acción ASUMA
Escribir n3 //Escribe el valor de n3 devuelto
por la acción ASUMA
Fin

Tratamiento de resultados

La Estructura de Datos (ED) a elegir va a depender de las operaciones que se

deseen implementar sobre ellas. Las operaciones se desarrollan como
tratamientos a datos de entrada y producción de resultados. La resolución de
todo problema está caracterizado por tres elementos:

 Dato
 Tratamiento
 Resultados

12
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Tipos de resultados

 Resultado incondicional
 Resultado condicional
 Lista de resultados
Resultado incondicional: se obtiene de manera incondicional
Resultado condicional: se obtiene dependiendo de la verificación de la
condición.
Lista de resultados: se obtiene mediante un tratamiento iterativo. Es decir un
mismo tratamiento aplicado a un conjunto de datos diferentes pero homogéneos.

Tipos de tratamiento

 Tratamiento secuencial
 Tratamiento condicional
 Tratamiento iterativo

Existe una correspondencia biunívoca entre los resultados y los tratamientos.

Tratamiento secuencial ↔ Resultado incondicional

Tratamiento condicional ↔ Resultado condicional
Tratamiento Iterativo ↔ Lista de resultados

Tratamiento secuencial

Cada tratamiento puede contener sentencias de asignación de la forma:

ASIGNACIÓN
Forma General:

Id ← Expresión

13
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

o tratamientos más complejos (condicional o iterativo o repetitivo)

En una sentencia de asignación el identificador Id se escribe siempre al lado

izquierdo de la asignación que puede ser un valor constante, una variable o una
expresión aritmética o lógica siempre que se escribe a la derecha del símbolo de
asignación.

Tratamiento condicional

Forma General:

Si Condición entonces hacer Tratamiento 1

Fin Si

Si Condición entonces hacer Tratamiento 1

Sino entonces hacer Tratamiento 2

Fin Si

La condición es una expresión lógica que al evaluarse retorna un valor verdadero

o Falso, en cuyo caso se ejecutará el tratamiento 1 o el tratamiento 2
respectivamente.

Estos tratamientos consisten en una secuencia de tratamientos de cualquier tipo,

es decir puede incluir un tratamiento secuencial, condicional o iterativo. Esta
definición permite definir un tratamiento como una secuencia de tratamientos.

Tratamiento iterativo

Forma General:

Mientras Condición hacer Tratamiento

Fin hacer

Este tratamiento consiste de un ciclo Condición a la entrada. El tratamiento se

ejecutará siempre que la condición sea Verdadera. Si la Condición no resultara
Verdadera no se ejecutará el Tratamiento y continúa la ejecución del ciclo
Mientras.

Tratamiento iterativo

Tratamiento Repetir

14
SESIÓN 1: Introducción a la Estructura de datos Facultad de Ingeniería de Sistemas e Informática
Mg. Luzmila Pró Concepción EAP: Ingeniería de Sistemas
2008 – I
______________________________________________________________________________________________

Forma General:

Repetir Tratamiento

Hasta Condición
Este Tratamiento consiste de un ciclo con condición de
salida. El Tratamiento se ejecutará siempre que la condición sea falsa. Si la
condición resulta Verdadera termina el ciclo y continua la ejecución fuera del
ciclo Repetir.

Tratamiento Para

Forma General:

Para I desde VI hasta Tratamiento (VF)

Este tratamiento consiste de un ciclo que se repetirá tantas veces como lo

indique contador. Desde el valor inicial del contador de 1 en 1 hasta llegar al
valor final indicado.

15