/큐

Question

나는이 그러나 아직 내가 (사실 난 그냥 설명은 간단 매우 복잡) 다음과 같은 데이터 구조체가 성공하지 해결하기 위해 열심히 노력하고있다

:

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

모든 노드를 삭제하려면 :

지금 나는 (I 그러나 아직 성공하지 몇 가지 방법을 시도), 그냥 참조를 위해이 순서를 고려 같은 값의 노드를 삭제할

Answer 1

이미 큐의 다음 항목을 가져 와서 제거하는 함수가 있다고 가정하면이 함수를 getQ(q)으로 호출하면 이미 가지고있는 작업을 사용하여 큐의 내부를 알지 않고도 목표를 달성 할 수 있습니다 , 예. 그것은 '아무튼, 그것은처럼 여전히

node_t *n; 
queue_t *q2 = initialiseQ(); 
while (n = getQ(q)) { 
    if (n->arg != 12) { 
     addQ(q2,n); 
    } 
} 
free(q); 
q = q2; 

Answer 2

이 솔루션은 이중 포인터와 약간의 털이 있어요,하지만 난 : 같은 (arg이 void 때문에이 작동하지 않습니다,하지만 논리는 명확해야한다) 어떤 노드 (첫 번째 노드와 나머지 노드)가 검사되는지 특별한 경우가 있습니다. 나는 무슨 일이 벌어지고 있는지를 설명하기 위해 충분한 설명을 덧붙이려고했지만, 언뜻보기에는 나를 따라 가기가 여전히 어렵다.

의사 ..

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); 
    } 
} 

Answer 3

여기에 이중 포인터를 사용하지 않는 인라인 솔루션입니다. 큐 구조에서 노드 구조로의 변경을 조정하기위한 포인터 이후 첫 번째 요소와 후속 요소를 다르게 처리해야합니다.

또한 후속 노드의 경우 후미 노드를 추적해야합니다. 일치 노드를 삭제할 때 조정해야하기 때문입니다.

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; 
     } 
    } 
}