c++ - 連結リストの作り方

Question

そのため、リンクされたリストを C++ でプログラミングしようとしていますが、正確に行う方法がわかりません。私は概念を多かれ少なかれ理解しており、このコードを提供するチュートリアルを見ましたが、あまりよく説明されていませんでした。皆さんが次のステップで私を助けてくれませんか、私が今何をしたか、そしてどのように続けるかを説明してくれませんか. 要素を追加し、要素を積み重ねてポップまたはプッシュし、最後に先入れ先出しし、最後に要素を解放してメモリを解放して、メモリ リークを防止したいと考えています。ありがとうございました。

    #include <iostream>
using namespace std;

struct node
{
    int num;
    node *link;
}*p;

void main()
{
    node *root;

    root = new node;
    root->num=5;
    root->link = p;
    p = root;

    node *q;

    for(q = p; q != NULL; q = q->link)
    {
        cout<<q->num;
        cout<<endl;
    }
}

Answer 1

簡単な連結リストのデモ

#include <iostream>
using namespace std;

typedef struct NODE
{
    int value;
    NODE *next;
};



int main()
{
    int opt;
    NODE *root = NULL;
    NODE *tmp = NULL;
    NODE *last = NULL;
    do
    {
        cout << "Simple Singly Linked-List Example\n\n";
        cout << "\t1. Create Root\n";
        cout << "\t2. Add Node\n";
        cout << "\t3. Delete First Node\n";
        cout << "\t4. Display Last Node\n";
        cout << "\t5. Display Nodes\n";
        cout << "\t6. Exit Program.\n\n";

        cout << "Enter a choice : ";
        cin >> opt;

        switch (opt)
        {

            case 1: // create root;
                if (root != NULL) // root already exists no need to ceate one
                {
                    cout << "Root already exists\n\n";
                    break;
                }

                root = new NODE;
                cout << "Enter Value for new Node : ";
                cin >> root->value;
                root->next = NULL;

                // root & last will be same for the when the node count is ONE
                last = root;
                cout << "\nRoot node has been created successfully\nPress any key to continue...\n\n";
                cin.get();

                break;

            case 2:
                if (root == NULL)
                {
                    cout << "Create root node first\n\n";
                    break;
                }

                tmp = new NODE;
                cout << "Enter Value for new Node : ";
                cin >> tmp->value;
                tmp->next = NULL;
                // attach it to the last node
                last->next = tmp;


                //set newly created node as last node
                last = tmp;
                cout << "\nRoot node has been created successfully\nPress any key to continue...\n\n";
                cin.get();
                break;

            case 3:
                if (root == NULL)
                {
                    cout << "No nodes to delete\n\n";
                    break;
                }

                // we have to delete the root node and set the next node as root
                tmp = root->next;
                cout << "Deleted the node with value : " << root->value << "\nPress any key to continue...\n\n";
                delete root;
                cin.get();

                //set second node as root now
                root = tmp;
                break;

            case 4:
                if (root == NULL)
                {
                    cout << "No nodes to delete\n\n";
                    break;
                }

                // delete the very last node (easy) and update the next pointer of second last node to null (tricky)

                //first lets find the second last node
                tmp = root;
                while(tmp->next != NULL)
                {
                    tmp = tmp->next;
                }
                //update the second last node next pointer to null
                cout << "Deleted the node with value : " << last->value << "\nPress any key to continue...\n\n";
                cin.get();
                delete last;

                //update second last one as last node
                last = tmp;
                last->next = NULL;

                break;
            case 5:
                if (root == NULL)
                {
                    cout << "No nodes to disply\n\n";
                    break;
                }

                tmp = root;
                cout << "Node Values  : ";
                while(tmp)
                {
                    cout << tmp->value << ",\t";
                    // set to print next node
                    if (tmp->next)
                        tmp = tmp-next;
                    else
                        break;

                }
                cout << "\nPress any key to continue\n\n";
                cin.get();
                break;

            default:
                cout << "Invalid Option\n\nPress any key to continue...\n\n";
                cin.get();

        }
    }while(opt != 6);

    // always a good practise to delete objects u have created;
    tmp = root;
    while(tmp)
    {
        //sorry for using the last node pointer, dont seems subtle
        last = tmp;
        tmp = tmp->next;
        cout << "Deleted Node with value : " << last->value << "\n";
        delete last;
    }

    return 0;
}

---

リンクリストに関するいくつかのリンクを確認してください

リンク＃1

リンク＃2

リンク # 3 <- とても便利です。今でもブックマークに入れています

リンク # 4 <-- 単独 - リンクされたリスト、すべての基本!

Answer 2

まず、標準ライブラリ ( #include <iostream>) を既に使用しているため、標準ライブラリには既にリスト: ( #include <list>) と他のコンテナーが含まれていることに注意してください。

ここでドキュメントを見つけることができます

自分で書きたい場合は、適切なアプローチを使用してください。すべてをメインに配置するのではなく、適切なクラスとメソッドを定義して要素を操作します。「インスピレーション」としてリンクした標準ドキュメントを参照できます。

あなたはおそらく次のようなもので終わるでしょう

class list
{
    struct element
    {
        element* pnext;
        int value;
    };

    element* root;

public:

    list() :root() 
    {}

    ~list() 
    { while(root) pop(); }

    list(const list&) =delete;

    list& operator=(const list&) =delete;

    void push(int val) 
    { 
        element* p = new element;
        p->value = val;
        p->pnext = root;
        root = p;
    }

    void pop()
    {
        element* pe = root;
        root = pe->pnext;
        delete pe;
    }

    class index
    {
        element* p;
        index(element* s) :p(s) {}
        friend class list;
    };

    index start() const const 
    { return index(root); }

    index next(index i) const 
    { return index(i.p->pnext); }

    int at(index i) const 
    { return i.p->value; }

    bool is_end(index i) const 
    { return i.p == nullptr; }
};