Data Structures and Algorithms
Polynomial Addition
1.Start 2. If (deg1>deg2) 2.1 for(i=0;i
c[m].coeff=a[i].coeff+b[i].coeff
c[m].exp=a[i].exp 2.2 for(i=deg2+1;i
c[n].coeff=a[i].coeff
c[m].exp=a[i].exp 3. Else 3.1 for(i=0;i
c[m].coeff=a[i]coeff+b[i].coeff
c[m].exp=a[i].exp
m++ 3.2 for(i=deg+1;i
c[m].coeff=b[i].coeff
c[n].exp=b[i].exp
m++ 4. End if 5. Print c[] 6.Stop
#include struct poly { float coeff; int exp; };
struct poly a[50],b[50],c[50],d[50];
int main() { int i; int deg1,deg2; int k=0,l=0,m=0; printf(“Enter the highest degree of poly1:”); scanf(“%d”,°1);
for(i=0;i
for(i=0;i
printf(“\nExpression 1 = %.1f”,a[0].coeff); for(i=1;i{ printf(“+ %.1fx^%d”,a[i].coeff,a[i].exp); } printf(“\nExpression 2 = %.1f”,b[0].coeff); for(i=1;ideg2) {for(i=0;ic[m].coeff = a[i].coeff + b[i].coeff; c[m].exp = a[i].exp;
m++; } for(i=deg2+1;i
else { for(i=0;i
m++;
} for(i=deg1+1;i
{c[m].coeff = b[i].coeff; c[m].exp = b[i].exp; m++; } }
printf(“\nExpression after additon = %.1f”,c[0].coeff); for(i=1;i
printf(“+ %.1fx^%d”,c[i].coeff,c[i].exp); }
return 0; }
Stack using Array
Push(s, item)
1. If top = max-1 1.1 print “stack is full”1.2 exit2. else 2.1 top++ 2.2 s[top]=item 3.end if 4.stop
Pop()
1.If(top==-1)1.1 print “stack is empty” 1.2 exit 2. Else 2.1 item=s[top] 2.2 top – – 3.end if 4.stop
#include
#include
#define MAX 5 //Maximum number of elements that can be stored int top=-1,stack[MAX];
void push();
void pop();
void display();
void main()
{int ch;
while(1) //infinite loop, will end when choice will be 4
{printf(“\n—Stack Options—“); printf(“\n\n1.Push\n2.Pop\n3.Display\n4.Exit”);
printf(“\n\nEnter your choice(1-4):”);
scanf(“%d”,&ch);
switch(ch)
{ case 1: push(); break;case 2: pop();break;case 3: display();break;case 4: exit(0);
default: printf(“\nWrong Choice!!”);}}}
void push(){int val;
if(top==MAX-1){
printf(“\nStack is full!!”);}
else printf(“\nEnter element to push:”);
scanf(“%d”,&val);
top=top+1;
stack[top]=val;}}
void pop(){ if(top==-1){
printf(“\nStack is empty!!”);}
else{ printf(“\nDeleted element is %d”,stack[top]); top=top-1;}}
void display(){int i;
if(top==-1){printf(“\nStack is empty!!”);}
else{printf(“\nStack is…
“);
for(i=top;i>=0;–i)
printf(“%d\n”,stack[i]);}}
Queue using Array
Algorithm enqueue(item)
1. Start 2. If (rear == max – 1)
print ‘queue overflow’
3. Else 3.1 If(front==-1) front=0 rear=rear+1
queue[rear]=item
3.2 else rear = rear+1 queue[rear]=item
3.3 end if 4. end if 5.stop
Algorithm dequeue()
1.Start 2.If(front==-1 or front>rear) 2.1 print “queue underflow” 3.else
print queue[front] is deleted
front++ 4.end if 5.stop
#include #include #define MAX 50
int queue_array[MAX]; int rear = – 1;
int front = – 1; void insert(){ int add_item;
if (rear == MAX – 1) printf(“Queue Overflow \n”); else{ if (front == – 1) front = 0; printf(“Inset the element in queue : “); scanf(“%d”, &add_item); rear = rear + 1; queue_array[rear] = add_item; } }
void delete(){ if (front == – 1 || front > rear){
printf(“Queue Underflow \n”); return ; }
else { printf(“Element deleted from queue is : %d\n”, queue_array[front]); front = front + 1; } } void display(){ int i; if (front == – 1)
printf(“Queue is empty \n”);
else {printf(“Queue is : \n”); for (i = front; i
{ printf(“—–QUEUE USING ARRAY——\n”); printf(“1.Insert element to queue \n”); printf(“2.Delete element from queue \n”); printf(“3.Display all elements of queue \n”); printf(“4.Quit \n”);
printf(“Enter your choice : “); scanf(“%d”, &choice); switch (choice) { case 1: insert(); break; case 2: delete(); break; case 3:display(); } } return 0; }
Priority Queue
Enqueue (value, priority)
1.Start 2. If rear==Max-1 then print “priority queue is full” 3.if rear==-1
front=rear=0
4.pos=front 5.while pos
pos=pos+1
6.for(k=rear+1;k>pos;k–) pq[k]=pq[k-1]
7.pq[pos].value=value 8.pq[pos].priority=priority 9.rear=rear+1 10.stop
Dequeue()
1.Start 2. If front==-1 then print “priority queue is empty” and return 3.print “”deleted value is pq[front].value” 4.If front==rear-1 then front=rear-1 5.Else
front=front+1 6.stop
Circular Queue
Algorithm enqueue
1.start 2.if isFull() then print “Queue is full” 3.else 3.1 if front == -1 then front = 0 3.2 rear = ( rear +1 ) % SIZE 3.3 items[rear] = element 3.4 print “element inserted” 4.stop
Algorithm dequeue()
1.start 2.if isEmpty() then print “ Empty queue” 3.else 3.1 element = items[front] 3.2 if front = rear then front=rear=-1 3.3 else then front = (front + 1) % SIZE 3.4 print “element deleted” 4.stop
#include #define SIZE 5
int items[SIZE];
int front = -1, rear = -1; int isFull() { if ((front == rear + 1) || (front == 0 && rear == SIZE – 1)) return 1; return 0;}
int isEmpty() { if (front == -1) return 1; return 0;}void enQueue() { int element;
printf(“Enter the value”); scanf(“%d”,&element);
if (isFull())printf(“\n Queue is full!! \n”);
else { if (front == -1) front = 0; rear = (rear + 1) % SIZE;
items[rear] = element; printf(“\n Inserted -> %d”, element);}}
int deQueue() {int element;
if (isEmpty()) { printf(“\n Queue is empty !! \n”);
return (-1); } else {element = items[front];
if (front == rear) { front = -1; rear = -1;}
else { front = (front + 1) % SIZE; } printf(“\n Deleted element -> %d \n”, element);
return (element);}} void display() { int i;
if (isEmpty()) printf(” \n Empty Queue\n”);
else { printf(“\n Front -> %d “, front);
printf(“\n Items -> “);
for (i = front; i != rear; i = (i + 1) % SIZE) { printf(“%d “, items[i]); } printf(“%d “, items[i]); printf(“\n Rear -> %d \n”, rear); } }int main() {
int choice=0; printf(“\n*********Circular Queue operations*********\n”); printf(“\n———————————————-\n”); while(choice != 4)
{ printf(“\n\nChose one from the below options…\n”); printf(“\n1.enQueue\n2.deQueue\n3.display\n4.Exit”); printf(“\n Enter your choice \n”); scanf(“%d”,&choice);
switch(choice)
{ case 1:{ enQueue(); break;}
case 2:{
deQueue(); break;}
case 3:{
display(); break;}
case 4:{
printf(“Exiting….”); break;}
default:{ printf(“Please Enter valid choice “);}};} return 0;}
Dequeue Using Array
Enqueue(item)
1.If(rear==MAX-1) 1.1 print queue overflow 2.Else 2.1(front==-1) front=0 2.2 end if 2.3 rear++ 2.4 DEQUE[rear]=item 3.end if
Dequeue_front()
1.If (front=-1 or front>rear) 1.1 Print queue under flow 2.Else
print DEQUE (front) is deleted
front++ 3.end if
Dequeue_rear()
1.If (front=-1 or front>rear) 1.1 Print ‘queue underflow’ 2. else 2.1 Print DEQUE(rear) is deleted 2.2 rear=rear-13. end if
Circular Linked list
Traverse(START)
1 TEMP = START 2 If TEMP=NULL Print “CLL is empty” 3.Else , While Temp–>link!=Start Then , Print temp–>data , Temp–>data–>link , end while , Print temp–>data 4 End if , Insert(START,Key)
1.If temp=null then print node is not created 2.else temp–>data=key , temp–>link=temp , if START=NULL then ,START=TEMP
else TEMP1=START, while(TEMP1–>link!=START) ,TEMP1=TEMP1–>link , end while, TEMP1–>link=TEMP , TEMP–>link=START , end if 3 end if
Delete()
1. If start = null print”deletion not possible” 2.Else if(START–>link=START) , START–>link=null , delete(START), 3. Else ,TEMP=START , START=START–>link , TEMP1=START , while(TEMP1–>link!=Temp) , Temp1=TEMP1–>link , end while , Temp1–>link=START , delete(TEMP)
Stack using LL:
Push(item)
1.If(TOP==NULL) , TOP–>data=item , TOP–>link=NULL 2.Else , TEMP–>data=item , TEMP–>link=TOP , TOP=TEMP
POP()
1IF(TOP==NULL) , print “Stack is empty” ,2.Else ,TEMP=TOP , TOP=TOP–>link , delete(TEMP)
#include #include void push(); void pop();
void display(); struct node
{ int val; struct node *next; };
struct node *head; void main ()
{int choice=0;
printf(“\n*********Stack operations using linked list*********\n”); while(choice != 4)
{ printf(“\n\nChose one from the below options…\n”); printf(“\n1.Push\n2.Pop\n3.Show\n4.Exit”);
printf(“\n Enter your choice \n”);
scanf(“%d”,&choice);
switch(choice)
{ case 1: {push();break} case 2: { pop(); break;} case 3: { display(); break; } case 4: { printf(“Exiting….”); break; } default: { printf(“Please Enter valid choice “); } }; } }
void push () {
int val; struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL) {
printf(“not able to push the element”); }
else { printf(“Enter the value”);scanf(“%d”,&val); if(head==NULL)
{ ptr->val = val; ptr -> next = NULL; head=ptr; }
else { ptr->val = val; ptr->next = head; head=ptr; } printf(“Item pushed”); } } void pop() { int item; struct node *ptr;
if (head == NULL) { printf(“Underflow”); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf(“Item popped”); } } void display() { int i; struct node *ptr; ptr=head;
if(ptr == NULL) {
printf(“Stack is empty\n”);}
else
{
printf(“Printing Stack elements \n”);
while(ptr!=NULL) {
printf(“%d\n”,ptr->val); ptr = ptr->next; } }}
LINEAR SEARCH
1.flag=0 2.for i=0 to n-1 do 3.{ if[Ai]==search_key {flag=1
break}} 4.if{flag==0 then print”element not found” else
element found at ith index} }
#include
int main(){
int i,n,key,pos=-1; printf(“Enter Length of array”); scanf(“%d”,&n);
int a[n];
printf(“\nEnter Values of array “); for(i=0;iscanf(“%d”,&a[i]);
printf(“\n Enter element to be searched “); scanf(“%d”,&key);
for(i=0;iif(a[i]==key){
pos = i+1;
printf(“\nElement found at %d “,pos);
}
if(pos==-1)
printf(“\nElement not found
“);
}
BINARY SEARCH
{ flag=0 while low{ mid=(low+mid)/2
if A[mid]=search_data then {flag=1
break}
else if A[mid]>search_data then high=mid-1
else low=mid+1
if {flag=0 then
print”element not found”
else
element found at index mid}}
code: #include
void bubbleSort(int arr[], int n) { }
void printArray(int arr[], int size) { }
void binarySearch(int a[],int low,int high,int key){
if (high >= low) {
int mid = (low + high) / 2; if (a[mid] == key)
printf(“Element found at %d “,mid+1); else if (a[mid] > key)
binarySearch(a, low, mid – 1, key); else binarySearch(a, mid + 1, high, key);
}else{
printf(“Element not found”); } }
int main(){
int i,j,temp,n,key,pos=-1; printf(“Enter Length of array “); scanf(“%d”,&n);
int a[n];
printf(“\nEnter Values of array “); for(i=0;i
scanf(“%d”,&a[i]); bubbleSort(a,n); printf(“\nSorted Array is \n “); printArray(a,n);
printf(“\n Enter element to be searched “); scanf(“%d”,&key); binarySearch(a,0,n-1,key);
return 0; }
int i, j,temp;
for (i = 0; i
for (j = 0; j arr[j+1]){
temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp;
}
int i;
for (i=0; i
printf(“%d “, arr[i]); printf(“\n”);
QUEUE USING LL
enqueue(item)
1.if front=null front–>data=item front–>link=null rear=front 2.else rear–>link=temp temp–>data=item temp–>link=null rear=temp
dequeue()
1 if(front=null) print queue is empty 2.else if (front–>link=null) temp=front , front=null , rear=null , delete(temp) 3.else , temp=front , front=front–>link , delete(temp)
#include #include struct node {int data;
struct node *next; };
struct node *front; struct node *rear; void insert();
void delete(); void display(); void main ()
{ int choice; while(choice != 4)
{printf(“\nQueue Using LinkedList\n”); printf(“\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n”);
printf(“\nEnter your choice ?”); scanf(“%d”,& choice);
switch(choice) {case 1: insert(); break; case 2: delete(); break; case 3: display(); break; case 4: exit(0); break; default: printf(“\nEnter valid choice??\n”);}}}
void insert()
{ struct node *ptr; int item;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{ printf(“\nOVERFLOW\n”); return; }
else { printf(“\nEnter value?\n”); scanf(“%d”,&item); ptr -> data = item; if(front == NULL)
{ front = ptr; rear = ptr; front -> next = NULL; rear -> next = NULL; }else
{ rear -> next = ptr; rear = ptr; rear->next = NULL; } }
display(); } void delete ()
{ struct node *ptr; if(front == NULL) { printf(“\nUNDERFLOW\n”); return; } else { ptr = front; front = front -> next; free(ptr);} display(); }
void display() { struct node *ptr; ptr = front; if(front == NULL)
{printf(“\nEmpty queue\n”); }
else { printf(“\nData in queue are\n”); while(ptr != NULL) {printf(“\n%d\n”,ptr -> data);
ptr = ptr -> next; }}}
QUICK SORT
algorithm mergesort(start,end) 1 start 2 if start!=end
mid=(start+end)/2 mergesort(start,mid) mergesort(mid+1,end) merge(start,mid,end) 3.end if 4.stop
algorithm merge(start,mid,end) 1.i=start 2 j=mid+1 3 k=start 4 while i1.if a[i]1.tem[k]=a[j] 2.i++ 3.k++ 2.else temp[k]=a[j] j++ k++ 3.end if 5 end while 6while i1.temp[k]=a[i] 2.j++ 3.k++ 7.end while 8.while j9.end while 10.k=start 11.while k12.end while 13.stop
#include
void quicksort(int number[25],int first,int last){ int i, j, pivot, temp;
if(firstpivot=first;
i=first;
j=last;
while(iwhile(number[j]>number[pivot])
j–;
if(itemp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot]; number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1); quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf(“enter the limit?: “); scanf(“%d”,&count);
printf(“Enter %d elements: “, count); for(i=0;iscanf(“%d”,&number[i]); quicksort(number,0,count-1);
printf(“Order of Sorted elements: “); for(i=0;iprintf(” %d”,number[i]);
return 0;
}
MERGE SORT algorithm mergesort(a[],left,right) 1 if left
1.mid=(left+right)/2 2.mergesort(a,left,mid) 3.mergesort(a,mid+1,right) 4.merge(a,left,mid,right)
2.end if
algorithm merge(a[],left,mid,right)
1. n1=(mid-left)+1 2.n2=right-mid 3.for(i=0;i4.for(j=0;j5.set i==j=0,k=low
6 while i1. if[i]
a[k]=L[i] i++ 2. else a[k]=R[j] j++3.end if 4.k++ 7. end while 8.whileii++,k++ end while 9.while j
#include
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
int main()
{
int a[30],n,i;
printf(“Enter no of elements:”); scanf(“%d”,&n);
printf(“Enter array elements:”); for(i=0;i
printf(“%d “,a[i]); return 0;
}
void mergesort(int a[],int i,int j) {
int mid;
if(i
{
mid=(i+j)/2; mergesort(a,i,mid); mergesort(a,mid+1,j); merge(a,i,mid,mid+1,j); }
}
Infix to Postfix
#include #include char stack[100]; int top = -1;
void push(char x){ stack[++top] = x;
}
char pop(){
if(top == -1) return -1;
else
return stack[top–];
}
int priority(char x){
if(x == ‘(‘) return 0;
if(x == ‘+’ || x == ‘-‘) return 1;
if(x == ‘*’ || x == ‘/’) return 2;
return 0; }
int main(){
char exp[100];
char *e, x;
printf(“Enter the expression : “); scanf(“%s”,exp);
printf(“\n”);
e = exp;
while(*e != ‘\0’)
{
if(isalnum(*e)) printf(“%c “,*e);
else if(*e == ‘(‘) push(*e);
else if(*e == ‘)’) {
while((x = pop()) != ‘(‘) printf(“%c “, x);
} else {
while(priority(stack[top]) >= priority(*e)) printf(“%c “,pop());
push(*e); }
e++; }
while(top != -1) {
printf(“%c “,pop()); }return 0;
}