算法的阶梯

Linked list sort

2018-08-29  本文已影响12人  Tedisaname

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.

上一篇下一篇

猜你喜欢

热点阅读