Servicio comunitario en un ancianato

Solo disponible en BuenasTareas
  • Páginas : 5 (1106 palabras )
  • Descarga(s) : 0
  • Publicado : 18 de marzo de 2011
Leer documento completo
Vista previa del texto
LOS ARBOLES BINARIOS:

Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunesde los árboles binarios son los árboles binarios de montículos binarios y Codificación de Huffman
En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente. En tales situaciones podríamos desear darle a cada celda sobre una lista un puntero a las celdas siguiente y anterior en lalista tal y como se muestra en la figura.

Otra ventaja de las listas doblemente enlazadas es que podemos usar un puntero a la celda que contiene el elemento de una lista para representar la posición i, mejor que usar el puntero a la celda anterior aunque lógicamente, también es posible la implementación similar a la expuesta en las listas simples haciendo uso de la cabecera. El único precioque pagamos por estas características es la presencia de un puntero adicional en cada celda y consecuentemente procedimientos algo más largos para algunas de las operaciones básicas de listas. Si usamos punteros (mejor que cursores) podemos declarar celdas que consisten en un elemento y dos punteros a través de:
typedef struct celda{
tipoelemento elemento;
struct celda*siguiente,*anterior;
}tipocelda;

typedef tipocelda *posicion;

Un procedimiento para borrar un elemento en la posición p en una lista doblemente enlazada es:void borrar (posicion p)
{
if (p->anterior != NULL)
p->anterior->siguiente = p->siguiente;
if (p->siguiente != NULL)
p->siguiente->anterior = p->anterior;
free(p);
}

El procedimiento anterior se expresa de forma gráfica en como muestra la figura:

Donde los trazoscontinuos denotan la situación inicial y los punteados la final. El ejemplo visto se ajusta a la supresión de un elemento o celda de una lista situada en medio de la misma. Para obviar los problemas derivados de los elementos extremos (primero y último) es práctica común hacer que la cabecera de la lista doblemente enlazada sea una celda que efectivamente complete el círculo, es decir, el anteriora la celda de cabecera sea la última celda de la lista y la siguiente la primera. De esta manera no necesitamos chequear para NULL en el anterior procedimiento borrar.
Por consiguiente, podemos realizar una implementación de listas doblemente enlazadas con cabecera tal que tenga una estructura circular en el sentido de que dado un nodo y por medio de los punteros siguientes podemos volver hastaél como se puede observar en la figura (de forma análoga para anterior).

Es importante notar que aunque la estructura física de la lista puede hacer pensar que mediante la operación siguiente podemos alcanzar de nuevo un nodo de la lista, la estructura lógica es la de una lista y por lo tanto habrá una posición primero y una posición fin de forma que al aplicar una operación anterior osiguiente respectivamente sobre estas posiciones el resultado será un error.
Respecto a la forma en que trabajarán las funciones de la implementación que proponemos hay que hacer constar los siguientes puntos:
* La función de creación debe alojar memoria para la cabecera y hacer que los punteros siguiente y anterior apunten a ella, devolviendo un puntero a dicha cabecera.
* La función...
tracking img