1

リンクされたリストからノードを削除する反復削除機能に取り組んでいます。コードは正常に機能するはずだと思います。リストをトラバースし、必要なノードを見つけ、次のノードに頭を向け、現在のノードを削除しますが、テスト実行すると、無限ループが発生します。エラーを特定するのを手伝ってください。関数は次のとおりです。

typedef struct E_Type * List;
struct E_Type
{
  int data;
  struct E_Type* next;
};

関数:

 bool erase(List & l, int data){
 List head = l; 
 if (l != 0){
    for(List current = head; current; current = current->next){
    if ( current->data == data )
       head = current->next;
       delete current;
       return true;
     }
   }
 return false;
}

テストプログラム:

int main()
{
  List l = 0;
  cout << boolalpha << l->data << "went well? "<< (insert(l,73)) << endl;
  cout << boolalpha << l->data << "went well? "<< (insert(l,24)) << endl;
  print(cout,l);
  cout << boolalpha << "Is deleted 24? "<<(erase(l,24)) << endl;    
  cout << boolalpha << "Is deleted 35? "<<(erase(l,35)) << endl;
  print(cout,l);
  cout << endl;
  return 0;
}

インサート:

bool insert(List & l, int data)
{   

    List current = l;
    while(current != 0) {
        if (current->data == data)
        return false;
       current = current->next;
    }

    if (l == 0 || l->data > data){
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
    return true;
    }

    else if(l->data < data){
    insert(l->next, data);
    return true;
    }

}
4

3 に答える 3

3

forループで前のノードも追跡し、次のようにする必要があります。

prev->next = current->next;
delete current;

削除された要素がリストの最初の要素である場合も処理する必要があります。この場合は、次のように設定lする必要があります。l->next

 bool erase(List & l, int data){
 if (l != 0){
    for(List current = head, prev = 0; current; prev = current, current = current->next){
    if ( current->data == data )
    {
       if (prev)
       {
           prev->next = current->next;
       }
       else
       {
            l = current->next;
       }
       delete current;
       return true;

     }
   }
 return false;
}

あなたの最初の消去はおそらく循環リストを作成しているでしょう。

于 2012-12-12T13:22:31.297 に答える
3

Andreas Brinck がすでに指摘しているように、「前の」リンクも更新する必要があります。ただし、これには専用の変数は必要ありません。ポインターへのポインターを使用するだけです。

bool erase(List & l, int data){
  List *it = &l;
  while ( *it ) {
    if ( (*it)->data == data ) {
      List next = (*it)->next;
      delete *it;
      *it = next;
      return true;
     }
     it = &(*it)->next;
  }
  return false;
}

これにより、空のリストからの削除、リストの最初の要素の削除、リストの最後の要素の削除など、すべての「特殊なケース」の処理も処理されます。

于 2012-12-12T13:49:05.750 に答える
0

挿入メソッドも確認する必要がある場合があります。

それは可能ですか

current == current->next

もしそうなら、それは無限ループを引き起こす可能性があります。

于 2012-12-12T13:17:28.317 に答える