Hoán đổi các nút trên một danh sách liên kết duy nhất

Question

Tôi đang cố gắng tạo một hàm swapNode có thể lấy bất kỳ hai nút nào và hoán đổi chúng. Tôi đã thực hiện một thuật toán hoạt động nếu chúng cách ít nhất 2 nút, nhưng tôi dường như không thể tìm ra thuật toán sẽ hoạt động nếu chúng gần nhau hơn.

Đây là những gì tôi đã viết cho đến nay:

void swapNode(call * &head, call * &first, call * &second){ 
    call * firstPrev = NULL; 
    call * secPrev = NULL; 
    call * current = head; 

    //set previous for first 
    while((current->next != first)){ 
     current = current->next; 
    } 

    firstPrev = current; 
    current = head; 

    //set previous for second 
    while((current->next != second)){ 
     current = current->next; 
    } 

    secPrev = current; 
    current = second->next; 

    //set firstPrev-> next to second 
    firstPrev->next = second; 
    //set secPrev->next to first 
    secPrev->next = first; 
    //set second->next = first->next 
    second->next = first->next; 
    //set first->next to current 
    first->next = current; 

    current = head; 
    while(current->next != NULL){ 
     cout << current->number << endl; 
     current = current->next; 
    } 

    cout << current->number << endl; 
} 

EDIT: bây giờ tôi có điều này như một phần trao đổi của tôi, nhưng nó vẫn có vẻ không hoạt động chính xác

//swap firstPrev-> next with second->next 
tmp = firstPrev->next; 
second->next = firstPrev->next; 
second->next = tmp; 
//swap swap first->next with second->next 
tmp = first->next; 
second->next = first->next; 
second->next = tmp; 

EDIT2: Điều này dường như không làm việc, hoặc, tôi nhận được một lỗi seg.

//swap previous's->next 
    tmp =firstPrev->next; 
    secPrev->next = firstPrev->next; 
    secPrev->next = tmp; 
    //swap swap first->next with second->next 
    tmp = first->next; 
    second->next = first->next; 
second->next = tmp; 

Answer 1

Giả sử chúng ta có:

Node1 -> Node2 -> Node3 -> Node4 -> Node5 

Để trao đổi hai nút, bạn cần phải trao đổi các next giá trị của những người trước mỗi trong số họ, và cũng là next giá trị của các nút bạn muốn trao đổi .

Vì vậy, để trao đổi, giả sử, Node2 và Node3, bạn có hiệu quả phải hoán đổi Node1->next với Node2->next và Node2->next với Node3->next. Điều đó sẽ hoạt động, ngay cả khi chúng nằm ngay cạnh nhau (hoặc thậm chí nếu nó là cùng một nút). Ví dụ:

Swap Node1->next và Node2->next

Node1->next = Node3 
Node2->next = Node2 

Swap Node2->next với Node3->next

Node2->next = Node4 
Node3->next = Node2 

này đi ra như:

Node1 -> Node3 -> Node2 -> Node4 -> Node5 

hoán đổi!

Như đã lưu ý trong phần nhận xét, nếu hoán đổi Node1 với bất kỳ thứ gì, bạn sẽ phải đặt một đầu mới cho danh sách được liên kết.

---

Để đối phó với các chỉnh sửa của câu hỏi:

Mã của bạn để bơm nạp tiếp gần đúng. Tuy nhiên, bạn cần trao đổi firstPrev bằng secPrev. Nó chỉ xảy ra trong ví dụ của tôi rằng chúng tôi đã trao đổi một trong các giá trị của các nút next hai lần, bởi vì chúng nằm cạnh nhau. Nhưng một cách hợp lý, chúng tôi muốn hoán đổi các next s của hai cái trước đó và sau đó hoán đổi next s của các nút thực tế. Hãy thử điều này:

//swap firstPrev-> next with secPrev->next 
tmp = firstPrev->next; 
secPrev->next = firstPrev->next; 
secPrev->next = tmp; 
//swap swap first->next with second->next 
tmp = first->next; 
second->next = first->next; 
second->next = tmp; 

