Definir estructura de datos. Identificar los arreglos dentro de la clasificación de los tipos de datos más frecuentes en los

diversos lenguajes de programación. Definir un arreglo Identificar las características basicas de un arreglo. Enunciar y diferenciar los diferentes tipos de arreglos

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 más 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?

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 más 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

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.

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

Definir un arreglo unidimensional. Saber declarar un arreglo unidimensional de cualquier tipo. Declarar arreglos unidimensionales en el contexto de un problema, diferencinadolos de los

datos simples. Conocer, citar y utilizar las reglas que definen un arreglo unidimensional.

Operaciones:

Citar los diferentes tipos de operaciones que se pueden realizar sobre los arreglos unidimensonales.

Saber Inicializar arreglos unidimensionales de diversos tipos. Saber asignar o dar valores a los elementos de un arreglo unidimensional. Saber leer y mostrar todo un arreglo unidimensional. Identificar los procesos para solucionar un problema que requiera de recorrido, visitado o

barrido de un arreglo unidimensional. Sumar los elementos numericos de un arreglo. Conocer y aplicar los algoritmos para calcular el minimo y maximo valor de un arreglo

unidimensional. Diseñar el desarrollo de problemas que requieran sumar o restar arreglos.

Diseñar el desarrollo de problemas que requiera multiplicar un arreglo unidimensional por un escalar y multiplicar arreglos unidimensionales.

Conocer el algoritmo para borrar o insertar un elemento en un arreglo unidimensional. Conocer y emplear el algoritmo burbuja para clasificar arreglos unidimensionales de tipo

numerico y/o cadenas.

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:

· El nombre del arreglo.

· El tipo de los datos del arreglo

· El conjunto de índices del arreglo(tamaño).

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

La importancia de mantener nuestros arreglos ordenados radica en que es mucho más rápido tener acceso a un dato en un arreglo ordenado que en uno desordenado.

Existen muchos algoritmos para la ordenación de elementos en arreglos, enseguida veremos algunos de ellos.

a)Selección Directa

Este método consiste en seleccionar el elemento más pequeño de nuestra lista para colocarlo

al inicio y así excluirlo de la lista.

Para ahorrar espacio, siempre que vayamos a colocar un elemento en su posición correcta lo intercambiaremos por aquel que la esté ocupando en ese momento.

El algoritmo de selección directa es el siguiente:

i <- 1 mientras i<= N haz min <-i j <- i + 1 mientras j <= N haz si arreglo[j] < [min] entonces min <-j j <- j + 1 intercambia(arreglo[min],arreglo[i])

Ordenación en Arreglos

i <- i +1

b)Ordenación por Burbuja

Es el método de ordenación más utilizado por su fácil comprensión y programación, pero es

importante señalar que es el más ineficiente de todos los métodos .

Este método consiste en llevar los elementos menores a la izquierda del arreglo ó los mayores a la derecha del mismo. La idea básica del algoritmo es comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.

i <- 1 mientras i < N haz j <- N mientras j > i haz si arreglo[j] < arreglo[j-1] entonces intercambia(arreglo[j],arreglo[j-1]) j < j - 1 i <- i +1

c)Ordenación por Mezcla

Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la

mitad derecha y mezclar las dos mitades ordenadas en un array ordenado. Este último paso

consiste en ir comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el

valor más pequeño en el siguiente hueco.

procedimiento mezclar(dat,izqp,izqu,derp,deru) inicio izqa <- izqp dera <- derp ind <- izqp mientras (izqa <= izqu) y (dera <= deru) haz si arreglo[izqa] < dat[dera] entonces temporal[ind] <- arreglo[izqa] izqa <- izqa + 1 en caso contrario temporal[ind] <- arreglo[dera] dera <- dera + 1 ind <- ind +1 mientras izqa <= izqu haz temporal[ind] <- arreglo[izqa] izqa <- izqa + 1 ind <- ind +1 mientras dera <= deru haz temporal[ind] <=dat[dera] dera <- dera + 1 ind <- ind + 1 para ind <- izqp hasta deru haz arreglo[ind] <- temporal[ind] fin

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 más grande está 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 más grande está en la posición 7

Paso 3:

Objetivo: Obtener el más 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 más grande está en la posición 6

Paso 4:

Objetivo: Obtener el más 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 más grande está en la posición 5

Paso 5:

Objetivo: Obtener el más 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 más grande está en la posición 4

Paso 6:

Objetivo: Obtener el más 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 más grande está en la posición 3

Paso 7:

Objetivo: Obtener el más 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 más grande está 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 más 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 }

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

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 ) { // suma elemento por elemento

S[i] = A [ i ] + B[i] ; } .... // Muestra arreglo S

}

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))

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

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

{ 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 }

Definir un arreglo bidimensional. Saber declarar un arreglo bidimensional de cualquier tipo. Demostrar como accesar un arreglo unidimensional. Conocer, citar y utilizar las reglas que definen un arreglo bidimensional.

Operaciones:

Citar los diferentes tipos de operaciones que se pueden realizar sobre los arreglos bidimensonales.

Saber inicializar arreglos bidimensionales de diversos tipos. Saber asignar o dar valores a los elementos de un arreglo bidimensional. Saber leer y mostrar todo un arreglo bidimensional. Identificar los procesos para solucionar un problema que requiera de recorrido, visitado o

barrido de un arreglo bidimensional(ejm contar) Conocer y aplicar los algoritmos para calcular el máximo y el minimo valor de un arreglo

bidimensional. Diseñar el desarrollo de problemas que requieran sumar o restar arreglos bidimensionales. Diseñar el desarrollo de problemas que requiera multiplicar un arreglo bidimensional por un

escalar y multiplicar 2 arreglos bdimensionales. Saber sumar filas para obtener el vector vertical a partir de una matriz Saber sumar columnas para obtener el vector horizontal a partir de una matriz

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:

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

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

A11 A12 A1j A1n

