estructuras de datos

EEssttrruuccttuurraass ddee DDaattooss AAllggoorriittmmoo II

IInngg.. RRuutthh FFiigguueerrooaa ddee FFlloorreess

1

DEFINICIÓN:

Los datos estructurados llamados también estructuras de datos

es una colección o conjunto de datos simples que tiene el

mismo nombre.

El valor de la estructura de datos se determina por:

1. El valor de los elementos.

2. La composición de los elementos

TIPOS DE ESTRUCTURAS DE DATOS:

Estáticas

Array

Vectores

Matrices

Registros

Ficheros o archivos

Dinámicas

Lineales

No lineales

Pila

Colas

Listas enlazadas

Árboles

Grafos

ESTRUCTURAS DE DATOS



2

DEFINICIÓN:

Son aquellos en los que el tamaño ocupado en la memoria se define

antes de que el programa se ejecute y no puede modificarse dicho

tamaño durante la ejecución del programa. Ejemplo de ello son los array

(Arreglos).

ARRAYS (ARREGLOS):

Un array (arreglo, vector o lista, tabla o matriz ) es una estructura de

datos utilizada para almacenar un conjunto de datos.

Un array se identifica : por su nombre y se asocia con un nombre de

variable valido.

Los componentes individuales de un array se llaman : elementos y

se distinguen entre ellos por el nombre del array seguido de uno o

varios índices o subíndice entre paréntesis o corchetes.

Los elementos de un array se almacenan en la memoria de la

computadora ( un elemento por Posición ).

LOS ARRAY SE CLASIFICAN EN:

Unidimensionales o Lineales (vectores o listas)

Bidimensionales (tablas o matrices)

ARREGLOS ESTÁTICOS



3

DEFINICIÓN:

Se define como un conjunto finito, homogéneo y ordenado de datos. Finito: Todo vector tiene un límite; es decir debe determinarse cual

será el número máximo de elementos que podrán formar parte del

vector.

Homogéneo: Esto significa que todos los elementos del vector serán

del mismo tipo (todos enteros, todos reales, todos booléanos etc.)

Ordenado: Se puede determinar cual es el primer elemento, el

segundo, el tercero y así sucesivamente hasta el enésimo elemento.

También el orden es significativo, el orden viene dado por el subíndice

de un vector.

Los índices son números enteros o expresiones enteras que

generalmente inician con 1 pero, dependiendo del lenguaje pueden

iniciar con 0 u otro valor.

EJEMPLO:

Vector sueldo:

Sueldo(1) Sueldo(2) Sueldo(3) Sueldo(4) Sueldo(10)

$150 $500 $600 $1000 ........................................ $2000

Primer Elemento

Segundo Elemento

Tercer Elemento

Cuarta Elemento

Décimo elemento

ELEMENTOS

ARREGLOS-VECTORES



4

PRESENTACIÓN:

Los vectores se pueden representar como filas de datos o columnas de

datos, los elementos del vector sueldo de 10 elementos se representa de

la siguiente manera.

Sueldo(1) $150

EL

EM

EN

TO

S

Sueldo(2) $500

Sueldo(3) $1000

ELEMENTOS

Sueldo(4) $1500 4 12 3 0 7 14

........

........

K(1) K(2) K(3) K(4) K(5) K(6)

Sueldo(10) $2000

COLUMNA FILA

DECLARACIÓN DE VECTORES:

Así. Para declarar el vector sueldo de 10 elementos se haría de la

siguiente manera.

Palabra reservada Para declara un vector

Nombre del vector

Tamaño

Tipo de datos

DIM Sueldo(10) : Real



5

OPERACIONES CON VECTORES:

Las operaciones con vectores se pueden realizar con elementos

individuales o sobre vectores completos mediante las instrucciones

básicas y estructuras de control.

Sea el vector sueldo de 10 elementos:

Dim sueldo(10): Real // Crea la estructura llamada sueldo con

