リンクリストのエンキュー機能

Question

私の教授が行った "エンキュー"機能を理解しようとしていますが、いくつかのステップはありません。

struct queue_node { 
int item; 
struct queue_node* next; 
}; 
typedef struct queue_node* queue; 


int enqueue (queue* tail, int i) { 
queue n; 
queue *iter; 
n = (queue)malloc(sizeof(struct queue_node)); 
if (!n) return 1; 
n->item = i; 
n->next = NULL; 
for (iter=tail; *iter != NULL; iter = &((*iter)->next) 
; 
*iter = n; 
return 0; 
} 

まず、 "typedef struct queue_node * queue;"というメッセージが表示されます。私は「エンキューを実行しようとしました私の教授の溶液を読み取ろうとする前に、途中でそう

（私が間違っている場合は、コードを修正してください）ので、私はコードをこのように再解釈しようとした

struct queue_node { 
int item; 
struct queue_node* next; 
}; 
typedef struct queue_node queue; 

int enqueue (queue **tail, int i) { 
queue *n; 
queue **iter; 
n = (queue)malloc(sizeof(struct queue_node)); 
if (!n) return 1; --->what does that mean? 
n->item = i; 
n->next = NULL; 
for (iter=tail; **iter != NULL; iter = &((*iter)->next)--->last part of the for is unclear to me... can i rewrite it as "iter = **((iter)->next)"? 
; 
*iter = n; -->this is the part i don't really get... 
return 0; 
} 

私を混乱させています」機能は自分で

typedef struct node{ 
int value; 
struct node *next; 
}node; 

void enqueue(node *head,int data){ 
if(head->next != NULL){ 
enqueue(head->next,data); 
} 
node *new=NULL; 
new=malloc(sizeof(node)); 
new->value=data; 
new->next=NULL; 
head->next=new; 
} 

これはいいですか？または私はそれを使用することはできません？あなたは

queue* myqueue = (queue*)malloc(sizeof(struct queue_node)); 

の代わりとして、このコメントで指摘

struct queue_node** myqueue = (struct queue_node**)malloc(sizeof(struct queue_node)); 

書くことができるようにtypedef struct queue_node* queue;は新しい型を定義

Answer 1

の助けを事前にすべてに感謝をpointer-ですポインタータイプです。

線

if (!n) return 1; 

試験ポインタnが有効である（すなわちないNULL）との比較が失敗した場合エラーコードとして1を返す場合。今

リストの上にコード

for (iter=tail; **iter != NULL; iter = &((*iter)->next) 
{ 
    *iter = n; /* -->this is the part i don't really get... */ 
    return 0; 
} 

反復するあなたはNULLポインタに遭遇するまで。 ライン*iter = n;だから、これは本質的に、キューの末尾を検索し、最後に新しい要素を割り当てる。現在nodeこの場合の現在のイテレータ（ポインタを間接参照し、それにnを割り当てる。

**((iter)->next) 

は

&((*iter)->next) 

文と同じではありませんあなただけqueueへの実際のポインタを持っているので、struct queue_nodeへのポインタへのポインタである。そして、それGE (*iter)->nextデリファレンスiterqueueのnextフィールドに入力します。 &は、next（これはアドレス演算子）によって参照される要素へのポインタを与えますが、コードは->nextによって参照される実際のオブジェクトを提供します。

今あなたがコードしているために：私はそれに何かを見ることはできません初めに私のコメント以外

void enqueue(node *head,int data) 
{ 
    if(head->next != NULL) /* what happens if head is NULL ?*/ 
    { 
     enqueue(head->next,data); 
    } 
    node *new=NULL; 
    new=malloc(sizeof(node)); 
    new->value=data; 
    new->next=NULL; 
    head->next=new; 
} 

。しかし、実際にコードが実行されているかどうかはテストしていません）;

:)私の説明とあいまいさがある場合は、コメントして、単純にdownvoteしないでください、私は最も経験豊富なのではないことを知っていますCプログラマー。

Answer 2

queue

struct queue_node 
{ 
    int item; 
    struct queue_node *next; 
}; 

typedef struct queue_node queue; 

のあなたの定義を使用する場合は、関数は次のようになります。あなたの関数定義向かい

int enqueue(queue **tail, int item) 
{ 
    queue *node = (queue *)malloc(sizeof(queue)); 
    int success = node != NULL; 

    if (success) 
    { 
     node->item = item; 
     node->next = NULL; 

     while (*tail != NULL) tail = &(*tail)->next; 

     *tail = node; 
    } 

    return success; 
} 

この機能は、キューに追加される新しいノードが正常にそうでなければ0に割り当てられているときで成功した場合に1を返します。

ですから、キューに以下の方法を宣言した場合

キュー*ヘッド= NULL;

関数呼び出しは、valueは、いくつかの整数式で

enqueue(&head, value); 

のように見えることができます。

queueの頭をポインタで間接的に渡す必要があります。そうでない場合は、ポインタを使用しないで、関数に直接頭を渡すと、関数は頭のコピーを取得します。したがって、関数内のコピーの変更は元のヘッドに影響しません。

新しいノードが作成され

queue *node = (queue *)malloc(sizeof(queue)); 

この文で。関数mallocは、割り当てられた動的ノードへのポインタを返します。この文で

int success = node != NULL; 

mallocの呼び出しが成功したか否かに応じて、式node != NULL（1または0のいずれか）の結果が割り当てられています。

mallocの呼び出しが成功した場合、つまりnodeがNULLと等しくない場合、新しいノードが初期化され、キューの末尾に追加されます。 if（成功） { node-> item = item; node-> next = NULL;

 while (*tail != NULL) tail = &(*tail)->next; 

     *tail = node; 
    } 

リストの末尾を見つけるにはどうすればよいですか？

リストが最初に空だった場合、*tailはNULLに等しく、while条件はfalseに等しくなります。*tailはNULLに等しくないのであればNULLに等しいtailの電流値が

*tail = node; 

そうでない場合は、割り当てられたノードのアドレスを代入し、私たちは現在のノードのデータフィールドnextを取得

(*tail)->next 

、我々は参照によって関数に頭を渡すと今度は同じように、そのアドレスを取る

&(*tail)->next 

AT最後に、このデータフィールドにNULLが含まれている場合、新しい作成ノードのアドレスにはNULLを代入します。

あなたがキューに新しいノードを追加する再帰関数を書きたいならば、それはあなたとあなたの教授は基本的に異なった変数を扱っている

typedef struct node 
{ 
    int value; 
    struct node *next; 
} node; 

void enqueue(node **tail, int data) 
{ 
    if (*tail != NULL) 
    { 
     enqueue(&(*tail)->next, data); 
    } 
    else 
    { 
     node *tmp = malloc(sizeof(node)); 
     tmp->value = data; 
     tmp->next = NULL; 

     *tail = tmp; 
    } 
} 

Answer 3

のように見えることができます。

tailポインタがあなたからデキューだろうと右端のノードを意味し、あなたがエンキュー場所に到達するために、あなたは：その後、私は教授が一種の本のように見える絵を目指していると思うの命名に基づき、キューの先頭に到達するまで繰り返します。今ここで重要なことは、iterがノードを直接指していないことです。ここで説明しようとすると、NULLというノードが見つかるまで各ノード内のnextセルを指しています。

私は実際にあなただけのノードを追加するためにキューをループしたくないと権利だと思います。実際のキュー実装（リンクリストを使用して作成されることもあります）では、一定時間が必要ですO(1)キューに入れるとデキューするので、常にキューの両端にポインタを置いています。

最後に、誰もがC命名規則について異なる意見を持っていますが、私は教授の例にいくつか混乱しているtypedefがあることに同意する傾向があります。 Linuxカーネルのようなコードベースの中には、ポインタや構造体のtypedefをまったく使用しないことをお勧めします。