A21 A22 A2j A2n

Ai1 Ai2 Aij Ain

+

B11 B12 B1j B1n

B21 B22 B2j B2n

Bi1 Bi2 Bij Bin

m

Am-11 Am-12 Am-1j Am-1n

Am1 Am2 Amj Amn

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

Un subprograma es una serie de instrucciones escritas independientemente del programa principal. Este subprograma está ligado al programa principal mediante un proceso de transferencia/retorno.

Ejemplo 12 • Título: – Subprograma de suma • Nombre – Ej12 • Descripción – Escribir un subprograma que calcule la suma de dos números • V1: función con dos parámetros de entrada y devuelve el resultado • V2: procedimiento con dos parámetros de entrada y uno de salida • V3: procedimiento con un parámetro de entrada y otro de entrada/salida • Observaciones – Ejemplo ilustrativo con cuerpo de cálculo evidente – Paso de parámetros – Los procedimientos no “devuelven” nada (usan parámetros de salida)

¿Que es una función?

Una función es un grupo de instrucciones con un objetivo en particular y que se ejecuta

al ser llamada desde otra función o procedimiento. Una función puede llamarse

múltiples veces e incluso llamarse a sí misma (función recurrente).

Las funciones pueden recibir datos desde afuera al ser llamadas a través de los

parámetros y deben entregar un resultado.

Se diferencian de los procedimientos porque estos no devuelven un resultado.

En general las funciones deben tener un nombre único en el ámbito para poder ser

llamadas, un tipo de dato de resultado, una lista de parámetros de entrada y su código.

Cuando una función es invocada se le pasa el control a la misma, una vez que esta

finalizó con su tarea el control es devuelto al punto desde el cual la función fue llamada.

¿Que es un procedimiento?

Porción de código dentro de un programa más grande, que realiza una tarea específica

y es relativamente independiente del resto del código. La mayoría de los lenguajes de

programación incluyen soporte para la creación de procedimientos (u otros tipos de

subrutinas, como funciones o módulos).

Los procedimientos suelen utilizarse para reducir la duplicación de códigos en un

programa, permitir reusar los códigos, descomponer problemas complejos en piezas

simples (mejorando la mantenibilidad y facilidad de extensión del código), mejora la

lectura del código de un programa, oculta o regula parte de un programa, etc.

Los procedimientos son ejecutados cuando son llamados desde otros procedimientos,

funciones o módulos. Los procedimientos pueden recibir parámetros, pero no necesitan

devolver un valor como las funciones.

Ejemplo 1

Programa que suma dos numeros utilizando un Procedimiento.

Pseudocódigo 1

2

3

4

5

6

Inicio

dN1<-0, dN2<-0

Leer "Numero 1", dN1

Leer "Numero 2", dN2

Llama Suma (dN1)

Fin

1

2

3

4

5

6

//Aqui empieza el procedimiento

Procedimiento Suma (dN1a, dN2a)

dSuma <- 0

dSuma<-0 dN1a+dN2a

Imprimir "El total es: ", dSuma

Fin Procedimiento

Diagrama de Flujo

Vemos que tenemos un nuevo símbolo el cual corresponde a la llamada a un procedimiento o

funcion.

Este es el diagrama correspondiente al principal.

Este es el diagrama correspondiente al procedimiento.

Código

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

#include<iostream.h>

#include<conio.h>

//DECLARACION DE PROCEDIMIENTO

void fSuma(float,float);

//INICIO DEL PRINCIPAL

main()

{

//DECLARACIÓN DE VARIABLES

float dN1,dN2;

//DATOS DE ENTRADA

cout<<"Numero 1:";

cin>>dN1;

cout<<"Numero 2:";

cin>>dN2;

//LLAMADA A PROCEDIMIENTO

fSuma(dN1,dN2);

getch();

}

//INICIO DE PROCEDIMIENTO

void fSuma(float dN1a,float dN2a)

{

//DECLARACIÓN DE VARIABLES

float dSuma;

28

29

30

31

32

33

34

35

//PROCESO

dSuma=dN1a+dN2a;

//SALIDA

cout<<"El total es: "<<dSuma;

}

Ejemplo Ejecutado

Un puntero es una variable que tiene la dirección de memoria de otra variable que contiene un valor.

Gráfica 1. Dirección de memoria.

La dirección es la posición que ocupa en la memoria una variable, un arreglo, una cadena, una estructura, otro puntero, etc. Normalmente las variables contienen valores específicos. En cambio, los punteros contienen direcciones de variables que contienen valores específicos. Si una variable contiene la dirección de otra variable entonces se dice que: “la primera variable apunta a la segunda”. Gráfica 2. Puntero de una variable a otra variable.

En este sentido, los nombres de variables hacen referencia directa a un valor y los punteros hacen referencia indirecta a un valor. La referencia a un valor a través de un puntero se llama indirección. Gráfica 3. Referencia directa e indirecta a una variable.

cont hace referencia directa a una variable cuyo valor es 23 cont hace referencia indirecta a una variable cuyo valor es 23 Existen tres razones para usar punteros en la creación de programas: - Los punteros proporcionan los medios mediante los cuales las funciones modifican sus argumentos de llamada. - Se pueden utilizar para soportar las rutinas de asignación dinámica del C++. - Se puede sustituir por arreglos en muchas situaciones para incrementar la eficacia.

Variable Puntero Sintaxis : tipo *nombre_variable; Propósito : Declarar si una variable contiene una dirección de memoria. Donde tipo puede ser cualquier tipo base del C++, y éste define a que tipo de variable puede apuntar el puntero. Ejemplo : int *punt, k; Esta sentencia declara que punt apunta a un valor u objeto de tipo entero. Cada variable que se declara como puntero debe ir precedida por un *. Los punteros se deben inicializar a 0, a NULL o a una dirección, al declararlos o mediante una asignación, para evitar que apunten a áreas desconocidas de memoria. Operadores Puntero Existen dos operadores especiales de punteros: & : Operador de dirección, devuelve la dirección de memoria de su operando (variable a la que precede). Gráfica 4. Aplicación del operador de dirección.

