C Program to check whether a graph contains a cycle or not

We will be using the following graph

As we know a graph may or may not contain a cycle i.e a graph which does not contain a cycle is called a tree. We can use either BFS (Breadth First Search) or Depth First Search (DFS) to check whether a graph contains a cycle or not .
So basically here we are carrying out the dfs of a graph and for each graph node we check if its adjaceny list contains a element or node that is already visited. A graph may have cycle if and only if if there exists a back link to node predecessor from its ancestors.
Here we will be using the same array visited as in DFS to keep track of the nodes that are visited.
Below is the C implementation of the same.

#include<stdio.h>
#include<stdlib.h>
int visited[10]={0,0,0,0};//take it to the no of nodes in graph ,or allocate memory dynamically
int flag=0;
struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}
void dfs(int x,struct graph *g)
{
struct node *temp;
if(visited[x]==1)
{
   flag=1;
   return;
}
else
   {
       printf("%d",x);
       visited[x]=1;

temp=g->array[x];
while(temp)
{
    dfs(temp->a,g);
    temp=temp->next;
}
   }
   return;
}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=4;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<4;i++) //intializing the graph
{
    struct node *n;
    n= (struct node*)malloc(sizeof(struct node));
    n->a=i;
    n->next=NULL;
    g->array[i]=n;
}
addedge(g,0,1); //Creating the graph first here
addedge(g,0,2);
addedge(g,1,2);
addedge(g,2,3);
addedge(g,2,0);
addedge(g,3,3);
printf("DFs=\n");
dfs(2,g);
printf("\n");
if(flag)
printf("There exists a cycle");
else
printf("There does not exists a cycle");
return 0;
}

Output:

Program to implement Depth First Search/traversal in C 

We will be using the following graph :

As we know that the dfs of a graph is similar to the dfs of a tree with the only difference that the graph may have cycles too.

We will be using the same approach as in tree, We start from the starting and traverse its leftmost or rightmost children first and and then its children and so on before traversing its sibling nodes but as we are traversing a graph a node may have link to the already visited node that creates the cycle so that node may be repeated again and this process will continue on ..so inorder to avoid this ambiguity, we will be using an array "visited" to keep track of all nodes that are visited.

We will be using recursion to print all the nodes of the graph. We will first print the starting node then all its adjacent like nodes as passed on the recursive function unlike binary trees where we pass only tree->left and tree->right , Here we will pass all its adjacent elements from its adjaceny list and so on.

Below is the C implementation of the same:

#include<stdio.h>
#include<stdlib.h>
int visited[10]={0,0,0,0};  //take it to the no of nodes in graph ,or allocate memory dynamically
struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}
void dfs(int x,struct graph *g)
{
struct node *temp;
   if(visited[x]==0)
   {
       printf("%d",x);
       visited[x]=1;

temp=g->array[x];
while(temp)
{
    dfs(temp->a,g);
    temp=temp->next;
}
   }
   return;
}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=4;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<4;i++) //intializing the graph
{
    struct node *n;
    n= (struct node*)malloc(sizeof(struct node));
    n->a=i;
    n->next=NULL;
    g->array[i]=n;
}
addedge(g,0,1); //Creating the graph first here
addedge(g,0,2);
addedge(g,1,2);
addedge(g,2,3);
addedge(g,2,0);
addedge(g,3,3);
printf("DFs=\n");
dfs(2,g);
return 0;
}

Output:

Program for Breadth First Search traversal of a graph in C
The graph used is shown below:

As we know the bfs traverses the tree or a graph across the width or say breadth of the graph. The bfs traversal of the graph is very much similar to the bfs of a tree with a difference that unlike trees graphs may have cycle too and we may traverse back to the previous visited node once again in the traversal if the next node that has to be visited has a link to the previously visited nodes.

So, We will be using an array "visit" to store the status of each node whether visited or not.
We will start from node '0' and visits its adjacent nodes using its adjacency list and store all its adjacent nodes in the queue provided its is not already visited using "visit" array, initially the queue contains the starting node i.e. 0

After that we process each element of the queue until it is empty 
The implementation of the above concepts is shown below :

#include<stdio.h>
#include<stdlib.h>
int visited[10];//take it to the no of nodes in graph ,or allocate memory dynamically
struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}

void bfs(struct graph *g)
{
    int i=0,v,f=0,r=0,c;
    struct node *temp;
int array[10],visit[5]={1,0,0,0,0};//we can initialize with only 1 also the rest will get by default to '0'
array[0]=0;
for(i=f;i<=r;i++)
{
    v=array[i];
    printf("%d",v);
    printf(" ");
    temp=g->array[v];
    while(temp->a!=v)
    {
        c=temp->a;
          if(visit[c]==0)
          {
             array[++r]=temp->a;
             visit[c]=1;
          }
        temp=temp->next;
    }
}

}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=5;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<5;i++) //intializing the graph
{
    struct node *n;
    n= (struct node*)malloc(sizeof(struct node));
    n->a=i;
    n->next=NULL;
    g->array[i]=n;
}
addedge(g,0,1); //Creating the graph first here 
addedge(g,0,4);
addedge(g,4,0);
addedge(g,4,1);
addedge(g,4,3);
addedge(g,3,4);
addedge(g,3,1);
addedge(g,3,2);
addedge(g,1,0);
addedge(g,1,2);
addedge(g,1,3);
addedge(g,1,4);
addedge(g,2,1);
addedge(g,2,3);
printf("BFS\n");
bfs(g);
return 0;

}
OUTPUT:

