18

1. Given (4,7,3,2,1,7,9,0) find the location of 7 using Linear and Binary

Program Code
01 #include<stdio.h>
02 #include<stdlib.h>
03
04 int A[100], n, key; // Declare an array A with size 100 and variables n and key
05
06 // Function for linear search
07 int Isearch(int a[], int n, int key) {
08 int i = -1;
09 while (i < n) {
10 if (A[++i] == key)
11 return i;
12 }
13 return -1;
14 }
15
16 // Function for binary search
17 int binsearch(int a[], int n, int key) {
18 int first, last, mid, i;
19 first = 0;
20 last = n - 1;
21 while (first <= last) {
22 mid = (first + last) / 2;
23 if (key == A[mid])
24 return mid;
25 else if (key < A[mid])
26 last = mid - 1;
27 else
28 first = mid + 1;
29 }
30 return -1;
31 }
32
33 // Function to accept input
34 void acceptInput() {
35 int i;
36 printf("Enter Number of Elements:");
37 scanf("%d", &n);
38 for (i = 0; i < n; i++) { // Fix the loop condition and use i++ instead of i;
39 printf("Enter Element %d:", i + 1);
40 scanf("%d", &A[i]);

2|Page
41 }
42 printf("Enter an Element to be Searched: ");
43 scanf("%d", &key);
44 }
45
46 // Main function
47 void main() {
48 int ch, flag;
49 while (1) {
50 printf("\n Searching Techniques");
51 printf("\n********");
52 printf("\n 1. Linear Search ");
53 printf("\n 2. Binary Search ");
54 printf("\n 3. Exit");
55 printf("\n Enter your choice: ");
56 scanf("%d", &ch);
57
58 switch (ch) {
59 case 1:
60 acceptInput();
61 flag = Isearch(A, n, key); // Fix the assignment operator and the function call
62 if (flag == -1)
63 printf("\n Search is Unsuccessful.");
64 else
65 printf("\n An Element %d Found at Position: %d", key, flag + 1);
66 break;
67 case 2:
68 printf("\n Enter Elements in Ascending Order for Binary Search\n");
69 acceptInput();
70 flag = binsearch(A, n, key); // Fix the assignment operator and the function call
71 if (flag == -1)
72 printf("%d not found in array (%d,%d);", key, n, key);
73 else
74 printf("An Element %d Found at Position: %d", key, flag + 1);
75 break;
76 case 3:
77 exit(0);
78 }
79 }
80 }

3|Page
Explanation of Program Code

4|Page
Program Output

Explanation of Program Output

Signature of Lab In charge

5|Page
2. Given (5,3,1,6,0,2,4) order the numbers in ascending order using
Bubble Sort Algorithm

Program Code
01 #include<stdio.h>
02 #include<conio.h>
03
04 // Function to perform bubble sort on an array
05 void bubble_sort(int a[], int n) {
06 int pass, temp, j; // Declare variables for pass, temp, and j
07
08 for (pass = 1; pass < n; pass++) { // Outer loop for passes
09 for (j = 0; j < n - pass; j++) { // Inner loop for comparisons within each pass
10 if (a[j] > a[j + 1]) { // Compare adjacent elements
11 // Swap the elements if they are in the wrong order
12 temp = a[j];
13 a[j] = a[j + 1];
14 a[j + 1] = temp;
15 }
16 }
17 }
18 }
19
20 // Main function
21 int main() {
22 int i, j, a[20], n, temp; // Declare variables
23
24 printf("\n Enter the number of elements: ");
25 scanf("%d", &n);
26
27 printf("\n Enter the array elements:\n");
28 for (i = 0; i < n; i++)
29 scanf("%d", &a[i]);
30
31 bubble_sort(a, n); // Call the bubble_sort function to sort the array
32
33 printf("\n The sorted elements are:\n");
34 for (i = 0; i < n; i++)
35 printf("%d ", a[i]);
36
37 return 0; // Indicate successful execution to the operating system
38 }

6|Page
Explanation of Program Code

7|Page
Program Output

Explanation of Program Output

Signature of Lab In charge

8|Page
3. Perform the Insertion and Selection Sort on the input
{75,8,1,16,48,3,7,0} and display the output in descending order.

