c++ - single - No entiendo por qué esta función "devuelve un puntero de la lista"

singly linked list java

Question

El libro que estoy leyendo, Introducción a las estructuras de datos con listas vinculadas (Presentación 21) , tiene 2 ejemplos de listas vinculadas. Aquí está el primero:

EnemySpaceShip* getNewEnemy ()
{
    EnemySpaceShip* p_ship = new EnemySpaceShip;
    p_ship->x_coordinate = 0;
    p_ship->y_coordinate = 0;
    p_ship->weapon_power = 20;
    p_ship->p_next_enemy = p_enemies;
    p_enemies = p_ship;
    return p_ship;
}

El segundo ejemplo de listas enlazadas es este:

EnemySpaceShip* addNewEnemyToList (EnemySpaceShip* p_list)
{
    EnemySpaceShip* p_ship = new EnemySpaceShip;
    p_ship->x_coordinate = 0;
    p_ship->y_coordinate = 0;
    p_ship->weapon_power = 20;
    p_ship->p_next_enemy = p_list;
    return p_ship;
}

Entonces el libro escribe esto:

Tenga en cuenta que esta función difiere de getNewEnemy porque devuelve un puntero a la lista, en lugar del nuevo enemigo.

Lo que no entiendo es lo que quiere decir con la "segunda función devuelve un puntero a la lista" y "la primera función devuelve el nuevo enemigo". Pensé que ambos habían creado un nuevo enemigo llamado p_ship (que es tanto un puntero como un nuevo enemigo) y lo devolvieron. ¿Qué se entiende por esta declaración?

Answer 1

Creo que el autor querría decir que la primera función está destinada a asignar un tipo de puntero "enemigo", la segunda función está destinada a asignar un tipo de puntero "lista de enemigos".

El tipo utilizado para implementar estos punteros es el mismo, pero su significado es diferente, así como su uso en el flujo lógico del programa.

Entonces el autor dice: atención, en el segundo caso está obteniendo algo que en el programa va a usar como una lista, no como un elemento de la lista ...

Por ejemplo, en este caso específico, la segunda función debería tener que asignar el parámetro p_list a su salida, de lo contrario, la p_list continúa apuntando al objeto enemigo anterior.

También considere que es más probable que getNewEnemy esté diseñado para trabajar con un tipo de datos abstracto u objeto, y addNewEnemyToList está diseñado para trabajar en un estilo "de procedimiento"

Answer 2

El primer getNewEnemy usa un campo p_enemies , que contiene la lista de enemigos. Se agrega al frente de la lista, cambiando p_enemies .

El segundo addNewEnemyToList utiliza un parámetro p_list pero deja p_list sin modificar (ya que es un parámetro de entrada). Por lo tanto, el resultado debe asignarse con toda razonabilidad a p_list para permitir que esa lista crezca en uno.

Uno esperaría:

p_enemies = addNewEnemyToList(p_enemies);

Aunque ambos apuntan a un nuevo enemigo, para mantener la lista, se puede decir que addNewEnemyToList devuelve la nueva lista.

Answer 3

Esta es la linea importante

p_ship->p_next_enemy = p_list;

Tenga en cuenta que p_ship tiene un puntero a p_next_enemy que en sí mismo es un EnemySpaceShip* . Por lo tanto, si sigues llamando a esta función una y otra vez, terminarás con una lista vinculada. Podría comenzar en la primera EnemySpaceShip* y recorrerlas todas en un bucle, por ejemplo

EnemySpaceShip* p_ship = p_first_ship;    // assume this was known
while (p_ship->p_next_enemy != nullptr)
{
    p_ship = p_ship->p_next_enemy;
    // p_ship has now advanced one element of your linked list
}

Además, debido al orden en que se están agregando estos envíos, si llamó varias veces a addNewEnemyToList , la última vez que lo llamó, obtendría un puntero al primer envío en la lista vinculada. Por eso el autor dice "devuelve un puntero a la lista".

