advertisement

ESTRUCTURAS DE DATOS FUNDAMENTALES

100 %
0 %
advertisement
Information about ESTRUCTURAS DE DATOS FUNDAMENTALES
ing

Published on December 6, 2007

Author: evansbv

Source: slideshare.net

Description

ESTRUCTURAS DE DATOS FUNDAMENTALES
advertisement

ESTRUCTURAS DE DATOS FUNDAMENTALES UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIA PROFESOR: Ing. Evans Balcazar Veizaga

PROFESOR:

Ing. Evans Balcazar Veizaga

Objetivos • Tipos de datos simples int, byte, short, long, double, float, char, boolean • Estructuras de datos fundamentales o básicas: Arrays (arreglos) Conjuntos Ficheros (secuencias) • Estructuras de datos avanzadas Pilas Colas Listas

• Tipos de datos simples

int, byte, short, long, double, float, char, boolean

• Estructuras de datos fundamentales o básicas:

Arrays (arreglos)

Conjuntos

Ficheros (secuencias)

• Estructuras de datos avanzadas

Pilas

Colas

Listas

Contenido : 2.1 LA ESTRUCTURA ARRAY (ARREGLO) 2.1.1 Arrays unidimensionales 2.1.2 Arrays multidimensionales: matrices 2.2 LA ESTRUCTURA CONJUNTO 2.3 LA ESTRUCTURA FICHERO (SECUENCIA) 2.3.1 Texto 2.3.2 Tipeados 2.3.4 Binarios

2.1 LA ESTRUCTURA ARRAY (ARREGLO)

2.1.1 Arrays unidimensionales

2.1.2 Arrays multidimensionales: matrices

2.2 LA ESTRUCTURA CONJUNTO

2.3 LA ESTRUCTURA FICHERO (SECUENCIA)

2.3.1 Texto

2.3.2 Tipeados

2.3.4 Binarios

Arreglos Unidimensionales : NIVEL LÓGICO · Un array o arreglo es una colección finita y de tamaño fijo de elementos homogéneos y ordenados. · El array es una estructura de acceso directo o aleatorio. Se accede directamente a un elemento del array a través del índice de selección.

NIVEL LÓGICO

· Un array o arreglo es una colección finita y de tamaño fijo de elementos homogéneos y ordenados.

· El array es una estructura de acceso directo o aleatorio. Se accede directamente a un elemento del array a través del índice de selección.

Arreglos Unidimensionales : NIVEL LÓGICO · Operaciones básicas: * Constructor: construir(dimension) * Selector: accederElemento ( indiceSelección) El ponedor y selector pueden usarse para: extraer un valor del array modificar el valor de una celda del array · Operaciones complejas: dependen del TipoBase

NIVEL LÓGICO

· Operaciones básicas:

* Constructor:

construir(dimension)

* Selector:

accederElemento ( indiceSelección)

El ponedor y selector pueden usarse para:

extraer un valor del array

modificar el valor de una celda del array

· Operaciones complejas: dependen del TipoBase

Almacenamiento en Memoria : - El array se almacena es posiciones consecutivas de memoria. A la variable referencia se le asocia la dirección del primer elemento del array, denominada dirección base. - Cantidad de espacio que se requiere para almacenar el array: tamañoFisicoArray = numElementos x p p = número de bytes necesarios para almacenar un elemento de tipo TipoBase - Se puede calcular la dirección física del elemento i-ésimo: direccion (nombreArray[indiceSeleccion]) = direccionBase (nombreArray) + (p ´ indiceSeleccion)

Arreglos Bidimensionales : NIVEL LÓGICO · Un array bimensional es un array cuyos elementos son arrays. · Es idéntico al array unidimensional sólo que se necesitarán dos índices que tenga el array. · Operaciones básicas: - Constructor: construirArray (fils, cols) - Selector: accederElemento (indiceSelección1, indiceSelección2)