Nếu bạn nhận được một segfault, hãy kiểm tra biến tmp - nó có thể là lỗi phân bổ hoặc xóa ở đâu đó. Nơi nào bạn nhận được segfault?

Answer 2

Trong hầu hết các tình huống thực tế cuộc sống, trao đổi các giá trị sẽ là giải pháp tốt nhất:

void swapNode(call * &head, call * &first, call * &second) { 
    // swap values, assuming the payload is an int: 
    int tempValue = first->value; 
    first->value = second->value; 
    second->value = tempValue; 
} 

Nếu đó là không được phép, sau đó bạn muốn làm một hoán đổi tương tự kiểu trên -> tiếp theo thay vì -> thành phần giá trị. Và sau đó thực hiện một hoán đổi khác trên thành phần tiếp theo đầu tiên-> next và secondPrev->. Xem ra cho trường hợp đặc biệt, nơi đầu tiên hoặc thứ hai == đầu.

Answer 3

Mặc dù tôi không chắc chắn 100% câu trả lời sẽ liên quan đến tham chiếu tới con trỏ nút (hoặc con trỏ trỏ đến con trỏ) và điều này sẽ xử lý trường hợp khi một trong các nút cũng là đầu danh sách.

void swapNodes(node *&first, node *&second) 
{ 
    node *t = second->next; 
    second->next = first->next; 
    first->next = t; 
    t = second; 
    second = first; 
    first = t; 
} 

Sau đó, bạn có thể gọi nó là ví dụ:

swapNodes(head, secPrev->next); 

hoặc

swapNodes(firstPrev->next, head); 

hoặc

swapNodes(firstPrev->next, secPrev->next) 

và nó cũng làm việc cách tự động.

EDIT:

swapNodes có thể còn dễ đọc hơn:

void swapNodes(node *&first, node *&second) 
{ 
    std::swap(first->next, second->next); 
    std::swap(first, second); 
} 

Answer 4

Rule of thumb: "Luôn dữ liệu tách biệt với con trỏ và không bao giờ trao đổi con trỏ, chỉ có dữ liệu!". Thực hiện trao đổi rõ ràng mà không sử dụng memcpy(), do đó bạn có thể tránh các vấn đề liên kết. Nó không gây ra hình phạt về hiệu suất về độ phức tạp của thuật toán, nhưng làm cho mã của bạn dễ đọc và an toàn hơn.

Answer 5

Nếu bạn muốn biết tất cả các phương pháp trao đổi hai nút trong danh sách liên kết trong đơn giản C chỉ sau đó truy cập liên kết này:

http://sahilalipuria.wordpress.com/2013/01/21/swapping-two-nodes-of-a-singly-linked-lists-set-2/

Answer 6

void swap() 
{ 
struct node *temp=0,*nxt,*ptr; 
ptr=head; 
int count=0; 
while(ptr) 
{ 
    nxt=ptr->link; 
    if(nxt) 
{ 
    if(count==0) 
    head=nxt; 
    count++; 
    ptr->link=nxt->link; 
    nxt->link=ptr; 
    if(temp!=NULL) 
    temp->link=nxt; 
    temp=ptr; 
    if(ptr->link==NULL) 
    break; 
    ptr=nxt->link->link; 
} 

} }

Answer 7

Đây p1 là nút thứ nhất được swaped, p2 là nút thứ hai được swaped. Và prevnode là nút đó là trước đây của p2

 temp=head; 
     while(temp!=NULL){ 
     if(temp->link==p1){ 
      temp->link=p2; 

      prevnode->link=p2->link; 
      p2->link=p1->link; 
      t=p1->link; 
      while(t!=prevnode) 
       t=t->link; 
       cout<<" YES"; 
      cout<<"["<<t->num<<"] "; 
      p1->link=prevnode->link; 
      prevnode->link=p1; 

      temp=p1; 
     }//if_ 

     cout<<" "<<temp->num;    
     temp=temp->link; 
    } 

Answer 8

Bạn sẽ phải cũng để trao đổi các thành phần next của nút trước đó, nếu không thì danh sách liên kết sẽ không vẫn liên kết với nhau. Lưu ý rằng cấu trúc của tôi được gọi là node.