punt = &cont;

Coloca la dirección de memoria 3500 de la variable cont en punt y la variable puntero punt está ubicada en la dirección 4000. Esta dirección es una posición interna del ordenador y no tiene que ver con el valor de cont. Se lee que punt “recibe la dirección del valor” cont. * : Operador de indirección, es el complemento de &, devuelve el valor de la variable situada en la dirección que sigue (sinónimo de la variable hacia el que apunta su operando). valt = *punt; Si punt contiene la dirección de memoria de la variable cont, entonces coloca el valor de cont en valt. Ejemplo, si cont al inicio tenía el valor 23, entonces, después de esta asignación, valt tendrá el valor 23 ya que es el valor guardado en la posición 3500, que es la dirección de memoria que asignó a punt. Recordar al * como “en la dirección”. Se lee como que valt “recibe el valor de dirección” punt. El proceso que consiste en reportar el valor de una variable precedida por un * se conoce como desreferenciación de un puntero. Ejemplo: cout<<*punt; Esta sentencia reporta el valor de la variable cont, es decir 23. También puede utilizarse un puntero desreferenciado del lado izquierdo de una sentencia de asignación. Ejemplo: *punt = 25; Esta sentencia asigna el valor 25 a la variable cont.

El puntero desreferenciado también puede usarse para recibir un valor de entrada. Ejemplo: cin>>*punt; Como el signo de multiplicación y el de “en la dirección” es el mismo, al escribir un programa, tener en cuenta que estos operadores no tienen relación. & y * tienen una precedencia más alta que el resto de operadores aritméticos. El tipo base del puntero determina el tipo de datos que el compilador asumirá que apunta el puntero. Como punt es un puntero entero, C++ copia dos bytes en valt desde la dirección a la que apunta punt. Expresiones con Punteros a) Se puede usar un puntero en la parte derecha de una sentencia de asignación para asignar el valor del puntero a otro puntero. Ejemplo:

int t, *x, *y; t = 450; x = &t; y = x; cout<<“La dirección es : ”<< y;

Este fragmento de programa visualiza la dirección de t en hexadecimal, y no el valor de t. b) En aritmética convencional el resultado de 3000+2 es 3002. Pero en aritmética de punteros esto no es así, pues si a un puntero se le suma (+) o resta (-) un entero; dicho puntero no aumenta o disminuye en la misma cantidad que el entero, sino en el entero por el número de bytes de la variable hacia la que apunta. Número de bytes depende de tipo de dato de variable. Ejemplo: x += 7; Si la variable x es de tipo entero; entonces, después de esta operación, x apuntará a la dirección 3014 (3000 + 7 * 2), ya que los enteros poseen dos bytes. Si el ejemplo hubiera sido: x – = 4; Entonces x apunta a la dirección 2992 (3000 – 4 * 2). c) Se pueden incrementar (++) o disminuir (- -) punteros. Por ejemplo: sea y un puntero a un número flotante con la dirección actual 3500. Después de la expresión: y++; la dirección de y será 3504 y no 3501. Cada vez que se incrementa y, la computadora apuntará al siguiente flotante, que usa cuatro bytes. Gráfica 5. Variación de un puntero.

d) Es posible asignar un apuntador a otro, si ambos son del mismo tipo. De otro modo, es necesario emplear un operador de conversión mediante cast para convertir el valor del apuntador del lado derecho de la asignación al tipo de apuntador a la izquierda de la asignación. e) Es posible comparar dos punteros en una relación: if(g>h) cout<<“g apunta a dirección más alta que h”; Se usan las comparaciones de punteros, generalmente, cuando dos o más punteros apuntan a un objeto común. f) No se pueden realizar otras operaciones sobre punteros; es decir, no se puede multiplicar o dividir punteros, no se puede sumar o restar dos punteros y no se puede sumar o restar los tipos float o double a punteros. Punteros y Arreglos Como la velocidad es una consideración frecuente en programación, el uso de punteros es más común que el método de indexación de arreglos, debido a que C++ tarda más en indexar un arreglo que lo que hace el operador *. El método de los punteros requiere de las siguientes consideraciones: a) Un nombre de arreglo sin índice, es la dirección del comienzo del arreglo. Es decir, el nombre de un arreglo es un puntero al arreglo. Ejemplo:

char w[50], *x; x = w;

Aquí se pone en x la dirección de 1er. elemento de w. b) Debido a que los índices de arreglos comienzan en cero; para acceder a un determinado elemento de un arreglo; por ejemplo el cuarto elemento de w, se puede escribir:

w[3] ó *(w+3)

c) En el caso del arreglo bidimensional g, cuyos contadores i y j se inicializan a partir de cero, el acceso puede especificarse como:

g[i][j] ó *(*(g + i) + j)

d) Se puede indexar un puntero como si fuera un arreglo: int g[7] = {1, 2, 3, 4, 5, 6, 7}; int j, *x;

x = g; for(j=0; j<7; j++) cout<<x[j];

Aquí se visualiza en la pantalla los números del 1 al 7.

e) El C++ trata a las cadenas como punteros al primer carácter de cadena y no como cadena propiamente dicha

strlen(char *q) { int j = 0; while(*q) { j++; q++; } return j; }

Recordar que toda cadena termina en un nulo (o falso). while(*q) Es verdad hasta que se alcance el final de la cadena. f) Si se quiere acceder al arreglo aleatoriamente, es mejor la indexación, ya que es tan rápido como la evaluación por punteros y porque es más fácil programar. g) Se puede asignar la dirección de un elemento específico de un arreglo aplicando el & a un arreglo indexado: q = &y[7]; Esta sentencia coloca la dirección del octavo elemento de y en q. Esto es útil en la localización de subcadenas.

