Cap3    

 

 

 

 

 

 

 

Hasta ahora sólo habiamos visto estructuras de datos simples (como variables y constantes enteras,  reales y caracter )., pero estas no son suficientes para resolver problemas mas complejos.  

 

Por ejemplo como responderiamos a estas interrogantes. 

 

¿ Cómo almacenar y accesar a las respuestas a 10 preguntas de 5 opciones múltiples 'A','B','C','D' y 'E'  ?

¿Usaríamos las variables. rpta1, rpta2, ....... rpta10 ?

¿ Cómo almacenar y localizar las notas y los nombres de 25 alumnos de esta clase ?

¿Usaríamos las variables. Nombre1, Nombre2, ....... Nombre25   y

Nota1, Nota2, ... Nota25?

indices Nombres Notas
0 Julio Perez 12
1 Edgar Condori 4
2 Erica Castro 11
3 Luis Risco 9
  .....  
22 Miura Fernández 16
23 Ada Lugo 12
24 André Fernández 5
¿ Cómo almacenar y localizar los nombres y sueldos de los 40 empleados de una pequeña empresa ?

¿Usaríamos las variables. Nombre1, Nombre2, ....... Nombre10   y

Sueldo1, Sueldo2, ...Sueldo39 ?

indices

Nombre

Sueldo

0 Ada Lugo 2400.6
1 Miura Fernández 3500.5
2 André Fernández 2800.8
i            .....        ...
37 Gladys Garcia 3200.0
38 Jorge Barzola 2105
39 Maria Cano 3700.2

¿ Cómo almacenar y localizar la cantidad de vehiculos ( bicicletas, triciclos, motos, autos y camiones) vendidos en cada uno de los 12 meses del año 2001, por una importadora de vehiculos de transporte y carga. ?

¿Usaríamos las variables. Can1, Can2, Can3 ... Can30?  

Fig. 4.1  Ejemplos de Arreglos 

 

 

Esas no serian las soluciones a los problemas planteados ¿ verdad ? 

¡ Ya no es adecuado usar los tipos de datos simples (enteros reales o caracteres) porque tendriamos que declarar muchas variables  ! 

Para resolver problemas de este tipo se requieren  datos estructurados mas complejas, capaces de almacenar datos relacionados entre sí.

 

Definición 1   Una estructura de datos es un modelo matemático o lógico de una organización particular de datos. 

Definición 2.  Una estructura de datos es una colección de datos que se caracterizan por la FORMA en que estos se ORGANIZAN, y por las OPERACIONES  que se pueden definir sobre dichos datos. 

 

Los tipos de datos mas frecuentes utilizados en los diferentes lenguajes de programación son:

Tipo de Datos Simples

(Datos Simples)

 

Estándar

Entero
Real
Caracter
Lógico
Definidos por el usuario

Subrango
Enumerado
Característica :Un identificador de un tipo de dato simple (nombre de variable) representa a un unico elemento

Tipos de Datos Complejos

(Datos estructurados)

 

Estáticos

Array (Vectores y Matrices)
Registros
Archivos
Conjuntos
Cadenas
Dinámicos

Listas Lineales

Pilas 
Colas 
Listas enlazadas

Listas  No Lin.

Arboles
Grafos
Característica:- Un identificador de un tipo de dato estructurado (nombre de variable)  puede representar a multiples datos individuales, pudiendo cada uno de ellos ser accesados de manera independiente.
Tipos Abstractos de Datos

Fig.  4.2  Clasificación de los Tipos de Datos


La elección de la estructura de datos adecuada dependerá del tipo de aplicación.
Existen dos maneras de representar en memoria a las estructuras lineales (o listas lineales):
En arreglos (o arrays) , almacenandolo los elementos de la lista en posiciones consecutivas de memoria.
En listas enlazadas, reflejando la relación entre los elementos por medio de punteros o enlaces. Esto lo veremos posteriormente.

 

 

Definición 1 :  Es un conjunto ordenado y finito de elementos homogéneos.  

Es decir, sus características básicas son:

"Finito" , porque se requiere definir el tamaño del array (definir el tamañ antes de ser utilizado).

Ejm : el array Notas que almacena las notas de los 25 alumnos de una clase es de tamaño 25

"Homogéneos" , porque todos los elementos del array son del mismo tipo.

Ejm:  en el array Notas, todas las notas almacenadas son de tipo entero.

"Ordenado" , porque se pueden identificar a cada elemento del array por la posición que ocupan : el primero, el segundo, el tercero, ..., el n-esimo, etc. 

Ejm: en el array Notas, la nota del tercer alumno de la clase (puede ser en orden alfabetico), ocupa la posición 3.

 

Fig. 4.3  Arreglos unidimensionales - caracteristicas

 

Definición 2 : 

Son posiciones en memoria consecutivas relacionadas entre sí por el hecho de que tienen el mismo nombre y los datos que contiene son todos del mismo tipo.

Son entidades estáticas ya que conservan el mismo tamaño durante toda la ejecución del programa.

 

 

Los arreglos se clasifican en:

a) Arreglo unidimensional

 ( array lineal o vector )

En matemática es conocido como Vector.   Ejm:  

Cantidad de canastas anotadas por el equipo peruano en cada uno de los 5 partodps del Sudamericano 2000

Tamaño 5

Arreglos unidimensionales paralelos

Dos o mas vectores de igual tamaño donde sus elementos de igual indice estan relacionados.  Ejm: 

Descripcion de productos y sus respectivos precios (8 tipos de productos).

Tamaño 8

Arreglo bidimensional

(array bidimensional o matriz )

En matemática es conocido como Matriz,  o en base de datos como  tabla.  Ejm: Los sueldos de 10 empleados en cada uno de los meses de Enero a Junio 2000.

Tamaño 10x6

Arreglo multidimensional ( n - dimensional) Ejm: Estados (libre u ocupado) de las 10 aulas en cada uno de los 4 pisos de los 5  pabellones. 

Tamaño 10x4x5 

Fig. 4.4  Clasificación de arreglos

 

 

 

 

          Operaciones:

 

 

...  Piense en algunos  ejemplos de arreglos unidimensionales 

Fig. 4.5  Ejemplos de arreglos unidimensionales

 

 

Es una estructura de datos lineal formado por una lista ordenada y finita de elementos de la misma naturaleza (o tipo), que se distinguen unos de otros por la posición que ocupan dentro de la lista. De manera que a cada elemento se le puede asociar un indice que señala el numero de orden dentro de la estructura.

Se dice que la estructura es lineal porque sus elementos forman una secuencia (lista lineal)

Los elementos del arreglo se almacenan en memoria en celdas consecutivas y se referencian a través de índices (números consecutivos).                                                                                

 

Si la longitud o tamaño del arreglo es n, los índices segun los lenguajes de programación pueden ser :

En pascal :

               
1 2 3 i n-1 n

 

En C++:

               
0 1 2 i n-2 n-1

 

En general la longitud o numero de datos del arreglo pueden obtenerse de la formula: 
Longitud (o tamaño)    = LS - LI + 1
LS = índice de mayor valor o límite superior del arreglo.
LI   = índice de menor valor o límite inferior del arreglo
Si Li = 0  y  Ls = n -1 :     Longitud = n -1 - 0 +1 = n elementos
Si Li = 1  y  Ls = n            Longitud = n -1+1 = n elementos

               

   V

12

14

16

10

20

06

09

12

17

...

19

08 

17

0 1 2 3 4 5 6 7 8   12 13 14

ver Arreglo_Unid

 

Cada Lenguaje de Programación tiene sus reglas para declarar un arreglo Pero cada declaración debe incluir 3 clases de información acerca del arreglo: 

Ejm  En  PASCAL:                 Autos[1..16] OF integer

Ejm: En C++                            int   Autos[16];

Al declararse un arreglo unidimensional se reserva espacio en la memoria principal para una cantidad de elementos del tipo declarado.

A este tipo de estructura se le denomina estatico, porque la longitud del arreglo no puede variarse durante la ejecución del programa.
Las estructuras dinámicas pueden cambiar su tamaño (aumentar o disminuir) durante la ejecución del programa.

 

EJEMPLO DE DECLARACION DE ARREGLOS UNIDIMENSIONALES
EN ALGORITMOS (seudocódigo) y en C++  (código) respectivamente
real   nota[25] nota almacena hasta 25 datos reales
double   nota[25];
real   talla[30] talla almacena hasta un maximo de 30 datos reales
double   talla [30];
entero  codigo[30] codigo almacena hasta 30 datos enteros
int   codigo[30];
entero   unidCompradas[10] unidCompradas almacena hasta 10 datos enteros
int   unidCompradas[10];
caracter  Letras[45] Letras almacena hasta 45 datos caracter ('r','T','s', ...)
char   Letras[45];
caracter   estCivil[50] estCivil almacena hasta 50 datos caracter ('S','C','S', ...)
char   estCivil[50];
caracter  nombres[5] [30] Los dos ultimos nombres son arrays de tamaño 5 que almacenan nombres en el primer caso de tamaño definido (30) y en el segundo caso de un tamaño no definido.
char  nombres [5] [30];
char*  nombres[5];
     
 

 

 

Fig. 4.6 Operaciones que pueden hacerse con arreglos unidimensionales

 

