6

私はノード構造体を使用してリンクリストを自分自身に教えようとしており、誰かがこれを手伝ってくれることを望んでいました。コマンドラインから入力を取得すると、ネストされたリストが作成され、出力できます。

例：

入力： "1 2 3 4 5"
出力： "1 2 3 4 5"

私が問題を抱えていることが2つあります：1）プログラムを実行すると、警告が表示され続けます：'typedef'はこの宣言で無視されました[デフォルトで有効] これを取り除くにはどうすればよいですか？

編集：私はこれをに変更しましたtypedef struct Node* NodePtr;

2）コードが正しく機能していません。どうすればこれを修正できますか？私はC++でリンクリストを自分自身に教えようとしています。

typedef struct Node;
typedef Node* NodePtr;
struct Node{
    int x;
    NodePtr next;
};

int main ()
{
    int n;
    NodePtr head, ptr = NULL;
    head = ptr;
    while (cin >> n){
        ptr = new Node;
        ptr->x = n;
        ptr->next = NULL;
        ptr = ptr->next;
    }

    NodePtr bling = head;
    while(bling != NULL){
        cout << bling->x << endl;
        bling = bling->next;
    }
    return 0;
}

理想的には、次のようなリンクリストを作成したいと思います。

1 -> 2 -> 3 -> NULL.
4

4 に答える 4

9

まず、構造体の宣言と必要と思われるポインターtypedefに関して、これを行うにはいくつかの方法があります。以下はCまたはC++で動作します。

// declare NodePtr as a pointer to Node, currently an incomplete type
//  C and C++ both allow you to declare a pointer to damn-near anything
//  so long as there is an understanding of what it *will* be, in this
//  case, a structure called Node.
typedef struct Node *NodePtr;

// Now declare the structure type itself
struct Node
{
    int x;
    NodePtr next;
};

そうは言っても、私は正直にこれを行うことをお勧めしません。ほとんどのエンジニアは、「これはポインタです！」と叫ぶ、明確で構文が見える定義を望んでいます。あなたは違うかもしれません。私は、個人的にこれを単に好むでしょう：

struct Node
{
    int x;
    struct Node *next; // omit the 'struct' for C++-only usage
};

あなた、そして同様に重要な、あなたのコードを読んでいる他のエンジニアが、ノードへのポインタとしてのあなたの使用法を理解しているNodePtr限り、そしてあなたの状況で最もうまくいくものを選んでください。ポインタ型の宣言は一部の人にとっては宗教に近いので、それを覚えておいてください。それらのアスタリスクを見ることを好む人もいれば（私は1人です）、そうでない人もいます（あなたのように聞こえます= P）。

注：edポインター型を使用すると、潜在的なエラーを回避するのに役立つ場所が1つあります。それは、複数の変数宣言です。このことを考慮：typedef

Node* a, b;     // declares one Node* (a), and one Node (b)

これをtypedef struct Node *NodePtr;許可する：

NodePtr a, b;   // declares two Node*; both (a) and (b)

Cでコードを書くのに十分な時間を費やすと、前者が戻ってきて、間違いを犯さないように学ぶことができますが、それでもたまに発生する可能性があります。

ロードループ

リストをつなぎ合わせるためのロードループに関しては、リストを正しく接続していません。率直に言って、それを行う方法は無数にあります。そのうちの1つは以下の方法です。これには、「余分なノード」をクリーンアップする必要はありません。if (head){} else{}また、同じ条件を回避するためにブロック構造も必要ありません。私たちが実際にやろうとしていることを考えてみましょう。ノードを作成し、それらのアドレスを適切なポインターに割り当てます。

NodePtr head = NULL;     // always the head of the list.
NodePtr* ptr = &head;    // will always point to the next pointer to assign.
int n;
while (cin >> n)
{
    *ptr = new Node;
    (*ptr)->x = n;
    ptr = &(*ptr)->next;
}

