リンクリストの要素を削除すると、無限ループ

Question

を引き起こし、私は入力に整数のリストを受け取り、プログラムを書いて、それが次の操作を実行する整数に基づいています：場合

1. は、絶対値を削除します数は、リストの末尾にそれを追加し、正であっても、そのリスト

2. 数が正と奇数の場合の上で追加した場合、入力の値が

3. 負である

4. 数値が0の場合は、プログラムを終了してリストを印刷します。

私の問題は、私はリストを印刷するときに、プログラムが無限ループに入り、リスト上の無限ループの原因となるpop_el機能、です。 これは私のコードです：

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

typedef struct ll_node_S * ll_node_ptr; 
struct ll_node_S 
{ 
    int v; 
    ll_node_ptr next; 
}; 
typedef struct ll_node_S ll_node; 

ll_node_ptr push_tail(ll_node_ptr head, int v) 
{ 
    ll_node_ptr backup = head; 
    ll_node_ptr current = head; 

    while(current->next != NULL) 
    { 
     current = current->next; 
    } 
    current->next = (ll_node_ptr) malloc(sizeof(ll_node)); 
    current->v = v; 
    return backup; 
} 

ll_node_ptr push_head(ll_node_ptr head, int v) 
{ 
    ll_node_ptr new_head = (ll_node_ptr)malloc(sizeof(ll_node)); 
    new_head->v = v; 
    new_head->next = head; 
    return new_head; 
} 

ll_node_ptr pop_el(ll_node_ptr head, int el) 
{ 
    ll_node_ptr backup = head; 
    ll_node_ptr current = head; 
    ll_node_ptr previous = NULL; 
    int found = 0; 

    while(current != NULL && !found) 
    { 
     if(current->v == el) 
     { 
      if(previous == NULL) 
      { 
       backup = current->next; 
       free(current); 
       current = backup; 
       previous = current; 
      } 
      else 
      { 
       previous->next = current ->next; 
       free(current); 
       current = current->next; 
      } 

      found = 1; 
     } 
     else 
     { 
      previous = current; 
      current = current->next; 
     } 
    } 
    return backup; 
} 

void print(ll_node_ptr head) 
{ 
    ll_node_ptr current = head; 
    printf("%d\n", head->v); 
    while(current->next != NULL) 
    { 
     current = current->next; 
     printf("%d\n", current->v); 
    } 
} 

int isPair(int n) 
{ 
    return ((n % 2) == 0); 
} 

int main(int argc, char** argv) 
{ 
    int n = 1; 
    ll_node_ptr list = NULL; 
    while(n != 0) 
    { 
     scanf("%d", &n); 

     if(n < 0) 
     { 
      list = pop_el(list, -n); 
     } 
     else 
     { 
      if(isPair(n)) 
      { 
       list = push_head(list, n); 
      } 
      else 
      { 
       list = push_tail(list, n); 
      } 

     } 


    } 

    print(list); 
    //should free the list 
    return 0; 
} 

、これは私が反対のコードをテストしてい（入力に渡された）テストケースである：

2 
2 
9 

：以下の出力を生成する必要があり

4 
5 
2 
-4 
-5 
-3 
9 
2 
0 

手がかりはありますか？

Answer 1

まず、リストを操作するときに再帰関数を使用することをお勧めします。デバッグと理解がはるかに簡単です。

私は私があなたのpush_tail機能で問題を見つけたと思う：次>あなたは電流のためにメモリを割り当てる

current->next = (ll_node_ptr) malloc(sizeof(ll_node)); 
current->v = v; 

が、現在のノードに値を割り当てます。 これは

current->next = (ll_node_ptr) malloc(sizeof(ll_node)); 
current->next->v = v; 
current->next->next = NULL; 

多分これはあなたの問題とは何かを持っていなければなりません。

Answer 2

@Vitekが指摘しているように、push_tail()の機能を修正することで、直ちに問題を解決することができます。元のコードは、間違ったノードに値を格納するだけでなく、新たに割り当てられたテールノードのnextフィールドをNULLに設定することもできませんでした。この関数にはもう1つの問題があります：とpush_tail()関数の両方が、NULLheadポインタで呼び出されたときにノードポインタを作成して返す必要があります。元のpush_head()関数はこれを行いますが、push_tail()関数はありません。ユーザによって入力された最初の数字が奇数の場合、最初のノードはpush_tail()関数を介してリストに追加され、未定義の動作（おそらくセグメンテーション違反）につながります。

さらに重要なことは、コードを単純化することに取り組むことです。これにより、書込みが容易になり、デバッグが容易になります。たとえば、あなたのprint()関数は3行に削減することができます。

void print(ll_node_ptr current) 
{ 
    while(current) { 
     printf("%d\n", current->v); 
     current = current->next; 
    } 
} 

push_tail()機能を改善するためにできることがいくつかあります。あなたがmalloc()の結果をキャストする必要はありません

