Linked list sort

作者: Tedisaname | 来源:发表于2018-08-29 09:21 被阅读12次

    The linked list is sorted under O(n log n) time complexity and constant >level space complexity.

    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>//function to exit()
    #define OK 1    //status for 1
    #define ERROR 0 //status for 0
    //struct for a node
    typedef struct Node{
        int data;
        struct Node * next;
    }Node,*PNode;
    
    void swap(PNode,PNode);//Function to swap data of two nodes a and b
    
    int Initialization(PNode& head)
    {
        head = (PNode)malloc(sizeof(Node));//create a head Node
        head->next = NULL;//initialize the head node
        return OK;
    }
    
    //crerate the linked list from user input
    void create(PNode head)
    {
    
        int m,a;
        PNode p, q;
        printf("Please input the length of the linked list:");
        scanf("%d",&m); 
        q = NULL;
        for(int i = 0; i < m; i++)
        {
            scanf("%d",&a);
            p = (PNode)malloc(sizeof(Node));
            p->data = a;
            p->next = NULL;
            if(head->next == NULL)//attention!!!!head ->next == NULL ,not head == NULL
            head->next = p;//head directly points to p if the head points to NULL 
            else
            q->next = p;//else,pointer q points to the p;
            
            q = p;//pointer q points to p   
        }
            
    }
    //print all the emements of linked list
    void printLinkedlist(PNode head)
    {
        PNode t = head->next;//the next field of the head pointer is the first valid node attention~!!!!!!
        while(t != NULL)
        {
            printf("%d ",t->data);
            t = t->next;
        }
        printf("\n");
    }
    //Bubble sort the given linked list
    void bubbleSort(PNode head)
    {
        int swapped;
        PNode ptr1;
        PNode lptr = NULL;
        
        if(head == NULL)
            return;
            
        do
        {
            swapped = 0;
            ptr1 = head->next;
            
            while(ptr1->next != lptr)
            {
                if(ptr1->data > ptr1->next->data)
                {
                    swap(ptr1,ptr1->next);
                    swapped = 1;
                }
                
                ptr1 = ptr1->next;
            }
            lptr =  ptr1;
        }while(swapped); 
    }
    //Function to swap data of two nodes a and b
    void swap(PNode a,PNode b)
    {
        int temp;
        temp = a->data;
        a->data = b->data;
        b->data = temp;
    }
    int main()
    {
        PNode head;
        if(Initialization(head)){
            printf("Initialization successful!\n");
        }
        else
        {
            printf("Initialization failed!\n"); 
            exit(ERROR);
        }   
        create(head);//Create linked list from the function to  user input
        printLinkedlist(head);//print list before sorting
        bubbleSort(head);//sort the linked list
        printLinkedlist(head);//print the list after sorting
        return 0; 
    }
    

    input: 4->2->1->3
    output: 1->2->3->4

    input: -1->5->3->4->0
    output: -1->0->3->4->5

    You can leave me a message if you find out any mistake in my diary, I'll correct it, thanks.

    相关文章

      网友评论

        本文标题:Linked list sort

        本文链接:https://www.haomeiwen.com/subject/qjqhwftx.html