13

1 つのパラメーター (ListNode へのポインター) を持つ、copyList という名前の補助関数を実装する必要があります。この関数は、元の連結リストのコピーの最初のノードへのポインターを返す必要があります。つまり、リンク リストのヘッダー ノードを取得し、そのリンク リスト全体をコピーして、新しいヘッダー ノードへのポインターを返す関数を C++ でコーディングする必要があります。私はこの機能を実装するのに助けが必要です.これは私が今持っているものです.

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;  //holds the current node

    Listnode *copy = new Listnode;
    copy->next = NULL;

    //traverses the list
    while (current != NULL) {
       *(copy->student) = *(current->student);
       *(copy->next) = *(current->next);

        copy = copy->next;
        current = current->next;
    }
    return copy;
}

また、これは私が取り組んでいる Listnode 構造です。

struct Listnode {    
  Student *student;
  Listnode *next;
};

注: この関数で遭遇するもう 1 つの要因は、ローカル変数へのポインターを返すという考えです。

4

7 に答える 7

5

自問する必要がある最初の質問は、コピー セマンティクスとは何かということです。特に、Student*ノードの内容として a を使用しています。ノードの内容をコピーするとはどういう意味ですか? 2 つのリストが同じ学生インスタンスを指す (共有する) ようにポインターをコピーする必要がありますか、それともディープ コピーを実行する必要がありますか?

struct Listnode {    
  Student *student; // a pointer?  shouldn't this be a `Student` object?
  Listnode *next;
};

次の質問は、2 番目のリストのノードをどのように割り当てるかです。現在、コピーには 1 つのノードのみを割り当てます。

コードは次のようになるはずです。

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;

    // Assume the list contains at least 1 student.
    Listnode *copy = new Listnode;
    copy->student = new Student(*current->student);
    copy->next = NULL;

    // Keep track of first element of the copy.
    Listnode *const head = copy;

    // 1st element already copied.
    current = current->next;

    while (current != NULL) {
       // Allocate the next node and advance `copy` to the element being copied.
       copy = copy->next = new Listnode;

       // Copy the node contents; don't share references to students.
       copy->student = new Student(*current->student);

       // No next element (yet).
       copy->next = NULL;

       // Advance 'current' to the next element
       current = current->next;
    }

    // Return pointer to first (not last) element.
    return head;
}

2 つのリスト間で生徒のインスタンスを共有したい場合は、次を使用できます。

copy->student = current->student;

それ以外の

copy->student = new Student(*current->student);
于 2012-04-10T03:11:08.143 に答える
2

自分で大部分の作業を行ったので、これは優れた質問です。ほとんどの「宿題をしてください」という質問よりもはるかに優れています。

いくつかのポイント。

まず、空のリストを渡すとどうなるでしょうか? おそらく、前もってそれをキャッチし、呼び出し元に空のリストを返すだけです。

次に、コピー リストの最初のノードのみを割り当てます。元のリストのノードごとに 1 つ行う必要があります。

次のようなもの (宿題用の疑似コード (ただし C++ に似ています)、申し訳ありません):

# Detect empty list early.

if current == NULL:
    return NULL;

# Do first node as special case, maintain pointer to last element
# for appending, and start with second original node.

copy = new node()
last = copy

copy->payload = current->payload
current = current->next

# While more nodes to copy.

while current != NULL:
    # Create a new node, tracking last.

    last->next = new node()
    last = last->next

    # Transfer payload and advance pointer in original list.

    last->payload = current->payload
    current = current->next

# Need to terminate new list and return address of its first node

last->next = NULL
return copy

そして、ローカル スタック変数へのポインターを返すべきではないというあなたの意見は正しいですが、それはあなたがしていることではありません。返される変数は、関数の終了後も存続するヒープ割り当てメモリを指します。

于 2012-04-10T03:08:15.673 に答える
1

私は同じことをしようとしてきました。私の要件は次のとおり

です。 1. 各ノードは非常に基本的で単純なクラスです (構造体モデルから離れました)。
2. 古いリンク リストへのポインタだけでなく、ディープ コピーを作成したい。

これを行うために私が選んだ方法は、次の C++ コードを使用することです。

template <class T>
Node <T> * copy(Node <T> * rhs)
{
    Node <T> * current = new Node<T>();
    Node <T> * pHead = current;
    for (Node <T> * p = rhs; p; p = p->pNext)
    {
        Node <T> * prev = current;
        prev->data = p->data;
        if (p->pNext != NULL)
        {
            Node <T> * next = new Node<T>();
            prev->pNext = next;
            current = next;
        }
        else
        {
            prev->pNext = NULL;
        }
    }
    return pHead;
}

これはうまく機能し、エラーは発生しません。「頭」は特殊なケースであるため、「現在の」ポインターの実装が必要です。

于 2015-02-11T19:02:05.000 に答える
0

声明 copy->next = current->next は間違っています。やったほうがいい

Create the first node copy here
copy->student = current->student;
copy->next = NULL;
while(current->next!=NULL)
{
    Create new node TEMP here
    copy->next = TEMP;
    TEMP->student = current->student;
    TEMP->next = NULL;
    copy = TEMP;
}
于 2012-04-10T03:07:48.413 に答える
0

リンクされたリストのコピーが必要なので、元のリストをトラバースしながら、ループ内に新しいノードを作成する必要があります。 

Listnode *startCopyNode = copy;

while (current != NULL) {
   *(copy->student) = *(current->student);
    copy->next = new Listnode;
    copy = copy->next;
    current = current->next;
}

copy->next = NULL;
return startCopyNode;

deleteリンクされたリストのノードに注意してください。

于 2012-04-10T03:07:53.653 に答える
0

@pat、メモリを1回しか作成しないため、seg_faultが発生すると思います。ノードごとにメモリを作成する（基本的に「new」と呼ぶ）必要があります。すべてのノードのメモリを作成するために「new」キーワードを使用する必要がある場所を見つけます。

これが完了したら、それを前のノードにリンクする必要があります。これは単独でリンクされたリストであるため、前のノードへのポインターを維持する必要があります。あなたが学びたいと思っていて、すべての人生を覚えていなければならない場合は、上記のコードを見ないでください. 上記の要因を考えて、独自のコードを考えてみてください。

于 2012-04-10T03:10:07.363 に答える
0

他の人が指摘したように、元のリストの各newノードを呼び出してコピー用のスペースを割り当て、古いノードを新しいノードにコピーし、コピーされたノードのポインターを更新する必要があります。

この関数で私が直面しているもう 1 つの要因は、ローカル変数へのポインターを返すという考えです。

ローカル変数へのポインターを返していません。を呼び出すと、ヒープにメモリが割り当てられ、それへのポインタが返されます (もちろん、関数の外部から、新しいリストを使い終わったら、それを解放するnewために呼び出すことを覚えておく必要があることを意味します)。delete

于 2012-04-10T03:15:11.327 に答える