Как я могу создать список в С++?

Ответ 1

Я понимаю, что вы знаете, что у С++ уже есть связанный класс списка, и вы хотите реализовать свое, потому что хотите узнать, как это сделать.

Сначала прочитайте Почему мы используем массивы вместо других структур данных?, который содержит хороший ответ на основные структуры данных. Затем подумайте о том, как смоделировать их в С++:

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

В принципе, все, что вам нужно для реализации списка! (очень простой). Однако у него нет абстракций, вам нужно привязать элементы к руке:

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

Теперь у вас есть связанный список узлов, все выделенные в стеке:

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

Следующий шаг - написать класс-оболочку List, который указывает на начало node, и позволяет добавлять узлы по мере необходимости, отслеживая головку списка (следующее упрощено):

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;
    }

    // ...
};

Следующий шаг - сделать шаблон List таким, чтобы вы могли набивать другие значения (а не только целые числа).

Если вы знакомы с интеллектуальными указателями, вы можете заменить необработанные указатели, используемые с интеллектуальными указателями. Часто я нахожу, что люди рекомендуют умные указатели для начинающих. Но, на мой взгляд, вы должны сначала понять, зачем вам нужны интеллектуальные указатели, а затем использовать их. Но для этого вам нужно сначала понять исходные указатели. В противном случае вы используете волшебный инструмент, не зная, зачем вам это нужно.

Ответ 2

Вы действительно должны использовать стандартный класс List . Если, конечно, это вопрос о домашнем задании, или вы хотите знать, как списки реализуются STL.

Вы найдете множество простых руководств через google, например этот. Если вы хотите знать, как связанные списки работают "под капотом", попробуйте найти примеры C/tutorials, а не С++.

Ответ 3

Если вы собираетесь использовать std::list, вам необходимо передать параметр типа:

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

Если вы хотите знать, как работают списки, я рекомендую googling для некоторых учебников C/С++, чтобы получить представление об этой теме. Следующим шагом будет обучение достаточно С++ для создания класса списка и, наконец, класс шаблона списка.

Если у вас есть еще вопросы, спросите здесь.

Ответ 4

Зачем изобретать колесо. Просто используйте контейнер списка STL.

#include <list>

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

Дополнительная информация...

Ответ 5

Я предполагаю, что это вопрос домашней работы, поэтому вы, вероятно, захотите пойти здесь. В нем есть учебник, объясняющий связанные списки, дает хороший псевдокод, а также имеет реализацию С++, которую вы можете скачать.

Я бы рекомендовал прочитать объяснение и понять псевдокод, прежде чем слепо использовать реализацию. Это тема, которую вы действительно должны понимать в глубину, если вы хотите продолжить работу в CS.

Ответ 6

Boost ptr_list

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

НТН

Ответ 7

Создайте список, используя шаблоны С++

то есть

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. 
}; 

Затем вы можете написать код, например:

List<MyClass>;

Тип T не является динамическим во время выполнения. Это только время компиляции.

В качестве полного примера нажмите "услышать" .

Для учебника по шаблонам С++ нажмите "услышать" .

Ответ 8

Мы уже в 21 веке! Не пытайтесь реализовать уже существующие структуры данных. Попытайтесь использовать существующие структуры данных.

Использовать библиотеку STL или Boost