UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
PRCTICA N 1: ARREGLOS Y OPERACIONES CON ARREGLOS
OBJETIVOS
Implementar algoritmos de bsqueda, ordenacin, insercin y eliminacin en arreglos unidimensionales.
FUNDAMENTO TERICO
OPERACIONES BSICAS CON ARREGLOS.
1.
Bsqueda.
La bsqueda consiste en encontrar un determinado valor dentro de un conjunto de datos, para recuperar
alguna informacin asociada con el valor buscado.
Existen diferentes formas de realizar esta operacin; en otras palabras hay distintos mtodos o tcnicas para
realizar bsqueda en vectores.
2.
Bsqueda secuencial o lineal.
Bsqueda Binaria.
Bsqueda Hash.
Arboles de bsqueda.
Ordenacin
La ordenacin se refiere a la operacin de organizar los elementos de un vector en algn orden dado:
ascendente o descendente.
Existen diferentes mtodos o tcnicas para organizar los elementos de un arreglo. Los ms comunes son:
3.
Mtodo de burbuja
Mtodo de burbuja mejorado.
Ordenacin por seleccin
Insercin o mtodo de la baraja
Shell
Binsort o por urnas
Por montculos o heapsort
Por mezcla o mergesot
Mtodo de la sacudida o shackersort
Rapid sort o quick sort
Por rboles.
Insercin
Esta operacin consiste en adicionar un nuevo elemento al arreglo. Se debe tener en cuenta:
1. Que no sobrepase el tamao mximo declarado para el vector.
2. La operacin puede darse para un arreglo ordenado o desordenado.
3. Si el arreglo est desordenado, se incrementa en uno el nmero de elementos y en esa posicin N + 1
se inserta el nuevo elemento,
4. Si el arreglo est ordenado hay que
o
o
o
4-1 Buscar el lugar dentro del arreglo donde se debe inserta el nuevo valor para que contine
el vector ordenado.
4-2 Correr todos los elementos del vector una posicin a la derecha, para abrirle espacio al
nuevo elemento, a partir del lugar donde debe insertarse el nuevo dato.
4-3 Insertar el nuevo elemento del vector en el espacio que le corresponde.
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
4.
Eliminacin
Consiste en eliminar un elemento del arreglo, puede darse cuando el arreglo est desordenado u ordenado.
El proceso de eliminacin sigue los pasos que se describen a continuacin:
Verificar que el arreglo no est vaco.
Buscar la posicin donde se encuentra el elemento a borrar.
Correr los elementos una posicin a la izquierda, a partir de la posicin siguiente donde se encuentra el
valor a borrar.
Disminuir el nmero de elementos del vector en uno.
Enviar un mensaje en caso de que el elemento a borrar no est dentro del arreglo.
PORQUE USAR ARREGLOS
Caso de ejemplo: Se tiene las calificaciones de un grupo de 30 alumnos. Se requiere saber cuntos alumnos
tienen un promedio de notas superior al promedio del grupo. Cul sera el algoritmo para resolver este problema,
haciendo uso slo de datos simples?
Solucin por Doble lectura:
i y Cont son variables enteras, AC, Promedio y Nota son reales
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
INICIO
AC=0
i=1
MIENTRAS
i<=30
Leer Nota
AC=AC+Nota
i=i+1
Promedio=AC/30
AC=0
i=1
MIENTRAS
i<=30
Leer Nota
SI
Nota>Promedio
Cont=Cont+1
i=i+1
Escribir
Cont
FIN
Solucin por Muchas Variables:
Cont es una variable entera, AC, Promedio y Nota1. Nota30 son reales.
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
INICIO
Leer Nota1
Leer Nota2
Leer Nota30
AC=Nota1+Nota2+ +Nota30
Promedio=Ac/30
Cont=0
SI
Nota1>Promedio
Cont=Cont+1
SI
Nota2>Promedio
Cont=Cont+1
SI
Nota30>Promedio
Cont=Cont+1
Escribir
Cont
FIN
PROCEDIMIENTO
Solucin usando Arreglos
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
INICIO
AC=0
Para i=1 to 30
Leer Nota[i]
AC=AC+Nota[i]
Promedio=AC/30
Para i=1 to 30
SI
Nota30>Promedio
Cont=Cont+1
Escribir
Cont
FIN
El ejemplo anterior muestra los inconvenientes que se encuentran al hacer uso slo de datos simples. En el
primer caso se debe efectuar una doble lectura de datos y en el segundo caso se requieren muchas variables
para evitar la doble lectura.
Cuando la solucin de problemas haciendo uso slo de datos simples es muy compleja, se recurre al uso de
datos estructurados.
Para la solucin del problema anterior hicimos uso de Arreglos Unidimensionales.
Operaciones con Arreglos Desordenados
1. Crear un programa que permita realizar todas las operaciones con arreglos desordenados: (Lectura,
Escritura, Insertar, Buscar, Eliminar, Modificar y Ordenar los elementos del Arreglo). Mostrar el Nmero
de Elementos y el Mayor de todos ellos.
Insercin:
n=n+1
V[n]=y
Eliminacin
SI
n<100
F
Error: el
arreglo est
lleno
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
SI
n>=1
Error:
Arreglo esta
vacio
i=1
Cen=0
MIENTRAS
i<=n y Cen=0
V
V
SI
V[i]=x
Cen=1
n=n+1
Para k=1->n
V[k]=v[k+1]
SI
Cen=0
X no est en
el arreglo
Modificacin:
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
SI
n>=1
Error:
Arreglo esta
vacio
i=1
Cen=0
MIENTRAS
i<=n y Cen=0
V
V
SI
V[i]=x
i=i+1
V[i]=x
Cen=1
SI
Cen=0
X no est en
el arreglo
Operaciones con Datos Ordenados
2. Crear un programa que permita realizar todas las operaciones con arreglos Desordenados: (Lectura,
Escritura, Insertar, Buscar, Eliminar y Modificar los elementos del arreglo). Mostrar el nmero de
elementos y el mximo ndice.
Bsqueda
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
i=1
MIENTRAS
i<=n y v[i]<w
i=i+1
V
Pos=
Insercin
SI
i<n y v[i]>w
F
Pos=i
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
SI
n<100
Buscar
Recibe: x,n,w
Devuelve: pos
Error: No
hay espacio
SI
Pos>0
Elemento w
ya existe
n=n+1
pos=pos*-1
Para i=1 (pos+1) 1--
V[i]=v[i-1]
V[pos]=w
Eliminacin
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
SI
n>0
Buscar
Recibe: x,n,w
Devuelve: pos
SI
Pos<0
Error: El
arreglo esta
vacio
n=n+1
Elemento w
no existe
Para i=pos n
V[i]=v[i+1]
Modificacin
SI
n>0
Buscar
Recibe: x,n,w
Devuelve: pos
Elemento w
no existe
SI
Pos<0
Error: El
arreglo esta
vacio
V[pos]=w
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
EJERCICIOS PROPUESTOS
1. Realice un programa que lea 20 nmeros enteros cada uno de los cuales ste entre 10 y 100. Conforme
cada nmero sea ledo, imprima slo si no es un duplicado de un nmero ledo anteriormente.
2. Escriba un programa en C que simule el lanzamiento de dos dados. El programa deber utilizar la funcin
rand para el lanzamiento de los dados, entonces la suma de los dados debe ser calculada. Nota: en vista
de que cada dado puede mostrar valores del 1 al 6, la suma de los dados deber estar comprendida entre
2 o 12, siendo la suma ms frecuente 7 y la menos frecuente 2 a 12. Su programa deber realizar 36000
lanzamientos. Utilice un arreglo para contar el nmero de veces que aparece cada suma posible. Imprima
los resultados en forma tabular y determine el porcentaje de veces que sali un 7, un 2 o un 12.
3. Una pequea aerolnea acaba de adquirir una computadora para un sistemas automatizado de
reservaciones. El presidente le ha solicitado a usted que programa el nuevo sistema en C. Usted debe
escribir un programa que asigne asientos en cada vuelo del nico avin de la aerolnea (capacidad 10
asientos).
Su programa deber mostrar el siguiente men de alternativas.
Ingrese 1 para Fumadores.
Ingrese 2 para No fumadores.
4. Si la persona escribe 1, entonces su programa deber asignar un asiento en la seccin de fumar (asientos
del 1 al 5) si la persona escribe 2, entonces su programa deber asignar un asiento en la seccin de no
fumar (asientos del 6 al 10). Si el programa a continuacin deber imprimir un pase de abordaje, indicando
el nmero de asiento de la persona y si est en la seccin de fumar o no fumar del avin.
Su programa no deber, naturalmente, asignar nunca un asiento que ya haya sido asignado. Cuando est
llena la seccin de fumar, su programa deber solicitar a la persona, si le parece ser colocada en la seccin
de no fumar (o viceversa). Si dice que s, entonces efecte la asignacin apropiada de asiento. Si dice que
no, entonces imprima el mensaje Siguiente Avin disponible en 3 Horas.
5. Imagine una tortuga que camina por la habitacin bajo un programa en C. La tortuga sujeta una pluma dos
posiciones posibles, arriba o abajo. Cuando la pluma est abajo, la tortuga traza formas conforme mueve;
cuando la pluma est arriba, la tortuga se mueve libremente, sin escribir nada. En este problema
simularemos la operacin de la tortuga. Utilice un arreglo de 50 por 50 de nombre Piso que inicializa a ceros.
Lea los comandos partiendo de un arreglo que los contenga. Lleve control en todo momento de la posicin
actual de la tortuga, as como de si la pluma en ese momento est arriba o abajo. Suponga que la tortuga
siempre empieza a partir de la posicin 0,0 en el piso, con su pluma arriba. El conjunto de comandos de la
tortuga que se programa debe procesar, son como sigue:
Comando
Significado
1
Pluma Arriba
2
Pluma Abajo
3
Giro a la Derecha
4
Giro a la Izquierda
5,10
Moverse hacia adelante 10 espacios (u otro nmero distinto
a 10)
6
Imprimir el arreglo 50 x 50
9
Fin de los datos (ver centinela)
Suponga que la tortuga est en algn logar cerca del centro del piso. El siguiente programa dibujara e
imprimira un cuadrado 12 por 12:
2
5,12
3
5,12
3
5,12
3
5,12
1
6
9
Conforme la tortuga se mueve con la pluma abajo, defina los elementos apropiados del arreglo Piso, al valor
1. Cuando se da el comando 6 (imprimir), siempre que exista en el arreglo un 1, despliegue un asterisco, o
cualquier otro carcter que seleccione. Siempre que aparezca un 0, despliegue un espacio vaco. Escriba
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
Facultad de Ingeniera
E.A.P. Ingeniera en Informtica y Sistemas
un programa en C para poner en operacin las capacidades grficas de la tortuga discutidas aqu.
