¿Cómo podría crear una lista en C++?

Question

¿Cómo puedo crear una lista en C++? Lo necesito para crear una lista vinculada. ¿Cómo voy a hacer eso? ¿Hay buenos tutoriales o ejemplos que pueda seguir?

Answer 1

Supongo que sabe que C++ ya tiene una clase de lista vinculada, y desea implementar la suya porque quiere aprender a hacerlo.

Primero, lea Why do we use arrays instead of other data structures?, que contiene una buena respuesta de las estructuras de datos básicas. Luego piense en cómo modelarlos en C++:

struct Node { 
    int data; 
    Node * next; 
}; 

¡Básicamente eso es todo lo que necesita para implementar una lista! (un muy simple).Sin embargo, no tiene abstracciones, tiene que vincular los artículos por mano:

Node a={1}, b={20, &a}, c={35, &b} d={42, &c}; 

Ahora, hay que tener una lista enlazada de nodos, todos asignados en la pila:

d -> c -> b -> a 
42 35 20 1 

El siguiente paso es escribir una clase contenedora List que apunta al nodo de inicio, y permite añadir nodos, según sea necesario, hacer el seguimiento de la cabeza de la lista (lo que sigue es muy simplificada):

class List { 
    struct Node { 
     int data; 
     Node * next; 
    }; 

    Node * head; 

public: 
    List() { 
     head = NULL; 
    } 

    ~List() { 
     while(head != NULL) { 
      Node * n = head->next; 
      delete head; 
      head = n; 
     } 
    } 

    void add(int value) { 
     Node * n = new Node; 
     n->data = value; 
     n->next = head; 
     head = n; 
    } 

    // ... 
}; 

el siguiente paso es hacer que la Lista sea una plantilla, de modo que pueda rellenar otros valores (no solo enteros).

Si está familiarizado con los punteros inteligentes, puede reemplazar los punteros sin formato utilizados con los punteros inteligentes. A menudo encuentro que la gente recomienda consejos inteligentes a los principiantes. Pero en mi opinión, primero debes entender por qué necesitas punteros inteligentes y luego usarlos. Pero eso requiere que primero se necesiten los indicadores crudos. De lo contrario, utiliza alguna herramienta mágica, sin saber por qué lo necesita.

Answer 2

Realmente debería usar el standard List class. A menos que, por supuesto, esta sea una pregunta de tareas, o si desea saber cómo STL implementa las listas.

Encontrarás muchos tutoriales sencillos a través de google, como this one. Si desea saber cómo funcionan las listas de enlaces "bajo el capó", intente buscar ejemplos/tutoriales de la lista C en lugar de C++.

Answer 3

Por qué reinventar la rueda. Solo use el contenedor de la lista STL.

#include <list> 

// in some function, you now do... 
std::list<int> mylist; // integer list 

More information...

Answer 4

ya estamos en el siglo 21 !! No intente implementar las estructuras de datos ya existentes. Intenta usar las estructuras de datos existentes.

uso de la biblioteca STL o Boost

Answer 5

Si se va a utilizar std::list, lo necesario para pasar un parámetro de tipo:

list<int> intList; 
list<int>* intListPtr = new list<int>; 

Si usted quiere saber cómo funcionan las listas, me recomendar buscando en Google para algunos C/C++ tutoriales para obtener una comprensión de ese tema. El siguiente paso sería aprender suficiente C++ para crear una clase de lista, y finalmente una clase de plantilla de lista.

Si tiene más preguntas, vuelva a preguntar aquí.

Answer 6

Supongo que esta es una pregunta para la tarea, por lo que probablemente quiera ir al here. Tiene un tutorial que explica las listas enlazadas, da un buen pseudocódigo y también tiene una implementación en C++ que puedes descargar.

Recomiendo leer la explicación y comprender el pseudocódigo antes de usar a ciegas la implementación. Este es un tema que realmente debe comprender en profundidad si desea continuar en CS.

Answer 7

Boost ptr_list

http://www.boost.org/doc/libs/1_37_0/libs/ptr_container/doc/ptr_list.html

HTH

Answer 8

Crear lista mediante C++ plantillas

es decir

template <class T> struct Node 
{ 
    T data; 
    Node * next; 
}; 

template <class T> class List 
{ 
    Node<T> *head,*tail; 

    public: 
     void push(T const&); // push element 
     void pop();   // pop element 
     bool empty()   // return true if empty. 
}; 

A continuación, puede escribir código como:

List<MyClass>; 

El tipo T no es dinámico en tiempo de ejecución. Solo es para el tiempo de compilación.

Para el ejemplo completo click hear.

Para el tutorial de plantillas C++ click hear.