1 Objetivos

  • Seguimos usando enteros de tamaño fijo.
  • Seguir adquiriendo práctica y destreza con las características de C++ que lo hacen un mejor C (anotación del código, límites numéricos, deducción automática de tipo, size_t).
  • Conocer que es una biblioteca, como se crea y se usa además de diferenciarla de un archivo de cabecera.
  • Implementar los TADs vistos en los temas 2 y 3 de la asignatura.

2 Tratamiento de errores

  • Usamos el modelo empleado en el lenguaje C, es decir una variable de tipo entero global en la que almacenamos el valor 0 para indicar que la última operación ha funcionado bien o un valor distinto de 0 para indicar que ha habido un error.
  • Para ello empleamos la biblioteca liberror que construye el Makefile proporcionado. Esta biblioteca exporta estas dos funciones:
    • int8_t get_error(): Obtiene el último código de error guardado por una operación previa.
    • void set_error(int8_t e): Almacena el código de error de la operación previa.
  • En el código de partida entregado junto a este enunciado tienes ejemplos de programas principales que compilan y enlazan con esta biblioteca.

3 Enunciado

  • En esta segunda práctica vamos a implementar algunas de las operaciones habituales con los TADs siguientes:

    • Lista simplemente enlazada
    • Pila
    • Cola
    • Árbol binario ordenado
    • Grafo dirigido y no-dirigido

  • Recordad que seguimos empleando C++ como un mejor C, es decir, podremos emplear:

  • Tenemos como punto de partida los ficheros de cabecera .h para cada TAD

    • Lista: list.h
    • Pila: stack.h
    • Cola: queue.h
    • Arbol: tree.h
    • Grafo dirigido/no-dirigido: graph.h

3.0.1 list.h

  1. Explicación de las funciones de ListNode y List
    ListNodePtr listNodeCreate (Element e) :
    Reserva memoria, inicializa variables y devuelve el nodo creado con su campo key igual a e.
    std::string listNodeToString (ListNodePtr p) :
    Devuelve una representación como cadena del nodo p.
    ListPtr listCreate () :
    Reserva memoria, inicializa variables y devuelve la lista creada.
    void listInit (ListPtr l); :
    Inicializa las variables de instancia de la lista a valores apropiados.
    bool listInsert (ListPtr l, Element x, Position i) :
    Inserta en la lista l el elemento x en la posición i. Devuelve cierto si pudo hacerlo y falso en otro caso.
    Position listLocate (ListPtr l, Element x) :
    Devuelve la posición que ocupa el elemento x en la lista l, si hubiera duplicados devolverá la posición del primer x encontrado. Si x no está en la lista devuelve la constante NOPOS. La primera posición es la 1 (y no la 0).
    ListNodePtr listRetrieve (ListPtr l, Position i) :
    Devuelve el puntero al nodo que ocupa la posición i en la lista l. Si la posición no existe devuelve nullptr.
    bool listRemove (ListPtr l, Position p) :
    Elimina y libera la memoria del nodo en la posición p. Si no puede hacerlo devuelve falso y en caso contrario cierto. Al eliminar el nodo reenlaza correctamente los otros nodos implicados.
    void listMakeNull (ListPtr l) :
    Borra y libera la memoria de todos los nodos de la lista, dejándola como una lista vacía.
    ListNodePtr listFirst (ListPtr l) :
    Devuelve el puntero al primer nodo de la lista.
    std::string listToString (ListPtr l, char c) :
    Devuelve una representación como cadena de la lista l usando el carácter c como separador entre los elementos. Ya lo teneis implementado.
    uint64_t listSize (ListPtr l) :
    Devuelve el número de nodos en la lista.

