Implementación de Estructuras de Datos y Algoritmos en C++

1.-   Matrices (4 puntos)

A)

(1.5 puntos)

 Considéresé el espacio vectorial inducido por los vectores en Rn. Considéresé la clase matrix_t que almacena una matriz de mxn en la que cada fila de la matriz representa un vector. Impleméntese un método de la clase matrix_t, al que se le pasa como parámetro un vector v de la clase vector_t y determina el número de vectores fila perpendiculares a v.

Para alcanzar este objetivo se deben efectuar los siguientes pasos:

i.- (0.5) Implementar un método T scalprod(const vector_t<T>& v, int row) const de la clase matrix_t que devuelva el producto escalar entre el vector v y el vector fila row de la matriz invocante.

T scalprod(const vector_t<T>& v, int row) const
{ T sp = 0;

  for(int j = 0; j <n_; j++)
    Sp += get(row, j + 1) * v.get_v(j);
  return sp;
}

ii.- (0.5) Implementar un método int num_perpendicular(const vector_t<int>& v, double eps = 0.0) const de la clase matrix_t que devuelva el número de vectores perpendiculares para el caso de que T sea de tipo entero.

int num_perpendicular(const vector_t<T>& v, double eps = 0.0) const
{ int num = 0;

  for(int i = 1; i <= m_; i++)
    if (scalprod(v, i) == 0)
      Num ++;
  return num;
}

iii.- (0.5) Implementar un método int num_perpendicular(const vector_t<double>& v, double eps = 0.0) const que devuelva el número de vectores perpendiculares para el caso de que T sea de tipo double.

int matrix_t<double>::num_perpendicular(const vector_t<double>& v, double eps) const
{ int num = 0;

  for(int i = 1; i <= m_; i++)
    if (fabs(scalprod(v, i)) < eps)
      Num ++;
  return num;
}

b) (2.0 puntos)
 Considéresé el espacio afín inducido por los puntos en Rn. Considéresé la clase matrix_t que almacena una matriz de mxn en la que cada fila de la matriz representa un punto. Impleméntese un método de la clase matrix_t, al que se le pasa como parámetro un punto p  y determínese cuál es el punto de la matriz que está a la menor distancia.

Para alcanzar este objetivo se deben efectuar los siguientes pasos:

i.- (0.5) Implementar un método de la clase matrix_t double distancia_l1(double* p, int row) que calcule la distancia según norma L1 entre el punto p y el punto inducido por la filarow de la matriz.

double distancia_l1(double* p, int row) const
{ T sp = 0;

  for (int j = 0; j <n_; j++)
    Sp += fabs(get(row, j + 1) - p[j]);
  return sp;
}

ii.- (0.5) Implementar un método de la clase matrix_t double distancia_l2(double* p, int row) que calcule la distancia según norma L2 entre el punto p y el punto inducido por la filarow de la matriz.

double distancia_l2(double* p, int row) const
{ T sp = 0;

  for (int j = 0; j <n_; j++)
    Sp +=  (get(row, j + 1) - p[j]) * (get(row, j + 1) - p[j]);
  return sqrt(sp);
}

iii.-(0.5) Implementar un método de la clase matrix_t int punto_menor_distancia_l1(double* p) que devuelva el índice del primer punto de la matriz con menor distancia al punto p.

int punto_menor_distancia_l1(double* p)
{ int fila = 1;
  double menor = distancia_l1(p,1);

  for(int i = 2; i <= m_; i++)
    if (distancia_l1(p, i) < menor) {
      Menor = distancia_l1(p, i);
      Fila = i;
    }
  return fila;
}

iv.-(0.5) Implementar un método de la clase matrix_t int punto_menor_distancia_l2(double* p) ) que devuelva el índice del primer punto de la matriz con menor distancia al punto p.

int ultima_fila_menor_distancia_l2(double* p)
{ int fila = 1;
  double menor = distancia_l2(p,1);

  for(int i = 2; i <= m_; i++)
    if (distancia_l2(p, i) < menor) {
      Menor = distancia_l2(p, i);
      Fila = i;
    }
  return fila;
}

c) (0,5 puntos)  Implementar un método para la clase matrix_t<int> que devuelva la columna que alberga la primera ocurrencia del mayor valor de la diagonal secundaria, con la premisa de que la matriz es cuadrada.

int matrix_t<int>::col_max_DS(void) const
{ int max_inx = n_;
  int max_val = get(1, n_);

  for(int i = 2; i <= m_; i++) {
    if (get(i,n_ - i + 1) > max_val) {
      Max_inx = n_ - i + 1;
      Max_val = get(i,n_ - i + 1);
  }
  return max_inx;
}

2.- Recursividad (1 punto)

Considéresé la función de Ackermann. Implementar un algoritmo recursivo que calcule el valor de la función para cualquier par de términos.

int Ackerman(int x, int y)
{ if (x==0)
    return y+1;
  else {
    if (y==0) return Ackerman(x-1, 1);
    else      return Ackerman(x-1, Ackerman(x, y-1));
  }
}

3.- Listas (5 puntos)

A) (0.5) Desarrollar el procedimiento void dll_t::remové(dll_node_t*)

