用数据结构C++链表实现基准划分简单写

以下是使用链表实现基准划分的简单代码：

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

// 定义节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node, *LinkedList;

// 创建链表
LinkedList createLinkedList(int n) {
    LinkedList head = (LinkedList)malloc(sizeof(Node));
    head->next = NULL;

    LinkedList tail = head;
    for (int i = 0; i < n; i++) {
        int value;
        printf("请输入第%d个节点的值: ", i + 1);
        scanf("%d", &value);

        LinkedList node = (LinkedList)malloc(sizeof(Node));
        node->data = value;
        node->next = NULL;

        tail->next = node;
        tail = node;
    }

    return head;
}

// 输出链表
void printLinkedList(LinkedList head) {
    LinkedList curr = head->next;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

// 拆分链表
LinkedList partitionLinkedList(LinkedList head, int pivot) {
    // 建立两个链表，一个存放小于基准值的节点，一个存放大于基准值的节点
    LinkedList smallHead = (LinkedList)malloc(sizeof(Node));
    smallHead->next = NULL;
    LinkedList smallTail = smallHead;

    LinkedList largeHead = (LinkedList)malloc(sizeof(Node));
    largeHead->next = NULL;
    LinkedList largeTail = largeHead;

    // 遍历原链表，将小于基准值的节点放入 small 链表，将大于基准值的节点放入 large 链表
    LinkedList curr = head->next;
    while (curr != NULL) {
        if (curr->data < pivot) {
            smallTail->next = curr;
            smallTail = curr;
        } else {
            largeTail->next = curr;
            largeTail = curr;
        }
        curr = curr->next;
    }

    // 将 small 链表和 large 链表合并
    smallTail->next = largeHead->next;
    largeTail->next = NULL;

    // 释放 large 链表的头节点
    free(largeHead);

    return smallHead;
}

int main() {
    int n;
    printf("请输入链表节点数: ");
    scanf("%d", &n);

    LinkedList head = createLinkedList(n);
    printf("原链表: ");
    printLinkedList(head);

    int pivot;
    printf("请输入基准值: ");
    scanf("%d", &pivot);

    LinkedList newHead = partitionLinkedList(head, pivot);
    printf("拆分后的链表: ");
    printLinkedList(newHead);

    // 释放链表内存
    LinkedList curr = newHead;
    while (curr != NULL) {
        LinkedList temp = curr;
        curr = curr->next;
        free(temp);
    }

    return 0;
}

在这个实现中，我们首先定义了一个节点结构体，包含数据和指向下一个节点的指针。然后，我们使用 createLinkedList 函数创建一个链表。在 createLinkedList 函数中，我们使用了一个 for 循环，提示用户输入每个节点的值，并使用 malloc 函数为每个节点分配内存。我们使用 tail 变量来跟踪链表的尾部，以便我们可以将新节点插入到末尾。

接下来，我们使用 printLinkedList 函数输出链表。

在 partitionLinkedList 函数中，我们创建了两个链表，一个用于存放小于基准值的节点，另一个用于存放大于基准值的节点。我们遍历原链表，将小于基准值的节点放入 small 链表，将大于基准值的节点放入 large 链表。然后，我们将 small 链表和 large 链表合并，并返回 small 链表的头节点。

在 main 函数中，我们先创建一个链表，然后提示用户输入基准值。接下来，我们使用 partitionLinkedList 函数将链表拆分，并使用 printLinkedList 函数输出拆分后的链表。最后，我们使用 while 循环释放链表内存。

注意，在释放链表内存时，我们必须从 newHead 开始遍历，因为它是我们创建的第一个节点。否则，我们将无法访问整个链表。