Arreglos Multidimensionales : NIVEL LÓGICO · Un array multimensional es un array cuyos elementos son arrays. · Es idéntico al array unidimensional sólo que se necesitarán tantos índices como dimensiones tenga el array. Operaciones básicas: - Constructor: construirArray (rangoIndice1, rangoIndice2, ..., rangoIndiceN) - Selector: accederElemento (indiceSelección1, ..., indiceSelecciónN)

Almacenamiento en Memoria : A. La matriz se sigue almacenando es posiciones consecutivas de memoria Opciones: 1. Almacenar por filas 2. Almacenar por columnas - Cantidad de espacio que se requiere para almacenar una matriz: tamañoFisicoMatriz = numFilas x numColumnas x p - Dirección física del elemento i , j :

A. La matriz se sigue almacenando es posiciones consecutivas de memoria

Opciones:

1. Almacenar por filas

2. Almacenar por columnas

- Cantidad de espacio que se requiere para almacenar una matriz:

tamañoFisicoMatriz = numFilas x numColumnas x p

- Dirección física del elemento i , j :

Almacenamiento en Memoria : B. Se almacenan en bloques consecutivos de memoria las direcciones de las filas de la matriz, que a su vez se almacenan como arrays - Cantidad de espacio que se requiere para almacenar una matriz: tamañoFisicoMatriz = numFilas ´ (p’ + numColumnas ´ p) p’ : número de bytes que ocupa una referencia a memoria

Conjunto : NIVEL LÓGICO · Un conjunto matemático C es una colección no ordenada de miembros o elementos de un determinado tipo (T0). · Conjunto potencia (2 C ): conjunto de todos los subconjuntos de T0 · Dado un tipo de conjunto definido sobre un tipo base T0, una variable de ese tipo podrá ser cualquier subconjunto del conjunto potencia de T0

Conjunto : NIVEL LÓGICO · Operaciones básicas: - Constructor : construirConjunto () Selector: no tiene sentido acceder a un elemento del conjunto, sino sólo decir si pertenece o no al mismo · Operaciones complejas: pertenencia, unión, intersección, diferencia, complemento, inclusión, igualdad

NIVEL LÓGICO

· Operaciones básicas:

- Constructor :

construirConjunto ()

Selector:

no tiene sentido acceder a un elemento del conjunto, sino sólo decir si pertenece o no al mismo

· Operaciones complejas:

pertenencia, unión, intersección, diferencia, complemento, inclusión, igualdad

Practica 3 : Realizar la Implementación de la Clase Conjunto, que almacena el TipoBase Char. Data ele:Array[1..MAX_C] of TipoBase; dim:integer Operations setElement, getElement, cantidad, pertenece

Realizar la Implementación de la Clase Conjunto, que almacena el TipoBase Char.

Data

ele:Array[1..MAX_C] of TipoBase;

dim:integer

Operations

setElement, getElement, cantidad, pertenece

Practica 3 : Realizar la Implementación de la Clase Cadena, que administra los caracteres en un vector. Data cad: Array[1..MAX_CxMAX_C] of TipoBase; dim: integer; may, min, sep: Conjunto Operations addChar, insChar, elimChar, interChar, cantChar, getChar, busqChar, invert, toMay, toMin, toTitle, cantPal, insPal, elimPal, cambPal, buscPal, addPal, rotar

Realizar la Implementación de la Clase Cadena, que administra los caracteres en un vector.

Data

cad: Array[1..MAX_CxMAX_C] of TipoBase;

dim: integer;

may, min, sep: Conjunto

Operations

addChar, insChar, elimChar, interChar, cantChar, getChar, busqChar, invert, toMay, toMin, toTitle, cantPal, insPal, elimPal, cambPal, buscPal, addPal, rotar

