Clase10-Vectores_2011

ARREGLOSTeoría – Alejandro Héctor González

Temas

Estructura de datos arreglo

Definición

Operaciones

Ejemplos

Arreglos - Características

Posición basePosición base

AA

BB

CC

11 22 33 5544INDICE

Estructura de datos-ARREGLO-Concepto

Suponga que se requiere procesar la información referida a ventas de diferentes sucursales (en total 4) de un supermercado. Para ello, se leen de teclado las cantidades PARCIALES vendidas por las diferentes sucursales. No hay garantía de que la información venga ordenada por sucursal. Se debe obtener como resultado, aquellas sucursales que superan el promedio vendido.


Por ejemplo:

SUC 3 12.000

SUC 1 5.500

SUC 4 15.500

SUC 1 7.500

Promedio: 56.000/4 = 14000

Las sucursales 3 y 4 superan el promedioSUC 2 7.500

SUC 3 8000

SUC 1 13.000

SUC 2 7.500

SUC 3 20.000

SUC 4 15.500


Podríamos leer desde teclado y tener cuatro variables, una para cada sucursal y de acuerdo, a la sucursal leída sumar con el totalizador correspondiente. Luego, se tiene que calcular el promedio y analizar para cada variable totalizador si lo supera o no


Para resolver estos problemas podemos usar una estructura de datos tipo arreglo.

Un arreglo (ARRAY) es una estructura de datos que permite acceder a cada componente a través de una variable índice, que da la posición de la componente dentro de la estructura de datos.

Un tipo de dato Arreglo es una colección indexada de elementos.

Estructura homogénea: los datos que almacena son del mismo tipo.

Estructura estática: su tamaño no varía al agregar o sacar elementos de la misma.

Estructura indizada: permite recuperar cualquier elemento del arreglo indicando su posición (índice).


¿Qué es el índice de un arreglo?


Es una variable de tipo ordinal.Permite acceder a cualquier elemento de manera directa.

Representa un desplazamiento desde la posición inicial del arreglo

Arreglos - Conceptos Un tipo de dato Arreglo es una colección indexada

de elementos.

HomogéneaHomogénea Acceso directoAcceso directoindexadoindexado

EstáticaEstática

LinealLineal

Uso de la memoria

Organización de los datos

Forma de accesoDatos que puede almacenar

Estructura de datos Arreglo

12001200 300300 50005000 250250

Índice: I

12001200

300300

50005000

250250

Memoria RAM

A012

A013

A014

A015

Vector: Sucursales

Dimensión física: 4 elementos en total

Los representamos habitualmente

en forma horizontal

Estructura de datos Arreglo

12001200 300300 50005000 250250

Índice: I es un subrango 1..4

Vector: Sucursales

¿Qué valor hay en Sucursales [3]?

Los corchetes se utilizan para mencionar la posición del

vector que va a ser

accedida


En el ejemplo de las sucursales….12.000 5.500 15.500 7.500 12.500 4.000 3.700

Arreglo de Ventas (VS)

VS[3] Índice del

arreglo

1 2 3 500….


Del ejemplo anterior … El nombre de la variable tipo arreglo lleva asociado un área de memoria fija consecutiva ( del tamaño especificado en la declaración ), que es el lugar donde se almacenarán los valores.

La variable índice, sirve para ubicar ó direccionar rápidamente las componentes del arreglo.

Estructura de datos-ARREGLO-ConceptoCuando trabajamos con arreglos se debe tener en cuenta…Declaración del tipo arreglo.

La utilización del índice del arreglo.

El acceso al contenido del arreglo.

Dimensión física y lógica del arreglo.

Operaciones permitidas con los arreglos.

Program uno; type sucursales= array[rango] of tipo;

integercharbooleanenumerativo

Estructura de datos-ARREGLO-Declaración

integercharbooleanenumerativorealregistros

Subrangos de tipos ordinales


EJEMPLO

Program uno; type sucursales= array [1..7] of integer;


EJEMPLO

