Group all occurrences of characters according to first appearance: C Program

Given a string of lowercase characters, the task is to print the string in a manner such that a character comes first in string displays first with all its occurrences in string.
Examples:

Input :  str = "occurrence"
output : occcurreen 

Input  : str = "cdab"
Output : cdab

C Program

#include <stdio.h>

#include <string.h>

main()

{

char st[100],temp,s[100];

int i,k=0,j,flag=0;

gets(st);

               

for(i=0;st[i]!='\0';i++)

{

                for(j=i;st[j]!='\0';j++)

                {

                                if(k<strlen(st))

                                {

                                                if(st[i] == st[j])

                                                                s[k++]=st[j];      

                                }

                                else

                                {

                                                flag=1;

                                                break;

                                }                                             

                }

                if(flag ==1)

                                break;

}

s[k]='\0';

puts(s);

}

Remove spaces from string Using Queues: Cprogram

Write a program that compresses a string by deleting all space characters in the string. One way to do so is to use a queue of characters. Insert non space  characters from the string into the queue. When you reach the end of the string , dequeue the characters from the queue and place them back into the string.  

#include <stdio.h>

#define MAX 50

char q[MAX],f=-1,r=-1;

void enq(char val)

{

                if(r == MAX-1)

                                printf("queue is full and hence cannot insert");

                else if(f == -1 && r == -1)

                                f=r=0;

                else

                                r=r+1;

                q[r]=val;

}

char deq()

{

                char val;

                if(f == -1)

                                printf("queue is empty and hence cannot delete");

                else

                {

                                val = q[f];

                                if(f == r)

                                                f=r=-1;

                                else

                                                f=f+1;

                }

                return val;

}

int main()

{

                int i;

                char s[MAX];

                gets(s);

                for(i=0;s[i]!='\0';i++)

                {

                                if(s[i] != ' ')

                                                enq(s[i]);

                }

                for(i= f;i<=r;i++)

                                s[i]=deq();

                s[i]='\0';

                puts(s);

}

Output:

Copying elements of one queue to another queue : C program

#include <stdio.h>

#define MAX 5

int q1[MAX],q2[MAX],f1=-1,r1=-1,f2=-1,r2=-1;

void enq(int q[],int *f,int *r,int val)

{

                if(*r == MAX-1)

                                printf("queue is full and hence cannot insert");

                else if(*f == -1 && *r == -1)

                                *f=*r=0;

                else

                                *r=*r+1;

                q[*r]=val;

}

void display(int q[],int *f, int *r)

{

                int i;

                if(*f == -1)

                                printf("queue is empty ");

                else

                {

                                for(i=*f;i<=*r;i++)

                                                printf("%d\t",q[i]);

                }             

}

main()

{

                int i,val;

                for(i=0;i<MAX;i++)

                {

                                printf("\nenter a value\n");

                                scanf("%d",&val);

                                enq(q1,&f1,&r1,val);

                }

                printf("\nelements in queue 1 are\n");

                display(q1,&f1,&r1);

               

                for(i=f1;i<=r1;i++)

                                enq(q2,&f2,&r2,q1[i]);

                printf("\nelements in queue 2 are\n");

                display(q2,&f2,&r2);

}

Output:

Different AVL Trees for a given set of numbers

 Create any 5 possible AVL trees with the following data  13, 10, 7, 30, 15, 25, 36.

Quadratic Probing: C program

Algorithm to insert a value in quadratic probing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be inserted, key

Step 2:  let i = 0

Step 3:  hkey=key%TABLE_SIZE
Step 4: compute the index at which the value has to be inserted in hash table

                index = (hkey+ i * i) % TABLE_SIZE

Step 5: if there is no element at that index then  insert the value at index and STOP

Step 6: If there is already an element at that index

                step 4.1: i = i+1

step 7:  if i < TABLE_SIZE then go to step 4

Algorithm to search a value in quadratic probing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be searched, key

Step 2:  let i = 0

Step 3:  hkey=key%TABLE_SIZE
Step 4: compute the index at which the value can be found

                index = (hkey + i * i) % TABLE_SIZE

Step 5: if the  element at that index is same as the search value then print element found and  STOP

Step 6: else

                step 4.1: i = i+1

step 7:  if i < TABLE_SIZE then go to step 4

 