10 casillas de memoria y guardará

datos de tipo real.

Haciendo analogía con la memoria quedaría así:

Sueldo(1) Sueldo(2) Sueldo(3) Sueldo(4) Sueldo(10)

$150.50 $520.7 $600 $1000 … $2000

1 2 3 4 … 10

Diferentes operaciones con el vector sueldo considerando el

subíndice de I = 2

Operaciones sobre elementos

Operaciones sobre vector completo

Asignación Recorrido

Lectura Búsqueda

Escritura Inserción

Eliminación

índices



6

INSTRUCCIÓN (ACCIÓN) EFECTO

Imprimir sueldo( I ) Visualiza 520.7 (valor de sueldo( 2 ))

Imprimir sueldo(I + 1) Visualiza 600 (valor de sueldo( 2+1 ))

Imprimir sueldo( I – 1 ) + 50 Visualiza 200.50 (valor de sueldo( 1 )+50)

Imprimir sueldo( I ) + 100 Visualiza 620.7 (valor de sueldo( 2 )+100)

Sueldo(I – 1 ) = Sueldo(I ) Asigna 520.7 a Sueldo(1)

Sueldo( I ) = Sueldo(I + 1 ) Asigna 600 a Sueldo(2)

Sueldo( I ) = Sueldo (11) Instrucción errónea ya que I > 10 y esa

casilla de memoria no ha sido declarada

LECTURA Y ESCRITURA DE VECTORES COMPLETOS.

Para poder realizar operaciones con el vector completo se tiene que

hacer uso de estructuras repetitivas tales como mientras, desde o

repetir.

LLENAR EL VECTOR SUELDO.

Desde I = 1 hasta 10 hacer Leer sueldo( I ) Fin-desde

I = 1 Mientras I <= 10 hacer Leer Sueldo( I ) I = I + 1 Fin-mientras

ESCRITURA DEL VECTOR SUELDO.

Desde I = 1 hasta 10 hacer Imprimir sueldo( I ) Fin-desde

I = 1 Mientras I <= 10 hacer Imprimir Sueldo( I ) I = I + 1 Fin-mientras



7

OPERACIONES CON ARREGLOS:

Las operaciones en la que intervienen los arreglos son:

1. Lectura /Escritura.

2. Asignación.

3. Actualización:

a) Inserción.

b) Eliminación.

c) Modificación.

4. Ordenación.

5. Búsqueda.

LECTURA:

El proceso de lectura de un arreglo consiste en leer y asignar

un valor a cada uno de sus elementos. Supóngase que se

desea leer todos los elementos del arreglo ARRE.

PSEUDOCÓDIGOS

Desde I = 1 hasta N hacer

Leer ARRE ( I )

Fin_desde

I = 1

Repetir I desde 1 hasta N hacer

Leer ARRE ( I )

I = I +1

Fin_desde



8

ESCRITURA:

El caso de la escritura es similar al de la lectura. Se debe

escribir el valor de cada uno de los componentes. Supóngase

que se desea escribir los primeros N componentes del arreglo

ARRE en forma consecutiva. Los pasos a seguir son los

siguientes:

PSEUDOCÓDIGOS


Escribir ARRE ( I )

Fin_desde

I = 1


Escribir ARRE ( I )

I = I +1

Fin_desde

ASIGNACIÓN:

En general no es posible asignar directamente un valor a todo el

arreglo; sino que se debe asignar el valor deseado a cada

componentes.

PSEUDOCÓDIGOS


ARRE ( I ) = 0

Fin_desde

I = 1


ARRE ( I ) = 0

I = I +1

Fin_desde



9

ACTUALIZACIÓN

Pueden insertarse nuevos elementos, eliminar y/o modificar

algunos de los ya existentes. Para llevar acabo estas

operaciones eficientemente se debe tener en cuenta si el arreglo

está o no ordenado.

