/* IMPLEMENTATION OF THE STACK USING ARRAYS */
# include
# include
# include
# include
# define size 100
int top = -1;
int flag = 0;
int stack[size];
void push(int *, int);
int pop(int *);
int peep(int *);
int update (int *);
void display(int *);
/* Definition of the push function */
void push(int s[], int d)
{
if(top ==(size-1))
flag = 0;
else
{
flag = 1;
++top;
s[top] = d;
}
}
/* Definition of the pop function */
int pop(int s[])
{
int popped_element;
if(top == -1)
{
popped_element = 0;
flag = 0;
}
else
{
flag = 1;
popped_element = s[top];
--top;
}
return (popped_element);
}
/* Definition of the push function */
int peep(int s[])
{
int i;
int peep_element;
printf("\n Input the information number to which you want to see: ");
scanf("%d", &i);
if(top - i + 1 <>
{
peep_element = 0;
flag = 0;
}
else
{
flag = 1;
peep_element = s[top - i + 1];
}
return (peep_element);
}
/* Definition of the change function */
int update(int s[])
{
int i;
int update_element;
printf("\n Input the information number to which you want to update: ");
scanf("%d", &i);
if(top - i + 1 <>
{
update_element = 0;
flag = 0;
}
else
{
flag = 1;
update_element = s[top-i +1];
printf("\n Input the new value: ");
scanf("%d", &s[top-i+1]);
}
return (update_element);
}
/* Definition of the display function */
void display(int s[])
{
int i;
if(top == -1)
printf("\n Stack is empty");
else
{
for(i = top; i >= 0; --i)
printf("\n %d", s[i] );
}
}
/* Function main */
void main()
{
int data;
char choice;
int q = 0;
int top = -1;
clrscr();
do
{
printf("\n\nPush->i Pop->p Peep->e Change->u Quit->q:");
printf("\nInput the choice : ");
do
{
choice = getchar();
choice = tolower(choice);
}
while(strchr("ipeuq",choice)==NULL);
printf("Your choice is: %c",choice);
switch(choice)
{
case 'i' :
printf("\n Input the element to push:");
scanf("%d", &data);
push(stack, data);
if(flag)
{
printf("\n After inserting ");
display(stack);
if(top == (size-1))
printf("\n Stack is full");
}
else
printf("\n Stack overflow after pushing");
break;
case 'p' :
data = pop(stack);
if(flag)
{
printf("\n Data is popped: %d", data);
printf("\n Rest data in stack is as follows:\n");
display(stack);
}
else
printf("\n Stack underflow" );
break;
case 'e' :
data = peep(stack);
if(flag)
{
printf("\n Data is peepped: %d", data);
printf("\n Stack is as follows:\n");
display(stack);
}
else
printf("\n Stack underflow");
break;
case 'u' :
data = update(stack);
if(flag)
{
printf("\n Data is peepped: %d", data);
printf("\n Stack is as follows:\n");
display(stack);
}
else
printf("\n Stack underflow");
break;
case 'q':
q = 1;
}
}
while(!q);
}
/* STACK IMPLEMENTATION USING LINKED LIST */
# include
# include
struct link
{
int info;
struct link *next;
} *start;
void display(struct link *);
struct link *push(struct link *);
struct link *pop(struct link *);
int main_menu();
void display(struct link *rec)
{
while(rec != NULL)
{
printf(" %d ",rec->info);
rec = rec->next;
}
}
struct link * push(struct link *rec)
{
struct link *new_rec;
printf("\n Input the new value for next location of the stack:");
new_rec = (struct link *)malloc(sizeof(struct link));
scanf("%d", &new_rec->info);
new_rec->next = rec;
rec = new_rec;
return(rec);
}
struct link * pop(struct link *rec)
{
struct link *temp;
if(rec == NULL)
printf("\n Stack is empty");
else
{
temp = rec->next;
free(rec);
rec = temp;
printf("\n After pop operation the stack is as follows:\n");
display(rec);
if(rec == NULL)
printf("\n Stack is empty");
}
return(rec);
}
int main_menu ()
{
int choice;
do
{
printf("\n 1<-Push ");
printf("\n 2<-Pop");
printf("\n 3<-Quit");
printf("\n Input your choice :");
scanf("%d", &choice);
if(choice <1>3)
printf("\n Incorrect choice-> Try once again");
}
while(choice <1>3);
return(choice);
}
/* main function */
void main()
{
struct link *start ;
int choice;
start = NULL;
do
{
choice = main_menu();
switch(choice)
{
case 1:
start = push(start);
printf("\n After push operation stack is as follows:\n");
display(start);
break;
case 2:
start = pop(start);
break;
default :
printf("\n End of session");
}
}
while(choice != 3);
}
/*DOUBLI LINKLIST */
#include
#include
struct linklist
{
struct linklist *llink;
int no;
struct linklist *rlink;
};
typedef struct linklist node;
node *creat(node *,int);
node *front_insert(node *,int );
node *middle_insert(node *,int ,int );
node *end_insert(node *,int );
node *front_delete(node *);
node *middle_delete(node *,int);
node *end_delete(node *);
void search(node *,int );
void count(node *);
void copy(node *);
node *sort(node *);
void reverse(node *);
void display(node *);
int flag=1;
void main()
{
node *head,*t;
int n,i,ch,x,ich,dch;
clrscr();
head=NULL;
menu:
clrscr();
printf("\n\n\n\n\t\t\t\tMENU");
printf("\n\t\t\t1.Create");
printf("\n\t\t\t2.Insert");
printf("\n\t\t\t3.Delete");
printf("\n\t\t\t4.Search");
printf("\n\t\t\t5.Display");
printf("\n\t\t\t6.Count");
printf("\n\t\t\t7.Copy");
printf("\n\t\t\t8.Sort");
printf("\n\t\t\t9.Reverse");
printf("\n\t\t\t0.Exit");
printf("\n\n\nEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
head=NULL;
printf("How many elements you want to enter: ");
scanf("%d",&n);
for(i=0;i { printf("Enter the element: "); scanf("%d",&x); head=creat(head,x); } break; case 2: goto insertmenu; case 3: goto deletemenu; case 4: printf("Which element you want to search: "); scanf("%d",&x); search(head,x); break; case 5: display(head); break; case 6: count(head); break; case 7: copy(head); break; case 8: sort(head); printf("\n\n\nSorting is perform successfully..."); break; case 9: reverse(head); printf("\n\n\nReverse is perform successfully..."); break; case 0: exit(1); default : printf("\n\nInvalid choice..."); break; } printf("\n\n\nPress any key to continue..."); getch(); goto menu; insertmenu: clrscr(); printf("\n\n\n\n\t\t\t\tMENU"); printf("\n\t\t\t1.Insert at Front"); printf("\n\t\t\t2.Insert in Middle"); printf("\n\t\t\t3.Insert at End"); printf("\n\t\t\t4.Back to main menu"); printf("\n\n\nEnter your choice: "); scanf("%d",&ich); switch(ich) { case 1: printf("Enter any no.: "); scanf("%d",&n); head=front_insert(head,n); break; case 2: printf("Enter any no.: "); scanf("%d",&n); printf("After which element: "); scanf("%d",&x); head=middle_insert(head,n,x); break; case 3: printf("Enter any no.: "); scanf("%d",&n); head=end_insert(head,n); break; case 4: goto menu; default : printf("\n\nInvalid choice..."); break; } printf("\n\nSuccessfully Inserted..."); printf("\n\n\nPress any key to continue..."); getch(); goto insertmenu; deletemenu: flag=1; clrscr(); printf("\n\n\n\n\t\t\t\tMENU"); printf("\n\t\t\t1.Delete from Front"); printf("\n\t\t\t2.Delete from Middle"); printf("\n\t\t\t3.Delete from End"); printf("\n\t\t\t4.Back to main menu"); printf("\n\n\nEnter your choice :"); scanf("%d",&dch); switch(dch) { case 1: head=front_delete (head); break; case 2: printf("Which element you want to delete: "); scanf("%d",&x); head=middle_delete (head,x); break; case 3: head=end_delete (head); break; case 4: goto menu; default : printf("\n\nInvalid choice..."); break; } if(flag==1) printf("\n\nSuccessfully Deleted..."); printf("\n\n\nPress any key to continue..."); getch(); goto deletemenu; } node *creat(node *head,int n) { node *temp,*new1; temp=head; new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->llink=new1; new1->no=n; new1->rlink=new1; head=new1; } else { temp=head; while(temp->rlink!=head) temp=temp->rlink; new1->no=n; new1->llink=temp; new1->rlink=head; temp->rlink=new1; head->llink=new1; } return(head); } node *front_insert(node *head,int n) { node *new1,*temp; new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->llink=head; new1->no=n; new1->rlink=head; head=new1; } else { temp=head; while(temp->rlink!=head) temp=temp->rlink; new1->no=n; new1->rlink=head; head->llink=new1; temp->rlink=new1; new1->llink=temp; head=new1; } return(head); } node *middle_insert(node *head,int n,int x) { node *temp,*new1; temp=head; new1=(node *)malloc(sizeof(node)); if(head==NULL) { printf("List is Empty...\n Cann't insert in Middle..."); return(head); } else { temp=head; while(temp->no!=x) temp=temp->rlink; new1->no=n; new1->rlink=temp->rlink; temp->rlink->llink=new1; temp->rlink=new1; new1->llink=temp; } return(head); } node *end_insert(node *head,int n) { node *temp,*new1; temp=head; new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->llink=head; new1->no=n; new1->rlink=head; head=new1; return(head); } else { temp=head; while(temp->rlink!=head) temp=temp->rlink; new1->no=n; new1->llink=temp; temp->rlink=new1; new1->rlink=head; head->llink=new1; } return(head); } node *front_delete (node *head) { node *temp,*htemp; if(head==NULL) { printf("List is empty...\n Cann't Delete..."); return(head); } else { temp=head; htemp=head; while(temp->rlink!=head) temp=temp->rlink; head=htemp->rlink; head->llink=temp; temp->rlink=head; free(temp); } return(head); } node *middle_delete (node *head,int x) { node *temp,*temp1; temp=head; if(head==NULL) { printf("List is Empty....\n Cann't delete from Middle..."); return(head); } else { temp=head; while((temp->rlink->no!=x)&&(temp!=NULL)) { if (temp->rlink->rlink->no==x) flag=1; else flag=0; temp=temp->rlink; } if (flag==1) { temp->rlink=temp->rlink->rlink; temp1=temp->rlink->rlink; temp1->llink=temp; } else printf("\n\n\nGiven node is not exist in list..." ); } return(head); } node *end_delete (node *head) { node *temp; temp=head; if(head==NULL) { printf("List is Empty....\n Cann't Delete ..."); return(head); } else { temp=head; while(temp->rlink->rlink!=head) temp=temp->rlink; temp->rlink=head; } return(head); } void search(node *head,int x) { node *temp; int c=1,flag=0; temp=head; while((flag==0)&&(temp->rlink!=head)) { if (temp->no==x) { flag=1; break ; } temp=temp->rlink; c++; } if (flag==1) printf("\n\nGiven element is stored at %d position in list...",c); else printf("\n\nElement %d is not in the linklist...",x); } void count(node *head) { node *temp; int c=0; temp=head; do { temp=temp->rlink; c++; } while(temp!=head); printf("Total elements in list are %d... ",c); } void copy(node *head) { node *temp,*new1=NULL,*head1=NULL,*temp1; temp=head; while(temp!=NULL) { new1=(node *)malloc(sizeof(node)); new1->llink=NULL; new1->no=temp->no; new1->rlink=NULL; temp=temp->rlink; if (head1==NULL) head1=new1; else { temp1=head1; while(temp1->rlink!=NULL) temp1=temp1->rlink; temp1->rlink=new1; new1->llink=temp1; } } printf("\n\nOriginal link list is: "); display(head); printf("\n\nNew copied link list is: "); display(head1); } node *sort(node *head) { node *temp,*temp1,*temp2; int no1; temp=head; do { temp1=temp; temp2=temp->rlink; do { if(temp->no>temp2->no) { no1=temp->no; temp->no=temp2->no; temp2->no=no1; } temp2=temp2->rlink; temp1=temp1->rlink; } while(temp2!=head); temp=temp->rlink; } while(temp->rlink!=head); return(head); } void reverse(node *head) { node *temp,*new1,*head1,*htemp; temp=head; do { if(temp==head) { new1=(node *)malloc(sizeof(node)); new1->llink=new1; new1->no=temp->no; new1->rlink=new1; head1=new1; } else { htemp=head1; while(htemp->rlink!=head1) htemp=htemp->rlink; new1=(node *)malloc(sizeof(node)); new1->no=temp->no; new1->rlink=head1; new1->llink=htemp; htemp->rlink=new1; head1->llink=new1; head1=new1; } temp=temp->rlink; } while(temp!=head); printf("\n\nOriginal link list is: "); display(head); printf("\n\nReverse link list is: "); display(head1); } void display(node *head) { node *temp; temp=head; do { printf("%d ->",temp->no); temp=temp->rlink; } while(temp!=head); printf("NULL"); } /* SINGLE LINK LIST */ #include #include struct linklist { int no; struct linklist *next; }; typedef struct linklist node; node *creat(node *,int); node *front_insert(node *,int ); node *middle_insert(node *,int ,int ); node *end_insert(node *,int ); node *front_delete(node *); node *middle_delete(node *,int); node *end_delete(node *); node *sort(node *); void search(node *,int ); void count(node *); void copy(node *); void reverse(node *); void display(node *); int flag=1; void main() { node *head,*t; int n,i,ch,x,ich,dch; clrscr(); head=NULL; menu: clrscr(); printf("\n\n\n\n\t\t\t\tMENU"); printf("\n\t\t\t1.Create"); printf("\n\t\t\t2.Insert"); printf("\n\t\t\t3.Delete"); printf("\n\t\t\t4.Search"); printf("\n\t\t\t5.Display"); printf("\n\t\t\t6.Count"); printf("\n\t\t\t7.Copy"); printf("\n\t\t\t8.Sort"); printf("\n\t\t\t9.Reverse"); printf("\n\t\t\t0.Exit"); printf("\n\n\nEnter your choice: "); scanf("%d",&ch); switch(ch) { case 1: printf("How many elements you want to enter: "); scanf("%d",&n); for(i=0;i { printf("Enter the element: "); scanf("%d",&x); head=creat(head,x); } break; case 2: goto insertmenu; case 3: goto deletemenu; case 4: printf("Which element you want to search: "); scanf("%d",&x); search(head,x); break; case 5: display(head); break; case 6: count(head); break; case 7: copy(head); break; case 8: sort(head); printf("\n\n\nSorting is performed successfully..."); break; case 9: reverse(head); break; case 0 : exit(1); default : printf("\n\nInvalid choice..."); break; } printf("\n\n\nPress any key to continue..."); getch(); goto menu; insertmenu: clrscr(); printf("\n\n\n\n\t\t\t\tMENU"); printf("\n\t\t\t1.Insert at Front"); printf("\n\t\t\t2.Insert in Middle"); printf("\n\t\t\t3.Insert at End"); printf("\n\t\t\t4.Back to main menu"); printf("\n\n\nEnter your choice: "); scanf("%d",&ich); switch(ich) { case 1: printf("Enter any no.: "); scanf("%d",&n); head=front_insert(head,n); break; case 2: printf("Enter any no.: "); scanf("%d",&n); printf("After which element: "); scanf("%d",&x); head=middle_insert(head,n,x); break; case 3: printf("Enter any no.: "); scanf("%d",&n); head=end_insert(head,n); break; case 4: goto menu; default : printf("\n\nInvalid choice..."); break; } printf("\n\nSuccessfully Inserted..."); printf("\n\n\nPress any key to continue..."); getch(); goto insertmenu; deletemenu: flag=1; clrscr(); printf("\n\n\n\n\t\t\t\tMENU"); printf("\n\t\t\t1.Delete from Front"); printf("\n\t\t\t2.Delete from Middle"); printf("\n\t\t\t3.Delete from End"); printf("\n\t\t\t4.Back to main menu"); printf("\n\n\nEnter your choice: "); scanf("%d",&dch); switch(dch) { case 1: head=front_delete (head); break; case 2: printf("Which element you want to delete: "); scanf("%d",&x); head=middle_delete (head,x); break; case 3: head=end_delete (head); break; case 4: goto menu; default : printf("\n\nInvalid choice..."); break; } if(flag==1) printf("\n\nSuccessfully Deleted..."); printf("\n\n\nPress any key to continue..."); getch(); goto deletemenu; } node *creat(node *head,int n) { node *temp,*new1; temp=head; new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->no=n; new1->next=new1; head=new1; } else { temp=head; while(temp->next!=head) temp=temp->next; new1->no=n; new1->next=head; temp->next=new1; } return(head); } node *front_insert(node *head,int n) { node *new1,*temp; new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->no=n; new1->next=head; head=new1; } else { temp=head; while(temp->next!=head) temp=temp->next; new1->no=n; new1->next=head; head=new1; temp->next=head; } return(head); } node *middle_insert(node *head,int n,int x) { node *temp,*new1; temp=head; new1=(node *)malloc(sizeof(node)); if(head==NULL) { printf("List is Empty...\n Cann't Insert in Middle..."); return(head); } else { temp=head; while(temp->no!=x) temp=temp->next; new1->no=n; new1->next=temp->next; temp->next=new1; } return(head); } node *end_insert(node *head,int n) { node *temp,*new1; temp=head; new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->no=n; new1->next=head; head=new1; return(head); } else { temp=head; while(temp->next!=head) temp=temp->next; new1->no=n; temp->next=new1; new1->next=head; } return(head); } node *front_delete (node *head) { node *temp,*htemp; if(head==NULL) { printf("List is Empty...\n Cann't Delete..."); return(head); } else { temp=head; htemp=head; while(temp->next!=head) temp=temp->next; head=htemp->next; temp->next=head; free(temp); } return(head); } node *middle_delete (node *head,int x) { node *temp; temp=head; if(head==NULL) { printf("List is Empty...\n Cann't Delete from Middle..."); return(head); } else { temp=head; while((temp->next->no!=x)&&(temp!=NULL)) { if (temp->next->next->no==x) flag=1; else flag=0; temp=temp->next; } if (flag==1) temp->next=temp->next->next; else printf("\n\n\nGiven node is not exist in list..." ); } return(head); } node *end_delete (node *head) { node *temp; temp=head; if(head==NULL) { printf("List is Empty....\n Cann't Delete ..."); return(head); } else { temp=head; while(temp->next->next!=head) temp=temp->next; temp->next=head; } return(head); } void search(node *head,int x) { node *temp; int c=1,flag=0; temp=head; while((flag==0)&&(temp->next!=head)) { if (temp->no==x) { flag=1; break ; } temp=temp->next; c++; } if (flag==1) printf("\n\nGiven element is stored at %d position in list...",c); else printf("\n\nElement %d is not in the linklist...",x); } void count(node *head) { node *temp; int c=0; temp=head; do { temp=temp->next; c++; } while(temp!=head); printf("Total elements in list are %d... ",c); } void copy(node *head) { node *temp,*new1=NULL,*head1=NULL,*temp1; temp=head; do { new1=(node *)malloc(sizeof(node)); new1->no=temp->no; if (head1==NULL) { new1->next=new1; head1=new1; } else { temp1=head1; while(temp1->next!=head1) temp1=temp1->next; temp1->next=new1; new1->next=head1; } temp=temp->next; } while(temp!=head); printf("\n\nOriginal link list is: "); display(head); printf("\n\nNew copied link list is: "); display(head1); } node *sort(node *head) { node *temp,*temp1,*temp2; int no1; temp=head; while(temp->next!=head) { temp2=temp; temp1=temp->next; while(temp1!=head) { if(temp->no>temp1->no) { no1=temp->no; temp->no=temp1->no; temp1->no=no1; } temp2=temp2->next; temp1=temp2->next; } temp=temp->next; } return(head); } void reverse(node *head) { node *temp,*new1,*head1,*temp1; temp=head; do { if(temp==head) { new1=(node *)malloc(sizeof(node)); new1->no=temp->no; new1->next=new1; head1=new1; } else { temp1=head1; new1=(node *)malloc(sizeof(node)); new1->no=temp->no; new1->next=head1; while(temp1->next!=head1) temp1=temp1->next; temp1->next=new1; head1=new1; } temp=temp->next; } while(temp!=head); printf("\n\nOriginal link list is: "); display(head); printf("\n\nReverse link list is: "); display(head1); } void display(node *head) { node *temp; temp=head; do { printf("%d ->",temp->no); temp=temp->next; } while(temp!=head); printf("NULL"); } /* DOUBLI LINK LIST PERATIONS */ #include #include struct linklist { struct linklist *llink; int no; struct linklist *rlink; }; typedef struct linklist node; node *creat(node *,int); node *concate(node *,node *); node *merge(node *,node *); node *union1(node *head1,node *head2); node *intersec(node *head1,node *head2); node *sort(node *); void display(node *); int flag=1; void main() { node *head1,*head2,*head3,*t; int n,i,ch,x,ich,dch; clrscr(); head1=head2=NULL; menu: clrscr(); printf("\n\n\n\n\t\t\t\tMENU"); printf("\n\t\t\t1.Create"); printf("\n\t\t\t2.Concate"); printf("\n\t\t\t3.Merge"); printf("\n\t\t\t4.Union"); printf("\n\t\t\t5.Intersection"); printf("\n\t\t\t6.Exit"); printf("\n\n\nEnter your choice: "); scanf("%d",&ch); switch(ch) { case 1: printf("How many elements in first linklist: "); scanf("%d",&n); for(i=0;i { printf("Enter the element: "); scanf("%d",&x); head1=creat(head1,x); } printf("How many elements in second linklist: "); scanf("%d",&n); for(i=0;i { printf("Enter the element: "); scanf("%d",&x); head2=creat(head2,x); } printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); break; case 2: printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); printf("\n\nFirst link list after concatenation is: "); head1=concate(head1,head2); display(head1); break; case 3: printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); printf("\n\nFirst link list after merging is: "); head1=merge(head1,head2); display(head1); break; case 4: printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); printf("\n\nResultant Union link list is: "); head3=union1(head1,head2); display(head3); break; case 5: printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); printf("\n\nResultant Intersection link list is: "); head3=intersec(head1,head2); display(head3); break; case 6: exit(1); default : printf("\n\nInvalid choice..."); break; } printf("\n\n\nPress any key to continue..."); getch(); goto menu; } node *creat(node *head,int n) { node *temp,*new1; temp=head; new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->llink=NULL; new1->no=n; new1->rlink=NULL; head=new1; } else { temp=head; while(temp->rlink!=NULL) temp=temp->rlink; new1->no=n; new1->rlink=NULL; temp->rlink=new1; new1->llink=temp; } return(head); } node *concate(node *head1,node *head2) { node *temp,*temp1,*new1; temp=head1; temp1=head2; while(temp->rlink!=NULL) temp=temp->rlink; while(temp1!=NULL) { new1=(node *)malloc(sizeof(node)); new1->no=temp1->no; new1->rlink=NULL; temp->rlink=new1; new1->llink=temp; temp1=temp1->rlink; temp=temp->rlink; } return(head1); } node *merge(node *head1,node *head2) { node *head; head=concate(head1,head2); sort(head); return(head); } node *sort(node *head) { node *temp,*temp1,*temp2; int no1; temp=head; while(temp!=NULL) { temp2=temp; temp1=temp->rlink; while(temp1!=NULL) { if(temp->no>temp1->no) { no1=temp->no; temp->no=temp1->no; temp1->no=no1; } temp2=temp2->rlink; temp1=temp2->rlink; } temp=temp->rlink; } return(head); } node *union1(node *head1,node *head2) { node *temp1,*temp2,*head=NULL,*temp,*new1; temp1=head1; while(temp1!=NULL) { new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->llink=NULL; new1->no=temp1->no; new1->rlink=NULL; head=new1; } else { temp=head; while(temp->rlink!=NULL) temp=temp->rlink; new1->no=temp1->no; new1->rlink=NULL; temp->rlink=new1; new1->llink=temp; } temp1=temp1->rlink; } temp=temp->rlink; temp2=head2; while(temp2!=NULL) { temp1=head1; while(temp1!=NULL) { if(temp1->no==temp2->no) { flag=0; break; } else flag=1; temp1=temp1->rlink; } if(flag==1) { new1=(node *)malloc(sizeof(node)); new1->no=temp2->no; new1->rlink=NULL; new1->llink=temp; temp->rlink=new1; temp=temp->rlink; } temp2=temp2->rlink; } return(head); } node *intersec(node *head1,node *head2) { node *temp1,*temp2,*head=NULL,*temp,*new1; temp2=head2; while(temp2!=NULL) { temp1=head1; while(temp1!=NULL) { if(temp1->no==temp2->no) { flag=1; break; } else flag=0; temp1=temp1->rlink; } if(flag==1) { new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->llink=NULL; new1->no=temp1->no; new1->rlink=NULL; head=new1; } else { temp=head; while(temp->rlink!=NULL) temp=temp->rlink; new1->no=temp2->no; new1->rlink=NULL; new1->llink=temp; temp->rlink=new1; temp=temp->rlink; } } temp2=temp2->rlink; } return(head); } void display(node *head) { node *temp; temp=head; while(temp!=NULL) { printf("%d ->",temp->no); temp=temp->rlink; } printf("NULL"); } /* DOUBLI LINK LIST PERATIONS */ #include #include struct linklist { int no; struct linklist *next; }; typedef struct linklist node; node *creat(node *,int); node *concate(node *,node *); node *merge(node *,node *); node *union1(node *head1,node *head2); node *intersec(node *head1,node *head2); node *sort(node *); void display(node *); int flag=1; void main() { node *head1,*head2,*head3,*t; int n,i,ch,x,ich,dch; clrscr(); head1=head2=NULL; menu: clrscr(); printf("\n\n\n\n\t\t\t\tMENU"); printf("\n\t\t\t1.Create"); printf("\n\t\t\t2.Concate"); printf("\n\t\t\t3.Merge"); printf("\n\t\t\t4.Union"); printf("\n\t\t\t5.Intersection"); printf("\n\t\t\t6.Exit"); printf("\n\n\nEnter your choice :"); scanf("%d",&ch); switch(ch) { case 1: printf("How many elements in first linklist: "); scanf("%d",&n); for(i=0;i { printf("Enter the element: "); scanf("%d",&x); head1=creat(head1,x); } printf("How many elements in second linklist: "); scanf("%d",&n); for(i=0;i { printf("Enter the element: "); scanf("%d",&x); head2=creat(head2,x); } printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); break; case 2: printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); printf("\n\nFirst link list after concatination is: "); head1=concate(head1,head2); display(head1); break; case 3: printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); printf("\n\nFirst link list after merging is: "); head1=merge(head1,head2); display(head1); break; case 4: printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); printf("\n\nResultant Union link list is: "); head3=union1(head1,head2); display(head3); break; case 5: printf("\n\nFirst link list is: "); display(head1); printf("\n\nSecond link list is: "); display(head2); printf("\n\nResultant Intersection link list is: "); head3=intersec(head1,head2); display(head3); break; case 6 : exit(1); default : printf("\n\nInvalid choice..."); break; } printf("\n\n\nPress any key to continue..."); getch(); goto menu; } node *creat(node *head,int n) { node *temp,*new1; temp=head; new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->next=NULL; new1->no=n; head=new1; } else { temp=head; while(temp->next!=NULL) temp=temp->next; new1->no=n; new1->next=NULL; temp->next=new1; } return(head); } node *concate(node *head1,node *head2) { node *temp,*temp1,*new1; temp=head1; temp1=head2; while(temp->next!=NULL) temp=temp->next; while(temp1!=NULL) { new1=(node *)malloc(sizeof(node)); new1->no=temp1->no; new1->next=NULL; temp->next=new1; temp1=temp1->next; temp=temp->next; } return(head1); } node *merge(node *head1,node *head2) { node *head; head=concate(head1,head2); sort(head); return(head); } node *sort(node *head) { node *temp,*temp1,*temp2; int no1; temp=head; while(temp!=NULL) { temp2=temp; temp1=temp->next; while(temp1!=NULL) { if(temp->no>temp1->no) { no1=temp->no; temp->no=temp1->no; temp1->no=no1; } temp2=temp2->next; temp1=temp2->next; } temp=temp->next; } return(head); } node *union1(node *head1,node *head2) { node *temp1,*temp2,*head=NULL,*temp,*new1; temp1=head1; while(temp1!=NULL) { new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->no=temp1->no; new1->next=NULL; head=new1; } else { temp=head; while(temp->next!=NULL) temp=temp->next; new1->no=temp1->no; new1->next=NULL; temp->next=new1; } temp1=temp1->next; } temp=temp->next; temp2=head2; while(temp2!=NULL) { temp1=head1; while(temp1!=NULL) { if(temp1->no==temp2->no) { flag=0; break; } else flag=1; temp1=temp1->next; } if(flag==1) { new1=(node *)malloc(sizeof(node)); new1->no=temp2->no; new1->next=NULL; temp->next=new1; temp=temp->next; } temp2=temp2->next; } return(head); } node *intersec(node *head1,node *head2) { node *temp1,*temp2,*head=NULL,*temp,*new1; temp2=head2; while(temp2!=NULL) { temp1=head1; while(temp1!=NULL) { if(temp1->no==temp2->no) { flag=1; break; } else flag=0; temp1=temp1->next; } if(flag==1) { new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->no=temp1->no; new1->next=NULL; head=new1; } else { temp=head; while(temp->next!=NULL) temp=temp->next; new1->no=temp2->no; new1->next=NULL; temp->next=new1; temp=temp->next; } } temp2=temp2->next; } return(head); } void display(node *head) { node *temp; temp=head; while(temp!=NULL) { printf("%d ->",temp->no); temp=temp->next; } printf("NULL"); } /* POLYNOMIAL ADD */ #include #include struct linklist { int coeff; int exp; struct linklist *next; }; typedef struct linklist node; node *creat(node *,int); node *add(node *,node *); void display(node *); int flag=1; void main() { node *head1,*head2,*head3; int m; clrscr(); head1=head2=NULL; printf("Enter total term of first pollynomial : "); scanf("%d",&m); head1=creat(head1,m); printf("Enter total term of second pollynomial : "); scanf("%d",&m); head2=creat(head2,m); printf("\n\nFirst pollynomial : "); display(head1); printf("\n\nSecond pollynomial : "); display(head2); printf("\n\nAddition of both pollynomial is : "); head3=add(head1,head2); display(head3); getch(); } node *creat(node *head,int m) { int i,co,d; node *temp,*new1; temp=head; for(i=1;i<=m;i++) { printf("Enter coefficient :"); scanf("%d",&co); printf("Enter degree :"); scanf("%d",&d); new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->coeff=co; new1->exp=d; new1->next=NULL; head=new1; } else { temp=head; while(temp->next!=NULL) temp=temp->next; new1->coeff=co; new1->exp=d; new1->next=NULL; temp->next=new1; } } return(head); } node *add(node *head1,node *head2) { node *temp1,*temp2,*temp,*head=NULL,*new1; temp1=head1; temp2=head2; while((temp1!=NULL)||(temp2!=NULL)) { new1=(node *)malloc(sizeof(node)); if(temp1->exp==temp2->exp) { new1->coeff=temp1->coeff+temp2->coeff; new1->exp=temp1->exp; new1->next=NULL; if(head==NULL) head=new1; else { temp=head; while(temp->next!=NULL) temp=temp->next; temp->next=new1; } temp1=temp1->next; temp2=temp2->next; } else { if((temp1!=NULL)&&(temp2!=NULL)) { if(temp1->exp>temp2->exp) { new1->coeff=temp1->coeff; new1->exp=temp1->exp; new1->next=NULL; if(head==NULL) head=new1; else { temp=head; while(temp->next!=NULL) temp=temp->next; temp->next=new1; } temp1=temp1->next; } else { new1->coeff=temp2->coeff; new1->exp=temp2->exp; new1->next=NULL; if(head==NULL) head=new1; else { temp=head; while(temp->next!=NULL) temp=temp->next; temp->next=new1; } temp2=temp2->next; } } else if(temp1==NULL) { new1=(node *)malloc(sizeof(node)); new1->coeff=temp2->coeff; new1->exp=temp2->exp; new1->next=NULL; if(head==NULL) head=new1; else { temp=head; while(temp->next!=NULL) temp=temp->next; temp->next=new1; } temp2=temp2->next; } else { new1=(node *)malloc(sizeof(node)); new1->coeff=temp1->coeff; new1->exp=temp1->exp; new1->next=NULL; if(head==NULL) head=new1; else { temp=head; while(temp->next!=NULL) temp=temp->next; temp->next=new1; } temp1=temp1->next; } } } return(head); } void display(node *head) { node *temp; temp=head; while(temp!=NULL) { if(temp->coeff>0) { if(temp->exp==0) printf("+%d",temp->coeff); else printf("+%dX^%d",temp->coeff,temp->exp); } else { if(temp->exp==0) printf("+%d",temp->coeff); else printf("%dX^%d",temp->coeff,temp->exp); } temp=temp->next; } } /* POLYNOMIAL MULTIPLICAION */ #include #include struct linklist { int coeff; int exp; struct linklist *next; }; typedef struct linklist node; node *creat(node *,int); node *mul(node *,node *); void display(node *); int flag=1; void main() { node *head1,*head2,*head3; int m; clrscr(); head1=head2=NULL; printf("Enter total term of first pollynomial : "); scanf("%d",&m); head1=creat(head1,m); printf("Enter total term of second pollynomial : "); scanf("%d",&m); head2=creat(head2,m); printf("\n\nFirst pollynomial : "); display(head1); printf("\n\nSecond pollynomial : "); display(head2); printf("\n\nMultiplication of both pollynomial is : "); head3=mul(head1,head2); display(head3); getch(); } node *creat(node *head,int m) { int i,co,d; node *temp,*new1; temp=head; for(i=1;i<=m;i++) { printf("Enter coefficient :"); scanf("%d",&co); printf("Enter degree :"); scanf("%d",&d); new1=(node *)malloc(sizeof(node)); if(head==NULL) { new1->coeff=co; new1->exp=d; new1->next=NULL; head=new1; } else { temp=head; while(temp->next!=NULL) temp=temp->next; new1->coeff=co; new1->exp=d; new1->next=NULL; temp->next=new1; } } return(head); } node *mul(node *head1,node *head2) { node *temp1,*temp2,*temp,*htemp,*head=NULL,*new1; temp1=head1; temp2=head2; while(temp1!=NULL) { temp2=head2; while(temp2!=NULL) { new1=(node *)malloc(sizeof(node)); new1->coeff=temp1->coeff*temp2->coeff; new1->exp=temp1->exp+temp2->exp; new1->next=NULL; if(head==NULL) head=new1; else { temp=head; while(temp->next!=NULL) temp=temp->next; temp->next=new1; } temp2=temp2->next; } temp1=temp1->next; } temp=head; htemp=temp->next; while(temp!=NULL) { if(temp->exp==htemp->exp) { temp->coeff=temp->coeff+htemp->coeff; temp->next=htemp->next; } else temp=temp->next; if(htemp->next==NULL) break; else htemp=htemp->next; } return(head); } void display(node *head) { node *temp; temp=head; while(temp!=NULL) { if(temp->coeff>0) { if(temp->exp==0) printf("+%d",temp->coeff); else printf("+%dX^%d ",temp->coeff,temp->exp); temp=temp->next; } else if(temp->coeff<0) { if(temp->exp==0) printf("%d",temp->coeff); else printf("%dX^%d ",temp->coeff,temp->exp); temp=temp->next; } else temp=temp->next; } } /* POSTFIX */ # include # include # include # include # define Arnold '\0' # define Blank ' ' # define Tab '\t' # define Maxlen 64 static char infix [Maxlen+1], stack[Maxlen], postfix[Maxlen+1]; # define Empty (-1) /* empty stack */ static int top; /* symbol types */ # define Operator (-10) # define Operand (-20) # define LeftParen (-30) # define RightParen (-40) static char *symbols = "()+-%*/"; /* Symbol precedence */ # define LeftParenPrec 0 /* ( */ # define AddPrec 1 /* + */ # define SubPrec 1 /* - */ # define MultPrec 2 /* * */ # define DivPrec 2 /* / */ # define RemPrec 3 /* % */ # define None 999 /* all else */ void read_input(void); void infix_to_postfix(void); void write_output(void); void push(char symbol); char pop (void); int get_type(char ); int get_prec(char ); int white_space(char ); void full_stack(); void empty_stack(); void main() { char ans[2]; clrscr(); do { top = Empty; /* reset stack */ read_input(); infix_to_postfix(); write_output(); /* Selection */ printf("\n\n Another (y/n)"); gets(ans); } while (toupper(ans[0]) == 'Y'); } /* function infix to postfix conversion */ void infix_to_postfix(void) { int i,p, len, type, precedence; char next ; /* i for infix, p for postfix */ i = p = 0; len = strlen(infix); /* loop through input string */ while(i <> { /* ignore whitepsce in infix expression */ if( !white_space(infix[i])) { type = get_type(infix[i]); switch(type) { /* push left paren onto stack */ case LeftParen: push(infix[i]); break; /* pop stack until matching left paren */ case RightParen: while((next = pop()) != '(') postfix[p++] = next; break; case Operand: postfix[p++] = infix[i]; break; /* Pop stack until first operator of higher precedence and then stack this operator */ case Operator: precedence = get_prec(infix[i]); /* Anything on stack to pop */ while(top > Empty && precedence<= get_prec(stack[top])) postfix[p++] = pop(); push(infix[i]); break; } } i++; /* next symbol in infix expression */ } /* pop any remaining operators */ while(top > Empty ) postfix[p++] = pop(); postfix[p] = Arnold ; /* ensure a string */ } /* Function to find operator type */ int get_type(char symbol ) { switch(symbol) { case '(' : return (LeftParen); case ')': return (RightParen); case '+': case '-': case '%': case '*': case '/': return (Operator); default: return (Operand); } } /* Find precedence of the operator */ int get_prec(char symbol ) { switch(symbol) { case '+': return (AddPrec); case '-': return (SubPrec); case '*': return (MultPrec); case '/': return (DivPrec); case '%': return (RemPrec); case '(': return (LeftParenPrec); default: return (None); } } /* Function push */ void push(char symbol) { /* check for overflow */ if(top > Maxlen) full_stack(); else stack[++top] = symbol; } /* Function pop */ char pop(void) { /* check for underflow */ if (top <= Empty ) empty_stack(); else return(stack[top--]); } /* Exit in case of overflow */ void full_stack(void ) { printf("\n Full Stsck ... exiting. \n"); exit(1); } /* Exit in case of underflow */ void empty_stack(void) { printf("\n Empty Stack ... exiting \n"); exit(2); } void read_input(void) { printf("\n Infix (up to %d chars): ", Maxlen); gets(infix); } /* Output function */ void write_output(void) { printf("\n Infix: %s", infix); printf("\n Postfix: %s \n",postfix); } /* function white space checking */ int white_space(char symbol) { return( symbol == Blank || symbol == Tab || symbol == Arnold); } /* QUEUE WITH ARRAY */ #include #include void push(int ); int pop(); void display(); int q[10],f=0,r=0,n,top=1,s[10]; void main() { int ch,x,i; clrscr(); printf("Enter how many element you want in Queue :"); scanf("%d",&n); do { printf("\n1.INSERT"); printf("\n2.DELETE"); printf("\n3.EXIT"); printf("\nEnter your choice : "); scanf("%d",&ch); switch(ch) { case 1 : printf("\nEnter any no."); scanf("%d",&x); push(x); display(); getch(); break; case 2 : pop(); display(); getch(); break; case 3: exit(1); break; default : printf("INVALID CHOICE...."); getch(); break; } } while(ch!=3); } void push(int x) { if(r==n) { printf("\nQueue overflow..."); return; } else { r++; q[r]=x; } if(f==0) f=1; return; } int pop() { int x; if(r+1==f) { printf("\n\nQueue underflow..."); return(0); } else { x=q[f]; f++; x=q[f+1]; return(x); } } void display() { int i; printf("\n"); printf("F->"); for(i=f;i<=r;i++) { printf("%4d",q[i]); if(i==r) printf("<-R"); } } /* QUEUE WITH LINKLIST */ #include #include struct queue { int no; struct queue *next; }*f,*r; typedef struct queue node; node *insert(node * ,int ); void display(node *); node *delet(node *); void main() { int n,ch; menu: clrscr(); printf("\n\n\n\n\t\t\t\tMENU"); printf("\n\t\t\t1.Insert"); printf("\n\t\t\t2.Delete"); printf("\n\t\t\t3.Exit"); printf("\n\n\nEnter your choice :"); scanf("%d",&ch); switch(ch) { case 1: printf("Enter any no. : "); scanf("%d",&n); f=insert(f,n); display(f); break; case 2: f=delet(f); display(f); break; case 3 : exit(1); default : printf("\n\nInvalid choice ........"); break; } printf("\n\n\nPress any key to contineu......"); getch(); goto menu; } node *insert(node * front,int n) { node *temp,*new1; temp=front; new1=(node *)malloc(sizeof(node)); new1->next=NULL; if (new1==NULL) { printf("Memory is not avalable...."); return(front); } else { if(front==NULL) { new1->no=n; front=new1; r=new1; return(front); } else { new1->no=n; while(temp->next!=NULL) temp=temp->next; temp->next=new1; r=new1; return(front); } } } node *delet(node *front) { node *temp; if(front==NULL) printf("Queue is empty...."); else { temp=front; front=temp->next; } return(front); } void display(node *front) { node *temp; temp=front; while(temp!=NULL) { printf("%d ->",temp->no); temp=temp->next; } } // DEFINATION : Write a program to implement Double-stack. // (Operations on stack are Push , Pop , Change , Peep , Status ). #include #include void push(int ); int pop(); void peep(int ); void change(int ,int); void display(); # define n 10 int s[10],top1=-1,top2=n,sno,m=n; void main() { int ch,x,i; clrscr(); menu: printf("\nMenu"); printf("\n1.PUSH"); printf("\n2.POP"); printf("\n3.PEEP"); printf("\n4.CHANGE"); printf("\n5.STATUS"); printf("\n6.EXIT"); printf("\nEnter your choice : "); scanf("%d",&ch); switch(ch) { case 1 : printf("\nEnter in which stack (1/2) :"); scanf("%d",&sno); if(ch>=2 || ch<=1) { printf("\nEnter any no."); scanf("%d",&x); } push(x); display(); break; case 2 : printf("\nEnter in which stack (1/2) :"); scanf("%d",&sno); pop(); display(); break; case 3 : printf("\nEnter in which stack (1/2) :"); scanf("%d",&sno); if(ch>2 || ch<1) { printf("\nEnter possition :"); scanf("%d",&i); } peep(i); display(); break; case 4 : printf("\nEnter in which stack (1/2) :"); scanf("%d",&sno); if(ch>2 || ch<1) { printf("\nEnter possion :"); scanf("%d",&i); printf("\nEnter any no."); scanf("%d",&x); } change(i,x); display(); break; case 5: printf("\nTotal no. of element in stack are %d",top1+(m-top2)+1); break; case 6: exit(1); break; default : printf("INVALID CHOICE...."); break; } goto menu; } void push(int x) { if(top1+1==top2) { printf("\nStack Overflow...\n"); return; } else { if(sno==1) { top1++; s[top1]=x; } else if (sno==2) { top2--; s[top2]=x; } else printf("INVALID STACK...."); } return; } int pop() { int x; if(top1<0> { printf("\nStack Underflow...\n"); return(0); } else { if(sno==1) { top1--; x=s[top1+1]; } else if (sno==2) { top2++; x=s[top2-1]; } else printf("INVALID STACK...."); return(x); } } void peep(int i) { int x; if(sno==1) { if(top1-i+1<0) printf("\nStack Underflow..."); else { x=s[top1-i+1]; printf("\nElement is %d \n",x); } } else if(sno==2) { if(top2+i-1>m) printf("\nStack Underflow..."); else { x=s[top2+i-1]; printf("Element is %d \n",x); } } else printf("INVALID STACK...."); return; } void change(int i,int x) { if(sno==1) { if(top1-i+1<0) printf("\nStack Underflow..."); else s[top1-i+1]=x; } else if(sno==2) { if(top2+i-1>m) printf("\nStack Underflow..."); else s[top2+i-1]=x; } else printf("INVALID STACK...."); return; } void display() { int i; printf("\n"); printf("First stack is : \n"); for(i=0;i<=top1;i++) printf("%4d",s[i]); printf("\n"); for(i=0;i<=top1;i++) printf(" "); printf("^top1"); printf("\nSecond stack is : \n"); for(i=m-1;i>=top2;i--) printf("%4d",s[i]); printf("\n"); for(i=m-1;i>=top2;i--) printf(" "); printf("^top2"); }
