ACTIVIDAD VOLUNTARIA: BÚSQUEDA EN ANCHURA EN GRAFOS DIRIGIDOS Y NO DIRIGIDOS

Realizada por:

• Cristian López Fernández
• Nadir Lara Sánchez
• Carlos García Ruiz

ACTIVIDAD

Actividad Voluntaria ABOE

Aqui se encuentra la actividad:

ActividadVoluntaria.pdf

Realizada por Cristian López Fernández y Rafael Jesús Leal Abad

Implementación del tipo pila usando celdas enlazadas

Aquí tenemos el código de la implementación de un TAD tipo pila usando celdas enlazadas. Se podrían incluir más funciones en dicha implementación.

#ifndef __PILA_HPP__

#define __PILA_HPP__

#include "pilainterfaz.hpp"

#include

#include

using namespace std;

namespace ed

{

template

struct Nodo

{

G Data;

Nodo *antiguo;

};

template

class Pila:public PilaInterfaz

{

private:

int _tamanyo;

int _limite;

Nodo *_cima;

public:

Pila(int m)

{

tamanyo(0);

limite(m);

_cima=NULL;

}

Pila &operator=(const Pila &x) throw()

{

int i;

G v[x.tamanyo()];

tamanyo(0);

limite(x.limite());

Nodo *aux;

aux= new Nodo;

aux=x._cima;

for(i = 0; i < x.tamanyo(); i++)

{

v[i]=aux->Data;

aux=aux->antiguo;

}

for(i=tamanyo()-1; i >=0; i--)

{

apilar(v[i]);

}

return *this;

}

void apilar(const G &n) throw()

{

assert(tamanyo() < limite());

Nodo *siguiente;

siguiente= new Nodo;

siguiente->Data=n;

siguiente->antiguo=_cima;

_cima=siguiente;

tamanyo(tamanyo()+1);

}

void desapilar() throw ()

{

assert(not estaVacia());

Nodo *aux=_cima;

_cima=_cima->antiguo;

delete aux;

tamanyo(tamanyo()-1);

}

const G & cima () const throw ()

{

assert(not estaVacia());

return _cima->Data;

}

bool estaVacia () const throw ()

{

if (tamanyo()==0)

return true;

else

return false;

}

bool estaLlena () const throw ()

{

if (tamanyo()==limite())

return true;

else

return false;

}

int limite() const throw()

{

return _limite;

}

int tamanyo() const throw()

{

return _tamanyo;

}

void limite(int m) throw()

{

_limite=m;

}

void tamanyo(const int &x) throw()

{

_tamanyo=x;

}

};

}

#endif

Organización de Ficheros

Actividad voluntaria 3

2.2. Registro de los bloques libres:

Se utilizan por lo general dos métodos:

• La lista de bloques libres como lista ligada.
• Un mapa de bits.

Lista ligada de bloques de disco:

• Cada bloque contiene tantos números de bloques libres como pueda.
• Los bloques libres se utilizan para contener a la lista de bloques libres.

Mapa de bits:

• Un disco con “n” bloques necesita un mapa de bits con “n” bits.
• Los bloques libres se representa con “1” y los asignados con “0” (o viceversa).
• Generalmente este método es preferible cuando existe espacio suficiente en la memoria principal para contener completo el mapa de bits.

5.3. Mecanismo de Proteccion: Lista de Posibilidades:

La matriz de protección también puede dividirse por renglones

• Se le asocia a cada proceso una lista de objetos a los cuales puede tener acceso.
• Se le indican las operaciones permitidas en cada uno.
• Esto define su dominio.

La lista de objetos se denomina lista de posibilidades y los elementos individuales se llaman posibilidades.

Cada posibilidad tiene:

• Un campo tipo:
• Indica el tipo del objeto.
• Un campo derechos:
• Mapa de bits que indica las operaciones básicas permitidas en este tipo de objeto.
• Un campo objeto:
• Apuntador al propio objeto (por ej.: su número de nodo-i).

Las listas de posibilidades son a su vez objetos y se les puede apuntar desde otras listas de posibilidades; esto facilita la existencia de subdominios compartidos.

Las listas de posibilidades o listas-c deben ser protegidas del manejo indebido por parte del usuario.

Los principales métodos de protección son:

• Arquitectura marcada:
• Necesita un diseño de hardware en el que cada palabra de memoria tiene un bit adicional:
• Indica si la palabra contiene una posibilidad o no.
• Solo puede ser modificado por el S. O.
• Lista de posibilidades dentro del S. O.:
• Los procesos hacen referencia a las posibilidades mediante su número.
• Lista de posibilidades cifrada dentro del espacio del usuario:
• Cada posibilidad está cifrada con una clave secreta desconocida por el usuario.
• Muy adecuado para sistemas distribuidos.

Generalmente las posibilidades tienen derechos genéricos aplicables a todos los objetos, por ej. :

• Copiar posibilidad:
• Crear una nueva posibilidad para el mismo objeto.
• Copiar objeto:
• Crear un duplicado del objeto con una nueva posibilidad.
• Eliminar posibilidad:
• Eliminar un dato dentro de la lista-c sin afectar al objeto.
• Destruir objeto:
• Eliminar en forma permanente un objeto y una posibilidad.

Muchos sistemas con posibilidades se organizan como una colección de módulos con módulos administradores de tipos para cada tipo de objeto y entonces es esencial que el módulo administrador de tipos pueda hacer más cosas con la posibilidad que un proceso ordinario.