a. ARREGLOS DESORDENADOS.

Consideramos un arreglo A de 100 elementos como el

presentado.

A

. . .

. . .

1 2 3 N N+1 100

a.1. INSERCIÓN:

Para insertar un elemento Y en un arreglo A desordenado debe verificarse que existe espacio. Si se cumple esta condición, entonces se asignará a la posición N + 1 el nuevo elemento. A continuación presentamos el diagrama de flujo correspondiente.

EXPLICACIÓN DE LAS VARIABLES:

N : ENTERO // Almacena el número actual de elementos del arreglo.

Y : ENTERO // Representa el valor que se va a insertar.

A : ENTERO // Arreglo unidimensional. Su capacidad máxima es de 100 elementos.



10

PSEUDOCÓDIGO:

Insertar_Desordenado Inicio

Var Entero: N, Y

Dim A(100) : Entero Si N < 100 entonces

Leer Y N = N+1 A(N) = Y

Sino Imprimir “ No hay espacio para insertar el elemento Y”

Finsi

Fin

A

Y . . .

. . .

1 2 3 N N+1 100

a.2. ELIMINACIÓN: Para eliminar un elemento X de un arreglo A desordenado debe verificarse que el arreglo no esté vacío y que X se encuentre en el arreglo. Si se cumple estas condiciones entonces se procederá a recorrer todo los elementos.



X : ENTERO // Representa el valor que se va a eliminar.


I : ENTERO // Se utiliza como variable de control del ciclo externo y como índice del arreglo.

K : ENTERO // Se utiliza como variable de control del ciclo interno y como índice del arreglo A.

BAND : BOOLEANA // Se inicializa en falso. Cambia su valor a verdadero si se encuentra el elemento a eliminar en el arreglo, en cuyo caso se interrumpe el ciclo.



11

PSEUDOCÓDIGO:

Eliminar_Desordenado Inicio

Var Entero: N, X, I, K,

Booleana : BAND

Dim A(100) : Entero

Si N >= 1 entonces Leer X I = 1 BAND = FALSO

Mientras ( I <= N ) and ( BAND = FALSO ) hacer Si A(I) = X entonces

BAND = VERDADERO N = N – 1 Desde K = I hasta N hacer

A(K) = A(K+1) Findesde

Sino I = I + 1

Finsi Finmientras

Si BAND = FALSO entonces

Imprimir “ El elemento”, X, “no está en el arreglo” Finsi

Sino Imprimir “ El arreglo A está vacío”

Finsi

Fin

A

. . .

. . .

1 2 3 N - 1 N N + 1 100



12

a.3. MODIFICACIÓN:

Para modificar un elemento X por un elemento Y, de un arreglo A

que se encuentra desordenado debe verificarse que el arreglo no

esté vacío y que X se encuentre en el arreglo. Si se cumplen estas

condiciones entonces se procederá a su actualización. Puede

observarse que existen tareas comunes con la operación de

eliminación:

Determinar que el arreglo no esté vacío.

Encontrar el elemento a modificar (eliminar).



X : ENTERO // Representa el valor que se va a modificar.


I : ENTERO // Se utiliza como variable de control del ciclo y como índice del arreglo.

K : ENTERO // Se utiliza como variable de control del ciclo interno y como índice del arreglo A.

BAND : BOOLEANA // Se inicializa en falso. Cambia su valor a verdadero si se encuentra el elemento a

modificar en el arreglo, en cuyo caso se interrumpe el ciclo.

Y : ENTERO // Representa al elemento que se introduce y modifica al elemento X.



13

PSEUDOCÓDIGO:

Modificar_Desordenado Inicio

Var Entero: N, X, I, K, Y

Booleana : BAND

Dim A(100) : Entero



Leer Y A(I) = Y

BAND = VERDADERO Sino

I = I + 1 Finsi

Finmientras



Sino

