다른 방법이

Question

내가 링크 된 목록을 반복 할 때 생각 제일 먼저이 작업을 수행하는 것입니다

Node* node = head; 

while (node) 
{ 
    // do something to node 
    node = node->next; 
} 

을하지만 가끔은 나는 사람들이이 복잡한 일을 수행 참조 :

Node** node = &head; 

while (*node) 
{ 
    // do something to node 
    node = &(*node)->next; 
} 

을

차이점과 두 번째 차이점은 무엇입니까?

Answer 1

분명히 첫 번째 방법을 이해합니다.

첫 번째와 두 번째의 근본적인 차이점은 포인터를 사용하여 목록을 열거하는 것입니다. 처음에는 포인터 의 값인이 로컬 변수를 통해 사용되며 매번 현재 노드의 next 포인터의 값으로 업데이트됩니다. 두 번째에서는 포인터 포인터가 "현재"포인터의 주소를 저장하는 데 사용됩니다. 주소가 가리키는 포인터는 그 값만이 아닌 "목록의 실제 포인터"입니다. 처음에는 head 포인터를 처리합니다. 각 단계마다 현재 노드의 next 포인터를 처리합니다. 알고리즘이 끝나면 의 주소를 마지막으로next 링크 된 목록의 구성원으로 유지합니다. 그 값은 더 나은 값입니다.

두 번째 항목은 단순한 열거 형을 제외하고는 별개의 장점이 있습니다. 이 방법은 위치 목록 삽입 및 제거와 같은 유지 관리 시나리오에서보다 일반적으로 사용됩니다.

예 :

struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

열거하는 첫 번째 방법을 사용하여 다음 노드 형태와 연결리스트 만 헤드 포인터 주어리스트의 마지막에 새로운 노드를 추가하는 기능을 쓰기 초기 NULL 헤드 포인터를 검출하기 위해 이전 포인터 및 특별한 고려 사항을 유지할 것을 요구한다. 다음 함수는 않는, 항상 연결리스트의 머리 반환

struct Node * ll_insertTail(struct Node *head, int data) 
{ 
    struct Node *prev = NULL, *cur = head; 

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

    cur = malloc(sizeof(*head)); 
    cur->data = data; 
    cur->next = NULL; 

    if (prev == NULL) 
     return cur; 

    prev->next = cur; 
    return head; 
} 

같은 작업을하지만, 포인터에 대한 포인터 접근 방식을 활용하면 실제 포인터 멤버 (단지 그 값)이 될 것이다 도보로

struct Node* ll_insertTail(struct Node *head, Type data) 
{ 
    struct Node **pp = &head; 

    while (*pp) 
     pp = &(*pp)->next; 

    *pp = malloc(sizeof(**pp)); 
    (*pp)->data = data; 
    (*pp)->next = NULL; 

    return head; 
} 

발신자가 헤드 포인터의 주소를 처음으로 통과하도록 요구함으로써이 기능을 더욱 향상시킬 수 있습니다. 이것은 당신이 함수의 리턴 값을리스트의 헤드 포인터가 아닌 다른 것을 위해 사용할 수있게 해주는 장점을 더합니다. 예를 들어 후자의 경우 모두로 인해 값으로 단순히 주소 포인터를 이용하는 대신으로 가능하다

int res = ll_insertTail(&head, data); 

:

int ll_insertTail(struct Node **pp, int data) 
{ 
    while (*pp) 
     pp = &(*pp)->next; 

    if ((*pp = malloc(sizeof(**pp))) == NULL) 
    { 
     perror("Failed to allocate linked list node"); 
     return EXIT_FAILURE; 
    } 

    (*pp)->data = data; 
    (*pp)->next = NULL; 
    return EXIT_SUCCESS; 
} 

같이 호출. 간단한 열거를 위해 포인터 간 포인터 방식을 사용하는 것은 거의 의미가 없습니다. 그러나 특정 노드 또는 노드 내의 특정 위치를 검색해야 할 경우 및은 거기에있는 포인터 ( head 일 수 있음, 일부는 next 일 수 있음)를 사용하는 메커니즘을 유지하고 포인터를 포인터로 만들어야합니다 우아한 솔루션.

행운을 빈다.

Answer 2

첫 번째 코드 샘플에서 변수 node은 Node 구조체에 대한 포인터입니다. Node 구조체가 저장된 메모리 위치의 주소를 포함합니다.

두 번째 코드 샘플에서 변수 node은 Node 구조체에 대한 포인터에 대한 포인터입니다. Node 구조체가 저장된 메모리 위치의 주소를 포함하는 메모리 위치의 주소를 포함합니다.

두 코드 샘플에서 변수 이름이 동일하고 거의 동일하므로 다소 혼란 스럽습니다. Node입니다. 포인터의 의미가 명확 해 지도록 코드 샘플을 다시 작성해 보겠습니다.

첫번째 경우 :

Node* node_pointer = head; 

while (node_pointer != NULL) { 
    // node_pointer points to a Node 
    // do something to that Node, then advance to the next element in the list 
    // ... something ... 
    node_pointer = node_pointer->next; // advance 
} 

번째 경우 : 두 경우

Node** node_pointer_pointer = &head; 

while (*node_pointer_pointer != NULL) { 
    // node_pointer_pointer points to a pointer which points to a Node 
    // do something to that Node, then advance to the next element in the list 
    // ... something ... 
    node_pointer_pointer = &((*node_pointer_pointer)->next); // advance 
} 

는 가변 head는 Node 구조체에 대한 포인터이다.

node_pointer = head; 

그리고 두 번째 경우, & 운영자가 head의 메모리 위치를 가져 오는 데 사용됩니다 : A는 무엇

node_pointer_pointer = &head; 

를 그 값이 첫 번째 경우에 node_pointer에 직접 할당되는 이유 Node? 에 대한 포인터 인 struct (아마도 다른 것들과 함께) 필드 next이 있습니다. 첫 번째 코드 샘플에서는 next의 값을 node_pointer에 직접 할당 할 수 있지만 두 번째 코드 샘플에서는 & 연산자로 참조해야합니다.

두 번째 접근 방식이 유용한 이유는 무엇입니까? 이 예에서는 그렇지 않습니다. 연결된 목록의 요소를 반복하려는 경우 Node 구조체에 대한 포인터 만 있으면됩니다.

그러나 하위 포인터를 조작하려는 경우 포인터에 대한 포인터를 갖는 것이 유용합니다. 예를 들어 목록 탐색이 끝났다고 가정하고 이제 꼬리에 새 노드를 추가하려고합니다.

위의 첫 번째 경우에서 node_pointer은 그 값이 NULL이기 때문에 도움이되지 않습니다. 더 이상 아무것도 할 수 없습니다.

두 번째 경우 *node_pointer_pointer의 값이 NULL 인 동안 node_pointer_pointer의 값은 아닙니다. 목록의 마지막 노드에있는 next 필드의 주소입니다.따라서, 우리는 next에 새 Node 구조체의 주소를 할당 할 수

*node_pointer_pointer = make_new_node(); // make_new_node() returns a pointer 

참고 별표, 또는 역 참조 연산자를 *node_pointer_pointer에. node_pointer_pointer을 참조하면 next 포인터가 생성되고 새로운 Node 구조체의 주소를 할당 할 수 있습니다.

또한이 할당은 node_pointer_pointer이 빈 목록의 헤드를 가리키는 경우 작동합니다. 이를 역 참조하면 head이되고 새로운 Node 구조체의 주소를 할당 할 수 있습니다.