char w[60],*y; int t; cout<<“Introducir una cadena: ”; gets(w); for(t=0; w[t] && w[t]==’’;t++); y = &w[t]; cout<<y;

Esto imprime el resto de una cadena, que se introdujo por teclado, desde el punto en que la computadora encuentre el primer espacio o el final de la cadena. h) Recordar que el acceso a una cadena individual se especifica solamente con el índice izquierdo. gets(y[i]); Esta sentencia es funcionalmente equivalente a: gets(&y[i][j]); i) Se pueden hacer arreglos de punteros. Ejemplo: int *b[10]; Declara un arreglo de punteros int de tamaño 10. j) Para asignar una dirección de variable entera llamada z al quinto elemento del arreglo de punteros, se escribirá: b[4] = &z; y para encontrar el valor de z se escribirá: *b[4]

Las listas son una sucesión de cero o más elementos.

Esta es una definición muy simple y que no aclara demasiado en términos informáticos, así que profundizaremos un poco más.

Hay varios tipos de listas, las hay enlazadas, no enlazadas, ordenadas y no ordenadas. Nosotros vamos a estudiar las listas enlazadas, tanto ordenadas como no ordenadas.

La diferencia que existe entre las listas enlazadas y las no enlazadas es que las enlazadas utilizan punteros, es decir, asignación dinámica de memoria, lo que optimiza la gestión de la misma. Una lista no enlazada es un simple array, y por lo tanto es un bloque contiguo de memoria, mientras que una lista enlazada es un conjunto de nodos que no tienen porque ocupar posiciones contiguas de memoria.

La diferencia entre listas ordenadas y no ordenadas es obvia, las ordenadas mantienen cierto orden entre sus elementos.

A partir de ahora nos centraremos en las listas enlazadas no ordenadas.

Una lista es una sucesión de nodos en la que a partir de un nodo se puede acceder al que ocupa la siguiente posición en la lista. Esta característica nos indica que el acceso a las listas es secuencial y no indexado, por lo que para acceder al último elemento de la lista hay que recorrer los n-1 elementos previos ( n es el tamaño de la lista).

Para que un nodo pueda acceder al siguiente y la lista no se rompa en varias listas cada nodo tiene que tener un puntero que guarde la dirección de memoria que ocupa el siguiente elemento. De esta forma un nodo se podría representar esquemáticamente así:

En el campo información se almacena el objeto a guardar y el puntero mantendrá la conexión con el nodo siguiente.

De esta forma al ir añadiendo nodos se iría formando una sucesión de nodos encadenados mediante punteros.

Operaciones básicas de las listas

En toda estructura de datos hay dos operaciones que sobresalen por encima del resto: Insertar y borrar. Estas dos operaciones aparecerán en toda estructura de datos, puede que con otro nombre, o con una funcionalidad ligeramente diferente, pero su filosofía será la misma, proporcionar unas operaciones para la construcción de la estructura de datos.

Insertar

La operación insertar consiste en la introducción de un nuevo elemento en la lista.

En una lista no ordenada no es necesario mantener ningún orden, por lo tanto la inserción de elementos se puede realizar en cualquier lugar de la lista, al principio, al final, en una posición aleatoria,...

Generalmente se realiza la inserción de tal forma que la complejidad temporal sea mínima, es decir, que sea una operación sencilla para que se realice en el menor tiempo posible. La operación más sencilla depende de la implementación de la estructura de datos, en unos casos puede ser la inserción al inicio, en otros la inserción al final y en este caso la inserción la realiza en el segundo nodo de la lista.

Si tenemos la lista...

... e insertamos el elemento 0, la lista quedaría de la siguiente forma:

Borrar

La operación borrar consiste en la eliminación de la lista de un elemento concreto. El elemento a borrar será escogido por el programador.

La eliminación en una lista no conlleva ningún trabajo adicional más que el propio de la eliminación del elemento en sí. Para borrar un elemento cualquiera habría que realizar un recorrido secuencial de la lista hasta encontrar el nodo buscado y una vez localizado reestructurar los punteros para saltarse el nodo a borrar y así poder eliminarlo.

Vamos a verlo con un ejemplo. Borrado del elemento 76 en la lista anterior:

Paso 1: Localizar el elemento a borrar.

Paso 2: Reestructurar punteros y eliminar nodo.

Otras operaciones

A partir de estas dos operaciones básicas cada lista puede presentar muchas operaciones diferentes, vamos a comentar algunas de ellas, dejando claro que las dos básicas que siempre aparecerán son las anteriores.

Tamaño: Esta operación suele informar sobre el número de elementos que tiene en ese instante la lista.

Buscar: Comprueba si existe un determinado elemento en la lista. Recorrer lista: Recorre toda la lista, realizando una operación en cada nodo. Por

ejemplo, mostrar el contenido por pantalla.

En este capítulo se definirá el concepto de pilas implementada con arreglo de registros.

Además se describen algunas de sus operaciones más importantes.

Definición

Una PILA es una estructura ordenada y homogénea, en la que podemos apilar o desapilar

elementos en una única posición llamada CIMA, siguiendo una política LIFO (Last In, First

Out).

Pilas

Representación de pilas con arreglos

Utilizaremos un arreglo llamado Pila de tamaño máximo MaxElemPila y una variable llamada

Cima que indicará cual es el último elemento ocupado en el arreglo (es decir la variable Cima

contiene la posición del elemento que se encuentra en la cima de la pila).

Representación de pilas con arreglos

Operaciones

Las operaciones son:

- CrearPila : Inicializa la pila en el estado vacío.

- PilaVacía : Determinar si la pila está vacía.

- PilaLlena : Determina si la pila está llena.

- Apilar : Agrega un nuevo elemento a la pila.

- Desapilar : Elimina el dato que se encuentra en la cima de la pila.

- CimaPila : Permite capturar el elemento que está en la cima de la pila, sin eliminarlo.