Imprimir “ El arreglo A está vacío” Finsi

Fin

A

Y . . .

. . .

. . .

1 2 3 I N N + 1 100



14

b. ARREGLOS ORDENADOS.

Considerando el arreglo ordenado A de 100 elementos, de la figura

siguiente. Los primeros N componentes del mismo tienen asignado un

valor. En este caso se trabajará con un arreglo ordenado de manera

creciente, es decir:

A(1) <= A(2) <= A(3) <= ... <= A(N)

A

. . .

. . .

1 2 3 N N+1 100

Cuando se trabaja con arreglos ordenados debe evitarse alterar el

orden al insertar nuevos elementos o al modificar los existentes.

b.1. INSERCIÓN:

Para insertar un elemento X en un arreglo A que se encuentra

ordenado, debe verificar que existe espacio.

Luego tendrá que encontrarse la posición en la que debería

estar el nuevo valor para no alterar el orden del arreglo.

Una vez detectada la posición, se procederá a recorrer todos

los elementos desde la misma hasta la N-ésima posición, un

lugar a la derecha.

Finalmente se asignará el valor X en la posición encontrada.

(Los pasos del recorrido no se llevan a cabo cuando el valor a

insertar es mayor que el último elemento del arreglo.)



15

Generalmente, cuando se quiere hacer una inserción debe

verificarse que el elemento no se encuentre en el arreglo. En la

mayoría de los casos prácticos no interesa tener información

duplicada, por lo tanto si el valor a insertar ya estuviera en el

arreglo, la operación no se llevaría a cabo.

Debemos señalar que tanto en los procesos de inserción y

eliminación en arreglos ordenados es recomendable tener un

procedimiento que busque el elemento X en el arreglo ordenado.

Este procedimiento dará como resultado la posición en la que se

encuentra el elemento X (en cuyo caso el elemento ya pertenece

al arreglo y por lo tanto no debemos insertarlo) o el negativo de la

posición en la que debería estar.


N : ENTERO // Almacena el número actual de elementos

del arreglo.

X : ENTERO // Representa el elemento que se va a insertar (si no se encuentra en el arreglo).


I : ENTERO // Se utiliza como variable de control del ciclo. En el módulo BUSCAR, detecta además la posición donde se encuentra o debería estar el elemento X. Es utilizado también como índice del arreglo.

POS : ENTERO // Almacena la posición donde se encuentra o debería estar el elemento X..



16

PSEUDOCÓDIGO:

Insertar_Ordenado Inicio

Var Entero: N, X, I, POS

Dim A(100) : Entero

Si N < 100 entonces

// INICIO DEL MÓDULO BUSCAR Leer X I = 1 Mientras ( I <= N ) and ( A(I) < X ) hacer

I = I + 1 Finmientras Si ( I > N ) OR ( A(I) > X ) entonces

POS = -1 Sino

POS = 1 Finsi // FIN DEL MÓDULO BUSCAR

// INICIO DEL MÓDULO INSERTAR Si POS > = entonces

Imprimir “ El elemento ya existe” Sino

N = N + 1 POS = POS * (-1)

I = N Repetir I desde N hasta (POS +1) hacer

A(I) = A(I - 1) I = I - 1

Finrepetir A(POS) = X

Finsi // FIN DEL MÓDULO INSERTAR

Sino Imprimir “ No hay espacio en el arreglo para nuevas inserciones”

Finsi

Fin



17

A

Y . . .

. . .

. . .

1 2 3 I N N + 1 100

Inserción en arreglo ordenado.

b.2. ELIMINACIÓN:

Para eliminar un elemento X en un arreglo ordenado A debe

verificarse que el arreglo no esté vacío. Si se cumple esta

condición, entonces tendrá que buscarse la posición del

elemento a eliminar.

Si el resultado del módulo BUSCAR es un valor positivo, quiere

decir que el elemento se encuentra en el arreglo y por lo tanto

