リンクリスト内のポインタへのポインタ

Question

誰かが私にこのコードが結果として空のリストを与える理由を説明できますか？

typedef struct str_node{
int data;
struct str_node *next;
}node;


void begin(node *head);
void display_list(node *head);


int main(){

node *head;
int i;

head = NULL;

for(i=0;i<5;i++) {
    begin(head);
}
display_list(head);




return 0;
}

void begin(node *head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = head;
head = new;
}

しかし、begin（）関数をポインターからポインターに変更すると、正しいリストが表示されますか？

void begin(node **head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = *head;
*head = new;
}

また、メインでノードヘッドを関数に渡すときに、「＆head」として渡さなければならない理由を説明できますか？そしてもはや「頭」として

Answer 1

このコードスニペットの最初のプログラムでは

head = NULL;

for(i=0;i<5;i++) {
    begin(head);
}

ポインタheadはbegin値によって関数に渡されます。つまりhead、mainで宣言されたポインターの値のコピーが作成され、関数beginと同じ名前のパラメーターに割り当てられます。

void begin(node *head);

したがって、関数内では、変更されるhead元のポインターのコピーを最初に保持するのはパラメーターですhead。headパラメータに値が割り当てられていた元のポインタは変更されていません。

mainで宣言された元のポインターヘッドを変更するには、2番目のプログラムで行われるように、ポインターヘッドへのポインターを介して間接的に参照することにより関数に渡す必要があります。

したがって、関数は次のように宣言する必要があります

void begin(node **head);

そして、あなたはそれにポインタを介して間接的にポインタヘッドを渡す必要があります

begin( &head );

この場合、渡されたポインターを逆参照すると、関数はmainで宣言された元のポインターヘッドに直接アクセスし、それを変更できます（最初の関数定義で行われる値のコピーではありません）

new->next = *head;
*head = new;

より明確にするために、この単純な実証プログラムを検討してください。

#include <stdio.h>

typedef int T;

void f( T t )
{
    t = 10;
}

int main(void) 
{
    T t = 0;
    
    printf( "Before calling f t is equal to %d\n", t );
    
    f( t );
    
    printf( "After  calling f t is equal to %d\n", t );

    return 0;
}

その出力は

Before calling f t is equal to 0
After  calling f t is equal to 0

関数fは渡された引数の値のコピーを処理するためt、mainで宣言された変数の値は変更されませんでした。

したがって、次のtようなポインタを介して参照によって元の変数を渡す必要があります。

#include <stdio.h>

typedef int T;

void f( T *t )
{
    *t = 10;
}

int main(void) 
{
    T t = 0;
    
    printf( "Before calling f t is equal to %d\n", t );
    
    f( &t );
    
    printf( "After  calling f t is equal to %d\n", t );

    return 0;
}

これで、プログラムの出力は次のようになります。

Before calling f t is equal to 0
After  calling f t is equal to 10

これらのデモンストレーションプログラムでは、名前Tはタイプのエイリアスとして使用され、int主にオブジェクトtはこのタイプを持っています。

ここで、名前Tがint *型のエイリアスであると仮定します。

typedef int * T;

この場合、例えば、mainでの宣言

T t = NULL;

変数tのポインタ型がint *。であることを意味します。つまり、それはと同等です

int * t = NULL;

したがって、元の変数を変更する必要がある関数に渡すには、次のように参照によって渡す必要があります。

f( &t );

つまり、対応する関数のパラメータタイプは次のように宣言されます。

void f( T *t );

しかしT、のエイリアスであるように、int *それは関数がタイプのパラメータを持っていることを意味しますint **。

void f( int * *t );

Answer 2

ためには、headそれが変化し、一方、関数の無影響外部を有していない変更、（効果的に）ローカル変数で*head変更何headを指し、したがってありません。

関数がint変数（たとえばx）の値を変更できるようにする場合xは、型int*を持つ、へのポインターを渡し、。xを使用してへのポインターを取得します&x。どんなタイプxでも同じことが言えます。

Answer 3

宣言することで少し混乱するかもしれません

    node        *head;

の代わりに

    node*       head;

あなたは宣言していheadます。headは変数であり、ポインタです。ノードではありません。また、ノードはリンクリストではないことにも注意してください。リンクリストはノードのコレクションであり、有用な実装を得るために他の何かである可能性があります。これについては、後で最後に詳しく説明します。

事実はあなたがmain()宣言したことですhead、ただnode*。ノード自体はまだ存在していません。あなたは次のbegin()ように宣言しました

    void begin(node *head);

そして私はあなたがそれをよりはっきりと見るだろうと思います

    void begin(node*  parameter);

parameterですnode*。

内部begin()にはポインタのコピーがあり、ポインタを変更しても元のポインタは変更されませんmain()。あなたの場合、それはmain()永遠にを指しNULLます。

重要なのは、ポインターは他の変数と同じであるということです。ポインターにはアドレスがあります。そして内容。値を渡すとき、あなたがしたのと同じように、のポインタは、から来たVALUEでbegin()始まります。しかし、それらの間の結合は、呼び出しで終了します：初期値。NULLmain()

