C LANGUAGE BOOK |
CIRCULAR SINGLY LINKED LIST
it is same as singly linked list but the last node does not point to null.
Pointer of last node Point to First Node.
A node has two field data and next Pointer.data is the value.and next pointer is the pointer
that point to next node.
traversing the linked list.
Moving through a circular linked list is complicated.but not complicated.
check list is not empty
To traverse a circular linked list you create a pointer and set it to head.
make sure to check that head is not NULL before trying to traverse the list.
we move through the list node one by one until we encounter first node.
Adding nodes to a linked list
Adding nodes to a linked list is relatively easy. We will need to cover the different cases of adding at the beginning, the middle or the end.
adding at the beginning:-
if list is empty.
create a temporary node assign data.
set its next pointer of temporary node to point to temporary node
set head pointer of list to point to temporary node.
if list is not empty
create a temporary node assign data.
set its next pointer of temporary node to point to the starting node of list.
traverse the list to end node.
set its next pointer of end node to point to the temporary node of list.
set the head pointer point to temporary node.
adding at the middle of the linked list specified by Position:-
check List is not Empty
check list is not short.and position exist.
create a temporary node assign data.
go the poistion specified.
set the next pointer of temporary node to point to next node specified by position.
set the next pointer of previous node specified by position to point to temporary node.
adding at the end of the linked list :-
if list is empty.then add it like add at beginning.
if list is not empty.
create a temporary node assign data.
set the next pointer of temporary node to point to starting node.
go to the last node of the linked list.
set its next pointer to point to temporary node.
deleting at the beginning:-
check list is not empty.
check list is having one node.
if so assign the node to temporary node
set head pointer of list to point to null.
free the temporary node.
check if list is having more than one node.
assign the starting node to temporary node
go to the end node.set next pointer of it to point to next node of starting node.
point the head pointer to point to next node of starting node.
free the temporary node.
deleting at the middle specified by position:-
check List is not Empty
check list is not short.and position exist.
go the position specified.
assign the node to temporary node
assign the next pointer of previous node of that node to point
to next node of that node.
free temporary node.
deleting at the end :-
check List is not Empty
check list is having one node.
if so assign the node to temporary node
set head pointer of list to point to null.
free the temporary node.
check if list is having more than one node.
go to previous node of last node of linked list.
assign the last node to temporary node
set the next pointer of Previous node to point to first node of list.
free temporary node.
/*WAP to Perform Circular Singly Linked List Operation */
#include<alloc.h>
#include<stdio.h>
struct me
{
int data;
struct me *succ;
};
void main()
{
struct me *p;
int j,m,n;
do
{
printf("\n\tCIRCULAR LINKED LIST");
printf("\n\t1.INSERTION");
printf("\n\t2.DELETION");
printf("\n\t3.DISPLAY");
printf("\n\t4.EXIT\n");
printf("\n\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 4): ");
scanf("%d", &j);
printf("\n");
switch(j)
{
case 1: Insertion(&p);
break;
case 2: Deletion(&p);
break;
case 3: Display(p);
printf("\n");
break;
case 4: exit(1);
default : err_msg(3);
}
}while(j>=1 && j<=4);
}
Insertion(struct me **q)
{
int i,m,n;
char ch[15];
do
{
printf("\n\tINSERTION");
printf("\n\t1.INSERT AT BEGINNING");
printf("\n\t2.INSERT AT POSITION");
printf("\n\t3.INSERT AT END");
printf("\n\t4.RETURN\n");
printf("\n\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 4): ");
scanf("%d", &i);
printf("\n\n i=%d ",i);
printf("\n");
switch(i)
{
case 1: printf("ENTER THE NUMBER : ");
scanf("%d", &m);
AddAtBeg(&(*q),m);
printf("\n");
break;
case 2: printf("ENTER THE NUMBER : ");
scanf("%d", &m);
printf("ENTER THE POSITION : ");
scanf("%d", &n);
AddAtPos(*q , m, n);
printf("\n");
break;
case 3: printf("ENTER THE NUMBER : ");
scanf("%d", &m);
AddAtEnd(&(*q) , m);
printf("\n");
break;
case 4: return;
default : err_msg(3);
}
}while(i>=1 && i<=4);
}
Deletion(struct me **q)
{
int i,m,n;
do
{
printf("\n\tDELETION");
printf("\n\t1.DELETION AT BEGINNING");
printf("\n\t2.DELETION AT POSITION");
printf("\n\t3.DELETION AT END");
printf("\n\t4.RETURN\n");
printf("\n\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 4): ");
scanf("%d", &i);
printf("\n");
switch(i)
{
case 1: DeleteAtBeg(&(*q));
printf("\n");
break;
case 2: printf("ENTER THE POSITION : ");
scanf("%d", &n);
DeleteAtPos(*q ,n);
printf("\n");
break;
case 3: DeleteAtEnd(&(*q));
printf("\n");
break;
case 4: return;
default : err_msg(3);
}
}while(i>=1 && i<=4);
}
AddAtBeg(struct me **q,int x)
{
struct me *p,*w;
p = *q;
if(p == NULL)
{
w = malloc(sizeof(struct me));
w->data = x;
w->succ = w;
*q = w;
}
else
{
w = malloc(sizeof(struct me));
w->data = x;
w->succ = *q;
while(p->succ != *q)
{
p = p->succ;
}
p->succ = w;
*q = w;
}
return;
}
AddAtPos(struct me *q,int x,int y)
{
struct me *p,*w,*z;
int i;
w = q;
z = q;
if(w == NULL)
{
err_msg(5);
return;
}
else
{
for(i = 0; i < y; i++)
{
z = z->succ;
if(z == NULL)
{
printf("\tTHERE ARE LESS THAN %d ELEMENTS IN THE LIST", y);
return;
}
}
printf("\tHEELLOIOYUO \n");
p = malloc(sizeof(struct me));
p->data = x;
p->succ = z->succ;
z->succ = p;
return;
}
}
AddAtEnd(struct me **q, int y)
{
struct me *p,*w,*z;
p = *q;
if(p == NULL)
{
p = malloc(sizeof(struct me));
p->data = y;
p->succ = p;
*q = p;
return;
}
else
{
for(z = *q; z->succ != *q; z = z->succ)
{
}
w = malloc(sizeof(struct me));
w->data = y;
w->succ = z->succ;
z->succ = w;
return;
}
}
DeleteAtBeg(struct me **q)
{
struct me *p,*w,*z;
p = *q;
if(p == NULL)
{
err_msg(1);
}
else
{
if(p->succ == *q)
{
printf("THE LIST");
*q = NULL;
free(p);
}
else
{
w = p;
*q = p->succ;
for(p = p->succ ; p->succ != w ; p = p->succ)
{
}
p->succ = *q;
free(w);
}
}
return;
}
DeleteAtPos(struct me *q,int x)
{
struct me *p,*w, *z;
int i;
p = q;
w = q;
if(p == NULL)
{
err_msg(6);
}
else
{
for(i = 0; i < x; i++)
{
w = w->succ;
if(w == NULL)
{
printf("CANNOT DELETE THERE ARE LESS THAN %d \n ELEMENTS IN THE LIST", x);
return;
}
}
z = w->succ;
w->succ = z->succ;
free(z);
return;
}
}
DeleteAtEnd(struct me **q)
{
struct me *p,*z;
p = *q;
if(p == NULL)
{
err_msg(1);
}
else
if(p->succ == *q)
{
*q = NULL;
free(p);
}
else
{
for(p = *q ; p->succ->succ != *q ; p = p->succ)
{
}
z = p->succ;
p->succ = p->succ->succ;
free(z);
}
return;
}
Display(struct me *q)
{
struct me *z;
z = q;
if(z == NULL)
{
err_msg(1);
return;
}
else
{
for(z = q ; z->succ != q ; z = z->succ)
{
printf("\n%d", z->data);
}
printf("\n%d", z->data);
}
return;
}
err_msg(int p)
{
if(p==1)
printf("THE LIST IS EMPTY");
if(p==2)
printf("HELLO");
if(p==3)
printf("WRONG CHOICE");
if(p==4)
printf("THE LIST IS ALREADY SORTED");
if(p==5)
printf("\nINSERTION AT POS REQUIRED ONE NODE");
if(p==6)
printf("\nDELETION AT POS REQUIRED TWO NODE");
}
C LANGUAGE BOOK |
No comments:
Post a Comment