Program for breadth first traversal of a tree in C 

It can be done using many methods
We will be using queue to implement bfs as it consumes space but takes less time due space time trade off

#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left;
struct node *right;
};
void bfs(struct node *r)
{
    int front=0, rear=0;
struct node **queue= (struct node **)malloc(100*sizeof(struct node *));//using array of size 100 to store    the pointers to the node
// the array is the array of pointers and hence pointer to pointer double pointer is used here
//We can also use linked list form of queue but for simplicity we have taken a fixed size 
queue[0]=r;
struct node *temp;
while(queue[front]!=NULL)
{
temp=queue[front];
printf("%d",temp->key);
printf(" ");
if(temp->left)
{
  queue[++rear]=temp->left;
}
if(temp->right)
{
    queue[++rear]=temp->right;
}
front++;
}

}
int main()
{
struct node * root;
root= (struct node *)malloc(sizeof(struct node));
root->key=1;
struct node*temp;
//Lets First Create the tree
temp= (struct node *)malloc(sizeof(struct node));
temp->key=2;
temp->left=NULL;
temp->right=NULL;
root->left=temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->key=3;
temp->left=NULL;
temp->right=NULL;
root->right=temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->key=4;
temp->left=NULL;
temp->right=NULL;
root->left->left=temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->key=5;
temp->left=NULL;
temp->right=NULL;
root->left->right=temp;
bfs(root);

return 0;
}

Output:

C Program to implement graphs 

As we know that a graph is generally represented using two notations 
namely 1) Adjacency Matrix 2) Adjacency List 
The first representation is pretty much simple but later is important one.
The choice of using either representation depends upon the task you are performing with the graph.
When the graph is sparse (i.e having less no. of edges we uses Adjacency List as it consumes less space when there are less no of edges in a graph)

Here is the implementation of the same 
The graph used here is :

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}
void printgraph(struct graph *g)
{
    struct node *temp;
    int i;
    printf("Adjaceny List representation of the graph is \n ");
    for(i=0;i<g->v;i++)
    {
        temp = g->array[i];
        printf("%d->",i);
        while(temp)
        {
            printf("%d->",temp->a);
            temp=temp->next;
        }
        printf("\n");
    }
}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=5;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<5;i++) //intializing the graph
{
    g->array[i]=NULL;
}
addedge(g,0,1);
addedge(g,0,4);
addedge(g,4,0);
addedge(g,4,1);
addedge(g,4,3);
addedge(g,3,4);
addedge(g,3,1);
addedge(g,3,2);
addedge(g,1,0);
addedge(g,1,2);
addedge(g,1,3);
addedge(g,1,4);
addedge(g,2,1);
addedge(g,2,3);
printgraph(g);

return 0;

}
Output:

Program to connect nodes at the same level in the tree

For eg. We are given the tree in the figure(a) and we need to connect the tree node as shown in the figure (b)

#include<stdio.h>
#include<stdlib.h>
struct Tree
{
int key;
struct Tree* left;
struct Tree *right;
struct Tree *nextright;
}*root=NULL;
void displaytree(struct Tree *);
void conASL(struct Tree *);
int main()
{
struct Tree *temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
root =temp;
root->key=2;
root->nextright=NULL;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=3;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=4;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=5;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=6;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left->right=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=7;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=8;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right->right=temp;
conASL(root);
displaytree(root);
return 0;
}
void displaytree(struct Tree *node)
{
    if(node==NULL)
        return;
printf("key=%d",node->key);
if(node->nextright==NULL)
printf("nextright=NULL");
else
printf("nextright=%d",node->nextright->key);
displaytree(node->left);
displaytree(node->right);
}
void conASL(struct Tree *node)
{
    if((node->left==NULL)&&(node->right==NULL))
        return;
    else
    {
        node->left->nextright=node->right;
        if(node->nextright==NULL)
        {
            node->right->nextright=NULL;
        }
        else
        {
        node->right->nextright=node->nextright->left;
        }
   conASL(node->left);
   conASL(node->right);
    }

}

Output:

Program to implement tree using linked list in C 

We will be using the linked list to connect the different nodes of the tree recursively and using preorder traversal to print the vertices of the tree

The sample tree used is :

The above figure shows the binary tree, however build any tree using the approach laid out in the program 

#include<stdio.h>
#include<stdlib.h>
struct Tree
{
int key;
struct Tree* left;
struct Tree *right;
}*root=NULL;
void displaytree(struct Tree *);
int main()
{
struct Tree *temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=5;
root=temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=6;
root->left=temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=7;
temp->left=NULL;
temp->right=NULL;
root->right=temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=8;
temp->left=NULL;
temp->right=NULL;
root->left->left=temp;
temp=(struct Tree *)malloc(sizeof(struct Tree));
temp->key=9;
temp->left=NULL;
temp->right=NULL;
root->left->right=temp;
displaytree(root);
return 0;
}
void displaytree(struct Tree *node)
{
    if(node==NULL)
        return;
printf("key=%d",node->key);
displaytree(node->left);
displaytree(node->right);
}