puede ser eliminado.

En otro caso no se puede ejecutar la operación.



X : ENTERO // Representa el elemento que se va a eliminar (si se encuentra en el arreglo).


I : ENTERO // Se utiliza como variable de control del ciclo. En el módulo BUSCAR, Almacena además la posición donde se encuentra o debería estar el elemento X. Es utilizado también como índice del arreglo.




18

PSEUDOCÓDIGO:

Eliminar_Ordenado Inicio

Var Entero: N, X, I, POS

Dim A(100) : Entero

Si N > 0 entonces // INICIO DEL MÓDULO BUSCAR Leer X I = 1

Mientras ( I <= N ) and ( A(I) < X ) hacer I = I + 1

Finmientras Si ( I > N ) OR ( A(I) > X ) entonces

POS = -1 Sino

POS = 1 Finsi // FIN DEL MÓDULO BUSCAR // INICIO DEL MÓDULO ELIMINAR Si POS < 0 entonces

Imprimir “ El elemento no existe” Sino

N = N - 1 I = POS Repetir I desde POS hasta N hacer

A(I) = A(I + 1) I = I + 1

Finrepetir Finsi // FIN DEL MÓDULO INSERTAR

Sino

Imprimir “ El arreglo esta vacío ” Finsi

Fin



19

A

. . .

. . .

1 2 3 N - 1 N 100

Eliminación en arreglo ordenado.

b.3. MODIFICACIÓN:

Se procede de manera similar a la eliminación de un elemento en un arreglo ordenado. La variante se presenta en que al modificar el valor X por un valor Y, debe verificarse que el orden, entonces debería reordenarse al arreglo, o bien eliminar primero el elemento a modificar e insertar posteriormente el elemento nuevo.



X : ENTERO // Representa el valor que se va a modificar.


I : ENTERO // Se utiliza como variable de control del ciclo. En el módulo BUSCAR, Almacena además la posición

donde se encuentra o debería estar el elemento X. Es utilizado también como índice del arreglo.


BAND : BOOLEANA // Se inicializa en falso. Cambia su valor a verdadero si se encuentra el elemento a modificar en el arreglo, en cuyo caso se interrumpe el ciclo.

Y : ENTERO // Representa al elemento que se introduce y modifica al elemento X.



20

PSEUDOCÓDIGO:

Modificar_Ordebado Inicio

Var Entero: N, X, I, POS, Y

Booleana : BAND

Dim A(100) : Entero



Leer Y A(I) = Y

BAND = VERDADERO Sino

I = I + 1 Finsi

Finmientras



// INICIO DEL MÓDULO ELIMINAR Si POS < 0 entonces

Imprimir “ El elemento no existe” Sino

N = N - 1 I = POS

Repetir I desde POS hasta N hacer A(I) = A(I + 1) I = I + 1

Finrepetir Finsi // FIN DEL MÓDULO INSERTAR

Sino



21

Imprimir “ El arreglo esta vacío ” Finsi

Fin

Sino

Imprimir “ El arreglo A está vacío” Finsi

Fin



22



23

EJEMPLOS:

1. Supóngase que se conoce el sueldo de 50 trabajadores de

una empresa. Utilizar éstos datos para generar el promedio

de sueldos de la empresa y la cantidad de empleados que

tienen sueldo abajo del promedio y cantidad de empleados

que tienen sueldo arriba del promedio. Al final imprimir los 50

salarios y la información generada.

2. Hacer un algoritmo mediante el cual se llene un vector con

50 edades y posteriormente que lo imprima.



24

3. Haga un algoritmo que determine las edades mayores a la

media aritmética en un conjunto de edades. Cuantas edades

están arriba de la media.

4. Hacer un algoritmo que determine de un vector general de

100 edades otro vector con las edades menores que la

media.

5.

ARREGLO BIDIMENCIONAL:

