3.

Implementation of Circular Queue Using C

#include <stdio.h>
# define max 6
int queue[max]; // array declaration
int front=-1;
int rear=-1;
// function to insert an element in a circular queue
void enqueue(int element)
{
if(front==-1 && rear==-1) // condition to check queue is
empty
{
front=0;
rear=0;
queue[rear]=element;
}
else if((rear+1)%max==front) // condition to check queue is
full
{
printf("Queue is overflow..");
}
else
{
rear=(rear+1)%max; // rear is incremented
queue[rear]=element; // assigning a value to the queue at the
rear position.
}
}
// function to delete the element from the queue
int dequeue()
{
if((front==-1) && (rear==-1)) // condition to check queue is
empty
{
printf("\nQueue is underflow..");
}
else if(front==rear)
{
printf("\nThe dequeued element is %d", queue[front]);
front=-1;
rear=-1;
}
else
{
printf("\nThe dequeued element is %d", queue[front]);
front=(front+1)%max;
}
}
// function to display the elements of a queue
void display()
{
int i=front;
if(front==-1 && rear==-1)
{
printf("\n Queue is empty..");
}
else
{
printf("\nElements in a Queue are :");
while(i<=rear)
{
printf("%d,", queue[i]);
i=(i+1)%max;
}
}
}
int main()
{
int choice=1,x; // variables declaration
while(choice<4 && choice!=0) // while loop
{
printf("\n Press 1: Insert an element");
printf("\nPress 2: Delete an element");
printf("\nPress 3: Display the element");
printf("\nEnter your choice");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the element which is to be inserted");
scanf("%d", &x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
display();
}}
return 0;
}
1)B. Program to demonstrate queues
using arrays
#include<stdio.h>
//#include<conio.h>
#include<stdlib.h>
#define SIZE 10
void enQueue(int);
void deQueue();
void display();
int queue[SIZE], front = -1, rear = -1;
int main()
{
int value, choice;
//clrscr();
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Insertion\n2. Deletion\n3.
Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be
insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!!
Try again!!!");
}
}
} void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is
not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
} void deQueue(){
//if(front == rear)
if (front == - 1 || front > rear)
printf("\nQueue is Empty!!! Deletion is
not possible!!!");
else{
printf("\nDeleted : %d", queue[front]);
front++;
// if(front == rear)
// front = rear = -1;
}
} void display(){
//if(rear == -1)
if(rear == -1||front> rear)
printf("\nQueue is Empty now !!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<rear;i++)
printf(“%d\t”,queue[i]);
}
}
//program to demonstrate postfix
evaluation
#include<stdio.h>
#include <ctype.h>
int stack[20];
int top = -1;
void push(int x)
{
stack[++top] = x;
} int pop()
{
return stack[top--];
} int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48;
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)
{
case '+':
{
n3 = n1 + n2;
break;
}
case '-':
{
n3 = n2 - n1;
break;
}
case '*':
{
n3 = n1 * n2;
break;
}
case '/':
{
n3 = n2 / n1;
break;
}
}
push(n3);
}
e++;
}
printf("\nThe result of expression %s =
%d\n\n",exp,pop());
return 0;
}
//Implementation of Infix to Postfix
Conversion
//save the program with anyname.c
#include<stdio.h>
#include<ctype.h>
char stack[100];
int top = -1;
void push(char x)
{
stack[++top] = x;
}c
har 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;
}
1. //Source code for stack operations, using
linked list:
2. include <stdio.h>
3. include <conio.h>
4. include <stdlib.h>
5. struct stack
6. {
7. int data;
8. struct stack *next;
9. };
10. void push();
11. void pop();
12. void display();
13. typedef struct stack node;
14. node *start=NULL;
15. node *top = NULL;
16. node* getnode()
17. {
18. node *temp;
19. temp=(node *) malloc( sizeof(node)) ;
20. printf("\n Enter data ");
21. scanf("%d", &temp -> data);
22. temp -> next = NULL;
23. return temp;
24. }
25. void push(node *newnode)
26. {
27. node *temp;
28. if( newnode == NULL )
29. {
30. printf("\n Stack Overflow..");
31. return;
32. }
33.
34. if(start == NULL)
35. {
36. start = newnode;
37. top = newnode;
38. }
39. else
40. {
41. temp = start;
42. while( temp -> next != NULL)
43. temp = temp -> next;
44. temp -> next = newnode;
45. top = newnode;
46. }
47. printf("\n\n\t Data pushed into stack");
48. }
49. void pop()
50. {
51. node *temp;
52. if(top == NULL)
53. {
54. printf("\n\n\t Stack
55. underflow"); return;
56. }
57. temp = start;
58. if( start -> next == NULL)
59. {
60. printf("\n\n\t Popped element is %d ",
top -> data);
61. start = NULL;
62. free(top);
63. top = NULL;
64. }
65. else
66. {
67. while(temp -> next != top)
68. {
69. temp = temp -> next;
70. }
71. temp -> next = NULL;
72. printf("\n\n\t Popped element is %d ",
top -> data);
73. free(top);
74. top = temp;
75. }
76. }
77. void display()
78. {
79. node *temp;
80. if(top == NULL)
81. {
82. printf("\n\n\t\t Stack is empty ");
83. }
84. else
85. {
86. temp = start;
87. printf("\n\n\n\t\t Elements in the stack:
\n");
88. printf("%5d ", temp -> data);
89. while(temp != top)
90. {
91. temp = temp -> next;
92. printf("%5d ", temp -> data);
93. }
94. }
95. }
96.
97. char menu()
98. {
99. char ch;
100. clrscr();
101. printf("\n \tStack operations using
pointers.. ");
102. printf("\n -----------**********-----------
--\n");
103. printf("\n 1. Push ");
104. printf("\n 2. Pop ");
105. printf("\n 3. Display");
106. printf("\n 4. Quit ");
107. printf("\n Enter your choice:
108. "); ch = getche();
109. return ch;
110. }
111. void main()
112. {
113. char ch;
114. node *newnode;
115. do
116. {
117. ch = menu();
118. switch(ch)
119. {
120. case '1' :
121. newnode = getnode();
122. push(newnode); break;
123. case '2' :
124. pop();
125. break;
126. case '3' :
127. display();
128. break;
129. case '4':
130. return;
131. }
132. getch();
133. } while( ch != '4' );
134.
1. //A Complete Source Code for the
Implementation of Double Linked List:
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <conio.h>
5. struct dlinklist
6. {
7. struct dlinklist *left;
8. int data;
9. struct dlinklist *right;};
11. typedef struct dlinklist node;
12. node *start = NULL;
13. node* getnode() {
15. node * newnode;
16. newnode = (node *)
malloc(sizeof(node));
17. printf("\n Enter data: ");
18. scanf("%d", &newnode -> data);
19. newnode -> left = NULL;
20. newnode -> right = NULL;
21. return newnode; }
23. int countnode(node *start){
25. if(start == NULL)
26. return 0;
27. else
28. return 1 + countnode(start -> right); }
30. int menu() {
32. int ch;
33. clrscr();
34. printf("\n 1.Create");
35. printf("\n------------------------------");
36. printf("\n 2. Insert a node at beginning
");
37. printf("\n 3. Insert a node at end");
38. printf("\n 4. Insert a node at middle");
39. printf("\n------------------------------");
40. printf("\n 5. Delete a node from
beginning");
41. printf("\n 6. Delete a node from Last");
42. printf("\n 7. Delete a node from
Middle");
43. printf("\n------------------------------");
44. printf("\n 8. Traverse the list from Left to
Right ");
45. printf("\n 9. Traverse the list from Right
to Left ");
46. printf("\n------------------------------");
47. printf("\n 10.Count the Number of
nodes in the list");
48. printf("\n 11.Exit ");
49. printf("\n\n Enter your choice: ");
50. scanf("%d", &ch);
51. return ch;}
53. void createlist(int n){
55. int i;
56. node *newnode;
57. node *temp;
58. for(i = 0; i < n; i++) {
60. newnode = getnode();
61. if(start == NULL)
62. start = newnode;
63. else{
65. temp = start;
66. while(temp -> right)
67. temp = temp -> right;
68. temp -> right = newnode;
69. newnode -> left = temp;}}}
74. void traverse_left_to_right() {
76. node *temp;
77. temp = start;
78. printf("\n The contents of List:
79. "); if(start == NULL )
80. printf("\n Empty List");
81. else{
83. while(temp != NULL) {
85. printf("\t %d ", temp -> data);
86. temp = temp -> right;}}}
90. void traverse_right_to_left() {
92. node *temp;
93. temp = start;
94. printf("\n The contents of List:
95. "); if(start == NULL)
96. printf("\n Empty List");
97. else {
99. while(temp -> right != NULL)
100. temp = temp -> right;}
102. while(temp != NULL) {
104. printf("\t%d", temp ->
105. data); temp = temp -> left;}}
108. void dll_insert_beg(){
110. node *newnode;
111. newnode = getnode();
112. if(start == NULL)
113. start = newnode;
114. else {
116. newnode -> right = start;
117. start -> left = newnode;
118. start = newnode;} }
121. void dll_insert_end(){
123. node *newnode, *temp;
124. newnode = getnode();
125. if(start == NULL)
126. else {}}
130. start = newnode;
131. temp = start;
132. while(temp -> right != NULL)
133. temp = temp -> right;
134. temp -> right = newnode;
135. newnode -> left = temp;
137. void dll_insert_mid(){
139. node *newnode,*temp;
140. int pos, nodectr, ctr = 1;
141. newnode = getnode();
142. printf("\n Enter the position: ");
143. scanf("%d", &pos);
144. nodectr = countnode(start);
145. if(pos - nodectr >= 2){
147. printf("\n Position is out of range..");
148. return; }
150. if(pos > 1 && pos < nodectr){
152. temp = start;
153. while(ctr < pos - 1){
155. temp = temp -> right;
156. ctr++;}
158. newnode -> left = temp; newnode
159. -> right = temp -> right; temp ->
160. right -> left = newnode; temp ->
161. right = newnode;}
163. else
164. printf("position %d of list is not a
middle position ", pos);}
166. void dll_delete_beg(){
168. node *temp;
169. if(start == NULL){
171. printf("\n Empty
172. list"); getch();
173. return ;}
175. else{
177. temp = start;
178. start = start -> right;
179. start -> left = NULL;
180. free(temp);}}
183. void dll_delete_last()
184. {
185. node *temp;
186. if(start == NULL)
187. {
188. printf("\n Empty
189. list"); getch();
190. return ;
191. }
192. else
193. {
194. temp = start;
195. while(temp -> right != NULL)
197. temp = temp -> right;
198. temp -> left -> right = NULL;
199. free(temp);
200. temp = NULL;
201. }
202. }
203. void dll_delete_mid()
204. {
205. int i = 0, pos, nodectr;
206. node *temp;
207. if(start == NULL)
208. 209. printf("\n Empty List");
210. getch();
211. return;
212. }
213. else
214. {
215. printf("\n Enter the position of the
node to delete: ");
216. scanf("%d", &pos);
217. nodectr = countnode(start);
218. if(pos > nodectr)
219. {
220. printf("\nthis node does not
221. exist"); getch();
222. return;
223. }
224. if(pos > 1 && pos < nodectr)
225. {
226. temp =
227. start; i = 1;
228. while(i < pos)
229. {temp = temp -> right; i++; }
233. temp -> right -> left = temp -> left;
234. temp -> left -> right = temp -> right;
235. free(temp);
236. printf("\n node deleted..");
237. }
238. else
239. {
240. printf("\n It is not a middle position..");
241. getch();
242. } } }
245. void main(void)
246. {
247. int ch, n;
248. clrscr();
249. while(1)
250. {
251. ch = menu();
252. switch( ch){
254. case 1 :
255. printf("\n Enter Number of nodes to
create: ");
256. scanf("%d", &n);
257. createlist(n);
259. printf("\n List
260. created.."); break
262. dll_insert_beg();
263. break;
265. dll_insert_end();
266. break;
268. dll_insert_mid();
269. break;
271. dll_delete_beg();
272. break;
273. case 6 : dll_delete_last();
274. break;
275. case 7 :
276. dll_delete_mid();
277. break;
278. case 8 :
279. traverse_left_to_right();
280. break;
281. case 9 :
282. traverse_right_to_left();
283. break;
284. case 10 :
285. printf("\n Number of nodes: %d",
countnode(start));
286. break;
287. case 11:
288. exit(0); }
290. getch(); }}
1. //10. a) Implementation of Binary Search
Using Recursive Method
2. #include <stdio.h>
3. void binary_search(int [], int, int, int);
4. int main()
5. {
6. int key, size, i;
7. int list[25];
8. printf("Enter size of a list: ");
9. scanf("%d", &size);
10. printf("Enter elements\n");
11. for(i = 0; i < size; i++)
12. {
13. scanf("%d",&list[i]);
14. }
15. printf("\n");
16. printf("Enter key to search\n");
17. scanf("%d", &key);
18. binary_search(list, 0, size, key);
19. }
20. void binary_search(int list[], int lo, int hi,
int key)
21. {
22. int mid;
23. if (lo > hi)
24. {
25. printf("Key not found\n");
26. return;
27. }
28. mid = (lo + hi) / 2;
29. if (list[mid] == key)
30. {
31. printf("Key found\n");
32. }
33. else if (list[mid] > key)
34. {
35. binary_search(list, lo, mid - 1, key);
36. }
37. else if (list[mid] < key)
38. {
39. binary_search(list, mid + 1, hi, key);
40. }
41. }
8. Implementation of Circular linked List
using C.
#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
int e;
Position next;
};
void Insert(int x, List l, Position p)
{
Position TmpCell;
TmpCell = (struct Node*)
malloc(sizeof(struct Node));
if(TmpCell == NULL)
printf("Memory out of space\n");
else
{
TmpCell->e = x;
TmpCell->next = p->next;
p->next = TmpCell;
}
}
int isLast(Position p, List l)
{
return (p->next == l);
}
Position FindPrevious(int x, List l)
{
Position p = l;
while(p->next != l && p->next->e != x)
p = p->next;
return p;
}
Position Find(int x, List l)
{
Position p = l->next;
while(p != l && p->e != x)
p = p->next;
return p;
}
void Delete(int x, List l)
{
Position p, TmpCell;
p = FindPrevious(x, l);
if(!isLast(p, l))
{
TmpCell = p->next;
p->next = TmpCell->next;
free(TmpCell);
}
else
printf("Element does not exist!!!\n");
}
void Display(List l)
{
printf("The list element are :: ");
Position p = l->next;
while(p != l)
{
printf("%d ->", p->e);
p = p->next;
}
}
void main()
{
int x, pos, ch, i;
List l, l1;
l = (struct Node *) malloc(sizeof(struct
Node));
l->next = l;
List p = l;
printf("CIRCULAR LINKED LIST
IMPLEMENTATION OF LIST ADT\n\n");
do{
printf("\n\n1. INSERT\t 2. DELETE\t 3.
FIND\t 4. PRINT\t 5. QUIT\n\nEnter the
choice :: ");
scanf("%d", &ch);
switch(ch){
case 1:
p = l;
printf("Enter the element to be inserted ::
");
scanf("%d",&x);
printf("Enter the position of the element ::
");
scanf("%d",&pos);
for(i = 1; i < pos; i++){
p = p->next;}
Insert(x,l,p);
break;
case 2:
p = l;
printf("Enter the element to be deleted :: ");
scanf("%d",&x);
Delete(x,p);
break;
case 3:
p = l;
printf("Enter the element to be searched ::
");
scanf("%d",&x);
p = Find(x,p);
if(p == l)
printf("Element does not exist!!!\n");
else
printf("Element exist!!!\n");
break;
case 4:
Display(l);
break;
}
}while(ch<5);
return 0;}
// Quick Sort
#include<stdio.h>
void quicksort(int[ ],int,int);
void main( ){
int low, high, pivot, t, n, i, j, a[10];
//clrscr( );
printf("\nHow many elements you want to
sort ? ");
scanf("%d",&n);
printf("\Enter elements for an array:");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
low=0;
high=n-1;
quicksort(a,low,high);
printf("\n After Sorting the elements are:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
//getch( );
}
void quicksort(int a[ ],int low,int high)
{
int pivot,t,i,j;
if(low<high)
{
pivot=a[low];
i=low+1;
j=high;
while(1){
while(pivot>a[i]&&i<=high)
i++;
while(pivot<a[j]&&j>=low)
j--;
if(i<j){
t=a[i];
a[i]=a[j];
a[j]=t;}
else
break;}
a[low]=a[j];
a[j]=pivot;
quicksort(a,low,j-1);
quicksort(a,j+1,high);
}
}
Implementation of linear search
#include <stdio.h>
int linearSearch(int a[], int n, int val) {
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
}
int main() {
int a[] = { 20, 35, 40, 16, 23, 22, 40}; //
Array
int val = 30; Key Element
int n = sizeof(a) / sizeof(a[0]); // size of
array
int res = linearSearch(a, n, val); // Store
result
printf (“The elements of the array are –
“);
for (int i = 0; i < n; i++)
printf(“%d “, a[i]);
printf(“\nElement to be searched is –
%d”, val);
 if (res == -1)
printf(“\nElement is not present in the
array”);
else
printf(“\nElement is present at %d
position of array”, res);
return 0;
}