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->4input: -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.