DS 1 - ARRAY OPERATIONS

1. Design, Develop and Implement a menu driven Program in C for the following Array operations a. Creating an Array of N Integer Elements b. Display of Array Elements with Suitable Headings c. Inserting an Element (ELEM) at a given valid Position (POS) d. Deleting an Element at a given valid Position(POS) e. Exit. Support the program with functions for each of the above operations.

array.c - PROGRAM

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

int a[10],n,elem,i,pos;
void create();
void display();
void insert();
void delete();

void create()
{
int i;
printf("Enter the size of array\n");
scanf("%d",&n);
printf("Enter the elements of array\n");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
}

void display()
{
int i;
printf("The array elements are:\n");
for(i=0; i<n; i++)
printf("%d\t",a[i]);
}

void insert()
{
int i;
printf("Enter the position for new element:\n");
scanf("%d",&pos);
printf("Enter the element to be inserted:\n");
scanf("%d",&elem);
for (i = n-1; i <=pos; i--)
a[i+1]=a[i];
a[pos]=elem;
n=n+1;
}

void delete()
{
printf("Enter  position of element to be deleted:\n");
scanf("%d",&pos);
elem=a[pos];
for (int i = 0; i < n-1; i++)
a[i]=a[i+1];
n=n-1;
printf("Deleted element is %d\n",elem );
}

int main()
{
int ch;
while(ch)
{
printf("\n\n______MENU_____\n");
printf("1.Create\n2.Display\n3.Insert\n4.Delete\n5.Exit\n");
printf("Enter Your Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:create();break;
case 2:display();break;
case 3:insert();break;
case 4:delete();break;
case 5:exit(0);break;
default :printf("INVALID CHOICE\n");
}
}return 0;

}

DS 2 - OPERATIONS ON STRINGS

2. Design, Develop and Implement a Program in C for the following operationson Strings a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP) b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR with REP if PAT exists in STR. Report suitable messages in case PAT does not exist in STR Support the program with functions for each of the above operations. Don't use Built-in functions.

patternmatching.c - PROGRAM

#include<stdio.h>

void main()
{
  char s[20],pat[20],rep[20],ans[30];
  int i,j,k,l,flag;
  printf("\nEnter string:");
  scanf("%s",s);
  printf("\nEnter pattern:");
  scanf("%s",pat);
  printf("\nEnter replacement:");
  scanf("%s",rep);
  for(i=0,k=0;s[i]!='\0';i++)
  {
    flag=1;
    for(j=0;pat[j]!='\0';j++)
      if(s[i+j]!=pat[j])
        flag=0;
    l=j;
    if(flag)
    {
      for(j=0;rep[j]!='\0';j++,k++)
        ans[k]=rep[j];
      i+=l-1;
    }
    else
      ans[k++]=s[i];
  }
  ans[k]='\0';
  printf("%s",ans);

}

DS 3 - STACK OPERATIONS

3. Design, Develop and Implement a menu driven Program in C for the following operations on STACK of Integers (Array Implementation of Stack with maximum size MAX) 
a. Push an Element on to Stack 
b. Pop an Element from Stack 
c. Demonstrate how Stack can be used to check Palindrome 
d. Demonstrate Overflow and Underflow situations on Stack 
e. Display the status of Stack 
f. Exit 
Support the program with appropriate functions for each of the above operations

stack.c - PROGRAM


#include <stdio.h>
#include <stdlib.h>
int s[5],top=-1;

void push()
{
    if(top==4)
        printf("\nStack overflow!!!!");
    else
    {
        printf("\nEnter element to insert:");
        scanf("%d",&s[++top]);
    }
}

void pop()
{
    if(top==-1)
        printf("\nStack underflow!!!");
    else
        printf("\nElement popped is: %d",s[top--]);
}
void disp()
{
    int t=top;
    if(t==-1)
        printf("\nStack empty!!");
    else
        printf("\nStack elements are:\n");
    while(t>=0)
        printf("%d ",s[t--]);
}
void pali()
{
    int num[5],rev[5],i,t;
    for(i=0,t=top;t>=0;i++,t--)
        num[i]=rev[t]=s[t];
    for(i=0;i<=top;i++)
        if(num[i]!=rev[i])
        break;
    /*printf(" num     rev\n");
    for(t=0;t<=top;t++)
      printf("%4d   %4d\n",num[t],rev[t]);*///remove /* */ to display num and rev
    if(i==top+1)
        printf("\nIt is a palindrome");
    else
        printf("\nIt is not a palindrome");
}

