Árboles binarios

Algoritmo propuesto a ejercicio de clase (Eliminar un dato de una lista simplemente ligada)

int p,q
lea dato
lea tope
p=q=tope
if(dato == tope(DATO)){
tope = tope(liga)
libere(p)
}
else{
while(p != NULL){
if(dato == p(DATO)){
q(liga) = p(liga)
libere(p)
break
}
else{
q=p
p=p(liga)
}
}
}

COLAS

Definición
Una cola es una lista de elementos en la que éstos ingresan por un extremo y se eliminan por el otro. Los elementos se eliminan de la cola en el mismo orden en el que ingresaron a ella, por esta razón, las colas, también son conocidas como estructuras FIFO (First-In, First-Out: Primero en entrar,Primero en salir).
Algunos ejemplos de colas en la vida real son: colas de personas para ingresar a un cine, colas de archivos para ser impresos, colas de pedidos en un restaurante, etc.

Representación de colas
Las colas se representan mediante el uso de arreglos unidimensionales o de listas ligadas. A continuación se presentan representaciones gráficas de las pilas utilizando para ello, arreglos unidimensionales o vectores.
Inicialmente se deben definir tres valores básicos para trabajar con colas:
• Frente, indica la posición en la que está ubicado el primer elemento de la cola
• Final, indica la posición en la que está ubicado el último elemento de la cola
• Máximo, indica el tamaño de la cola

2.2 Operaciones con colas
• Insertar un elemento, las inserciones se llevan a cabo por el final de la cola
• Eliminar un elemento, las eliminaciones se llevan a cabo por el frente de la cola
Es importante aclarar que cuando un elemento es eliminado, los demás NO se desplazan dentro de la cola, es decir, ningún elemento “sube” a ocupar la posición que ha dejado libre el elemento eliminado. De igual forma, cuando un elemento ingresa a una cola, NO “empuja” a los elementos que ya están en el interior de la estructura.

Algoritmo para insertar en una cola sencilla

Algoritmo para eliminar en una cola sencilla

Colas circulares
En este tipo de estructuras, el primer elemento puede estar precedido por el último. Los siguientes ejemplos gráficos representan el comportamiento de una cola en la cual se han eliminado de forma secuencial dos elementos (XX , YY) y luego se ingresa un nuevo elemento (PP), a pesar de que FINAL = MAX, sin embargo como la cola es circular, el último elemento queda en la posición 1:



Algoritmo para insertar en una cola circular


Algoritmo para eliminar de una cola circular

Doble cola
En este tipo de estructura los elementos pueden ser insertados o eliminados por cualquiera de los dos extremos que posee, (frente o final). La siguiente es una representación gráfica de una doble cola:

La doble flecha en cada extremo indica que se pueden insertar o eliminar elementos por cada “lado”.
Cuando sólo uno de los dos extremos recibe ambas operaciones (insertar y eliminar), se dice que tenemos un caso de Doble cola con entrada o salida restringida, así:
• Entrada restringida

• Salida restringida

Taller de vectores y matrices

Taller Nº 1 de Estructuras de Datos (Individual o en parejas), valor 10%.

Fecha de entrega: Lunes, 02 de marzo de 2009

1. Se tienen dos arreglos unidimensionales con datos no repetidos. Uno de ellos con N elementos y el otro con M elementos. Los elementos de los dos arreglos se encuentran ordenados de forma ascendente. Elabore un algoritmo que lea los dos vectores y forma uno nuevo de N + M elementos, el cual contendrá los elementos de los dos arreglos ordenados de menor a mayor. Es posible que entre ambos vectores existan elementos comunes, y en el vector resultado NO deben haber elementos repetidos.
2. Elaborar un algoritmo que genere y llene una matriz de orden M x N. luego intercambie el contenido de la primera y la última columna, de la segunda y la penúltima y así hasta obtener una matriz con columnas invertidas. Imprima ambas matrices. (Considere que M puede ser par o impar).

Evaluación 1

1. Genere y llene dos vectores A y B de tamaño M; luego genere un tercer vector C con la unión de la primera mitad del vector A y la segunda mitad del vector B. (Asuma que M es par). Ejemplo gráfico:


2. Genere y llene un vector A de tamaño M y una matriz B de tamaño M x N, luego inserte el vector A antes de la primera columna de la matriz B. Ejemplo gráfico:

Solución a evaluación 1

Ejercicios propuestos de matrices

1. Ingrese datos numéricos a una matriz cuadrada A, de orden N, luego encuentre la suma de los elementos ubicados en la diagonal principal y la suma de los elementos ubicados en la diagonal secundaria.












2. Encuentre e imprima la transpuesta de una matriz A. ()La transpuesta de una matriz se encuentra intercambiando las filas y las columnas)