template <class T>
void dll_t<T>::remové(dll_node_t<T>* n)
{ assert(n != NULL);

  if (n->get_prev() != NULL)
    N->get_prev()->set_next(n->get_next());
  else {
    Head_ = n->get_next();
    Head_->set_prev(NULL);
  }

  if (n->get_next() != NULL) 
    N->get_next()->set_prev(n->get_prev());
  else {
    Tail_ = n->get_prev();
    Tail_->set_next(NULL);
  }

  N->set_next(NULL);
  N->set_prev(NULL);
  delete n;
  Sz_--;
}

b) (0.5) Para la clase dll_t<int>, desarrollar el método especializado template<> int dll_t<int>::sum(void) que devuelve la suma de todos los valores de la lista.

template<>
int dll_t<int>::sum(void)
{ int s = 0;
  Dll_node_t<int> *ptr = get_head();
  while (ptr != NULL) {
    S += ptr->get_data();
    Ptr = ptr->get_next();
  }
  return s;
}

c) (0.5) Para la clase dll_t<int>, desarrollar el método especializado template<> dll_node_t<int>* dll_t<int>::find(const int v) que busca un valor dentro de la lista, devolviendo el puntero del nodo que lo contiene o NULL si no lo encuentra.

template<>
Dll_node_t<int>* dll_t<int>::find(const int v)
{ dll_node_t<int> *ptr = get_head();
  while (ptr != NULL && ptr->get_data() != v)
    Ptr = ptr->get_next();
  return ptr;
}

d) (1.0) Desarrollar el método template <class T> void dll_t<T>::invert(void) que invierte el orden de los valores de una lista sobre ella misma (sin usar lista auxiliar
)
.

template <class T>
void dll_t<T>::invert(void)
{ assert(!empty());
  Dll_node_t<T> *ini = get_head(), *fin = get_tail();
  
  int i = 1;
  while (i <= sz_ / 2) {
    T temp = ini->get_data();
    Ini->set_data(fin->get_data());
    Fin->set_data(temp);
    Ini = ini->get_next();
    Fin = fin->get_prev();
    I++;
  }
}

e) (1.0) Desarrollar el procedimiento void merge(dll_t<int>& L1, dll_t<int>& L2, dll_t<int>& R) que fusiona dos listas de enteros L1 y L2, y devuelve el resultado en R.

void merge(dll_t<int>& L1, dll_t<int>& L2, dll_t<int>& R)
{ dll_node_t<int> *ptr1 = L1.get_head(), *ptr2 = L2.get_head();

  while (ptr1 != NULL && ptr2 != NULL) {
    if (ptr1->get_data() <= ptr2->get_data()) {
      //cout << ptr1->get_data() << " ";
      R.insert_tail(new dll_node_t<int>(ptr1->get_data()));
      Ptr1 = ptr1->get_next();
    }
    else if (ptr1->get_data() > ptr2->get_data()) {
      //cout << ptr2->get_data() << " ";
      R.insert_tail(new dll_node_t<int>(ptr2->get_data()));
      Ptr2 = ptr2->get_next();
    }
  }
  
  while (ptr1 != NULL) {
    R.insert_tail(new dll_node_t<int>(ptr1->get_data()));
    Ptr1 = ptr1->get_next();
  }

  while (ptr2 != NULL) {
    R.insert_tail(new dll_node_t<int>(ptr2->get_data()));
    Ptr2 = ptr2->get_next();
  }
}

f) (1.5) Desarollar el procedimiento void dll_union(dll_t<int>& A, dll_t<int>& B, dll_t<int>& C) que realiza la uníón (tipo conjunto) de dos listas no ordenadas A y B con elementos no repetidos, y devuelve el resultado en la lista C. Para ello, puede usarse la funcionalidad desarrollada en el apartado (c). Por ejemplo, si A={2,1,4,3} y B={1,5,3,6}, el resultado sería C={2,4,1,5,3,6}.

void dll_union(dll_t<int>& A, dll_t<int>& B, dll_t<int>& C)
{ dll_node_t<int> *ptr = A.get_head();

  // inserta los elementos de A que no están en B
  while (ptr != NULL) {
    if (B.find(ptr->get_data()) == NULL)
      C.insert_tail(new dll_node_t<int>(ptr->get_data()));
    Ptr = ptr->get_next();
  }

  // inserta todos los elementos de B
  Ptr = B.get_head();
  while (ptr != NULL) {
    C.insert_tail(new dll_node_t<int>(ptr->get_data()));
    Ptr = ptr->get_next();
  }
}