A) Inicialización de vectores 

    Al igual que con las variables simples (no estructurados), los vectores se pueden inicializar al momento de declararse. Ejm:

Ejemplos de declaración e inicialización de arreglos unidimensionales en algoritmos (pseudocódigo) y en C++

real   nota[25] = { 12,07,15,12, ...,10,20,19} nota se inicializa con 25 datos reales.
double nota[25]={ 12,07,15,12, ...,10,20,19};
real talla[30] = { 1.56, 1.78, 1.45, 1.71, ....,1.52 } talla se inicializa con 30 datos reales 
double talla[30] = { 1.56, 1.78, 1.45, 1.71 ,..., 1.52};
entero  codigo[30]={11,12,22,23,33,34,...,99} codigo se inicializa con 30 datos enteros 
int codigo[30]={11,12,22,23,33,34,...,99};
entero unidCompradas[10] = {12. 24, 36, ...,100} unidCompradas se inicializan con 10 datos enteros 
int   unidCompradas[10] = {12. 24, 36, ...,100};
caracter  Letras[52]={'A','B','C', .,'Z','a','b',...,'z'} Letras se inicializa con 52 datos de tipo caracter 
char Letras[52]={'A','B','C', .,'Z','a','b',...,'z'};
caracter estCivil[50]={'S','C','C','V','S',...,'V','S'} estCivil se inicializa con 50 datos de tipo caracter 
char estCivil[50]={'S','C','C','V','S',...,'V','S'};
caracter Rpta[] = {'a','d','c','a','c','b','a','b'}; El compilador completa el tamaño del arreglo con el numero de inicializadores proporcionado (8)
char Rpta[] = {'a','d','c','a','c','b','a','b'};
 
entero  A[5]={1,3,7,}; A se inicializa con 5 datos de tipo entero, el resto se inicializa en 0
int  A[5]={1,3,7,};
 
char* preProf [4]={"Ing. ","Lic. ", "Dr. ", "Mag."}; preProf  inicializa 4 datos prefijos que son punteros a cadenas
char* descripcion[10] = { "TV 14","TV 24", "TV 29", ..., "VHS"} descripcion  inicializa 10 datos que son punteros a cadenas
caracter nombres[2] [30] = {"Juana", "Jose Luis"} nombres inicializa dos nombres (cadenas cuyo maximo numero de caracteres es 30)
char nombres[2] [30] = {"Juana", "Jose Luis"};
       
Los arreglos de caracteres pueden inicializarse asi:
  char A[4] = {'a','b','c','c'};     o   char A[5] = "abcd"; 
  El compilador añade "\0" (fin de cadena) por lo tanto el arreglo debe ser al menos 1 mas grande que el numero de caracteres de la cadena.

 

 

B) Asignación 

 Permite dar valor a uno o varios  elementos de un vector.

Asignación de valores a los elementos de un vector.  En algoritmos (pseudocódigo) y en C++

entero  A[15];

int  A[15];

caracter* nombre[5];

char* nombre[5];

caracter  vocales[5];

char  vocales[5];

real  talla[10];

double  talla[10];

caracter Apell[5][25]

char Apell[5][25];

A[10] = 45 A[10] = 45;
Asigna el valor 45 al elemento de indice 10 del arreglo A.
 
talla[2] = 1.56 talla[2] = 1.56;
Asigna 1.56 al elemento de indice 2 del arreglo talla
   
nombre[2] = "Andre Fernandez G." nombre[2] = "Andre Fernandez.";
Asigna Andre Fernandez G. al elemento de indice 2 del arreglo nombre
 
vocales[3] = 'E' vocales[3] = 'E';
Asigna E al elemento de indice 3 del arreglo vocales.
 
CopiaCadena(Apell[2], "Garcia") strcpy (Apell[2] , "Garcia");
Asigna el apellido Garcia al elemento de indice 2 del arreglo Apell.

 

C) Operaciones de Entrada/Salida 

Lectura/Escritura .- Permite dar  valor (leer o ingresar por teclado) o mostrar (en pantalla) el valor de los elementos de un arreglo unidimensional   Ejm:    

Lectura / Escritura de elementos de un arreglo en pseudocódigo y en C++ respectivamente
Leer V[3] Permite Leer el elemento de indice 3 del array unidimensional V
cin>> V[3] ;
 

Mostrar V[3]

Permite Mostrar el elemento de indice 3 del array unidimensional V

cout<< V[3] ;

 
Lectura / Escritura de los elementos de un arreglo por grupos en pseudocódigo y en C++ respectivamente

const entero N=10

entero  V[N]

const int  N=10;

int  V[N];

real Peso[N]

double Peso[N];

para (i = 1 ; hasta   i <= N ; con   i=i+1)

{      Leer   V [ i ];    }

Lee los elementos del vector V cuyo indice i varia desde 1 hasta N ( i varia de 1 en 1).

Nota: N debe ser conocido.

for (i = 0 ;  i < N ;  i=i+1)

{    cin>> V [ i ];    }

 

En C++: Lee los elementos del vector V cuyo indice i varia desde 0 hasta N-1( i varia de 1 en 1).  Nota  N debe ser conocido.

   

para (i = 1 ; hasta  i<= N ; con   i=i+1)

{      Mostrar  Peso [ i ];    }

Muestra los elementos del vector V cuyo indice i varia desde 1 hasta N.(i varia de 1 en 1).  Nota:  N debe ser conocido.

for (i = 0 ;   i< N ; i = i+1)

{      cout<< Peso [ i ];    }

En C++: Muestra los elementos del vector V cuyo indice i varia desde 0 hasta N-1. (i varia de 1 en 1).  Nota:  N debe ser conocido.

Ejemplo :

entero  V[5]

real Peso[5]

Ejemplo :

entero  V[5];

real Peso[5];

para (i = 1 ; hasta   i<= 5 ; con   i=i+1)

{      Leer   V [ i ];    }

Permite ingresar por teclado  los valores para cada elemento del array:

V[1],  V[2], V[3], V[4]  y V[5]

for (i = 0 ; i<= 4 ; i = i+1)

{      cin>>  V [ i ];     }

Permite ingresar por teclado  los valores para cada elemento del array:

V[0],  V[1], V[2], V[3]  y V[4]

Ejemplo Ejemplo

para (i = 1 ; Hasta   i<= 5 ; con   i=i+1)

{      Mostrar  Peso [ i ];    }

Muestra en pantalla los valores almacenados en cada elemento del array:   Peso[1],  Peso[2], Peso[3], Peso[4]  y Peso[5]

for (i = 0 ; i< 5   i = i+1)

{      cout >> Peso [ i ];    }

 

Muestra en pantalla los valores almacenados en cada elemento del array:   Peso[0],  Peso[1], Peso[2], Peso[3]  y Peso[4]

 

D) Operaciones de acceso a los arreglos 

D1) Recorrido ( barrido o visitado ) .- Procesamiento que permite el acceso a todos y cada uno de los elementos del array.

Asi se puede recorrer todo un array para procesos como: 

Ejm:  generico de Recorrido Recorrido del array lineal A con límite inferior LI y límite superior LS conocidos (ingresados por teclado o asignados). El algoritmo recorre al arreglo realizando la operación PROCESO a cada uno de los elementos del arreglo. a) Use estructura repetitiva Mientras. b) use para.

Algoritmo RECORRIDO  PROGRAMA RECORRIDO C++

INICIO

    COM: Declaración de Variables

   entero   LI, LS, i

   real    A [20]

    COM: Inicializa el valor de LI y LS

   LI = 1

   LS = 20;

   COM  Inicializa el contador

   i = LI ;

   mientras (  i <= LS )

   {   // Visita al elemento A[i]

       PROCESA   A [ i ]   

          i =  i + 1     // Incrementa el contador

   }

FIN

{

    // Declaración de Variables

   int   LI, LS, i;

   double  A [20];

    // Inicializa el valor de LI y LS

   LI = 0 ;   LS = 19;

    //  Inicializa el contador

   i =  LI;

   while (  i <= LS )

   {   // Visita al elemento A[i]

       procesa  A [ i ]   

          i =  i + 1;     // Incrementa el contador

   }

}

procesa cambia de acuerdo a los requerimientos del problema.  
PROCESA   puede ser :
  • LEER (cin>>) cada elemento del array.
  • MOSTRAR (cout<<) cada elemento del array
  • Acumular los elementos A[i]
  • Si es igual a algun valor contar o mostrar el elemento A[ì]
 
Algoritmo  RECORRIDO Programa RECORRIDO C++

INICIO

    COM:  Declaración de Variables

   entero   LI, LS, i

   real    A [20]

   LI = 1

   LS = 20

   COM:  Recorrido del Array A

  para ( i= LI ; hasta LS ; i =i+1)

  {   COM:  Visita al elemento A[i]

      PROCESA a A [ i ]          

  }

FIN

{

    // Declaración de Variables

   int  LI, LS, i ;

   double  A [20] ;

   LI = 0 ;

   LS = 19 ;

    //  Recorrido del Array A

   for ( i= LI ; i <= LS ; i =i+1 )

   {   // Visita al elemento A[i]

      PROCESA a A [ i ]          

   }

}