Output:

Write a program to find length of Longest Common Subsequence(LCS) in two strings using dynamic programming.

#include<stdio.h>
#include<string.h>
void lcs(char*, char*, int, int);
int smax(int, int);
int array[51][51];
int main()
{
char a[50],b[50];
int m,n;
printf("Enter the first sequence \n");
scanf("%s",a);
m=strlen(a);
printf("Enter the second one\n");
scanf("%s",b);
n=strlen(b);
lcs(a,b,m,n);
printf("%d",array[m][n]);
    return 0;
}
void lcs(char *a, char *b,int m , int n)
{
    int i,j;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==0||j==0)
                array[i][j]=0;
                else if(a[i-1]==b[j-1])
                {
                    array[i][j]=1+array[i-1][j-1];
                }
                else
                {
                    array[i][j]=smax(array[i-1][j],array[i][j-1]);
                }
        }
    }
}

int smax(int a, int b)
{
    if(a>b)
        return a;
    else
        return b;

}

Output:

Write a program to find LCS (Longest common subsequence of two strings) using divide and conquer only.
First using divide and conquer only.
So , what is LCS of two strings 
Here is an eg of the same
first consider two strings a and b of lengths m and n respectively
LCS for Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Solution by Divide and Conquer

#include<stdio.h>
#include<string.h>
int lcs(char*, char*, int, int);
int smax(int, int);
int main()
{
char a[50],b[50];
int m,n;
printf("Enter the first sequence \n");
scanf("%s",a);
m=strlen(a);
printf("Enter the second one\n");
scanf("%s",b);
n=strlen(b);
printf("%d",lcs(a,b,m,n));
    return 0;
}
int lcs(char *a, char *b, int m , int n)
{
    if(m==0||n==0)
        return 0;
    else if(a[m-1]==b[n-1])
        return 1+lcs(a,b,m-1,n-1);
    else
        return smax(lcs(a,b,m-1,n),lcs(a,b,m,n-1));
}
int smax(int a,int b)
{
    if(a>b)
    return a;
    else
    return b;

}

Output:-

Calculating Fibonacci series using Dynamic Programming

Normally using divide and conquer algorithm using recurrence relation the complexity reaches to O(2^n) i.e. exponentially 
We can reduce the time the time complexity of the same by avoiding doing the necessary work and saving using reusing our previous work using dynamic programming
Here is an example of the same.
#include<stdio.h>
int sdynamicfib(int);
int table[100]={-1};
int main()
{
 int n,i,temp ;
 printf("Calculating fibonnaci series using dynamic programming\n");
 printf("Enter n");
 scanf("%d",&n);
 for(i=0;i<=n;i++)
 {
     table[i]=-1;
 }
 temp=sdynamicfib(n);
 for(i=0;i<n;i++)
 {
     printf("%d",table[i]);
     printf(" ");
 }
    return 0;
}
int sdynamicfib(int n)
{
    if(n==0||n==1)
    {
        table[n]=n;
        return n;
    }
    else
    {
      if(table[n]==-1)
      {
          if(table[n-1]==-1)
            table[n-1]=sdynamicfib(n-1);
            if(table[n-2]==-1)
            table[n-2]=sdynamicfib(n-2);
          table[n]=table[n-1]+table[n-2];
          return table[n];
      }
    }
}
 Output

Program to find the Hamming distance and edit distance b/w two two DNA strings using dynamic programming in C.

#include<stdio.h>
#include<string.h>
int mymin(int,int,int);
int main()
{
char A[50]="ACACATGATAGACCCTATTAAACCCTTTGGGA";
char B[50]="GGGACACCATAATTTTAAACCGGGGCCGGG";
int array[50][50];
int len1,len2,i,j,count=0,a,b,c,v;
len1= strlen(B);
len2=strlen(A);
for(i=0;i<len1;i++)
{
if(A[i]!=B[i])
{
count++;
}
}
printf("Hamming Distance%d",count);
for(j=0;j<=len1;j++)
{
array[0][j]=j;
}
for(i=0;i<=len2;i++)
{
array[i][0]=i;
}
for(i=1;i<=len2;i++)
{
for(j=1;j<=len1;j++)
{
if(A[i-1]==B[j-1])
{
array[i][j]=array[i-1][j-1];
}
else
{
a=array[i-1][j]+1;
b=array[i][j-1]+1;
c=array[i-1][j-1]+1;
v= mymin(a,b,c);
array[i][j]=v;
}
}
}

printf("The edit distance is %d",array[len2][len1]);
return 0;
}

int mymin(int x, int y,int z)
{
if(x<y&&x<z)
return x;
else if(y<x&&y<z)
return y;
else
return z;

}

Working with Linked List in C 

