Friday, 1 July 2022

ADS

 P1: Coffee

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

struct node {
    int custid;
    char n[30];
    int amt;
    struct node* next;
} *head = 0, *temp, *ptr1 = 0, *ptr2 = 0, *new1, *max_id, *min_id;

int main() {
    int ch, id, cost, c = 0, max, min;
    char res, name[30];
    do {
        printf("1.Add\n2.Search by ID\n3.Print Bill\n4.Max and Min Sell\n\nChoose any 1: \t");
        scanf("%d", &ch);
        switch(ch) {
            case 1:
                do {
                    new1 =(struct node*)malloc(sizeof(struct node));
                    printf("\nEnter Customer ID, Name, Purchase Amount: \t");
                    scanf("%d %s %d", &id, &name, &cost);
                    new1->custid = id;
                    strcpy(new1->n, name);
                    new1->amt = cost;
                    new1->next = 0;

                    if(head == 0) {
                        head = new1;
                        c++;
                    } else {
                        temp = head;
                        while(temp->next != 0) {
                            temp = temp->next;
                        }
                        temp->next = new1;
                        c++;
                    }
                    printf("\nDo you want to add more: \t");
                    scanf(" %c", &res);
                } while(res == 'y');
            break;

            case 2:
                printf("\nEnter ID of customer to be searched : \t");
                scanf("%d", &id);
                temp = head;
                while(temp != 0) {
                    if(temp->custid == id) {
                        printf("\n**********************************************************\n");
                        printf("\nCustomer ID\tName\tTotal Purchase");
                        printf("\n%d\t%s\t%d", temp->custid, temp->n, temp->amt);
                        break;
                    } else {
                        temp = temp->next;
                    }
                }
            break;

            case 3:
                temp = head;
                max_id = head; min_id = head;
                int tot_sale = 0;
                printf("\n**********************************************************\n");
                printf("\nC_ID\t\tName\tTotal Purchase");
                while(temp != 0) {
                    printf("\n%d\t|\t%s\t|\t%d", temp->custid, temp->n, temp->amt);
                    tot_sale += temp->amt;
                    temp = temp->next;
                }
                printf("\n\nTotal Sale of the Day is :\t%d", tot_sale);
            break;

            case 4:
                temp = head->next;
                max = head->amt;
                min = head->amt;
                while(temp != 0) {
                    if(temp->amt > max) {
                        max_id = temp;
                        max = temp->amt;
                    }
                    if(temp->amt < min) {
                        min_id = temp;
                        min = temp->amt;
                    }
                    temp = temp->next;
                }
                printf("\nSell Type\tC_ID\t\tName\tTotal Purchase");
                printf("\nMax Sell:\t%d\t|\t%s\t|\t%d", max_id->custid, max_id->n, max_id->amt);
                printf("\nMin Sell:\t%d\t|\t%s\t|\t%d", min_id->custid, min_id->n, min_id->amt);
            break;
        }
        printf("\n\nDo you want to continue: \t");
        scanf(" %c", &res);
    } while(res == 'y');
}

---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------

P2a: Stack

#include<bits/stdc++.h>
using namespace std;

struct node {
    struct node* prev;
    int val;
    struct node* next;
} *head = 0, *ptr1, *ptr2, *temp, *new1;

int main() {
    int ch, x, c = 0;
    char res;
    do {
        printf("\n1.Push\n2.Pop\n3.Display\nChoose any 1: \t");
        scanf("%d", &ch);
        switch(ch) {
            case 1:
                do {
                    printf("\nEnter value: \t");
                    scanf("%d", &x);
                    new1 = (struct node*)malloc(sizeof(struct node));
                    new1->prev = 0;
                    new1->val = x;
                    new1->next = 0;
                    if(head == 0) {
                        head = new1;
                        c++;
                    } else {
                        temp = head;
                        while(temp->next != 0) {
                            temp = temp->next;
                        }
                        temp->next = new1;
                        new1->prev = temp;
                        c++;
                    }
                    printf("\nDo you want to add more: \t");
                    scanf(" %c", &res);
                } while(res == 'y');
            break;

            case 2:
                temp = head;
                while(temp->next != 0) {
                    temp = temp->next;
                }
                ptr1 = temp;
                temp = temp->prev;
                temp->next = 0;
                free(ptr1);
            break;

            case 3:
                temp = head;
                while(temp->next != 0) {
                    temp = temp->next;
                }
                while(temp != head) {
                    printf("%d\n", temp->val);
                    temp = temp->prev;
                }
                printf("%d\n", head->val);
            break;
        }
        printf("\nDo you want to continue: \t");
        scanf(" %c", &res);
    }while(res == 'y');
}

