Arreglos Unidimensionales y Bidimensionales ESTRUCTURAS DE DATOS I Ing. Víctor Andrés Ochoa Correa.

  • Published on
    13-Feb-2015

  • View
    14

  • Download
    14

Embed Size (px)

Transcript

  • Diapositiva 1
  • Arreglos Unidimensionales y Bidimensionales ESTRUCTURAS DE DATOS I Ing. Vctor Andrs Ochoa Correa
  • Diapositiva 2
  • Estructuras de Datos: Conceptos Conjunto de datos de tipos iguales o diferentes que se relacionan entre si y que se pueden operar como un todo. Conjunto de datos de tipos iguales o diferentes que se relacionan entre si y que se pueden operar como un todo. Entero, Real, Carcter, Lgico Datos Simples Hacen referencia a un nico valor a la vez en memoria Datos Estructurados Se refieren a un grupo de casillas de memoria Estticos Dinmicos Arreglos, Registros, Archivos, Cadenas Listas, Arboles, Grafos
  • Diapositiva 3
  • Qu es una Estructura de Datos? Una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulacin. Un dato elemental es la mnima informacin que se tiene en un programa.(ejemplos de datos elementales seran int, float, char,etc) Una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulacin. Un dato elemental es la mnima informacin que se tiene en un programa.(ejemplos de datos elementales seran int, float, char,etc) Lo que se pretende con las estructuras de datos es facilitar un esquema lgico para manipular los datos en funcin del problema que haya que tratar y el algoritmo para resolverlo. Lo que se pretende con las estructuras de datos es facilitar un esquema lgico para manipular los datos en funcin del problema que haya que tratar y el algoritmo para resolverlo.
  • Diapositiva 4
  • Qu es una Estructura de Datos? En algunos casos la dificultad para resolver un problema radica en escoger la estructura de datos adecuada. Y, en general, la eleccin del algoritmo y de las estructuras de datos que manipular estarn muy relacionadas. En algunos casos la dificultad para resolver un problema radica en escoger la estructura de datos adecuada. Y, en general, la eleccin del algoritmo y de las estructuras de datos que manipular estarn muy relacionadas.
  • Diapositiva 5
  • Estructuras de Datos: Implementacin Para implementar alguna estructura de datos, primero es necesario tener muy claro cmo va a ser el manejo de memoria. Para implementar alguna estructura de datos, primero es necesario tener muy claro cmo va a ser el manejo de memoria. La diferencia entre estructuras estticas y dinmicas es el manejo de memoria. La diferencia entre estructuras estticas y dinmicas es el manejo de memoria. Esttica Durante la ejecucin del programa el tamao de la estructura no cambia Dinmica Durante la ejecucin del programa el tamao de la estructura puede cambiar
  • Diapositiva 6
  • Estructuras de Datos Tema: Memoria Esttica Subtema: Conceptos de Arreglos Definicin: Coleccin finita, homogenea y ordenada de elementos. Finita: Porque todo arreglo tiene un lmite. Homogenea: Porque todos los elementos son del mismo tipo. Ordenada: Porque se puede determinar cul es el ensimo elemento. Definicin: Coleccin finita, homogenea y ordenada de elementos. Finita: Porque todo arreglo tiene un lmite. Homogenea: Porque todos los elementos son del mismo tipo. Ordenada: Porque se puede determinar cul es el ensimo elemento. Un arreglo tiene dos partes: Componentes e ndices Un arreglo tiene dos partes: Componentes e ndices C1C1 C2C2....CnCn i0i0 i1i1 inin Componentes ndices Componentes: Hacen referencia a los elementos que forman el arreglo. Componentes: Hacen referencia a los elementos que forman el arreglo. ndices: Permiten referirse a los componentes del arreglo en forma individual. ndices: Permiten referirse a los componentes del arreglo en forma individual.
  • Diapositiva 7
  • Arreglos o arrays? Un arreglo (array) es una coleccin de datos del mismo tipo, que se almacenan en posiciones consecutivas de memoria y reciben un nombre comn.
  • Diapositiva 8
  • Arreglos Para referirse a un determinado elemento de un array se deber utilizar un ndice, que especifique su posicin relativa en el array. Un arreglo es una coleccin finita, homognea y ordenada de elementos.
  • Diapositiva 9
  • Finita:Todo arreglo tiene un lmite; es decir,debe determinarse cul ser el nmero mximo de elementos que podrn formar parte del arreglo. Finita:Todo arreglo tiene un lmite; es decir,debe determinarse cul ser el nmero mximo de elementos que podrn formar parte del arreglo. Homognea: Todos los elementos del arreglo deben ser del mismo tipo. Homognea: Todos los elementos del arreglo deben ser del mismo tipo. Ordenada: Se puede determinar cul es el primer elemento, el segundo, el tercero,.... y el n-simo elmento. Ordenada: Se puede determinar cul es el primer elemento, el segundo, el tercero,.... y el n-simo elmento.
  • Diapositiva 10
  • Los arreglos se clasifican de acuerdo con el nmero de dimensiones que tienen. As se tienen los: Unidimensionales (vectores) Unidimensionales (vectores) Bidimensionales (tablas o matrices) Bidimensionales (tablas o matrices) Multidimensionales (tres o ms dimensiones) Multidimensionales (tres o ms dimensiones)
  • Diapositiva 11
  • Unidimensionales y bidimensionales
  • Diapositiva 12
  • Diapositiva 13
  • Si no existieran los arreglos Suponga que se desea desarrollar un programa para: 1. Leer una lista de calificaciones de un examen 2. Encontrar su media 3. Escribir una lista de las calificaciones mayores que la media 4. Ordenar la lista de las calificaciones en orden ascendente.
  • Diapositiva 14
  • Estructuras de Datos Tema: Memoria Esttica Subtema: Arreglos Unidimensionales Son los arreglos ms simples y constan de un solo ndice, tambien se llaman vectores. Son los arreglos ms simples y constan de un solo ndice, tambien se llaman vectores. Notacin: Podra ser de diferentes maneras. Por ej: Notacin: Podra ser de diferentes maneras. Por ej: Array [0...9] de enteros: Vector Vector: x 1443....4 x0x0 x1x1 x9x9 Componentes ndices X hace referencia a todo el vector, mientras que x 0, o x 1 hace referencia los elementos en forma individual X hace referencia a todo el vector, mientras que x 0, o x 1 hace referencia los elementos en forma individual
  • Diapositiva 15
  • Estructuras de Datos Tema: Memoria Esttica Subtema: Arreglos Unidimensionales Los arreglos se almacenan en forma adyacente, as que su representacin en memoria es: Los arreglos se almacenan en forma adyacente, as que su representacin en memoria es: X 0,Direccin z; X 1,Direccin z+1; X n,Direccin z+n Cada elemento del arreglo se puede procesar como si fuera una variable simple.Ej: Cada elemento del arreglo se puede procesar como si fuera una variable simple.Ej: Suma Suma + x[2] X[2] 15 i3i3 X[i] 15 X[i+2] 15 Sobre los vectores se pueden realizar las siguientes operaciones: Lectura/Escritura, Asignacin, Actualizacin(ins, eli, Mod), Ordenamiento y Bsqueda. Sobre los vectores se pueden realizar las siguientes operaciones: Lectura/Escritura, Asignacin, Actualizacin(ins, eli, Mod), Ordenamiento y Bsqueda.
  • Diapositiva 16
  • Arreglos unidimensionales Estn formados por un conjunto de elementos de un mismo tipo de datos que se almacenan bajo un mismo nombre, y se diferencian por la posicin que tiene cada elemento dentro del arreglo de datos.
  • Diapositiva 17
  • Al declarar un arreglo, se debe inicializar sus elementos antes de utilizarlos. Para declarar un arreglo tiene que indicar su tipo, un nombre nico y la cantidad de elementos que va a contener
  • Diapositiva 18
  • Diapositiva 19
  • Partes de un arreglo Los componentes Los componentes Los ndices Los ndices
  • Diapositiva 20
  • Los componentes. Hacen referencia a los elementos que forman el arreglo, es decir, a los valores que se almacenan en cada una de las casillas del mismo.
  • Diapositiva 21
  • Los ndices. Permiten hacer referencia a los componentes del arreglo en forma individual, especifican cuntos elementos tendr el arreglo y adems, de qu modo podrn accesarse esos componentes.
  • Diapositiva 22
  • Diapositiva 23
  • Operaciones con vectores Lectura/ escritura Lectura/ escritura Asignacin Asignacin Actualizacin (insercin, eliminacin, modificacin) Actualizacin (insercin, eliminacin, modificacin) Recorrido (acceso secuencial) Recorrido (acceso secuencial) Ordenacin Ordenacin Bsqueda Bsqueda
  • Diapositiva 24
  • Sea arre un arreglo de 70 elementos enteros con ndices enteros. Su representacin nos queda:
  • Diapositiva 25
  • Sea bool un arreglo de 26 elementos booleanos con ndices de tipo caracter. Su representacin nos queda:
  • Diapositiva 26
  • Lectura El proceso de lectura de un arreglo consiste en leer y asignar un valor a cada uno de sus elementos. Normalmente se realizan con estructuras repetitivas, aunque pueden usarse estructuras selectivas. Usamos los ndices para recorrer los elementos del arreglo: desde i = 1 hasta 70 hacer leer ( arre[i]) fin_desde
  • Diapositiva 27
  • Escritura Es similar al caso de lectura, slo que en vez de leer el componente del arreglo, lo escribimos. leer (N) desde i = 1 hasta N hacer escribir (arre[i]) fin_desde
  • Diapositiva 28
  • Asignacin No es posible asignar directamente un valor a todo el arreglo; sino que se debe asignar el valor deseado en cada componente. Con una estructura repetitiva se puede asignar un valor a todos los elementos del vector. Por ejemplo: arre[1] =120 (asignacin de un valor constante nico a una casilla del vector) arre[3] =arre[1] / 4 (asignar una operacin)
  • Diapositiva 29
  • Se puede asignar un valor constante a todos los elementos del vector: desde i = 1 hasta 5 hacer arre[i] =3 fin_desde O bien arre =3 (con arre del tipo arreglo)
  • Diapositiva 30
  • Inicializacin Para inicializar con cero todos los elementos del arreglo: desde i = 1 hasta 70 hacer arre[i] 0 desde i = 1 hasta 70 hacer arre[i] 0 fin_desde fin_desde
  • Diapositiva 31
  • Acceso Secuencial (recorrido) El acceso a los elementos de un vector puede ser para leer en l o para escribir (visualizar su contenido). Recorrido del vector es la accin de efectuar una accin general sobre todos los elementos de ese vector.
  • Diapositiva 32
  • Actualizacin Incluye aadir (insertar), borrar o modificar algunos de los ya existentes. Se debe tener en cuenta si el arreglo est o no ordenado. Aadir datos a un vector consiste en agregar un nuevo elemento al final del vector, siempre que haya espacio en memoria.
  • Diapositiva 33
  • Estructuras de Datos Tema: Memoria Esttica Subtema: Arreglos Bidimensionales Estos arreglos constan de dos ndices, tambin se llaman matrices. Estos arreglos constan de dos ndices, tambin se llaman matrices. Notacin: Podra ser de diferentes maneras. Por ej: Notacin: Podra ser de diferentes maneras. Por ej: Array [0...2, 0...2] de enteros: Matriz Matriz: M 344390 012 Componentes Indices 83241 56753 0 1 2 Operaciones: Lectura, Escritura, Asignacin. Operaciones: Lectura, Escritura, Asignacin.
  • Diapositiva 34
  • Arreglo bidimensional Es un conjunto de datos homogneo, finito y ordenado, donde se hace referencia a cada elemento por medio de dos ndices. El primero se utiliza para los renglones (filas) y el segundo para las columnas.
  • Diapositiva 35
  • Tambin puede definirse como un arreglo de arreglos. Internamente en memoria se reservan MxN posiciones consecutivas para almacenar todos los elementos del arreglo. Tambin puede definirse como un arreglo de arreglos. Internamente en memoria se reservan MxN posiciones consecutivas para almacenar todos los elementos del arreglo.
  • Diapositiva 36
  • Declaracin de una matriz