int swapNode(node *&head * &first, node * &second) 
{ 
    //first we will declare the 
    //previous of the swapping nodes 
    node *firstprev=NULL; 
    node*secprev=NULL; 
    node*current=head; 
    //set previous first 
    while(current->next!=first) 
    { 
     current=current->next; 
    } 
    firstprev=current; 
    //seting 2nd previous 
    while(current->next!=second) 
    { 
     current=current->next; 
    } 

    // swap values, assuming the payload is an int: 
    int tempValue = first->value; 
    first->value = second->value; 
    second->value = tempValue; 
    //swaping next of the nodes 
    firstprev->next=second; 
    secprev->next=first; 
    return; 
} 

Answer 9

Cảm ơn mọi người đã trả lời! Tôi nhận ra rằng câu hỏi này đã được hỏi gần hai năm trước và một câu trả lời từ lâu đã được chấp nhận, nhưng tôi đã có một chút bối rối bởi câu trả lời. Vì vậy, mặc dù người hỏi có lẽ không quan tâm đến câu trả lời mới, tôi muốn thêm phiên bản của tôi, trong trường hợp các độc giả khác cũng bối rối và ghi lại cách tiếp cận của riêng tôi. Một số điều này có thể phù hợp hơn với ý kiến, nhưng tôi chưa có tiếng để bình luận.

Đầu tiên, cho dù tôi thường xuyên xem nó như thế nào - trên bảng trắng hoặc trong trình gỡ lỗi - dường như tôi không thể tránh kết thúc bằng một vòng lặp trong nút đầu tiên, tức làchỉ vào chính nó, nếu tôi không sử dụng điều kiện để phân biệt giữa các trường hợp các nút nằm liền kề và không, ngay cả với các bước trừu tượng hoặc mã bê tông từ câu trả lời hiện tại được chấp nhận bởi Smashery. Tôi đã nhìn xung quanh một chút trên Internet để tìm mã theo phong cách của câu trả lời được chấp nhận hiện nay để tránh điều kiện như vậy, nhưng với tôi thì thật khó để tránh và các tìm kiếm của tôi không được giải quyết như vậy (trừ khi tôi sai về đề xuất có thể không chính xác). Nếu có một số biểu thức thông minh sẽ sinh ra địa chỉ của nút đầu tiên khi chúng liền kề và địa chỉ của người kế thừa nút đầu tiên khi chúng không, thì điều kiện đó sẽ không cần thiết, bởi vì tìm ra người thừa kế mới của nút thứ hai là những gì (dường như) cần thiết có điều kiện.

Thứ hai, tôi có cùng câu hỏi về các bài tập liên tiếp cho cùng một biến trong câu trả lời được chấp nhận với tư cách là người bình luận khác. Tôi hy vọng tôi không cực kỳ dày đặc ở đây, nhưng gán các giá trị khác nhau cho cùng một chuỗi theo thứ tự, trừ khi có lẽ trong trường hợp tác dụng phụ, với tôi dường như không bao giờ để biến với bất kỳ giá trị nào khác. những gì cấu hình của các nút tôi xem xét, và do đó làm cho các bài tập trước đó dường như dư thừa. Nếu tôi sai về điều đó và cách tiếp cận đó sẽ giải quyết vấn đề này thì tôi đã có thể loại bỏ điều kiện cuối cùng trong đoạn mã dưới đây, điều mà tôi đang cố gắng loại bỏ khi lần đầu tiên tôi nhìn vào Internet để tìm giải pháp trao đổi các nút mà không cần các nút lân cận đặc biệt. Tôi không hoàn toàn chắc chắn, nhưng có vẻ như Smashery đã cố tình để lại những bài tập lặp đi lặp lại đó ra khỏi sự nghiêm khắc hợp lý và minh họa tốt hơn quy trình - tôi có thể đã hiểu lầm. Thứ ba, trên trang này và các trang web khác, tôi thường thấy câu trả lời từ các câu trả lời khác lặp đi lặp lại rằng tốt hơn là trao đổi nội dung của các nút, chứ không phải là con trỏ. Tất nhiên, trong trường hợp các số nguyên đơn giản, như trong các ví dụ cho đến nay, điều đó dường như mang lại mã ngắn hơn, đơn giản hơn. Tuy nhiên, khi chúng ta thảo luận về các danh sách liên kết với các nút chứa các số nguyên, nó thường là một điểm tựa cho cấu trúc dữ liệu sao lưu của một thùng chứa phức tạp và chung chung hơn. Như vậy, tôi không nghĩ rằng việc trao đổi nội dung của các nút thực sự dễ dàng, ít nhất là nếu việc thực hiện cấu trúc dữ liệu không thể đưa ra các giả định về ngữ nghĩa sao chép của các mục của thùng chứa. Ngoài ra, có thể trao đổi xung quanh nội dung của các nút như vậy ngụ ý rằng danh sách được liên kết có quyền sở hữu nội dung của các nút đó, bởi vì nếu không mã bên ngoài phương thức của danh sách được liên kết có thể giữ tham chiếu đến đối tượng trong các nút đó. đột nhiên thay đổi bên dưới chúng.