P2b: Queue


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

// Structure to create a node with data and next pointer
struct node {
int data;
struct node *next;
};

struct node *front = NULL;
struct node *rear = NULL;

// Enqueue() operation on a queue
void enqueue(int value) {
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = value;
ptr->next = NULL;
if ((front == NULL) && (rear == NULL)) {
front = rear = ptr;
} else {
rear->next = ptr;
rear = ptr;
}
printf("Node is Inserted\n\n");
}

// Dequeue() operation on a queue
int dequeue() {
if (front == NULL) {
printf("\nUnderflow\n");
return -1;
} else {
struct node *temp = front;
int temp_data = front->data;
front = front->next;
free(temp);
return temp_data;
}
}

// Display all elements of queue
void display() {
struct node *temp;
if ((front == NULL) && (rear == NULL)) {
printf("\nQueue is Empty\n");
} else {
printf("The queue is \n");
temp = front;
while (temp) {
printf("%d--->", temp->data);
temp = temp->next;
}
printf("NULL\n\n");
}
}

int main() {
int choice, value;
printf("\nImplementation of Queue using Linked List\n");
while (choice != 4) {
printf("1.Enqueue\n2.Dequeue\n3.Display\n4.Exit\n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("\nEnter the value to insert: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
printf("Popped element is :%d\n", dequeue());
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nWrong Choice\n");
}
}
return 0;
}

---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------

P3: Skip List


#include <stdio.h>
#include <stdlib.h>
const int level = 3;
typedef struct Skip_List
{
    int data;
    struct Skip_List *next[3];
} * skl;
skl head = NULL;

skl getNode()
{
    int val;
    printf("Enter The value You want to Insert:-");
    scanf("%d", &val);
    struct Skip_List *newNode = (struct Skip_List *)malloc(sizeof(struct Skip_List));
    newNode->data = val;
    for (int i = 0; i < level; i++)
        newNode->next[i] = NULL;
    return newNode;
}

void DisplyExpress()
{
    struct Skip_List *temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next[1];
    }
}
void DisplyExpress2()
{
    struct Skip_List *temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next[2];
    }
}
void normalWay()
{
    struct Skip_List *newNode = getNode();
    if (head == NULL)
    {
        head = newNode;
        return;
    }
    struct Skip_List *temp = head;
    int cnt = 1;
    while (temp->next[0] != NULL)
    {
        temp = temp->next[0];
    }
    temp->next[0] = newNode;
}
void expressWay()
{
    skl temp, prev;
    for (int i = 1; i < level; i++)
    {
        int ct = 1;
        temp = head->next[i - 1];
        for (prev = head; temp != NULL; temp = temp->next[i - 1])
        {
            if (ct % level == 0)
            {
                prev->next[i] = temp;
                prev = temp;
            }
            ct++;
        }
    }
}
void Display()
{
    struct Skip_List *temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next[0];
    }
}
void search(int key)
{
    skl prev = head;
    skl temp = head;
    int i = level - 1;
    int found = 0;
    int ct = 0;
    while (found == 0 && i >= 0)
    {

        if (key < head->data || temp == NULL)
        {
            printf("%d Element Not found", key);
            return;
        }
        else if (temp->data == key)
        {
            ct++;
            found = 1;
            printf(" %d Found in %d Iterations", key, ct);
        }
        else if (key > temp->data)
        {
            ct++;
            prev = temp;
            temp = temp->next[i];
            if (temp == NULL)
            {
                i--;
                temp = prev->next[i];
            }
        }
        else if (key < temp->data)
        {
            i--;
            temp = prev->next[i];
            ct++;
        }
        else
        {
            found=0;
        }
    }
    if(found==0)
        printf("Element Not Found!!!\n");
    
    printf("\n");
}
int main()
{
    char ch = 'y';
    do
    {
        normalWay();
        printf("\nWant To insert a Node(y/n):-");
        scanf(" %c", &ch);
    } while (ch == 'y');
    expressWay();
    printf("\n\nNormal Lane:\n");
    Display();
    printf("\n");
    printf("Express Lane 1:\n");
    DisplyExpress();
    printf("\n");
    printf("Express Lane 2:\n");
    DisplyExpress2();
    printf("\n\n");
    do
    {
        int key;
        printf("Enter Element You Want To search:");
        scanf("%d", &key);
        search(key);
        printf("\nWant To search another element ?(y/n):-");
        scanf(" %c", &ch);
    } while (ch == 'y');
    return 0;
}