にポインタを渡すとbegin()、演算子「address of」を使用して&head変更を記述します。演算子を使用してポインタを変更'*'します。つまり、ポインタが指すアドレスを変更するため、main()。以来headされnode*、それへのポインタとして宣言されますnode**

ただし、次begin()を使用してリンクリストの宣言を変更することを検討してください。

    node* begin(node* node);

ロジックは、ノードを挿入するとリストの先頭が変更される可能性があるため、次のように新しいアドレスを返すというものです。

node* _insert_begin(int value, node* pNode)
{
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = pNode;
    return new;
}

これを書くための一般的な方法です。もう1つはを使用することnode**です。

ここで説明しているように、リストの先頭を変更できる操作はすべて、

• 新しい頭を返す
• 頭のポインタへのポインタを受け取り、更新します

リストの先頭に挿入される次のコードをもう一度参照してください。

node* _insert_begin(int value, node* pNode)
{   // insert 'value' at the start of the list
    node* new = (node*)malloc(sizeof(node));
    (*new).data = value;
    new->next = pNode;
    return new;
}

戻るnewとhead更新されます。そして、あなたは書くことができますmain()

node* another = NULL;
display_list(another);

// inserts 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
    another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);

行に注意するanother = _insert_begin(i, another);と、のポインタがどのようmain()に更新されるかがわかります。

これが出力です

empty list
inserted 5..0 at the beginning
       0        1        2        3        4
       5
list has 6 elements

のこの実装を使用するとdisplay_list()、1行に5つの値が出力されます。

int display_list(node* p)
{
    if (p == NULL)
    {
        printf("empty list\n");
        return 0;
    };
    int count = 0;
    // not empty
    do
    {
        printf("%8d ", p->data);
        count++;
        if (count % 5 == 0) printf("\n");
        p = p->next;
    } while (p != NULL);
    if (count % 5 != 0) printf("\n");
    printf("list has %d elements\n", count);
    return count;
};

別の例：最後に挿入

リストが空の場合、最後に挿入するとヘッドも変更される可能性があるため、ヘッドアドレスを返す必要があることに注意してください

node* _insert_end(int value, node* pNode)
{   // insert value at the end of the list
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = NULL;
    if (pNode == NULL) return new;
    node* p = pNode;
    while (p->next != NULL) p = p->next;
    p->next = new;
    return pNode;
}

別の使用法：昇順で挿入

確かに、昇順で挿入すると、次のように頭を変更することもできます

node* _insert_ordered(int value, node* pNode)
{   // insert value at ascending order in the list
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = NULL;
    if (pNode == NULL) return new;

    node* p = pNode;
    node* prev = NULL; // previous node: list if forward only
    while (p->next != NULL)
    {
        if (new->data < p->data)
        {
            // insert before first greater than value
            if (prev == NULL)
            {
                // new head
                new->next = p;
                return new;
            };  // if()
            prev->next = new;
            new->next = p;
            return pNode; // no change in head
        };
        prev = p; p = p->next; // updates pointers
    };  // while()
    // we are at the end: new will be the last?
    if (new->data < p->data)
    {
        if (prev == NULL)
            pNode = new;
        else
            prev->next = new;
        new->next = p;
    }
    else
    {
        p->next = new;
    };
    return pNode;
}   // _insert_ordered()

リストの削除

リストを削除するnode*と、ヘッドポインタを無効にするためにも返されるはずです。いつものことです。あなたがそれの仕組みに慣れるにつれて、これは無効なポインタが周りに残っていないことを保証します。

このロジックは協調的であることに注意してください。ヘッドを変更する可能性のあるすべての呼び出しで、ヘッドポインタを割り当てる必要があります。

node* delete_list(node* H)
{
    if (H == NULL) return NULL;
    if (H->next == NULL)
    {   // single node
        free(H);
        return NULL; 
    };
    // more than one node
    do
    {   node* p = H->next;
        free(H);
        H = p;
    } while (H != NULL);
    return NULL;
};

実行中のプログラム

サンプルプログラムの出力

empty list
inserted 5..0 at the beginning
       0        1        2        3        4
       5
list has 6 elements
inserted 6 to 10 at the end
       0        1        2        3        4
       5        6        7        8        9
      10
list has 11 elements
inserted 0 to 10, ordered
       0        0        1        1        2
       2        3        3        4        4
       5        5        6        6        7
       7        8        8        9        9
      10       10
list has 22 elements
inserted -1 to -10, ordered
     -10       -9       -8       -7       -6
      -5       -4       -3       -2       -1
       0        0        1        1        2
       2        3        3        4        4
       5        5        6        6        7
       7        8        8        9        9
      10       10
list has 32 elements
inserted 11 to 20, ordered
     -10       -9       -8       -7       -6
      -5       -4       -3       -2       -1
       0        0        1        1        2
       2        3        3        4        4
       5        5        6        6        7
       7        8        8        9        9
      10       10       11       12       13
      14       15       16       17       18
      19       20
list has 42 elements
about to delete list
empty list

Cプログラムの例

#include <stdio.h>
#include <stdlib.h>

