C++ LinkedList의 교환 노드

-1

가능한 중복 : 나는 C++에서 단독 LinkedList의 두 노드를 교환 할 수있는 알고리즘을 쓰기 위해 노력하고있어
debug help - swap 2 nodes of double link list C++ LinkedList의 교환 노드

. 여기에 지금까지이 작업은 다음과 같습니다

void swap(ListNode *node1, ListNode *node2) 
{ 
    ListNode *prev1 = head; 
    ListNode *prev2 = head; 

    //Search previous node for node1: 
    while(prev1->next!=node1 || prev1 != node1) 
     prev1 = prev1->getNext(); 

    //Search previous node for node2: 
    while(prev2->next!=node2 || prev2 != node2) 
     prev2 = prev2->getNext(); 


    if(node1->next==node2) 
    { //This means node1 == prev2? 
     tail = node1; 
     node1->next = NULL; 
     head = node2; 
     node2->next = node1; 
    } 
    else if(node2->next==node1) 
    { // node2 == prev1 
     tail = node2; 
     node2->next = NULL; 
     head = node1; 
     node1->next = node2; 
    } 
    if(node1->next == NULL) 
    { //node1 is last 
     node1->next = node2->next; 
     tail = node2; 
     node2->next = NULL; 
     prev1->next = node2; 
     prev2->next = node1; 
    } 
}

하지만 LL은 두 가지 요소가 있다면처럼 내가 얻을 수있는 다양한 경우의 수를 실현하거나, 노드 1, 등 등 내가 전에 우리에게 노드 2를 준 경우 이것이 복잡하고 추악 할 수 없다는 것을 깨달았습니다. 그렇다면 두 노드를 서로 바꾸는 알고리즘을 어떻게 작성합니까?

출처

2012-03-04 Richard

* 특정 *이 질문이 무엇입니까? –

스택 오버플로 (웹 포럼이나 게시판이 아님)에 "몇 가지 팁"을 제공하지 않습니다. 우리는 프로그래밍 언어에 관한 구체적인 질문에 답합니다. –

"연결된 목록에서 두 노드를 어떻게 바꿔 넣을 수 있습니까?"라는 질문은 꽤 합리적이고 구체적인 질문입니다. – tenfour

하나의 루틴에서 전체 작업을 잘못 수행했습니다. 두 가지 간단한 문제로 분해하십시오.

1) 모든 특수한 경우를 포함하여 목록에서 노드를 제거하십시오. 2) 모든 특수한 경우를 포함하여 목록에 노드를 삽입하십시오.

여기에서 전체적인 문제는 쉽지만 분명히 숙제이기 때문에 스스로 해결할 수 있습니다.

출처

2012-03-04 16:20:03 stark

-1

#include <stdio.h> 

struct llist { 
     struct llist *next; 
     char *payload; 
     } llists[]= 
{{ llists+1, "one"} 
,{ llists+2, "two"} 
,{ llists+3, "three"} 
,{ llists+4, "four"} 
,{ llists+5, "five"} 
,{ llists+6, "six"} 
,{ llists+7, "seven"} 
,{ llists+8, "eight"} 
,{ llists+9, "nine"} 
,{ NULL, "ten"} 
}; 

struct llist *head = llists; 

void llistswap(struct llist *one, struct llist * two) 
{ 
struct llist **hnd, **h1, **h2; 

h1 = h2 = NULL; 

for (hnd= &head; *hnd; hnd = &(*hnd)->next) { 
    struct llist *tmp; 
    if ((*hnd) == one) h1 = hnd; 
    else if ((*hnd) == two) h2 = hnd; 
    else continue; 
    if (!h1 || !h2) continue; 

    tmp = *h1; 
    *h1 = *h2; 
    *h2 = tmp; 

    tmp = (*h1)->next; 
    (*h1)->next = (*h2)->next; 
    (*h2)->next = tmp; 
    break; 
    } 
} 

void do_print(struct llist *lp) 
{ 
for (; lp; lp = lp->next) { 
    printf("%s%c", lp->payload, (lp->next) ?',' : '\n'); 
    } 
} 

int main(void) 
{ 
do_print (head); 
llistswap (llists+4, llists+7); 
do_print (head); 

return 0; 
}

출처

2012-03-04 16:21:05 wildplasser

OP는 단일이 아닌 이중 연결 목록에 대해 묻습니다. 그리고이 코드는 설명이 전혀 필요 없다고 자명 할만큼 충분하지 않습니다. – tenfour

글쎄, 그건 어쨌든 숙제인데, 백 포인터에 업데이트를 추가하는 것은 (우리가 진행하는 동안) 사소한 것처럼 보인다. – wildplasser

BTW : 제목과 질문 모두 이중 링크 목록이나 -> 이전 포인터를 언급하지 않습니다. (prev [12]라고 불리는 변수가 있지만 이것들은 또 다른 목적을 가지고있는 것처럼 보입니다) – wildplasser

이 나에게 청소기 보인다

//Maybe this function should go instide ListNode itself... 

ListNode *prev(ListNode *node) { 

    if (node == head) 
     return null; 

    ListNode *search = head; 

    while (search != node) 
     search = search->getNext(); 

    return search; 
} 

void swap(ListNode *node1, ListNode *node2) 
{ 
    ListNode *prev1 = prev(node1), 
      *prev2 = prev(node2), 
      *next1 = node1->getNext(), 
      *next2 = node2->getNext(); 

    if (prev1) 
     prev1->next = node2; 
    else 
     head = node2; 

    if (prev2) 
     prev2->next = node1; 
    else 
     head = node1; 

    if (!next1) 
     tail = node2; 
    else if (!next2) 
     tail = node1; 

    node1->next = next2; 
    node2->next = next1; 
}

이 OFC를 테스트하지 않았습니다 ...

출처

2012-03-04 16:32:54

C++ LinkedList의 교환 노드

답변

관련 문제