Program Code
01 #include<stdio.h>
02 #include<stdlib.h>
03
04 int z[100], n;
05
06 // Function to find the index of the maximum element in an array
07 int max(int a[], int k, int n) {
08 int loc, j, max;
09 max = a[k];
10 loc = k;
11 for (j = k + 1; j < n; j++) {
12 if (max < a[j]) {
13 max = a[j];
14 loc = j;
15 }
16 }
17 return loc;
18 }
19
20 // Function to perform insertion sort
21 void insertion_sort(int a[], int n) {
22 int pass, k, temp, j;
23 for (pass = 1; pass < n; pass++) {
24 k = a[pass];
25 for (j = pass - 1; j >= 0 && k < a[j]; j--) {
26 a[j + 1] = a[j];
27 }
28 a[j + 1] = k;
29 }
30 }
31
32 // Function to accept input from the user
33 void acceptinput() {
34 int i;
35 printf("Enter the number of elements: ");
36 scanf("%d", &n);
37 printf("\nEnter the array elements: ");
38 for (i = 0; i < n; i++) {
39 scanf("%d", &z[i]);
40 }
41 }
42
43 // Function to display the sorted array
44 void display() {
45 int i;
46 printf("\nThe Sorted Array is: ");

9|Page
47 for (i = 0; i < n; i++) {
48 printf("%d ", z[i]);
49 }
50 }
51
52 // Main function
53 void main() {
54 int k, temp, loc, ch;
55 while (1) {
56 printf("\nSorting Techniques");
57 printf("\n******");
58 printf("\n1. Insertion Sort");
59 printf("\n2. Selection Sort");
60 printf("\n3. Exit");
61 printf("\nEnter your choice: ");
62 scanf("%d", &ch);
63
64 switch (ch) {
65 case 1:
66 acceptinput();
67 insertion_sort(z, n);
68 display();
69 break;
70 case 2:
71 acceptinput();
72 for (k = 0; k < n; k++) {
73 loc = max(z, k, n);
74 temp = z[k];
75 z[k] = z[loc];
76 z[loc] = temp;
77 }
78 display();
79 break;
80 case 3:
81 exit(0);
82 }
83 }
84 }

10 | P a g e
Explanation of Program Code

11 | P a g e
Program Output

Explanation of Program Output

Signature of Lab In charge

12 | P a g e
4. Write a program to insert the elements {61,16,8,27} into singly
linked list and delete 8,61,27 from the list. Display your list after each
insertion and deletion.

Program Code
001 #include<stdio.h>
002 #include<stdlib.h>
003 #include<conio.h>
004 #include<ctype.h>
005
006 struct node {
007 int INFO;
008 struct node *LINK;
009 };
010
011 typedef struct node NODE;
012 NODE *start = NULL;
013
014 // Function to create a linked list
015 void create() {
016 char ch;
017 int i = 0;
018 NODE *CURRPTR, *NEWNODE;
019
020 // Allocate memory for the first node
021 CURRPTR = (NODE*)malloc(sizeof(NODE));
022 start = CURRPTR;
023
024 while (1) {
025 printf("\n Enter the node %d ", i + 1);
026 scanf("%d", &CURRPTR->INFO);
027
028 printf("\n Do you wish to add one more node (Y/N): ");
029 ch = getch();
030
031 if (toupper(ch) == 'Y') {
032 // Allocate memory for a new node
033 NEWNODE = (NODE*)malloc(sizeof(NODE));
034 CURRPTR->LINK = NEWNODE;
035 } else {
036 CURRPTR->LINK = NULL;
037 break;
038 }
039
040 CURRPTR = NEWNODE;
041 i++;
042 }
043 }
044