Implementación:

Archivo:

- Pilas.vb

- Pilas.cpp

Operación Crear Pila

{

Objetivo : Inicializar al estado vacío.

Entrada : Pila, Cima, MaxElemPila

Precondiciones : Cima correspondiente a una pila

Salida : Cima

Postcondiciones: Pila está vacía. Cima tiene valor inicial de cero

}

Función CrearPila (?Pila, ?Cima, MaxElemPila)

Inicio

Pila = Memoria [MaxElemPila]

Cima = 0

Fin

Operación Pila Vacía

{

Objetivo: Indica si pila está vacía.

Entrada: Cima

Precondiciones: Cima de una pila

Salida: Valor verdadero o falso.

Postcondiciones: PilaVacia es un valor lógico verdadero si pila está vacía y falso en caso

contrario

}

Logico Función PilaVacia (Cima )

Inicio

Si ( Cima == 0 ) entonces

retorna verdadero

Sino

retorna falso

Fin_si

Fin

Operación Pila Llena

{

Objetivo: Indica si pila está llena.

Entrada: Cima, MaxElemPila

Precondiciones: Parámetros de la pila a ser probada

Salida: Valor lógico de la función.

Postcondiciones: valor lógico verdadero si pila está llena y falso en caso contrario

}

Logico Función PilaLlena (Cima, MaxElemPila )

Inicio

Si (Cima ==MaxElemPila) entonces

retorna verdadero

Sino

retorna falso

Fin_si

Fin

Operación Apilar

{

Objetivo: Añade NuevoElemento a la cima de la pila

Entrada: Pila, Cima, NuevoElemento, MaxElemPila

Precondiciones: Pila no está llena

Salida: Pila

Postcondiciones: Pila original con NuevoElemento añadido a la cabeza.

}

Procedimiento Apilar (?Pila, ?Cima, NuevoElemento, MaxElemPila )

Inicio

Si (PilaLlena (Cima, MaxElemPila) == verdadero) entonces

Escribir “Pila llena”

Sino

Cima = Cima + 1

Pila [Cima] = NuevoElemento

Fin_si

Fin

Operación Desapilar

{

Objetivo: Quita el elemento cima de la pila y lo devuelve en ElemSacado.

Entrada: Pila, Cima, ElemSacado.

Precondiciones: Pila no está vacía, ElemSacado no tiene valor

Salida: Pila, Cima, ElemSacado.

Postcondiciones: Pila original con elemento cima quitado. Pila y ElemSacado con valor.

}

Procedimiento Desapilar (?Pila, ?Cima, ?ElemSacado )

Inicio

Si (PilaVacia (Pila,Cima) == verdadero) entonces

Escribir “Pila vacia”

Sino

ElemSacado = Pila [Cima]

Cima = Cima - 1

Fin_si

Fin

Operación CimaPila

{

Objetivo : Captura el elemento que está en la cima de la pila sin eliminarlo.

Entrada : Pila, Cima

Precondiciones : Pila no está vacía

Salida : Pila, Cima, valor de la función

Postcondiciones : Pila original

}

Entero Funcion CimaPila (Pila,Cima)

Inicio

Si (PilaVacia Cima) == verdadero) entonces

Escribir “Pila vacia”

Retorna -1

Sino

retorna Pila [Cima]

Fin_si

Fin

Aplicaciones de pilas

Las Pilas son una estructura de datos muy usado en la solución de diversos tipos de

problemas. Estos son algunos de los casos más representativos de aplicación de pilas:

- Llamadas a subprogramas.

- Tratamiento de expresiones aritméticas.

Llamadas a subprogramas

Uno de los usos más comunes de la pila es el de almacenar la información de las sucesivas

llamadas a subrutinas en un programa, lo que nos permitirá volver de las mismas tras su

finalización.

Fig. 5.3 Llamadas a subprogramas

En el programa P, la instrucción r-1 es una llamada al procedimiento A1; sabemos que esta

instrucción implica pasar a la ejecución de A1 y cuando éste finalice, pasa a ejecutar la

instrucción siguiente, esto es la r.

Por su parte, la instrucción s-1 de A1 supone la ejecución de una llamada a A2. Se pasa el

control a A2 y cuando finalice pasa a ejecutar la posición s. Este proceso puede repetirse un

número cualquiera de veces, y es necesario disponer de un mecanismo que nos permita

ejecutar las instrucciones en el orden adecuado.

En la memoria del ordenador, el Sistema Operativo reserva una zona que se denomina pila

que se maneja como una estructura de datos de este tipo, es decir, siguiendo una política

LIFO. El uso de esta pila nos ayuda a almacenar la información necesaria para poder devolver

el control de forma correcta después de cada llamada: cuando se realiza una llamada a un

subprograma, además de otra información relacionada con los argumentos del mismo, se

almacena en la pila la dirección de retorno. Cada vez que finalice la ejecución de un

subprograma, en la cima de la pila tendremos la información necesaria para saber en que

instrucción nos habíamos quedado cuando realizamos la llamada. Al volver del subprograma,

eliminaremos del tope de la pila la dirección de retorno, lo que dejará como nuevo tope la

información necesaria para volver al finalizar el subprograma actual.

Información en la pila durante el desarrollo del programa

El gráfico de la figura representa en forma simplificada, la información que tendremos en la

pila del sistema durante el desarrollo del programa del ejemplo anterior:

Tratamiento de expresiones aritméticas

Un problema interesante en computación es poder convertir expresiones en notación infija a

su equivalente en notación postfija (o prefija).

Notación Infija : ejemplo A + B, operador entre operandos.

Notación Postfija : ejemplo AB+, operador después de los operandos.

Notación Prefija : ejemplo +AB, operador antes de los operandos.

Ventaja: En las expresiones en notación prefija y postfija no son necesarios los paréntesis

para indicar orden de operación ya que este queda establecido por la ubicación de los

