c - 在用户输入后使用快速排序对单链表进行排序，然后插入新节点和排序列表

Question

我有大部分代码，但我粗略地尝试让我的快速排序功能工作并对创建的实际链接列表进行排序。不知道我是否错误地调用了函数，或者我的结构是否正确。

程序将编译并运行，直到到达快速排序的调用函数。然后它只是卡住并且什么都不做。任何帮助都会很棒。谢谢你的时间。

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

struct node{
    int data;
    struct node *link_list;
};

struct node *insertion(struct node *pointer, int i){
    struct node *temp_val;
    if(pointer == NULL){
        pointer = (struct node *)malloc(sizeof(struct node));
        if(pointer == NULL){
            printf("Error Exiting\n");
            exit(0);
        }
        pointer->data = i;
        pointer->link_list = pointer;
    }else{
        temp_val = pointer;
        while(temp_val->link_list != pointer){
            temp_val = temp_val->link_list;
        }
        temp_val->link_list = (struct node *)malloc(sizeof(struct node));
        if(temp_val->link_list == NULL){
            printf("Error Exiting\n");
            exit(0);
        }
        temp_val = temp_val->link_list;
        temp_val->data = i;
        temp_val->link_list = pointer;
    }
    return(pointer);    
};


struct node *findPivot(struct node *head, struct node *term, struct node **newHead, struct node **newTerm){
    struct node *pivot = term;
    struct node *previous = NULL, *current = head, *tail = pivot;
    //finding the pivot and dividing the list while also updating the head and term
    // with newHead and newTerm
    while(current != pivot){
        if(current->data < pivot->data){
            //assigning the newHead to the first value less then the pivot
            if((*newHead) == NULL){
                (*newHead) = current;
            }
            previous = current;
            current = current->link_list;
        }else{
            // if the current node has a higher value then the pivot
            // assinging it to newTerm
            if(previous){
                previous->link_list = current->link_list;
            }
            struct node *temp = current->link_list;
            current->link_list = NULL;
            tail->link_list = current;
            tail = current;
            current = temp;
        }
    }
    //Checks the case if the pivot is the smallest value and moves to head
    if((*newHead)== NULL){
        (*newHead) = pivot;
    }
    (*newTerm) = tail; // makes sure the last element is newEnd

    return pivot;

}
//finds the last node in the list and returns it
struct node *getTail(struct node *current){
    while(current != NULL && current->link_list != NULL){
        current = current->link_list;
    }
    return current;
}

// the actual recursive quicksort algorithm
struct node *quickSort(struct node *head, struct node *term){
    if(!head || head == term)  //base case for the recursion
        return head;

    struct node *newHead = NULL, *newTerm = NULL;

    // the recursive case
    struct node *pivot = findPivot(head, term, &newHead, &newTerm);

    //no need for recursion if pivot is smallest value
    if(newHead != pivot){
        struct node *temp = newHead;
        while(temp->link_list != pivot){
            temp = temp->link_list;
        }
        temp->link_list = NULL;
        newHead = quickSort(newHead, temp);
        temp = getTail(newHead);
        temp->link_list = pivot;
    }

    pivot->link_list = quickSort(pivot->link_list, newTerm);

    return newHead;

}

void quickSortFunction(struct node **pointer){
    *pointer = quickSort(*pointer, getTail(*pointer));
    return;
}

void printList_Unsorted(struct node *pointer){
    struct node *temp;
    temp = pointer;
    printf("\nThe Data values in the list are:\n");
    if(pointer != NULL){
        do{
            printf("%d\t", temp->data);
            temp = temp->link_list;
        }while(temp != pointer);
    }else{
        printf("the list is empty\n");
    }
}


void printList_Sorted(struct node *node){
    while(node!= NULL){
        printf("%d ", node->data);
        node = node->link_list;
    }
    printf("\n");
}