// note this always terminates the load with a NULL tail.
(*ptr)->next = NULL;

使い方

  1. ヘッドポインタをNULLに初期化します
  2. ヘッドポインターを指すようにノードポインターポインター（はい、ポインターへのポインター）を初期化します。このポインタ間ポインタは、次の動的に割り当てられたノードのアドレスを受け取るターゲットポインタのアドレスを常に保持します。最初は、それがヘッドポインタになります。上記のコードでは、このポインターからポインターは変数です：ptr。
  3. whileループを開始します。ptr読み取られた値ごとに、新しいノードを割り当て、それを（したがって）が指すポインターに保存します*ptr。最初の反復では、これはheadポインターのアドレスを保持するため、head変数は新しいノード割り当てを取得します。以降のすべての反復では、最後に挿入されたノードnextのポインターのアドレスが含まれます。ちなみに、この新しいターゲットポインタのアドレスを保存することは、次の割り当てサイクルに移る前にループで行われる最後のことです。
  4. ループが完了すると、最後に挿入されたノードのnextポインターをNULLに設定して、リンクリストが適切に終了するようにする必要があります。これは必須です。そのポインタへのポインタ（これまでずっと使用してきたものと同じもの）があると便利なので、「指す」ポインタをNULLに設定します。リストが終了し、ロードが完了しました。Brain Food：ロードループがノードをロードしなかった場合、どのポインターを指しますか？回答：&head、これはNULL、リストが空の場合に必要なもの（ヘッドポインタ）です。

設計

これが、ループの3回の完全な反復を通じてどのように機能するかをよりよく説明するのに役立つことを願っています。

初期構成

      head ===> NULL;
ptr --^

1回の反復後：

head ===> node(1)
          next
ptr ------^

2回の反復後

head ===> node(1)
          next ===> node(2)
                    next
ptr ----------------^

3回の反復後

head ===> node(1)
          next ===> node(2)
                    next ===> node(3)
                              next
ptr --------------------------^

3回の反復で停止した場合、最終的な終了割り当て（*ptr = NULL;）は次のようになります。

head ===> node(1)
          next ===> node(2)
                    next ===> node(3)
                              next ===> NULL;
ptr --------------------------^

最初の反復が終了すると、変更されないことに注意してくださいhead（常に最初のノードを指します）。またptr、入力される次のポインターのアドレスを常に保持していることにも注意してください。これは、最初の反復後（ヘッドポインターのアドレスとして開始された場合）、常に最後に追加されたノードのnextポインターのアドレスになります。

それがあなたにいくつかのアイデアを与えることを願っています。headこれらの2つのポインター（ポインターとptrポインター）を独自の構造にペアリングし、適切な管理機能を使用すると、教科書のキューが定義されることに注意してください。ここで、一方の端は挿入専用（ptr）で、もう一方の端は抽出用（head）であり、コンテナーはランダムアクセスを許可しません。のような標準ライブラリコンテナアダプタでは、最近そのようなことはあまり必要ありませんがstd::queue<>、ポインタからポインタへの概念をうまく利用するための興味深い冒険を提供します。

完全な作業サンプル

このサンプルでは、​​キューに20個の要素をロードして印刷し、キューをクリーンアップして終了します。必要に応じて使用法に適応します（ヒント：受信データのソースを変更するなど）

#include <iostream>
using namespace std;

// declare NodePtr as a pointer to Node, currently an incomplete type
//  C and C++ both allow you to declare a pointer to damn-near anything
//  so long as there is an understanding of what it *will* be, in this
//  case, a structure called Node.
typedef struct Node *NodePtr;

// Now declare the structure type itself
struct Node
{
    int x;
    NodePtr next;
};

