C语言 单向链表 插入排序

好的，我能够回答您关于 C 语言单向链表插入排序的问题。

插入排序是一种简单直观的排序算法，对于链表的插入排序，我们可以将未排序的节点一个一个插入到已排序好的链表中。具体的过程是，我们从链表的第二个节点开始遍历链表，将当前节点插入到已排序的链表中的合适位置，然后继续遍历下一个节点，直到遍历完整个链表。

实现过程中，需要两个指针，一个指针指向已排序链表的头节点，另一个指针指向未排序链表的头节点。我们每次从未排序链表中取出一个节点，找到它应该插入的位置，然后将它插入到已排序链表中去。

值得注意的是，在插入一个节点到已排序的链表中时，可能需要更新已排序链表的头节点。此外，对于链表的插入排序，算法的时间复杂度为 O(n^2)。

相关问题

如何用C语言实现链表的排序？

在C语言中实现链表的排序通常会使用一种叫做“插入排序”的简单算法，因为链表不适合直接使用复杂排序算法（如快速排序、归并排序等），它们依赖于随机访问，而链表则是顺序访问。

以下是使用插入排序对单向链表进行升序排序的一个基本步骤：

1. 定义一个辅助函数`insert_sorted`，用于将新节点插入到已排序的部分，保证链表的有序性。

2. 定义一个主函数`sort_list`，首先创建一个新的头结点`sorted_head`和`current`指针指向原头结点。

3. 使用`while`循环遍历链表，当`current`不为空时：
a. 获取当前节点的值`temp Val`。
b. 创建一个临时指针`prev`，初始化为`sorted_head`。
c. 同样遍历已排序部分的链表，直到找到一个大于等于`temp Val`的节点或遍历完，将`prev`指向前一个大于等于`temp Val`的节点。
d. 如果`prev`未改变，则说明`temp Val`应该作为新的头结点；否则，将`temp`链接到`prev`之后。

4. 遍历结束后，将原头结点指向`sorted_head`，完成链表排序。

typedef struct Node {
    int data;
    struct Node *next;
} Node;

void insert_sorted(Node **sorted_head, Node *new_node) {
    if (*sorted_head == NULL || new_node->data <= (*sorted_head)->data) {
        new_node->next = *sorted_head;
        *sorted_head = new_node;
    } else {
        Node *current = *sorted_head;
        while (current->next != NULL && current->next->data < new_node->data) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

void sort_list(Node **head) {
    Node *sorted_head = NULL, *current = *head, *temp;
    while (current != NULL) {
        temp = current;
        current = current->next;
        insert_sorted(&sorted_head, temp);
    }
    *head = sorted_head;
}

C语言双向循环链表排序案例，不要只是交换数据域的值

在C语言中，双向循环链表是一种数据结构，每个节点都包含数据域以及两个指针域，一个指向前一个节点，一个指向后一个节点。与单向链表不同，双向循环链表的头尾相接，形成一个环。对双向循环链表进行排序时，我们通常需要比较节点中的数据，并根据排序算法调整节点的指针域，而不仅仅是数据域的值。

下面是一个简化的C语言双向循环链表排序的案例，使用插入排序算法进行演示。请注意，实际代码需要进行错误检查和异常处理，此处仅提供基本的排序逻辑。

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

// 定义双向循环链表的节点结构体
typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

// 创建一个新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    newNode->data = data;
    newNode->prev = newNode;
    newNode->next = newNode;
    return newNode;
}

// 向双向循环链表中插入一个节点
void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (!newNode) return;

    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        // 找到链表的最后一个节点
        while (temp->next != *head) {
            temp = temp->next;
        }
        // 插入新节点
        temp->next = newNode;
        newNode->prev = temp;
        newNode->next = *head;
        (*head)->prev = newNode;
    }
}

// 双向循环链表的插入排序
void insertionSort(Node** head) {
    if (*head == NULL || (*head)->next == *head) {
        return; // 链表为空或只有一个节点时不需要排序
    }

    Node *sorted = NULL; // 已排序部分的最后一个节点

    // 遍历链表中的所有节点
    for (Node* current = *head; current != NULL; ) {
        Node* next = current->next; // 保存下一个节点的指针

        // 寻找current的正确位置，插入到sorted链表中
        if (sorted == NULL || sorted->data >= current->data) {
            // 插入到sorted的开头
            if (sorted != NULL) {
                current->next = sorted;
                sorted->prev = current;
            }
            current->prev = NULL;
            current->next = *head;
            (*head)->prev = current;
            *head = current;
        } else {
            // 寻找current在sorted中的位置并插入
            Node* sortedCurrent = sorted;
            while (sortedCurrent->next != sorted && sortedCurrent->data < current->data) {
                sortedCurrent = sortedCurrent->next;
            }
            // 插入current到sortedCurrent之后
            current->next = sortedCurrent->next;
            current->prev = sortedCurrent;
            sortedCurrent->next->prev = current;
            sortedCurrent->next = current;
        }

        // 更新current为下一个要处理的节点
        current = next;
        if (current != NULL && current == *head) {
            // 如果已经回到链表头部，则结束排序
            break;
        }
    }
}

// 打印双向循环链表
void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    Node* temp = head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

int main() {
    Node* head = NULL;
    insertNode(&head, 4);
    insertNode(&head, 3);
    insertNode(&head, 2);
    insertNode(&head, 1);

    printf("Original list:\n");
    printList(head);

    insertionSort(&head);

    printf("Sorted list:\n");
    printList(head);

    // 释放链表内存的代码应该在这里，但为了简洁性，省略了

    return 0;
}

请注意，上述代码是一个简单的示例，仅用于演示插入排序算法在双向循环链表中的应用。在实际应用中，可能需要处理更复杂的情况，如内存释放、错误处理等。