A Composite linked List Program to carry out the following functions on linked lists:
 1. Create list
 2. Display the list
 3. Sort the elements of the list
 4. Delete the duplicate elements from the list
 5. Insert an element in to the list
 6. Delete an element from the list
 7. Count the no of elements in the list
 8. To get the union of the two lists
 9. To find theintersection of the two lists
 10.To check whether a list is empty or not
 11.To print the list in reverse order
 12.To findout the maximum marks obtained in a given subject
 13.To remove the common elemnts of the list1 which are present in the list2
 14.To carry out the symmetric differences of the lists

Sample Code :

#include<stdio.h>      © Shyam Choudhary 16/2/2015 All Rights Reserved
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<process.h>

struct list
{
int rollno;
char name[30];
char subcode[30];
int marks;
struct list *next;
}*front1=NULL,*rear1=NULL,*front2=NULL,*rear2=NULL,*rear3=NULL,*front3=NULL;
typedef struct list node;
node* create();
void display(node *);
void sort(node*);
void delduplicate(node*);
void insert(node*);
void remove(node*);
void count(node*);
void lunion();
void lintersection();
void isempty(node*);
void printrev(node*);
void maxmarks(node*);
void ldifference();
void sdifference(node*,node*);
void main()
{
clrscr();
int ch,a=1,lch;
do
{
printf("\n 1.Create list ");
printf("\n2. Display the list");
printf("\n 3. Sort the elements of the list");
printf("\n4 .delete the duplicate element sfrom the list ");
printf("\n 5.Insert an element in to the list");
printf("\n 6.Delete an element from the list ");
printf("\n 7.Count the no of elementsin the list");
printf("\n 8.To get the union of the two lists");
printf("\n 9. To find theintersection of the two lists");
printf("\n 10.To check whether a list is empty or not");
printf("\n 11.To print the list in reverse order");
printf("\n 12.To findout the maximum marks obtained in a given subject");
printf("\n13. To remove the common elemnts of the list1 which are present in the list2");
printf("\n 14.To carry out the symmetric differences of the lists");
printf("\n Enter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nwhich list");
printf("\n List 1,List2...Enter 1,2");
scanf("%d",&lch);
if(lch==1)
{
   front1  = create();
}
else
{
      front2  =create();
}
break;
case 2:   printf("\n which list u want to display");
  printf("\n List 1,List2,List3");
  scanf("%d",&lch);
  if(lch==1)
  {
 display(front1);
 }
 else if(lch==2)
 {
 display(front2);
 }
else if(lch==3)
{
  display(front3);
}
 break;
case 3 :  printf("\n Enter the list which u want to sort");
 printf("\n Enter List1,List2,List3Enter 1,2,3");
 scanf("%d",&lch);
 if(lch==1)
 {
 printf("\n List 1 is going to be sorted");
 sort(front1);
 }
 else if(lch==2)
 {
 printf("\n list2 is goig to be sorted");
 sort(front2);
 }
 else if(lch==3)
 {
 printf("\n List3 is gpoiing to be sorted ");
 sort(front3);
 }
 break;
case 4: printf("\n Enter the list from which u want to delete the duplicate records");
printf("\n LIst1,List2,List3....enter 1,2");
scanf("%d",&lch);
if(lch==1)
{
delduplicate(front1);
}
else if(lch==2)
{
delduplicate(front2);
}
else if(lch==3)
{
 delduplicate(front3);
}
 break;
case 5: printf("\n In which list do you want to insert the element");
printf("\n List1,List2,List3....Enter1,2..");
scanf("%d",&lch);
if(lch==1)
{
insert(front1);
}
else if(lch==2)
{
insert(front2);
}
else if(lch==3)
{
insert(front3);
}
break;
case 6: printf("\n enter the list from which u want to delete the record");
printf("\n List 1,List2,List3....enter your choice");
scanf("%d", &lch);
if(lch==1)
{
remove(front1);
}
else if(lch==2)
{
remove(front2);
}
else if(lch==3)
{
remove(front3);
}
break;
case 7: printf("\n Enter the list in which u want to count the no of records");
printf("\n List1,List2,List3....enter1,2,3");
scanf("%d",&lch);
if(lch==1)
{
count(front1);
}
else if(lch==2)
{
count(front2);
}
else if(lch==3)
{
count(front3);
}
break;
case 8: front3 = NULL;
if(front1==NULL)
{
printf("\n First create the lists before taking its union with the other");
}
else if(front2==NULL)
{
printf("\n First create the list2 before taking its union with the other");
}
else
{
lunion();
}
break;
case 9:  front3 = NULL;
printf("\n the intersection of the two lists is going on");
lintersection();
break;
case 10: printf("\n Enter the list which u want to check");
scanf("%d",&lch);
if(lch==1)
{
isempty(front1);
}
else if(lch==2)
{
isempty(front2);
}
else if(lch==3)
{
isempty(front3);
}
break;

case 11 : printf("\n Enter the list which u want to print in the reverse order");
 printf("\n List1,List2,List3....Enter1,2,3");
 scanf("%d",&lch);
 if(lch==1)
 {
 printrev(front1);
 }
 else if (lch==2)
 {
 printrev(front2);
 }
 else if(lch==3)
 {
 printrev(front3);
 }
 break;
case 12: printf("\n Enter the list in which u want to determine the max.marks");
printf("\n List1,List2,List3...\n Enter1,2,3...");
scanf("%d",&lch);
if(lch==1)
{
maxmarks(front1);
}
else if(lch==2)
{
maxmarks(front2);
}
else if(lch==3)
{
maxmarks(front3);
}
break;
case 13 :ldifference();
 break;
case 14 : printf("\n Symmmetric diffence of list1 with respect to List2\n Or") ;
 printf("\n Symmmetric diffence of  List2 with respect to List1");
 printf("\n enter your choice\n Enter1,2...");
 scanf("%d",&lch);
 if(lch==1)
 {
   sdifference(front1,front2) ;
 }
 else if(lch==2)
 {
 sdifference(front2,front1);
 }
 break;
default: printf("\n Wrong choice");
}
printf("\n Want to continue enter 0 to terminate");
scanf("%d",&a);
}while(a!=0);
 getch();
 }
 //------------------begining of create-----------------//
 node* create()
 {
 int lno;
 node * front=NULL,*rear=NULL;
 printf("\n How many elements");
 scanf("%d",&lno);
 for(int i=0;i<lno;i++)
 {
 if(front==NULL)
 {
 front = (node* )malloc(sizeof(node));
 printf("\n Enter the rollno");
 scanf("%d",&front->rollno);
 printf("\n Enter name");
 scanf("%s",front->name);
 printf("\n Enter subcode");
 scanf("%s",front->subcode);
 printf("\n enter the marks");
 scanf("%d",&front->marks);
 front->next=NULL;
 rear=front;
 }
 else
 {
 node *n;
 n= (node* )malloc (sizeof(node));
   printf("\n Enter the rollno");
 scanf("%d",&n->rollno);
 printf("\n Enter name");
 scanf("%s",n->name);
 printf("\n Enter subcode");
 scanf("%s",n->subcode);
 printf("\n enter the marks");
 scanf("%d",&n->marks);
  n->next =NULL;
  rear->next=n;
  rear= n;
  }
  }//----end of for loop-----
  return(front);
  }
  void display(node *r)
  {
  printf("\n the contents of the list are as follows");

  printf("\n-------------------------------------------------------");
  while(r!=NULL)
  {

  printf("\n Rollno = %d",r->rollno);
 printf("\n  Name=%s",r->name);

 printf("\nSubcode=%s",r->subcode);

 printf("\n Marks%d",r->marks);
printf("\n---------------------------------------------------------");
  r= r->next;
  }
  }
  //-----Begining of the sort function--------------//
