3

私はこれを解決しようと懸命に努力してきましたが、まだ成功していません.次のようなデータ構造体があります(実際には非常に複雑で、議論のために単純化しています):

typedef struct node{
 struct node* next;
  void* arg;
}node_t;

typedef struct queue{
node_t* head;
node_t* tail;
}queue_t;

addQ(queue_t*ptr , int data)
{
    queue_t* q = ptr;
    node_t * n = malloc(sizeof(*n));

    n->arg = data;
    n->next = NULL;

    if(NULL == q->head){
       q->head = q->tail = n;
       return ;
    }
    q->tail->next = n;
    q->tail = q->tail->next;
}

今、私は同じ値のノードを削除したいです (私はいくつかの方法を試しましたが、まだ成功していません)、参考のためにこのシーケンスを検討してください:

addQ(q, 12);
addQ(q, 12);
addQ(q,  4);
addQ(q, 12);
addQ(q, 12);
addQ(q, 14);
addQ(q, 12);
addQ(q, 12);

値が 12 のすべてのノードを削除します。

4

3 に答える 3

4

このソリューションは、ダブル ポインターで少し複雑になりましたが、どのノード (最初のノードと残りのノード) がチェックされているかを特別なケースにする必要がないため、それでも気に入っています。何が起こっているかを説明するのに十分なコメントを入れようとしましたが、一見しただけでは理解できません。

疑似コード..

Queue * q;
VALUE = 12;

// double pointer so we can treat the queue head and subsequent nodes the same.
//   because they are both pointers to Node.  
// Otherwise you'd have to have code that says if the one you're removing is the 
// first element of the queue, adjust q->head, otherwise adjust node->next.  
// This lets you not special case the deletion.
Node ** node_ptr = &(q->head)

while (*node_ptr != null) {
    if ((**node_ptr).arg == VALUE) {
        // store off the matching node to be freed because otherwise we'd orphan
        // it when we move the thing pointing to it and we'd never be able to free it
        Node * matched_node = *node_ptr;

        // when we find a match, don't move where node_ptr points, just change the value it
        // points to to skip the matched node and point to the one after it (or null)
        *node_ptr = matched_node->next; 
        free(matched_node);
    } else {
        // otherwise, nothing was deleted, so skip over that node to the next one.
        // remember, **node_ptr is a double dereference, so we're at the node
        // now, so then we grab the address of the non-matching node's next value so it can be
        // potentially changed in the next iteration
        node_ptr = &((**node_ptr).next);
    }
}
于 2013-05-13T07:20:10.200 に答える
0

キュー内の次のアイテムを取得して削除する関数を既に持っていると仮定してgetQ(q)、それを呼び出しましょうのように (これは であるために機能しませんargがvoid、ロジックは明確である必要があります):

node_t *n;
queue_t *q2 = initialiseQ();
while (n = getQ(q)) {
    if (n->arg != 12) {
        addQ(q2,n);
    }
}
free(q);
q = q2;
于 2013-05-13T06:49:14.967 に答える
0

これは、二重ポインターを使用しないインライン ソリューションです。調整するポインタがキュー構造からノード構造に変更されるため、最初の要素と後続の要素を異なる方法で処理する必要があります。

また、後続のノードについては、後続ノードを追跡する必要があります。これは、一致するノードを削除するときに調整を行う必要があるためです。

Queue * q;
VALUE = 12;


// handle the case where the first node matches.
// you have to adjust the q's head pointer
// delete from the head and set a new head node until a non-matching head is found
while (q->head != NULL && q->head->arg == VALUE) {
  Node * matching_node = q->head;
  q->head = q->head->next;
  free(matching_node);
}

// if there is more than one node left, need to check the subsequent nodes
if (q->head != NULL && q->head->next != NULL) {

    Node * node_ptr = q->head->next;
    Node * prev_node_ptr = q->head;

    while (node_ptr != NULL) {
        if (node_ptr->arg == VALUE) {
            Node * matched_node = node_ptr; // don't orphan it before it's freed

            // You don't move the prev_node pointer since that doesn't change when a match
            //   is found.  Only the node_ptr, which skips to the next one. 
            node_ptr = node_ptr->next;
            free(matched_node);            
        } else {
            prev_node_ptr = node_ptr;
            node_ptr = node_ptr->next;
        }
    }
}
于 2013-05-13T07:38:17.120 に答える