Según la dimensión del arreglo se los denomina de diferentes maneras:1 Dimensión: VECTORES2 Dimensiones: MATRICES3 Dimensiones: TENSORESN Dimensiones: ARREGLO N-DIMENSIONAL;

OPERACIONES CON VECTORES

•Asignar elementos.•Lectura/escritura.•Recorridos.•Agregar elementos.•Insertar elementos.•Borrar elementos.•Búsqueda de un elemento.•Ordenación de un arreglo.

Estructura de datos-ARREGLO-Operaciones

Estructura de datos-ARREGLO- Asignar elementos

Program uno; type sucursales= array [1..7] of integer; var VS: sucursales; begin VS[6]:= 7.200;

? ? ? ? ? ? ?

? ? 15.200 ? ? ? ?

VS[3]:= 15.200;? ? 15.200 ? ? 7.200 ?


Program uno; type sucursales= array [1..7] of integer; var VS: sucursales; x,i:integer; begin

? ? ? ? ? ? ?

100 2.500 15.200 7563 4570 23.564 0

for i:= 1 to 7 do

read (x); VS[i]:= x;


Program uno; type sucursales= array [1..7] of integer; var VS: sucursales; x,i:integer; begin

? ? ? ? ? ? ?

for i:= 1 to 7 do

read (x); VS[i]:= x;

for i:= 1 to 7 do

read (vs[i]);

Estructura de datos-ARREGLO-Ejercicio

Suponga que se leen las lluvias de cada día del mes de enero, y se quiere obtener aquellos días en que las lluvias superan el promedio del mes.


Program Ejemplo1; type lluvias= array [1..31] of real; var enero: lluvias; i:1..31;begin CargarLluvias (enero); prom: = promedio(enero); For i:= 1 to 31 do If (enero [i] > prom) then writeln (‘El día ’, i, ‘supera el promedio del mes’); end.


Procedure CargarLluvias (var enero:lluvias); For i:= 1 to 31 do readln(enero[i]); end.

? ? ? ? ? ? ?

1 2 3 4 ….. 30 31


Suponga que se requiere procesar la información referida a ventas de diferentes sucursales (CAMBIAMOS EL PROBLEMA ORIGINAL – AHORA 7 SUCURSALES) de un supermercado. Para ello, se leen de teclado las cantidades PARCIALES vendidas por las diferentes sucursales. No hay garantía de que la información venga ordenada por sucursal. Se debe obtener como resultado, aquellas sucursales que superan el promedio vendido.

Estructura de datos-ARREGLO-EjercicioProgram uno; type codigosuc= 0..7; ventas= record suc: codigosuc; cantvendida: integer; end; sucursales= array [1..7] of integer; var VS: sucursales;i: 1..7;Begin InicializarSucursales(VS); {Es un módulo que pone cada posición del vector en cero} CargarVentas (VS); prom: = promedio(VS); For i:= 1 to 7 do If (VS [i] > prom) then writeln (‘La sucursal ’, i, ‘supera el promedio’); end.

Estructura de datos-ARREGLO- Ejercicio

Queda para el alumno la implementación de los proceso leer e InicializarSucursales de este EjercicioProcedure CargarVentas (var suc:sucursales); var i:integer; v: ventas; begin leer (v); {Es un módulo que hace un read de cada campo del registro v} While (v.suc <>0) do {consideramos que seguro en v.suc viene cargado un número entre 0 y 7} Begin suc[v.suc]:=suc[v.suc]+ v.cantvendida; leer (v); End; end;

Estructura de datos-ARREGLO- Recorridos

Recorrido completo.

Recorrido condicional.

Arreglos: Recorridos Esta operación consiste en recorrer el vector

total o parcialmente.

Por ejemplo si nos piden saber la cantidad de veces que figura el valor 23 en un vector de 100 componentes, habrá que recorrerlo completo, contando las apariciones del 23:

Arreglos: Recorrido Total Program REC-TO23;