3.0.2 stack.h

  1. Explicación de las funciones de Stack
    StackPtr stackCreate () :
    Reserva memoria y devuelve la pila creada.
    void stackPush (StackPtr s, Element x) :
    Apila el elemento x en la pila s.
    Element stackTop (StackPtr s) :
    Devuelve el elemento en la cabeza de la pila s. Si la pila está vacía invocará a la función set_error con el valor 1.
    Element stackPop (StackPtr s) :
    Devuelve el elemento en la cabeza de la pila s y lo desapila. Libera la memoria ocupada por ese elemento. No se puede desapilar de una pila vacía, si la pila está vacía invocará a la función set_error con el valor 1.
    bool stackEmpty (StackPtr s) :
    Devuelve cierto si la pila s está vacía.
    std::string stackToString (StackPtr s,char c) :
    Devuelve una representación como cadena de la pila s usando el carácter c como separador entre los elementos. Ya lo teneis implementado.

3.0.3 queue.h

  1. Explicación de las funciones de Queue
    QueuePtr queueCreate () :
    Reserva memoria y devuelve la cola creada.
    void queueEnqueue (QueuePtr q, Element x) :
    Encola x en la cola q.
    Element queueHead (QueuePtr q) :
    Devuelve el elemento en la cabeza de la cola q. si la cola está vacía invocará a la función set_error con el valor 1.
    Element queueDequeue (QueuePtr q) :
    Devuelve y desencola el elemento de la cabeza de la cola q. Libera la memoria ocupada por ese elemento. No se puede desencolar de una cola vacía, si la cola está vacía invocará a la función set_error con el valor 1.
    bool queueEmpty (QueuePtr q) :
    Devuelve cierto si la cola q está vacía.
    std::string queueToString (QueuePtr q, char c) :
    Devuelve una representación como cadena de la cola q usando el carácter c como separador entre los elementos. Ya lo teneis implementado.

3.0.4 tree.h

  1. Explicación de las funciones de TreeNode
    TreeNodePtr treeNodeCreate (Element e) :
    Reserva memoria, inicializa variables y devuelve el nodo creado con su campo key igual a e.
    TreePtr treeNodeLeftSibling (TreeNodePtr p) :
    Devuelve el hijo izquierdo del nodo p.
    TreePtr treeNodeRightSibling (TreeNodePtr p) :
    Devuelve el hijo derecho del nodo p.
    Element& treeNodeKey (TreeNodePtr p) :
    Devuelve la clave del nodo p.
    bool treeNodeIsLeaf (TreeNodePtr p) :
    Devuelve cierto si p es un nodo hoja.
    std::string treeNodeToString (TreeNodePtr p) :
    Devuelve una representación como cadena del nodo p. Está implementada en tree.h.
  1. Explicación de las funciones de Tree
    TreePtr treeCreate () :
    Reserva memoria, inicializa variables y devuelve el árbol creado.
    void treeDestroy (TreePtr t) :
    Libera toda la memoria ocupada por los nodos del arbol así como la del propio árbol.
    TreeNodePtr& treeRoot (TreePtr t) :
    Devuelve la raíz del árbol.
    bool treeEmpty (TreePtr t) :
    Devuelve cierto si el árbol está vacío, falso en caso contrario.
    bool treeInsert (TreePtr t, Element x) :
    Si el valor x no está en el árbol lo inserta en la posición que le corresponde y devuelve cierto, en caso contrario devuelve falso.
    bool treeRemove (TreePtr t, Element x) :
    Si el valor x está en el árbol lo elimina y devuelve cierto, si no, devuelve falso.
    void treeMakeNull (TreePtr t) :
    Libera toda la memoria ocupada por los nodos del arbol.
    uint32_t treeSize (TreePtr t) :
    Devuelve el número de nodos del árbol.
    uint32_t treeHeight (TreePtr t) :
    Devuelve la altura del árbol.
    uint32_t treeLeafTreeNodes (TreePtr t) :
    Devuelve el número de nodos hoja del árbol.
    TreeNodePtr treeSearch (TreePtr t, Element x) :
    Devuelve el nodo ocupado por el elemento x si está en el árbol y si no lo está devuelve nullptr.
    TreeNodePtr treeParent (TreePtr t, Element x) :
    Devuelve el nodo padre del nodo ocupado por el elemento x. Si x no tiene padre entonces devuelve nullptr.
    TreeNodePtr treeParent (TreePtr t, TreeNodePtr p) :
    Devuelve el nodo padre del nodo p. Si p no tiene padre entonces devuelve nullptr.
    TreeNodePtr treeMaximum (TreePtr t) :
    Devuelve el nodo cuya clave tiene el valor máximo.
    std::string treePreOrder (TreePtr t, char c) :
    Devuelve en una cadena la representación en pre-orden del árbol t. Para ello representa como una cadena cada nodo (nodeToString) y esta representación la separa de la del siguiente nodo con el carácter c.
    std::string treePostOrder (TreePtr t, char c) :
    Devuelve en una cadena la representación en post-orden del árbol t. Para ello representa como una cadena cada nodo (nodeToString) y esta representación la separa de la del siguiente nodo con el carácter c.
    std::string treeInOrder (TreePtr t, char c) :
    Devuelve en una cadena la representación en in-orden del árbol t. Para ello representa como una cadena cada nodo (nodeToString) y esta representación la separa de la del siguiente nodo con el carácter c.
    std::string treeByLevels (TreePtr t, char c) :
    Devuelve en una cadena la representación por niveles del árbol t. Para ello recorre cada nivel de izquierda a derecha y representa como una cadena cada nodo (nodeToString) y esta representación la separa de la del siguiente nodo con el carácter c.

    En este recorrido te puede resultar útil usar una cola para almacenar los valores del nivel actual. Con vistas a que sigáis practicando con el uso de la biblioteca estándar de C++ (ya habéis usado la clase std::string) se os propone que uséis el TAD cola que hay implementado en C++.

    • Por ejemplo, para crear una cola de NodePtr y encolar, desencolar en ella, lo haríamos así:

      1
