0

SinglyLinkedListを実装しようとしました。addAtLast（）関数が正しく実行されていません。この関数の実行中にプログラムがクラッシュします。いくつかの変更を提案してください。

class LList
{
public:
    int noOfNodes;
    Node const *start;/*Header Node*/

    LList()
    {
        start=new Node;
        noOfNodes=0;start=0;
    }

    void addAtFront(Node* n)
    {
        /*
        cout<<endl<<"class"<<n;
        cout<<"start"<<start;
        cout<<"data in node";n->print();
        */
        n->next=const_cast<Node*>(start);
        start=n;
        // cout<<" next=";start->print();
        noOfNodes++;
    }

    void addAtLast(Node* n)
    {
        Node *cur=const_cast<Node*>(start);
        if (start==NULL)
        { 
            start=n;
            return;
        }
        while(cur->next!=NULL)
        {
            cur=cur->next;
        }
        cur->next=n;
        noOfNodes++;
    }

    int getPosition(Node data)
    {
        int pos=0;
        Node *cur=const_cast<Node*>(start);
        while(cur!=NULL)
        {
            pos++;
            if(*cur==data)
            {
                return pos;
            }
            cur=cur->next;
        }
        return -1;//not found
    }

    Node getNode(int pos)
    {
        if(pos<1)
            return -1;// not a valid position
        else if(pos>noOfNodes)
            return -1; // not a valid position

        Node *cur=const_cast<Node*>(start);
        int curPos=0;
        while(cur!=NULL)
        {
            if(++curPos==pos)
                return *cur;
            cur=cur->next;
        }
    }

    void traverse()
    {
        Node *cur=const_cast<Node*>(start);
        while(cur!=NULL)
        {
            //   cout<<"start"<<start;        
            cur->print();
            cur=cur->next;
        }
    }  

    ~LList()
    {
        delete start;
    }
};
4

4 に答える 4

2 
void addAtLast(Node* n) {
    Node *cur=const_cast<Node*>(start);
    if(start==NULL) {
        start=n;
        n->next = NULL;
        noOfNodes++;
        return;
    }
    while(cur->next!=NULL) {
        cur=cur->next;
    }
    cur->next=n;
    n->next = NULL;  // Added
    noOfNodes++;
}
于 2012-11-12T08:32:09.387 に答える
1

最初から..

start=new Node;
noOfNodes=0;start=0;

これはすべきですか？

start=new Node;
noOfNodes=0;start->next=NULL;

2行以内に、メモリリークが発生しました。なぜ設定したいのかわかりませんstart=0。そうしないでください、あなたはそれにメモリを割り当てただけです！

クラッシュに関しては、@liulinhuaiの回答で対処されています。メンバーを取得しようとして、初期化されていないポインターを間接参照しますnext。

于 2012-11-12T08:28:58.940 に答える
1

コンストラクターでは、startを0に設定します。クラッシュ関数では、最初に次のことを確認しますNULL。

if (start==NULL)
{ 
   start=n;
   //n->next is now points to nowhere
   return;
}

addAtLastが見つかるまで反復する次の呼び出しNULLですが、前の割り当てではnextポインタが設定されてNULLいないため、2回目の反復では：が発生しaccess violationます。

while(cur->next!=NULL) {
   //first time it's ok but second call on cur will crash
   cur=cur->next;
}

解決策は-すべての新しいのはポインタをに設定するNode必要がありますnextNULL

于 2012-11-12T08:36:12.057 に答える
1

私はこのコメントに言及しましたが、ここで答えとして取り上げます。この関数の呼び出し元は、次の2つのことを確認する必要があります。

  1. 渡されたノードリスト（および、要素の長さが1つしかない場合でもリスト）は、end-next-pointerをNULLに設定して適切に終了する必要があります。このコードはそれを想定して盲目的に設定することができないため、呼び出し元はこれを確認する必要がありますnode->next = NULL;

  2. これが実行されると、このリストが渡されたノードとそれが開始する可能性のあるリストを所有していることを呼び出し元が認識していることを絶対に確認してください。したがって、呼び出し元は、呼び出し元側でそれまたはそれが指すものを解放してはなりません。

ノード数管理の問題を除けば、関数には何の問題もありませんがaddAtLast()、少し異なる方法で実装します。

void addAtLast(Node* n)
{
    // no nulls allowed
    if (n == NULL)
        return;

    // set start if first in list
    if (start == NULL)
    {
        start = n;
        noOfNodes = 1;
    }

    // else walk list to find end
    else
    {
        Node *cur = const_cast<Node*>(start);
        while(cur->next != NULL)
            cur = cur->next;
        cur->next = n;
        ++noOfNodes;
    }

    // adjust count to contain any nodes from 'n'
    while (n->next != NULL)
    {
        ++noOfnodes;
        n = n->next;
    }
}
于 2012-11-12T08:54:50.840 に答える