Ficheros : NIVEL LÓGICO · El fichero es una secuencia almacenada en memoria secundaria . · Los arrays y conjuntos tiene cardinalidad finita, siempre que los tipos sobre los que se definen sean de cardinalidad finita, pero los ficheros son de cardinalidad infinita · En tiempo de compilación no se puede determinar el tamaño del fichero, ya que éste puede crecer/decrecer. · La secuencia es una estructura de cardinalidad infinita .

Ficheros : NIVEL DE IMPLEMENTACIÓN · Tipos de ficheros Ficheros de texto Ficheros de acceso aleatorio (clase RandomAccessFile) Ficheros con tipo (interfaz Serializable)

Ficheros : NIVEL DE IMPLEMENTACIÓN · Operaciones básicas: El acceso a un elemento del fichero dependerá de si éste es de acceso secuencial o directo - Constructor construirFichero () insertarElemento ( elemento) insertarElemento ( elemento, posición) - Selector: seleccionarElemento (nombreFichero) seleccionarElemento (nombreFichero, posición) · Operaciones complejas: recorrido del fichero, determinación del tamaño del fichero, concatenación de ficheros, búsqueda de un elemento.

NIVEL DE IMPLEMENTACIÓN

· Operaciones básicas: El acceso a un elemento del fichero dependerá de si éste es de acceso secuencial o directo

- Constructor

construirFichero ()

insertarElemento ( elemento) insertarElemento ( elemento, posición)

- Selector:

seleccionarElemento (nombreFichero)

seleccionarElemento (nombreFichero, posición)

· Operaciones complejas: recorrido del fichero, determinación del tamaño del fichero, concatenación de ficheros, búsqueda de un elemento.

Ficheros : NIVEL DE APLICACIÓN · Los ficheros se utilizan siempre que es necesario mantener información en memoria secundaria. · La elección de un tipo de fichero u otro depende de la especificación del problema : El fichero de texto sólo permite acceso secuencial y la unidad constitutiva es el carácter. El fichero de acceso aleatorio puede accederse secuencial o aleatoriamente, y está compuesto de bytes. El fichero con tipo permite trabajar con objetos y acceder secuencialmente.

NIVEL DE APLICACIÓN

· Los ficheros se utilizan siempre que es necesario mantener información en memoria secundaria.

· La elección de un tipo de fichero u otro depende de la especificación del problema :

El fichero de texto sólo permite acceso secuencial y la unidad constitutiva es el carácter.

El fichero de acceso aleatorio puede accederse secuencial o aleatoriamente, y está compuesto de bytes.

El fichero con tipo permite trabajar con objetos y acceder secuencialmente.

Ficheros Textos : ARCHIVOS TEXTOS: · Están constituidos por líneas de longitud variables separadas unas de otras por los códigos de retorno y avance de línea Operaciones: Declaración : Var f:text; Asignación : Assign(f,”nombre_archivo.txt”) Apertura : Reset(f); Rewrite(f)

ARCHIVOS TEXTOS:

· Están constituidos por líneas de longitud variables separadas unas de otras por los códigos de retorno y avance de línea

Operaciones:

Declaración :

Var f:text;

Asignación :

Assign(f,”nombre_archivo.txt”)

Apertura :

Reset(f);

Rewrite(f)

Ficheros Textos : ARCHIVOS TEXTOS: Operaciones: Lectura/Escrituras: Readln(f, c) Writeln(f,c) Fin de Línea: Eof(f) Cerrar Archivo: Close(f) Añadir Texto: Append(f)

ARCHIVOS TEXTOS:

Operaciones:

Lectura/Escrituras:

Readln(f, c)

Writeln(f,c)

Fin de Línea:

Eof(f)

Cerrar Archivo:

Close(f)

Añadir Texto:

Append(f)

Practica 4 : Realizar un programa que me permita Crear un Archivo Texto indicandole con un cadena el nombre y dos filas que contendra. Realizar un programa que me permita leer el archivo creado en el ejercicio anterior y me imprima en pantalla.

Realizar un programa que me permita Crear un Archivo Texto indicandole con un cadena el nombre y dos filas que contendra.

