Estructura de datos

[pic 1]

[pic 2]

[pic 3]

[pic 4]

[pic 5]

[pic 6]

DESARROLLO

 DESARROLLO DE LA TAREA:

1. Un inspector de un tren está indagando si el pasajero del asiento 23a está en el vagón de la imagen, para validar el proceso el inspector deberá consultar el ticket del pasajero. Indique qué operación de listas doblemente enlazadas está realizando el inspector. Explique con sus palabras y aplicando los conceptos tratados en los contenidos, la forma en la cual se desarrolla esta operación.

[pic 7]

Con las listas doblemente enlazadas, es posible realizar un recorrido en ambos sentidos. Para el caso, el inspector podría partir recorriendo desde la parte delantera del vagón o desde la parte trasera.

Como primera instancia, ya el inspector puede saber cuál es el inicio y cuál es el final, porque los extremos del vagón tienen un último asiento, el cual no tiene predecesor (o sucesor en el caso del último) En este caso asignaremos como primer nodo (inicio) al asiento de más adelante, por lo cual este asiento no tiene más elementos más hacia el frente del tren, y el de más a la cola del tren, no tendrá más asientos hacia atrás, o sea, sus flechas apuntarán a NULL. Con esta información, ya podemos hacer un recorrido, con lo cual, gracias a que se puede recorrer en ambos sentidos, no será necesario recorrer todos los nodos para llegar al dato requerido.

Ahora bien, la búsqueda precisa se puede lograr sabiendo la ubicación del asiento 23a, lo cual podemos conseguirlo sabiendo cuantos asientos hay por delante y cuantos por detrás. Con ello, incluso dependiendo desde donde nos movamos para recorrer, podemos llegar de una forma más exacta y rápida al nodo con el dato requerido. El inspector podría decir, por ejemplo, que la fila comienza en el 20, es decir tiene 3 nodos por la izquierda (si lo analizamos tal como mostramos las listas enlazadas en el gráfico), o sea los asientos 20, 21 y 22, y tiene 6 asientos por detrás o a la derecha, o sea los asientos, 24, 25, 26, 27 28 y 29.

1. Realice una tabla comparativa entre listas enlazadas y listas doblemente enlazadas, considerando 2 diferencias y/o similitudes en cada caso.

1.  Usando la siguiente imagen ejemplifique cómo se realiza operación de inserción de un nodo 20 entre el nodo 12 y el nodo 57. Explique paso a paso cómo se realiza el proceso.

[pic 8]

Para poder insertar un nuevo nodo a la lista enlazada, lo primero que debemos hacer es crearlo, para ello, en base a lo mostrado en el material de la Semana 6, se pueden utilizar los siguientes comandos en C++

Asumiendo que nuestra lista ya está creada, podríamos visualizar en C que tipo de dato existe y se ha definido que debe apuntar tanto hacia adelante como atrás.

struct nodo{

    int dato;

    nodo* siguiente;

    nodo* atras;

} *primero, *ultimo;

Dicho esto, la definición de los nodos de la lista doblemente enlazada deben estar creados y por lo tanto, tal como lo indica el enunciado de la pregunta 3, se procederá a realizar la inserción de un nodo 20 en la lista compuesta por los nodos 12, 57 y 95, insertándolo entre los dos primeros.

Podemos hacer un recorrido de la lista para verificar los datos existentes y a la vez poder verificar donde vamos a insertar el nuevo nodo.

void desplegarListaPrimeroUltimo(){

    nodo* actual = new nodo();

    actual = primero;

    if(primero!=NULL){

        do{

            cout << "\n " << actual->dato;

            actual = actual->siguiente;

        }while(actual!=primero);

    }else{

        cout << "\n La lista se Encuentra Vacia\n\n";

...