void sort(node*r)
{
node *temp,*temp1,local;
if(r==NULL)
{
printf("\n the list is empty");
}
else
{
printf("\n sorting the elements of the list");
for( temp= r;temp->next!=NULL;temp=temp->next)
{
for( temp1=temp->next;temp1!=NULL;temp1=temp1->next)
{
      if((temp->rollno)>= temp1->rollno)
      {
if(temp->rollno>temp1->rollno)
{
local.rollno = temp->rollno;
strcpy(local.name,temp->name);
strcpy(local.subcode ,temp->subcode);
local.marks = temp->marks;
   //------------------------//
   temp->rollno= temp1->rollno;
   strcpy(temp->name,temp1->name);
   strcpy(temp->subcode,temp1->subcode);
   temp->marks= temp1->marks;
   //------------------------------//
   temp1->rollno= local.rollno;
strcpy(temp1->name,local.name);
strcpy(temp1->subcode ,local.subcode);
temp1->marks = local.marks;
  //-----------------------------//
  }  //----------End of inner if here---------- //
  else if(temp->rollno== temp1->rollno)
  {
     if( strcmp(temp->subcode,temp1->subcode)>0)
     {
//----swaping on the basis  of the subcode----//
local.rollno = temp->rollno;
strcpy(local.name,temp->name);
strcpy(local.subcode ,temp->subcode);
local.marks = temp->marks;
   //------------------------//
   temp->rollno= temp1->rollno;
   strcpy(temp->name,temp1->name);
   strcpy(temp->subcode,temp1->subcode);
   temp->marks= temp1->marks;
   //------------------------------//
   temp1->rollno= local.rollno;
strcpy(temp1->name,local.name);
strcpy(temp1->subcode ,local.subcode);
temp1->marks = local.marks;
//----------------------------------//
     }  //-----end of innners else if if's ----//
  } //-------end of else if---//
      } //-----end of outer if with in the nested loop---//
}
}
}
}
//------------Begining of delduplicate function here--------
void delduplicate(node*r)
{
node *reach,*t,*temp,*temp1 ;
if(r==NULL)
{
printf("\n The list is empty");
}
else
{
printf("\n deleting the duplicate records from the list");
for( temp= r;temp->next!=NULL;temp=temp->next)
{
for( temp1=temp->next;temp1!=NULL;temp1=temp1->next)
{
if((temp->rollno==temp1->rollno)&&(strcmp(temp->subcode,temp1->subcode)==0))
{
    if(temp1->next==NULL)
    {
       reach= r;
       while(reach->next!=temp1)
{
reach= reach->next;
}
       reach->next= NULL;
    t= temp1;
    free(t);
    }
    else
    {
     reach= r;
     while(reach->next!=temp1)
{
reach= reach->next;
}
t= temp1;
reach->next=temp1->next;
free(t);
    }
}
}//---end of inner for
}  //----end of outer for
} //---end of else just above the function ending-----
}
//-------begining of insert function------------