procesa cambia de acuerdo a los requerimientos del problema. 
PROCESA   puede ser :
  • Leer (cin>>) cada elemento del array.
  • Mostrar (cout<<) cada elemento del array
  • Acumular los elementos A[i]
  • Si es igual a algun valor contar o mostrar el elemento A[ì]
  • Calcular el minimo y el maximo valor del arreglo A.

 

Ejemplo - Aplicación : Una compañía de autos utiliza un arreglo  AutoV para almacenar el numero de autos vendidos desde 1979 hasta 2000.

AutoV [ k ]  =  numero de autos vendidos en el año k

LS = 2000.     LI =1979   Longitud = 2000 -1979 + 1 = 22.

 

ALGORITMO autos

Programa autos.cpp

INICIO

{

o

entero AutoV[22], i, Min, Max,Ca, Av

o

int AutoV[22], i, Min, Max, Ca, Av;

o

COM: Crear el array AutoV 

para( i=1, hasta 22 ,i=i+1) 

{   COM: visita cada elemento i 

    LEER AutoV [ i ]    

}

 

// Crear el array AutoV  

for ( i=0 ; i<= 21 ; i=i+1) 

{   // visita cada elemento i 

    cin>> AutoV [ i ];

}

 

 COM:  Mostrar AutoV y el año en que se vendieron.

para ( i=1, hasta 22 ,i=i+1)

{     // Visita cada  elemento i

    MOSTRAR  AutoV [ i ], i +1978

}   

 

 //  Mostrar AutoV y el año en que se vendieron.

for ( i=0 ; i<= 21 ; i=i+1)

{     // Visita cada  elemento i

    cout<<AutoV [ i ]<<" "<< i+1979<<endl;

}   

 

COM:   Cuantos autos se vendieron de 1979  a  2000

AV= 0    // Inicializa AutosVendidos

para ( i=1, hasta 22 ,i=i+1)

{    // Visita cada elemento i

       AV = AV +  AutoV [ i ]

 }

 

//   Cuantos autos se vendieron de 1979  a  2000

AV= 0    // Inicializa AutosVendidos

for ( i=0 ; i <=21 ; i=i+1)

{    // Visita cada elemento i

       AV = AV + AutoV [ i ];

 }

 

COM: Años  transcurridos de 1979 a 2000

CA =  0  // Inicializa Contador de Años

PARA  ( i=1, hasta 22 ,i=i+1)

{   // Visita cada elemento i contando

    CA =  CA + 1     

}

 

// Años  transcurridos de 1979 a 2000

CA =  0  // Inicializa Contador de Años

for ( i=0 ; i<= 21 ; i=i+1)

{   // Visita cada elemento i contando

    CA =  CA + 1;     

}

 

COM: En que años se vendieron mas de 900

autos anuales y cuantos se vendieron en cada uno

de esos años

PARA  ( i=1, hasta 22 ,i=i+1)

{  // Visita cada elemento i

   SI  ( AutoV [ i ] > 900 )

    MOSTRAR i+1978, AutoV[ i ]  }

}

 

/*  En que años se vendieron mas de 900

autos anuales y cuantos se vendieron en cada uno

de esos años */

for ( i=0 ; i<=21 ; i=i+1)

{  // Visita cada elemento i

   SI  ( AutoV [ i ] > 900 )

    cout<<i+1979<<" "<<AutoV [ i ]<< endl;  }

}

 

COM: En que año o años se vendieros menos autos y cual es ese valor 

Min =  AutoV[ 1 ];

PARA  ( i=1, hasta 22 ,i=i+1)

{   // Visita cada elemento i

     SI  (AutoV[ i ] < Min )

     {   Min = AutoV[ i ];   }

}

Mostrar Min

PARA  ( i=1, hasta 22 ,i=i+1)

{    // Visita cada elemento i

     SI  ( AutoV[ i ] = Min )

      {  Mostrar  i+1978   }

 }

 

//: En que año o años se vendieros menos autos y cual es ese valor 

Min =  AutoV [0 ];

for ( i=0; i<=21;=i+1)

{    // Visita cada elemento i

     SI  (AutoV[ i ] < Min )

     {   Min = AutoV [ i ];   }

}

cout<< Min<<endl;

for ( i=0 ; i<=21 ; i=i+1)

{     // Visita cada elemento i

     if ( AutoV[ i ] == Min )

       {  cout << i+1979<<endl;   }

}

 

COM: En que año o años se vendieron mas autos y cuantos fueron

MAX =  AutoV [ 1 ]

PARA  ( i=1, hasta 22 ,i=i+1)

{     COM: Visita  cada  elemento i

       SI  ( AutoV[ i ] > Max )

        {   Max = AutoV [ i ]   }

}

Mostrar Max

PARA  ( i=1, hasta 22 ,i=i+1)

{     COM: Visita cada  elemento i

       SI  ( AutoV[ i ] = Max  )

       {  Mostrar  i+1978   }

}

 

// En que año o años se vendieron mas autos y cuantos fueron

MAX =  AutoV [ 0 ];

for ( i=0; i<=21; i=i+1)

{     // Visita cada elemento i

       if ( AutoV[ i ] > Max )

        {   Max = AutoV [ i ];   }

}

cout<<Max<<endl;

for ( i=0 ; i<=21; i=i+1)

{     // Visita cada  elemento i

       if  ( AutoV[ i ] == Max  )

       {  cout<<  i+1979<<endl;  }

}

FIN

}

 

E) Operaciones de Actualización 

 

E1) Inserción  

  Adición de un nuevo elemento al array unidimensional o vector.  

 

E2) Borrado 

 Eliminación de un elemento del array unidimensional o vector.   Ver inserción y borrado.

F) Otras Operaciones 

 

F1) Ordenamiento o clasificación

  Organización de los elementos de la lista de acuerdo con algún tipo de orden.   Ejemplo ordenar las notas de mayor a menor , ordenar los nombres en orden alfabético, etc.

¿ Porqué se clasifica un arreglo ?

Esto se hace por lo general para facilitar la búsqueda de los elementos del array. Asi se clasifica en: los diccionarios, las agendas telefónicas, los casilleros de bibliotecas, relación de amigos, etc.

 

 

  • Ordenamiento por el Método de burbuja

Para entender el método ordenaremos de menor a mayor la lista de 8 datos enteros, usando el método de burbuja ( N = 8 ).  Sea el arreglo A:

A

30   

50      

28    

89

76

24

16

60

Paso1:

Objetivo: Obtener el mas grande al final de la lista. Para ello se compara  cada elemento A[j] con el siguiente A[j+1],  donde j varia de 1 a N -1 ( 7 comparaciones)

Es decir :     si  A[j] > A[j +1]   es verdad se intercambia. 

Finalmente el arreglo queda así :

30 28 50 76 24 16 60 89
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

El elemento mas grande esta en la posición 8.

Paso2 :

Objetivo: Obtener el mas grande al final de la lista (con 7 elementos). Para ello se compara  cada elemento A[j] con el siguiente A[j+1],  donde j varia de 1 a N -2.(6 comparaciones)

Es decir :     si  A[j] > A[j +1]   es verdad se intercambia. 

Finalmente el arreglo queda así :

28 30 50 24 16 60 76 89
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

El elemento mas grande esta en la posición 7

Paso 3:

Objetivo: Obtener el mas grande al final de la lista (con 6 elementos). Para ello se compara  cada elemento A[j] con el siguiente A[j+1],  donde j varia de 1 a N -3.(5 comparaciones)

Es decir :     si  A[j] > A[j +1]   es verdad se intercambia. 

Finalmente el arreglo queda así :

28 30 50 24 16 60 76 89
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

El elemento mas grande esta en la posición 6

Paso 4:

Objetivo: Obtener el mas grande al final de la lista (con 5 elementos). Para ello se compara  cada elemento A[j] con el siguiente A[j+1],  donde j varia de 1 a N -4 (4 comparaciones).

Es decir :     si  A[j] > A[j +1]   es verdad se intercambia. 

Finalmente el arreglo queda así :

28 24 16 30 50 60 76 89
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

El elemento mas grande esta en la posición 5

Paso 5:

Objetivo: Obtener el mas grande al final de la lista (con 4 elementos). Para ello se compara  cada elemento A[j] con el siguiente A[j+1],  donde j varia de 1 a N -5 (3 comparaciones).

Es decir :     si  A[j] > A[j +1]   es verdad se intercambia. 

Finalmente el arreglo queda así :

28 24 16 30 50 60 76 89
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

El elemento mas grande esta en la posición 4

Paso 6:

Objetivo: Obtener el mas grande al final de la lista (con 3 elementos). Para ello se compara  cada elemento A[j] con el siguiente A[j+1],  donde j varia de 1 a N -6 (2 comparaciones).

Es decir :     si  A[j] > A[j +1]   es verdad se intercambia. 

Finalmente el arreglo queda así :

16 24 28 30 50 60 76 89
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

El elemento mas grande esta en la posición 3

Paso 7:

Objetivo: Obtener el mas grande al final de la lista (con 2 elementos). Para ello se compara  cada elemento A[j] con el siguiente A[j+1],  donde j varia de 1 a N -7 ( 1 comparación).

Es decir :     si  A[j] > A[j +1]   es verdad se intercambia. 

Finalmente el arreglo queda así (ordenado de mayor a menor):

16 24 28 30 50 60 76 89
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