Realizar un programa que me permita leer el archivo creado en el ejercicio anterior y me imprima en pantalla.

Ficheros Con Tipo : Archivos con tipo (de acceso directo), contienen una serie de datos accesibles individualmente. · Estos tipos de datos pueden ser simples (enteros, carácter, etc) o estructurados (registros, cadenas, etc) pero no enumerados ni subrango. · Los archivos con tipos están organizados en registros con estructuras fijas. La longitud de un registro corresponde al número de bytes requeridos para almacenar el tipo de datos. · Cuando un archivo se abre, su puntero indica el registro de rango cero, es decir el primer registro. Después de cada operación de lectura o escritura, el puntero de archivo se incrementa en el número de registros leídos o escritos.

Ficheros Con Tipos : Declaración: TYPE Cliente = RECORD Codigo : String[10]; Nombre : String[40]; Direccion : String[30]; Saldo : Real END; VAR f_clie: FILE OF Cliente; r_clie: Cliente;

Declaración:

TYPE

Cliente = RECORD

Codigo : String[10];

Nombre : String[40];

Direccion : String[30];

Saldo : Real

END;

VAR

f_clie: FILE OF Cliente;

r_clie: Cliente;

Ficheros Con Tipos : Operaciones con archivos de acceso directo: – declaración de un archivo – asignación de archivo – apertura de un archivo – registro actual y tamaño de un archivo FileSize, FilePos – posicionamiento en el interior de un archivo Seek – lectura y escritura de archivos Read, Write – fin de archivo – cierre de un archivo

Operaciones con archivos de acceso directo:

– declaración de un archivo

– asignación de archivo

– apertura de un archivo

– registro actual y tamaño de un archivo

FileSize, FilePos

– posicionamiento en el interior de un archivo

Seek

– lectura y escritura de archivos

Read, Write

– fin de archivo

– cierre de un archivo

Practica 5 : Realizar un programa que me permita guardar un registro de persona y luego recuperarlo.

Realizar un programa que me permita guardar un registro de persona y luego recuperarlo.

GRACIAS Estructura de Datos

Add a comment

Related pages

Estructuras fundamentales de Datos | Metodos de ...

Las estructuras de datos se clasifican en: estructuras de datos estáticas y estructuras de datos dinámicas. Las estáticas son las que su espacio ocupado ...
Read more

Estructura de datos - Wikipedia, la enciclopedia libre

Descripción. Las estructuras de datos se basan generalmente en la capacidad de un ordenador para recuperar y almacenar datos en cualquier lugar de su memoria.
Read more

Estructuras Fundamentales De Datos - Prezi

arreglos unidimensionales, bidimensionales y multidimensionales estructuras fundamentales de datos 1-.tipos de datos simples 2-.tipos de datos ...
Read more

ESTRUCTURAS FUNDAMENTALES DE PROGRAMACION

La Lectura/Escritura de datos en un arreglo u operaciones de entrada/salida normalmente se realizan con estructuras repetitivas, aunque puede también ...
Read more

Algoritmos y Estructura de datos. Conceptos fundamentales ...

Algoritmos y estructura de datos Conceptos fundamentales Introducción: ... junto a las estructuras de datos, constituyen la solución de los problemas.
Read more

Ensayo Estructura de Datos | Fer WV - Academia.edu

ESTRUCTURAS FUNDAMENTALES DE DATOS. 1.1 INTRODUCCIÓN. La importancia de las computadoras radica fundamentalmente en su capacidad para procesar ...
Read more

ESTR-ORG-DATOS - FUNDAMENTOS DE ESTRUCTURA DE DATOS

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 ...
Read more

Estructuras Fundamentales - Mis referencias

Un arreglo tiene la característica de que puede almacenar N elementos del mismo tipo, para poder recuperar estos datos se requiere de los indices.
Read more

Lista enlazada - Wikipedia, la enciclopedia libre

En Ciencias de la Computación, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras ...
Read more