c++ - C++ポインタ/リストの実装

Question

次のプロパティを持つクラスListNodeを記述します。

int値;

ListNode * next;

次の機能を提供します。

ListNode（int v、ListNode * l）

int getValue（）;

ListNode * getNext（）;

void insert（int i）;

bool listcontains（int j）;

ユーザーにいくつかの整数を入力してそれらをListNodesとして格納するように要求し、次にリストで検索する必要のある数値を要求するプログラムを作成します。

これが私のコードです：

#include <iostream>
using namespace std;

class ListNode
{
    private:
        struct Node
        {
            int value;
            Node *next;
        } *lnFirst;

    public:
        ListNode();
        int Length();       
        void DisplayList();     
        void Insert( int num );
        bool Contains( int num );       
        int GetValue( int num );        
};

ListNode::ListNode()
{
    lnFirst = NULL;
}

int ListNode::Length()
{
    Node *lnTemp;
    int intCount = 0;
    for( lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
    {
        intCount++;
    }
    return intCount;
}

void ListNode::DisplayList()
{
    Node *lnTemp;
    for( lnTemp = lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
        cout<<endl<<lnTemp->value;
}

void ListNode::Insert(int num)
{
    Node *lnCurrent, *lnNew;

    if( lnFirst == NULL )
    {
        lnFirst = new Node;
        lnFirst->value = num;
        lnFirst->next = NULL;
    }
    else
    {
        lnCurrent = lnFirst;
        while( lnCurrent->next != NULL )
            lnCurrent = lnCurrent->next;

        lnNew = new Node;
        lnNew->value = num;
        lnNew->next = NULL;
        lnCurrent->next = lnNew;
    }
}

bool ListNode::Contains(int num)
{
    bool boolDoesContain = false;
    Node *lnTemp,*lnCurrent;
    lnCurrent = lnFirst;
    lnTemp = lnCurrent;
    while( lnCurrent!=NULL )
    {
        if( lnCurrent->value == num )
        {
            boolDoesContain = true;
            return boolDoesContain;
        }
        lnTemp = lnCurrent;
        lnCurrent = lnCurrent->next;
    }
    return boolDoesContain;
}

int ListNode::GetValue(int num)
{
    Node *lnTemp;
    int intCount = 1;
    for( lnTemp=lnFirst; lnTemp != NULL; lnTemp = lnTemp->next )
    {
        if (intCount == num)
        {
            return lnTemp->value;
        }
        intCount++;
    }    
}

int main()
{   
    cout << "Input integers below. Input the integer -1 to stop inputting.\n\n";
    
    ListNode lnList;
    int intNode = 1, intInput = 0;
    while (intInput != -1) {
        cout << "Please input integer number " << intNode << ": "; cin >> intInput;
        intNode++;
        if (intInput != -1) { lnList.Insert(intInput); }
    }   
    
    lnList.DisplayList();
    cout << "\n\n";
    
    int intListLength = lnList.Length();    
    cout << "Which value do you wish to recall? (Between 1 and " << intListLength << "): "; cin >> intNode;    
    if ( intNode >= 1 && intNode <= intListLength ) {
        cout << "Value at position " << intNode << " is " << lnList.GetValue(intNode) << ".";                
    } else {
        cout << "No such position in the list. Positions run from 1 to " << intListLength << ". You asked for " << intNode << ".";
    }
    
    cout << "\n\nCheck if the following value is in the list: "; cin >> intNode;
    bool IsThere = lnList.Contains(intNode);
    if (IsThere) {
        cout << intNode << " is in the list.";
    } else {
        cout << intNode << " is not in the list.";
    }
    
    cout << "\n\n";
    system("pause");
    return 0;  
}

これをどこで改善できますか？

score 3 · Accepted Answer

リクエストされたデザインを誤解されたと思います。ListNodeクラスは、ノードを含むリストではなく、ノードであると想定されています。

次のように、1つのリグに複数のコマンドを配置しないことをお勧めします。

cout << "Please input integer number " << intNode << ": "; cin >> intInput;

これは単に紛らわしいです。

score 3 · Accepted Answer

くつろぎとckarmannが言うこと。ここにヒントがあります。割り当ての意味を理解するために、listcontainsを実装します。

class ListNode {
private:
    int value;
    ListNode * next;

public:
    bool listcontains(int v) { 
        // does this node contain the value?
        if(value == v) return true; 

        // was this the last node?
        if(next == 0) return false;

        // return whether nodes after us contain the value 
        return next->listcontains(v);
    }
};

したがって、リストの先頭のみがあり、次のノードに順番にリンクします。尻尾はnext == 0;

score 3 · Accepted Answer

より一般的なスタイルノートでは、ポインターを定義する場所の近くでポインターを宣言し、スコープをできるだけ小さくします。
コードで技術的に問題が発生することはありませんが、常にこれを行うことで、私の経験では、はるかに大きな/古いコードベースのバグを回避できます。

たとえば、代わりに

Node *lnTemp;
int intCount = 0;
for( lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
{
}

書きます

int intCount = 0;
for(Node* lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
{
}

または同様に、代わりに

Node *lnTemp,*lnCurrent;
lnCurrent = lnFirst;
lnTemp = lnCurrent;

書きます

Node* lnCurrent = lnFirst;
Node* lnTemp = lnCurrent;

score 2 · Accepted Answer

リストノードのモデリングを過剰に設計していると思います。クラスListNodeは、その名前から明らかなリストノードです。その場合、リストの情報を保持するためにネストされた構造は必要ありません。これは非常に混乱します。

score 2 · Accepted Answer

この投稿の最後に詳細なフィードバックがありますが、まずはインラインコメントとコードの変更のみを示します。

struct Node // Why doesn't this have a constructor initializing the members?
{
        int value;
        Node *next;
} *lnFirst; 


ListNode::ListNode() : lnFirst(NULL) {} // Use initializer lists instead of initializing members in the ctor body. It's cleaner, more efficient and may avoid some nasty bugs (because otherwise the member gets default-initialized *first*, and then assigned to in the body)

int ListNode::Length()
{
    int intCount = 0;
    for( Node* lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next ) // Create the loop iteration variable lnTemp here, in the loop, not at the start of the function
    {
        intCount++;
    }
    return intCount;
}

void ListNode::DisplayList()
{
    for(Node* lnTemp = lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next ) // And again, initialize the loop variable in the loop
        cout<<endl<<lnTemp->value; // Not a huge deal, but endl flushes the stream as well as inserting a newline. That can be needlessly slow. So you might want to just use "\n" in cases where you don't need the flushing behavior.
}

void ListNode::Insert(int num)
{
//    Node *lnCurrent, *lnNew; // Very subjective, but I prefer not declaring multiple variables on the same line, because the syntax if they're pointers can be surprising (You got it right, but a lot of people would write Node* lnCurrent, lnView, which would make lnView not a pointer. I find it clearer to just give ecah variable a separate line:
    if( lnFirst == NULL )
    {
//        lnFirst = new Node;
//        lnFirst->value = num;
//        lnFirst->next = NULL;
        lnFirst = new Node(num); // Make a constructor which initializes next to NULL, and sets value = num. Just like you would in other languages. ;)
    }
    else
    {
        Node* lnCurrent = lnFirst; // Don't declare variables until you need them. Both to improve readability, and because C++ distinguishes between initialization and assignment, so in some cases, default-initialization followed by assigment may not be the same as just initializing with the desired value.
        while( lnCurrent->next != NULL )
                lnCurrent = lnCurrent->next;

        Node* lnNew = new Node(num); // Again, let a constructor do the work.
        lnCurrent->next = lnNew;
    }
}

bool ListNode::Contains(int num)
{
    bool boolDoesContain = false;
//    Node *lnTemp,*lnCurrent; // Again, don't initialize variables at the start of the function if they're not needed
    Node* lnCurrent = lnFirst;
//    lnTemp = lnCurrent;
    while( lnCurrent!=NULL )
    {
        if( lnCurrent->value == num )
        {
//                boolDoesContain = true;
//                return boolDoesContain;
                  return true; // Just return directly, and remove the boolDoesContain variable. Alternatively, set boolDoesContain to true, and then break out of the loop without returning, so you have a single exit point from the function. Both approaches have their merits, but setting a variable you don't need, and then returning is silly. ;)
        }
//        Node* lnTemp = lnCurrent; // you don't actually use lnTemp for anything, it seems
        lnCurrent = lnCurrent->next;
    }
//    return boolDoesContain;
      return false; // just return false. If you get this far, it must be because you haven't found a match, so boolDoesContain can only be false anyway.
}

int ListNode::GetValue(int num)
{
//    Node *lnTemp;
    int intCount = 1; // Wouldn't most people expect this indexing to be zero-based?
    for( Node* lnTemp=lnFirst; lnTemp != NULL; lnTemp = lnTemp->next )
    {
        if (intCount == num)
        {
            return lnTemp->value;
        }
        intCount++;
    }    
}

さて、一般的なコメントをいくつか。(割り当てを誤解しているかどうかは無視して、投稿したコードに焦点を当てます) まず、ハンガリー語表記: しないでください。「ln」プレフィックスなしで、最初にノードポインター、temp などを呼び出します。不必要な「bool」プレフィックスなしで bool 変数 doesContain を呼び出します。次に、編集したコードで試みたように、変数は必要な場合にのみ作成します。C では、ブロックの先頭で変数を宣言する必要がありましたが、C++ ではそうではありませんでした。第三に、メイン関数の最後に「0 を返す」必要はありません。Main は、関数の最後に到達すると自動的に 0 を返す特殊なケースです。

第 4 に、大きな厄介な問題があります: メモリ管理です。決して解放されないメモリを割り当てます。RemoveNode 関数がないので、これは論点のように思えるかもしれませんが、リスト全体が範囲外になり、削除されるとどうなるでしょうか? リストにあるのは一連のポインターだけであり、それらに対して削除を自動的に呼び出すわけではないため、そのノードは削除されません。したがって、少なくとも、リストクラス自体にデストラクタが必要です。これにより、リストが削除されたときに、そのすべての子ノードが確実に削除されます。

これは、リストを作成し、それにノードを追加し、リストを削除するという単純なデフォルトのケースを処理する必要があります。

次の大きな問題は、リストをコピーしたらどうなるか?

int main(){
ListNode list;
list.Insert(1);
list.Insert(2);
list.Insert(3);
}
ListNode list2 = list;

あなたのコードは爆発します。ノードのコピーを作成する代わりに、両方のリストが同じノードを指すようになりました。一方のリストにノードを追加すると、もう一方のリストにも表示されます。そして、「これは機能であり、バグではありません」と主張する前に ;)、リストの 1 つが削除された場合に何が起こるかを考えてください。

list2 が最初に削除されると仮定します。先ほど定義したデストラクタで、3 つのノードを削除して戻ります。リストは削除されたノードを指します。それらへのアクセスは未定義の動作であり、クラッシュする可能性が非常に高くなります。したがって、それらにアクセスしないとしましょう。代わりに、このリストもすばやく削除します。

おっと、それは、すでに削除された子ノードを削除しようとしていることを意味します。それは間違いなくクラッシュのように聞こえます。

したがって、これを修正するには、ListNode クラスに 2 つの追加関数、コピーコンストラクターと代入演算子を実装する必要があります。

ListNode(const ListNode& other);
ListNode& operator==(const ListNode& other);

これら 2 つは、すべてのデータが'other' からコピーされたときに確実にする必要があります。「その他」のすべてのノードについて、両方のリストが同じノードを指すようにするのではなく、現在のリストに新しいノードを割り当てる必要があります。(つまり、ノードクラスには、少なくともコピーコンストラクターも必要になる可能性が最も高いということです)。

これがメモリ管理を処理する基本的な方法であり、理解しておくことが重要です。そうしないと失敗するからです。;)

score 1 · Accepted Answer

課題の一部は次のとおりです。

次の機能を提供します。

ListNode（int v、ListNode * l）

int getValue（）;

ListNode * getNext（）;

void insert（int i）;

bool listcontains（int j）;

あなたはそれらの機能のどれも提供しませんでした。

他のいくつかがポインタを持っているので、ListNodeの代わりにListを実装しました。これが、関数のシグネチャが異なる理由です。

ただし、割り当てのコーディング規約に不注意に違反してはなりません。C＃のバックグラウンドはありますか？C ++のコーディング規約では、通常、小文字のメソッド名が義務付けられています。

score 0 · Accepted Answer

リストコードのもう1つの改善点は、長さを取得するためにリスト全体をトラバースするべきではありません。挿入/削除時に更新される要素の量についてカウンターを保持し、それを返すことができます。

c++ - C++ポインタ/リストの実装

7 に答える 7

Related

Reference