El elemento mas grande esta en la posición 2

EL ARRAY YA  ORDENADO  DE MENOR A MAYOR

16 24 28 30 50 60 76 89
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

 

Observación : Si se desea ordenar de mayor a menor, lo unico que cambia es la pregunta para hacer el intercambio, con el objetivo de obtener en cada paso el mas pequeño al final de la lista 

Es decir :     si     A[j]   <  A[j +1]   es verdad se intercambia. 

 

 

Algoritmo BURBUJA Programa C++ BURBUJA
INICIO {
 

COM: Declaracion de variables

entero  A[10], k , J, Aux , N=8

const int  N=10;

 

// Declaracion de variables

int  A[10], k , J, Aux , N=8;

const int  N = 10;

 

COM: Inicialización o lectura del arreglo A

para (i=1, hasta N, i = i+1)

{   Leer A[i]      }

 

 

//  Inicialización o lectura del arreglo A

for (i=0; i < N ; i = i+1)

{   cin>> A[i] ;     }

 

COM: Algoritmo de ordenamiento burbuja

COM: k = Numero de pasos (1 a  N-1)

para  ( k =1 hasta  N -1; k=k+1 )

{        

COM: Nro de compar. j depende del Nro de paso 

   para(J=1, hasta N–1-k;J =J +1)  

   {  

      SI ( A [J ] > A [J+1] ) 

      {    COM:  Intercambiamos A[J] y A[J+1]

           Aux = A [ J ]

           A [ J ] =  A [ J+1]        

           A [ J+1] = Aux

       }

   COM:  fin del PARA interior

}   COM: fin del PARA exterior

 

// Algoritmo de ordenamiento burbuja

//  k = Numero de pasos (1 a  N-1)

for  ( k = 0 ; k <  N -1 ; k = k+1 )

{        

//  Nro de comparac. j depende del Nro de paso 

   for (J = 0 ;J < N –1-k ; J =J +1)  

   {  

      if ( A [J ] > A [J+1]

      {    //  Intercambiamos A[J] y A[J+1]

           Aux = A [ J ];

           A [ J ] =  A [ J+1]        ;

           A [ J+1] = Aux;

       }

   }   // fin del para interno

} //COM: fin del PARA exterior

 

COM: Se muestra el arreglo ordenado

para (i=1, hasta N, i = i+1)

{   Mostrar  A[i]      }

 

// Se muestra el arreglo ordenado

for  (i=0 : i < N ; i = i+1)

{   cout<<  A[i] <<"  ";    }

FIN

}

 

 

 

Cuando se trata de arreglos de cadenas se requiere usar las funciones de comparación y de asignación de variables de ese tipo.

 

F2) Búsqueda

Búsqueda de la posición ocupada por un elemento con un determinado valor o del registro con un determinado valor de clave.

 

 

  • Método de Busqueda Secuencial

Sea el arreglo A de tamaño 50 que almacena valores reales, y sea ElemB el elemento que deseamos buscar en el arreglo. Lug almacena el lugar donde se encuentra a Elem dentro del arreglo ( es decir, 1 a 50 en pseudocodigo o 1 a 49 en c++). Suponga que el arreglo ha sido inicializado.

BusquedaSecuencial

BusquedaSecuencial  - C++
ALGORITMO BusquedaSecuencial void main ( )

INICIO

{

 
o

constante entera N = 50

real  A[ N ] = { 1.5,2.6,7.8, ..... , 6.9, 8.0}

real  ElemB

entero  i, Lug ;

Leer ElemB

para ( i= 1, hasta N , i = i+1 )

{

  COM: compara c/elemento i de A con ElemB

     SI  ( A [ i ] = ElemB )

     {   Lug = i

         Mostrar “Esta en  “, Lug

         ruptura;

      }

}   COM:  fin del para

o

const int N = 50;

double A[N] = { 1.5,2.6,7.8, ..... , 6.9, 8.0};

double ElemB;

int  i, Lug;

cin>> ElemB;

for  ( i= 0 ; i< N ; i = i+1 )

{  //  compara c/elemento i de A con ElemB

   if  (A [ i ] == ElemB )

     {  // si lo encuentra muestra la posición  

       Lug = i;

       cout<< “Esta en  “<<Lug <<endl ;

       break;     // sale del for

     }   

}   // fin del for

FIN }  

 

 

BusquedaSecuencial

BusquedaSecuencial  - C++
void main( ) void main ( )

{   // con do while

{

// con while
o

const int N = 50;

double A[N] = { 1.5,2.6,7.8, ..... , 6.9, 8.0};

double ElemB;

int  Enc, Lug, i=-1 ;

cin>> ElemB;

do  

{    //  el indice incrementa

      i = i+1;

     // si no lo encuentra e i <50 continua buscando

} while ((ElemB !=A[i] ) && (i<50)); 

if ( i == 50)

{  Lug = i;

   cout<<"esta en "<<Lug<<endl;

}

else 

{  cout<<" no esta"<<endl; }

getch();

o

const int N = 50;

double A[N] = { 1.5,2.6,7.8, .. , 6.9, 8.0};

double ElemB;

int  Lug, i=0 ;

cin>> ElemB;

while  ((ElemB!=A[i] && (i< 50))

{    //  el indice incrementa

      i = i+1;

}   // fin del while

if ( i == 50)

{  Lug = i;

   cout<<"esta en "<<Lug<<endl;

}

else 

{  cout<<" no esta"<<endl; }

getch();"

FIN }  

 

Ver Procedimiento busqueda_secuencial

 

  • Método de BUSQUEDA BINARIA

Se utiliza para arreglos ordenados de manera creciente (tanto numericos como cadenas).

 

Ejemplo: Si queremos buscar una palabra en el diccionario, podemos usar este algoritmo:

Abrimos el diccionario por la mitad para determinar que mitad contiene la palabra buscada.

Teniendo la mitad elegida, la abrimos nuevamente por la mitad, para determinar que cuarta parte contiene la palabra buscada.

Si repetimos este proceso, podemos encontrar rapidamente la palabra buscada pues reducimos las posibles zonas donde se encuentra la palabra buscada.

 

Sea el array A que inicialmente debe estar ordenado de manera ascendente.

 

1259

1470

1554

1789

1790

1891

1956

2001

2345

2567

3200

1 2 3 4 5 6 7 8 9 10 11

 

Se busca el elemento 1956.

Las variables LI y LS indican los limites superior e inferior del intervalo de búsqueda

Se empieza con : LI = 1 y LS = 11

Se examina el elemento central: c = (1+11)/2 = 6

1259

1470

1554

1789

1790

1891

1956

2001

2345

2567

3200

1 2 3 4 5 6 7 8 9 10 11

LI =1

c= 6 

LS=11

                                                                         

  Como 1956  > 1891 (A[c] ,  nos quedamos con la segunda sublista:

 

           

1956

2001

2345

2567

3200

7 8 9 10 11

LI =7

LS=11

 

LI = c+1   = 7

Se examina el elemento central :    c = ( LI + LS)/2 = 9

 

           

1956

2001

2345

2567

3200

7 8 9 10 11

LI =7

c=9

LS=11

 

Como 2345 > 1956 nos quedamos con la primera sublista

 

           

1956

2001

     
7 8

LI =7

LS=8

 

LS = c -1 = 8

Se examina el elemento central :    c = ( LI + LS)/2 = 7

 

           

1956

2001

     
7 8

c=7

 

Como A[c] es igual al Elemento buscado, entonces sale del lazo while.

Como el elemento buscado es igual al elemento central A[c] al Lug se le asigna c

 

Si el elemento no se encuentra en el arreglo A , llegará un momento en que LS < LI. Esto indica que la busqeuda a sido fallida y en ese caso Lug = 0 (fuera de conjunto de datos de 1 a N 

 

Pseudocodigo

Programa   C++

Algoritmo Busqueda Binaria void main()
INICIO {
o

constante entero N = 11

entero i , ElemB, LI, LS,c, Lug

entero A[N] = {1,5,7,9,12,15,,...., 56,78 }

 

LEER  ElemB

LI = 1      COM:  Lim Inferior de busqueda

LS = N    COM:  Lim Superior de busqueda

c = (LI+LS)/2

Mientras  ((LI<=LS) y (A[c] ¹ ElemB))

{   

    SI ( ElemB < A[c] )

    {    LS = c-1 }      COM:  primera sublista

    sino 

    {    LI  = c+1  }    COM: segunda sublista

    c = entero de ( LI+LS) /2

}

SI  ( ElemB = A[c ] )

{    Lug  = c

     Mostrar  Lug  

}

Sino  

{   Lug = 0

    Mostrar  ElemB, "No se encuentra”  

}

o

const int  N = 11;

int  i , ElemB, LI, LS,c, Lug;

int A[N] = {1,5,7,9,12,15,,...., 56,78 };

 

cin>> ElemB;

LI = 0;           // Lim Inferior de busqueda

LS = N -1;    //  Lim Superior de busqueda

c = (LI+LS)/2;

while  ((LI <= LS)  && ( A[c] != ElemB))

{   

    if  ( ElemB < A[c] )

    {   LS  = c - 1; }      // primera sublista

    else 

    {   LI = c + 1;  }      // segunda sublista

.   c =  (LI+LS)/2;

}

if  ( ElemB == A[c ] )

{    Lug  = c;

     cout<< Lug<<endl;  

}

else  

{    Lug = 0;

     cout<<ElemB<< “ no se encuentra”<<endl;

}

FIN }  

 

ver procedimiento BusquedaBinaria

 

G) Operaciones entre arreglos unidimensionales

 

G1) Sumar

 

    Sumar los elementos de dos arreglos A y B para obtener un tercer arreglo S:      

 

A      En 
A[1] A[2]   A[ i ] .... A[n-1] A[n]
pseudocodigo
1 2   i     n
B      En 
B[1] B[2]   B[ i ] .... B[n-1] B[n]
pseudocodigo
1 2   i   n-1 n

S     En

A[1] + B[1] A[2] + B[2]  

A[i]+B[i]

    A[n] + B[n]
pseudocodigo
1 2   i   n-1 n
 

S [ i ] = A [ i ] + B [ i ]

// a cada elemento A[i] se le suma el respectivo elemento B[i]

 

G2) Restar

  Restar los elementos de dos arreglos A y B para obtener un tercer arreglo R:

 

A      En 
A[1] A[2]   A[ i ] .... A[n-1] A[n]
pseudocodigo
1 2   i     n
B      En 
B[1] B[2]   B[ i ] .... B[n-1] B[n]
pseudocodigo
1 2   i   n-1 n

R     En

A[1] - B[1] A[2] - B[2]  

A[i]-B[i]

    A[n] - B[n]
pseudocodigo
1 2   i   n-1 n
 

R [ i ] = A [ i ] - B [ i ]

// a cada elemento A[i] se le resta el respectivo elemento B[i]

 

    
Programas en C++ para sumar y restar arreglos unidimensionales 
Suma Arreglos resta  Arreglos

void main()

{

   const int N=20;

    // Declaración de Variables

   int  i;

   double A[N], B[N] S[N];

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( i= 0 ;  i < N ; i =i+1  )

   {  // suma elemento por elemento

       S[i] = A [ i ] + B[i] ;  

   }

   ....  // Muestra arreglo S

}

void main()

{  

   const int N=20;

    // Declaración de Variables

   int   i;

   double  A[N], B[N], R[N];

   ........ // Leer o inicializar Arreglo A

   .......  // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( i= 0 ;  i < N ; i =i+1  )

   {   // Multiplica elmento por elemento 

        R [i] = A [ i ] - B[i] ;  

   }

   ......  // Muestra arreglo R

}

 

G3) Multiplicar arreglo unidimensional por un escalar

  Multiplicar  cada elemento del arreglo A por un escalar K:          

 

A      En
A[1] A[2]   A[i] .... A[n-1] A[n]
pseudocodigo
1 2   i     n

C     En

k*A[1] k*A[2]  

k *A[i]

    k*A[n]
pseudocodigo
1 2   i   n-1 n
 

 

C[i]  = k * A[i]

 

// cada elemento de A[i] es multiplicado por el escalar k

 

           

G4) Multiplicar arreglos unidimensionales

