Простой связанный список в С++

Ответ 1

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

#include <iostream>
using namespace std;

class LinkedList{
    // Struct inside the class LinkedList
    // This is one node which is not needed by the caller. It is just
    // for internal work.
    struct Node {
        int x;
        Node *next;
    };

// public member
public:
    // constructor
    LinkedList(){
        head = NULL; // set head to NULL
    }

    // destructor
    ~LinkedList(){
        Node *next = head;

        while(next) {              // iterate over all elements
            Node *deleteMe = next;
            next = next->next;     // save pointer to the next element
            delete deleteMe;       // delete the current entry
        }
    }

    // This prepends a new value at the beginning of the list
    void addValue(int val){
        Node *n = new Node();   // create new Node
        n->x = val;             // set value
        n->next = head;         // make the node point to the next node.
                                //  If the list is empty, this is NULL, so the end of the list --> OK
        head = n;               // last but not least, make the head point at the new node.
    }

    // returns the first element in the list and deletes the Node.
    // caution, no error-checking here!
    int popValue(){
        Node *n = head;
        int ret = n->x;

        head = head->next;
        delete n;
        return ret;
    }

// private member
private:
    Node *head; // this is the private member variable. It is just a pointer to the first Node
};

int main() {
    LinkedList list;

    list.addValue(5);
    list.addValue(10);
    list.addValue(20);

    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    // because there is no error checking in popValue(), the following
    // is undefined behavior. Probably the program will crash, because
    // there are no more values in the list.
    // cout << list.popValue() << endl;
    return 0;
}

Я настоятельно рекомендую вам прочитать немного о C++ и объектно-ориентированном программировании. Хорошая отправная точка может быть такой: http://www.galileocomputing.de/1278?GPP=opoo

РЕДАКТИРОВАТЬ: добавил поп-функцию и некоторые выходные данные. Как вы видите, программа выдвигает 3 значения 5, 10, 20, а затем выдает их. После этого порядок меняется на обратный, потому что этот список работает в режиме стека (LIFO, Last in First out)

Ответ 2

Вам следует взять указатель на голову. В противном случае модификация указателя не будет видна вне функции.

void addNode(struct Node *&head, int n){
    struct Node *NewNode = new Node;
 NewNode-> x = n;
 NewNode -> next = head;
 head = NewNode;
}

Ответ 3

Обе функции ошибочны. Прежде всего функция initNode имеет запутанное имя. Он должен называться как, например, initList и не должен выполнять задачу addNode. То есть, он не должен добавлять значение в список.

На самом деле, нет смысла в функции initNode, потому что инициализация списка может быть выполнена при определении головы:

Node *head = nullptr;

или

Node *head = NULL;

Таким образом, вы можете исключить функцию initNode из вашего дизайна списка.

Также в вашем коде нет необходимости указывать расширенное имя типа для структуры Node, которая должна указывать ключевое слово struct before name Node.

Функция addNode должна изменить исходное значение головы. В реализации функции вы изменяете только копию головы, переданную в качестве аргумента функции.

Функция может выглядеть так:

void addNode(Node **head, int n)
{
    Node *NewNode = new Node {n, *head};
    *head = NewNode;
}

Или, если ваш компилятор не поддерживает новый синтаксис инициализации, вы можете написать

void addNode(Node **head, int n)
{
    Node *NewNode = new Node;
    NewNode->x = n;
    NewNode->next = *head;
    *head = NewNode;
}

Или вместо указателя на указатель вы можете использовать ссылку на указатель на Node. Например,

void addNode(Node * &head, int n)
{
    Node *NewNode = new Node {n, head};
    head = NewNode;
}

Или вы можете вернуть обновленную голову из функции:

Node * addNode(Node *head, int n)
{
    Node *NewNode = new Node {n, head};
    head = NewNode;
    return head;
}

И в main напишите:

head = addNode(head, 5);

Ответ 4

Функция addNode должна иметь возможность изменять head. Как теперь написано, просто изменяется локальная переменная head (параметр).

Изменение кода на

void addNode(struct Node *& head, int n){
    ...
}

решит эту проблему, потому что теперь параметр head передается по ссылке, и вызываемая функция может мутировать его.

Ответ 5

head определяется внутри основного следующим образом.

struct Node *head = new Node;

Но вы меняете голову только в функциях addNode() и initNode(). Изменения не отражаются на главном.

Сделайте объявление головы глобальным и не передавайте его функциям.

Функции должны быть следующими.

void initNode(int n){
    head->x = n;
    head->next = NULL;
}