int main()
{
    int ch;
    do
    {
        printf("\n...Stack operations.....\n");
        printf("1.PUSH\n");
        printf("2.POP\n");
        printf("3.Palindrome\n");
        printf("4.Display\n");
        printf("5.Exit\n________________\n");
        printf("Enter choice:");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1:push();break;
            case 2:pop();break;
            case 3:pali();break;
            case 4:disp();break;
            case 5:exit(0);
            default:printf("\nInvalid choice");
        }
    }
    while(1);
    return 0;

}

DS 4 - INFIX EXPRESSION TO POSTFIX EXPRESSION

4. Design, Develop and Implement a Program in C for converting an Infix Expression to Postfix Expression. Program should support for both parenthesized and free parenthesized expressions with the operators: +, -, *, /, %(Remainder), ^(Power) and alphanumeric operands.

infixtopostfix.c - PROGRAM

#include<stdio.h>
#include<string.h>

int F(char symbol)
{
switch (symbol)
{
case '+':
case '-':return 2;
case '*':
case '/':
case '%':return 4;
case '^':
case '$':return 5;
case '(':return 0;
case '#':return -1;
default :return 8;
}
}

int G(char symbol)
{
switch (symbol)
{
case '+':
case '-':return 1;
case '*':
case '/':
case '%':return 3;
case '^':
case '$':return 6;
case '(':return 3;
case ')':return 0;
default :return 7;
}
}

void infix_postfix(char infix[], char postfix[])
{
int top=-1, j=0, i;
char s[30], symbol;
s[++top] = '#';
for(i=0; i < strlen(infix); i++)
{
symbol = infix[i];
while (F(s[top]) > G(symbol))
{
postfix[j] = s[top--];
j++;
}
if(F(s[top]) != G(symbol))
s[++top] = symbol;
else
top--;
}
while(s[top] != '#')
postfix[j++] = s[top--];
postfix[j] = '\0';
}

void main()
{
char infix[20], postfix[20];
printf("\nEnter a valid infix expression\n") ;
scanf ("%s", infix) ;
infix_postfix (infix, postfix);
printf("\nThe infix expression is:\n");
printf ("%s",infix);
printf("\nThe postfix expression is:\n");
printf ("%s",postfix) ;

}

DS 5A - SUFFIX EXPRESSION

5. Design, Develop and Implement a Program in C for the following Stack Applications 

a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^

suffix.c - PROGRAM

#include<stdio.h>
#include<math.h>
#include<string.h>

float compute(char symbol, float op1, float op2)
{
switch (symbol)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
case '$':
case '^': return pow(op1,op2);
default : return 0;
}
}

void main()
{
float s[20], res, op1, op2;
int top, i;
char postfix[20], symbol;
printf("\nEnter the postfix expression:\n");
scanf ("%s", postfix);
top=-1;
for (i=0; i<strlen(postfix) ;i++)
{
symbol = postfix[i];
if(isdigit(symbol))
s[++top]=symbol - '0';
else
{
op2 = s[top--];
op1 = s[top--];
res = compute(symbol, op1, op2);
s[++top] = res;
}
}
res = s[top--];
printf("\nThe result is : %f\n", res);

}

DS 5B - TOWER OF HANOI

5. Design, Develop and Implement a Program in C for the following Stack Applications 
b. Solving Tower of Hanoi problem with n disks

towerofhanoi.c - PROGRAM

#include<stdio.h>
#include<math.h>
void tower(int n, int source, int temp, int destination);

void tower(int n, int source, int temp, int destination)
{
if(n == 0)
return;
tower(n-1, source, destination, temp);
printf("\nMove disc %d from %c to %c", n, source, destination);
tower(n-1, temp, source, destination);
}

void main ()
{
int n;
printf("\nEnter the number of discs: \n\n");
scanf("%d", &n);
printf("\nThe sequence of moves involved in the Tower of Hanoi are\n");
tower(n, 'A', 'B', 'C');
printf("\n\nTotal Number of moves are: %d\n", (int)pow(2,n)-1);

}

DS 6 - CIRCULAR QUEUE

6. Design, Develop and Implement a menu driven Program in C for the following operations on Circular QUEUE of Characters (Array Implementation of Queue with maximum size MAX) a. Insert an Element on to Circular QUEUE b. Delete an Element from Circular QUEUE c. Demonstrate Overflow and Underflow situations on Circular QUEUE d. Display the status of Circular QUEUE e. Exit Support the program with appropriate functions for each of the above operations