Multiplicar los elementos de dos arreglos A y B para obtener un tercero P:

 
A      En 
A[1] A[2]   A[ i ] .... A[n-1] A[n]
pseudocodigo
1 2   i     n
B      En 
B[1] B[2]   B[ i ] .... B[n-1] B[n]
pseudocodigo
1 2   i   n-1 n

P     En

A[1] * B[1] A[2] * B[2]  

A[i]*B[i]

    A[n] * B[n]
pseudocodigo
1 2   i   n-1 n
 

P [ i ] = A [ i ] * B [ i ]

// a cada elemento A[i] se le multiplica por su respectivo elemento B[i]

 

 

Programas en C++ para multiplicar arreglos unidimensionales entre si y por un escalar
MULTIPLICA POR ESCALAR MULTIPLICA  Arreglos

void main()

const int N=20;

    // Declaración de Variables

   int  i;

   double A[N],C[N], k ;

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

   .......   // Leer o inicializar  k 

    // Recorrido del Array A

   for ( i= 0 ;  i < N ; i =i+1  )

   {  // suma elemento por elemento

       C[ i ] = k * A [ i ] ;  

   }

   ....  // Muestra arreglo A

}

void main()

const int N=20;

    // Declaración de Variables

   int   i;

   double  A[N], B[N], P[N];

   ........ // Leer o inicializar Arreglo A

   .......  // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( i= 0 ;  i < N ; i =i+1  )

   {    // Multiplica elmento por elemento 

        P [ i ] = A [ i ] * B[i] ;  

   }

   ......  // Muestra arreglo M

}

 

G5) Mezcla o intercalación 

 Combinar dos listas en una sola.

 

 

Vectores Originales:

A  
3 4 7 19
   
1 2 3 4
B  
-5 0 4 13 17 19 90 95
   
1 2 3 4 5 6 7 8
C  
                       
   
1 2 3 4 5 6 7 8 9 10 11 12

 

Ver proceso de mezcla_algoritmos

 

Vectores Mezclados:

 

A     
3 4 7 19
   
   
1 2 3 4
   
B  
-5 0 4 13 17 19 90 95
r varía desde j=7 hasta 8
   
1 2 3 4 5 6 7 8
   
C

k = k+1=9

-5

0

3

4

7

13

17

19

90 95    
  k = k+1=10
1 2 3 4 5 6 7 8 9 10 11 12

 

Ver proceso de mezcla_c++ 

 

 

Programas en algoritmos y en C++ para la mezcla de los vectores A y B, se obtiene el vector mezcla C
algoritmo programa c++

INICIO

   constante entero M=4,N=8

    // Declaración de Variables

   entero  i , j , k , r 

   real A[M],B[N],C[M+N] ;

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    COM: Inicializa i , j ,k

   i=1,  j=1,  k=0

   Mientras ((i<=M) y (j<=N))

   {

      k=k+1

      si (A[ i ] < B[ j ])

      {   C[ k ] = A[ i ]

           i = i +1

      }

      sino

      {    C[ k ] = B[ j ]

           j = j +1

      }

   }

   si (i<=M)

   {

      para(r=i hasta M, r=r+1)

      {   k=k+1

          C[ k ] = A[ r ]

      }

   }

   sino

   {   

      para(r=j hasta N, r=r+1)

      {   k=k+1

          C[ k ] = B[ r ]

       }

   } 

   COM: Muestra arreglo C intercalado o mezclado

   para(i=1, hasta k, i=i+1)

      {   cout<< C[ k ]<<"  ";  }

FIN

INICIO

   const int M=4,N=8;

    // Declaración de Variables

   int  i , j , k , r 

   double A[M],B[N],C[M+N] ;

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    // Inicializa i , j ,k

   i =1;  j =1;  k = 0;

   while (( i < M ) && ( j< N ))

   {  k=k+1;

      if ( A[ i ] < B[ j ] )

      {   C[ k ] = A[ i ];

           i = i +1;

      }

      else

      {   C[ k ] = B[ j ];
           if (A[ i ] == B[ j ])
              { i=i+1; j=j+1;}

           j = j +1;

      }

   }

   if ( i < M)

   {

      for(r= i ;r< M; r=r+1)

      {   k = k+1;

          C[ k ] = A[ r ];

      }

   }

   else

   {   

      for (r= j ;r< N; r=r+1)

      {   k = k +1;

          C[ k ] = B[ r ];

      }

   }

   // Muestra arreglo C intercalado o mezclado

   for (i=0; i<= k, i=i+1)

      {   cout<< C[ k ]<<"  ";  }

   cout<<endl;getch();

}

 

Ejemplo - Aplicación:  El administrador de una embotelladora utiliza los arreglos UVMan y UVTar para almacenar las unidades vendidas (cajas) en la mañana y tarde respectivamente y en el arreglo PreUni se almacena el precio de venta de cada unidad (cajas) de producto.  Hacer un algoritmo y su programa respectivo en C++ para calcular las unidades vendidas en todo el dia y a cuanto asciende la venta en soles por cada producto. Se comercializan 10 variedades de productos.

 

ALGORITMO  Ventas PROGRAMA  Ventas
   
INICIO {
o

COM: declaracion de variables

entero  UVMan[10], UVTar[10]; entero  UVDia[10], VenTotD

real  PreUni[10], VentaD[10]

o

//  declaracion de variables

int  UVMan[10], UVTar[10]; 

int  UVDia[10], VenTotD;

double  PreUni[10], VentaD[10];

 

COM: Lectura del arreglo UVMan

para ( i= 1 hasta  120 ,i=i+1 )

{    LEER  UVMan [ i ]  }  

 

/ Lectura del arreglo UVMan

for ( i= 0 ; i<10 ; i=i+1 )

{    cin>>  UVMan [ i ];  }  

 

COM: Lectura del arreglo UVTar

para ( i= 1, hasta  120, ,i=i+1 )

{    LEER  UVTar [ i ]    }  

 

// Lectura del arreglo UVTar

for ( i= 0; i <10 ; i=i+1 )

{    cin>>  UVTar [ i ];    }  

 

COM: Lectura del arreglo PreUni

para ( i= 1 hasta  120 ,i=i+1 )

{    LEER  PreUni [ i ]   }

 

// Lectura del arreglo PreUni

for ( i= 0; i <10 ; i=i+1 )

{    cin>>  PreUni [ i ];    }  

 

COM: Calculo del arreglo UVDia que almacena  las unidades vendidas en el dia

para ( i= 1 hasta  120 ,i=i+1 )

{  // Visita cada uno de los elemento de los arreglos

   UVDia[i] = UVMan[ i ]+UVTar[i];   

}

 

COM: Calculo del arreglo UVDia que almacena  las unidades vendidas en el dia

for ( i= 0; i <10 ; i=i+1 )

{  // Visita cada uno de los elemento de los arreglos

   UVDia [ i ] = UVMan [ i ] + UVTar [ i ];   

}

 

COM:  Calculo dle arreglo VentaDia que almacena la venta del dia en soles en c/u de los productos.

para  ( i= 1, hasta  10 ,i=i+1 )

// Visita cada elemento i  

    VentaD[i]=UVDia[i] * PreUni[i]        }

 

