포인터를 사용하여 이중 연결된 목록에서 2 노드를 변경하는 방법은 무엇입니까? C

Question

문제는 다음과 같이 나타납니다. 노드를 변경하여 이중 연결 목록을 정렬해야합니다 (그 안에있는 값이 아님). (A 1, B 2, C 3) :

struct DataNode { 
    char* name; 
    int number; 
}; 

struct QSNode { 
    DataNode* data; 
    QSNode* prev; 
    QSNode* next; 
}; 

내가 3 개 데이터 노드를 만듭니다 그래서, 나는이 목록을 가지고 말할 수 있습니다.

이제 C 1과 A 3을 교환하면되므로 (C 3, B 2, A 1)이 값은 변경되지 않지만 실제 노드는 변경되지 않습니다. 지금, 나는 행한이 기능을 사용하여 :

QSNode* interchangeNodes(QSNode* list, QSNode* first, QSNode* second) { 
    QSNode* mark1 = first; 
    QSNode* mark2 = second; 

    first->next = second->next; 
    second->next = first; 
    first->prev->next = second; 
    second->prev = first->prev; 
    second->next->prev = first; 
    first->prev = second; 
    QSNode* mark3 = second; 
     second = first; 
     first = mark3; 


    if (mark1 == list) 
     return first; 
    else 
    if (mark2 == list) 
     return second; 
    else 
    if (mark2 == list->prev){ 
     list->prev = second; 
     return list; 
    } 
    else 
     return list;  
} 

왜이 모양을? 왜냐하면 노드를 변경하더라도 : C 3, B 2, A 1, 나는 C 3을 내 머리글로 사용하기를 원합니다. 따라서 목록에서 미리보기 기능을 호출하면 C 3이 먼저 표시됩니다.

void previewList(QSNode* list) { 

    QSNode* marker = list; 
    while (list->next != marker) { 
     cout << "Name: " << list->data->name << " Number: " << list->data->number << endl; 
     list = list->next; 
    } 
    cout << "Name: " << list->data->name << " Number: " << list->data->number << endl; 
} 

이제는 문제입니다. 정렬하려고 할 때 (요점은 목록을 없애고 배열을 바꾸지 않고 노드의 포인터를 변경하는 것이 아닙니다.)

좋아, 문제는 너무 많은 옵션을 시도했기 때문에 복잡하지 않습니다. 이 시점에서 Bubble 정렬이 작동 할 수 있습니다. 문제는 여기에 있습니다 :

QSNode* sortFinale1(QSNode* list){ 
    int count = 1; 
    QSNode * tmp = list; 
    while (tmp->next != list) { 
     if (tmp->data->number > tmp->next->data->number){ 
      list = interchangeNodes(list, tmp, tmp->next); 
     } 
     tmp = tmp->next; 
    } 
    return list; 
} 

참고 :이 기능은 하나 개의 노드가 하나의 반복 이후에 지적되지 않는다는 것을 보여주기 위해, 단지 테스트입니다.

내 목록이 동일하게 유지되고 배열처럼 동작하도록 tmp를 만들려고합니다. 하지만 문제는 내가 연결을 끊는 것입니다. 입력 :

Name4 3 
Name3 4 
Name2 1 
Name1 2 

미리보기 목록 출력 & & 전화 sortFinale1 함수 :

내 생각은 내가 놓친 거지 뭔가 : 교류와

출력 that sortFinale1에서 조건. 교환 및 정렬 (정렬 병합) :

Answer 1

여기

가 포함 C.

에서 문제의 빠른 구현입니다.

은 도움이 :) 희망

#include <stdlib.h> 
#include <stdio.h> 

typedef struct  DataNode { 
    char*   name; 
    int    number; 
}     DataNode; 

typedef struct  QSNode { 
    DataNode*  data; 
    struct QSNode* prev; 
    struct QSNode* next; 
}     QSNode; 

void   node_swap(QSNode **head, QSNode *first, QSNode *second) 
{ 
    QSNode *tmp; 

    if (first->next != NULL) 
     first->next->prev = second; 
    if (first->prev != NULL) 
     first->prev->next = second; 

    if (second->next != NULL) 
     second->next->prev = first; 
    if (second->prev != NULL) 
     second->prev->next = first; 
    tmp = first->next; 
    first->next = second->next; 
    second->next = tmp; 

    tmp = first->prev; 
    first->prev = second->prev; 
    second->prev = tmp; 
    if (first == *head) 
     *head = second; 
} 

DataNode  *new_data(char *name, int nr) 
{ 
    DataNode *result; 

    result = (DataNode*)malloc(sizeof(DataNode)); 
    result->name = name; 
    result->number = nr; 
    return (result); 
} 

QSNode   *new_node(DataNode *data) 
{ 
    QSNode *result; 

    result = (QSNode*)malloc(sizeof(QSNode)); 
    result->next = NULL; 
    result->prev = NULL; 
    result->data = data; 
    return (result); 
} 