circularqueue.c - PROGRAM

#include <stdio.h>
#include <stdlib.h>
#define max 5
int q[max],f=-1,r=-1;
void ins()
{
    if(f==(r+1)%max)
        printf("\nQueue overflow");
    else
    {
        if(f==-1)
            f++;
        r=(r+1)%max;
        printf("\nEnter element to be inserted:");
        scanf("%d",&q[r]);
    }
}
void del()
{
    if(r==-1)
        printf("\nQueue underflow");
    else
    {
        printf("\nElemnt deleted is:%d",q[f]);
        if(f==r)
            f=r=-1;
        else
            f=(f+1)%max;
    }
}
void disp()
{
    if(f==-1)
        printf("\nQueue empty");
    else
    {
        int i;
        printf("\nQueue elements are:\n");
        for(i=f;i!=r;i=(i+1)%max)
            printf("%d\t",q[i]);
        printf("%d",q[i]);
        printf("\nFront is at:%d\nRear is at:%d",q[f],q[r]);
    }
}
int main()
{
    printf("\nCircular Queue operations");
    printf("\n1.Insert");
    printf("\n2.Delete");
    printf("\n3.Display");
    printf("\n4.Exit");
    int ch;
    do{
        printf("\nEnter choice:");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1:ins();break;
            case 2:del();break;
            case 3:disp();break;
            case 4:exit(0);
            default:printf("\nInvalid choice...!");
        }
   }while(1);
    return 0;

}

DS 7 - SINGLY LINKED LIST (SLL)

7. Design, Develop and Implement a menu driven Program in C for the following operations on Singly Linked List (SLL) of Student Data with the fields: USN, Name, Branch, Sem, PhNo 

a. Create a SLL of N Students Data by using front insertion. 
b. Display the status of SLL and count the number of nodes in it 
c. Perform Insertion / Deletion at End of SLL 
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack) 
e. Exit

sll.c - PROGRAM

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
struct stud
{
    char usn[11],name[15],branch[4],phno[11];
    int sem;
    struct stud *next;
}*f=NULL,*r=NULL,*t=NULL;
void ins(int ch)
{
    t=(struct stud*)malloc(sizeof(struct stud));
    printf("\nEnter USN:");
    scanf("%s",t->usn);
    printf("Enter Name:");
    scanf("%s",t->name);
    printf("Enter Branch:");
    scanf("%s",t->branch);
    printf("Enter Sem:");
    scanf("%d",&t->sem);
    printf("Enter Phno:");
    scanf("%s",t->phno);
    t->next=NULL;
    if(!r)
        f=r=t;
    else
    {
        if(ch)
        {
            r->next=t;
            r=t;
        }
        else
        {
            t->next=f;
            f=t;
        }
    }
}
void del(int ch)
{
    if(!f)
        printf("\nList Empty");
    else
    {
        struct stud *t1;
        if(f==r)
        {
            t1=f;
            f=r=NULL;
        }
        else if(ch)
        {
            t1=r;
            for(t=f;t->next!=r;t=t->next)
                r=t;
            r->next=NULL;
        }
        else
        {
            t1=f;
            f=f->next;
        }
        printf("\nElement deleted is:\n");
        printf("USN:%s\nName:%s\nBranch:%s\nSem:%d\nPhno:%s\n",t1->usn,t1->name,t1->branch,t1->sem,t1->phno);
        free(t1);
    }
}
void disp()
{
    if(!f)
        printf("\nList Empty!!!");
    else
        printf("\nList elements are:\n");
    for(t=f;t;t=t->next)
        printf("\nUSN:%s\nName:%s\nBranch:%s\nSem:%d\nPhno:%s\n",t->usn,t->name,t->branch,t->sem,t->phno);
}
void main()
{
    int ch,n,i;
    printf("\n........Menu..........,\n");
    printf("1.Create\n");
    printf("2.Display\n");
    printf("3.Insert at end\n");
    printf("4.Delete at end\n");
    printf("5.Insert at beg\n");
    printf("6.Delete at beg\n");
    printf("7.Exit\n");
    while(1)
    {
        printf("\nEnter choice:");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1: printf("\nEnter no. of nodes:");
                    scanf("%d",&n);
                    for(i=0;i<n;i++)
                        ins(0);
                    break;
            case 2:disp();break;
            case 3:ins(1);break;
            case 4:del(1);break;
            case 5:ins(0);break;
            case 6:del(0);break;
            case 7:exit(0);
            default:printf("\nInvalid choice!!!!");
        }
    }

}