---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------

P4: Hashing


#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
struct node
{
  int data;
  struct node *next;
};
struct node *head[10]={NULL},*c;
void insert()
{
  int i,key;
  printf("\n\nEnter a value to be inserted :\n");
  scanf("%d",&key);
  i=key%10;
  struct node * newnode=(struct node *)malloc(sizeof(struct node));
  newnode->data=key;
  newnode->next = NULL;
  if(head[i] == NULL)
     head[i] = newnode;
  else
  {
  c=head[i];
  while(c->next != NULL)
  {
   c=c->next;
  }
  c->next=newnode;
}
}
void search()
{
  int key,index;
  printf("\nEnter the element to be searched:\t");
  scanf("%d",&key);
  index=key%10;
  if(head[index] == NULL)
  printf("\nSearch element not found\n");
  else
  {
  for(c=head[index];c!=NULL;c=c->next)

{
  if(c->data == key)
  {
  printf("\nSearch element found at index %d\n",index);
  break;
  }
}
  if(c==NULL)
  printf("\nSearch element not found\n");
 }
}
void display()
  {
  printf("\n");
  int i;
  for(i=0;i<10;i++)
  {
  if(head[i] == NULL)
  {
  printf("INDEX %d: \t0->", i);
  }
  else
  {
  printf("INDEX %d: \t", i);
  for(c=head[i];c!=NULL;c=c->next)
   printf("%d->",c->data);
  }
  printf("NULL\n\n");
 }


}
int main()
 {
 int ch,key,i;
 while(1)
 {
 printf("\n\n1.Add\n2:Display\n3:Search\n4:Exit");
 printf("\nEnter your choice :\t");
 scanf("%d",&ch);

 switch(ch)
 {
  case 1:
  insert();
  break;
  case 2:
  display();
  break;
  case 3:
  search();
  break;
  case 4:
  exit(0);
  }
 printf("\n*************************************************************");
 printf("\n*************************************************************");
 printf("\n");
 }
}

---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------

P5: BST


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

struct node
{
    char emp_name[30];
    int emp_sal;
    struct node *right_child;
    struct node *left_child;
};

void Print(struct node *root, int k1, int k2)
{
   if ( NULL == root )
      return;
   if ( k1 < root->emp_sal )
    Print(root->left_child, k1, k2);
   if ( k1 <= root->emp_sal && k2 >= root->emp_sal )
    printf("\n%s\t|\t%d", root->emp_name, root->emp_sal);
   Print(root->right_child, k1, k2);
}

int FindTot(struct node* root) {
    int tot = 0, totLeft = 0, totRight = 0;
    if(root == NULL) {
        printf("Tree is empty\n");
        return 0;
    }
    else {
        if(root->left_child != NULL)
            totLeft = FindTot(root->left_child);

        if(root->right_child != NULL)
              totRight = FindTot(root->right_child);

        tot = root->emp_sal + totLeft + totRight;
        return tot;
   }
}

