오름차순으로 연결된 목록을 만드는 방법

Question

"머리"라는 희소 배열이 주어졌습니다.이 배열은 색인과 값을 갖는 2 차원입니다. 그래서 같은 것을 : I은 오름차순이 희소 배열에 노드 (값, 인덱스)를 삽입 할 (3, 100) (6200) (8100)

1. . 내가 (2100)을 받았을 경우에는, 목록이 같아야합니다 그래서 : 내가 받았을 경우에는 마찬가지로 (2, 100) (4,200) (8,100)

을 (6200)를 (3100)를, 그것은 ( 를 반환해야 3,100) (4,200) (6,200) (8,100)

조건 1 : 인덱스가 동일한 경우, 그때는 값 I가 주어하고 그래서 경우

(3,100을 추가해야합니다), 그때 를 반환해야합니다 (3,200) (6,200) (8,100)

조건 2 : 인덱스가 같고 값이 0이면 값을 제거해야합니다. 배열 (3, -100) 인 경우 그래서, 난

(6200)를 반환해야합니다 (8100)

Node * List_insert_ascend(Node * head, int value, int index) 
{ 
    Node * node = List_create(value, index); //this creates an empty node, "node" 

    if (index < (head->index)) //node's index is less, e.g. (1,100) 
    {node -> next = head;} //this inserts "node" before "head" 
    if (index == (head->index)) 
    { 
    node = head; 
    head->value = head->value + value; //Condition 1 
    while ((head->value)==0) //Condition 2 
    { 
     Node *p = head->next; 
     head = p; 

    } 
    } 
    return node; 

} 

나의 이해는 내가 할 때 머리 -> 새로운 머리 옆, 즉 가야한다는 것입니다 원래 항목을 제거합니다.

그러나 값이 0 인 색인은 계속 목록에 남아 있습니다. 누군가가 내가 정말 감사하겠습니다 내가 잘못하고 (그리고 아마도 그 이유)하고있는 무슨을 파악 좀 도와 수 있다면 결과는 (3,0) (6,200) (8,100)

입니다.

Answer 1

반환 헤드에 의해 또는 노드에 의해 새로운 머리 중 하나를 반환해야 함수 ** 매개 변수로 머리

및

머리 -> 모든

Node * list_insert_update_remove(Node **head, int value, int index) 
{ 
    Node *node = List_create(...); 
    if (*head == NULL) 
    *head = node; 
    else { 
    Node *prev = NULL; 
    Node *list = head; 
    while (list) { 
     if (index < list->index) { //prepend 
     if (prev == NULL) // before head 
      *head = node; 
     else { 
      prev->next = node; // into the middle/end 
      node->next = list; 
     } 
     break; 
     } else if (index == list->index) { 
     //update or remove (execercise) 
     break; 
     } else if (list->next == NULL) { // append at end 
     list->next = node; 
     break; 
     } 
     prev = list; 
     list = list->next; 
    } 
    } 

    return *head; 
} 

에서 더 머리가없는 IFF에 지수는 충돌입니다

Answer 2

코드에 정의되지 않은 동작이 있습니다. 당신이

Node *p = head->next; 
head = p; 
free(p); 

을 수행 할 때

실제로 모두head 및 p 점에 노드를 확보하고 있습니다. 그런 다음 head을 역 참조하면 정의되지 않은 동작이 발생합니다.

하지만 그게 유일한 문제는 아닙니다. 다른 하나는 해제하려는 노드를 실제로 연결 해제하지 않는다는 것입니다. 이전 head->next (head의 재 할당 및 후속 해제 전) 포인터는 여전히 현재 사용 가능한 노드를 가리 킵니다.