1

そのため、私はまだ C の連結リストに頭を悩ませようとしています。ポインタへのポインタはもちろん、連結リストが必要とする動的メモリ割り当てはもちろん、ポインタについても完全に理解していないため、今は気が遠くなるようなものです。 .

独立した高さと幅の値を持つ 2 次元配列を作成しようとしています。せいぜい 30x30 です。私は 2 次元配列を持っており、それを arr[x][y] と呼びましょう。arr[x][y] は -2 から 1 までの範囲の整数値で満たされています。この 2 次元配列を連結リストに転送するにはどうすればよいですか? 気まぐれにこのリンクされたリストから値にアクセスするにはどうすればよいですか? 私は非常に混乱しています。私たちが話している間、私はチュートリアルを見ています。

さらに、これは、push (新しい値をリンク リストの一番上にプッシュする)、pop (リンク リストの一番上から値をポップする)、top(スタックに最後にプッシュされた値を返します)、isEmpty (スタックが空かどうかを確認します)。

完全なコードは必要ありませんが、ここではコードが役に立ちます。リンクリストと、これらの種類の機能を実装する方法を理解する必要があります。

さらに、これが関連する割り当ては次のとおりです。

これは迷路ソルバーです。アスキー画像を 2 次元配列の整数値に分析するためのコードを既に作成しました。そして、上で述べたように、それは私が助けを必要としているものです。

4

4 に答える 4

3

ヒント: あなたの割り当てから、スタックは配列を完全に表すことは想定されていませんが、迷路の開始位置から迷路の目標位置までの道を見つけるために動的に構築するパスを表すことになっています。

于 2012-11-05T20:19:06.057 に答える
2

基本的に、各ノードがメンバーとして含まれる別のリストの先頭であるリンク リストを作成する必要があります (概念的には下方向に成長します)。リスト内の通常の次のポインターと共に。

arr[3][4] などの 2D 配列のような要素にアクセスするには、y のカウントを維持しながら最初のリストをたどる必要があり、次に x をカウントして下に移動するか、その逆を行うことができます。

これは、「マルチスタックまたはマルチキュー」という名前で呼ばれる一般的なデータ構造の割り当てであり、リストで実装すると、探しているものが得られます。

struct Node
{
    int data;
    struct Node *next;
    struct Node *head; // This head can be null initially as well as for the last node in a direction
};
于 2012-11-05T20:17:42.183 に答える
1

まず、適切な構造を定義する必要があります。最初は、次のノードへのポインタがNULLのときに終了するリストを作成する方が簡単です。その後、番兵、双方向リストなどのリストを見つけることができます。複雑すぎるように見えるかもしれません。
たとえば、それは構造です:

typedef struct __node
{
    int info;
    struct __node* next;
}node;

typedef node* list;

今回は、リストとノードが同じものであると仮定します。ノードの概念よりもリストの概念をより正確に分離できます。たとえば、リストにその長さを格納できます(すべてのノードを毎回カウントすることを回避します)。 、しかし今のところはそのようにしましょう。
リストを初期化します。

list l=NULL;

したがって、リストにはゼロノードが含まれています。空かどうかをテストするには、ポインタがNULLかどうかを確認します。
新しい要素を追加します。

if(NULL==l)
{
    l=(node*)malloc(sizeof(node));
    l->next=NULL;
    l->info=0;
}

これでリストにゼロノードが含まれるようになりました。新しいノードを追加する関数を作成します。

void pushBack(list* listPointer, int info)
{
    if(NULL==*listPointer)
    {
        *listPointer=(node*)malloc(sizeof(node));
        (*listPointer)->info=info;
    }
    else
    {
        node* ptr=l;
        while(ptr->next!=NULL)
            ptr=ptr->next;
        ptr->next=(node*)malloc(sizeof(node));
        ptr->info=info;
    }
}

前に要素を追加することで効率を上げることもできます。または、追加した要素を返すことでコードを最適化して、毎回最後の要素を見つける必要がないようにします。これはあなたに任せます。次に、すべての要素に対してpushBack関数を呼び出します。配列の:

for(int i=0; i<N; i++)
{
    pushBack(l,arr[i]);
}

以上で、リンクリストを実装する方法を学びましょう。

于 2012-11-05T20:29:37.047 に答える
1

配列全体をリンクリストに変換するのではなく、最適なパスをリンクリストに変換するだけです。行き止まりに遭遇したときは、力ずくで指示を試し、バックトラックすることでこれを行います。

リンクリストであるパスは、次のようになります。

struct PathNode
{
    int coordX, coordY;
    PathNode * next, * prev;
}

後で思い出すなら、この構造の絵か何かを描いて、それを投稿に追加します。私の注意を引くために、数時間以内にこの投稿にコメントしてください。

リストには常に開始点が含まれ、これがリストの最初のノードになります。次々と他の位置に移動すると、それらをリストの最後にプッシュします。このように、リストから要素を1つずつ順番にポップするだけで、現在の位置から迷路の始まりまでのパスをたどることができます。

この特定のリンクリストは、2つの方法があるという点で特別です。つまり、次の要素と前の要素の両方へのポインタがあります。2つのうち1つだけのリストは単一リンクリストと呼ばれ、両方のリストは二重リンクリストと呼ばれます。単一リンクリストは一方向のみであり、一方向にのみトラバースできます。

リンクリストは、それぞれ開始端と終了端を持つ巨大な文字列の山と考えてください。迷路の中を歩くとき、あなたはあなたが訪れるすべてのノードでひもを結び、次の広場にあなたと一緒に終わりをもたらします。バックトラックする必要がある場合は、文字列を持ち帰って、間違った正方形を指さないようにします。迷路の終わりまでの道を見つけたら、文字列をたどることで歩数をたどることができます。

->の意味を正確に説明していただけますか?

->オールインワンのポインター逆参照およびメンバーアクセス演算子です。私たちが持っていると言う:

PathNode * p = malloc(sizeof(*p));
PathNode q;

次のいずれかの方法でpとqのメンバーにアクセスできます。

(*p).coordX;
q.coordX;
p->coordX;
(&q)->coordX;
于 2012-11-05T20:31:23.923 に答える