#include<stdio.h>
#include<conio.h>
struct node
{
int val;
struct node *next;
};
typedef struct node node;
void main()
{
int choice;
node *start;
node* createnode(node*);
node* mergesort(node*);
void printlist(node*);
start=NULL;
while(1)
{
printf("\nEnter your choice:1.CreateList 2.Sorting 3.Print 4.Exit");
printf("\nChoice:");
scanf("%d",&choice);
switch(choice)
{
case 1:start=createnode(start);
break;
case 2:start=mergesort(start);
break;
case 3:printlist(start);
break;
case 4:exit(0);
break;
default:printf("\nEnter Correct Choice");
}
}
getch();
}
node* makenode(int val)
{
node *nn;
nn=(node*)malloc(sizeof(node));
nn->val=val;
nn->next=NULL;
return nn;
}
node* createnode(node*start)
{
int tmp;
node *nn;
node* last;
last=start;
printf("\nEnter -99 for Stop This Process");
while(1)
{
printf("\nEnter the Val of Node:");
scanf("%d",&tmp);
if(tmp==-99)
break;
nn=makenode(tmp);
if(!start)
start=nn;
else
last->next=nn;
last=nn;
}
return start;
}
node* divide(node *start)
{
node *start2=NULL,*prev,*ptr;
if(!start)
return;
if(start->next)
{ prev=start;
ptr=start->next->next;
}
while(ptr)
{
prev=prev->next;
ptr=ptr->next;
if(ptr)
ptr=ptr->next;
}
start2=prev->next;
prev->next=NULL;
return start2;
}
node* merge(node*nn,node*start)
{
node *start3,*last3,*tmp;
start3=last3=NULL;
while(nn&&start)
{
if(nn->val<start->val)
{
tmp=nn;
nn=nn->next;
}
else
{ tmp=start;
start=start->next;
}
if(!start3)
start3=tmp;
else
last3->next=tmp;
last3=tmp;
}
if(nn)
{
if(!start3)
start3=nn;
else
last3->next=nn;
}
if(start)
{
if(!start3)
start3=start;
else
last3->next=start;
}
return start3;
}
node* mergesort(node* start)
{
node *nn;
if(start->next)
{
nn=divide(start);
start=mergesort(start);
nn=mergesort(nn);
start=merge(nn,start);
}
return start;
}
void printlist(node *start)
{
if(!start)
return;
printf("\nSorted List:");
while(start)
{
printf("%d-->",start->val);
start=start->next;
}
printf("End");
}
No comments:
Post a Comment