Estructuras de Datos y Programación Orientada a Objetos: Árboles, Grafos, Paradigmas y C++

Estructuras de datos: árboles y grafos

ÁRBOL: estructura jerárquica con nodos dinámicos del mismo tipo.

• NODO RAÍZ: único en el primer nivel.
• TERMINAL (HOJA): nodos sin descendientes.
• ALTURA o PROFUNDIDAD: número de niveles.

Árboles binarios

BINARIO: cada nodo solo puede tener 0, 1 o 2 descendientes.

• PREORDEN
• INORDEN
• POSTORDEN

Grafos

GRAFO: compuesto por nodos y aristas.

• ARISTA: determina el PESO.
• DIRIGIDO: tiene sentido para cada peso.
• NO DIRIGIDO: no es jerárquico.

Representaciones

• MATRIZ DE ADYACENCIA: simétrica y con diagonal si no es dirigido; relaciona nodos con pesos.
• LISTA ENLAZADA: tantas como nodos.

Paradigmas de programación

Paradigma imperativo

IMPERATIVO: instrucciones secuenciales que cambian la dirección de memoria. Ejemplos: FORTRAN, COBOL, Pascal, C, Ada, Modula-2 (modularidad, encapsulamiento, no herencia).

Paradigma declarativo

DECLARATIVO: se centra en el qué y no en el cómo. Ejemplos: Hope, Miranda, Haskell, Prolog (cláusulas), Lisp (antiguo de alto nivel, listas, no destructivo, inteligencia artificial).

Paradigma orientado a objetos

• ENCAPSULACIÓN: datos ocultos, solo accesibles desde los métodos (private, protected) y dentro de la clase.
• ABSTRACCIÓN DE DATOS: no se conoce cómo se implementa; se utilizan las operaciones definidas para ese tipo de dato.
• POLIMORFISMO: distintas funciones con el mismo nombre se distinguen por la firma (número o tipo de argumentos; no por el valor devuelto).
• HERENCIA: atributos y métodos propios más heredados de la base. Lenguajes: Smalltalk, C++, Java.

Lenguajes de programación

• JAVA: multiplataforma, orientado a red; 80% compilado y 20% interpretado (bytecode ejecutado por la máquina virtual).
• PERL: script (interpretado).
• PHP: web.
• FORTRAN: matemáticas.
• COBOL: gestión.
• PYTHON: interpretado.
• PASCAL: propósito general (compilado).
• OBJECTIVE-C: desarrollo GNU, orientado a objetos.
• XML: marcado.
• DELPHI: herramienta de desarrollo.

Ejemplos en C++

Clase con encapsulación y amistad

class Dai {
 public:
  Dai(char* = "");
  Dai(Dai&);
  ~Dai();
  const char* lee() const;
  void inser(char*);
  friend class Modulo;
 private:
  char* asig;
};

Clase amiga con acceso a datos privados

class Mod {
 public:
  void min(Dai&);
 private:
};

void Modulo::min(Dai& v) {
  if (v.asi < 1) cout << "NO";
}

main() {
  Dai pri;
  Mod des;
  des.min(pri);
}

Herencia

class Mod : public Dai {
 public:
  void inserta(char*);
 private:
};

main() {
  Mod pri;
  pri.inser;
  pri.inserta;
}

Para herencia múltiple se usa :: para diferenciar los miembros.

Mod::Mod(char*) : Dai(asi) {
  m = new char;
}

void Mod::carga(char* m, char* asi) {
  Dai::carga(asi);
  delete[] m;
  m = new char[strlen(asi) + 1];
  strcpy(m, asi);
}

Funciones virtuales y polimorfismo

class Ani {
  virtual void cm();
};

class Lob : public Ani {
  virtual void cm();
};

Ani* v[2];
v[0] = new Ani;
v[1] = new Lob;
v[0]->cm();
v[1]->cm();

Sobrecarga de operadores

int operator==(Dai);

int Dai::operator==(Dai v) {
  if (v.asi == asi) return 1;
  else return 0;
}

Dai& operator=(Dai);

Dai& Dai::operator=(Dai v) {
  if (v == *this) return *this;
  else asi = v.asi;
  return *this;
}

int operator+(Dai);

int Dai::operator+(Dai v) {
  return asi + v.asi;
}

const char* Dai::lee() const {
  return asi;
}

Operadores que no pueden sobrecargarse: ., ?:, .*, :: y sizeof.

Conceptos adicionales de C++

• CLASE ABSTRACTA: sin objetos propios; solo se hereda.
• FUNCIÓN VIRTUAL PURA: sin código; vinculación dinámica en tiempo de ejecución.
• ENTRADA/SALIDA: cout.setf(ios::left); cout << ""; cout.unsetf(ios::left);
• HERENCIA MÚLTIPLE: puede generar ambigüedad; usar :: para evitarla.
• ACCESO EN HERENCIA: si la base es privada, en la derivada es inaccesible; prevalece siempre el nivel de acceso más restrictivo.
• MÉTODOS INSPECTORES: devuelven información sin modificar el objeto.
• INLINE: ahorra tiempo en la llamada al evitar la sobrecarga del cambio de contexto, a costa de aumentar el tamaño del código. Puede ser método o función amiga; sobrecarga las macros y no permite el paso de parámetros.