Tôi thừa nhận, tuy nhiên, điều này có thể phụ thuộc vào ngữ nghĩa của vùng chứa. Đối với một mảng, một phương thức hoán đổi có thể được dự kiến ​​sẽ thay đổi giá trị bên dưới các tham chiếu đến một chỉ mục nhất định của mảng đó. Điều đó có nghĩa là các tham chiếu không có nghĩa là tham chiếu đến một đối tượng cụ thể, nhưng đến một vị trí trong một vùng chứa mà một người có thể lập chỉ mục. Nếu chúng ta xem xét một danh sách liên kết như một phương tiện để chỉ đặt một tập hợp các đối tượng, có sử dụng chúng bên ngoài danh sách liên kết, người dùng có thể mong đợi một hoạt động hoán đổi để chỉ trao đổi vị trí chứ không phải nội dung.

Hãy tưởng tượng, ví dụ: danh sách được liên kết thể hiện các đối tượng thuộc loại "ô tô". Mỗi chiếc xe có một chủ sở hữu và chủ sở hữu đó tham khảo xe của họ thông qua một con trỏ đến nó. Bây giờ giả sử danh sách liên kết đại diện cho thứ tự một tập hợp các chiếc xe được dự kiến ​​sẽ được phục vụ để kiểm tra tại một đại lý xe hơi. Nếu chúng ta hoán đổi nội dung của hai nút, để trao đổi lịch trình cho hai chiếc xe, và thực hiện nó bằng cách trao đổi nội dung của chúng, thì sự phục vụ trong thực tế sẽ xảy ra theo thứ tự mới, đúng - nhưng mọi người cũng sẽ bất ngờ sở hữu những chiếc xe khác nhau! (Tuy nhiên, tôi sẽ không đổi ý với một chiếc Tesla, vì tôi chỉ lái chiếc Corolla.)

Nếu danh sách được liên kết, như trong ví dụ của mảng, dựa trên ngữ nghĩa lập chỉ mục thì vị trí trong nút đơn giản có thể đại diện cho thứ tự mà trong đó những chiếc xe được tải lên một con tàu để vận chuyển. Tại thời điểm này, những chiếc xe không có bất kỳ chủ sở hữu nào và chúng tôi thực sự chỉ quan tâm đến vị trí của chúng. Sau đó, tôi cho rằng nó thực sự không gây tổn hại cho việc trao đổi xe, tức là nội dung của các đối tượng được các nút tham chiếu.

Cuối cùng là mã. Như tôi đã nói ở trên, tôi đã không thể tránh được vỏ bọc đặc biệt cho các nút liền kề.

Đầu tiên, định nghĩa về một phương pháp phụ trợ:

int find_node(int v, node* root, node** n, node** pn) { 
    int i = 0; 
    for (*n = root; *n != NULL && (*n)->v != v; ++i) { 
     *pn = *n; 
     *n = (*n)->next; 
    } 
    return i; 
} 

