Description:
In this program we have to create a single linked list,
insert the elements into that list ,delete the some elements from that list and
then perform the sorting operation and traversal operation on that created
linkedlist
Algorithm :
Step 1: Start
Step 2: Declare a structure named
linked-list
Step 3: Declare the pointers next,
first, fresh, ptr
Step 4: Print main menu
Step 5: Read choice
Step 6: Switch(choice)
Step 7: If(choice==1)
7.1
Assign fresh=malloc(size of (node))
7.2
Read the element fresh->data
7.3
Read the choice where to insert
7.4:Switch(choice)
7.4.1:
If choice==1
7..4.2:
Call the function IBegin()
7.4.3: If choice==2
7.4.4:
Call the function Iend()
7.4.5:
If choice==3
7.4.6:
Call the function Imiddle()
Step 8: If(choice==2)
8.1:
Read the position to delete
8.2:
Switch(choice)
8.2.1:
If choice==1
8..2.2:
Call the function DBegin()
8.2.3: If choice==2
8.2.4:
Call the function Dend()
8.2.5:
If choice==3
8.2.6:
Call the function Dmiddle()
Step 9: If choice==3
9.1
Call function view
Step 10: If choice==4
10.1
Exit()
Step 11: Start insert function
Step 12: If(first==null)
Step 13: First->data=e
Step 14: First->next=null
Step 15: Else declare new node
Step 16:fresh->data=e
Step 17: If choice=1
Step 18: frsh->next=first
Step 19: first=fresh
Step 20:if choice=2
Step 21: ptr=first
Step 22: ptr->next=fresh
Step 23: fresh->next=full
Step 24: If choice =3
Step 25: Enter the position
Step 26:at p-1 node
Step 27: fresh->next=
ptr->next
Step 28: ptr->next=fresh
Step 29: for delete function
Step 30: If first!=null
Step 31: Enter the position to
delete
Step 32: If choice=1
Step 33: d=first->data
Step 34: first=first->next
Step 35: if choice=2
Step 36: ptr=first
Step 37: Traverse to last node
Step 38: d=ptr->next->data
Step 39: ptr
->next=ptr->next->next
Step 40: Print d value
Step 41: for function view
Step 42: for ptr=first and
ptr!=null and ptr=ptr->next
Step 43: Print ptr->data
Step 44: End
# include<stdio.h>
# include<malloc.h>
int ch,i,n,j,p,item;
/* VARIABLE DECLARATION */
/* START OF STRUCTURE DEFINITION */
struct link
{
int data;
struct link *next;
}*start,*new,*l,*l1,*start1,*t;
/* END OF STRUCTURE DEFINITION */
/* START OF MAIN FUNCTION */
main()
{
clrscr();
start=NULL;
start1=NULL;
printf(" **** MENU **** ");
printf("\n 1.Insertion\n 2.Deletion\n 3.Traverse\n 4.Search\n
5.Sort\n 6.Merge\n 7.Reverse\n");
while(1)
{
printf("enter the choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: insert();
break;
case 2: delete();
break;
case 3: traverse();
break;
case 4: search();
break;
case 5: sort();
break;
case 6: merge();
break;
case 7: reverse();
break;
case 8:exit();
}
}
getch();
}
/* END OF MAIN FUNCTION */
/* START OF INSERT FUNCTION */
insert()
{
l=start;
printf("enter the item to be inserted:");
scanf("%d",&item);
new=malloc(sizeof(struct link));
new->data=item;
if(start==NULL)
{
new->next=NULL;
start=new;
}
else
{
printf("1.start\n2.middle\n3.end\n");
printf("enter the place to place the
item:");
scanf("%d",&ch);
if(ch==1)
{
new->next=start;
start=new;
}
if(ch==2)
{
printf("enter the position to place
item:");
scanf("%d",&p);
for(i=1;i<p-1;i++)
l=l->next;
new->next=l->next;
l->next=new;
}
if(ch==3)
{
while(l->next!=NULL)
l=l->next;
new->next=NULL;
l->next=new;
}
}
}
/* END OF INSERT FUNCTION */
/* START OF DISPLAY FUNCTION */
traverse()
{
if(start==NULL)
printf("LIST IS EMPTY\n");
else
{
for(l=start;l->next!=NULL;l=l->next)
if(l==start)
printf("\nstart:%d->",l->data);
else
printf("\n%7d->",l->data);
if(l->next==NULL)
printf("\n
last:%d->\n",l->data);
}
}
/* END OF DISPLAY FUNCTION */
/* START OF DELETE FUNCTION */
delete()
{
l=start;
if(start==NULL)
printf("NO ITEMS IN THE
LIST\n");
else
{
printf("1.start\n2.middle\n3.end\n");
printf("enter the place to delete the
item:");
scanf("%d",&ch);
if(ch==1)
{
item=start->data;
printf("deleted item
is:%d\n",item);
start=start->next;
}
if(ch==2)
{
printf("enter the position to delete
item:");
scanf("%d",&p);
if(l->next==NULL)
{
item=l->data;
printf("deleted item
is:%d\n",item);
l=start=NULL;
}
else
{
for(i=1;i<p-1;i++)
l=l->next;
item=l->next->data;
printf("deleted item
is:%d\n",item);
l->next=l->next->next;
}
}
if(ch==3)
{
if(l->next==NULL)
{
item=l->data;
printf("deleted item
is:%d\n",item);
l=start=NULL;
}
else
{
while(l->next->next!=NULL)
l=l->next;
item=l->next->data;
printf("deleted item
is:%d\n",item);
l->next=NULL;
l=l->next;
}
}
}
}
/* END OF DELETE FUNCTION */
/* START OF SEARCH FUNCTION */
search()
{
int f=0;
printf("enter the search item:");
scanf("%d",&item);
if(start==NULL)
printf("LIST IS EMPTY");
else
{
for(l=start,i=1;l!=NULL;l=l->next,i++)
if(l->data==item)
{
f=1;
break;
}
if(f==1)
printf("item %d found at position
:%d\n",item,i);
else
printf("item %d not
found\n",item);
}
}
/* END OF SEARCH FUNCTION */
/* START OF SORT FUNCTION */
sort()
{
int t;
if(start==NULL)
printf("LIST IS EMPTY");
else
{
for(l1=start;l1->next!=NULL;l1=l1->next)
{
for(l=start;l->next!=NULL;l=l->next)
if(l->data > l->next->data)
{
t=l->data;
l->data=l->next->data;
l->next->data=t;
}
}
printf("THE SORTED ORDER IS:");
for(l=start;l!=NULL;l=l->next)
printf("%3d",l->data);
}
printf("\n");
}
/* END OF SORT FUNCTION */
/* START OF MERGE FUNCTION */
merge()
{
printf("enter no of elements to be inserted in second list
:");
scanf("%d",&n);
for(j=1;j<=n;j++)
{
l1=start1;
printf("enter the item to be
inserted:");
scanf("%d",&item);
new=malloc(sizeof(struct link));
new->data=item;
new->next=NULL;
if(start1==NULL)
start1=new;
else
{
printf("1.start\n2.middle\n3.end\n");
printf("enter the place to place the
item:");
scanf("%d",&ch);
if(ch==1)
{
new->next=start1;
start1=new;
}
if(ch==2)
{
printf("enter the position to place
item:");
scanf("%d",&p);
for(i=1;i<p-1;i++)
l1=l1->next;
new->next=l1->next;
l1->next=new;
}
if(ch==3)
{
while(l1->next!=NULL)
l1=l1->next;
l1->next=new;
}
}
}
if(start==NULL)
start=start1;
else
{
l=start;
while(l->next!=NULL)
l=l->next;
for(l1=start1;l1->next!=NULL;l1=l1->next)
{
l->next=l1;
l=l->next;
}
}
printf(" *** LIST IS MERGED ***
\n");
}
/* END OF MERGE FUNCTION */
/* START OF REVERSE FUNCTION */
reverse()
{
if(start==NULL)
printf("LIST IS EMPTY\n");
else
{
l=start;
l1=t=NULL;
while(l!=NULL)
{
l1=t;
t=l;
l=l->next;
t->next=l1;
}
start=t;
printf(" *** LIST IS REVERSED
***\n");
}
}
/* END OF REVERSE FUNCTION */
***** OUTPUT
*****
**** MENU ****
1.Insertion
2.Deletion
3.Traverse
4.Search
5.Sort
6.Merge
7.Reverse
enter the choice:1
enter the item to be inserted:1
enter the choice:1
enter the item to be inserted:2
1.start
2.middle
3.end
enter the place to place the item:1
enter the choice:1
enter the item to be inserted:3
1.start
2.middle
3.end
enter the place to place the item:3
enter the choice:1
enter the item to be inserted:4
1.start
2.middle
3.end
enter the place to place the item:2
enter the position to place item:3
enter the choice:3
start:2->
1->
4->
last:3->
enter the choice:4
enter the search item:4
item 4 found at position :3
enter the choice:6
enter no of elements to be inserted in second list :3
enter the item to be inserted:5
enter the item to be inserted:6
1.start
2.middle
3.end
enter the place to place the item:1
enter the item to be inserted:7
1.start
2.middle
3.end
enter the
place to place the item:2
enter the
position to place item:2
*** LIST IS MERGED ***
enter the
choice:3
start:2->
1->
4->
3->
6->
7->
last:5->
enter the choice:7
*** LIST IS REVERSED ***
enter the choice:3
start:5->
7->
6->
3->
4->
1->
last:2->
enter the choice:4
enter the search item:1
item 1 found at position :6
enter the choice:5
THE SORTED ORDER IS: 1
2 3 4 5 6 7
enter the choice:2
1.start
2.middle
3.end
enter the place to delete the
item:1
deleted item is:1
enter the choice:2
1.start
2.middle
3.end
enter the place to delete the
item:3
deleted item is:7
enter the choice:2
1.start
2.middle
3.end
enter the place to delete the
item:2
enter the position to delete item:4
deleted item is:5
enter the choice:3
start:2->
3->
4->
last:6->
enter the choice:2
1.start
2.middle
3.end
enter the place to delete the
item:1
deleted item is:2
enter the choice:2
1.start
2.middle
3.end
enter the place to delete the
item:2
enter the position to delete item:2
deleted item is:4
enter the choice:3
start:3->
last:6->
enter the choice:2
1.start
2.middle
3.end
enter the place to delete the
item:2
enter the position to delete item:2
deleted item is:6
enter the choice:2
1.start
2.middle
3.end
enter the place to delete the
item:1
deleted item is:3
enter the choice:3
LIST IS EMPTY
enter the choice:2
NO ITEMS IN THE LIST
enter the choice:8
conclusion: the program is error free
VIVA QUESATIONS:
1) List out the memory allocation functions ?
Ans: malloc(), calloc(),free(), realloc() etc..,
2) Define linked list
?
Ans: Linked list is list whose order is given by links from
one item to the next
3) List out the advantages of linked list ?
Ans: i) Dyanamic data structure
ii) no waste
memory space
iii)
flexibility
No comments:
Post a Comment