ユーザ入力後にquicksortで単独リンクされたリストをソートし、新しいノードと頼りになるリストを挿入する

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 

あなたのコードの問題は、パラメータがノードへのポインタが、構造体へのポインタではありませんでしたので、それが無限ループに入ったということでした。リストを参照渡しするので、リストを返す必要もありません。