如何使用指針更改雙鏈表中的2個節點？ C

Question

問題就像這樣：我必須通過更改節點（不是其中的值）來對雙鏈表進行排序。 所以，可以說我有此列表：

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

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

我創建具有數據3個節點：（A 1，B 2，C 3）。

現在，我想要做的是與C 3交換A 1，所以它看起來像這樣（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; 
} 

好的，現在的問題。當我嘗試對它進行排序（重點不是要銷燬列表並重新排列它，而是要更改節點的指針）。

好的，問題是我嘗試了很多選項，我不在乎複雜性在這一點上，所以泡泡排序可以工作。問題就在這裏：

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功能：

我的猜測是，我失去了一些東西：

與交流輸出在那種結局1條件。

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

（發佈代表OP）的。

問題出在交換功能。

正常工作：

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; 

}