void insert(node *r)
{
node *i,*temp,*rr;
int f=0;
if(r==NULL)
{
printf("\n the list is empty");
}
else
{
//sort(r);
//delduplicate(r);
i= (node*)malloc(sizeof(node));
printf("\n Enter the subject record of the student \nwhich u want to insert in the list");
 printf("\n Enter the rollno");
 scanf("%d",&i->rollno);
 printf("\n Enter name");
 scanf("%s",i->name);
 printf("\n Enter subcode");
 scanf("%s",i->subcode);
 printf("\n enter the marks");
 scanf("%d",&i->marks);
 i->next=NULL;
 for( temp= r;temp!=NULL;temp=temp->next)
 {
 if((temp->rollno==i->rollno)&&(strcmp(temp->subcode,i->subcode)==0))
 {
 printf("\n The record already exists in the list ");
 printf("\n unable to update the record");
 f=1;
 }
 }
 if((temp==NULL)&&(f==0))
 {
 if(r==front1)
 {
  rr= front1;
  while(rr->next!=NULL)
  {
    rr= rr->next;
  }
  rear1= rr;
 rear1->next= i;
// sort(front1);
 printf("\n the record is succesfully updated the list1");
 }
 else if(r==front2)
 {
 rr = front2;
 while(rr->next!=NULL)
 {
 rr= rr->next;
 }
 rear2= rr;
 rear2->next=i;
// sort(front2);
 printf("\n the record is succesfully updated in the list2");
 }
 }

} //----end of else just above the end of function------//
}
//------count function starts here -----//
void count(node*r)
{
int count =0;
if(r==NULL)
{
printf("\n the list is empty");
}
else
{
printf("\m counting the no of records in the list");
while(r!=NULL)
{
count++;
r= r->next;
}
printf("\n  the np pf records in the given list is %d",count);
} //----end of else just above the function end -------//
}
void remove(node* r)
{
node *temp,*t,*local;
temp= r;
int ele,found=0;
char sub[30];
if(r==NULL)
{
printf("\n the list is empty");
}
else
{
printf("\n Enterthe rollno and subject code of the subject record \nwhich u want to delete ");
printf("\n enter rollno");
scanf("%d",&ele);
printf("\n enter subject code");
scanf("%s",sub);
while(!(temp->rollno==ele)&&(strcmp(temp->subcode,sub)==0))
{
   temp= temp->next;
}  //------end of searching while--------//
 if(temp==NULL)
 {found =0;

 }
 else
 {
  found =1;
printf("\n the record is fpound in the list ");
printf("\n Now deleting the record from the list");
if(temp==r)
{
  if((temp->next==NULL)&&(temp==r))
  {
     t= r;
  if(r==front1)
  {
  front1=NULL;
  free(t);
  printf("\n th element is succesfully deleted from the list");
  printf("\n Now after the deletion the list1 is empty");
  }
  if(r==front2)
  {
  front2=NULL;
  free(t);
  printf("\n the element is succesfully deleted from the list");
  printf("\n Now after the deletion the list2 is empty");
  }
  }
 else if(r==front1)
  {
  front1= front1->next;
  r = r->next;
  free(temp);
  printf("\n the record is succesfully deleted from the list");
  }
  else if(r==front2)
  {
  front2= front2->next;
  r= r->next;
  free(temp);
  printf("\n The record is succesfully deleted from the  list");
  }

}//----- end of bigger if------//
else if(temp->next==NULL)
{
 t= r;
 while(t->next!=temp)
 {
 t= t->next;
 }
 t->next=NULL;
 free(temp);
 printf("\n the element is succesfully deleted  from the list");
}
//------case3-----begins here---------//
else
{
   t= r;
   while(t->next!=temp)
   {
   t= t->next;
   }
    local= temp;
    t->next= temp->next;
    free(local);
    printf("\n the element is succesfully deleted from the list");

}

 }   //---end of else in case element is record in the list--------//
if(found==0)
{
printf("\n the element is notnfound n the list");
}
}  //-------end of else just above the function end----//
}
//-------lunion function starts here----------//
void lunion()
{
node * temp1,*temp2;
printf("\n the union of the two lists is taking place");
 delduplicate(front1);
 delduplicate(front2);
 sort(front1);
 sort(front2);
  for( temp1= front1;temp1!=NULL;temp1= temp1->next)
  {
  for(temp2= front2;temp2!=NULL;temp2= temp2->next)
  {
  if(((temp1->rollno)==(temp2->rollno))&&(strcmp(temp1->subcode,temp2->subcode)==0))
  {
  if(front3==NULL)
  {
   node *n1;
   n1=(node*)malloc(sizeof(node));
   front3=n1;
//    front3= temp1;   assigning the valuesin the respective structures//
    n1->rollno = temp1->rollno;
    strcpy(n1->name,temp1->name);
    strcpy(n1->subcode,temp1->subcode);
    n1->marks = temp1->marks;
    n1->next=NULL;
    front3 = n1;
    rear3=front3;
  }
  else
  {
  node *n1;
  n1 = (node*)malloc(sizeof(node));
   n1->rollno = temp1->rollno;
    strcpy(n1->name,temp1->name);
    strcpy(n1->subcode,temp1->subcode);
    n1->marks = temp1->marks;
    n1->next=NULL;
   rear3->next=n1;
   rear3 = n1;

  }
  }//-----end of if enclosing the equality case -----//
  else
  {
    if(front3==NULL)
    {
    node *n1;
    n1= (node*)malloc(sizeof(node));
//       front3= temp1;     assignining the values of th estructures---//
       n1->rollno = temp1->rollno;
    strcpy(n1->name,temp1->name);
    strcpy(n1->subcode,temp1->subcode);
    n1->marks = temp1->marks;
    n1->next=NULL;
    front3= n1;
    rear3= front3;
      //----------------------------------//
node *n2;
   n2 = (node*)malloc(sizeof(node));
 n2->rollno= temp2->rollno;
 strcpy(n2->name,temp2->name);
 strcpy(n2->subcode,temp2->subcode);
 n2->marks= temp2->marks;
 n2->next=NULL;
 rear3->next=n2;
       rear3=n2;
      }    //-------end of if incase of unequlity and if front is null------//
      else
      {
node *n1;
n1 = (node*)malloc(sizeof(node));
    n1->rollno = temp1->rollno;
    strcpy(n1->name,temp1->name);
    strcpy(n1->subcode,temp1->subcode);
    n1->marks = temp1->marks;
    n1->next=NULL;
rear3->next= n1;
rear3 = n1;
   //----------------------------//
   node *n2;
   n2 = (node*)malloc(sizeof(node));
 n2->rollno= temp2->rollno;
 strcpy(n2->name,temp2->name);
 strcpy(n2->subcode,temp2->subcode);
 n2->marks= temp2->marks;
 n2->next=NULL;

rear3->next=n2;
rear3=n2;

      }

   }//-----end of else in case of unequality ----//
  } //---end of inner nested loop------//
  }  //-------end of outer nested loop-----//
delduplicate(front3);
sort(front3);
}
//--------isempty function starts here----------//
void isempty(node *r)
{
if(r==NULL)
{
printf("\n the list is empty");
}
else
{
printf("\n the list is not empty");
}
}
//------function lintersection starts here-----//
void lintersection()
{
int found;
node *temp1,*temp2;
if((front1==NULL)||(front2==NULL))
{
if(front1==NULL)
{
printf("\n List1 is empty");
printf("\n First create the list");
}
else if (front2==NULL)
{
printf("\n Lis2 is empty");
printf("\n firstt create the list2");
}
}//---End of bigger if-------//
else
{
for(temp1= front1;temp1!=NULL;temp1= temp1->next)
{
found =0;
for(temp2= front2;temp2!=NULL;temp2= temp2->next)
{
 if((temp1->rollno==temp2->rollno)&&(strcmp(temp1->subcode,temp2->subcode)==0))
 {
 found =1;
 }
}//----end of inner for----//
if(found==1)
{
 if(front3==NULL)
 {
 node *n;
 n= (node*)malloc(sizeof(node));
 //-----equating n= temp1-----//
  n->rollno= temp1->rollno;
  strcpy(n->name,temp1->name);
  strcpy(n->subcode,temp1->subcode);
  n->marks= temp1->marks;
  n->next= NULL;
  front3 = n;
  rear3= n;
 }
 else
 {
  node *n;
  n = (node*)malloc(sizeof(node));
 n->rollno= temp1->rollno;
  strcpy(n->name,temp1->name);
  strcpy(n->subcode,temp1->subcode);
  n->marks= temp1->marks;
  n->next= NULL;
  rear3->next= n;
  rear3= n;
 }
}//-----end of if found=1--------//

} //---end of outer for----//
}//------end of else just above fthe function end----//
}
//-------function printrev starts here---//
void printrev(node*r)
{
int roll;
char sub[30];
if(r==NULL)
{
printf("\n the list is empty");
printf("\n first create the list");
}
else
{
node *temp = r;
while(temp->next!=NULL)
{
temp = temp->next;
}
roll = temp->rollno;
strcpy(sub,temp->subcode);
printf("\n-----------------------------------------------");
printf("\n printing the list in the reverse order");
printf("\n Rollno=%d",temp->rollno);
printf("\n Name=%s",temp->name);
printf("\n Subject code= %s",temp->subcode);
printf("\n Marks = %d",temp->marks);
printf("\n-----------------------------------------------");
temp= NULL;
while(temp!=r)
{
for(temp=r;temp!=NULL;temp=temp->next)
{
  if((temp->next->rollno==roll)&&(strcmp(sub,temp->next->subcode)==0))
  break;
}
printf("\n Rollno=%d",temp->rollno);
printf("\n Name=%s",temp->name);
printf("\n Subject code= %s",temp->subcode);
printf("\n Marks = %d",temp->marks);
printf("\n------------------------------------------------");
roll =temp->rollno ;
strcpy(sub,temp->subcode);
}
}//----end of else just above the function end---//
}
//----function maxmarks starts here----//
void maxmarks(node *r)
{
char scode[30];
int mmarks=0;
int found=0;
node*temp;
if( r==NULL)
{
printf("\n The list is empty");
printf("\n first create the list");
}
else
{
printf("\n enter the subject code in which u want to determine the max.marks");
scanf("%s",scode);
temp= r;
while(temp!=NULL)
{
 if(strcmp(temp->subcode,scode)==0)
 {  found =1;
   if((temp->marks)>mmarks)
   {
   mmarks = temp->marks;
   }
 }
 temp= temp->next;
}
}//-----end of else just above the function end----//
if(found==0)
{
printf("\n No such subject code exists in the list");
}
else
{
printf("\n The maximum marks obtained in the%s are %d",scode,mmarks);
}
}
void ldifference()
{
node *temp1,*temp2,*l,*t;
if((front1==NULL)&&(front2==NULL))
{
printf("\n Both the lists are empty");
}
else
{
printf("\n the difference of the two lists as going on");
lintersection();
if(front3!=NULL)
{
for(temp1= front1;temp1!=NULL;temp1=temp1->next)
{
for(temp2=front3;temp2!=NULL;temp2=temp2->next)
{
 if((temp1->rollno==temp2->rollno)&&(strcmp(temp1->subcode,temp2->subcode)==0))
  {
    if(temp1==front1)
    {
    l= front1;
    front1 = front1->next;
    free(l);
    }
    else if(temp1->next==NULL)
    {
      t = front1;
      while(t->next!=temp1)
      {
      t = t->next;
      }
      l = t->next;
      t->next= NULL;
      free(l);
    }
    else
    {
      t = front1;
      while(t->next!=temp1)
      {
       t= t->next;
      }
      l = temp1;
      t->next= temp1->next;
      free(l);
    }
  }
}

}

}
else
{
printf("\nthe difference of the list1 with respect to list2 is the list1 itself");
display(front1);
}
}
}
//--------Function sdifference starts here--------//
void sdifference(node*r1,node*r2)
{
node *temp1,*temp2,*l,*t;
if((r1==NULL)&&(r2==NULL))
{
printf("\n Both the list are empty");
printf("\n First create the lists");
}
else
{
lintersection();
if((r1==front1)&&(r2==front2))
{
printf("\n The symmetric difference of the list1 withrespect tp list2 is going on");
if(front3!=NULL)
{
for(temp1= front1;temp1!=NULL;temp1=temp1->next)
{
for(temp2=front3;temp2!=NULL;temp2=temp2->next)
{
 if((temp1->rollno==temp2->rollno)&&(strcmp(temp1->subcode,temp2->subcode)==0))
  {
    if(temp1==front1)
    {
    l= front1;
    front1 = front1->next;
    free(l);
    }
    else if(temp1->next==NULL)
    {
      t = front1;
      while(t->next!=temp1)
      {
      t = t->next;
      }
      l = t->next;
      t->next= NULL;
      free(l);
    }
    else
    {
      t = front1;
      while(t->next!=temp1)
      {
       t= t->next;
      }
      l = temp1;
      t->next= temp1->next;
      free(l);
    }
  } //----end of if in case the record matches with the other------//
}  //----end of inner nested for-------//

}  //---end of outer for loop----//

}  //-----end of if checking whether the list3 is not empty---//
else
{
printf("\nthe difference of the list1 is the list itself");
display(front1);
}

}//------end of if checking for the nodes----------//
else if((r1==front2)&&(r2==front1))
{
printf("\n the symmetric difference of the list2 with respect to List1 is going on");
if(front3!=NULL)
{
for(temp1= front2;temp1!=NULL;temp1=temp1->next)
{
for(temp2=front3;temp2!=NULL;temp2=temp2->next)
{
 if((temp1->rollno==temp2->rollno)&&(strcmp(temp1->subcode,temp2->subcode)==0))
  {
    if(temp1==front2)
    {
    l= front2;
    front2 = front2->next;
    free(l);
    }
    else if(temp1->next==NULL)
    {
      t = front2;
      while(t->next!=temp1)
      {
      t = t->next;
      }
      l = t->next;
      t->next= NULL;
      free(l);
    }
    else
    {
      t = front2;
      while(t->next!=temp1)
      {
       t= t->next;
      }
      l = temp1;
      t->next= temp1->next;
      free(l);
    }
  } //----end of if in case the record matches with the other------//
}  //----end of inner nested for-------//

}  //---end of outer for loop----//

}  //-----end of if checking whether the list3 is not empty---//
else
{
printf("\nthe difference of the  list2 with respect to the list1 is the list itself");
display(front2);
}
}//---end of else if checking for the nodes----//
}//-----end of else just above the function end-----//
}