void addNode(int n){
    struct Node *NewNode = new Node;
    NewNode-> x = n;
    NewNode->next = head;
    head = NewNode;
}

Ответ 6

Я присоединяюсь к битве. С тех пор я написал C. Кроме того, здесь нет полных примеров. Код OP в основном C, поэтому я пошел вперед и включил его в GCC.

Проблемы были рассмотрены ранее; указатель next не продвигался. В этом суть проблемы.

Я также воспользовался возможностью, чтобы сделать предлагаемое редактирование; вместо двух функций на malloc, я помещал его в initNode(), а затем использовал initNode() to malloc оба (malloc - это "C новый", если вы это сделаете). Я изменил initNode(), чтобы вернуть указатель.

#include <stdlib.h>
#include <stdio.h>

// required to be declared before self-referential definition
struct Node;

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

struct Node* initNode( int n){
    struct Node *head = malloc(sizeof(struct Node));
    head->x = n;
    head->next = NULL;
    return head;
}

void addNode(struct Node **head, int n){
 struct Node *NewNode = initNode( n );
 NewNode -> next = *head;
 *head = NewNode;
}

int main(int argc, char* argv[])
{
    struct Node* head = initNode(5);
    addNode(&head,10);
    addNode(&head,20);
    struct Node* cur  = head;
    do {
        printf("Node @ %p : %i\n",(void*)cur, cur->x );
    } while ( ( cur = cur->next ) != NULL );

}

компиляция: gcc -o ll ll.c

выход:

Node @ 0x9e0050 : 20
Node @ 0x9e0030 : 10
Node @ 0x9e0010 : 5

Ответ 7

Ниже приведен пример связанного списка

    #include <string>
    #include <iostream>

    using namespace std;


    template<class T>
    class Node
    {
    public:
        Node();
        Node(const T& item, Node<T>* ptrnext = NULL);
        T value;
        Node<T> * next;
    };

    template<class T>
    Node<T>::Node()
    {
        value = NULL;
        next = NULL;
    }
    template<class T>
    Node<T>::Node(const T& item, Node<T>* ptrnext = NULL)
    {
        this->value = item;
        this->next = ptrnext;
    }

    template<class T>
    class LinkedListClass
    {
    private:
        Node<T> * Front;
        Node<T> * Rear;
        int Count;
    public:
        LinkedListClass();
        ~LinkedListClass();
        void InsertFront(const T Item);
        void InsertRear(const T Item);
        void PrintList();
    };
    template<class T>
    LinkedListClass<T>::LinkedListClass()
    {
        Front = NULL;
        Rear = NULL;
    }

    template<class T>
    void LinkedListClass<T>::InsertFront(const T  Item)
    {
        if (Front == NULL)
        {
            Front = new Node<T>();
            Front->value = Item;
            Front->next = NULL;
            Rear = new Node<T>();
            Rear = Front;
        }
        else
        {
            Node<T> * newNode = new Node<T>();
            newNode->value = Item;
            newNode->next = Front;
            Front = newNode;
        }
    }

    template<class T>
    void LinkedListClass<T>::InsertRear(const T  Item)
    {
        if (Rear == NULL)
        {
            Rear = new Node<T>();
            Rear->value = Item;
            Rear->next = NULL;
            Front = new Node<T>();
            Front = Rear;
        }
        else
        {
            Node<T> * newNode = new Node<T>();
            newNode->value = Item;
            Rear->next = newNode;
            Rear = newNode;
        }
    }
    template<class T>
    void LinkedListClass<T>::PrintList()
    {
        Node<T> *  temp = Front;
        while (temp->next != NULL)
        {
            cout << " " << temp->value << "";
            if (temp != NULL)
            {
                temp = (temp->next);
            }
            else
            {
                break;
            }
        }
    }

    int main()
    {
        LinkedListClass<int> * LList = new LinkedListClass<int>();
        LList->InsertFront(40);
        LList->InsertFront(30);
        LList->InsertFront(20);
        LList->InsertFront(10);
        LList->InsertRear(50);
        LList->InsertRear(60);
        LList->InsertRear(70);
        LList->PrintList();
    }

Ответ 8

Использование:

#include<iostream>

using namespace std;

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

Node *head = NULL;
Node *tail = NULL;

void AddnodeAtbeggining(){
    Node *temp = new Node;
    cout << "Enter the item";
    cin >> temp->num;
    temp->next = NULL;
    if (head == NULL)
    {
        head = temp;
        tail = temp;
    }
    else
    {
        temp->next = head;
        head = temp;
    }
}