3. Elabore una aplicación que lea una matriz de F filas y C columnas y calcule la suma de las filas y de columnas, dejando los resultados en dos vectores, uno con la suma de las filas y otro con la suma de las columnas. Imprima ambos vectores.
4. La siguiente imagen representa un tablero de damas. Un uno (1) representa la presencia de una ficha roja, un dos (2) representa la presencia de una ficha negra y un cero (0) representa la ausencia de ficha. Hacer una aplicación que calcule el número de fichas de cada color y el número total de fichas.













5. Elabore una matriz que contenga la información sobre ventas de N productos, grabando en la primera columna el código del artículo y en las siguientes el número de unidades vendidas durante el mes (meses de 30 días). Cada fila corresponde a los datos para un artículo; utilizar las tres columnas siguientes para calcular: promedio de ventas diarias, promedio de ventas por cada artículo y número de días en los que sí se vendió. Imprima la matriz.
6. Elabore una aplicación que entre una matriz de orden N*M elementos y muestre la suma total de los elementos ubicados en la primera fila, primera columna, última fila y última columna.
7. Dada una matriz de N filas por M columnas que debe ser leída, elaborar un algoritmo que ordene todos los elementos en forma descendente por filas.
8. En las elecciones para Alcalde del PUEBLITO PAISA se han presentado tres candidatos (A,B,C). El Pueblito se ha dividido en 5 zonas de votación. Elk reporte de votos de la zona se recibe en orden: primero la zona 1, la 2, etc.
Elabore una aplicación que:
a. Forme una matriz de 5 filas y 3 columnas que contenga, en cada fila, los votos reportados por las zonas para cada uno de los tres candidatos.
b. Encuentre el total de votos obtenidos por cada candidato y el porcentaje que éste representa.
c. Muestre un mensaje declarando ganador a un candidato, si éste obtuvo más del 50% de la votación. De lo contrario muestre un mensaje indicando: “No hay ganador”

Taller de vectores (Preparado por la docente Sixta Rosa Camacho)

TALLER VECTORES
1. Leer 5 números y crear un vector con ellos.
2. Realizar un programa que genere los números pares de 2 a 200 y llenar un vector con ellos.
3. Llenar un vector con los 10 primeros múltiplos de 3., sumar el vector
4. Crear un vector de 20 posiciones con valores diferentes. Hallar el mayor valor y su posición y el valor promedio
5. Leer un vector de N elementos. Imprimir cuantas veces se repite el elemento 25., sume los elementos de las posiciones pares. Imprimir los elementos del vector empezando por el último elemento.
6. Se tiene un vector de 15 elementos imprimir la suma y el promedio
7. De los elementos de un vector de 50 posiciones. Cuantos son: pares, impares, negativos y positivos .calcule el valor promedio del vector
8. Genere un vector de tamaño 10, con números reales leídos desde teclado. Calcule el promedio e indique cuantos elementos del vector son mayores que el promedio y cuantos menores o iguales.
9. Dado un vector con 10 elementos numéricos enteros ya almacenados, indique cuántos de ellos son múltiplos de 3
10. Se tiene un vector con las notas de un grupo de 30 estudiantes hallar e imprimir la nota más alta y la más baja. Cuantas personas perdieron y la nota promedio del grupo.
11. Hacer un diagrama que lea dos vectores de N y M posiciones. Crear un vector con la unión de ambos vectores e imprimirlos.
12. Cargar 2 vectores, uno con los códigos de los estudiantes que perdieron Estructura de Datos, el segundo con los códigos de los estudiantes que perdieron Cálculo Integral. Se pide crear otro vector formado por los códigos de los estudiantes que perdieron ambas materias. Imprimir el vector resultante.
13. Se tienen 3 vectores A, B, C de M elementos. Se debe crear otro vector NUEVO de tres elementos, donde cada elemento tenga la suma de los elementos de cada vector.
14. Lea un vector de S posiciones e inviértalo. Utilice otro Vector.
15. Dado un vector con 8 elementos y un número cualquiera, se debe colocar el número en la 5 posición del vector desplazando los demás valores hacia la derecha. La dimensión del vector es de 12.
16. Llenar un vector de 20 elementos, imprimir la posición y el valor del elemento mayor almacenado en el vector. Suponga que todos los elementos del vector son diferentes.
17. Almacenar 500 números en un vector, elevar al cuadrado cada valor almacenado en el vector, almacenar el resultado en otro vector. Imprimir el vector original y el vector resultante.
18. Almacenar 300 números en un vector, imprimir cuantos son ceros, cuántos son negativos, cuantos positivos. Imprimir además la suma de los negativos y la suma de los positivos.
19. Teniendo un vector de 95 posiciones con elementos numéricos enteros diferentes, realice un algoritmo en subprogramas que le permita:
• Buscar el elemento mayor y en qué posición lo encontró
• Calcular el promedio
• Sumar los elementos de las posiciones pares e imprimir la suma;
• Contar cuantos elementos del vector hay mayores que el promedio
• Buscar cuántos elementos del vector son mayores de 50 y menores de 100;
• Hallar cuántos elementos del vector son múltiplos de 7 los no múltiplos sumarlos.
• Llenar un vector con los elementos de las posiciones impares
• Imprimir los vectores de manera inversa.

