问题描述:

I have my code for the most part but having a rough go of it trying to get my quick sort function to work and sort through the actual link list created. Don't know if I am calling the function improperly or if I have the struct correct.

The program will compile and run up until it gets to the calling function for the quicksort. Then it just freezes and does nothing. Any help would be great. Thank you a head of time.

 #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;

}

网友答案:

Please look at this working example.

#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;
}

Test

/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

The problem with your code was that it entered an infinite loop because the parameter was not a pointer to the node, but a pointer to the struct. You also don't need to return the list because you are passing it by reference.

相关阅读:
Top