PDF de programación - Estructura de Datos - Apuntes

ESTRUCTURA DE DATOS



“APUNTES”



INTRODUCCION

Como ya sabemos, las computadoras fueron diseñadas o ideadas como una
herramienta mediante la cual podemos realizar operaciones de cálculo
complicadas en un lapso de mínimo tiempo. Pero la mayoría de las
aplicaciones de este fantástico invento del hombre, son las de almacenamiento
y acceso de grandes cantidades de información.
La información que se procesa en la computadora es un conjunto de datos, que
pueden ser simples o estructurados. Los datos simples son aquellos que
ocupan sólo un localidad de memoria, mientras que los estructurados son un
conjunto de casillas de memoria a las cuales hacemos referencia mediante un
identificador único.
Debido a que por lo general tenemos que tratar con conjuntos de datos y no
con datos simples (enteros, reales, booleanos, etc.) que por sí solos no nos
dicen nada, ni nos sirven de mucho, es necesario tratar con estructuras de
datos adecuadas a cada necesidad.
Las estructuras de datos son una colección de datos cuya organización se
caracteriza por las funciones de acceso que se usan para almacenar y acceder
a elementos individuales de datos.
Una estructura de datos se caracteriza por lo siguiente:

-Pueden descomponerse en los elementos que la forman.

-La manera en que se colocan los elementos dentro de la estructura afectará la
forma en que se realicen los accesos a cada elemento.

-La colocación de los elementos y la manera en que se accede a ellos puede
ser encapsulada



UNIDAD I. TIPOS DE DATOS

TIPOS DE DATOS

Definición: El tipo de un dato es el conjunto de valores que puede tomar
durante el programa. Si se le intenta dar un valor fuera del conjunto se
producirá un error.

La asignación de tipos a los datos tiene dos objetivos principales:

• Por un lado, detectar errores en las operaciones
• Por el otro, determinar cómo ejecutar estas operaciones



Un lenguaje fuertemente tipeado es aquel en el que todos los datos deben
de tener un tipo declarado explícitamente, y además que existen ciertas
restricciones en las expresiones en cuanto a los tipos de datos que en ellas
intervienen. Una ventaja de los lenguajes fuertemente tipeados es que se gasta
mucho menos esfuerzo en depurar (corregir) los programas gracias a la gran
cantidad de errores que detecta el compilador.

Clasificaciones en los tipos de datos

Existen muchas clasificaciones para los tipos de datos. Una de estas es la
siguiente:

• Dinámicos
• Estáticos

o El tipo cadena
o Estructurados
o Simples

Ordinales
No-ordinales



Tipos estáticos

Casi todos los tipos de datos son estáticos, la excepción son los
punteros. Que un tipo de datos sea estático quiere decir que el tamaño que
ocupa en memoria no puede variar durante la ejecución del programa. Es decir,
una vez declarada una variable de un tipo determinado, a ésta se le asigna un
trozo de memoria fijo, y este trozo no se podrá aumentar ni disminuír.

Tipos dinámicos.

Dentro de esta categoría entra sólamente el tipo puntero. Este tipo te permite
tener un mayor control sobre la gestión de memoria en tus programas. Con

ellos puedes manejar el tamaño de tus variables en tiempo de ejecución, o sea,
cuando el programa se está ejecutando. Los punteros quizás sean el concepto
más complejo a la hora de aprender un lenguaje de programación.

Tipos simples

Como su nombre indica son los tipos básicos. Son los más sencillos y los más
fáciles de aprender. Los tipos simples más básicos son: entero, lógico, carácter
y real. Y la mayoría de los lenguajes de programación los soportan, no como
ocurre con los estructurados que pueden variar de un lenguaje a otro.

Tipos estructurados

Mientras que una variable de un tipo simple sólo referencia a un elemento, los
estructurados se refieren a colecciones de elementos.
Las colecciones de elementos que aparecen al hablar de tipos estructurados
son muy variadas: tenemos colecciones ordenadas que se representan
mediante el tipo array, colecciones sin orden mediante el tipo conjunto, e
incluso colecciones que contienen otros tipos, son los llamados registros.

Tipos ordinales

Dentro de los tipos simples, los ordinales son los más abundantes. De un tipo
se dice que es ordinal porque el conjunto de valores que representa se puede
contar, es decir, podemos establecer una relación uno a uno entre sus
elementos y el conjunto de los números naturales.
Dentro de los tipos simples ordinales, los más importantes son:

• El tipo entero.
• El tipo lógico.
• El tipo carácter.


Tipos no-ordinales

Simplificando, podríamos reducir los tipos simples no-ordinales al tipo real. Este
tipo nos sirve para declarar variables que pueden tomar valores dentro del
conjunto de los números reales. A diferencia de los tipos ordinales, los no-
ordinales no se pueden contar. No se puede establecer una relación uno a uno
entre ellos y los número naturales. Dicho de otra forma, para que un conjunto
se considere ordinal se tiene que poder calcular la posición, el anterior
elemento y el siguiente de un elemento cualquiera del conjunto.¿Cuál es el
sucesor de 5.12? Será 5.13, o 5.120, o 5.121, ...



