이중 연결 목록의 중간에 새 노드를 삽입하려고 할 때 잘못 연결 했습니까? <pre><code>class DList{ private: struct Elem { Elem *prev, *next; }; Elem *_head, *_tail; } </code></pre> <p></p>가 지금은 기존의 두 노드를 가지고 :

Question

구조 속에서 다음> CUR과의 Cur, 그리고 그들 사이에 새로운 노드 인을 삽입 싶어요. 내가 한 일은 다음과 같습니다.

cur->next = ins;//step-1-1 cur 
    ins->prev = cur;//step-1-2 cur 

    ins->next = cur->next;//step-2-1 cur->next 
    cur->next->prev = ins;//step-2-2 cur->next 

문제점은 더 이상 내 프로그램의 트래버스 루프가 _tail에 더 이상 도달 할 수 없다는 것입니다. 내 삽입 부분에서 뭔가를 mishook 했습니까? (위의 중간 코드에서 삽입을 주석하면 루프가 완벽하게 작동합니다.)

Answer 1

네는 여기에 오 배선이있다. 사진을 그려 봅시다!

상상 일이 처음과 같이 우리가 더 이상 원래 있던 요소에 대한 포인터가없는

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
          +----------+ 
          | next | 
          +----------+ 
          | prev | 
          +----------+ 
           ^
           | 
           ins 

주의 사항 :

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | ----------------------> | next | --> ... 
     +----------+       +----------+ 
... <-- | prev | <---------------------- | prev | <-- ... 
     +----------+       +----------+ 
          +----------+ 
          | next | 
          +----------+ 
          | prev | 
          +----------+ 
           ^
           | 
           ins 

먼저, 당신은이 작업을 수행 cur->next = ins;을 실행 curr 이후 - 죄송합니다. 그것은 나중에 문제가 될 것입니다.

이제, 우리는 다음과 같이 보이는, ins->prev = curr;을 수행

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
      ^   +----------+ 
       |   | next | 
       |   +----------+ 
       +---------- | prev | 
          +----------+ 
           ^
           | 
           ins 

지금, 우리는 ins->next = curr->next; 물품. 그러나 웁스! ins 해당 curr->next 점을 주목, 그래서 우리는 여기에 사이클을 추가 :

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
      ^   +----------+ 
       |   | next | --+ 
       |   +----------+ | 
       +---------- | prev | <-+ 
          +----------+ 
           ^
           | 
           ins 

을 그리고 마지막으로, 당신은 그러나 죄송합니다 cur->next->prev = ins; 쓰기!

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
          +----------+ 
         +-> | next | --+ 
         | +----------+ | 
         +-- | prev | <-+ 
          +----------+ 
           ^
           | 
           ins 

여기서 문제는 당신이 바로 그 장소에서 볼 수있는 능력을 잃게 있도록, 처음 할당 한 후 curr->next에 의해 지적했다 셀의 트랙을 잃을 것입니다 : curr->next은 여전히 ​​prev, 그래서 우리는 또 다른주기를 얻는다.

이렇게 작성하면 어떻게됩니까?

DList* next = curr->next; 

후 다음 상황 중 일부에 next 대신 curr->next을 사용할 수 있습니까?

Answer 2

키는 나중에 사용할 값을 잃지 않습니다. 첫 번째 코드 줄 cur->next = ins;은 원래 값을 잃게합니다 (cur->next); 그 후에 당신은 누가 next에서 ins이 될지 정말로 모릅니다.

중간에 새 노드를 삽입하려면이 논리를 사용하십시오. 처음

cur - cur->next 
    | 
    [ins] 

수행

ins->next = cur->next; 

(현재) (인)를 말할 수 - (Cur 코드> 다음) 는 {가정 - 다음에, 그리고 = 다음 및 이전을위한}

cur->next = ins; 

(현재) - (인) - (Cur 코드> 다음)

ins->prev = cur; 

CUR = 인 - (Cur 코드> 다음)

ins->next->prev = ins; 

CUR = 기능 = (Cur 코드> 다음)