1Arreglos

Arreglos

2013TransversaldeProgramacinBsicaProyectoCurriculardeIngenieradeSistemas

2Arreglos

1.Objetivos

Asimilarelconceptodearreglo. Identificarproblemasquepuedensersolucionadosmediantearreglos. Solucionarproblemasutilizandoarreglos.

2.IntroduccinUna estructura de datos es una coleccin de datos que pueden ser caracterizados por suorganizacin y lasoperacionesque sedefinenenella.Algunas veces aestasestructuras se lesllamatiposdedatos.Una estructura de datos es una coleccin de datos que pueden ser caracterizados por suorganizacin y las operaciones que se definen en ella. Las estructuras de datos son muyimportantesenlossistemasdecomputadora.Lostiposdedatosmsfrecuentesutilizadosenlosdiferenteslenguajesdeprogramacinson:

Lasestructurasdedatosestticassonaquellasen lasqueeltamaoocupadoen lamemoriasedefineantesdelaejecucindelprogramaynopuedemodificarseduranteesta.

3Arreglos

Lasestructurasdedatosdinmicas no tienen las limitaciones y restriccionesenel tamaodememoriadelasestructurasestticas.Medianteelusodeuntipodedatoespecfico,denominadopuntero, es posible construir estructuras de datos dinmicas soportadas por lamayora de loslenguajesdeprogramacin.1Unacaractersticaimportantequediferenciaalosdatossimplesdelosestructuradosesqueparalosdatossimplescadavariablerepresentaunelemento,mientrasqueenlosdatosestructuradoscadaidentificador(nombre)representamltiplesdatosindividuales,pudiendocadaunodeellosserreferenciadosindividualmente.Unarregloesunconjuntofinitoyordenadodeelementoshomogneos.Lapropiedadordenadosignificaqueelprimerelemento,elsegundo,eltercero,...,elensimopuedeseridentificado.Lahomogeneidadimplicaquetodosloselementosdelarreglosondatosdelmismotipo.3.DefinicinUnarregloesunaestructuradedatos,omstcnicamente,unespaciodememoriaquepermitealmacenarunacoleccindeelementos,todosdelmismotipo.Convieneimaginarunarreglocomounasecuenciacontiguadeceldas(espaciosdememoria),ocasillas,encadaunade lascualessepuedeguardarunelementode lacoleccin.Adems,esusualdibujarlocomo lo ilustra la figurasiguiente:

0 1 2 3 4 5 6

Esta figura representaunarreglode siete casillas cadaunade las cuales sepuedeutilizarparaguardarundato.Ladimensinotamaodeunarregloeselnmerodecasillasqueloconforman.Debeserclaro,entonces,quelafiguraanteriorcorrespondeaunarreglodedimensin7.Cadaunadelascasillasdeunarreglotieneasociadounnmeroquelaidentificademaneranica.Aestenmeroselellamandiceodireccin.Enlafiguraanterior,debajodecadacasilla,aparecesundice.EnlenguajescomoC,C++yjava,laprimeracasilladelarreglotienendice0,lasegundatienendice1,latercerandice2,yassucesivamente.EsmuyimportantetenerpresentequesielarregloesdedimensinN,laltimacasillatienendiceN1.Otrasposiblesnotacionespuedenser:

1Cuando un lenguaje de programacin no soporta de estructura de datos dinmicas eventualmente pueden ser simuladas mediante el algoritmo apropiado.

4Arreglos

Loslenguajesdeprogramacin,permitenqueelprogramadordeclarearreglosdecualquiertipoyprcticamente de cualquier tamao. En el seudolenguaje, un arreglo se declara usando elsiguienteformatooplantilla:

:arreglo[]de

En este formato aparecen enmaysculas y entre los caracteres los componentes que elprogramador debe determinar. As por ejemplo, si se quiere declarar un arreglo con nombreletras,dedimensin15yquepuedaalmacenardatosdetipocaracter,sedebeescribirlasiguientelnea.

letras:arreglo[15]decarcter

Volviendo al formato anterior, el programador debe bautizar el arreglo (ponerle un nombresignificativo),debedecirculessudimensin,ytambindebedecirdequtiposonloselementosquealmacenaresearreglo.Enseguidasedanalgunosejemplosdedeclaracionesdearreglos.