Phương pháp này tìm thấy một nút bởi giá trị của nó. Số nguyên được trả về là vị trí dựa trên số không (gọi nó là chỉ mục nếu bạn thích) của nút trong danh sách được liên kết. Tôi phát hiện thấy sự kề nhau thông qua vị trí, thay vì so sánh con trỏ, dễ đọc hơn. Bắt đầu danh sách là root. Phương thức thiết lập n để trỏ tới nút chứa giá trị đã truyền. Trong pn, phương thức lưu trữ tiền thân của n.

Sau đây là trao đổi thực tế:

void swap_nodes(node **root, int v1, int v2) { 
    if (v1 == v2) return; 

    node *n1, *n2, *pn1, *pn2; 

    int p1 = find_node(v1, *root, &n1, &pn1); 
    int p2 = find_node(v2, *root, &n2, &pn2); 

    if (p1 > p2) { 
     std::swap(n1, n2); 
     std::swap(pn1, pn2); 
     std::swap(p1, p2); 
    } 

    if (p1 == 0) *root = n2; 
    else pn1->next = n2; 

    node* nn1 = n1->next; 
    n1->next = n2->next; 

    if (p2 - p1 > 1) { 
     n2->next = nn1; 
     pn2->next = n1; 
    } else { 
     n2->next = n1; 
    } 
} 

Tôi xin lỗi mà tôi đã thay đổi chữ ký của phương pháp của OP một chút. Tôi thấy thuận tiện hơn khi truyền các giá trị của các nút để hoán đổi, trái ngược với các nút con trỏ. Nếu bạn chỉ chuyển các nút con trỏ đến các nút tương ứng, bạn sẽ phải thực hiện một traversal khác để tìm những người tiền nhiệm với giải pháp này, điều này cảm thấy hơi khó xử với tôi. Nếu chúng tôi không thể phân biệt các nút theo các giá trị này, ví dụ: các giá trị không phải là duy nhất, tuy nhiên, chúng tôi sẽ cần các con trỏ tới các nút.

Như với lời giải thích cho find_node ở trên, đầu tiên chúng tôi tìm vị trí, nút và tiền thân cho các giá trị nút được chuyển đến swap_nodes thông qua v1 và v2. Các giá trị cho các nút đầu tiên và thứ hai đều được hoán đổi nếu nút thứ hai hoán đổi xuất hiện trước nút đầu tiên. Nó không có nhiều mã để làm như vậy, làm giảm vỏ đặc biệt, và làm cho nó dễ dàng hơn một chút để hình dung.

Bây giờ, chúng tôi chỉ còn lại hai điều kiện nữa, không phải điều kiện nào cũng có tầm thường để tránh. Nếu nút đầu tiên ở đầu danh sách được liên kết, tức là ở vị trí 0, gốc cần phải trỏ đến nút thứ hai. Nếu không, người tiền nhiệm của nút đầu tiên sẽ trỏ đến nút thứ hai.

Giá trị trước đó của người kế thừa nút đầu tiên cần được ghi nhớ, trong trường hợp các nút không liền kề. Sau đó, người kế nhiệm của nút đầu tiên được đặt thành người kế thừa hiện tại của nút thứ hai. Đây là thay đổi duy nhất áp dụng cho tất cả các trường hợp: người kế thừa mới của nút đầu tiên là nút kế thừa cũ của nút thứ hai là sự chắc chắn duy nhất và hữu ích để bắt đầu với để nhớ các hoạt động của con trỏ và trình tự của chúng khi triển khai trao đổi này .

Cuối cùng, nếu vị trí của các nút khác nhau nhiều hơn một, chúng không liền kề. Sau đó, người kế nhiệm mới của nút thứ hai trở thành người kế thừa cũ của nút đầu tiên - được lưu ở trên - và nút tiền nhiệm của nút thứ hai bây giờ trỏ đến nút đầu tiên. Nếu chúng liền kề, không có nút giữa các nút cần trao đổi cần cập nhật, vì vậy chỉ cần liên kết nút thứ hai với nút đầu tiên là tất cả những gì còn lại để thực hiện.