UNIDAD II. ESTRUCTURAS SECUENCIALES
INTRODUCCION

Supongamos que nos enfrentamos a un problema como este: Una empresa
que cuenta con 150 empleados, desea establecer una estadística sobre los
salarios de sus empleados, y quiere saber cual es el salario promedio, y
también cuantos de sus empleados gana entre $1250.00 y $2500.00.
Si tomamos la decisión de tratar este tipo de problemas con datos simples,
pronto nos percataríamos del enorme desperdicio de tiempo, almacenamiento y
velocidad. Es por eso que para situaciones de este tipo la mejor solución son
los datos estructurados.
Un arreglo puede definirse como un grupo o una colección finita, homogénea y
ordenada de elementos. Los arreglos pueden ser de los siguientes tipos:

• De una dimensión.
• De dos dimensiones.
• De tres o más dimensiones.

Arreglos Unidimensionales

Un arreglo unidimensional es un tipo de datos estructurado que está formado
de una colección finita y ordenada de datos del mismo tipo. Es la estructura
natural para modelar listas de elementos iguales.
El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir,
podemos acceder a cualquier elemento del arreglo sin tener que consultar a
elementos anteriores o posteriores, esto mediante el uso de un índice para
cada elemento del arreglo que nos da su posición relativa.
Para implementar arreglos unidimensionales se debe reservar espacio en
memoria, y se debe proporcionar la dirección base del arreglo, la cota superior
y la inferior.

REPRESENTACION EN MEMORIA

Los arreglos se representan en memoria de la forma siguiente:
x : array[1..5] of integer



Para establecer el rango del arreglo (número total de elementos) que
componen el arreglo se utiliza la siguiente formula:
RANGO = Ls - (Li+1)
donde:
ls = Límite superior del arreglo
li = Límite inferior del arreglo
Para calcular la dirección de memoria de un elemento dentro de un arreglo se
usa la siguiente formula:
A[i] = base(A) + [(i-li) * w]
donde :
A = Identificador único del arreglo
i = Indice del elemento
li = Límite inferior
w = Número de bytes tipo componente
Si el arreglo en el cual estamos trabajando tiene un índice numerativo
utilizaremos las siguientes fórmulas:
RANGO = ord (ls) - (ord (li)+1)
A[i] = base (A) + [ord (i) - ord (li) * w]



Arreglos Bidimensionales

Este tipo de arreglos al igual que los anteriores es un tipo de dato estructurado,
finito ordenado y homogéneo. El acceso a ellos también es en forma directa por
medio de un par de índices.

Los arreglos bidimensionales se usan para representar datos que pueden verse
como una tabla con filas y columnas. La primera dimensión del arreglo
representa las columnas, cada elemento contiene un valor y cada dimensión
representa una relación
La representación en memoria se realiza de dos formas : almacenamiento por
columnas o por renglones.
Para determinar el número total de elementos en un arreglo bidimensional
usaremos las siguientes fórmulas:



RANGO DE RENGLONES| (R1) = Ls1 - (Li1+1)
RANGO DE COLUMNAS (R2) = Ls2 - (Li2+1)
No. TOTAL DE COMPONENTES = R1 * R2



REPRESENTACION EN MEMORIA POR COLUMNAS



x : array [1..5,1..7] of integer


Para calcular la dirección de memoria de un elemento se usan la siguiente
formula:



A[i,j] = base (A) + [((j - li2) R1 + (i + li1))*w]



REPRESENTACION EN MEMORIA POR RENGLONES



x : array [1..5,1..7] of integer



Para calcular la dirección de memoria de un elemento se usan la siguiente
formula:
A[i,j] = base (A) + [((i - li1) R2 + (j + li2))*w]
donde:
i = Indice del renglón a calcular
j = Indice de la columna a calcular
li1 = Límite inferior de renglones
li2 = Límite inferior de columnas
w = Número de bytes tipo componente


Arreglos Multidimensionales



RANGO (Ri) = lsi - (lii + 1)
No. TOTAL DE ELEMENTOS = R1 * R2* R3 * ...* Rn

Este también es un tipo de dato estructurado, que está compuesto por n
dimensiones. Para hacer referencia a cada componente del arreglo es
necesario utilizar n índices, uno para cada dimensión
Para determinar el número de elementos en este tipo de arreglos se usan las
siguientes fórmulas:


donde:
i = 1 ... n
n = No. total de dimensiones
Para determinar la dirección de memoria se usa la siguiente formula:



LOC A[i1,i2,i3,...,in] = base(A) + [(i1-li1)*R3*R4*Rn + (i2-li2)*R3*R2*... (in - lin)*Rn]*w

Operaciones Con Arreglos

Las operaciones en arreglos p