Const DIMF= 100; Type rango= 1..DIMF; vector = array [ 1..DIMF ] of integer ; Var a: vector; J : rango; Can23 : integer ; Begin Can23 := 0; For J := 1 to DIMF do {cargando datos en cada componentes del vector} Read ( A [ J ] ) ; For J := 1 to DIMF do { recorrido total del vector} If ( A [ J ] = 23 ) then Can23 := Can23 + 1; Writeln ( ´Veces que aparece 23´, Can23 ); end.

Arreglos: Recorrido Condicional

Ejemplo: Encontrar la posición del primer cero en un vector de 1000 componentes, sabiendo que por lo menos existe un cero.

Es claro que en este caso no conviene hacer un recorrido total del vector, pues nos piden la posición del primer cero sabiendo que existe al menos uno.


Program POSCE;Const DIMF=1000;Type rango= 1..DIMF; vector = Array [ 1..DIMF] of real; Var A: vector; J : rango; Begin CargarVector(A); J := 1; { Recorre el vector hasta encontrar el cero} While ( A [ J ] <> 0 )do J := J + 1; Writeln ( ´La posición es : ´, J ) ; End.

Esto debiera modificarse en caso que no me aseguren que el cero está seguro

Esto debiera modificarse en caso que no me aseguren que el cero está seguro


Program POSCE;Const DIMF=1000;Type rango= 1..DIMF+1; vector = Array [ 1..DIMF] of real; Var A: vector; J : rango; encontre:boolean; Begin CargarVector(A); { Se considera que el vector se carga en todas las posiciones} encontre:=false; J := 1; { Recorre el vector hasta encontrar el cero o hasta que se acabe el vector} While ( not encontre) and (J<=DIMF )do If (A [J] = 0) then encontre:= true else J := J + 1; If encontre then Writeln ( ´La posición es : ´, J ) ; End.

Arreglos: dimensiones...

Cuando se trabaja con arreglos se deben hacer consideraciones importantes acerca de algunos aspectos:

Dimensión Física del arregloDimensión Lógica del arregloArreglos como parámetros

DIMENSIÓN FÍSICA Y LÓGICA DEL VECTOR

Supongamos que se quiere cargar una estructura que permita almacenar números enteros hasta leer el número 99. Al finalizar la carga se pide calcular el mínimo numero leído. Se sabe que a lo sumo son 10000 números.

Estructura de datos-ARREGLO - Ejercicio

Dimensión física

Dimensión lógica

Estructura de datos-ARREGLO – Dim Física

Program tres; Const Dim= 10000 type numeros = array [1..Dim] of integer; var nume: numeros;

Dimensión física Dimensión

lógica

¿Hasta cuando cargo el vector?

Estructura de datos-ARREGLO – Dim Física-Lógica

Program cuatro;Const DIMF=10000 Type rango=0..DIMF; numeros = array [1..DIMF] of integer; Var nume: numeros; dimL: rango; Begin cargarNumeros(nume,dimL); write(“el menor numero leido es”, minimo(nume,dimL)); End.


Procedure cargarNumeros (var n:numeros; var tam:rango); var num:integer; begin tam:=0; read(num); while (num <> 99) do begin n[tam+1]:= num; tam:= tam + 1; read(num); end; end;

Qué pasa si el número 99 se lee

después de los 10000 números?

La solución no es correcta, pues podríamos estar accediendo a posiciones no válidas


Procedure cargarNumeros (var n:numeros; var tam:rango); var num:integer; begin tam:=0; read(num); while (num <> 99) and (tam < DIMF) do begin n[tam+1]:= num; tam:= tam + 1; read(num); end; end;

SIEMPRE SE DEBE CONTROLAR NO

INGRESAR MAS NUMEROS QUE LA DIM. FISICA

DECLARADA


function minimo (n:numeros, DimL:rango):integer; var i: rango; min:integer; Begin min:=9999; for i:= 1 to DimL do if (n[i]< min) then min:= n[i]; minimo:= min;end;

OPERACIONES: Agregar Un Elemento Nuevo En El

Vector

Arreglos: Agregar al final (append)

Aspectos a considerar:

• dimF : dimensión del vector (tamaño especificado en la declaración del vector)

• dimL : cantidad de elementos en el vector. Luego de la operación la cantidad de elementos es dimL+1, siempre que haya espacio ( dimL< dim).