13 | P a g e
045 // Function to display the linked list
046 void display() {
047 NODE *CURRPTR = start;
048
049 if (start == NULL) {
050 printf("\n The Linked list is empty");
051 } else {
052 while (CURRPTR != NULL) {
053 printf("%d->", CURRPTR->INFO);
054 CURRPTR = CURRPTR->LINK;
055 }
056 printf("NULL");
057 }
058 }
059
060 // Function to calculate the length of the linked list
061 int length() {
062 int len = 0;
063 NODE *CURRPTR;
064
065 if (start == NULL) {
066 printf("The linked list is empty \n");
067 return len;
068 }
069
070 CURRPTR = start;
071 while (CURRPTR != NULL) {
072 len++;
073 CURRPTR = CURRPTR->LINK;
074 }
075 return len;
076 }
077
078 // Function to insert a node at the beginning
079 void insert_beg(int item) {
080 NODE *NEWNODE;
081 NEWNODE = (NODE*)malloc(sizeof(NODE));
082 NEWNODE->INFO = item;
083 NEWNODE->LINK = start;
084 start = NEWNODE;
085 }
086
087 // Function to insert a node at the end
088 void insert_end(int item) {
089 NODE *CURRPTR, *NEWNODE;
090
091 if (start == NULL) {
092 NEWNODE = (NODE*)malloc(sizeof(NODE));
093 NEWNODE->INFO = item;
094 NEWNODE->LINK = NULL;
095 start = NEWNODE;

14 | P a g e
096 } else {
097 CURRPTR = start;
098 while (CURRPTR->LINK != NULL) {
099 CURRPTR = CURRPTR->LINK;
100 }
101 NEWNODE = (NODE*)malloc(sizeof(NODE));
102 NEWNODE->INFO = item;
103 CURRPTR->LINK = NEWNODE;
104 NEWNODE->LINK = NULL;
105 }
106 }
107
108 // Function to insert a node at a specified position
109 void insert_pos(int item, int POS) {
110 int i;
111 NODE *CURRPTR = start, *NEWNODE;
112
113 if (POS == 1) {
114 insert_beg(item);
115 } else {
116 for (i = 0; i < POS - 2; i++) {
117 CURRPTR = CURRPTR->LINK;
118 }
119
120 NEWNODE = (NODE*)malloc(sizeof(NODE));
121 NEWNODE->INFO = item;
122 NEWNODE->LINK = CURRPTR->LINK;
123 CURRPTR->LINK = NEWNODE;
124 }
125 }
126
127 // Function to delete the first node
128 void delete_beg() {
129 NODE *CURRPTR;
130
131 if (start == NULL) {
132 printf("\n The linked list is empty \n");
133 return;
134 } else {
135 CURRPTR = start;
136 start = start->LINK;
137 free(CURRPTR);
138 }
139 }
140
141 // Function to delete the last node
142 void delete_end() {
143 NODE *CURRPTR, *PREVPTR;
144
145 if (start == NULL)
146 printf("\n The linked list is empty \n");

15 | P a g e
147 else if (start->LINK == NULL) {
148 start = NULL;
149 return;
150 } else {
151 CURRPTR = start;
152 PREVPTR = NULL;
153
154 while (CURRPTR->LINK != NULL) {
155 PREVPTR = CURRPTR;
156 CURRPTR = CURRPTR->LINK;
157 }
158
159 PREVPTR->LINK = NULL;
160 }
161 }
162
163 // Function to delete a node at a specified position
164 void delete_pos(int POS) {
165 int i;
166 NODE *CURRPTR, *PREVPTR;
167
168 if (POS == 1) {
169 delete_beg();
170 } else {
171 CURRPTR = start;
172 PREVPTR = NULL;
173
174 for (i = 1; i < POS; i++) {
175 PREVPTR = CURRPTR;
176 CURRPTR = CURRPTR->LINK;
177 }
178
179 PREVPTR->LINK = CURRPTR->LINK;
180 free(CURRPTR);
181 }
182 }
183
184 // Function to delete a node with a given item
185 void delete_item(int item) {
186 NODE *CURRPTR = start, *PREVPTR = NULL;
187
188 if (start == NULL) {
189 printf("\n The linked list is empty");
190 return;
191 } else if (start->INFO == item) {
192 start = start->LINK;
193 free(CURRPTR);
194 return;
195 }
196
197 while (CURRPTR != NULL && CURRPTR->INFO != item) {

16 | P a g e
198 PREVPTR = CURRPTR;
199 CURRPTR = CURRPTR->LINK;
200 }
201
202 if (CURRPTR == NULL) {
203 printf("\n The item is not found in the linked list \n");
204 } else {
205 PREVPTR->LINK = CURRPTR->LINK;
206 free(CURRPTR);
207 }
208 }
209
210 // Main function
211 void main() {
212 int ch, item, pos;
213
214 while (1) {
215 printf("\n 1. Create a Linked List ");
216 printf("\n 2. Display ");
217 printf("\n 3. Insert First Node ");
218 printf("\n 4. Insert at the End ");
219 printf("\n 5. Insert at the Specified Position ");
220 printf("\n 6. Delete First Node ");
221 printf("\n 7. Delete Last Node ");
222 printf("\n 8. Delete at the Specified Position ");
223 printf("\n 9. Delete a Node When Item is Given ");
224 printf("\n 10. Exit");
225 printf("\n Enter Your Choice: ");
226 scanf("%d", &ch);
227
228 switch (ch) {
229 case 1:
230 start = NULL;
231 create();
232 break;
233 case 2:
234 display();
235 break;
236 case 3:
237 printf("\n Enter the Item to Insert at the Beginning: ");
238 scanf("%d", &item);
239 printf("\n Linked List before Insertion is: \n");
240 display();
241 insert_beg(item);
242 printf("\n Linked List after Insertion is: \n");
243 display();
244 break;
245 case 4:
246 printf("\n Enter the Item to Insert at the End: ");
247 scanf("%d", &item);
248 printf("\n Linked List before Insertion is: \n");

17 | P a g e
249 display();
250 insert_end(item);
251 printf("\n Linked List after Insertion is: \n");
252 display();
253 break;
254 case 5:
255 printf("\n Enter an Item to Insert at a Certain Position: ");
256 scanf("%d", &item);
257 printf("\n Enter a Valid Position: ");
258 scanf("%d", &pos);
259
260 if ((pos == 0) || (pos > length() + 1)) {
261 printf("\n It is an Invalid Position \n");
262 break;
263 } else {
264 printf("\n Linked List before Insertion is: \n");
265 display();
266 insert_pos(item, pos);
267 printf("\n Linked List after Insertion is: \n");
268 display();
269 break;
270 }
271 case 6:
272 printf("\n Linked List before Deletion is: \n");
273 display();
274 delete_beg();
275 printf("\n Linked List after Deletion is: \n");
276 display();
277 break;
278 case 7:
279 printf("\n Linked List before Deletion is: \n");
280 display();
281 delete_end();
282 printf("\n Linked List after Deletion is: \n");
283 display();
284 break;
285 case 8:
286 printf("\n Enter a Valid Position to Delete: \n");
287 scanf("%d", &pos);
288
289 if ((pos == 0) || (pos > length())) {
290 printf("\n It is an Invalid position \n");
291 break;
292 } else {
293 printf("\n Linked List before Deletion is: \n");
294 display();
295 delete_pos(pos);
296 printf("\n Linked List after Deletion is: \n");
297 display();
298 break;
299 }

18 | P a g e
300 case 9:
301 printf("\n Linked List before Deletion is: \n");
302 display();
303 printf("\n Enter an Item to be Deleted: \n");
304 scanf("%d", &item);
305 delete_item(item);
306 printf("\n Linked list after Deletion is: \n");
307 display();
308 break;
309 case 10:
310 exit(0);
311 }
312 }
313 }

