// List using ADT
#include<stdio.h>
#include<stdlib.h>
int n, list[25];
void create();
int insert();
int del();
void display();
void find();
void main()
{
int ch;
printf("\n\t\t\t\tLIST USING ARRAY");
printf("\n\t\t\t\t**** ***** *****");
do
{
printf("\n\nMAIN MENU");
printf("\n1.Create\n2.Insert\n3.Delete\n4.Find\n5.Display\n6.Exit");
printf("\nEnter your choice");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\nenter the number of elements");
scanf("%d", &n);
create();
display();
break;
case 2:
n = insert();
display();
break;
case 3:
n = del();
display();
break;
case 4:
find();
break;
case 5:
display();
break;
case 6:
}
} while (ch <= 6);
}
int insert()
{
int i, ele, pos;
printf("\nEnter the number and position");
scanf("%d %d", &ele, &pos);
if (n == 25)
{
printf("\nlist is full");
return n;
}
else if (n == 0)
{
printf("\nlist has to be created first");
return 0;
}
else if (pos == n + 1)
{
list[pos] = ele;
n = n + 1;
return n;
}
else if (pos > n)
{
printf("\nnot valid");
return n;
}
else
{
for (i = n; i >= pos; i--)
list[i + 1] = list[i];
list[pos] = ele;
n = n + 1;
return n;
}
}
void create()
{
int i;
printf("\nlist to be created:");
for (i = 1; i <= n; i++)
scanf("%d", &list[i]);
}
int del()
{
int i, pos;
printf("enter the position to be deleted:");
scanf("%d", &pos);
for (i = pos; i <= n; i++)
list[i] = list[i + 1];
n--;
return n;
}
void find()
{
int i, find;
printf("\nenter the data to be searched:");
scanf("%d", &find);
if (n == 0)
{
printf("list is empty");
return;
}
else
{
for (i = 1; i <= n; i++)
if (list[i] == find)
{
printf("\nthe element %d is positioned at %d\n", find, i);
getch();
return;
}
}
printf("\nelement is not found");
return;
}
void display()
{
int i;
if (n == 0)
printf("\nlist is empty");
else
{
for (i = 1; i <= n; i++)
printf("\t%d", list[i]);
}
}
#include <stdio.h>
#include <stdlib.h>
void create();
void insert();
void delet();
void display();
struct node
{
int data;
struct node *link;
};
struct node *first = NULL, *last = NULL, *next, *prev, *cur;
void create()
{
cur = (struct node *)malloc(sizeof(struct node));
printf("\nENTER THE DATA: ");
scanf("%d", &cur->data);
cur->link = NULL;
first = cur;
last = cur;
}
void insert()
{
int pos, c = 1;
cur = (struct node *)malloc(sizeof(struct node));
printf("\nENTER THE DATA: ");
scanf("%d", &cur->data);
printf("\nENTER THE POSITION: ");
scanf("%d", &pos);
if ((pos == 1) && (first != NULL))
{
cur->link = first;
first = cur;
}
else
{
next = first;
while (c < pos)
{
prev = next;
next = prev->link;
c++;
}
if (prev == NULL)
{
printf("\nINVALID POSITION\n");
}
else
{
cur->link = prev->link;
prev->link = cur;
}
}
}
void delet()
{
int pos, c = 1;
printf("\nENTER THE POSITION : ");
scanf("%d", &pos);
if (first == NULL)
{
printf("\nLIST IS EMPTY\n");
}
else if (pos == 1 && first->link == NULL)
{
printf("\n DELETED ELEMENT IS %d\n", first->data);
free(first);
first = NULL;
}
else if (pos == 1 && first->link != NULL)
{
cur = first;
first = first->link;
cur->link = NULL;
printf("\n DELETED ELEMENT IS %d\n", cur->data);
free(cur);
}
else
{
next = first;
while (c < pos)
{
cur = next;
next = next->link;
c++;
}
cur->link = next->link;
next->link = NULL;
if (next == NULL)
{
printf("\nINVALID POSITION\n");
}
else
{
printf("\n DELETED ELEMENT IS %d\n", next->data);
free(next);
}
}
}
void display()
{
cur = first;
while (cur != NULL)
{
printf("\n %d", cur->data);
cur = cur->link;
}
}
void main()
{
int ch;
printf("\nSINGLY LINKED LIST");
do
{
printf("\n\n1.CREATE\n2.INSERT\n3.DELETE\n4.EXIT");
printf("\nENTER YOUR CHOICE : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
create();
display();
break;
case 2:
insert();
display();
break;
case 3:
delet();
display();
break;
case 4:
exit(0);
}
} while (ch <= 3);
}
#include <stdio.h>
#include <stdlib.h>
void create();
void insert();
void del();
void display();
struct node
{
int data;
struct node *flink, *blink;
};
struct node *first = NULL, *last = NULL, *next, *prev, *cur;
void create()
{
cur = (struct node *)malloc(sizeof(struct node));
printf("Enter the data:");
scanf("%d", &cur->data);
cur->flink = NULL;
cur->blink = NULL;
first = cur;
last = cur;
}
void insert()
{
int pos, c = 1;
cur = (struct node *)malloc(sizeof(struct node));
printf("Enter the data:");
scanf("%d", &cur->data);
printf("Enter the position:");
scanf("%d", &pos);
if (pos == 1 && first != NULL)
{
cur->flink = first;
cur->blink = NULL;
first->blink = cur;
first = cur;
}
else
{
next = first;
while (c < pos)
{
prev = next;
next = prev->flink;
c++;
}
if (prev == NULL)
{
printf("Invalid position");
}
else
{
cur->flink = prev->flink;
cur->blink = prev;
prev->flink->blink = cur;
prev->flink = cur;
}
}
}
void del()
{
int pos, c = 1;
printf("Enter the position to be deleted");
scanf("%d", &pos);
if (first == NULL)
{
printf("DLL is empty");
}
else if (pos == 1 && first->flink == NULL)
{
printf("Deleted element is %d", first->data);
free(first);
first = NULL;
last = NULL;
}
else if (pos == 1 && first->flink != NULL)
{
cur = first;
first = first->flink;
cur->flink = NULL;
first->blink = NULL;
}
else
{
next = first;
while (c < pos)
{
cur = next;
next = next->flink;
c++;
}
if (next == NULL)
{
printf("Invalid position");
}
else
{
cur->flink = next->flink;
next->flink->blink = cur;
next->flink = NULL;
next->blink = NULL;
printf("Deleted element is %d", next->data);
free(next);
}
}
}
void display()
{
cur = first;
printf("\n The elements in the list are:");
while (cur != NULL)
{
printf("%d\t", cur->data);
cur = cur->flink;
}
}
void main()
{
int ch;
printf("Doubly linked list:");
do
{
printf("\n 1.Create \n 2.Insert \n 3.Delete \n 4.Exit");
printf("\n\nEnter your option");
scanf("%d", &ch);
switch (ch)
{
case 1:
create();
display();
break;
case 2:
insert();
display();
break;
case 3:
del();
display();
break;
case 4:
exit(0);
}
} while (ch <= 3);
}
#include <stdio.h>
#include <stdlib.h>
int i, top, item, s[10];
int max = 10;
void push(int item, int s[]);
void pop(int s[]);
void display(int s[]);
void main()
{
int ch;
top = -1;
do
{
printf("\n\n 1.PUSH \n 2.POP \n 3.EXIT \n");
printf("\n ENTER YOUR CHOICE : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\t PUSH \n");
if (top >= max - 1)
{
printf("\n STACK IS FULL\n");
}
else
{
printf("\n ENTER AN ELEMENT : ");
scanf("%d", &item);
push(item, s);
}
display(s);
break;
case 2:
printf("\t\n POP \n");
if (top < 0)
{
printf("\nSTACK IS EMPTY\n");
}
else
{
pop(s);
}
display(s);
break;
}
} while (ch != 3);
}
void push(int item, int s[])
{
top = top + 1;
s[top] = item;
}
void pop(int s[])
{
item = s[top];
top = top - 1;
printf("\nDELETED ELEMENT IS %d\n", item);
}
void display(int s[])
{
printf("\n");
for (i = top; i >= 0; i--)
{
printf(" \n %d", s[i]);
}
}
#include <stdio.h>
#include <stdlib.h>
int i, rear, front, item, s[10];
void insert(int item, int s[]);
void del(int s[]);
void display(int s[]);
void main()
{
int ch;
front = 0;
rear = -1;
do
{
printf("\n\n 1.INSERTION \n 2.DELETION \n 3.EXIT \n");
printf("\nENTER YOUR CHOICE : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\n\t INSERTION \n");
if (rear >= 9)
{
printf("\t\nQUEUE IS FULL\n");
}
else
{
printf("\nENTER AN ELEMENT : ");
scanf("%d", &item);
insert(item, s);
}
display(s);
break;
case 2:
printf("\n\t DELETION \n");
if (front > rear)
{
printf("\t\nQUEUE IS EMPTY\n");
}
else
{
del(s);
}
display(s);
break;
}
} while (ch != 3);
}
void insert(int item, int s[])
{
rear = rear + 1;
s[rear] = item;
}
void del(int s[])
{
item = s[front];
front = front + 1;
printf("\n DELETED ELEMENT IS %d\n\n", item);
}
void display(int s[])
{
printf("\n");
for (i = front; i <= rear; i++)
{
printf(" \t %d", s[i]);
}
}
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *cur, *first;
void create();
void push();
void pop();
void display();
void create()
{
printf("\nENTER THE FIRST ELEMENT: ");
cur = (struct node *)malloc(sizeof(struct node));
scanf("%d", &cur->data);
cur->link = NULL;
first = cur;
}
void display()
{
cur = first;
printf("\n");
while (cur != NULL)
{
printf("%d\n", cur->data);
cur = cur->link;
}
}
void push()
{
printf("\nENTER THE NEXT ELEMENT: ");
cur = (struct node *)malloc(sizeof(struct node));
scanf("%d", &cur->data);
cur->link = first;
first = cur;
}
void pop()
{
if (first == NULL)
{
printf("\nSTACK IS EMPTY\n");
}
else
{
cur = first;
printf("\nDELETED ELEMENT IS %d\n", first->data);
first = first->link;
free(cur);
}
}
void main()
{
int ch;
while (1)
{
printf("\n\n 1.CREATE \n 2.PUSH \n 3.POP \n 4.EXIT \n");
printf("\n ENTER YOUR CHOICE : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
create();
display();
break;
case 2:
push();
display();
break;
case 3:
pop();
display();
break;
case 4:
exit(0);
}
}
}
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *cur, *first, *last;
void create();
void insert();
void delte();
void display();
void create()
{
printf("\nENTER THE FIRST ELEMENT: ");
cur = (struct node *)malloc(sizeof(struct node));
scanf("%d", &cur->data);
cur->link = NULL;
first = cur;
last = cur;
}
void insert()
{
printf("\nENTER THE NEXT ELEMENT: ");
cur = (struct node *)malloc(sizeof(struct node));
scanf("%d", &cur->data);
cur->link = NULL;
last->link = cur;
last = cur;
}
void delte()
{
if (first == NULL)
{
printf("\t\nQUEUE IS EMPTY\n");
}
else
{
cur = first;
first = first->link;
cur->link = NULL;
printf("\n DELETED ELEMENT IS %d\n", cur->data);
free(cur);
}
}
void display()
{
cur = first;
printf("\n");
while (cur != NULL)
{
printf("\t%d", cur->data);
cur = cur->link;
}
}
void main()
{
int ch;
while (1)
{
printf("\n\n 1.CREATE \n 2.INSERT \n 3.DELETE \n 4.EXIT \n");
printf("\nENTER YOUR CHOICE : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
create();
display();
break;
case 2:
insert();
display();
break;
case 3:
delte();
display();
break;
case 4:
exit(0);
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct link
{
int coeff;
int pow;
struct link *next;
};
struct link *poly1 = NULL, *poly2 = NULL, *poly = NULL;
void create(struct link *node)
{
int ch;
do
{
printf("\n Enter coeff:");
scanf("%d", &node->coeff);
printf("\n Enter power:");
scanf("%d", &node->pow);
node->next = (struct link *)malloc(sizeof(struct link));
node = node->next;
node->next = NULL;
printf("\n To Continue press any no (Press 0 to exit):");
scanf("%d", &ch);
} while (ch > 0);
}
void show(struct link *node)
{
while (node->next != NULL)
{
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->next != NULL)
printf("+");
}
}
void polyadd(struct link *poly1, struct link *poly2, struct link *poly)
{
while (poly1->next && poly2->next)
{
if (poly1->pow > poly2->pow)
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
else if (poly1->pow < poly2->pow)
{
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
else
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff + poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}
poly->next = (struct link *)malloc(sizeof(struct link));
poly = poly->next;
poly->next = NULL;
}
while (poly1->next || poly2->next)
{
if (poly1->next)
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
if (poly2->next)
{
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
poly->next = (struct link *)malloc(sizeof(struct link));
poly = poly->next;
poly->next = NULL;
}
}
main()
{
poly1 = (struct link *)malloc(sizeof(struct link));
poly2 = (struct link *)malloc(sizeof(struct link));
poly = (struct link *)malloc(sizeof(struct link));
printf("\nEnter 1st number:");
create(poly1);
printf("\nEnter 2nd number:");
create(poly2);
printf("\n1st Number:");
show(poly1);
printf("\n2nd Number:");
show(poly2);
polyadd(poly1, poly2, poly);
printf("\nAdded polynomial:");
show(poly);
}
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define SIZE 20
char Expr[SIZE];
char Stack[SIZE];
int Top = -1;
void push(char ch);
void pop();
void infix_to_postfix();
int m, l;
void main()
{
char ch;
printf("Program to covert infix expression into postfix expression:\n");
printf("Enter your expression & to quit enter fullstop(.)\n");
while ((ch = getc(stdin)) != '\n')
{
Expr[m] = ch;
m++;
}
l = m;
infix_to_postfix();
}
void push(char ch)
{
if (Top + 1 >= SIZE)
{
printf("\nStack is full");
}
else
{
Top = Top + 1;
Stack[Top] = ch;
}
}
void pop()
{
if (Top < 0)
{
printf("\n Stack is empty");
}
else
{
if (Top >= 0)
{
if (Stack[Top] != '(')
printf("%c", Stack[Top]);
Top = Top - 1;
}
}
}
void infix_to_postfix()
{
m = 0;
while (m < l)
{
switch (Expr[m])
{
case '+':
case '-':
while (Stack[Top] == '-' || Stack[Top] == '+' || Stack[Top] == '*' || Stack[Top] == '/' || Stack[Top] == '^' && Stack[Top] != '(')
pop();
push(Expr[m]);
++m;
break;
case '/':
case '*':
while (Stack[Top] == '*' || Stack[Top] == '/' || Stack[Top] == '^' && Stack[Top] != '(')
pop();
push(Expr[m]);
++m;
break;
case '^':
push(Expr[m]);
++m;
break;
case '(':
push(Expr[m]);
++m;
break;
case ')':
while (Stack[Top] != '(')
pop();
pop();
++m;
break;
case '.':
while (Top >= 0)
pop();
exit(0);
default:
if (isalpha(Expr[m]))
{
printf("%c", Expr[m]);
++m;
break;
}
else
{
printf("\n Some error");
exit(0);
}
}
}
}
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int pop();
int i, l, top = -1, value[25], val, p, q, r;
char a[25], x;
void main()
{
printf("\nEnter the postfix expression\n");
gets(a);
l = strlen(a);
for (i = 0; i < l; i++)
{
if (isalpha(a[i]))
{
printf("\nEnter the value for %c", a[i]);
scanf("%d", &val);
top = top + 1;
value[top] = val;
}
else
{
x = a[i];
p = pop();
q = pop();
switch (x)
{
case '+':
r = p + q;
top = top + 1;
value[top] = r;
break;
case '-':
r = q - p;
top = top + 1;
value[top] = r;
break;
case '*':
r = p * q;
top = top + 1;
value[top] = r;
break;
case '/':
r = q / p;
top = top + 1;
value[top] = r;
break;
}
}
}
r = value[top];
printf("\nValue of expression is %d", r);
}
int pop()
{
int ch;
ch = value[top];
top = top - 1;
return ch;
}
#include <stdio.h>
#include <stdlib.h>
struct tree
{
int data;
struct tree *lchild;
struct tree *rchild;
} *t, *temp;
int element;
void inorder(struct tree *);
void preorder(struct tree *);
void postorder(struct tree *);
struct tree *create(struct tree *, int);
struct tree *find(struct tree *, int);
struct tree *insert(struct tree *, int);
struct tree *del(struct tree *, int);
struct tree *findmin(struct tree *);
struct tree *findmax(struct tree *);
int main()
{
int ch;
do
{
printf("\n\t\t\tBINARY SEARCH TREE");
printf("\n\t\t\t****** ****** ****");
printf("\nMain Menu\n");
printf("\n1.Create\n2.Insert\n3.Delete\n4.Find\n5.FindMin\n6.FindMax");
printf("\n7.Inorder\n8.Preorder\n9.Postorder\n10.Exit\n");
printf("\nEnter ur choice :");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\nEnter the data:");
scanf("%d", &element);
t = create(t, element);
inorder(t);
break;
case 2:
printf("\nEnter the data:");
scanf("%d", &element);
t = insert(t, element);
inorder(t);
break;
case 3:
printf("\nEnter the data:");
scanf("%d", &element);
t = del(t, element);
inorder(t);
break;
case 4:
printf("\nEnter the data:");
scanf("%d", &element);
temp = find(t, element);
if (temp->data == element)
printf("Element is found");
else
printf("\nElement is not found");
break;
case 5:
temp = findmin(t);
printf("\nMax element=%d", temp->data);
break;
case 6:
temp = findmax(t);
printf("\nMax element=%d", temp->data);
break;
case 7:
inorder(t);
break;
case 8:
preorder(t);
break;
case 9:
postorder(t);
break;
case 10:
exit(0);
}
} while (ch <= 10);
}
struct tree *create(struct tree *t, int element)
{
t = (struct tree *)malloc(sizeof(struct tree));
t->data = element;
t->lchild = NULL;
t->rchild = NULL;
return t;
}
struct tree *find(struct tree *t, int element)
{
if (t == NULL)
return NULL;
if (element < t->data)
return (find(t->lchild, element));
else if (element > t->data)
return (find(t->rchild, element));
else
return t;
}
struct tree *findmin(struct tree *t)
{
if (t == NULL)
return NULL;
else if (t->lchild == NULL)
return t;
else
return (findmin(t->lchild));
}
struct tree *findmax(struct tree *t)
{
if (t != NULL)
{
while (t->rchild != NULL)
t = t->rchild;
}
return t;
}
struct tree *insert(struct tree *t, int element)
{
if (t == NULL)
{
t = (struct tree *)malloc(sizeof(struct tree));
t->data = element;
t->lchild = NULL;
t->rchild = NULL;
return t;
}
else
{
if (element < t->data)
{
t->lchild = insert(t->lchild, element);
}
else if (element > t->data)
{
t->rchild = insert(t->rchild, element);
}
else if (element == t->data)
{
printf("element already present\n");
}
return t;
}
}
struct tree *del(struct tree *t, int element)
{
if (t == NULL)
printf("element not found\n");
else if (element < t->data)
t->lchild = del(t->lchild, element);
else if (element > t->data)
t->rchild = del(t->rchild, element);
else if (t->lchild && t->rchild)
{
temp = findmin(t->rchild);
t->data = temp->data;
t->rchild = del(t->rchild, t->data);
}
else
{
temp = t;
if (t->lchild == NULL)
t = t->rchild;
else if (t->rchild == NULL)
t = t->lchild;
free(temp);
}
return t;
}
void inorder(struct tree *t)
{
if (t == NULL)
return;
else
{
inorder(t->lchild);
printf("\t%d", t->data);
inorder(t->rchild);
}
}
void preorder(struct tree *t)
{
if (t == NULL)
return;
else
{
printf("\t%d", t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void postorder(struct tree *t)
{
if (t == NULL)
return;
else
{
postorder(t->lchild);
postorder(t->rchild);
printf("\t%d", t->data);
}
}
#include <stdio.h>
#include <stdlib.h>
struct avltree
{
int data;
struct avltree *left, *right;
int height;
} *t;
int x;
void inorder(struct avltree *);
static int height(struct avltree *);
static int max(int, int);
struct avltree *insertion(struct avltree *, int);
struct avltree *singlerotationwithleft(struct avltree *k2);
struct avltree *singlerotationwithright(struct avltree *k1);
struct avltree *doublerotationwithleft(struct avltree *k3);
struct avltree *doublerotationwithright(struct avltree *k1);
void main()
{
int choice;
printf("\nAVL TREE");
do
{
printf("\nMAIN MENU");
printf("\n1.INSERTION \n2.INORDER DISPLAY \n3.EXIT");
printf("\nENTER YOUR CHOICE");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("\nENTER DATA");
scanf("%d", &x);
t = insertion(t, x);
inorder(t);
break;
case 2:
inorder(t);
break;
case 3:
exit(0);
break;
}
} while (choice <= 2);
}
struct avltree *insertion(struct avltree *t, int x)
{
if (t == NULL)
{
t = (struct avltree *)malloc(sizeof(struct avltree));
t->data = x;
t->left = t->right = NULL;
t->height = 0;
}
else if (x < t->data)
{
t->left = insertion(t->left, x);
if ((height(t->left) - height(t->right)) == 2)
{
if (x < t->left->data)
t = singlerotationwithleft(t);
else
t = doublerotationwithleft(t);
}
}
else if (x > t->data)
{
t->right = insertion(t->right, x);
if ((height(t->right) - height(t->left)) == 2)
{
if (x > t->right->data)
t = singlerotationwithright(t);
else
t = doublerotationwithright(t);
}
}
t->height = max(height(t->left), height(t->right)) + 1;
return t;
}
struct avltree *singlerotationwithleft(struct avltree *k2)
{
struct avltree *k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1->height = max(height(k1->left), height(k2)) + 1;
return k1;
}
struct avltree *singlerotationwithright(struct avltree *k1)
{
struct avltree *k2;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->right), height(k1->left)) + 1;
k2->height = max(height(k2->right), height(k1)) + 1;
return k2;
}
struct avltree *doublerotationwithleft(struct avltree *k3)
{
k3->left = singlerotationwithright(k3->left);
return singlerotationwithleft(k3);
}
struct avltree *doublerotationwithright(struct avltree *k1)
{
k1->right = singlerotationwithleft(k1->right);
return singlerotationwithright(k1);
}
void inorder(struct avltree *t)
{
if (t != NULL)
{
inorder(t->left);
printf(" %d ", t->data);
inorder(t->right);
}
}
int height(struct avltree *t)
{
if (t == NULL)
return -1;
else
return t->height;
}
static int max(int left, int right)
{
return left > right ? left : right;
}
#include <stdio.h>
#include <malloc.h>
void insert();
void del();
void display();
struct node
{
int priority;
int info;
struct node *next;
} *start = NULL, *q, *temp, *new;
typedef struct node N;
int main()
{
int ch;
do
{
printf("\n[1] INSERTION\t[2] DELETION\t[3] DISPLAY [4] EXIT\t:");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
break;
}
} while (ch < 4);
}
void insert()
{
int item, itprio;
new = (N *)malloc(sizeof(N));
printf("ENTER THE ELT.TO BE INSERTED :\t");
scanf("%d", &item);
printf("ENTER ITS PRIORITY :\t");
scanf("%d", &itprio);
new->info = item;
new->priority = itprio;
new->next = NULL;
if (start == NULL)
{
// new->next=start;
start = new;
}
else if (start != NULL && itprio <= start->priority)
{
new->next = start;
start = new;
}
else
{
q = start;
while (q->next != NULL && q->next->priority <= itprio)
{
q = q->next;
}
new->next = q->next;
q->next = new;
}
}
void del()
{
if (start == NULL)
{
printf("\nQUEUE UNDERFLOW\n");
}
else
{
new = start;
printf("\nDELETED ITEM IS %d\n", new->info);
start = start->next;
// free(start);
}
}
void display()
{
temp = start;
if (start == NULL)
printf("QUEUE IS EMPTY\n");
else
{
printf("QUEUE IS:\n");
if (temp != NULL)
for (temp = start; temp != NULL; temp = temp->next)
{
printf("\n%d priority =%d\n", temp->info, temp->priority);
}
}
}
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define V 4
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void printSolution(int dist[])
{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t\t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
int main()
{
int graph[V][V] = {{0, 4, 0, 0},
{4, 0, 8, 0},
{0, 8, 0, 7},
{0, 0, 7, 0}};
dijkstra(graph, 0);
return 0;
}
#include <stdio.h>
void floyd(int a[4][4], int n)
{
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (a[i][j] > a[i][k] + a[k][j])
{
a[i][j] = a[i][k] + a[k][j];
}
}
}
}
printf("All Pairs Shortest Path is :\n");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
}
int main()
{
int cost[4][4] = {{0, 2, 10, 999}, {999, 0, 3, 6}, {8, 999, 0, 4}, {7, 999, 999, 0}};
int n = 4;
floyd(cost, n);
}
#include <stdio.h>
#include <stdlib.h>
int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];
int find(int);
int uni(int, int);
void main()
{
printf("Kruskal's algorithm in C\n");
printf("========================\n");
printf("Enter the no. of vertices:\n");
scanf("%d", &n);
printf("\nEnter the cost adjacency matrix:\n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
cost[i][j] = 999;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
while (ne < n)
{
for (i = 1, min = 999; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (cost[i][j] < min)
{
min = cost[i][j];
a = u = i;
b = v = j;
}
}
}
u = find(u);
v = find(v);
if (uni(u, v))
{
printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);
mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}
printf("\nMinimum cost = %d\n", mincost);
}
int find(int i)
{
while (parent[i])
i = parent[i];
return i;
}
int uni(int i, int j)
{
if (i != j)
{
parent[j] = i;
return 1;
}
return 0;
}
#include <stdio.h>
#include <stdbool.h>
#define INF 9999999
#define V 5
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}};
int main()
{
int no_edge;
int selected[V];
memset(selected, false, sizeof(selected));
no_edge = 0;
selected[0] = true;
int x;
int y;
printf("Edge : Weight\n");
while (no_edge < V - 1)
{
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++)
{
if (selected[i])
{
for (int j = 0; j < V; j++)
{
if (!selected[j] && G[i][j])
{
if (min > G[i][j])
{
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
printf("%d - %d : %d\n", x, y, G[x][y]);
selected[y] = true;
no_edge++;
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef struct Q
{
int data[MAX];
int R, F;
} Q;
typedef struct node
{
struct node *next;
int vertex;
} node;
void enqueue(Q *, int);
int dequque(Q *);
int empty(Q *);
int full(Q *);
void BFS(int);
void readgraph(); // create an adjecency list
void insert(int vi, int vj); // insert an edge (vi,vj)in adj.list
void DFS(int i);
int visited[MAX];
node *G[20]; // heads of the linked list
int n; // no of nodes
void main()
{
int i, op;
do
{
printf("\n\n1)Create\n2)BFS\n3)DFS\n4)Quit");
printf("\nEnter Your Choice: ");
scanf("%d", &op);
switch (op)
{
case 1:
readgraph();
break;
case 2:
printf("\nStarting Node No. : ");
scanf("%d", &i);
BFS(i);
break;
case 3:
for (i = 0; i < n; i++)
visited[i] = 0;
printf("\nStarting Node No. : ");
scanf("%d", &i);
DFS(i);
break;
}
} while (op != 4);
}
void BFS(int v)
{
int w, i, visited[MAX];
Q q;
node *p;
q.R = q.F = -1; // initialize
for (i = 0; i < n; i++)
visited[i] = 0;
enqueue(&q, v);
printf("\nVisit\t%d", v);
visited[v] = 1;
while (!empty(&q))
{
v = dequeue(&q);
// insert all unvisited,adjacent vertices of v into queue
for (p = G[v]; p != NULL; p = p->next)
{
w = p->vertex;
if (visited[w] == 0)
{
enqueue(&q, w);
visited[w] = 1;
printf("\nvisit\t%d", w);
}
}
}
}
void DFS(int i)
{
node *p;
printf("\n%d", i);
p = G[i];
visited[i] = 1;
while (p != NULL)
{
i = p->vertex;
if (!visited[i])
DFS(i);
p = p->next;
}
}
int empty(Q *P)
{
if (P->R == -1)
return (1);
return (0);
}
int full(Q *P)
{
if (P->R == MAX - 1)
return (1);
return (0);
}
void enqueue(Q *P, int x)
{
if (P->R == -1)
{
P->R = P->F = 0;
P->data[P->R] = x;
}
else
{
P->R = P->R + 1;
P->data[P->R] = x;
}
}
int dequeue(Q *P)
{
int x;
x = P->data[P->F];
if (P->R == P->F)
{
P->R = -1;
P->F = -1;
}
else
P->F = P->F + 1;
return (x);
}
void readgraph()
{
int i, vi, vj, no_of_edges;
printf("\nEnter no. of vertices :");
scanf("%d", &n);
// initialise G[] with NULL
for (i = 0; i < n; i++)
G[i] = NULL;
// read edges and insert them in G[]
printf("\nEnter no of edges :");
scanf("%d", &no_of_edges);
for (i = 0; i < no_of_edges; i++)
{
printf("\nEnter an edge (u,v) :");
scanf("%d%d", &vi, &vj);
insert(vi, vj);
insert(vj, vi);
}
}
void insert(int vi, int vj)
{
node *p, *q;
// acquire memory for the new node
q = (node *)malloc(sizeof(node));
q->vertex = vj;
q->next = NULL;
// insert the node in the linked list for the vertex no. vi
if (G[vi] == NULL)
G[vi] = q;
else
{
// go to the end of linked list
p = G[vi];
while (p->next != NULL)
p = p->next;
p->next = q;
}
}
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int n; /*Number of vertices in the graph*/
int adj[MAX][MAX]; /*Adjacency Matrix*/
void create_graph();
int queue[MAX], front = -1, rear = -1;
void insert_queue(int v);
int delete_queue();
int isEmpty_queue();
int indegree(int v);
int main()
{
int i, v, count, topo_order[MAX], indeg[MAX];
create_graph();
/*Find the indegree of each vertex*/
for (i = 0; i < n; i++)
{
indeg[i] = indegree(i);
if (indeg[i] == 0)
insert_queue(i);
}
count = 0;
while (!isEmpty_queue() && count < n)
{
v = delete_queue();
topo_order[++count] = v; /*Add vertex v to topo_order array*/
/*Delete all edges going fron vertex v */
for (i = 0; i < n; i++)
{
if (adj[v][i] == 1)
{
adj[v][i] = 0;
indeg[i] = indeg[i] - 1;
if (indeg[i] == 0)
insert_queue(i);
}
}
}
if (count < n)
{
printf("\nNo topological ordering possible, graph contains cycle\n");
exit(1);
}
printf("\nVertices in topological order are :\n");
for (i = 1; i <= count; i++)
printf("%d ", topo_order[i]);
printf("\n");
return 0;
} /*End of main()*/
void insert_queue(int vertex)
{
if (rear == MAX - 1)
printf("\nQueue Overflow\n");
else
{
if (front == -1) /*If queue is initially empty */
front = 0;
rear = rear + 1;
queue[rear] = vertex;
}
} /*End of insert_queue()*/
int isEmpty_queue()
{
if (front == -1 || front > rear)
return 1;
else
return 0;
} /*End of isEmpty_queue()*/
int delete_queue()
{
int del_item;
if (front == -1 || front > rear)
{
printf("\nQueue Underflow\n");
exit(1);
}
else
{
del_item = queue[front];
front = front + 1;
return del_item;
}
} /*End of delete_queue() */
int indegree(int v)
{
int i, in_deg = 0;
for (i = 0; i < n; i++)
if (adj[i][v] == 1)
in_deg++;
return in_deg;
} /*End of indegree() */
void create_graph()
{
int i, max_edges, origin, destin;
printf("\nEnter number of vertices : ");
scanf("%d", &n);
max_edges = n * (n - 1);
for (i = 1; i <= max_edges; i++)
{
printf("\nEnter edge %d(-1 -1 to quit): ", i);
scanf("%d %d", &origin, &destin);
if ((origin == -1) && (destin == -1))
break;
if (origin >= n || destin >= n || origin < 0 || destin < 0)
{
printf("\nInvalid edge!\n");
i--;
}
else
adj[origin][destin] = 1;
}
}
#include <math.h>
#include <stdio.h>
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n - 1; i++)
{
min_idx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
if (min_idx != i)
swap(&arr[min_idx], &arr[i]);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
#include <stdio.h>
int partition(int a[], int start, int end)
{
int pivot = a[end]; // pivot element
int i = (start - 1);
for (int j = start; j <= end - 1; j++)
{
if (a[j] < pivot)
{
i++;
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i + 1];
a[i + 1] = a[end];
a[end] = t;
return (i + 1);
}
void quick(int a[], int start, int end)
{
if (start < end)
{
int p = partition(a, start, end); // p is the partitioning index
quick(a, start, p - 1);
quick(a, p + 1, end);
}
}
void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = {24, 9, 29, 14, 19, 27};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quick(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
#include <stdio.h>
void main()
{
int array[100], search, c, n;
printf("Enter the Number of elements\n");
scanf("%d", &n);
printf("Enter the Elements\n");
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter the number to search\n");
scanf("%d", &search);
for (c = 0; c < n; c++)
{
if (array[c] == search)
{
printf("%d is present at location %d.\n", search, c + 1);
break;
}
}
if (c == n)
{
printf("%d is not present in array.\n", search);
}
}
#include <stdio.h>
int BinarySearch(int *array, int n, int key)
{
int low = 0, high = n - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (array[mid] < key)
{
low = mid + 1;
}
else if (array[mid] == key)
{
return mid;
}
else if (array[mid] > key)
{
high = mid - 1;
}
}
return -1;
}
int main()
{
int n = 5;
int array[n];
int i, key, index;
printf("\nEnter the 5 elements");
// scanf("%d",&n);
printf("\nEnter the elements");
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
for (i = 1; i < n; i++)
{
if (array[i] < array[i - 1])
{
printf("Given input is not sorted\n");
return 0;
}
}
printf("Enter the key to be searched");
scanf("%d", &key);
index = BinarySearch(array, n, key);
if (index == -1)
{
printf("Element not found\n");
}
else
{
printf("Element is at index %d\n", index);
}
return 0;
}
#include <stdio.h>
int tsize;
int hasht(int key)
{
int i;
i = key % tsize;
return i;
}
//-------LINEAR PROBING-------
int rehashl(int key)
{
int i;
i = (key + 1) % tsize;
return i;
}
//-------QUADRATIC PROBING-------
int rehashq(int key, int j)
{
int i;
i = (key + (j * j)) % tsize;
return i;
}
void main()
{
int key, arr[20], hash[20], i, n, s, op, j, k;
printf("Enter the size of the hash table: ");
scanf("%d", &tsize);
printf("\nEnter the number of elements: ");
scanf("%d", &n);
for (i = 0; i < tsize; i++)
hash[i] = -1;
printf("Enter Elements: ");
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
do
{
printf("\n\n1.Linear Probing\n2.Quadratic Probing \n3.Exit \nEnter your option: ");
scanf("%d", &op);
switch (op)
{
case 1:
for (i = 0; i < tsize; i++)
hash[i] = -1;
for (k = 0; k < n; k++)
{
key = arr[k];
i = hasht(key);
while (hash[i] != -1)
{
i = rehashl(i);
}
hash[i] = key;
}
printf("\nThe elements in the array are: ");
for (i = 0; i < tsize; i++)
{
printf("\n Element at position %d: %d", i, hash[i]);
}
break;
case 2:
for (i = 0; i < tsize; i++)
hash[i] = -1;
for (k = 0; k < n; k++)
{
j = 1;
key = arr[k];
i = hasht(key);
while (hash[i] != -1)
{
i = rehashq(i, j);
j++;
}
hash[i] = key;
}
printf("\nThe elements in the array are: ");
for (i = 0; i < tsize; i++)
{
printf("\n Element at position %d: %d", i, hash[i]);
}
break;
}
} while (op != 3);
}