typedef struct str_node
{
    int             data;
    struct str_node* next;
}   node;

void    begin(node* pNode);
node*   delete_list(node*);
int     display_list(node*);
node*   _insert_begin(int, node*);
node*   _insert_end(int, node*);
node*   _insert_ordered(int, node*);

int main()
{
    node* another = NULL;
    display_list(another);

    // insert 5 to 0 at the beginning
    for (int i = 5; i >= 0; i -= 1)
        another = _insert_begin(i, another);
    printf("inserted 5..0 at the beginning\n");
    display_list(another);

    // insert 6 to 10 at the end
    for (int i = 6; i <= 10; i += 1)
        another = _insert_end(i, another);
    printf("inserted 6 to 10 at the end\n");
    display_list(another);

    // insert 0 to 10 ordered
    for (int i = 0; i <=10; i += 1)
        another = _insert_ordered(i, another);
    printf("inserted 0 to 10, ordered\n");
    display_list(another);

    // insert -1 to -10 ordered
    for (int i = -1; i >= -10; i -= 1)
        another = _insert_ordered(i, another);
    printf("inserted -1 to -10, ordered\n");
    display_list(another);

    // insert 11 to 20 ordered
    for (int i = 11; i <= 20; i += 1)
        another = _insert_ordered(i, another);
    printf("inserted 11 to 20, ordered\n");
    display_list(another);

    printf("about to delete list\n");
    another = delete_list(another);
    display_list(another);
    return 0;
}

node* delete_list(node* H)
{
    if (H == NULL) return NULL;
    if (H->next == NULL)
    {   // single node
        free(H);
        return NULL; 
    };
    // more than one node
    do
    {   node* p = H->next;
        free(H);
        H = p;
    } while (H != NULL);
    return NULL;
};

node* _insert_begin(int value, node* pNode)
{   // insert 'value' at the start of the list
    node* new = (node*)malloc(sizeof(node));
    (*new).data = value;
    new->next = pNode;
    return new;
}

node* _insert_end(int value, node* pNode)
{   // insert value at the end of the list
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = NULL;
    if (pNode == NULL) return new;
    node* p = pNode;
    while (p->next != NULL) p = p->next;
    p->next = new;
    return pNode;
}

node* _insert_ordered(int value, node* pNode)
{   // insert value at ascending order in the list
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = NULL;
    if (pNode == NULL) return new;

    node* p = pNode;
    node* prev = NULL; // previous node: list if forward only
    while (p->next != NULL)
    {
        if (new->data < p->data)
        {
            // insert before first greater than value
            if (prev == NULL)
            {
                // new head
                new->next = p;
                return new;
            };  // if()
            prev->next = new;
            new->next = p;
            return pNode; // no change in head
        };
        prev = p; p = p->next; // updates pointers
    };  // while()
    // we are at the end: new will be the last?
    if (new->data < p->data)
    {
        if (prev == NULL)
            pNode = new;
        else
            prev->next = new;
        new->next = p;
    }
    else
    {
        p->next = new;
    };
    return pNode;
}   // _insert_ordered()

int display_list(node* p)
{
    if (p == NULL)
    {
        printf("empty list\n");
        return 0;
    };
    int count = 0;
    // not empty
    do
    {
        printf("%8d ", p->data);
        count++;
        if (count % 5 == 0) printf("\n");
        p = p->next;
    } while (p != NULL);
    if (count % 5 != 0) printf("\n");
    printf("list has %d elements\n", count);
    return count;
};

間違いなくより便利なリンクリスト構造

次のことを考慮してください

struct no
{
    void*       item;
    struct no*  next;
    struct no*  prev;
};  // no
typedef struct no Node;

typedef struct
{   // example, more flexible
    char*       name;
    unsigned    size;
    unsigned    capacity;
    Node*       head;
    Node*       tail;
}   Linked_list;

このようにして、リンクリストはノードのコンテナとして定義されます。

• オプションもありますname。
• size 常に利用可能で最新です
• サイズ制限は次のように実装できます capacity
• リストには先頭と末尾の両方へのポインタがカプセル化されているため、最後と最初に挿入する場合、他のすべてのノードをたどる必要はありません。
• ノードには次のノードと前のノードへのポインタがあるため、プレイリストやそのようなコレクションなどの一部のデータをより簡単に繰り返すことができます。
• 各リストはこのメタデータのすべてをカプセル化するため、プログラムは任意の数のリストを持つことができます。
• データはvoidへのポインタであるため、リストには何でも含めることができます。 void*
• empty（）やsize（）のような関数は簡単に実装できます
• すべての関数はリストへのポインタを使用します

    Linked_list  ll_one;
    Linked_list  many_ll[20];
    Linked_list* pLL = &ll_one;

Answer 4

に関して：

void begin(node *head){

変更headすると、呼び出しスタックの「head」のみが変更されます。必要なのは、呼び出し元の関数の「head」が指す場所を変更することです。これを行うには、呼び出し元は「head」のアドレスを渡す必要があります。「頭」自体がポインタであるという事実は、何をする必要があるかを明確にするのに役立ちません。