1

リンクリストを表現する方法を私が知っている方法は、基本的にNodeクラス（より好ましくはstruct）を作成し、実際のlinkedListクラスを作成することです。しかし、昨日、私は単一リンクリスト操作を逆にするロジックを探していました。私が遭遇したソリューションのほぼ90％は、データ型Node*を返す関数を含むものでした。したがって、どのような操作を行ってもリストを逆にしたい場合は、再びlinkedListのタイプになりませんか？私はそれを間違った方法でやっていますか？

私がいつも行っているリンクリストの実装。

#include <iostream>
using namespace std;

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

class linkedList
{
public:
    Node* firstPtr;
    Node* lastPtr;

    linkedList()
    {
        firstPtr=lastPtr=NULL;
    }
    void insert(int value)
    {
        Node* newNode=new Node;
        newNode->data=value;
        if(firstPtr==NULL)
            firstPtr=lastPtr=newNode;
        else {
            newNode->next=firstPtr;
            firstPtr=newNode;
        }
    }
    void print()
    {
        Node *temp=firstPtr;
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
    }
};
4

3 に答える 3

4

linkedListあなたのアプローチは間違っていませんが、クラスに重点を置きすぎている可能性があります。

そのクラスには実際に何が含まれていますか？最初のノードへのポインターと、最後のノードへのポインター (最初のノードを知るだけで最後のノードを見つけることができるため、これは冗長な情報です)。したがって、基本的にlinkedListは、追加情報を持たない単なるヘルパー クラスです。

のメンバー関数linkedListは、簡単に内部に移動したり、 as パラメーターNodeを取るフリー関数を作成したりできます。Node

于 2012-04-23T08:50:02.817 に答える
2

では、連結リストとは、最初のノードへのポインターではなく、何ですか? 最初のノードに到達できれば、リストは完全にアクセス可能であり、そのために必要なのは最初のノードへのポインタだけです。

リストに関する追加の制御情報 (たとえば、長さなど)を保存する必要がない限り、リスト自体に別のデータ型を使用する必要はありません。

現在、一部の実装 (あなたのものなど) は、効率のためにリストの最後のノードへのポインターを格納することもでき、O(n) の代わりに O(1) にアイテムを追加できます。しかし、これはリストの追加機能であり、一般的なリストの要件ではありません。

于 2012-04-23T08:49:12.443 に答える
0

これらの関数は、リンクされたリストを逆にした後、リストの最初のノードへのポインターを返すため、タイプ Node* を返す可能性があります。

于 2012-04-23T08:52:12.953 に答える