//  Calculo dle arreglo VentaDia que almacena la venta del dia en soles en c/u de los productos.

for ( i= 0; i <10 ; i=i+1 )

// Visita cada elemento i  

    VentaD[i]= UVDia[i]*PreUni[i];        }

 

COM: Calculo de la VentaTotal del dia en soles VenTotDia

VenTotD= 0

para ( i= 1 hasta 10 ,i=i+1 )

{  // Visita al elemento , acumula

     VenTotD =VenTotD +VentaD[ i]   

}

Mostrar VenTotD

 

// Calculo de la VentaTotal del dia en soles VenTotDia

VenTotD= 0

for ( i= 0; i <10 ; i=i+1 )

{  // Visita al elemento , acumula

     VenTotD =VenTotD + VentaD[ i ];  

}

cout<< VenTotD<<endl;

FIN }  

 

 

Los arreglos paralelos son arreglos unidimensionales de igual tamaño donde los elementos de igual indice estan relacionados entre si.  Es decir, permite almacenar información de diferente tipo relacionado. 

Por ejemplo si queremos mostrar los nombres, sexo, edad, telefono y direccion de los empleados de una empresa.  

 

Indices en

C++ / Algoritmo

Nombres Edad Sexo Telefono
0 1
1 2
....

....

.... ....
n-2 n-1
n-1 n
"Edgar F. C."
"Miura F. G"
 
"André F. G"
"Gladys G".
"Herminia V".
 40
12
 
16
40
56
'M'
'F'
 
'M'
'F'
'F'
807-4567
456-7890
 
567-8090
345-6780
245-7809

 

Sin embargo la mayoria de los lenguajes de programación indorporan estructura tipo registro dentro del lenguaje, que facilita la manipulación de datos como el mencionado. El C++ tiene la estructura de dato struct que permite aquello.

 

 

 
          Operaciones:
 
 
...  Piense en algunos  ejemplos de arreglos bidimensionales 

Fig. 4.7.  Ejemplos de arreglos bidimensionales

Se puede considerar como un vector de vectores. Por tanto es un conjunto de elementos todos del mismo tipo en el que se utilizan dos subíndices para especificar un elemento.

Ejm  Una cadena de tiendas está formada por 10 sucursales y cada uno consta de 5 secciones (Lacteos/Bebidas/... /carnes). En la siguiente tabla o matriz (matemático) se representan las ventas mensuales en soles.

 

 

Secciones

0 1 .... 3 4
1 2 ... 4 5
VENTAS
Sucursales

Los indices en psuedocodigo y en C++

0 1
1 2
 
 
4 5
5 6

2400 

3600   5600 7200   3100
1800 5120 3490 5690 5670 
... ... ... ... ...
... ... ... ... ...
3490 3460  5671 4567  5423
1780 3450 6740 4356 3210

     

En un array bidimensional cada elemento del array se referencia a través de dos índices.

En pseudocodigo :

VENTAS [1] [2] =3600     VENTAS [2][4] = 5690
En C++  

VENTAS [0] [1] =3600     VENTAS [1][3] = 5690

 

 

EJEMPLO DE DECLARACION DE ARREGLOS BIDIMENSIONALES
EN ALGORITMOS (seudocódigo) y en C++  (código) respectivamente
real   nota[25][4]

declara nota, las 4 notas de cada uno de los 25 alumnos. Reserva celdas de memoria.para 100 datos double

double  nota[25][4];
 
real   Peso[20][12] declara Peso, los pesos promedios de 30 deportistas en cada uno de los 12 meses del 2001. Reserva celdas de memoria para 240 datos double.
double   Peso [20][12];
entero  DocCasacas[3][30] declara DocCasacas, las docenas de casacas de 3 tallas ('S', 'M','L') confeccionadas en cada uno de los 30 dias del mes de Junio.  Reserva celdas de memoria para 90 datos iint. 
int   DocCasacas[3][30];
entero   unidInsumo[5][12] declara unidInsumo, las unidades de 5 variedades de insumo comprados en cada uno de los 12 meses del 2000  Reserva celdas de memoria para 60 datos int
int   unidInsumo[5][12];
caracter  Rpta[45][10] declara Rpta, las respuestas de 45 alumnos a 10 preguntas de opcion muiltiple ('a',...'e'). Reserva celdas de memoria para 450 datos char.
char   Rpta[45][10];

     

                        

 

A) Inicialización de Matrices 

    Al igual que con las variables simples (no estructurados) y los vectores, las matrices  se pueden inicializar al momento de declararse. Ejm:

 

Ejemplos de declaración e inicialización de arreglos bidimensionales en algoritmos (pseudocódigo) y en C++

real   nota[25][4] = { {12.5, 5.5, 7,14}, {10,16,17,10,5), ...., {15,17,19,19.5} } double nota[25][4] = { {12.5, 5.5, 7,14}, {10,16,17,10,5), ...., {15,17,19,19.5} }
real nota[25][4]={ 12.5, 5.5, 7,14, 10,16,17,10,5, ...., 15,17,19,19.5 } double nota[25][4]={ {12.5, 5.5, 7,14}, {10,16,17,10,5), ...., {15,17,19,19.5} }
real nota[ ][4]={ {12.5, 5.5, 7,14}, {10,16,17,10,5), ...., {15,17,19,19.5} } double nota[ ][4]={ {12.5, 5.5, 7,14}, {10,16,17,10,5), ...., {15,17,19,19.5} }

nota declara e inicializa las 4 notas de cada uno de los 25 alumnos.(total 100 notas, agrupadas de 4)

Puede omitirse el tamaño de la primera dimension pero no la segunda. Total 100 datos reales.

 

real Peso[20][12] = { {50.5, 70,80,80.6,90,67.5,45.7, 78.5, 90,110,56.7,89},  ...., {.....} } double Peso[20][12] = { {50.5, 70,80,80.6,90,67.5,45.7, 78.5, 90,110,56.7,89},  ...., {.....} }
real Peso[20][12] = { 50.5, 70,80,80.6,90,67.5,45.7, 78.5, 90,110,56.7,89},  ...., ..... } double Peso[20][12] = { 50.5, 70,80,80.6,90,67.5,45.7, 78.5, 90,110,56.7,89},  ...., ..... }
real Peso[ ][12] = { {50.5, 70,80,80.6,90,67.5,45.7, 78.5, 90,110,56.7,89},  ...., {.....} } double Peso[ ][12] = { {50.5, 70,80,80.6,90,67.5,45.7, 78.5, 90,110,56.7,89},  ...., {.....} }
Peso declara e incializa los pesos promedios de 30 deportistas en cada uno de los 12 meses del 2001.(total 240 pesos agrupados de 12 en 12).  Total 240 datos reales
entero  DocCasacas[3][4]= {{20,40,35,80}, {25,70,50,36}, {48,36,64,24}} int  DocCasacas[3][4]={{20,40,35,80}, {25,70,50,36}, {48,36,64,24}};
entero  DocCasacas[3][4]={20,40,35,80,25,70,50,36, 48,36,64,24} int  DocCasacas[3][4]={20,40,35,80, 25,70,50,36, 48,36,64,24};
entero  DocCasacas [ ][4] ={{20,40,35,80},{25,70,50,36}, {48,36,64,24}} int  DocCasacas[ ][4]={{20,40,35,80}, {25,70,50,36}, {48,36,64,24}};
declara e incializa DocCasacas, las docenas de casacas de 3 tallas ('S', 'M','L') confeccionadas en cada una de los 4 semanas del mes de Junio-2002
   
caracter  Rpta[3][4]= { {'a','e','c','d'}, {'e','c','d','a'}, {'c','c','d','c'} } char Rpta[5][4]= { {'a','e','c','d'}, {'e','c','d','a'}, {'c','c','d','c'} };
caracter  Rpta[3][4]={'a','e','c','d','e','c','d','a',  'c','c','d','c' } char Rpta[5][4]={'a','e','c','d','e','c','d','a',  'c','c','d','c' };
caracter  Rpta[ ][4]={'a','e','c','d', 'e','c','d','a', 'c','c','d','c' } char Rpta[ ][4]={'a','e','c','d', 'e','c','d','a', 'c','c','d','c' };
declara e inicializa Rpta, las respuestas de 3 alumnos a 4preguntas de opcion muiltiple ('a',...'e'). Reserva celdas de memoria para 12 datos char. Total de 12 datos 3 grupos agrupados de 4 en 4.
   