int main()
{
    // load our list with 20 elements
    NodePtr head = NULL;
    NodePtr* ptr = &head;
    for (int n=1;n<=20;++n)
    {
        *ptr = new Node;
        (*ptr)->x = n;
        ptr = &(*ptr)->next;
    }

    // terminate the list.
    *ptr = NULL;

    // walk the list, printing each element
    NodePtr p = head;
    while (p)
    {
        cout << p->x << ' ';
        p = p->next;
    }
    cout << endl;

    // free the list
    while (head)
    {
        NodePtr victim = head;
        head = head->next;
        delete victim;
    }

    return 0;
}

出力

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
于 2013-01-27T05:31:27.403 に答える
3

実際には、'head'変数をNULL（head = ptr）を超えて設定することはありません。あなたは実際に最初からあなたのリストを失います。これを試して：

int n;
NodePtr head, ptr;
ptr = new Node;
head = ptr;
while (cin >> n){
    ptr->x = n;
    ptr->next = new Node;
    ptr = ptr->next;
}

次に、最後のptr-> nextを削除して0に設定すると、メモリを節約し、余分な値が出力されないようにすることができます。

于 2013-01-27T04:58:20.327 に答える
1

リストを接続していません。すべての新しいアイテムは->nextNULLになります。

あなたはptr = ptr->next（これはNULLです）と言いますが、次の反復はptrを新しく割り当てられたノードで上書きします。ノードをつなぎ合わせるには、コードを再配置する必要があります...

これを行う1つの方法はptr->next = head、新しいノードが古いヘッドを指すようにすることです。次にhead = ptr、ヘッドを新しいノードに移動します。例えば：

最初に挿入するには（たとえば、LIFOの場合、後入れ先出し）：

while (cin >> n){
    ptr = new Node;
    ptr->x = n;
    ptr->next = head;
    head = ptr;
}

最後に挿入するには（FIFOの場合）：

while (cin >> n){
    if(!head) {
        head = new Node;
        ptr = head;
    }
    else
    {
        ptr->next = new Node;
        ptr = ptr->next;
    }
    ptr->next = NULL;
    ptr->x = n;
}
于 2013-01-27T04:56:48.223 に答える
1

まず、typedef：typedef struct Node;が正しくありません。構文を使用して構造体を宣言します。

struct st_Name{
    int field1;
    double field2;
};

Typedefは名前属性関数のようなものです。（読みやすく/作業しやすくするために）構造体の名前を変更する必要があります。これは、宣言した後、次のようにして可能です。

typedef struct Node_st Node;

または、すべてを1つのステートメントにまとめます。

typedef struct node_st{
  int x;
  struct node_st *next;
}Node;

NodePtr上記のセグメントでは、次の理由でに変更したことに注意してstruct node_st *Nextください。すべてを1つのセグメントで行う場合、c++コードは線形に上から下に読み取られるため（ちょっと）、構造体宣言の前にNodePtrポインタを作成しようとするとエラーが発生します。Node後でそれを実行して構造体内で使用するとNodePtr、エラーも発生します。コンパイラは構造体が存在することをまだ知らないので、存在しないものに名前を付けようとしていると表示されます。

次に、ポインタの操作が間違っています。

...
while (cin >> n){
    ptr = new Node;
    ptr->x = n;
    ptr->next = NULL;  // You're making the next slot inexistent/NULL
    ptr = ptr->next;   // You're just setting ptr to NULL
}
...

私があなたが望んでいると思うのは、最後に頭を最初の数字に保ち続けることです。これは、最初のケースのif/elseステートメントを使用して簡単に行うことができます。

 while (cin >> n){
     if(head == NULL){
        ptr = new Node;
        ptr->x = n;
        ptr->next = NULL;
        head = ptr;
     }else{ 
        ptr->next = new Node;
        ptr = ptr->next;
        ptr->x = n;
        ptr->next = NULL; 
     }
}

このように、挿入は最後に行われるため、印刷ループが機能するはずです。

お役に立てれば。

于 2013-01-27T05:20:57.317 に答える