2
3
4
5
6
7
8

      #include <queue>
NodePtr n = ...;
std::queue<NodePtr> nq;
nq.push(n)
if (not nq.empty()) {
  NodePtrp = nq.front();
  nq.pop();
}

    • Y aquí tienes un ejemplo completo de como usar una cola de caracteres:

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

      #include <queue>
#include <iostream>
int main(int argc, char *argv[]) {
  std::queue<char> cq;

  for (char c = 'a'; c < 'g'; c++)  cq.push(c);

  while (not cq.empty()) {
    char c = cq.front();
    cq.pop();
    std::cout << "cq-head: " << c << std::endl;
  }
  return 0;
}

3.0.5 graph.h

  1. Explicación de las funciones de Graph
    GraphPtr graphCreate (uint64_t nv, GraphType directed) :
    Reserva memoria para nv vértices, inicializa variables y devuelve el grafo creado.
    void graphDestroy (GraphPtr g) :
    Libera la memoria de los nodos que forman el grafo g y la propia memoria del grafo.
    void graphMakeNull (GraphPtr g) :
    Libera la memoria de los nodos que forman el grafo g.
    size_t graphVertexSize (GraphPtr g) :
    Devuelve el número de vértices del grafo g.
    size_t graphEdgeSize (GraphPtr g) :
    Devuelve el número de aristas del grafo g.
    bool graphInsert (GraphPtr g, size_t o, size_t e, weight_t w) :
    Inserta una arista con peso w entre dos vértices con valores o el vértice origen y valor e el vértice destino. Devuelve cierto si se ha podido crear y falso en caso contrario. Tendrá en cuenta si el grafo g es un grafo dirigido o no.
    std::vector<weight_t> dijkstra (GraphPtr g, size_t i) :
    Aplica el algoritmo de Dijkstra al grafo g desde el nodo i. Devuelve el resultado en un vector en el cada componente j representa el menor coste para llegar a ella desde el nodo i.
    std::vector<Edge> prim (GraphPtr g, size_t i) :
    Aplica el algoritmo de Prim al grafo g desde el nodo i. Devuelve el resultado en un vector en el que cada componente j representa una arista del árbol.

    El tipo std::vector<XXX> de C++ es similar a un array de C:

    • el elemento XXX entre <> representa el tipo de cada componente.
    • puede crecer en tiempo de ejecución usando la función push_back(v), la cual añade el elemento v al final del vector. Por ejemplo: 
      1
2
3
4

      std::vector<int> ve;