Matriz C

Bibliografía

• MARTÍNEZ, Román y QUIROGA, Elda. Estructuras de Datos. Referencia práctica con orientación a objetos. Thomson Learning, México, 2002.

• JOYANES AGUILAR, Luis y Otros. Estructura de Datos. Libro de problemas. McGrawHill, España, 1999.

• CAIRÓ, Oswaldo y GUARDATI, Silvia. Estructura de Datos. Segunda edición. McGrawHill, México, 2002

Arreglos

1. Arreglo

1.1 Definición de arreglo
Es un grupo de elementos del mismo tipo, organizados de forma secuencial. La posición que ocupa cada elemento dentro del grupo se representa mediante un valor llamado índice; estos valores facilitan el acceso a cada elemento del grupo o arreglo.

1.2 Formas de los arreglos
La forma se refiere al número de dimensiones que posee el arreglo, así:

1.2.1 Arreglos unidimensionales, también se conocen con el nombre de vectores, son aquellos grupos de elementos dispuestos de forma “lineal”, por lo tanto, sólo poseen un número de índice para referirse a su posición dentro del arreglo. Al realizar la representación gráfica de los vectores, es indiferente si se dibujan de forma vertical u horizontal, a continuación , un ejemplo gráfico de vector:




El nombre de vector es A, es de magnitud o tamaño 7 y todas sus posiciones están ocupadas (no hay casillas “vacías”), se observa también que sólo está almacenando caracteres de texto, por lo que se puede asumir que es un vector de tipo char (caracteres).

1.2.2 Arreglos bidimensionales, también se conocen con el nombre de matrices. En este tipo de arreglos, la ubicación de cada elemento dentro del grupo, está dada por dos índices; el primer índice se refiere a la fila en la cual se encuentra el elemento, y el segundo índice se refiere a la columna. En este tipo de arreglos es muy importante tanto el orden en que se realiza la representación gráfica, como el orden en los índices de posición de cada elemento. Al referirnos al arreglo bidimensional, debemos hacerlo por su nombre, por ejemplo, “La matriz C”. A continuación, un ejemplo gráfico de una matriz de 3 filas y 4 columnas, que contiene datos de tipo numérico únicamente; el “nombre” de la matriz es B.






1.2.3 Arreglos multidimensionales. En este tipo de arreglos, la ubicación de cada elemento dentro del grupo, está dada por 3 o más índices, uno para cada componente del arreglo; por ejemplo, en el caso de un arreglo tridimensional, los tres valores de índice serán fila, columna y plano en ese orden estrictamente. A continuación un ejemplo gráfico de un arreglo “C”, tridimensional.








Se llama “fila” al subgrupo de elementos ubicados horizontalmente en la misma hilera horizontal, y se llama “columna” al subgrupo de elementos ubicados en la misma hilera vertical. En los arreglos de tres dimensiones, la tercera componente se llama plano.

1.3 Índice
Es un valor numérico entero y positivo que se refiere a la posición relativa de un elemento específico dentro de uno de los componentes de un arreglo (fila, columna, plano, etc.)
El máximo valor que puede tener un índice es el tamaño del componente al que se refiere (número de filas, número de columnas, número de planos, etc.). Un índice puede estar almacenado en una variable de tipo entero, o puede ser el resultado de una operación aritmética cuyo resultado sea un número entero positivo. Ejemplos de índices válidos:
3, 9, i, j, k, i+4, máximo-2, i+j-1
Donde las variables i, j, k deben contener números enteros positivos, esta misma restricción se aplica a los resultados de las tres últimas expresiones.

1.4 Referencia a un componente
Para hacer referencia al contenido de una posición específica de un arreglo, bien sea para leerlo o para modificarlo, se debe escribir el nombre del arreglo seguido del índice o índices de posición encerrados entre corchetes, así:
• Nombre_ArregloUni [índice]
• Nombre_ArregloBi [índiceFila][índiceColumna]

1.5 Ejercicios propuestos:
a. Llenar un vector de 10 posiciones con los números del 12 al 21
b. Llenar un vector de tamaño 10 con números pares consecutivos a partir de 2
c. Recorrer e imprimir los datos contenidos en un vector de tamaño n, en orden inverso
d. Calcular el valor promedio y la varianza de un grupo de datos contenidos en un vector.
e. Llenar, por columnas, una matriz de tamaño 3x3, con los múltiplos del 5, a partir de 10.
f. Determinar si una matriz cuadrada es simétrica. (Una matriz es simétrica cuando cada elemento de la posición [i,j] es igual al elemento de la posición [j,i])
g. Llene con números una matriz de tamaño 3x2, luego, forme un vector con los datos que existen en la matriz. Debe quedar al comienzo del vector la primera columna, luego la segunda columna y así sucesivamente. El arreglo bidimensional debe ser llenado por filas.