19 | P a g e
Explanation of Program Code

20 | P a g e
Program Output

Explanation of Program Output

Signature of Lab In charge

21 | P a g e
5. Write a program to insert the elements {61,16,8,27} into linear
queue and delete three elements from the list. Display your list after
each insertion and deletion.

Program Code
01 #include<stdio.h>
02 #include<stdlib.h>
03
04 #define N 10
05
06 int QUEUE[N], FRONT = 0, REAR = -1, ITEM;
07
08 // Function to insert an element into the queue
09 void Qinsert() {
10 if (REAR == N - 1)
11 printf("\n Queue Overflow");
12 else {
13 scanf("%d", &ITEM);
14 REAR++;
15 QUEUE[REAR] = ITEM;
16 }
17 }
18
19 // Function to delete an element from the queue
20 void Qdelete() {
21 if (REAR < FRONT - 1)
22 printf("\n Queue Underflow");
23 else if (REAR == FRONT) {
24 printf("\n This is the Last Element in the Queue ");
25 printf("\n The Last Element Deleted is: %d", QUEUE[FRONT]);
26 FRONT = 0;
27 REAR = -1;
28 } else {
29 printf("\n Deleted item is %d", QUEUE[FRONT]);
30 FRONT++;
31 }
32 }
33
34 // Function to display the elements in the queue
35 void Qdisplay() {
36 int I;
37
38 if (REAR < FRONT - 1)
39 printf("\n\t No elements in Queue");
40 else {
41 printf("\n Queue: ");
42 for (I = FRONT; I <= REAR; I++)
43 printf("%d\t", QUEUE[I]);
44

22 | P a g e
45 printf("\n Front Element of the Queue is: %d", QUEUE[FRONT]);
46 printf("\n Rear Element of the Queue is: %d", QUEUE[REAR]);
47 }
48 }
49
50 // Main function
51 void main() {
52 int ch;
53
54 while (1) {
55 printf("\n*** Queue Implementation using Array");
56 printf("\n 1. Insert into Queue");
57 printf("\n 2. Delete from Queue ");
58 printf("\n 3. Display Queue");
59 printf("\n 4. Exit");
60 printf("\n Enter your choice: ");
61 scanf("%d", &ch);
62
63 switch (ch) {
64 case 1:
65 Qinsert();
66 Qdisplay();
67 break;
68 case 2:
69 Qdelete();
70 Qdisplay();
71 break;
72 case 3:
73 Qdisplay();
74 break;
75 case 4:
76 exit(0);
77 }
78 }
79 }

23 | P a g e