ll_node_ptr push_tail(ll_node_ptr head, int v) 
{ 
    ll_node_ptr current = head; 
    ll_node_ptr prev = NULL; 
    ll_node_ptr tail = malloc(sizeof(ll_node)); 

    if (tail == NULL) { 
     fprintf(stderr, "Tail node allocation error\n"); 
     exit(EXIT_FAILURE); 
    } 

    tail->v = v; 
    tail->next = NULL; 

    while (current) { 
     prev = current; 
     current = current->next; 
    } 

    if (head) { 
     prev->next = tail; 
    } else { 
     head = tail; 
    } 

    return head; 
} 

：ここでは新バージョンです。 Opinions differ on whether or not you should do soですが、キャストなしでの記述はコードを単純化します。また、malloc()が要求されたメモリを割り当てたことを確認する必要があります。これは、代わりにrealloc()を使用している場合に特に重要です。そうしないとメモリリークが発生する可能性があるためです。ここで新しいテールノードが作成されると、vとnextのフィールドがすぐに設定されます。

通常、current->nextノードを調べるのではなく、currentノードを調べることによって、リンクされたリストを反復する方が簡単です。ノードポインタprevを使用すると、これが容易になります。新しい関数は、current == NULLまでリストを反復処理し、その時点でリストの最後のノードを指すprevを指します。ユーザが入力した最初の数字が奇数である場合に発生する可能性のあるNULLポインタとしてheadが渡された場合、はheadに初期化されているため、繰り返しループはスキップされます。ループの後のコードは、最後のノードのnextフィールドに、空でないリストが関数に与えられた場合に新しく作成されたテールノードを指すように設定します。そうでない場合はheadが新しいテールノードになります。最後に、headが呼び出し関数に返されます。

pop_el()関数には非常に単純化され、余分なコードがたくさんあります。この関数は本当に完全に再設計されるべきです。あなたが持っている場合は：

previous->next = current ->next; 
free(current); 
current = current->next; 

をあなたはcurrentによって参照free Dのメモリを持っている、あなたは、このメモリへのポインタを間接参照にしてみてください。 free()への呼び出しの後で、このメモリを所有しなくなりました。これはundefined behaviorです。代わりにあなたがしたい：

current = previous->next; 

をしかしfoundが1への次のセットであるため、これは、本当に問題ではない、ループが終了し、currentのこれ以上の用途に機能return秒backup、。上記の割り当ては不要なので、currentに削除するだけです。

この情報を使用して、プログラムの残りのコードを改善することができます。あなたが見たいかもしれない他の問題があります。 typedefポインタには一般的に悪い習慣があります。これはコードを難読化するだけであり、プログラミングエラーの可能性を高めます。指定した仕様では、同じ値を含む複数のノードがある場合、つまり1つまたはすべてを削除する必要がある場合に、どうなるべきかを明確にしていませんか？また、ユーザーが入力した最初の数字が0の場合はどうなりますか？

Answer 3

いくつかのこと、pop_elで

、

1。previousがNULLの場合は、head ptrを次のノードに移動するだけです。だからそれは新しいheadになるでしょう。以前2.Ifは

if(previous == NULL) 
{ 
    backup = current->next; 
    free(current);  
    //current = backup; ---> Not needed. 
    //previous = current; ---> Not needed. 
    break; //   ---> No need of setting found flag. You can remove it 
} 

はNULLではない、あなただけのcurrentノードの次のノードにPTR横previousノードを指すようにする必要があります。

else 
{ 
    previous->next = current ->next; 
    free(current);   
    //current = current->next; ---> Not needed. 
    break; //   ---> No need of setting found flag. You can remove it 
} 

3.In push_tailあなたはcurrent->nextノードに対して、あなたは現在のノードのvにvを追加している次の行にメモリを割り当てています。それは間違っている。次のことを確認し、

ll_node_ptr push_tail(ll_node_ptr head, int v) 
{ 
    ll_node_ptr backup = head; 
    ll_node_ptr current = head; 
    ll_node_ptr new = NULL; // Created new pointer 
    while(current->next != NULL) 
    { 
     current = current->next; 
    } 
    //current->next = (ll_node_ptr) malloc(sizeof(ll_node)); 
    new = (ll_node_ptr) malloc(sizeof(ll_node)); 
    //current->v = v; ----> incorrect. new Value is actually replacing the old value. 
    new->v = v;  // New value is added in the newly created node. 
    new->next = NULL; 
    current->next = new; 
    return backup; 
} 

4.Youは、デバッガが役立つだろうあなたのprintロジック

void print(ll_node_ptr head) 
{ 
    ll_node_ptr current = head; 
    //printf("%d\n", head->v); 
    while(current != NULL) 
    { 
     printf("%d\n", current->v); 
     current = current->next; 
    } 
}