int main(int argc, char *argv[]) {
    int num_nodes, node_val;
    struct node *list = NULL;
    printf("Enter the number of nodes to be created: ");
    scanf("%d", &num_nodes);

    while(num_nodes --> 0){
        printf("\n\nEnter the data values to be placed in a node: ");
        scanf("%d", &node_val);
        list = insertion(list, node_val);
    }
    printf("\n\nThe Created list is as follow:\n");
    printList_Unsorted(list);
    printf("\n");

    quickSortFunction(&list);
    printList_Sorted(list);

    //getchar();
    //getchar();



    return 0;
}

Answer 1

请看这个工作示例。

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

struct node {
    int data;
    struct node *link_list;
};

void insertion(struct node **pointer, int i) {
    struct node *temp_val = malloc(sizeof *temp_val);
    temp_val->data = i;
    temp_val->link_list = (*pointer);
    (*pointer) = temp_val;
}

/* A utility function to print linked list */
void printList(struct node *node) {
    while (node != NULL) {
        printf("%d  ", node->data);
        node = node->link_list;
    }
    printf("\n");
}

// Returns the last node of the list
struct node *getTail(struct node *current) {
    while (current != NULL && current->link_list != NULL)
        current = current->link_list;
    return current;
}


struct node *findPivot(struct node *head, struct node *term,
                       struct node **newHead, struct node **newTerm) {
    struct node *pivot = term;
    struct node *previous = NULL, *current = head, *tail = pivot;


    while (current != pivot) {
        if (current->data < pivot->data) {

            if ((*newHead) == NULL)
                (*newHead) = current;

            previous = current;
            current = current->link_list;
        }
        else
        {

            if (previous)
                previous->link_list = current->link_list;
            struct node *tmp = current->link_list;
            current->link_list = NULL;
            tail->link_list = current;
            tail = current;
            current = tmp;
        }
    }

    // If the pivot data is the smallest element in the current list,
    // pivot becomes the head
    if ((*newHead) == NULL)
        (*newHead) = pivot;

    // Update newTerm to the current last node
    (*newTerm) = tail;

    // Return the pivot node
    return pivot;
}


// the actual recursive quicksort algorithe
struct node *quickSort(struct node *head, struct node *end) {
    // base case
    if (!head || head == end)
        return head;

    struct node *newHead = NULL, *newEnd = NULL;


    struct node *pivot = findPivot(head, end, &newHead, &newEnd);


    if (newHead != pivot) {

        struct node *tmp = newHead;
        while (tmp->link_list != pivot)
            tmp = tmp->link_list;
        tmp->link_list = NULL;


        newHead = quickSort(newHead, tmp);


        tmp = getTail(newHead);
        tmp->link_list = pivot;
    }

    pivot->link_list = quickSort(pivot->link_list, newEnd);

    return newHead;
}


void quickSortFunction(struct node **headRef) {
    (*headRef) = quickSort(*headRef, getTail(*headRef));
    return;
}


int main() {
    struct node *list = NULL;

    int num_nodes, node_val;
    printf("Enter the number of nodes to be created: ");
    scanf("%d", &num_nodes);
    while(num_nodes --> 0){
        printf("\n\nEnter the data values to be placed in a node: ");
        scanf("%d", &node_val);
        insertion(&list, node_val);
    }
    printf("\n\nThe Created list is as follows:\n");
    printList(list);
    printf("\n");
    quickSortFunction(&list);
    printList(list);
    return 0;
}

测试

/home/dac/.CLion2016.2/system/cmake/generated/gnu-fadf49ce/fadf49ce/Debug/gnu
Enter the number of nodes to be created: 3


Enter the data values to be placed in a node: 2


Enter the data values to be placed in a node: 4


Enter the data values to be placed in a node: 3


The Created list is as follows:
3  4  2  

2  3  4  

Process finished with exit code 0

您的代码的问题在于它进入了无限循环，因为参数不是指向节点的指针，而是指向结构的指针。您也不需要返回列表，因为您是通过引用传递它的。