1

編集: 問題: 2 つのノード間のノードを削除し、外側のノードを相互にリンクします。

いくつかの四分木と八分木を学習して構築し、細分割が本当に好きだったので、サーバーで細分割を使用することにしました。ただし、ノードを自分自身の中に配置するだけです。私の問題は、ノードが途中にある場合、前のノードを次のノードにリンクする方法がわからないことです。私はこれを正しくやっているのだろうかと思っています。以下は私のコードで、問題領域がどこにあるかをコメントします。どんな助けでも素晴らしいでしょう！

bool deleteNode ( SOCKET s , client_information_class *prev ) {
          bool return_value = false;
          if ( node[0]->client_socket != s ) {
               if ( node[0]->node != NULL ) {
                    return_value = node[0]->deleteNode ( s , *node );
               } else {
                    cout << endl << "Can not call deleteNode anymore ... Did not find the node to delete ... " << endl;
                    return return_value;
               }
          } else {
               if ( node[0]->client_state == 1 )
                    InterlockedDecrement(&connection_count);
               if ( node[0]->node != NULL ) {          // there is a next node
                    client_information_class **next = node[0]->node;
                    if ( next[0]->node != NULL ) {
                         // problem area
                         cout << endl << "next[0]->node is not null" << endl;
                         prev->node = next[0]->node[0]->node; // ??? I know its wrong
                    } else {
                         // problem area
                         cout << endl << "next[0]->node is null" << endl;
                         prev->node = next[0]->node;  // ??? I know its wrong
                    }
                    delete node;
               } else {                                   // its the last one
                    prev->node = NULL;
                    delete node;
               }
               InterlockedDecrement(&socket_count);
               return_value = true;
          }
          return return_value;
}
4

2 に答える 2

2

問題が正しければ、リンクされたリスト内にアイテムを挿入するのに問題があります。これが問題であることを本当に願っています。

コードのすべてを実際に取得したわけではありませんが (少し文脈から外れているため)、例でロジックを示します。次の構造を持つノードを使用します。

class Node
{
public:
    Node * next_;
    Node * prev_;
    int i;//we need this to tell nodes apart. 
    //And whatever data you want.
}

そのため、各項目が前の項目と次の項目へのポインタを持つリンク リストを作成します。より複雑な構造 (たとえば、左+右+子+親ポインターがある場合など) のロジックは同じですが、唯一の違いは、それらすべてを設定する必要があることです。本当にあまり変わりません。

したがって、リストを構築するには、さまざまな操作を処理するいくつかのコンストラクターが必要になります。

空のノードを作成するデフォルトのコンストラクター:

Node()//default constructor
{
    prev_ = nullptr;
    next_ = nullptr;
    i = 0;
}

リストの最後の項目へのポインタを取り、それ自体をリストの最後に追加するコンストラクタ:

Node( Node * prev )//constructor for appending to the end of the list
{
    prev_ = prev;
    next_ = nullptr;//we append to the end, so there is no "next" element
prev->next_ = this;
    i = 0;
}

そして最後に、途中に挿入するコンストラクター（これが必要だと思います）：

Node( Node * prev, Node * next)//Inserting between prev and next nodes
{
    prev->next_ = this;
    next->prev_ = this;
    this->prev_ = prev;
    this->next_ = next;
    i = 0;
}

これで、やりたいことを何でもできるツール一式がそろいました。最後に、ノードを削除します。

void deleteNode( Node * deleteMe )
{
    deleteMe->prev_->next_ = deleteMe->next;
    deleteMe->next_->prev_ = deleteMe->prev;
    delete deleteMe;
}

または、より読みやすい構文:

void deleteNode( Node * deleteMe )
{
    Node * prevNode = deleteMe->prev_;
    Node * nextNode = deleteMe->next_;
    prevNode->next_ = deleteMe->next;
    nextNode->prev_ = deleteMe->prev;
    delete deleteMe;
}

たとえば、10 個の要素のサンプル リストを作成してみましょう。

int main()
{
    Node * root =  new Node();//the root of the list. it never changes.
    Node * last = root;//The pointer to the last element
    for(int i = 0; i < 10; i++)
    {
        Node * tmp = new Node( last );
        last = tmp;
    }
}

ここでは、リスト内のすべての要素が適切にリンクされており、iフィールドの値が 0 になっています。たとえば、3 番目と 4 番目の要素の間など、中間のどこかに別の要素を挿入してみましょう。

Node * thirdNode = root->next_->next_;//I know this sucks, but it's just an example.
Node * insertMe = new Node(thirdNode, thirdNode->next_);//inserting between the third and the fourth.
insertMe->i = 9;//this will indicate the one we inserted, since all the others will have this as 0.

これで、挿入が正しく行われたかどうかを簡単に確認できます。すべての要素のデータを入力してみましょう:

for( Node * it = root; it!= last; it = it->next_)
{
    std::cout << it->i << " ";
}

結果は になります0 0 0 9 0 0 0 0 0 0 0。

最後に、挿入したばかりのノードを削除しましょう。

deleteNode( insertMe );

同じ vay に値を出力しない場合は、ゼロのみが表示されます。これは、ノードが正常に削除されたことを意味します。

ノードにさらに多くのポインターがある場合は、同じ方法でそれらを適切に処理するだけです。もう 1 つのヒントは、 のような構造を避けることですthis->next->next->prev。現在の要素から 3 番目の要素の「前の」ポインタを参照しているとは言い難いです。代わりに、次のようなものを使用します。

Node * target = this->next->next;//easy to read

または多分

Node * target = this;
for(int i = 0; i < 5; i++)
    target = target->next;

次に、取得したポインターを操作します。

于 2012-07-20T06:36:17.177 に答える