entero A[2][4] = {{1,2},{3,4}} es igual a: int A[2][4] = {{1,2},{3,4}};  es igual a:
entero A[2][4] = {{1,2,0,0},{3,4,0,0}}  int A[2][4] = {{1,2,0,0},{3,4,0,0}} ;
A Declara e inicializa un arreglo A con 8 elementos, 

 

B)  Asignación 

 Permite dar valor a uno o varios  elementos de un vector.

Asignación de valores a los elementos de un vector.  En algoritmos (pseudocódigo) y en C++

entero  A[15][30];

int  A[15][30];

caracter  Rpta [50] [10];

char  Rpta [50][10];

A[10] [20] = 45 A[10] [20] = 45;
Asigna el valor 45 al elemento de la fila 10 y columna 20 del arreglo bidimensional A.
 
Rpta [2][5] = 'c' Rpta [2][5] = 'c';
Asigna 'c'  al elemento de la fila 2 y columna 5 del arreglo Rpta

 

C) Operaciones de Entrada/Salida 

Lectura/Escritura .- Permite dar  valor (leer o ingresar por teclado) o mostrar (en pantalla) el valor de los elementos de un arreglo bidimensional   Ejm:    

Lectura / Escritura de elementos de un arreglo bidimensional en pseudocódigo y en C++ respectivamente
Leer V[3][5] Permite Leer el elemento de la fila 3 y columna 5 del arreglo bidimensional V
cin>> V[3] [5] ;
 

Mostrar V[3][5]

Permite Mostrar el elemento de la fila 3 y columna 5 del arreglo bidimensional V

cout<< V[3] [5];

 
Lectura / Escritura de los elementos de un arreglo por grupos en pseudocódigo y en C++ respectivamente

constante entera M = 10, N=12; 

entero  V[10][12]

const int M=10, N=12;

int  V[10][12];

real Peso[M][N]

double Peso[M][N];

para (i = 1 ; hasta   i <= M ; con   i=i+1)

{     para (j=1 hasta j <=N ; con j=j+1)

       {   Leer   V [ i ][ j ];    }

}

Lee los elementos de la matriz V cuyo indice i varia desde 1 hasta M, y j varia desde 1 hasta N.

Nota: M y N deben ser conocidos.

for (i = 0 ;  i < M ;  i=i+1)

{    for ( j = 0 ;  j < N ;  j=j+1)

       cin>> V [ i ][ j ];    }

}

En C++: Lee los elementos de la matriz V cuyo indice i varia desde 0 hasta M-1 y j varia desde 1 hasta N-1.  

Nota  M y N debe ser conocido.

   

para (i = 1 ; hasta  i<= M ; con   i=i+1)

{      

       para (j=1 hasta j <=N ; con j=j+1)

       {  Mostrar  Peso [ i ][ j ]; }

}

Muestra los elementos de la matriz V cuyo indice i varia desde 1 hasta M, y j varia desde 1 hasta N.

Nota: M y N deben ser conocidos.

for (i = 0 ;   i< n ; i = i+1)

{   

     for (j = 0 ;   j< n ; j = j+1)

     {   cout<< Peso [ i ][ j ]; }

}

En C++: Muestra los elementos de la matriz V cuyo indice i varia desde 0 hasta M-1 y j varia desde 1 hasta N-1. 

Nota  M y N debe ser conocido.

Ejemplo:

Ejemplo:

entero  V[5][3]

real Peso[5][3]

int  V[5[13];

double Peso[5][3];

para (i = 0 ; i< 5 ; i = i+1)

{   para ( j = 0 ; j< 3 ; j = j+1)

    Leer  V [ i ][ j ];     }

}

Permite ingresar por teclado  los valores para cada elemento del arreglo V:

V[0][0],  V[0][1], V[0][2], V[1][0] , V[1][1], V[1][2], V[2][0], V[2][1], V[2][2], V[3][0], V[3][1], V[3][2], V[4][1], V[4][2], V[4][3]

for (i = 0 ; i< 5 ; i = i+1)

{   for ( j = 0 ; j< 3 ; j = j+1)

    cin>>  V [ i ][ j ];     }

}

Permite ingresar por teclado  los valores para cada elemento del arreglo V:

V[0][0],  V[0][1], V[0][2], V[1][0] , V[1][1], V[1][2], V[2][0], V[2][1], V[2][2], V[3][0], V[3][1], V[3][2], V[4][1], V[4][2], V[4][3]

Ejemplo Ejemplo

para (i = 1 ; Hasta   i<= 5 ; con   i=i+1)

{   para (j = 1;hasta j<= 3 ; con j=j+1)    

    {  Mostrar  Peso [ i ][ j ];    }

}

Muestra en pantalla los valores almacenados en cada elemento del arreglo:   Peso[1][1], Peso[1][2]  Peso[1][3], Peso[2][1], Peso[2][2], Peso[2][3] ,Peso[3][1]  Peso[3][2], Peso[3][3], Peso[4][1], Peso[4][2]  Peso[4][3], Peso[5][1], Peso[5][2], Peso[5][3]  

for (i = 0 ; i< 5   i = i+1)

{   for ( j = 0 ; j< 3 ; j = j+1)

    {  cout >> Peso [ i ][ j ];    }

}

Muestra en pantalla los valores almacenados en cada elemento del arreglo:   Peso[0][0], Peso[0][1]  Peso[0][2], Peso[1][0], Peso[1][1], Peso[1][2] ,Peso[2][0]  Peso[2][1], Peso[2][2], Peso[3][0], Peso[3][1]  Peso[3][2], Peso[4][0], Peso[4][1], Peso[4][2] 

 

D) Operaciones de acceso a los arreglos 

D1) Recorrido ( barrido o visitado ) .- Procesamiento que permite el acceso a todos y cada uno de los elementos del arreglo bidimensional..

Asi se puede recorrer todo un arreglo bidimensional para los procesos de: 

Ejm:  generico de Recorrido Recorrido del arreglo bidimensional A con M filas y N columnas valores conocidos (ingresados por teclado o asignados). El algoritmo recorre al arreglo realizando la operación PROCESO a cada uno de los elementos del arreglo. a) Use estructura repetitiva para.

Algoritmo  RECORRIDO Programa RECORRIDO C++

INICIO

    COM:  Declaración de Variables

   constante entero M = 10, N=6

   entero i, j

   real    A [M][N] 

    COM:  Recorrido del Array A

   para ( i= 1 ; hasta M ; i =i+1)

   {   Para (j=1; hasta N;j=j+1)

       {  COM:  Visita cada elemento A[i][j]

          PROCESA a A [ i ][j]

       }          

   }

FIN

{

    // Declaración de Variables

   const int  M = 10, N=6;

   int  i, j;

   double   A [M][N] ;

    //  Recorrido del Array A

   for ( i= 0 ; i < M ; i =i+1 )

   {   for (j=0; j < N ; j=j+1)

        {   // Visita al elemento A[i]

            PROCESA a A [ i ] [j]         

        }

   }

}

Nota procesa cambia de acuerdo a los requerimientos del problema.  Haga clic alli.  

PROCESA   puede ser :

  • Leer (cin>>) cada elemento del arreglo bidimensional.
  • Mostrar (cout<<) cada elemento del arreglo bidimensional
  • Acumular los elementos A[i][ j ] 
  • Si es igual a algun valor contar o mostrar el elemento A[ì] [j]
  • Calcular el minimo y el maximo valor del arreglo bidimensional A

 

 

E) Operaciones entre arreglos Bidimensionales

 

E1) Sumar Matrices:

Sean las matrices A y B, representadas en matemáticas así: :

Observación: para la suma y resta de matrices, el rango de las matrices A y B deben ser iguales, es decir m x n

 

A                    Columnas

1 2 j n
 

B      Columnas

1 2 j n
1
2
i
m-1
m
A11 A12   A1j   A1n
A21 A22   A2j   A2n
           
           
Ai1 Ai2   Aij   Ain
           
Am-11 Am-12   Am-1j   Am-1n
Am1 Am2   Amj   Amn

   +

B11 B12   B1j   B1n
B21 B22   B2j   B2n
           
           
Bi1 Bi2   Bij   Bin
           
Bm-11 Bm-12   Bm-1j   Bm-1n
Bm1 Bm2   Bmj   Bmn

 

La matriz suma será:

S

Columnas
1 2 j n

1

2

i

m-1

m

A11+ B11 A12+ B12 ... A1j+ B1j ... A1n+ B1n
A21+ A21 A22+ B22 ... A2j+ B2j ... A2n+ B2n
           
           
Ai1+ Bi1 Ai2+ Bi2 ... Aij+Bij .. Ain+ Bin
           
Am-11+ Bm-11 Am-12+ Bm-12 ... Am-1j+ Bm-1j ... Am-1n+ Bm-1n
Am1+ Bm1 Am2+ Bm2 ... Amj+ Bmj ... Amn+ Bmn

La instrucción representativa para cada elemento de la matriz suma S, será:

En Matemáticas:   

  Sij  =  Aij  +  Bij  

En algoritmos y en C++   

  S [ i ] [ j ]  = A[ i ] [ j ] + B[ i ] [ j ] 

