Download 1. objetivos 2. tad árbol de búsqueda binaria 3. tareas a

Universidad Técnica Federico Santa María
Departamento de Informática
ESTRUCTURA DE DATOS
EXPERIENCIA DE LABORATORIO N°3
(del 4 al 18 de Mayo de 2011)
Profesor: Mauricio Solar
Profesora: Lorna Figueroa
[email protected]
[email protected]
TAD Árbol de Búsqueda Binaria
1. OBJETIVOS
Implementar funciones para árboles de búsqueda binaria y luego aplicarlos para realizar una sencilla
aplicación de base de datos bancaria en memoria principal.
2. TAD ÁRBOL DE BÚSQUEDA BINARIA
crearArbol(tABB arbol): crea un árbol de búsqueda binaria vacío.
insertarNodo(tNodo n, tABB arbol): inserta el nodo en el árbol de acuerdo con las reglas de inserción del
ABB
esVacio(tABB arbol): retorna 1 si el árbol es vació, de otro modo, retorna 0.
buscarNodo(tABB arbol, int aBuscar): busca y retorna el nodo del árbol que tenga su dato igual a
“aBuscar”. Si no lo encuentra, retorna “NULL”.
3. TAREAS A REALIZAR
Se deben programar en C estándar (en Linux) al menos las funciones descritas en el punto 2 para implementar
un sistema de gestión de cuentas para un banco, en el cuál se almacene la información de los clientes, sus
cuentas y los saldos asociados a cada una.
Se trata de un árbol ABB (organizado en base a los RUT de cliente) en el cuál cada nodo representará un
cliente, que debe almacenar en una lista enlazada (ligada al nodo del cliente) las cuentas que este tiene y el
saldo de cada una.
El programa deberá ejecutar las siguientes funciones:
AgregarCuenta(tABB arbol, int rut, int id_cuenta, int saldo): se verifica si existe el cliente, de no existir,
debe ser creado. Si existe, se verifica que no exista la cuenta, de existir, se retorna -1. Si no existe, la cuenta
debe ser agregada a las cuentas del cliente y su saldo debe ser el especificado.
ModificarSaldo(tABB arbol, int rut, int id_cuenta, int aCambiar): se modifica el saldo de la cuenta
id_cuenta del cliente con rut igual al entregado. Se debe validar que el cliente y la cuenta existan, de no ser
asi, se debe retornar -1.
Universidad Técnica Federico Santa María
Departamento de Informática
EliminarCuenta(tABB arbol, int rut_cliente, int id_cuenta): se elimina la cuenta de id “id_cuenta” en el
cliente “rut_cliente”. Se debe verificar que exista tanto el cliente como la cuenta, de no existir alguno de los 2,
se retorna -1.
SaldoCliente(tABB arbol, int rut_cliente): se retorna la suma del saldo de todas las cuentas del cliente con
rut “rut_cliente”. Si el cliente no existe se debe retornar -1.
MostrarClientes(tABB árbol): debe mostrar todos los clientes del banco ordenados por RUT y el saldo total
(suma de los saldos de todas sus cuentas) asociado a cada uno.
SaldoBanco(tABB arbol): debe retornar la suma de los saldos de todas las cuentas de todos los clientes del
banco. En caso de no existir clientes, debe retornar 0.
El programa deberá recibir un archivo de entrada llamado Clientes.txt con el siguiente formato:
Clientes.txt
10
12998337 2
1 200000 2 5500000
3874638 3
1 40000 2 56700 3 10000000
…
9872134
1 4032000
En donde el primer número es el número de clientes que contiene el archivo de entrada (en el ejemplo 10)
seguido de los clientes.
En las siguientes líneas del archivo, están escritos los clientes, cada cliente ocupa 2 líneas, la primera línea de
cada cliente contiene dos enteros, el primero es el RUT del cliente, seguido por el número de cuentas que este
posee. La segunda línea contiene pares de 2 enteros (1 par por cada cuenta), en donde el primer número
representa el identificador de la cuenta y el segundo número el saldo de la cuenta.
Por ejemplo, el primer cliente del archivo es:
12998337 2
1 200000 2 5500000
RUT: 12998337
Número de cuentas: 2
Cuentas: id: 1 - saldo: 200000
id: 2 - saldo: 5500000
Una vez cargados los datos en el árbol se debe generar un archivo de salida llamado Estado1.txt y a
continuación, se deben realizar las siguientes operaciones:
Universidad Técnica Federico Santa María
Departamento de Informática
- Cada cliente ha decidido retirar el 50% del saldo de todas sus cuentas.
- El cliente de más edad (RUT menor) decide cerrar su primera cuenta
- El cliente mas joven (RUT mayor) decide abrir una nueva cuenta con identificador 9 y saldo $6.400.000.
Una vez realizadas estas operaciones, el programa deberá generar otro archivo de salida llamado
Estado2.txt.
Los archivos Estado1.txt y Estado2.txt tienen el siguiente formato (que debe ser respetado):
Situación del Banco
------------------------------------------------------------------------------------------------------Clientes
------------------------------------------------------------------------------------------------------RUT
N Cuentas
Saldo
------------------------------------------------------------------------------------------------------3874638
2
10096700
…
9872134
1
4032000
12998337
3
5700000
------------------------------------------------------------------------------------------------------Saldo total del Banco
90393829
Los clientes se muestran ordenados por RUT de menor a mayor. “N cuentas” es el número de cuentas de
cada cliente.
El programa debe ser realizado en Linux, compilado con la función –gcc y –Wall. Se recomiendan las
funciones malloc, realloc o calloc, para el uso de memoria dinámica.
4. RESTRICCIONES Y CONSIDERACIONES
Se debe programar un TAD para el manejo de Listas. La implementación de Listas debe hacerse de manera
dinámica, cualquier implementación estática (usando arreglos) será evaluada con nota cero.
Se permite la creación de otras funciones además de las definidas en el TAD ABB.
El acceso a la información de los nodos debe hacerse usando las funciones del TAD, se considerará grave la
violación del TAD ABB. No es necesario utilizar todas las funciones sugeridas para el TAD ABB, pero si
deben estar todas programadas.
Si se desea, se permite la separación del código en archivos para mejorar el orden y la comprensión (Ejemplo:
listas.h, ABB.h, tarea3.c, etc), no es obligatorio, pero si se hace deben incluirse instrucciones de compilación
en el archivo README.
Universidad Técnica Federico Santa María
Departamento de Informática
5. ENTREGA
La entrega de esta experiencia puede hacerse vía Moodle http://moodle.inf.utfsm.cl (Estructura de Datos –
Campus Santiago) o también vía e-mail a [email protected]
La tarea deberá estar comprimida en un archivo Grupo.XX.tar.gz (Ejemplo Grupo.01.tar.gz). Este contendrá
el archivo tarea3.c, un archivo nombres.txt con nombres y rol de los alumnos indicando que hizo cada
integrante, el archivo Clientes.txt con al menos 10 clientes y un archivo README.txt con instrucciones
generales y de compilación de ser necesario.
Debe ser enviada a más tardar a las 23:59:59 del día 18 de Mayo de 2011.
La entrega vía e-mail debe enviarse desde un correo electrónico institucional (alumnos.usm.cl o
alumnos.inf.utfsm.cl) con el Asunto: [EDD] Tarea 3 GrupoXX. (EJEMPLO: “[EDD] Tarea 3 Grupo01”,
sin las comillas, respetando espacios, corchetes y cambiando XX por su número de Grupo) Entregas con
otro asunto o desde otras casillas de correo serán ignoradas.
Los retrasos serán penalizados con descuentos de 30 puntos por día o parte de él.
Las tareas deben cumplir con las siguientes condiciones para ser evaluadas:
1.- No deben tener errores de compilación.
2.- Por cada Warning en la compilación se descontarán 5 puntos.
3.- Debe ejecutar al menos un archivo de clientes escrito por los alumnos con al menos 10 clientes.
Grupos
No se permiten divorcios injustificados en los Grupos. Si un grupo se separa y entrega más de una tarea, todos
los integrantes serán evaluados con nota cero. En caso de que alguno de los integrantes del grupo realice
Rebaja Académica Voluntaria, contactarse a la brevedad con el ayudante de Laboratorio
([email protected]) para una posible solución.