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

Question

Как я могу создать список в C ++? Мне нужно, чтобы создать связанный список. Как бы я поступил так? Есть ли хорошие уроки или примеры, которым я мог бы следовать?

Answer 1

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

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

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, который указывает на начальный узел и позволяет при необходимости добавлять узлы, отслеживая заголовок списка (следующее очень упрощено):

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 шаблоном, чтобы вы могли добавлять другие значения (не только целые числа).

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

#include <list>

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

Подробнее ...

Answer 5

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

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

Answer 6

Создание списка с использованием C ++ шаблонов

* 1005 т.е. *

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 не является динамическим во время выполнения. Это только для времени компиляции.

Для полного примера нажмите «услышать» .

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

Answer 7

Boost ptr_list

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

НТН

Answer 8

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

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