Se repite para cada elemento de la matriz S

 

E2) Restar Matrices:

  La matriz Resta será :

R

Columnas
1 2 j n
1
2
i
m-1
m
A11-B11 A12-B12   A1j-B1j   A1n -B1n
A21-A21 A22-B22   A2j-B2j   A2n-B2n
           
           
Ai1-Bi1 Ai2-Bi2   Aij-Bij   Ain-Bin
           
Am-11-Bm-11 Am-12-Bm-12   Am-1j-Bm-1j   Am-1n-Bm-1n
Am1-Bm1 Am2-Bm2   Amj-Bmj   Amn-Bmn

La instrucción representativa para cada elemento de la matriz  resta R será:

En Matemáticas:   

  Rij  =  Aij  +  Bij  

En algoritmos y en C++   

  R [ i ] [ j ]  = A[ i ] [ j ]  B[ i ] [ j ] 

Se repite para cada elemento de la matriz R

 

Programas en C++ para sumar y restar arreglos Bidimensionales 
Suma Arreglos resta  Arreglos

void main()

{

   const int M=4, N=5;

    // Declaración de Variables

   int  i;

   int A[M][N], B[M][N], S[M][N];

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( i= 0 ;  i < M ; i =i+1  )

   {   

      for (j=0 ; j < N ; j=j+1)

      { // suma elemento por elemento

          S[i] = A [ i ] + B[i] ;  

        }

   }

   ....  // Muestra arreglo S

}

void main()

{

   const int M=4, N=5;

    // Declaración de Variables

   int  i;

   int A[M][N], B[M][N], R[M][N];

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( i= 0 ;  i < M ; i =i+1  )

   {   

       for (j=0 ; j < N ; j=j+1)

       { // suma elemento por elemento

             R[i] = A [ i ] - B[i] ;  

          }

   }

   ....  // Muestra arreglo S

}

 

 

E3) Multiplicar escalar por  Matriz:

 

 

C

Columnas
1 2 j n
1
2
i
m-1
m
k*A11 k*A12   k*A1j   k*A1n
k*A21 k*A22   k*A2j   k*A2n
           
           
k*Ai1 k*Ai2   k*Aij   k*Ain
           
k*Am-11 k*Am-12   k*Am-1   k*Am-1n
k*Am1 k*Am2   k*Amj   k*Amn

La instrucción representativa para cada elemento de la matriz C, será :

En Matemáticas:   

  Cij  =  k *  Aij   

En algoritmos y en C++   

  C [ i ] [ j ]  = k * A[ i ] [ j ]   

                Se repite para cada elemento de la matriz C

E4) Multiplicar Matrices:

Las características de la matriz A y B deben ser :

Rango de la matriz A :  m x p

Rango de la matriz B :  p x n

Rango de la matriz producto  P  :  m x n

 

 

A      Columnas

1 2 k p
   

B      Columnas

1 2 j n
1
2
i
m-1
m
A11 A12   A1k   A1p
A21 A22   A2k   A2p
           
           
Ai1 Ai2   Aik   Aip
           
Am-11 Am-12   Am-1k   Am-1p
Am1 Am2   Amk   Amp

 *

1
2
k
p
B11 B12   B1J   B1n
B21 B22   B2J   B2n
           
           
Bk1 Bk2   Bkj   Bkn
           
Bp-11 Bp-12   Bp-1j   Bp-1n
Bp1 Bp2   Bpj   Bpn

 

Aquí : Rij  se obtiene multiplicando la fila i de la matriz A por la columna j de la matriz B

Es decir Rij  será   

En matemáticas:

R ij    =    Ai1*B1j+Ai2*B2j+   ...  +Aip*Bpj

           

R ij   =

Aik *B kj

Se repite para cada elemento de la matriz P

 

        

R

Columnas
1 2 j n
1
2
i
m-1
m
R11 R12   R1j   R1n
R21 R22   R2j   R2n
           
           
Ri1 Ri2   Ai1*B1j+Ai2*B2j+...+Aip*Bpj   

Pin

           
Rm-1 1 Rm-1 2   Rm-1 j   Rm-1 n
Rm 1 Rm 2   Rm  j   Rm n

La instrucción representativa para cada elemento de la matriz  R, será :

En algoritmos 

R [ i ] [ j ]  = 0

para  ( k = 1, hasta p,  k=k+1)  

{     R [ i ] [ j ]  =  R [ i ] [ j ] + A[ i ] [ k ] * B[ k ] [ j ]     }

En C++

R [ i ] [ j ]  = 0;

for  ( k = 0; k < p ; k=k+1)  

{     R [ i ] [ j ]  =  R [ i ] [ j ] + A[ i ] [ k ] * B[ k ] [ j ];    }

 

Esto se repite para cada uno de los elementos de la matriz P:

Es decir:

i varia desde 1 hasta m, mientras j varia desde 1 hasta n (en algoritmos)

i varia desde 0 hasta m-1, mientras j varia desde 0 hasta n-1  (en C++)

 

 

Programas en C++ para Multiplicar arreglos Bidimensionales 
Escalar por Matriz producto de matrices

void main()

{

   const int M=4, N=5;

    // Declaración de Variables

   int  i;

   int A[M][N], k, C[M][N];

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( i= 0 ;  i < M ; i =i+1  )

   {   

      for (j=0 ; j < N ; j=j+1)

      { // multiplica elemento por elemento

          C[i][j]  = k * A[i][j] ;  

        }

   }

   ....  // Muestra arreglo S

}

void main()

{

   const int M=4, N=5,P=3;

    // Declaración de Variables

   int  i;

   int A[M][P], B[P][N], R[M][N];

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( i= 0 ;  i < M ; i =i+1  )

   {   

      for ( j=0 ; j < N ; j=j+1)

     R[i][j] = 0;

         for ( k=0 ; k < P ; k=k+1)

         {// acumula elemento por elemento

                R[i][j] = R[i][j] + A[i][k]*B[k][j] ;  

         }

        }

   }

   ....  // Muestra arreglo S

}

 

F) Operaciones de suma de filas y columnas de una matriz

 

F1) Sumar filas - Vector Vertical

 

A

Columnas
1 2 j n

V

1

2

i

m-1

m

A[1][1] A[1][2] ... A[1][j] ... A[1][n]
A[2][1] A[2][2] ... A[2][j] ... A[2][n]
           
           
A[i][1] A[i][2] ... A[i][j] .. A[i][n]
           
A[m-1][1] A[m-1][2] ... A[m-1][j] ... A[m-1][n]
A[m][1] Am2 ... A[m][j] ... A[m][n]
 
 
 
 

V[ i ]

 
 
 

H

     

H[ j ]

   
 
   

 STot

 

Para obtener V[i] que es un acumulador de la toda la fila i, donde j varia de 1 a N (algoritmos)

V[i] = 0

for (j=0 ; j < N ; j=j+1)

// multiplica elemento por elemento

       V[i]  = V[i] + A[ i ][ j ] ;  

}

 

Pero para el calculo del vector V, i varia de 1 a M:

 for ( i= 0 ;  i < M ; i =i+1  )

 {  V[i] = 0; 

      for (j=0 ; j < N ; j=j+1)

      // multiplica elemento por elemento

           V[i]  = V[i] + A[ i ][ j ] ;  

        }

 }

 

 

F2) Sumar Columnas - Vector Horizontal

De manera similar para el calculo de H[j]:

Para obtener H[j] que es un acumulador de la toda la columna j, donde i varia de 1 a M (algoritmos)

for ( i=0 ; i < M ; i=i+1)

{   // acumula elemento por elemento

         H [ j ] = H [ j ] + A [ i ][ j ] ;  

}

 

Pero para el calculo del vector V, i varia de 1 a M:

 for ( j= 0 ;  j < N ; j = j+1  )

 {    H[ j ] = 0; 

      for (i=0 ; i < M ; i= i+1)

      // multiplica elemento por elemento

           H[ j ]  = H[ j ] + A [ i ][ j ] ;  

        }

 }

 

Programas en C++ Calculos de Vectores Horizontal y vertical a partir de   arreglo Bidimensional
CALCULO DEL VECTOR VERTICAL CALCULO DEL VECTOR HORIZONTAL

void main()

{

   const int M=4, N=5;

    // Declaración de Variables

   int  i;

   int A[M][N], k, V[M];

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( i= 0 ;  i < M ; i =i+1  )

   {  V[i] = 0; 

      for (j=0 ; j < N ; j=j+1)

      // multiplica elemento por elemento

           V[i]  = V[i] + A[ i ][ j ] ;  

        }

   }

   ....  // Muestra arreglo V[]

}

void main()

{

   const int M=4, N=5;

    // Declaración de Variables

   int  i;

   int A[M][N], H[N];

   ........  // Leer o inicializar Arreglo A

   .......   // Leer o inicializar  Arreglo B 

    // Recorrido del Array A

   for ( j=0 ; j < N ; j=j+1)

   {   H [ j ] = 0;

       for ( i=0 ; i < M ; i=i+1)

         {// acumula elemento por elemento

                H [ j ] = H [ j ] + A [ i ][ j ];  

         }

        }

   }

   ....  // Muestra arreglo H[]

}

 

 

 

ENLACES - BIBLIOGRAFIA 
Arreglos

 

 

 

Cap3