Answer 4

Estoy de acuerdo con Vlad y simplemente votaría esa respuesta, pero si nos fijamos en los dos métodos desde una perspectiva de caja negra, ninguno implica dónde se agregará el nuevo enemigo.

El nombre del primer método indica que el enemigo recién creado es lo que se devolverá. Un efecto secundario es que se agrega a una lista de p_enemies. En mi opinión, esto sería una violación del principio de responsabilidad única, pero se podría aliviar con más contexto alrededor de ese método. Si el método se actualiza para agregar el nuevo elemento al final o se basa en un orden ordenado, ya no devolverá el encabezado de la lista.

El segundo método dice explícitamente que está agregando un nuevo enemigo a la lista pasada. No queda claro a partir de la definición qué se devuelve y esto podría ser confuso. ¿Debería devolver el nuevo enemigo o la lista actualizada? Si no devuelve la lista, ¿puede la persona que llama estar segura de que el nuevo elemento está al principio de la lista? ¿Qué sucede si los requisitos cambian y el nuevo elemento se agrega al final de la lista? No es una forma eficiente de agregar enemigos, pero es posible.

Parece que el libro puede estar tratando de señalar que se supone que la segunda función devuelve el encabezado de la lista y no el nuevo enemigo. En este caso, el hecho de que el jefe de la lista sea el nuevo enemigo es una coincidencia.

Answer 5

Incluso se podría decir que la función getNewEnemy () se puede reemplazar por addNewEnemyToList (NULL)

EnemySpaceShip* getNewEnemy ()
{
  p_enemies = addNewEnemyToList( NULL );
  return p_enemies;
}

O incluso eliminado si usas:

p_enemies = addNewEnemyToList( NULL );
p_enemies = addNewEnemyToList( p_enemies );

Answer 6

No creo que la oración tenga sentido.

Solo hay una diferencia entre las funciones. En la primera función, la lista de naves es global en relación con la función. Quizás es un miembro de datos de una clase y la función es una función de miembros de la clase que tiene acceso a los miembros de datos de la clase. O de hecho, la lista se declara en el espacio de nombres global.

En la segunda función, la lista se pasa a la función como un argumento.

Las dos funciones devuelven el puntero a los primeros nodos de las listas.

Si para eliminar el código no importante de las funciones y hacer que los nombres de las listas sean idénticos, entonces obtendrá

EnemySpaceShip* getNewEnemy ()
{
    EnemySpaceShip* p_ship = new EnemySpaceShip;
    //...
    p_ship->p_next_enemy = p_enemies;
    p_enemies = p_ship;
    return p_ship;
}


EnemySpaceShip* addNewEnemyToList (EnemySpaceShip* p_enemies)
{
    EnemySpaceShip* p_ship = new EnemySpaceShip;
    //...
    p_ship->p_next_enemy = p_enemies;
    return p_ship;
}

Como ves las funciones difieren solo en una declaración

p_enemies = p_ship;

que está presente en la primera función (porque tiene acceso a la propia lista original) y está ausente en la segunda función porque la función solo tiene una copia del encabezado de la lista (cambiar una copia del encabezado de la lista original sí lo hace). No cambie el cabezal original en sí mismo porque los parámetros son variables locales de funciones).

Puedes llamar a las dos funciones de la siguiente manera.

p_enemies = getNewEnemy();

p_enemies = addNewEnemyToList( p_enemies );

y como resultado p_enemies será la misma lista a la que se agregó un nodo.

Solo en la primera función se cambia la lista dentro de la función; en la segunda función debe asignar el puntero de retorno a la lista porque dentro de la función no se cambia la lista en sí.

Así puedo concluir que la oración solo confunde a los lectores. Se debe reescribir de alguna manera para aclarar lo que el autor iba a decir. :) Es muy importante en los libros para principiantes que todas las oraciones sean claras.