int FindMax(struct node* root)
{
    struct node* current = root;
    while (current->right_child != NULL)
        current = current->right_child;
    printf("\n%s\t|\t%d", current->emp_name, current->emp_sal);
    return 0;
}

int FindMin(struct node* root)
{
    struct node* current = root;
    while (current->left_child != NULL)
        current = current->left_child;
    printf("\n%s\t|\t%d", current->emp_name, current->emp_sal);
    return 0;
}
/*
struct node* search(struct node *root, int x)
{
    if(root==NULL)
        return 0;
    else if(root->data == x) return root;
    else if(x>root->data)
        return search(root->right_child, x);
    else
        return search(root->left_child,x);
}

struct node* find_minimum(struct node *root)
{
    if(root == NULL)
        return NULL;
    else if(root->left_child != NULL)
        return find_minimum(root->left_child);
    return root;
}
*/
struct node* new_node(char name[], int sal)
{
    struct node *p;
    p = malloc(sizeof(struct node));
    p->emp_sal = sal;
    strcpy(p->emp_name, name);
    p->left_child = NULL;
    p->right_child = NULL;

    return p;
}

struct node* insert(struct node *root, char name[], int sal)
{

    if(root==NULL)
        return new_node(name, sal);
    else if(sal > root->emp_sal)
        root->right_child = insert(root->right_child, name, sal);
    else
        root->left_child = insert(root->left_child, name, sal);
    return root;
}
/*
struct node* delete(struct node *root, int x)
{
    if(root==NULL)
        return NULL;
    if (x>root->data)
        root->right_child = delete(root->right_child, x);
    else if(x<root->data)
        root->left_child = delete(root->left_child, x);
    else
    {
        if(root->left_child==NULL && root->right_child==NULL)
        {
            free(root);
            return NULL;
        }

        else if(root->left_child==NULL || root->right_child==NULL)
        {
            struct node *temp;
            if(root->left_child==NULL)
                temp = root->right_child;
            else
                temp = root->left_child;
            free(root);
            return temp;
        }

        else
        {
            struct node *temp = find_minimum(root->right_child);
            root->data = temp->data;
            root->right_child = delete(root->right_child, temp->data);
        }
    }
    return root;
}
*/
void inorder(struct node *root)
{
    if(root!=NULL)
    {
        inorder(root->left_child);
        printf("\n%s\t|\t%d", root->emp_name, root->emp_sal);
        inorder(root->right_child);
    }
}
void preorder(struct node *root)
{
    if(root!=NULL)
    {
        printf("\n%s\t|\t%d", root->emp_name, root->emp_sal);
        preorder(root->left_child);
        preorder(root->right_child);
    }
}
void postorder(struct node *root)
{
    if(root!=NULL)
    {
        postorder(root->left_child);
        postorder(root->right_child);
        printf("\n%s\t|\t%d", root->emp_name, root->emp_sal);
    }
}
int main()
{
    int m = 0, n = 0;
    struct node *root;
    int ch, cnt = 0, sal;
    char res, name[30];
    do{
        printf("1.Add Employee\n2.Display Database\n3.Employee with Max and Min Salary\n4.Total Monthly Salary Expenditure of Company\n5.Display Salary in Range\n\nChoose any one: \t");
        scanf("%d", &ch);
        switch(ch) {
            case 1:
                do{
                    if(cnt == 0) {
                        printf("\nEnter Employee Name and Salary: \t");
                        scanf("%s %d", &name, &sal);
                        root = new_node(name, sal);
                        cnt++;
                    } else {
                        printf("\nEnter Employee Name and Salary: \t");
                        scanf("%s %d", &name, &sal);
                        insert(root, name, sal);
                    }
                    printf("\nDo you want to add more: \t");
                    scanf(" %c", &res);
                }while(res == 'y');
                printf("\n\n***********************************************************************");
                printf("\n***********************************************************************\n\n");
            break;
            case 2:
                printf("\nPreorder Display: \n");
                printf("\nName\t|\tSalary");
                preorder(root);
                printf("\n\nInorder Display: \n");
                printf("\nName\t|\tSalary");
                inorder(root);
                printf("\n\nPostorder Display: \n");
                printf("\nName\t|\tSalary");
                postorder(root);
                printf("\n\n***********************************************************************");
                printf("\n***********************************************************************\n\n");
            break;
            case 3:
                printf("\nMaximum Salary");
                printf("\nName\t|\tSalary\n");
                FindMax(root);
                printf("\n");
                printf("\nMinimum Salary");
                printf("\nName\t|\tSalary\n");
                FindMin(root);
                printf("\n");
                printf("\n\n***********************************************************************");
                printf("\n***********************************************************************\n\n");
            break;
            case 4:
                printf("\n-----------------------------------------------------------------------");
                printf("\nTotal Monthly Salary: ");
                int mon = FindTot(root);
                printf("%d", mon);
                printf("\n-----------------------------------------------------------------------");
                printf("\n\n***********************************************************************");
                printf("\n***********************************************************************\n\n");
            break;
            case 5:
                printf("\nSpecify Minimum and Maximum Salary: \t");
                scanf("%d %d", &m, &n);
                printf("\nName\t|\tSalary\n");
                Print(root, m, n);
                printf("\n\n***********************************************************************");
                printf("\n***********************************************************************\n\n");
            break;
        }
        printf("\nDo you want to continue: \t");
        scanf(" %c", &res);

    }while(res == 'y');
    return 0;
}