void addnodeAtend()
{
    Node *temp = new Node;
    cout << "Enter the item";
    cin >> temp->num;
    temp->next = NULL;
    if (head == NULL){
        head = temp;
        tail = temp;
    }
    else{
        tail->next = temp;
        tail = temp;
    }
}

void displayNode()
{
    cout << "\nDisplay Function\n";
    Node *temp = head;
    for(Node *temp = head; temp != NULL; temp = temp->next)
        cout << temp->num << ",";
}

void deleteNode ()
{
    for (Node *temp = head; temp != NULL; temp = temp->next)
        delete head;
}

int main ()
{
    AddnodeAtbeggining();
    addnodeAtend();
    displayNode();
    deleteNode();
    displayNode();
}

Ответ 9

Я думаю, что, чтобы удостовериться, что в каждом списке node указано значение indeep, метод addNode должен быть таким:

void addNode(struct node *head, int n) {
  if (head->Next == NULL) {
    struct node *NewNode = new node;
    NewNode->value = n;
    NewNode->Next = NULL;
    head->Next = NewNode;
  }
  else 
    addNode(head->Next, n);
}

Ответ 10

В коде есть ошибка:

void deleteNode ()
{
    for (Node * temp = head; temp! = NULL; temp = temp-> next)
        delete head;
}

Это необходимо так:

for (; head != NULL; )
{
    Node *temp = head;
    head = temp->next;

    delete temp;
}

Ответ 11

Вот моя реализация.

#include <iostream>

using namespace std;

template< class T>
struct node{
    T m_data;
    node* m_next_node;

    node(T t_data, node* t_node) :
        m_data(t_data), m_next_node(t_node){}

    ~node(){
        std::cout << "Address :" << this << " Destroyed" << std::endl;
    }
};

template<class T>
class linked_list {
public:
    node<T>* m_list;

    linked_list(): m_list(nullptr){}

    void add_node(T t_data) {
        node<T>* _new_node = new node<T>(t_data, nullptr);
        _new_node->m_next_node = m_list;
        m_list = _new_node;
    }


    void populate_nodes(node<T>* t_node) {
        if  (t_node != nullptr) {
            std::cout << "Data =" << t_node->m_data
                      << ", Address =" << t_node->m_next_node
                      << std::endl;
            populate_nodes(t_node->m_next_node);
        }
    }

    void delete_nodes(node<T>* t_node) {
        if (t_node != nullptr) {
            delete_nodes(t_node->m_next_node);
        }
        delete(t_node);
    }

};


int main()
{
    linked_list<float>* _ll = new linked_list<float>();

    _ll->add_node(1.3);
    _ll->add_node(5.5);
    _ll->add_node(10.1);
    _ll->add_node(123);
    _ll->add_node(4.5);
    _ll->add_node(23.6);
    _ll->add_node(2);

    _ll->populate_nodes(_ll->m_list);

    _ll->delete_nodes(_ll->m_list);

    delete(_ll);

    return 0;
}

Ответ 12

#pragma once
#include "SKBStringList.h"

SKBStringList::SKBStringList()
{ 
    _Head = NULL;
    _Tail = NULL;
}

SKBStringList::~SKBStringList()
{
    _Head = NULL;
    _Tail = NULL;
}

void SKBStringList::Append(const char* iData)
{
    SKBStringData *pNewData = new SKBStringData(iData);

    if(_Head == NULL)
    {
        _Head = pNewData;
        _Tail = pNewData;
    }
    else
    {
        _Tail->SetLink(pNewData);
        _Tail = pNewData;
    }

    return;
}

void SKBStringList::Remove(const int iPos)  
{
    if(iPos < 0 || _Head == NULL)             // empty list
    {
        return ;
    }

    SKBStringData* pCurrData = _Head;
    for(int i =0; i < iPos-1; i++)
    {
        pCurrData = pCurrData->GetLink();
    }
    pCurrData->SetLink(pCurrData->GetLink()->GetLink());
    delete pCurrData;
    return;
}

void SKBStringList:: Find(const char* iData,int &oPos)
{
    if(_Head == NULL || iData == NULL)
    {
        return;
    }

    int nStatus = -1;
    int nCount  = 0;
    SKBStringData* pCurrData = _Head;
    while(pCurrData->GetData() != NULL)
    {
        if(pCurrData->GetData() == iData)
        {
            nStatus = 0;
            break;
        }
        else
        {
            nCount++;
            pCurrData = pCurrData->GetLink();
        }
    }


    if(nStatus == 0)
    {
        oPos = nCount; 
    }
    else
    {
        oPos = -1;
    }

    return ;
}