算法实现

SingleListSort.c

#include <stdio.h>
#include <malloc.h>

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

void InsertListNode(ListNode *head, int pos, int data, int len);

void printflist(ListNode *head);

void SortSingleList(ListNode *head);


int main() {
    printf("Hello, World!2\n");
    printf("single list sort\n");
    printf("----by lynnbest ----\n\n");
    int a[] = {3, 5, 8, 6, 2, 1, 11, 45, 16};
    int len = sizeof(a) / sizeof(a[0]);
    ListNode *head = (ListNode *) malloc(sizeof(ListNode));
    if (NULL == head) {
        printf("head node create error\n");
        exit(-1);
    }
    head->next = NULL;
    for (int i = 0; i < len; i++)
        InsertListNode(head, i + 1, a[i], len);
    printf("before sorted:\n");
    printflist(head);
    SortSingleList(head);
    printf("after sorted:\n");
    printflist(head);
    return 0;
}

// implements of struct ListNode
void InsertListNode(ListNode *head, int pos, int data, int len) {
    ListNode *pre = head, *newNode;
    if (pos < 1 || pos > (len + 1)) {
        printf("insert location error");
        exit(-1);
    }
    for (int i = 1; i < pos; ++i) {
        pre = pre->next;
    }
    if (NULL == (newNode = (ListNode *) malloc(sizeof(ListNode)))) {
        printf("create new node error");
        exit(-1);
    }
    newNode->data = data;
    newNode->next = pre->next;
    pre->next = newNode;
}

void printflist(ListNode *head) {
    ListNode *p = head->next;
    while (p != NULL) {
        printf("%3d", p->data);
        p = p->next;
    }
    printf("\n");
}

void SortSingleList(ListNode *head) {
    ListNode *pre = head, *p = pre->next, *q, *r;
    q = p->next;
    p->next = NULL;
    while (q != NULL) {
        while (pre->next != NULL && q->data > pre->next->data) {
            pre = pre->next;
        }
        r = q->next;

        q->next = pre->next;
        pre->next = q;

        q = r;
        pre = head;
    }
}