---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------

P6a: Trie

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


#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE (26)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
#define MAX 100

struct TrieNode
{
struct TrieNode *children[ALPHABET_SIZE];
bool isEndOfWord;
};

struct TrieNode *getNode(void)
{
struct TrieNode *pNode = NULL;

pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

if (pNode)
{
int i;

pNode->isEndOfWord = false;

for (i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
}
return pNode;
}
void insert(struct TrieNode *root, const char *key)
{
int level;
int length = strlen(key);
int index;

struct TrieNode *pCrawl = root;

for (level = 0; level < length; level++)
{
index = CHAR_TO_INDEX(key[level]);
if (!pCrawl->children[index])
pCrawl->children[index] = getNode();

pCrawl = pCrawl->children[index];
}

pCrawl->isEndOfWord = true;
}
void display(struct TrieNode* root, char *str, int level)
{
struct TrieNode *pCrawl = root;
if (pCrawl->isEndOfWord == true)
{
str[level] = '\0';
printf("%s\t",str);
}

int i;
for (i = 0; i < ALPHABET_SIZE; i++)
{
if (pCrawl->children[i])
{
str[level] = i + 'a';
display(pCrawl->children[i], str, level + 1);
}
}
}
bool search(struct TrieNode *root, const char *key)
{
int level;
int length = strlen(key);
int index;
struct TrieNode *pCrawl = root;

for (level = 0; level < length; level++)
{
index = CHAR_TO_INDEX(key[level]);

if (!pCrawl->children[index])
return false;

pCrawl = pCrawl->children[index];
}

return (pCrawl->isEndOfWord);
}

int main()
{
    struct TrieNode *root = getNode();
    FILE *fptr = NULL;
    int i = 0;
    char word[MAX] = {0};
    char searchword[MAX];
    char res;
    

    fptr = fopen("input.txt", "r");
    while(fscanf(fptr, "%100s\n", word)!=EOF){
        insert(root, &word[i]);
    }
    fclose(fptr);


//Display
int level = 0;
    char str[20];
printf("Content of Trie:\n");
display(root, str, level);

char output[][32] = {"Not present in trie", "Present in trie"};

    do
    {
        printf("\nEnter Word to Search: ");
        scanf("%s",searchword);
        printf("%s --- %s\n", searchword, output[search(root, searchword)] );
        printf("\nDo you want to search more: ");
    scanf(" %c", &res);
    } while (res=='y');

return 0;
}

P6b: Trie

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define N 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

typedef struct TrieNode
{
struct TrieNode *children[N];
int flag;
}*Tr;

Tr getNode(void)
{
Tr newnode = NULL;

newnode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

if (newnode)
{
int i;

newnode->flag = 0;

for (i = 0; i < N; i++)
newnode->children[i] = NULL;
}

return newnode;
}

void insert(Tr root, const char *word)
{
int i;
int length = strlen(word);
int index;

struct TrieNode *temp = root;

for (i = 0; i < length; i++)
{
index = CHAR_TO_INDEX(word[i]);
if (!temp->children[index])
temp->children[index] = getNode();

temp = temp->children[index];
}

temp->flag = 1;
}

int search(Tr root, char *word)
{
int i;
int length = strlen(word);
int index;
struct TrieNode *temp =root;

for (i = 0; i< length; i++)
{
index = CHAR_TO_INDEX(word[i]);

if (!temp->children[index])
return 0;

temp = temp->children[index];
}

return (temp->flag);
}

int main()
{
char word[][15] = {"and","bat","ball","book","cot","cotton","internet","interview","joy","job","king","lion","man","mango","mango"};

char output[][32] = {"Not present in trie", "Present in trie"};

char word1[][15] = {0};


struct TrieNode *root = getNode();

// Construct trie
FILE* fp;

    printf("\nHow many words you have to search: \t");
    int n;
    scanf("%d", &n);
    char word2[30];

int i;

for (i = 0; i < ARRAY_SIZE(word); i++)
insert(root, word[i]);

// Search for different keys
printf("-----------------------------------\n");
printf("-----------------------------------\n");
// fp = fopen("Trie.txt", "r");
// int j=0;
// while (fscanf(fp, "%s/t", word1) == 1)
// {
for(int i=0;i < n; i++)
{
            printf("Enter the word: \t");
            scanf("%s", word2);
        printf("\nPresent\t\t\tNot Present\n");
    //printf("%d",(search(root, word1[i])));
    if((search(root, word2)) == 1) {
                printf("%d) %s\t\t\n", i, word2);
    } else printf("%d)\t\t\t%s\n", i, word2);
//printf("%s --- %s\n\n", word1[i],output[search(root, word1[i])] );
            printf("\n");
}
return 0;
}

P6c: Trie

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define N 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

typedef struct TrieNode
{
struct TrieNode *children[N];
int flag;
}*Tr;

Tr getNode(void)
{
Tr newnode = NULL;

newnode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

if (newnode)
{
int i;

newnode->flag = 0;

for (i = 0; i < N; i++)
newnode->children[i] = NULL;
}

return newnode;
}

void insert(Tr root, const char *word)
{
int i;
int length = strlen(word);
int index;

struct TrieNode *temp = root;

for (i = 0; i < length; i++)
{
index = CHAR_TO_INDEX(word[i]);
if (!temp->children[index])
temp->children[index] = getNode();

temp = temp->children[index];
}

temp->flag = 1;
}

int search(Tr root, char *word)
{
int i;
int length = strlen(word);
int index;
struct TrieNode *temp =root;

for (i = 0; i< length; i++)
{
index = CHAR_TO_INDEX(word[i]);

if (!temp->children[index])
return 0;

temp = temp->children[index];
}

return (temp->flag);
}

int main()
{
char word[][15] = {"and","bat","ball","book","cot","cotton","internet","interview","joy","job","king","lion","man","mango","mango"};

char output[][32] = {"Not present in trie", "Present in trie"};

char word1[][15] = {0};


struct TrieNode *root = getNode();

// Construct trie
FILE* fp;


int i;

for (i = 0; i < ARRAY_SIZE(word); i++)
insert(root, word[i]);

// Search for different keys
printf("Present\t\t|\tNot Present\n");
printf("-----------------------------------\n");
printf("-----------------------------------\n");
fp = fopen("Trie.txt", "r");
int j=0;
while (fscanf(fp, "%s/t", word1) == 1)
{
for(int i=0;i < ARRAY_SIZE(word1); i++)
{
    //printf("%d",(search(root, word1[i])));
    if((search(root, word1[i])) == 1) {
                printf("%d) %s\t\t|\n", j+1, word1[i]);
    } else printf("%d)\t\t|\t%s\n", j+1, word1[i]);
//printf("%s --- %s\n\n", word1[i],output[search(root, word1[i])] );
}
j++;

}


return 0;
}


---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------

P7: Network Failure

#include<stdio.h>
#include<stdlib.h>
int min(int a,int b)
{
    return(a<b?a:b);
}
struct node
{
 int val;
 struct node* next;
};
struct graph
{  
 int v;
 struct node** arr;
};
struct graph* createGraph(int v)
{
    int i;
    struct graph* temp =(struct graph*)malloc(sizeof(struct graph));
    temp->v=v;
    for(i=0;i<v;i++)
     temp->arr=(int*)malloc(sizeof(int*)*v);
    for(i=0;i<v;i++)
     temp->arr[i]=NULL;
    return temp;
}
void addEdge(struct graph* g,int u,int v)
{
    struct node* temp =(struct node*)malloc(sizeof(struct node));
    temp->val = v;
    temp->next = g->arr[u];
    g->arr[u] = temp;    
}
void apUtil(struct graph * g,int node,int* isVisited,int* des,int* parent,int* low,int* ap)
{
    struct node* temp=NULL;
    static int time=0;
    int children=0;
    temp = g->arr[node];
    isVisited[node]=1;
    time++;
    //printf("\nsetting time for %d",node);
    des[node]=low[node]=time;

    while(temp!=NULL)
    {      
       if(!isVisited[temp->val])
        {
          children++;
          parent[temp->val]=node;
          apUtil(g,temp->val,isVisited,des,parent,low,ap);

      low[node]= min(low[node],low[temp->val]);

          if(parent[node]==-1 && children>1)
             ap[node]=1;

      if(parent[node]!=-1 && des[node]<=low[temp->val])
            ap[node]=1;          
        }    
        else if(temp->val!=parent[node])
        {
            low[node]=min(low[node],des[temp->val]);
        }
       temp= temp->next;
      }
     //printf("%d",node);
}
void AP(struct graph* g)
{
    int i;
    int* des = (int*)malloc(sizeof(int)*g->v);
    int* isVisited = (int*)malloc(sizeof(int)*g->v);
    int* parent = (int*)malloc(sizeof(int)*g->v);
    int* low = (int*)malloc(sizeof(int)*g->v);
    int* ap = (int*)malloc(sizeof(int)*g->v);
    for(i=0;i<g->v;i++)
    {
        isVisited[i]=0;
        parent[i]=-1;
        ap[i]=0;
    }
    for(i=0;i<g->v;i++)
    {
        if(isVisited[i]==0)
        {
            apUtil(g,i,isVisited,des,parent,low,ap);
        }
    }
    printf("\n");
    int flag=0;
    printf("\nPoint of failure in a Network");
    for(i=0;i<g->v;i++)
    {
       
        if(ap[i]==1)
 {
   flag=1;
   printf("\nVertex : %d",i);
 }
    }
    if(flag==0)
 printf("\nNo point found.");
}
int main()
{
   
    int size=0,edges=0,i,u,v;
    struct graph* g = createGraph(5);
    addEdge(g, 1, 0);
    addEdge(g, 0, 2);
    addEdge(g, 2, 1);
    addEdge(g, 0, 3);
    addEdge(g, 3, 4);
   
    AP(g);
}

---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------

P8a: Graph

#include<bits/stdc++.h>
using namespace std;

class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // to add an edge to graph
bool isCyclic(); // returns true if there is a cycle in this graph
};

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

