LSLLSE

Vista previa del material en texto

Centro Universitario de Ciencias
Exactas e Ingenierías
Ingeniería informática
SEMINARIO DE SOLUCIÓN DE PROBLEMAS DE ESTRUCTURAS DE DATOS I
Nombre del Alumno:
Valenciano Tadeo Jeremy Esau
Lista Simplemente Ligada Lineal Sin
Encabezado
Ejercicio Socios
Declaración de la clase Member
Empezaremos con la declaración de una clase llamada Member esta clase será la
encargada de definir los atributos y métodos con los que contara nuestros objetos,
esta clase contara con los atributos, nombre, numero de Socio, domicilio y año de
ingreso. Estos atributos serán de tipo string y enteros int..
Por otra parte, los getters se encargaran de obtener y retornar los datos que el
objeto tenga, además contara de otros métodos como lo son imprimir. El método
imprimir se encargara de concatenar todos los atributos del objeto y los retornara.
A cada método setter se le pasara por referencia los valores que el usuario ingrese,
estos se deben mantener de manera constante debido a que no se modificara su
valor a lo largo de la ejecución del método.
Los constructores que contara esta clase será uno parametrizado y uno sin
parámetros.
1
Después encontraremos la respectiva sobrecarga de operadores, estos se
encargarán de modificar el comportamiento de dichos operadores para poder
manipular los objetos de la manera que se desea. Por ejemplo en esta práctica sé
solicito ordenar de manera alfabética los objetos de tipo Persona dentro de nuestra
Lista, la comparación de atributos dentro de nuestros objetos con ayuda de la
sobrecarga de operadores va a ser muy útil.
2
Implementación de la clase Member
Método Constructor parametrizado.
Este metodo recibira un valor por referencia constante, mediante al cual se le asignaran dichos
valores a los atributos de la clase.
Métodos de actualización getters & setters.
Los métodos setters nos seran de ayuda para asignar los valores que el usuario ingrese al
objeto en cueston, esto se hace por medio de paso de valor por referencia y de manera
constante para asi asegurarnos que el valor no sea modificado.
3
Los métodos getters nos seran de ayuda para retornar los valores de los atrubutos de la clase
Member, dibido a que nosotros como usuarios y programadores no podemos hacer uso de
elloos directamente, esto ayuda a preservar el encapsulamiento y retornarnan el valor de dicho
atributo de una manera mas eficiente.
4
Este método imprimir es el encargado de concatenar y retornar todos los atributos
en un solo string, con ayuda de to_string convertiremos los datos de tipos int a
string para poder concatenarlos de manera adecuada. Al final del método retornará
dicho string para poder imprimirlo.
Sobrecarga de los operadores en la clase Member
5
La sobrecarga de cada uno de los operadores como lo son (==, <,>,<=,>=) nos
ayudaran para determinar el ordenamiento por medio del numero de socio de la
clase Member. Al final de cada sobrecarga se retornará el valor del numero de socio.
Debido a que posteriormente la sobrecarga nos ayudara a ordenar los objetos
mediante el numero de socio con los operadores < y >
6
Declaración de la Lista Simplemente Ligada Lineal.
La lista contará con un tamaño dinamico, esto quiere decir que modificara su
tamaño de manera dinamica, conforme el usuario ingrese mas informacion. Los
principales métodos de la lista son el copyAll que se encargara de recibir una lista por
referencia para después copiar cada uno de los elementos a otra lista.
El método swapData será el encargado de intercambiar dos valores, este método
será de gran utilidad para los ordenamientos. Tambien contaremos con un metodo
SwapDataPtr es cual nos ayudara a intercambiar datos con ayuda de dos nodos los
cuales apuntan a algun dato.
Ahora dentro de los atributos de nuestra lista contaremos con una clase llamada Nodo
el cual se encargara de apuntar al siguiente dato de la lista. Dentro de la clase Nodo
tambien contaremos con sus metodo de actulizacion como lo son los getters y setters.
Algunos de estos metodos se pasan por referencia y otros reciben un apuntador de
tipo Nodo el cual contiene cierta direccion de memoria.
Finalmente daremos permiso de acceso a la clase Nodo a los metodos y atributos de la
clase Lista, esto con ayuda de la palabra reservada Friend.
7
Métodos de la Lista Dinamica
Dicha clase también tendrá métodos como:
● Vacía
● Insertar
● Eliminar
● obtener primera posición
● obtener última posición
● obtener siguiente posición
● obtener anterior posición
● Recuperar
● imprimir
● eliminar lista
8
● ordenar lista
● Numero elementos de la lista
La lista contara con un ancla la cual sera de tipo Nodo, se inciara en nullptr, despues ira
apuntatando a los siguientes elementos de la lista.
Como estamos usando memoria dinamica entonces haremos uso de las palbras
reservadas new y delete, la cuales crean espacio en memoria y eliminan dicho espacio
creado. Haremos uso de un template el cual nos ayudara a que las funciones y clases
operen con tipos de dato genéricos.
Esto permite que una función o clase trabaje en muchos tipos de datos diferentes sin
tener que volver a escribir para cada uno.
9
Librerias utilizadas
importaremos las librerias iostream, el header menu y el using namespace std;
10
Función main.
Dentro de nuestra función main solo encontraremos la declaración de un objeto de
tipo menú, debido a que toda la implementación del menú se encuentra dentro de
dicho objeto. Con ayuda de un bucle while y la función evaluateMenu evaluaremos
nuestro menú. Esto ayuda a tener más organizado nuestra función main.
Explicación implementación de la clase Menu.
Declaración de variables auxiliares y delegación del constructor.
Declararemos unas variables auxiliares de tipo int,float,String y Member. Debido a
que estas serán utilizadas al hacer uso de los métodos setters.
Delegaremos las variables cont y j en los constructores para asignarles valores al
momento de crear el objeto menú, Además de pasar por referencia los atributos de
dicha clase.
11
Método capturar Datos
Este método es el encargado de capturar los datos que el usuario ingrese a nuestro
objeto llamado myPerson, con ayuda de las variables previamente declaradas y de
los setters llenaremos los atributos de dicho objeto.
12
Método mostrar menú.
nuestro método show menú mostrara las opciones de nuestro menú principal, este
capturara un char que será retornado para después utilizarlo en el método evaluar
menu, que será el encargado de definir el curso del programa.
13
Método evaluar menú.
Opcion registrar Socio y dar de baja Socio.
Para registrar un usuario hacermos uso de la funcion capture data, la cual obtiene toda
la información del usuario y la ingresa en un objeto auxiliar de tipo Member, despues se
insertara en la lista.
El metodo dar de baja Socio sera el encargado de imprimir toda la lista de Socios para
despues preguntar al usuario que socio desea eliminar por medio de su numero de
Socio,
14
Opcion Editar direccion de Socios e Imprimir reporte de todos los socios.
La opcion cambiar Socio sera el encargado de cambiar la direccion de un Socio,
primero debera preguntar al usuario que socio desea modificar por medio de su numero
de Socio, para eso primero imprimiremos la lista de socios.
Despues se hara uso del metodo retrieve el cual regresa un elemento de la lista, con
ayuda de find data se buscara y recuperara el Socio con el cual coincide el Codigo que
el usuario ingreso.
El metodo ToString incluido en la Lista Dinamica es una concatenacion de los metodos
toString de los Objetos de tipo Member.
15
Opcion Numero de Socios y opcion invalida
Esta opcion calculara el numero de miembros de la lsita dinamica, esto con ayuda de
un bucle que incicia desde la ancla hasta que apunta a nullptr, con ayuda de un
contador va contando los elementos de la lista.
En caso de que el usuario no digite una opcion correcta, se imprimira Error, ingrese una
opcion valida.
Opcion Reporte dado una fecha.
16
Dentro de esta funcion declaramos un nodo que empezaraa hacer una iteracion desde
el ancla hasta nullptr, esto nos sevira para ir recorriendo e imprimiendo los datos en
donde la fecha que ingreso el usuario sea mayor o igual a la del objeto auxiliar.
List.H
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include <iostream>
#include <string>
#include "Member.h"
using namespace std;
template <class T>
class List
{
private:
///nodo forma parte de la lista
17
class Node
{
private:
T data; ///guarda el dato
Node *next; ///apunta al siguiente nodo de la
lista
public:
///getters & setters deata y next
Node();
Node(const T &);
T getData() const; ///retorna el dato
Node *getNext() const; ///retorna siguiente
void setData(const T &); ///asignar dato
void setNext(Node *); ///asignar el siguiente
///otorga acceso a los metodos de la lista(clase
amiga)
friend class List;
};
Node *anchoir; ///ancla de la lista
18
void copyAll(const List<T> &);
void swapData(T&, T&);
void swapDataPtr(Node*,Node*);
bool isValidPos(Node *) const; ///validar posicion en
la lista
public:
typedef Node *Position;
List();
List(const List<T> &);
bool isEmpty() const;
void insertData(Node *, const T &);
void deleteData(Node *);
19
Node *getFirstPos() const;
Node *getLastPos() const;
Node *getPrevPos(Node *) const;
Node *getNextPos(Node *) const;
Node *findData(const T &) const;
T retrieve(Node *) const;
std::string toString() const;
//numero de socios
int numberOfMembers();
void dateReport(const int);
//metodos de ordenamiento
void SortLinkedList(Node*);
void deleteAll();
List<T> &operator=(const List<T> &);
20
~List(); /// El destructor solo se usa cuando es
memoria dinamica
};
/// Implementaciones
/// Nodo
template <class T>
List<T>::Node::Node() : next(nullptr) {} ///inicializar
next en nullptr
template <class T>
List<T>::Node::Node(const T &e) : data(e), next(nullptr)
{}
template <class T>
T List<T>::Node::getData() const
{
return data;
}
21
template <class T>
typename List<T>::Node *List<T>::Node::getNext() const
{
return next;
}
template <class T>
void List<T>::Node::setData(const T &e)
{
data = e;
}
template <class T>
void List<T>::Node::setNext(Node *p)
{
next = p;
}
/// Lista
template <class T>
22
void List<T>::copyAll(const List<T> &lista1)
{
Node *aux(lista1.anchoir);
Node *last(nullptr);
Node *nuevoNodo;
while (aux != nullptr)
{
/// insertData(getLastPos(), aux->getData());
/// Al nodo nuevo, le colocamos los datos de la
lista original
nuevoNodo = new Node(aux->getData());
if (last == nullptr)
{
/// Es porque la nueva lista esta vacia
anchoir = nuevoNodo;
}
else
23
{
/// Ya hay por lo menos 1 elemento dentro de
la nueva lista
last->setNext(nuevoNodo);
}
/// Hacemos que el ultimo nodo este apuntando al
agregado recientemente
last = nuevoNodo;
/// Seguimos copiando
aux = aux->getNext();
}
}
template <class T>
void List<T>::swapData( T& a, T& b)
{
T aux(a);
a = b;
b = aux;
}
24
template <class T>
void List<T>::swapDataPtr( Node *a, Node *b)
{
T temp = a->data;
a->data = b->data;
b->data = temp;
}
template <class T>
bool List<T>::isValidPos(Node *posi) const
{
Node *aux(anchoir);
while (aux != nullptr)
{
if (aux == posi)
{
return true;
}
aux = aux->getNext();
}
25
return false;
}
template <class T>
List<T>::List() : anchoir(nullptr) {}
template <class T>
List<T>::List(const List<T> &lista1) : anchoir(nullptr)
{
copyAll(lista1);
}
template <class T>
bool List<T>::isEmpty() const
{
return anchoir == nullptr;
}
template <class T>
void List<T>::insertData(Node *pos, const T &ele)
26
{
if (pos != nullptr and !isValidPos(pos))
{
cout << "Posicion invalida, inserData() \n";
}
Node *aux(new Node(ele));
if (aux == nullptr)
{
cout << "Memoria no disponible, tratando de crear
new Node, insertData \n";
}
/// Ubicamos que tipo de insercion es
if (pos == nullptr)
{
/// Insertar al principio
aux->setNext(anchoir);
anchoir = aux;
27
}
else
{
/// En cualquier otra posicion (contando la
ultima)
aux->setNext(pos->getNext());
pos->setNext(aux);
}
}
template <class T>
void List<T>::deleteData(Node *pos)
{
if (!isValidPos(pos))
{
cout << "Posicion invalida, deleteData \n";
}
/// Buscamos que tipo de eliminacion es para hacer el
RELIGADO
if (pos == anchoir)
{
28
/// Eliminar el primero
/// RELIGANDO el primero
anchoir = anchoir->getNext();
}
else
{
/// Eliminar cualquier otra posici�n (Tambien la
ultima)
/// RELIGANDO cualquier otra posici�n
getPrevPos(pos)->setNext(pos->getNext());
}
/// Cualquier caso, liberamos la memoria reservada
delete pos;
}
template <class T>
typename List<T>::Node *List<T>::getFirstPos() const
{
return anchoir;
29
}
template <class T>
typename List<T>::Node *List<T>::getLastPos() const
{
if (isEmpty())
{
return nullptr;
}
Node *aux(anchoir);
while (aux->getNext() != nullptr)
{
aux = aux->getNext();
}
return aux;
}
30
template <class T>
typename List<T>::Node *List<T>::getPrevPos(Node *pos)
const
{
if (pos == anchoir)
{
return nullptr;
}
Node *aux(anchoir);
while (aux != nullptr and aux->getNext() != pos)
{
aux = aux->getNext();
}
return aux;
}
template <class T>
31
typename List<T>::Node *List<T>::getNextPos(Node *pos)
const
{
if (!isValidPos(pos))
{
return nullptr;
}
return pos->getNext();
}
template <class T>
typename List<T>::Node *List<T>::findData(const T &ele)
const
{
Node *aux(anchoir);
while (aux != nullptr and aux->getData() != ele)
{
aux = aux->getNext();
}
32
return aux;
}
template <class T>
T List<T>::retrieve(Node *pos) const
{
Member auxMember;
auxMember.setMemberNumber(0);
if (!isValidPos(pos))
{
//cout << "Posicion invalida, retrieve Data \n";
return auxMember;
}
return pos->getData();
}
template <class T>
std::string List<T>::toString() const
{
33
std::string resultado;
Node *aux(anchoir);
while (aux != nullptr)
{
resultado += aux->getData().toString() + "\n";
aux = aux->getNext();
}
return resultado;
}
template <class T>
int List<T>::numberOfMembers() {
int total(0);
Node* aux(anchoir);
while(aux != nullptr) {
aux = aux->getNext();
total++;
}
34
return total;
}
template <class T>
void List<T>::dateReport(const int date) {
Node* aux(anchoir);
while(aux != nullptr) {
Member auxiliar;
auxiliar = aux->getData();
int year = auxiliar.getEntryYear();
aux = aux->getNext();
if(year >= date){
cout << auxiliar.toString();
}
}
}
template <class T>
void List<T>::SortLinkedList(Node *head)
{
35
int swapped;
Node *lPtr; // left pointer will always point to the
start of the list
Node *rPrt = nullptr; // right pointer will always
point to the end of the list
do
{
swapped = 0;
lPtr = head;
while(lPtr->next != rPrt)
{
if (lPtr->data > lPtr->next->data)
{
swapDataPtr(lPtr, lPtr->next);
swapped = 1;
}
lPtr = lPtr->next;
}
//as the largest element is at the end of the
list, assign that to rPtr as there is no need to
36
//check already sorted list
rPrt = lPtr;
}
while(swapped);
}
template <class T>
void List<T>::deleteAll()
{
Node *aux;
while (anchoir != nullptr)
{
aux = anchoir;
anchoir = anchoir->getNext();
/// Liberamos memoria
delete aux;
}
}
37
template <class T>
List<T> &List<T>::operator=(const List<T> &lista1)
{
deleteAll();
copyAll(lista1);
return *this;
}
template <class T>
List<T>::~List()
{
deleteAll();
}
#endif // LIST_H_INCLUDED
38
Member.H
#ifndef MEMBER_H_INCLUDED
#define MEMBER_H_INCLUDED
#include <string>
using namespace std;
class Member{
private:
int memberNumber;
string memberName;
string address;
int entryYear;
public:
Member();
Member(const Member&);
void setMemberNumber(const int&);
void setMemberName(const string&);
void setAddress(const string&);
void setEntryYear(const int&);
39
int getMemberNumber();
string getMemberName();
string getAddress();
int getEntryYear();
Member& operator = (const Member&);
booloperator == (const Member&);
bool operator != (const Member&);
bool operator < (const Member&);
bool operator <= (const Member&);
bool operator > (const Member&);
bool operator >= (const Member&);
string toString();
};
#endif // MEMBER_H_INCLUDED
40
Menu.cpp
#include <iostream>
#include "Menu.h"
using namespace std;
Menu::Menu():cont(-1),j(0) {}
Menu::Menu(const Menu&
a):myList(a.myList),myMember(a.myMember),cont(a.cont) {}
Menu& Menu::operator=(const Menu& a)
{
myList = a.myList;
myMember = a.myMember;
cont = a.cont;
return *this;
}
//auxiliar variables
string myString;
int myInt, myNumber;
Member temporalMember;
41
void Menu::captureData()
{
char _opc = 's';
do
{
cout<<"\n\t\tREGISTRO DE SOCIOS"<<endl;
cout<<"\n\tIngrese los datos solicitados:"<<endl;
if(myList.isEmpty())
{
cout<<"\n\tNumero de Socio : ";
fflush(stdin);
cin>> myNumber;
myMember.setMemberNumber(myNumber);
cout<<"\n\tNombre del Socio: ";
fflush(stdin);
getline(cin,myString);
myMember.setMemberName(myString);
cout<<"\n\tDomicilio del Socio: ";
fflush(stdin);
getline(cin,myString);
42
myMember.setAddress(myString);
cout<<"\n\tAnio de Ingreso: ";
fflush(stdin);
cin>> myInt;
myMember.setEntryYear(myInt);
myList.insertData(myList.getLastPos(),
myMember);
myList.SortLinkedList(myList.getFirstPos());
cout << "\tDesea Ingresar otro Miembro? -> (S
| N) ";
cin>> _opc;
}
else
{
cout<<"\n\tNumero de Socio : ";
fflush(stdin);
cin>> myNumber;
myMember.setMemberNumber(myNumber);
Member auxMember =
myList.retrieve(myList.findData(myMember));
if(auxMember.getMemberNumber() == myNumber)
43
{
cout << "No puede haber mas de un socio
con el mismo numero"<< endl;
system("pause");
return;
}
cout<<"\n\tNombre del Socio: ";
fflush(stdin);
getline(cin,myString);
myMember.setMemberName(myString);
cout<<"\n\tDomicilio del Socio: ";
fflush(stdin);
getline(cin,myString);
myMember.setAddress(myString);
cout<<"\n\tAnio de Ingreso: ";
fflush(stdin);
cin>> myInt;
myMember.setEntryYear(myInt);
myList.insertData(myList.getLastPos(),
myMember);
myList.SortLinkedList(myList.getFirstPos());
44
cout << "\tDesea Ingresar otro Miembro? -> (S
| N) ";
cin>> _opc;
system("cls");
}
}
while(_opc=='s' or _opc=='S');
}
char Menu::showMenu() const
{
char op;
cout<<"\n\tMENU PRINCIPAL"<<endl;
cout<<"\ta.- Registrar un nuevo socio"<<endl;
cout<<"\tb.- Dar de baja un Socio del club"<<endl;
cout<<"\tc.- Generar reporte dada antiguedad"<<endl;
cout<<"\td.- Cambiar domicilio de un socio"<<endl;
cout<<"\te.- Generar un reporte con los datos de los
socios"<<endl;
45
cout<<"\tf.- Imprimir el total de socios
registrados"<<endl;
cout<<"\tg.- Salir"<<endl<<"\t--> ";
cin>>op;
return op;
}
void Menu::evaluateMenu()
{
char opc;
opc = showMenu();
system("cls");
switch(opc)
{
case 'a':
{
captureData();
system("cls");
46
}
break;
case 'b':
//dar de baja con numero de socio
cout <<"\t La lista de Socios es la siguiente..."
<< endl;
cout << myList.toString();
cout <<"\t Ingrese el Numero del Socio que desea
eliminar: ";
cin>> myInt;
myMember.setMemberNumber(myInt);
myList.deleteData(myList.findData(myMember));
system("pause");
system("cls");
break;
case 'c':
cout <<"\tIngrese el anio de antiguedad apartir
del cual desea el reporte de socios: ejemplo(2015);";
cin>> myInt;
myList.dateReport(myInt);
system("pause");
47
system("cls");
break;
case 'd':
{
cout <<"\t La lista de Socios es la siguiente..."
<< endl;
cout << myList.toString();
cout <<"\t Ingrese el numero del socio que desea
cambiar la direccion...";
cin>> myInt;
myMember.setMemberNumber(myInt);
Member temporalMember =
myList.retrieve(myList.findData(myMember));
cout <<"\t Ingrese la nueva direccion del socio:
";
fflush(stdin);
getline(cin,myString);
temporalMember.setAddress(myString);
myList.insertData(myList.findData(myMember),
temporalMember);
myList.deleteData(myList.findData(myMember));
system("pause");
48
system("cls");
break;
}
case 'e':
cout <<"\t Imprimiendo reporte con la informacion
de todos los usuarios..." << endl;
cout << myList.toString();
system("pause");
system("cls");
break;
case 'f':
cout <<"\t El numero total de Socios de la lista
es.." << endl;
cout << "\t " << myList.numberOfMembers() <<
endl;
system("pause");
system("cls");
break;
case 'g':
j=1;
system("cls");
49
break;
default:
cout<<"\n\t#ERROR, Ingresa una de las
opciones"<<endl;
system("pause");
system("cls");
break;
}
}
50