 |
||||||
| Home | About Us | Portfolio | Services | Career | Contact Us | Industrial Training | Achievement | ||||||
/*INCLUDE HEADER FILES*/
#include<stdio.h>
#include<conio.h>
struct node//DECLARE THE STRUCTURE
{
int data;//DATA FIELD
struct node *next;//NEXT POINTER
};
//Function to copy a list into other
void copy(struct node *,struct node **);
//Function to delete all the elements of a list
void delAll(struct node **);
//Function to insert an element in an ascending ordered list
void insertAsc(struct node **,int);
//Function to insert an element in an descending ordered list
void insertDesc(struct node **,int );
//Function to merge 2 lists into other
void merge(struct node *,struct node *,struct node **);
//Function to concatenate 2 lists into other
void concat(struct node *,struct node *,struct node **);
//Function to sort a list by exchanging the data
void sortData(struct node **);
//Function to sort a list by exchanging node pointers
void sortNode(struct node **);
//Function to count the number of nodes
int count (struct node *);
//Main function
void main()
{
//Declaring three lists required
struct node *list1,*list2,*list3,*list;
int choice,info,ch;
//Initiating them all to NULL
list=list1=list2=list3=NULL;
clrscr();//clears the user screen
/*Entering the list*/
printf("Do you want to enter the element in the list? ");
printf("Enter\n1-Yes\n0-No\n");
scanf("%i",&ch);
while(ch==1)
{
printf("Enter the element in list: ");
scanf("%i",&info);
addAtEnd(&list1,info);//ADDS AT THE END
fflush(stdin);
printf("Do you want to enter the element in the list? ");
printf("Enter\n1-Yes\n0-No\n");
scanf("%i",&ch);
}
while(1)
{
clrscr();
//Display of menu
printf("********MENU********\n");
printf("1. Create a copy of a list!\n");
printf("2. Delete all elements of a list!\n");
printf("3. Insert in an ascending order list!\n");
printf("4. Insert in a descending order list!\n");
printf("5. Merge two sorted linked lists!\n");
printf("6. Concatenate two lists!\n");
printf("7. Sort the contents of a linked list by exchanging data!\n");
printf("8. Display the list!\n");
printf("0. Exit!\n");
printf("Your choice: ");
scanf("%i",&choice);
switch(choice)
{
case 1: copy(list1,&list2); //Function call[Create a copy of a list]
getch();
break;
case 2: delAll(&list1); //Function call[Delete all elements of a list]
getch();
break;
case 3: printf("Enter the data to be inserted: ");
scanf("%i",&info);
insertAsc(&list1,info); //Function call[Insert in an ascending order list]
getch();
break;
case 4: printf("Enter the data to be inserted: ");
scanf("%i",&info);
insertDesc(&list1,info); //Function call[Insert in a descending order list]
getch();
break;
case 5: //Entering the list to be merged with first one
printf("Enter the list to be merged with:\n");
printf("Do you wish to enter a number? Enter\n1-Yes\n0-No\n");
scanf("%i",&ch);
while(ch==1)
{
printf("Enter an element in the list: ");
scanf("%i",&info);
addAtEnd(&list2,info);//Function call[adds the node at the list at the end of the list ]
fflush(stdin);
printf("Do you wish to enter a number? Enter\n1-Yes\n0-No");
scanf("%i",&ch);
}
merge(list1,list2,&list); //Function call[Merge two sorted linked lists]
getch();
break;
case 6: //Entering the list to be concatenated with first one
printf("Enter the list to be concatenated with:\n");
printf("Do you wish to enter a number? Enter\n1-Yes\n0-No\n");
scanf("%i",&ch);
while(ch==1)
{
printf("Enter an element in the list: ");
scanf("%i",&info);
addAtEnd(&list3,info); //Function call
printf("Do you wish to enter a number? Enter\n1-Yes\n0-No\n");
scanf("%i",&ch);
}
concat(list1,list3,&list); //Function call[Concatenate two lists]
getch();
break;
case 7: sortData(&list1); //Function call[Sort the contents of a linked list by exchanging data]
getch();
break;
case 8: display(list1); //Function call[DISPLAY THE LIST]
getch();
break;
case 0: exit();
break;
default: printf("You entered wrong choice!");
getch();
break;
}
}
}
/*creates the copy of the linked list*/
void copy(struct node *head,struct node **newlist)
{
struct node *temp1,*temp2,*newnode;
temp1=head; //As 'temp' will traverse the whole list
//If the list is empty
if(head==NULL)
{
*newlist=NULL; //Equating to NULL
printf("The list is empty");
return; //End of function
}
//Allocating memory
newnode=(struct node *)malloc(sizeof(struct node));
//Equating 'next' of the 'newnode' to NULL
newnode->next=NULL;
//Till the end of list is not encountered
while(temp1!=NULL)
{
//If the resultant list is empty
if(*newlist==NULL)
{
//Setting data to that stored in head of source list
newnode->data=head->data;
//Equating 'newlist' to head of new list
*newlist=newnode;
temp2=*newlist; //As 'temp2' will traverse the new list
temp1=temp1->next; //Moving to next node of source list
}
else
{
//Allocating memory for next node of new list
temp2->next=(struct node *)malloc(sizeof(struct node));
temp2=temp2->next; //Now next node will be the working node
temp2->next=NULL; //Setting it's next to NULL
temp2->data=temp1->data; //Setting data
temp1=temp1->next; //Moving to next node of source list
}
}
//Assigning NULL to next of last node of copied list
temp2->next=NULL;
//Displaying the resultant list
display(*newlist);
}
/*deletes all the nodes the of the list*/
void delAll(struct node **head)
{
struct node *temp;
//Till the end of list is not encountered
while(*head!=NULL)
{
temp=*head; //Equating 'temp' to head
*head=(*head)->next; //Shifting head
free(temp); //In order to free 'temp'
}
}
/*insert the nodes in the in the ascending order*/
void insertAsc(struct node **head,int info)
{
struct node *temp,*newnode;
temp=*head; //As 'temp' will traverse the whole list
//Allocating memory for new node to be inserted
newnode=(struct node *)malloc(sizeof(struct node));
//Setting data for new node
newnode->data=info;
/*If the list is empty or data is least
and hence is to be the first node */
if(*head==NULL||info<(*head)->data)
{
newnode->next=*head;
*head=newnode;
return;
}
//Traversing list till the end of list is not encountered
while(temp!=NULL)
{
/* If current node contains data less than that
of new node and the next node contains data
greater then it OR current node is last node*/
if(((temp->data)<=info)&&((temp->next->data)>=info||temp->next==NULL))
{
newnode->next=temp->next;
temp->next=newnode;
return;
}
//Else move further to check next node
else
temp=temp->next;
}
}
/*insert the nodes in the in the descending order*/
void insertDesc(struct node **head,int info)
{
struct node *temp,*newnode;
temp=*head; //As 'temp' will traverse the whole list
//Allocating memory for new node to be inserted
newnode=(struct node *)malloc(sizeof(struct node));
//Setting data for new node
newnode->data=info;
/*If the list is empty or data is greatest
and hence is to be the first node */
if(*head==NULL||info>(*head)->data)
{
newnode->next=*head;
*head=newnode;
return;
}
//Traversing list till the end of list is not encountered
while(temp!=NULL)
{
/* If current node contains data greater than that
of new node and the next node contains data
less then it OR current node is last node*/
if(((temp->data)>=info)&&((temp->next->data)<=info||temp->next==NULL))
{
newnode->next=temp->next;
temp->next=newnode;
return;
}
//Else move further to check next node
else
temp=temp->next;
}
}
/*function for merging the two linked lists*/
void merge(struct node *head1,struct node *head2,struct node **head)
{
struct node *temp1,*temp2,*temp;
temp1=head1; //As 'temp1' will traverse the first list
temp2=head2; //As 'temp2' will traverse the second list
temp=*head=NULL; //As 'temp' will traverse the resultant list
//If both the lists are empty then resultant list is empty
if(head1==NULL&&head2==NULL)
return;
/* If only one is empty then we'll copy
the other list into resultant list */
if(head1==NULL&&head2!=NULL)
{
copy(head2,&temp);//call the copy function to create the copy of the list
return;
}
if(head2==NULL&&head1!=NULL)
{
copy(head1,&temp);
return;
}
//Else traverse the two list till their end is reached
while(temp1!=NULL&&temp2!=NULL)
{
if(*head==NULL) //If resultant list is empty
{
//Allocate memory for head
*head=(struct node *)malloc(sizeof(struct node));
//Setting it's 'next' to NULL
(*head)->next=NULL;
temp=*head;
}
else
{
//Allocate memory for next node
temp->next=(struct node *)malloc(sizeof(struct node));
//Moving to next node of resultant list
temp=temp->next;
//Setting 'next' of that new node to NULL
temp->next=NULL;
}
//Setting of data begins:-
/* If data of first list's node is less then that of second one
then temp will be assigned the value of data in first list &
traversing pointer of first node will move to it's next node*/
if((temp1->data)<(temp2->data))
{
temp->data=temp1->data;
temp1=temp1->next;
}
/* If data of first list's node is greater then that of second one
then temp will be assigned the value of data in second list &
traversing pointer of second node will move to it's next node*/
else if((temp1->data)>(temp2->data))
{
temp->data=temp2->data;
temp2=temp2->next;
}
/* If data of first & second list's node are equal then temp
will be assigned the value of that data and the traversing
pointer of both the nodes will move to the next node */
else if(temp1->data==temp2->data)
{
temp->data=temp1->data;
temp1=temp1->next;
temp2=temp2->next;
}
}
//If end of first list is not reached
while(temp1!=NULL)
{
//Allocate the memory for next node of resultant list
temp->next=(struct node *)malloc(sizeof(struct node));
//Moving to next node of resultant list
temp=temp->next;
//Setting data of that new node
temp->data=temp1->data;
//Setting next of that new node to NULL
temp->next=NULL;
//Moving to next node of first list
temp1=temp1->next;
}
//If end of second list is not reached
while(temp2!=NULL)
{
//Allocate the memory for next node of resultant list
temp->next=(struct node *)malloc(sizeof(struct node));
//Moving to next node of resultant list
temp=temp->next;
//Setting data of that new node
temp->data=temp2->data;
//Setting next of that new node to NULL
temp->next=NULL;
//Moving to next node of second list
temp2=temp2->next;
}
//'next' of last node will point to NULL
temp->next=NULL;
//Displaying resultant list
display(*head);
}
/*concatenates the two linked lists*/
void concat(struct node *head1,struct node *head2,struct node **newlist)
{
struct node *part1,*part2,*temp;
//Initialisation to NULL
part1=part2=NULL;
//Copying first list into 'part1'
copy(head1,&part1);
//Equating newlist to 'part1' i.e. first list
*newlist=part1;
//Now copying second list into 'part2'
copy(head2,&part2);
//As 'temp' will traverse 'newlist'
temp=*newlist;
//Traversing list via 'temp' till it's end is encountered
while(temp->next!=NULL)
temp=temp->next;
//Pointing 'next' of last node to head of new list
temp->next=part2;
//Displaying concatenated list
display(*newlist);
}
/*sorts the list by data*/
void sortData(struct node **head)
{
struct node *temp,*cur;
int i,j,num,tempo;
temp=*head; //As 'temp' will traverse whole list
//If the list is empty
if(*head==NULL)
return;
//Calculating number of nodes in list
num=count(*head); //Function call
for(i=0;i<num-1;i++)
{
//'cur' will point to the node next to 'temp'
cur=temp->next;
for(j=i+1;j<num;j++)
{
//If data at 'temp' is greater then that at 'cur'
if(temp->data>cur->data)
{
//Swapping the data using tempo
tempo=temp->data;
temp->data=cur->data;
cur->data=tempo;
}
//Repeating above loop for 'temp' & node next to 'cur'
cur=cur->next;
}
//Shifting 'temp' to next node
temp=temp->next;
}
display(*head);
}
/*counts the no. of nodes in the list*/
int count (struct node *head)
{
struct node *temp;//declare the new pointer
int cnt=0; //Node counter
if(head==NULL) //If list is empty, cnt=0
return cnt;
temp=head; //As 'temp' will traverse whole list
//Counting number of nodes till end of list is encountered
while(temp!=NULL)
{
temp=temp->next;
cnt++;
}
return cnt; //End of function
}