ve.push_back(3);
ve.push_back(7);
// ve == [3,7]
    • sabe la cantidad de elementos que tiene: 
      1

      assert(ve.size() == 2);
    std::string graphToString (GraphPtr g) :
    Devuelve representado como una cadena el grafo g. Está implementada en graph.h.

4 División del código fuente en archivos

  • Tendremos un único archivo de implementación por cada TAD (list.cc, stack.cc, queue.cc, tree.cc y graph.cc) con la implementación de todas las funciones del TAD correspondiente además de los #include necesarios para que no de errores de compilación. Estos archivos no contendrá ningún programa principal (main) pero sí podrán contener las funciones auxiliares que necesites.

  • Para poder probar tus funciones dispones de un programa principal de prueba para cada TAD. No es necesario entregarlos, si se hace no pasa nada

  • También puedes emplear el archivo Makefile para compilar y enlazar cada uno de estos programas principales.

  • Todos los archivos `.cc' se encontrarán dentro de una carpeta llamada irp2-p2.

5 Entrega. Requisitos técnicos

  • Requisitos que tiene que cumplir este trabajo práctico para considerarse válido y ser evaluado (si no se cumple alguno de los requisitos la calificación será cero):

  • El archivo entregado se llama irp2-p2.tgz (todo en minúsculas), no es necesario entregar ningún programa principal, sólo son necesarios tus archivos `.cc' en una carpeta llamada irp2-p2. A su vez, esta carpeta estará comprimida en el fichero llamado irp2-p2.tgz. Este archivo lo puedes crear así en el terminal:

    tar cfz irp2-p2.tgz irp2-p2

  • También puedes emplear el archivo Makefile que tienes en la carpeta de la práctica para generar el fichero de la entrega tal y como hemos visto en clase de prácticas: make tgz.

  • Al descomprimir el archivo irp2-p2.tgz se crea un directorio de nombre irp2-p2 (todo en minúsculas).

  • Dentro del directorio irp2-p2 estarán al menos los archivos list.cc, stack.cc, queue.cc, tree.cc y graph.cc (todos en minúsculas).

    Recuerda que los ficheros ‘.h’ no se deben modificar, de lo contrario tus ficheros ‘.cc’ no compilarán con el corrector. No es necesario entregarlos, si se hace no pasa nada.

  • Las clases, métodos y funciones implementados se llaman como se indica en el enunciado (respetando en todo caso el uso de mayúsculas y minúsculas). También es imprescindible respetar estrictamente los textos y los formatos de salida que se indican en este enunciado.

  • Al principio de todos los ficheros fuente (`.h’ y `.cc’) entregados y escritos por ti se debe incluir un comentario con el nombre y el NIF (o equivalente) de la persona que entrega la práctica, como en el siguiente ejemplo:

    // NIF: 12345678-Z
// NOMBRE: GARCIA PEREZ, LAURA

  • Un error de compilación/enlace implicará un cero en esa parte de la práctica.

  • Lugar y fecha de entrega : Recuerda que las entregas se realizan siempre en (y sólo en) https://pracdlsi.dlsi.ua.es en las fechas y condiciones allí publicadas. Puedes entregar la práctica tantas veces como quieras, sólo se corregirá la última entrega (las anteriores no se borran). El usuario y contraseña para entregar prácticas es el mismo que se utiliza en UACloud.

6 Detección de plagios/copias

  • En el Grado en Ingeniería Robótica, la Programación es una materia muy importante. La manera más efectiva de aprender a programar es programando y, por tanto, haciendo las prácticas correspondientes además de otros programas (más sencillos o más complicados, eso da igual).

  • Tratar de aprobar las asignaturas de programación sin programar (copiando) es complicado y obviamente, te planteará problemas para seguir otras asignaturas así como en tu futura vida laboral.

  • En una asignatura como Programación-II es difícil que alguien que no ha hecho las prácticas supere los exámenes de teoría o el de recuperación de prácticas.

  • IMPORTANTE:

    • Cada práctica debe ser un trabajo original de la persona que la entrega.

    • En caso de detectarse indicios de copia de una o más prácticas se tomarán las medidas disciplinarias correspondientes, informando a las direcciones de Departamento y de la EPS por si hubiera lugar a otras medidas disciplinarias adicionales.