Es un conjunto de datos homogéneo, finito y ordenado, donde se hace

referencia a cada elemento por medio de dos índices. El primero de los

índices se utiliza generalmente para indicar filas y el segundo para

indica columna.

EJEMPLO:

ARRAYS BIDIMENCIONALES

<MATRICES>



25

M (2 , 3) se refiere al elemento de la segunda fila, tercera

columna. En nuestro caso contiene 18

Fila 1

Fila 2 18

Fila 3

Fila 4

Fila 5

Fila 6

Columna 6

Columna 5

Columna 4

Columna 3

Columna 2

Columna 1

PRESENTACIÓN DE LA MATRIZ:

El arreglo A(M x N) tiene M filas y N columnas.

Un elemento A(I,J) estará en la fila I, y en la columna J. Internamente

en memoria se reservan M x N posiciones consecutivas para almacenar

todos los elementos del arreglo.

1 2 … J … N

1

2

…

I A(I , J)

…

M



26

Donde,

I = 1, … , M O bien 1<= I <= M

J = 1, … , N 1<= J <= N

DECLARACIÓN DE VECTORES:

Para declarar la matriz notas de 20 alumnos y 5 asignaturas se haría de

la siguiente manera. Matriz = Arreglo (1…20, 1…5) de reales.

OPERACIONES CON ARREGLOS BIDIMENCIONALES:

Las operaciones que pueden realizar con arreglos bidimensionales son:

6. Lectura /Escritura. 7. Asignación. 8. Actualización:

a) Inserción. b) Eliminación. c) Modificación.

9. Ordenación. 10. Búsqueda.

LECTURA:

Cuando se introdujo la lectura en arreglos unidimensionales se dijo que

se iban asignar valores a cada uno de los componentes. Lo mismo

sucede con los arreglos bidimensionales. Sin embargo, como sus

Palabra reservada Para declara un vector

Nombre del vector

Fila Columna

Tipo de datos

DIM notas(20 , 5) : Real



27

elementos deben referenciarse por medio de dos índices, normalmente

se usan dos ciclos para lograr la lectura de elementos consecutivos.

Supóngase que desea leer todos los elementos del arreglo

bidimensional MATRIZ. Los pasos a seguir son los siguientes:

PSEUDOCÓDIGO

Desde I 1 hasta 15 hacer

Desde J 1 hasta 5 hacer

Leer MATRIZ ( I , J )

Fin_desde

Fin_desde

I 1 Repetir I desde 1 hasta 15 hacer J 1 Repetir J desde 1 hasta 5 hacer Leer MATRIZ ( I , J ) J J+1 Fin_desde I I +1 Fin_desde

LECTURA:

La escritura de un arreglo bidimensional también se lleva acabo elemento

por elemento. Supóngase que se quiere escribir todos los componentes

del arreglo MATRIZ. Los pasos a seguir son los que se muestran a

continuación:

PSEUDOCÓDIGO



escribir MATRIZ ( I , J )

Fin_desde

Fin_desde

I 1 Repetir I desde 1 hasta 15 hacer J 1 Repetir J desde 1 hasta 5 hacer escribir MATRIZ ( I , J ) J J+1 Fin_desde I I +1 Fin_desde

ASIGNACIÓN:



28

La asignación de valores a un arreglo bidimensional puede realizarse de

dos maneras diferentes, según el número de componentes involucrados.

1. A todos los elementos del arreglo: en este caso se necesitarán dos ciclos para recorrer todo el arreglo.

PSEUDOCÓDIGO



MATRIZ ( I , J ) 0

Fin_desde

Fin_desde

I 1 Repetir I desde 1 hasta 15 hacer J 1 Repetir J desde 1 hasta 5 hacer MATRIZ ( I , J ) 0 J J+1

Fin_desde I I +1 Fin_desde

2. A un elemento en particular del arreglo: en este caso la asignación

es directa.

Documents

estructuras de datos