• espacio suficiente: debe verificarse que dimL < dim.

Arreglos: Agregar al final

{Este programa agrega varios elementos invocando al procedure Agregar}

Program AgregarElementos;const dimF = 10;Type rango= 0..dimF; vector = array [1..dimF] of integer;Var v : vector; elem: integer; sepuede: boolean; dimL, i: rango;

Arreglos: Agregar al final Begin {prog. ppal}

read (elem); sepuede:=true; dimL:=0; while (elem <> 0) and ( sepuede) do begin AGREGAR ( v, dimL, elem, sepuede); if sepuede then read (elem); end; write ('El vector resultante es: '); readln; For i := 1 to dimL do write (v[i], ' ');End.

Podemos hacer un módulo para más legibilidad

Podemos hacer un módulo para más legibilidad

Arreglos: Agregar al final

Procedure AGREGAR (var v: vector; var dimL:rango; elemento: integer; var exito : boolean);Begin {verificar espacio suficiente} If (dimL < DimF) then begin v[dimL + 1]:= elemento; dimL := dimL + 1; {actualizar cantidad de elementos} end else exito := false; End;

OPERACIONES: INSERTAR Un Elemento Nuevo En El

Vector

Arreglos: Insertar

11 22 33 1010..............

2 5 3

6

Dim Logica

44

5

6

32

Supongamos que deseamos insertar el

VALOR 6 en la POSICIÓN 1 del

vector

Supongamos que deseamos insertar el

VALOR 6 en la POSICIÓN 1 del

vector

La posición donde debo insertar debe ser VÁLIDA

La posición donde debo insertar debe ser VÁLIDA

Arreglos: Insertar Program

insertarelementos; Const dimF = 1000 Type rango= 0..dimF;vector = array [1..dimF] of integer;var v: vector; elem : integer; pos , DimL: rango; sepuede : boolean;

begin cargar-vector (v, DimL); sepuede := true; readln (elem); readln(pos); Validar(pos, sepuede); while (elem < > 0) and (sepuede) do begin INSERTAR ( v, DimL, elem, pos, sepuede); if (sepuede) then begin read (elem); readln(pos); Validar (pos,sepuede); end; end.

Arreglos: Insertar Procedure cargar-vector ( var num: vector; var DimL: integer );

var elem : integer; Begin DimL := 0; read (elem); while (elem < > 9999) and (DimL< dimF ) do begin DimL := DimL + 1; num [ DimL ] := elem; read (elem) end; End.

Arreglos: Insertar Procedure INSERTAR (var num:vector; var dimL:rango; elem:integer;

pos:rango; var exito:boolean );var i : rango;Begin if (dimL < DimF ) then begin exito := true; i := DimL; While ( i >= pos ) do begin num [ i + 1 ] := num [ i ] ; i := i - 1 ; end; num [pos] := elemento; DimL := DimL + 1; {Incremento dim logica} end else exito := false; end;

OPERACIONES: BORRAR Un Elemento Existente En

El Vector

Arreglos: Borrar Aspectos a considerar:

DimL : cantidad de elementos en el vector. Luego de la operación la cantidad de elementos disminuye en 1.

Pos : posición del elemento del vector que se quiere borrar. Debe verificarse que pos<= DimL

{Consideremos un programa que borra varios elementos en posiciones

que se ingresan como dato, invocando al procedure Borrar}

Arreglos: Borrar

program borrarelementos;const dimF = 1000; type rango= 0..dimF; vector = array [1..dimF] of integer;var v: vector; elem : integer; pos , DimL: rango; sepuede : boolean;

begin cargarvector (v, DimL); sepuede := true; read (pos); while ( pos< > 0) do begin BORRAR ( v, DimL, elem, pos, sepuede); if sepuede then writeln (“El elemento borrado es: ”, elem); read (p); end; End.