- Sisenecesitaguardarlasventasdiariasdeunatiendadurantelaltimasemana,sepuededeclararelsiguientearreglo:

ventas:arreglo[7]dereal

- Sisequiereguardar lasnotasquehasacadounestudianteen loscincotalleresyen loscinco laboratorios del curso de Programacin Bsica se pueden declarar los siguientesarreglos:

talleres:arreglo[5]dereallaboratorios:arreglo[5]dereal

- Sisequiereguardarelvalorde lasltimas12facturastelefnicasdeunacasa,sepuede

declararelsiguientearreglo:

facturasTel:arreglo[12]dereal

Los ndicessecrearonparapermitirqueelprogramadorsepuedareferir,deformaespecfica,auna cualquierade las casillasdelarreglo, tantoparaguardarundatoenesa casilla, comoparaobtenereldatoguardado.Para referirseaunacasillaparticulardeunarreglosedebeseguirelsiguienteformato:

[]

5Arreglos

esdecir,sedebeescribirelnombredelarregloseguidoporelndicedelacasillaentreparntesiscuadrados.EjemplosA continuacin se muestran algunos ejemplos con el objeto de esclarecer la teora antespresentada EjemploUnoParaelsiguienteejemplo,supongaquesedeclaraelarreglocifras,delasiguientemanera:

cifras:arreglo[10]deentero

- La siguiente instruccin asigna o guarda el nmero 100 en la primera casilla de estearreglo:

cifras[0]:=100- Lasiguiente instruccin iterativaguarda550encadaunade lasltimas5casillasdeeste

