/************************************************/
/*PROGRAM TO SEARCH IN SORTED LINEAR LINKED LIST*/
/************************************************/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<process.h>
#include<ctype.h>
struct linear_list
{
int info;
struct linear_list *next;
}*start,*newnode,*ptr;
void menu();
void create();
void display_traverse();
int list_empty();
int count();
int search_sort(int);
void sort();
void main()
{
clrscr();
menu();
}
void menu()
{
int choice,loc,loc1,item,num,var;
printf("MENU");
printf("\n1. Create");
printf("\n2. Display/Traverse");
printf("\n3. Search in Sorted Linked List");
printf("\n4.Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
clrscr();
printf("The created linked list is:\n");
display_traverse();
getch();
clrscr();
menu();
break;
case 2:
clrscr();
if(list_empty()==1)
{
printf("The linked list is:\n");
display_traverse();
}
getch();
clrscr();
menu();
break;
case 3:
clrscr();
if(list_empty()==1)
{
sort();
printf("Enter the item tobe searched: ");
scanf("%d",&item);
loc=search_sort(item);
if(loc==0)
{
printf("\n%d is not present in the linked list",item);
}
else
{
printf("\n%d is present in the linked list at %d location",item,loc);
}
}
getch();
clrscr();
menu();
break;
case 4:
exit(1);
default:
clrscr();
printf("Your choice is wrong\n\n");
menu();
}
}
void create()
{
int item;
char ch;
clrscr();
newnode=(struct linear_list*)malloc(sizeof(struct linear_list));
start=newnode;
do
{
printf("\nEnter data: ");
scanf("%d",&item);
newnode->info=item;
printf("\nDo you want to create another node:(y/n)");
fflush(stdin);
scanf("%c",&ch);
if(tolower(ch)=='y')
{
newnode->next=(struct linear_list*)malloc(sizeof(struct linear_list));
newnode=newnode->next;
}
else
{
newnode->next=NULL;
}
}while(tolower(ch)!='n');
}
void display_traverse()
{
int i;
ptr=start;
i=1;
while(ptr!=NULL)
{
printf("\nNode %d : %d",i,ptr->info);
ptr=ptr->next;
i++;
}
}
int list_empty()
{
if(start==NULL)
{
printf("\nLinked List is empty");
return(0);
}
else
{
return(1);
}
}
int count()
{
int num;
num=0;
ptr=start;
while(ptr!=NULL)
{
ptr=ptr->next;
num++;
}
return(num);
}
int search_sort(int item)
{
int loc,i;
i=1;
loc=0;
ptr=start;
while((ptr!=NULL)&&(item>=ptr->info))
{
if((ptr->info)==item)
{
loc=i;
break;
}
ptr=ptr->next;
i++;
}
return(loc);
}
void sort()
{
struct linear_list *ptr1;
int temp,num,i;
num=count();
ptr=start;
ptr1=ptr->next;
for(i=1;i<=num-1;i++)
{
while(ptr->next!=NULL)
{
if((ptr->info)>(ptr1->info))
{
temp=ptr->info;
ptr->info=ptr1->info;
ptr1->info=temp;
}
ptr=ptr->next;
ptr1=ptr1->next;
}
ptr=start;
ptr1=ptr->next;
}
}