// This function is a variation of DFSUtil() in https://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}

}
recStack[v] = false; // remove the vertex from recursion stack
return false;
}

// Returns true if the graph contains a cycle, else false.
// This function is a variation of DFS() in https://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}

// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if ( !visited[i] && isCyclicUtil(i, visited, recStack))
return true;

return false;
}

int main()
{
// Create a graph given in the above diagram
Graph g(4);

FILE *fptr;
int vrt;
int wt;
fptr = fopen("nfile.txt", "r");

while(fscanf(fptr, "%d    %d", &vrt, &wt)!=EOF)
    {
        g.addEdge(vrt, wt);
    }
fclose(fptr);



if(g.isCyclic())
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}

P8b: Cycle

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

#define MAX 100
#define initial 1
#define visited 2
#define finished 3

void CreateGraph();
void DFS(int v);
void DFSTraversal();

int num;
int state[MAX];
int matrix[MAX][MAX];

void DFSTraversal()
{
        int v;
        for(v=0;v<num;v++)
        {
                state[v]=1;
        }
        //Our Root Vertex Is 0
        DFS(0);
        for(v=0;v<num;v++)
        {
                if(state[v]==1)
                {
                        DFS(v);
                }
        }
        printf("Graph Is Acyclic\n");
}

void DFS(int v)
{
        int i;
        state[v]=2;
        for(i=0;i<num;i++)
        {
                if(matrix[v][i]==1)
                {
                        if(state[i]==1)
                        {
                                DFS(i);
                        }
                        else if(state[i]==2)
                        {
                                printf("Back Edge From %d To %d Found!\n",v,i);
                                printf("Graph Is Cyclic\n");
                                exit(1);
                        }
                }
        }
        state[v]=3;
}

