冒泡排序链表

Question

我已经使用帮助器swapper()编写了一个排序函数。该函数将列表中的节点按其在内存中的地址按降序排序(最高地址到最低地址)。

只要列表的头不改变，函数就会排列得很好，但是当头发生变化时，返回的只是头和后面的任何东西。在某个地方，我失去了名单的其余部分，我无法弄清楚。

到目前为止我的职责是：

void swapper(NODE *left, NODE *right)
{
    if(left->prev)
        left->prev->next = right;
    if(right->next)
        right->next->prev = left;

    left->next = right->next;
    right->prev = left->prev;

    right->next = left;
    left->prev = right;
}
NODE *sort_nodes(NODE *head)
{
    NODE *new_second, *new_first, *list = head;
    int swaps;
    do{
        swaps = 0;
        while(list)
        {
            if(&(*list) < &(*(list->next)))
            {
                swapper(list, list->next);
                swaps = 1;
            }
            list = list->next;
        }
        list = head;
    }while(swaps);
    return list;
}

如果列表的头是列表中声明的第三个节点，则示例输出：

Unsorted: 0x93657050 -> 0x936570d0 -> 0x93657070 -> 0x93657090 -> 0x93657030 -> 0x936570b0 -> 0x93657010 -> NULL
Sorted:   0x93657050 -> 0x93657030 -> 0x93657010 -> NULL

Answer 1

当你想到这件事的时候就很简单。

你有

head -> A -> B

然后你交换A和B而不换头，所以你得到

head -|
      v
 B -> A

如果您交换head元素，则需要将head指针移动到新head。

Answer 2

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

/* structure for a node */
struct Node
{
    int data;
    struct Node *next;
};

/* Function to insert a node at the begining of a linked lsit */
void insertAtTheBegin(struct Node **start_ref, int data);

/* Function to bubble sort the given linked lsit */
void bubbleSort(struct Node *start);

/* Function to swap data of two nodes a and b*/
void swap(struct Node *a, struct Node *b);

/* Function to print nodes in a given linked list */
void printList(struct Node *start);

int main()
{
    int arr[] = {12, 56, 2, 11, 1, 90};
    int list_size, i;

    /* start with empty linked list */
    struct Node *start = NULL;

    /* Create linked list from the array arr[].
      Created linked list will be 1->11->2->56->12 */
    for (i = 0; i< 6; i++)
        insertAtTheBegin(&start, arr[i]);

    /* print list before sorting */
    printf("\n Linked list before sorting ");
    printList(start);

    /* sort the linked list */
    bubbleSort(start);

    /* print list after sorting */
    printf("\n Linked list after sorting ");
    printList(start);

    getchar();
    return 0;
}


/* Function to insert a node at the begining of a linked lsit */
void insertAtTheBegin(struct Node **start_ref, int data)
{
    struct Node *ptr1 = (struct Node*)malloc(sizeof(struct Node));
    ptr1->data = data;
    ptr1->next = *start_ref;
    *start_ref = ptr1;
}

/* Function to print nodes in a given linked list */
void printList(struct Node *start)
{
    struct Node *temp = start;
    printf("\n");
    while (temp!=NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
}

/* Bubble sort the given linked lsit */
void bubbleSort(struct Node *start)
{
    int swapped, i;
    struct Node *ptr1;
    struct Node *lptr = NULL;

    /* Checking for empty list */
    if (ptr1 == NULL)
        return;

    do
    {
        swapped = 0;
        ptr1 = start;

        while (ptr1->next != lptr)
        {
            if (ptr1->data > ptr1->next->data)
            { 
                swap(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    }
    while (swapped);
}

/* function to swap data of two nodes a and b*/
void swap(struct Node *a, struct Node *b)
{
    int temp = a->data;
    a->data = b->data;
    b->data = temp;
}