void   add_node(QSNode **head, QSNode *new_node, QSNode *prev) 
{ 
    if (*head == NULL) 
    { 
     *head = new_node; 
     new_node->prev = prev; 
    } 
    else 
     add_node(&((*head)->next), new_node, *head); 
} 

void   print_list(QSNode *head) 
{ 
    if (head) 
    { 
     printf("%d\n", head->data->number); 
     if (head->prev) 
      printf("\tprev: %d\n", head->prev->data->number); 
     else 
      printf("\tprev: NULL\n"); 
     printf("\n"); 
     print_list(head->next); 
    } 
} 

/* 
** Merge sort 
*/ 

static void  arrange_prev_vals(QSNode *head, QSNode *prev) 
{ 
    if (head != NULL) 
    { 
     head->prev = prev; 
     arrange_prev_vals(head->next, head); 
    } 
} 

static void  front_back_split(
        QSNode *source, 
        QSNode **front_ref, 
        QSNode **back_ref) 
{ 
    QSNode *fast; 
    QSNode *slow; 

    if (source == NULL || source->next == NULL) 
    { 
     *front_ref = source; 
     *back_ref = NULL; 
    } 
    else 
    { 
     slow = source; 
     fast = source->next; 
     while (fast != NULL) 
     { 
      fast = fast->next; 
      if (fast != NULL) 
      { 
       slow = slow->next; 
       fast = fast->next; 
      } 
     } 
     *front_ref = source; 
     *back_ref = slow->next; 
     slow->next = NULL; 
    } 
} 

static QSNode *sorted_merge(QSNode *a, QSNode *b, int (*cmp)(DataNode*, DataNode*)) 
{ 
    QSNode *result; 

    if (a == NULL) 
     return (b); 
    else if (b == NULL) 
     return (a); 
    if (cmp(a->data, b->data) > 0) 
    { 
     result = a; 
     result->next = sorted_merge(a->next, b, cmp); 
    } 
    else 
    { 
     result = b; 
     result->next = sorted_merge(a, b->next, cmp); 
    } 
    return (result); 
} 

void   ft_lst_merge_sort(QSNode **head_ref, int (*cmp)(DataNode*, DataNode*)) 
{ 
    QSNode *head; 
    QSNode *a; 
    QSNode *b; 

    head = *head_ref; 
    if (head == NULL || head->next == NULL) 
     return ; 
    front_back_split(head, &a, &b); 
    ft_lst_merge_sort(&a, cmp); 
    ft_lst_merge_sort(&b, cmp); 
    *head_ref = sorted_merge(a, b, cmp); 
    arrange_prev_vals(*head_ref, NULL); 
} 

/* 
** A function used to compare nodes 
*/ 

int  cmp_numbers(DataNode *data1, DataNode *data2) 
{ 
    return (data2->number - data1->number); 
} 

int  cmp_rev_numbers(DataNode *data1, DataNode *data2) 
{ 
    return (data1->number - data2->number); 
} 


int  main() 
{ 
    QSNode *head; 
    QSNode *swap1; 
    QSNode *swap2; 

    head = NULL; 
    add_node(&head, new_node(new_data("1", 1)), NULL); 
    add_node(&head, new_node(new_data("2", 2)), NULL); 
    add_node(&head, new_node(new_data("3", 3)), NULL); 
    add_node(&head, new_node(new_data("4", 4)), NULL); 
    add_node(&head, new_node(new_data("5", 5)), NULL); 

    /* 
    ** Swap demonstration 
    */ 

    swap1 = head;       //node 1 
    swap2 = head->next->next->next->next; //node 5 

    printf("Swaping: %d with %d\n", swap1->data->number, swap2->data->number); 
    node_swap(&head, swap1, swap2); 
    print_list(head); 

    /* 
    ** Sort demonstration 
    */ 

    printf("Sorting ascending:\n"); 
    ft_lst_merge_sort(&head, &cmp_numbers); 

    print_list(head); 
    printf("Sorting descending:\n"); 
    ft_lst_merge_sort(&head, &cmp_rev_numbers); 

    print_list(head); 
} 

결과 :

Swaping: 1 with 5 
5 
    prev: NULL 

2 
    prev: 5 

3 
    prev: 2 

4 
    prev: 3 

1 
    prev: 4 

Sorting ascending: 
1 
    prev: NULL 

2 
    prev: 1 

3 
    prev: 2 

4 
    prev: 3 

5 
    prev: 4 

Sorting descending: 
5 
    prev: NULL 

4 
    prev: 5 

3 
    prev: 4 

2 
    prev: 3 

1 
    prev: 2 

Answer 2

(영업 이익 대신에 게시 됨).

문제는 교환 기능에 있습니다.

올바른 기능 : 연결리스트에서

QSNode* test123(QSNode* list, QSNode* first, QSNode* second) { 
QSNode* mark1 = first; 
QSNode* mark2 = second; 
first->prev->next = second; 
second->next->prev = first; 

first->next = second->next; 
second->next = first; 
second->prev = first->prev; 
first->prev = second; 

if (mark1 == list) 
    return second; 
else 
if (mark2 == list) 
    return first; 
else 
    return list; 

}