arreglo:i:=5MIENTRAS(i

6Arreglos

Considereelproblemadeconstruirunalgoritmoquehagaunhistogramaparauna listadehasta100 valores, donde cada valor es un nmero entero comprendido en el intervalo 1 al 5. Lasentradas(datosconocidos)paraelalgoritmoson:

Elnmerodedatosdelacoleccin Lacoleccinmisma

Lasalidaesperada(datodesconocido)es:

ElhistogramadelacoleccinEn este problema, los arreglos son tiles para guardar los datos que conforman la coleccin ytambinparaguardarelhistograma.Elnmerodedatosdelacoleccinsepuedeguardarenunavariable entera. La siguiente grfica resume las entradas y las salidas del algoritmo que se

pretendedisear.Ademsbautizatodaslasvariablesmencionadas:Las condiciones inciales y finales se pueden expresar mediante dos clusulas: REQUIERE yGARANTIZA,delasiguientemanera:

REQUIERE:Elnmerodedatosde lacoleccindebesermayorqueceroymenoro igualquecien.(100totalDatos>0)Cadaunodeloselementosdelacoleccindebeserunnmeroentre1y5.GARANTIZA:Calculaelhistogramaasociadoa lacolecciny lopresentaen lapantalla.Lafrecuenciadecadadatoaparecegraficadocomounasecuenciadeasteriscos.

Unaprimeraversindelalgoritmosolucinpuedesersimplementelasiguiente:

InicioPaso1.LeerelnmerodeelementosquetienelacoleccinPaso2.LeerloselementosdelacoleccinPaso3.CalcularelhistogramaPaso4.PresentarelhistogramaenlapantallaFin

Lospasos1y2son interaccionesconelusuarioquepermitencapturar losdatosdeentrada. Laversin inicial se puede refinar detallando estos pasos y adems, definiendo las variablesnecesariasparahacerlos:

Totaldatoshistograma

coleccion

7Arreglos

ProcedimientoprincipalVariablesi,totalDatos:enterocoleccin:arreglo[100]deenteroInicioescribir(Por favor digite el nmero de datos de la coleccin : (inferior o igual a100))leer(totalDatos)i:=0mientras(i

8Arreglos

i:=i+1finmientras

Finalmente,unavezcalculadoelhistograma,sedebepresentarenlapantalla.Cadadatosedebepresentarjuntoconsufrecuencia,peroserequierequelafrecuenciaaparezcacomounacadenade asteriscos, en vez de como un nmero. Por ejemplo, si el dato 8 aparece 3 veces en lacoleccin,en lapantalladebeaparecer8:***,comouna lneadelhistograma.Estoquieredecirqueparaescribirlafrecuenciadeundato,serequiereuncicloqueescribatantosasteriscoscomosealafrecuencia.Concluyendo,elpaso4(presentarelhistogramaenlapantalla)sepuederefinarcomosemuestraenseguida:

i:=0mientras(i

9Arreglos

escribir(i+1) leer(coleccin[i]) i:=i+1finmientrasi:=0mientras(i

10Arreglos

Enesteproblema,losarreglossontilesparaguardarlasrespuestascorrectasylasopcioneselegidas por el estudiante. El nmero de preguntas del examen se puede guardar en unavariableentera,aligualquelanota.Enseguidasemuestralaespecificacindeesteproblema:

REQUIERE

- Elnmerodepreguntasdelexamendebesermayorquecero.(totalPreguntas>0).- Cadaunade lasrespuestasdelestudiantedebeseruna letramaysculaqueest

entreAyE.- Cadaunadelasrespuestascorrectasdebeserunaletramaysculaqueestentre

AyE.GARANTIZA

- Lanotadadapor el algoritmo corresponde al totalde respuestas acertadasdelestudiante

Escribaunalgoritmoquecumplaconestaespecificacin.

2. Escribaunalgoritmoqueefecte lanormalizacindeunacoleccindenmerosreales.Para

llevaracaboestanormalizacin, sedebeenprimer lugarencontrarelnmeromayorde lacoleccin; luego se divide cada nmero por dicho valormximo, de forma que los valoresresultantes(normalizados)estncomprendidosenelintervalodel0al1.

3. Escribaunalgoritmoquesumeenbinario.Lasentradassondosnmeros(binarios)ylasalida

es la suma de estos dos valores (tambin en binario). Por ejemplo, si el usuario digita lascadenasbinarias101y1101,larespuestadadadebeser10010.

Ejerciciosparadesarrollarencasa1. EscribaunalgoritmoqueleadosarreglosdenmerosenterosORDENADOSascendentemente

y luegoproduzca la listaordenadade lamezclade losdos.Porejemplo, si losdosarreglostienenlosnmeros136917y241017,respectivamente,lalistadenmerosenlapantalladebeser123469101717.

2. Escribaunalgoritmoque leaunarreglodenmerosenteros,yunnmerox,yescribaen la

pantallatodoslosndicesdelasposicionesdelarreglodondeestx.Porejemplo,sielarregloeselqueapareceenseguidayxes2:

1 2 3 100 23 2 2 1

totalPregunta

notarespuestas

correctas

11Arreglos

Elprogramadebeescribir:156.3. Un arreglo de nmeros se llama partidario si todo nmero que est en una casilla par

(0,2,4,)esmayorquecualquierade losnmerosqueestnenlascasillasimpares(1,3,5,).Escribaunalgoritmoqueleaunarreglodenmerosenterosyluego,digasiespartidarioono.Porejemplo,sielarregloeselsiguiente:

100 5 200 1 1000 0 600 50 300 4

Elprogramadebeescribir:espartidario.

AnexosEnestaseccinsemostraracomoeslacodificacindelateoravistaenclase,paraelloseutilizaracomoherramientadecodificacin:C++.

CodificacinenC++dearreglosymatrices

Seudocdigo C++Arreglo :arreglo[]de

[];

Ejemplo#include#includeusingnamespacestd;intmain(intargc,char*argv[]){intconstN=5; //NeseltamaomximodelhistogramaintconstMAXDATOS=100; //MAXDATOSeseltamaomximodelacoleccin;inti,j,totalDatos,d,f;intcoleccion[MAXDATOS];inthistograma[N];cout(totalDatos);i=0;while(i

12Arreglos

}i=0;while(i

13Arreglos

Fuentes:

http://www.sites.upiicsa.ipn.mx/polilibros/portal/Polilibros/P_terminados/EstrRepreDat/Files/insercion_nodos.html

http://lictoledomarcelo.awardspace.com/archivos/Ejercicios_VB_Arreglos.pdf http://cyberprogramacion.zxq.net/pdf/Arrays%20%28Vectores%20y%20Matrices%29%20

2012%20%20Luis%20U..pdf http://www.fismat.umich.mx/mn1/manual/node6.html http://www.herrera.unt.edu.ar/programacion/archivos/ejemplos%20de%20Arreglos.pdf