void CreateGraph()
{
        int maxedges;
        int origin;
        int destin;
        int i=0;
        printf("Enter The Number Of Vertices: ");
        scanf("%d",&num);
        maxedges=num*(num-1);
        for(i=1;i<=maxedges;i++)
        {
                printf("Enter %d Edge(-1 -1 To Quit): ",i);
                scanf("%d %d",&origin,&destin);
                if((origin==-1) && (destin==-1))
                {
                        break;
                }
                if(origin>=num || destin>=num || origin<0 || destin<0)
                {
                        printf("Invalid Edge!\n");
                        i--;
                }
                else
                {
                        matrix[origin][destin]=1;
                }
        }
}

int main()
{
        CreateGraph();
        DFSTraversal();
        return 0;
}

P8c: Cycle from matrix

#include<iostream>
#include<set>
#define NODE 3
using namespace std;

/*
    {0, 1, 0, 0, 0},
   {0, 0, 0, 0, 0},
   {1, 0, 0, 1, 0},
   {0, 0, 0, 0, 1},
   {0, 0, 1, 0, 0}
*/

int graph[NODE][NODE] = {
   {0,1,0},
   {0,0,1},
   {1,0,0}
};

bool dfs(int curr, set<int>&wSet, set<int>&gSet, set<int>&bSet) {
   //moving curr to white set to grey set.
   wSet.erase(wSet.find(curr));
   gSet.insert(curr);

   for(int v = 0; v < NODE; v++) {
      if(graph[curr][v] != 0) {    //for all neighbour vertices
         if(bSet.find(v) != bSet.end())
            continue;    //if the vertices are in the black set
         if(gSet.find(v) != gSet.end())
            return true;    //it is a cycle
         if(dfs(v, wSet, gSet, bSet))
            return true;    //cycle found
      }
   }

   //moving v to grey set to black set.
   gSet.erase(gSet.find(curr));
   bSet.insert(curr);
   return false;
}

bool hasCycle() {
   set<int> wSet, gSet, bSet;    //three set as white, grey and black
   for(int i = 0; i<NODE; i++)
      wSet.insert(i);    //initially add all node into the white set

   while(wSet.size() > 0) {
      for(int current = 0; current < NODE; current++) {
         if(wSet.find(current) != wSet.end())
            if(dfs(current, wSet, gSet, bSet))
               return true;
      }
   }
   return false;
}

int main() {
   bool res;
   res = hasCycle();
   if(res)
      cout << "The graph has cycle" << endl;
   else
      cout << "The graph has no cycle" << endl;
}


posted by Himanshu Agarkar @ July 01, 2022   0 Comments

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home