#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

 int key,index,i,flag=0,hkey;
 printf("\nenter a value to insert into hash table\n");
 scanf("%d",&key);
 hkey=key%TABLE_SIZE;
 for(i=0;i<TABLE_SIZE;i++)
{

     index=(hkey+i*i)%TABLE_SIZE;

     if(h[index] == NULL)
     {
        h[index]=key;
         break;
     }
}
if(i == TABLE_SIZE)
     printf("\nelement cannot be inserted\n");
}
void search()
{

 int key,index,i,flag=0,hkey;
 printf("\nenter search element\n");
 scanf("%d",&key);
 hkey=key%TABLE_SIZE;
 for(i=0;i<TABLE_SIZE; i++)
 {
    index=(hkey+i*i)%TABLE_SIZE;
    if(h[index]==key)
    {
      printf("value is found at index %d",index);
      break;
    }
  }
  if(i == TABLE_SIZE)
    printf("\n value is not found\n");
}
void display()
{
  int i;

  printf("\nelements in the hash table are \n");

  for(i=0;i< TABLE_SIZE; i++)

              printf("\nat index %d \t value =  %d",i,h[i]);

}
main()
{
    int opt,i;
    while(1)
    {
        printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:
                insert();
                break;
            case 2:
                display();
                break;
            case 3:
                search();
                break;
            case 4:exit(0);
        }
    }
}

Output:

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
12

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
22

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
32

Press 1. Insert     2. Display     3. Search     4.Exit
2

elements in the hash table are

at index 0      value =  0
at index 1      value =  0
at index 2      value =  12
at index 3      value =  22
at index 4      value =  0
at index 5      value =  0
at index 6      value =  32
at index 7      value =  0
at index 8      value =  0
at index 9      value =  0
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
22
value is found at index 3
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
123

 value is not found

Press 1. Insert     2. Display     3. Search     4.Exit
4

Double Hashing: C program

Algorithm to insert a value in Double hashing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be inserted,key

Step 2:  let i = 0

Step 3: Let R be the nearest prime < TABLE_SIZE

Step 4: hkey=key%TABLE_SIZE;
 hash2 = 7-(key %7);
Step 5: compute the index at which the value has to be inserted in hash table

                 index=(hkey+i*hash2)%TABLE_SIZE;

Step 6: if there is no element at that index then  insert the value at index and STOP

Step 7: If there is already an element at that index

                step 6.1: i = i+1

step 8:  if i < TABLE_SIZE then go to step 5

Algorithm to search a value in Double Hashing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be searched, key

Step 2:  let i = 0

Step 3: Let R be the nearest prime < TABLE_SIZE

Step 4:  hkey=key%TABLE_SIZE;
 hash2 = 7-(key %7);
Step 5: compute the index at which the value can be found

             index=(hkey+i*hash2)%TABLE_SIZE;

Step 6: if the  element at that index is same as the search value then print element found and  STOP

Step 7: If there is already an element at that index

                step 6.1: i = i+1

step 8:  if i < TABLE_SIZE then go to step 5

 


#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

 int key,index,i,flag=0,hkey,hash2;
 printf("\nenter a value to insert into hash table\n");
 scanf("%d",&key);
 hkey=key%TABLE_SIZE;
 hash2 = 7-(key %7);
 for(i=0;i<TABLE_SIZE;i++)
 {
    index=(hkey+i*hash2)%TABLE_SIZE;
    if(h[index] == NULL)
    {
        h[index]=key;
        break;
    }
 }
 if(i == TABLE_SIZE)
     printf("\nelement cannot be inserted\n");
}
void search()
{

 int key,index,i,flag=0,hash2,hkey;
 printf("\nenter search element\n");
 scanf("%d",&key);
  hkey=key%TABLE_SIZE;
 hash2 = 7-(key %7);
 for(i=0;i<TABLE_SIZE; i++)
 {
    index=(hkey+i*hash2)%TABLE_SIZE;
    if(h[index]==key)
    {
      printf("value is found at index %d",index);
      break;
    }
  }
  if(i == TABLE_SIZE)
    printf("\n value is not found\n");
}
void display()
{

  int i;
  printf("\nelements in the hash table are \n");
  for(i=0;i< TABLE_SIZE; i++)
    printf("\nat index %d \t value =  %d",i,h[i]);

}
main()
{
    int opt,i;
    while(1)
    {
        printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:
                insert();
                break;
            case 2:
                display();
                break;
            case 3:
                search();
                break;
            case 4:exit(0);
        }
    }
}



Output
Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
12

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
22

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
32

Press 1. Insert     2. Display     3. Search     4.Exit
2

elements in the hash table are

at index 0      value =  0
at index 1      value =  0
at index 2      value =  12
at index 3      value =  0
at index 4      value =  0
at index 5      value =  32
at index 6      value =  0
at index 7      value =  0
at index 8      value =  22
at index 9      value =  0
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
22
value is found at index 8
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
34

 value is not found

Press 1. Insert     2. Display     3. Search     4.Exit
4