Arreglos: Borrar Procedure BORRAR (var num: arreglo; var DimL: integer; var

elemento: integer; pos: rango; var exito: boolean );Var j: rango; Begin if (pos <= DimL) and (pos >=1) then begin {verifica valor de pos, valida ese valor} elemento := num [pos] ; {Guarda el valor del elemento que se borra } for j:= pos to DimL-1 do num [ j ] := num [ j + 1 ] ; DimL := DimL - 1 ; end else exito := false; End;

Estructura de datos EJERCICIOS

1. Se lee una secuencia de números comprendidos en el rango de 5 a 60. La secuencia termina cuando se lee el número 24. Informar cuantas veces apareció cada número.

2. Se lee una secuencia de letras minúsculas que termina en punto. Informar la cantidad de veces que aparece cada letra.

3. Se lee una sucesión de datos de a lo sumo 100 alumnos. De cada alumno se conoce nombre y nota de alumnos. Informar los nombres de aquellos alumnos que superen el promedio del grupo. La lectura termina con el alumno de nombre ZZZ.

Estructura de datos EJERCICIO 1

Program uno;

type rango = 5..60; cantidades = array [rango] of integer;

var num: cantidades;

Estructura de datos-ARREGLO –

EJERCICIO 1

Begin inicializar (num); contabilizar (num); informar (num);

End.


EJERCICIO 1

Procedure inicializar (var a: cantidades);Begin for i:= 5 to 60 do a[i]:= 0;End;


EJERCICIO 1

Procedure contabilizar (var a: cantidades);Var valor:rango;Begin read (valor); while (valor<>24) do begin a[valor]:= a[valor] + 1; read (valor); end;End;


2. Se lee una secuencia de letras minúsculas que termina en /. Informar la cantidad de veces que aparece cada letra.


EJERCICIO 2

3. Se lee una sucesión de datos de a lo sumo 100 alumnos. De cada alumno se conoce nombre y nota de alumnos. Informar los nombres de aquellos alumnos que superen el promedio del grupo. La lectura termina con el alumno de nombre ZZZ.

Program dos;

type cantidades = array [‘a’..’z’] of integer;var num: cantidades;Begin inicializar(num); cargar (num); informar(num); End.End.


EJERCICIO 2

Procedure inicializar (var a: cantidades);Vari:char;Begin for i:= ‘a’ to ‘z’ do a[i]:= 0;End;


EJERCICIO 2


EJERCICIO 2

Procedure contabilizar (var a: cantidades);Var valor: char; Begin read (valor); while (valor <> ‘/’) do begin a[valor]:= a[valor] + 1; read (valor); end;End;


EJERCICIO 2

Procedure informar (a: cantidades);Var i:char;

Begin for i:= ‘a’ to ‘z’ do write (a[i]);End;


3. Se lee una sucesión de datos de a lo sumo 100 alumnos. De cada alumno se conoce nombre y nota. Informar los nombres de aquellos alumnos que superen el promedio del grupo. La lectura termina con el alumno de nombre ZZZ.

2. Se lee una secuencia de letras minúsculas que termina en punto. Informar la cantidad de veces que aparece cada letra.


EJERCICIO 3


EJERCICIO 3

Program Ej3;Const numdatos = 100;type rango=0..numdatos; str20 = string [20]; alumno = record nombre : str20; nota : real; end; ListaAlum = array [1.. numdatos] of alumnos;var datos: ListaAlum; dimL: rango; suma,promedio : Real;


EJERCICIO 3

begin {Principal} Leo_y_Sumo_Datos (datos , suma, dimL);

promedio := suma / dimL;

for i := 1 to dimL do if (datos[i].nota > promedio) then WriteLn (datos[i].nombre, ´ ´, datos[i].nota )end;


EJERCICIO 3

procedure Leo_y_Sumo_Datos (var dat: ListaAlum;var sum:Real;var DimL: rango);Var alu: alumno;begin sum := 0; dimL:= 0; leerAlumno (alu); while (alu.nombre <> ‘zzz’) and (dimL < numdatos)do begin dat[dimL+1]:= alu; sum := sum + dat[dimL+1].nota; dimL:= dimL +1; leerAlumno (alu); endend;

Clase10-Vectores_2011

Documents

Transcript of Clase10-Vectores_2011