operadores con respecto a los operandos.

Prioridad de los operadores

1. ( ) paréntesis

2. ^ potencia

3. *, / multiplicación y división

4. +, - sumas y restas

Los operadores con igual prioridad se procesan de izquierda a derecha.

Ejemplo

Traducir la expresión infija X + Y *W a notación postfija.

Notación postfija

Ejemplo

Traducir la expresión infija X + Y *W a notación prefija.

Notación prefija

Recursividad

La recursividad es una característica de los lenguajes de programación en virtud de la cual se

permite que un procedimiento haga referencia a sí mismo dentro de su definición.

La definición recursiva debe estar hecha de manera que la cadena de invocaciones termine en

algún momento con una llamada que no genere nuevas invocaciones.

La recursión en los subprogramas puede darse de dos maneras diferentes:

a) Directa: El subprograma se llama directamente a sí mismo.

Recursión directa

b) Indirecta: El subprograma llama a otro subprograma y éste a su vez llama al primero.

Recursión indirecta

La construcción de estos procedimientos no sigue una fórmula concreta, pero el programador

puede utilizar la noción de inducción de la siguiente forma:

1. Solucionar el caso/s más simple. Caso base.

2. Expresar el caso general en función de casos más simples que tiendan hacia el caso base.

3. Desarrollar el algoritmo recursivo, que en general tendrá la siguiente estructura:

Si estamos en un caso base entonces

Devolver la solución al caso base

Sino

- Descomposición del problema

- Llamada recursiva

- Obtención de la solución a partir del resultado obtenido en la llamada recursiva.

- Devolver solución.

Fin si

Ejemplo 1:

Escriba una función recursiva que permite calcular el factorial de un número entero positivo.

¨ Caso base:

Factorial (0) =1

¨ Enunciado General:

Factorial(n) = n * Factorial(n-1)

¨ Algoritmo recursivo:

Entero Función Factorial (n)

Inicio

Si (n = 0) entonces

Fact =1

Sino

Fact = n * Factorial(n-1)

Fin si

Devolver Fact

Fin

Simulación de ejecución del algoritmo

Ejercicios Resueltos

Ejercicio1. Considere la operación Reemplazar (Pila, ElemAntiguo, ElemNuevo) que consiste

en reemplazar todas las ocurrencias de un valor ElemAntiguo en la pila Pila por un nuevo

valor ElemNuevo. Escribir el algoritmo para esta operación. Utilice las operaciones sobre pilas

estudiadas en clase pero no asumir ninguna representación de pilas

Solución:

Algoritmo Reemplazar (?Pila, CimaPila, MaxElemPila, ElemAntiguo, ElemNuevo)

Inicio

CrearPila (PilaAux,cimaAux, MaxElemPilaAux)

Repetir mientras (PilaVacia (cimaPila)==Falso)

Desapilar (Pila, CimaPila, X)

Si(X== ElemAntiguo) entonces

Apilar (PilaAux, cimaAux, ElemNuevo, MaxElemPilaAux)

Sino

Apilar (PilaAux, cimaAux, X, MaxElemPilaAux)

Fin si

Fin repetir

Repetir mientras (PilaVacia (cimaAux) ==Falso)

Desapilar (PilaAux, CimaAux, X)

Apilar (Pila, CimaPila, X, MaxElemPila)

Fin repetir

Fin

Ejercicio 2. Formule un algoritmo que particione una pila P en dos pilas P1, P2, de la

siguiente manera: los valores menores que un valor dado x son ubicados en P1, los otros se

ubican en P2. Emplee solo operaciones de pilas. No asuma ninguna implementación en

particular.

Solución:

Algoritmo Particionar (?P, CimaPila, max, X, ?P1, ?P2, ?cimaP1, ?cimaP2)

Inicio

CrearPila (P1,cimaP1, max)

CrearPila (P2, cimaP2, max)

Repetir mientras (PilaVacia (CimaPila)== Falso)

Desapilar (P, CimaPila, z)

Si ( z < X) entonces

Apilar (P1, cimaP1, z, max)

Sino

Apilar (P2, cimaP2, z, max)

Fin si

Fin repetir

Fin

Ejercicio 3. Considere la operación CopiaArriba (P1, cimaP1, P2, cimaP2, P3, cimaP3, tam3)

que copia la primera pila P1 en la segunda pila P2 en el mismo orden. Escriba el algoritmo

correspondiente a esta operación. Use las operaciones de Pila.

Solución:

Algoritmo CopiaArriba (P1, cimaP1, P2, cimaP2, ?P3, ?cimaP3, tam3)

Inicio

MaxAux=tam3

CrearPila(P3,cimaP3, cimaP3)

CrearPila (PAux, cimaAux, MaxAux)

Repetir mientras (PilaVacia (cimaP1) == falso)

Desapilar (P1, cimaP1, X)

Apilar (PAux, cimaAux, X, maxAux)

Fin repetir

Repetir mientras (PilaVacia (cimaP2) == falso)

Desapilar (P2, cimaP2, X)

Apilar (PAux, cimaAux, X, maxAux)

Fin repetir

Repetir mientras (PilaVacia (cimaAux) == falso)

Desapilar (PAux, cimaAux, X)

Apilar (P3, cimaP3, X, tam3)

Fin repetir

Fin

Ejercicio 4. Considere la operación EliminarDato (Pila, cimaPila, Dato, MaxElemPila), que

consiste en eliminar de la pila P el elemento Dato. Escriba el algoritmo correspondiente a esta

operación. Use las operaciones de Pila.

Solución:

En caso hubieran más elementos Dato, solamente elimina el primero.

Algoritmo EliminarDato (?Pila, ?cimaPila, Dato, MaxElemPila)

Inicio

maxAux= MaxElemPila

CrearPila (PAux, cimaAux, maxAux)

Sw = 0

Repetir mientras (PilaVacia (cimaPila) == Falso y Sw == 0)

Desapilar (Pila, cimaPila, x)

Si (x ¹Dato) entonces

Apilar (PAux, cimaAux, x, MaxAux)

Sino

Sw= 1

Fin si

Fin repetir

Repetir mientras (PilaVacia (cimaAux) ==Falso)

Desapilar (PAux, cimaAux, Y)

Apilar (Pila, cimaPila, Y, MaxElemPila)

Fin repetir

Fin

Ejercicio 5. Considere un arreglo lineal llamado A el cual almacena n números enteros,

escriba un algoritmo recursivo que permita buscar un elemento llamado Val.

Solución:

Lógico Función BuscarValor (A, n, Val)

Inicio

Si (n ==1) entonces

Si A[n]= Val entonces

Buscar = verdadero

Sino

Buscar = BuscarValor(A, n-1, Val)

Fin si

Sino

Buscar = falso

Fin si

Devolver Buscar

Fin

Ejercicio 6. Considere un arreglo lineal llamado A el cual almacena n números enteros,

escriba un algoritmo recursivo que permita calcular el elemento más grande.

Solución:

Entero Función Mayor (A, n)

Inicio

Si (n==1) entonces

May = A[n]

Sino

Si (A[n]> Mayor(A, n-1)) entonces

May = A[n]

Sino

May = Mayor(A, n-1)

Fin si

Fin si

Devolver May

Fin

Ejercicio 7. El coeficiente binomial C(n, m) indica el número de maneras de escoger m

objetos entre n objetos.

Se conoce la relación C(n, m) = C(n-1, m-1) + C(n-1, m)

a) Formule un algoritmo recursivo para calcular C(n, m).

Solución

Entero Función C (n, m)

Inicio

Si (m == 1) entonces

Comb = n (Caso Base 1)

Sino si (n == m) entonces

Comb = 1 (Caso Base 2)

Sino (Caso General)

Comb = C (n-1, m-1) + C (n -1, m)

Fin si

Devolver Comb

Fin

b) Identifique el caso base.

Solución

m = 1, ? C = n

m = n, ? C = 1

Colas

En este capítulo se definirá el concepto y uso de la estructura y algoritmos de colas. Será

implementado con arreglos, describiéndose las operaciones en colas simples, colas circulares,

colas con prioridades y bicolas.

Definición y uso

Es una lista de elementos en la que las eliminaciones se realizan solo en un extremo llamado

el frente y las adiciones se realizan en el otro extremo llamado final (FIFO, First Input First

Output). La atención de un grifo es un ejemplo de cómo funciona una cola,

Colas

Se utilizan por ejemplo en los sistemas operativos en las salidas a impresora formando una

cola de impresión. Los trabajos en proceso forman cola para ser atendidos.

Representación de colas con arreglos

Una cola se puede implementar mediante un arreglo. Además se requiere una variable Frente

(la posición del extremo izquierdo) por donde se extrae elementos y una variable Final (la

posición del extremo derecho) por donde se añaden elementos. Además se requiere un

tamaño de cola N.

Representación de colas con arreglos

La implementación utiliza la siguiente definición: Cola: arreglo [1..N]

Operaciones

Las operaciones de cola son:

- Crear cola: inicializa la cola en el estado vacío.

- Cola vacía: determina si la cola está vacía.

- Cola llena: determina si la cola está llena.

- Encolar: añadir un nuevo elemento a la cola. Implica incrementar en uno el valor de Final y

luego ubicar el último elemento en la nueva posición.

- Desencolar: extraer el elemento que se encuentra en el frente y avanzar Frente un lugar.

Implementación

Archivo:

- PrincipalCola.cpp

- PrincipalCola.vb

Crear cola

{

Objetivo: Crear una cola vacía

Entrada: Frente, Final

Precondición: Ninguna

Salida: Frente, Final

Postcondición: Cola definida y vacía

}

Procedimiento CrearCola(#Cola, N, #Frente, #Final)

Inicio

{Definir Cola de tamaño N}

Frente = 0

Final = 0

Fin

Cola vacía

{

Objetivo: Indicar si la cola tiene o no elementos

Entrada: Frente

Precondición: Ninguna

Salida: Valor lógico

Postcondición: Indica si está vacío o no

}

Lógico Función ColaVacía(Frente)

Inicio

Si (Frente == 0) entonces

retornar verdadero

Sino

retornar falso

Fin si

Fin

Cola Llena

Cola llena

{

Objetivo: Indicar verdadero si la cola tiene el máximo número de elementos

Entrada: Final,N

Precondición: Ninguna

Salida: Indicador lógico

Postcondición: Indica si está llena o no

}

Lógico Función ColaLlena(Final, N)

Inicio

Si (Final == N) entonces

retorna verdadero

Sino

retorna falso

Fin si

Fin

Agregar un elemento a la cola – Encolar

{

Objetivo: Añade un elemento al final de la cola

Entrada: Cola, Frente, Final, N, NuevoElemento

Precondición: Ninguna

Salida: Cola, Frente, Final

Postcondición: Cola original con nuevo elemento añadido al final

}

Procedimiento Encolar(Cola, Frente, Final, N, NuevoElemento)

Inicio

Si (ColaLLena (Final, N) == verdadero) entonces

Escribir “Cola llena”

sino

Si (ColaVacia (Frente) == verdadero) entonces

Frente = 1

Final = 1

Sino

Final = Final + 1

Fin si

Cola [Final] = NuevoElemento

Fin si

Fin

Extraer un elemento a la cola – Desencolar

{

Objetivo: Extraer un elemento del frente de la cola

Entrada: Cola, Frente, Final, ElementoExtraido (sin valor)

Precondición: Ninguna

Salida: Cola, Frente, Final, ElementoExtraido (con valor)

Postcondición: Cola con elemento extraído del frente

}

Procedimiento Desencolar(Cola, Frente, Final, ElementoExtraido)

Inicio

Si (ColaVacia (Frente) == verdadero) entonces

Escribir “Cola vacía”

Sino

ElementoExtraido = Cola [Frente]

Si (Frente == Final) entonces

Frente = 0

Final = 0

Sino

Frente = Frente + 1

Fin si

Fin si

Fin

Cola circular

Observando el gráfico de la figura, aparentemente la cola está llena, Final = N, sin embargo

podemos observar que existen celdas disponibles en la cual se pueden añadir más elementos.

Para usar este espacio se usan las Colas Circulares.

Cola con celdas disponibles

Colas circulares

Se debe tener en cuenta que en las colas circulares se presentan dos casos los cuales se

muestran en la figura.

Casos circulares

Operaciones de cola circular

Las operaciones de cola circular que son diferentes a las de cola simple son:

- Cola llena.

- Encolar.

- Desencolar.

Implementación

Archivo:

- PrincipalColaCircular.cpp

- PrincipalColaCircular.vb

Cola llena en cola circular

{

Objetivo: Indica si la cola está llena

Entrada: Frente, Final, N

Precondición: Ninguna

Salida: Indicador lógico

Postcondición: Indica si está llena o no

}

Lógico Función ColaLlenaCircular (Frente, Final, N)

Inicio

Si (Frente == 1 y Final == N o Final + 1 == Frente) entonces

retornar verdadero

Sino

retornar falso

Fin si

Fin

Encolar en cola circular

{

Objetivo: Añade un elemento al final de la cola

Entrada: Cola, Frente, Final, N, NuevoElemento

Precondición: Cola no llena

Salida: Cola, Frente, Final.

Postcondición: Cola original con nuevo elemento añadido al final

}

Procedimiento EncolarCircular (Cola, Frente, Final, N, NuevoElemento)

Inicio

Si (ColaLLenaCircular (Frente, Final, N) == verdadero) entonces

Escribir “Cola circular llena”

Sino

Si (ColaVacia (Frente) == verdadero) entonces

Frente = 1

Final = 1

Sino

Si (Final ==N) entonces

Final = 1

Sino

Final = Final + 1

Fin si

Fin si

Cola [Final] = NuevoElemento

Fin si

Fin

Desencolar cola circular

{

Objetivo: Extraer un elemento del frente de la cola

Entrada: Cola, Frente, Final, N, ElemExtraido

Precondición: Cola no está vacía

Salida: Cola, ElementoExtraido

Postcondición: Cola original con elemento del frente extraido

}

Procedimiento DesencolarCircular (?Cola,?Frente, ?Final, N, ? ElemExtraido)

Inicio

Si (ColaVacia (Frente) = verdadero) entonces

Escribir “Cola Circular vacía”

Sino

ElemExtraido = Cola [Frente]

Si (Frente = Final) entonces {la cola tiene un solo elemento}

Frente = 0

Final = 0

Sino

Si Frente = N entonces {si está en la última posición}

Frente = 1

Sino

Frente = Frente + 1

Fin si

Fin si

Fin si

Fin

Cola con prioridades

Son colas en que los elementos tienen asociada una prioridad. La implementación de colas

con prioridades puede ser utilizando listas enlazadas, arreglos paralelos y mediante arreglos

bidimensionales.

En el caso de arreglos bidimensionales, cada fila del arreglo bidimensional es considerada

una cola circular. Dos arreglos Frente y Final almacenan las posiciones de los elementos que

están en el frente y final de cada cola. Además cada fila representa la prioridad que tienen

esos elementos en ser procesados.

Cola con prioridades

Se aplican en sistemas operativos, en los que los programas de mayor prioridad se procesan

primero, a igualdad de prioridades se mantiene el orden de la cola.

Inserción en cola con prioridades con arreglos bidimensionales

Se busca la fila correspondiente a la prioridad del elemento a ser insertado y luego se inserta

al final de la cola, siempre que no esté llena.

Extracción en cola con prioridades con arreglos bidimensionales

Se busca la primera cola no vacía y se procede a extraer el elemento que está al frente de la

cola.

Bicolas

En este caso, se puede añadir o extraer elementos por cualquier extremo. Puede

implementarse en un arreglo como cola circular. En este caso se cumpliría que Bicola[Der] va

detrás de Bicola[Izq].

Bicolas

Ejercicios Resueltos

Ejercicio1. Algoritmo que elimina Dato de la Cola.

Procedimiento Eliminar(?Cola, ?Frente, ?Final, N, Dato)

Inicio

CrearCola( C1, N1, Frente1, Final1)

Sw = 1

Repetir mientras (ColaVacia (Frente) ==Falso y Sw ==1 )

Desencolar (Cola, Frente, Final, X)

Si (X ==Dato) entonces

Sw = 0

Sino

Encolar (C1, Frente1, Final1, N1, X)

Fin si

Fin repetir

Repetir mientras (ColaVacia (Frente) == Falso)

Desencolar (Cola, Frente, Final, X)

Encolar (C1, Frente1, Final1, N1, X)

Fin repetir

Repetir mientras (ColaVacia (Frente1) == Falso)

Desencolar (C1, Frente1, Final1, X)

Encolar (Cola, Frente, Final, N, X)

Fin repetir

Fin

Ejercicio 2. Algoritmo que invierte el contenido de una Cola. (Utilizar sola las operaciones de

cola.)

Procedimiento InvertirCola(?Cola, ?Frente, ?Final, N)

Inicio

CrearPila (PAux, cima, maxPila)

Repetir mientras (ColaVacia (Frente) == Falso)

Desencolar (Cola, Frente, Final, num)

Apilar (PAux, cima, maxPila, num)

Fin repetir

Repetir mientras (PilaVacia (cima) == Falso)

Desapilar (PAux, cima, X)

Encolar (Cola, Frente, Final, N, X)

Fin repetir

Fin

Implementación

Archivo:

- PrincipalEjercicioCola.cpp

- PrincipalEjercicioCola.vb