· 4 years ago · Feb 16, 2021, 03:26 PM
1DATA STRUCTURES LABORATORY
2[As per Choice Based Credit System (CBCS) scheme]
3(Effective from the academic year 2019 -2020)
4SEMESTER - III
5Laboratory Code 18CPL38 IA Marks 40
6Number of Lecture Hours/Week 01I + 02P Exam Marks 60
7Total Number of Lecture Hours 40 Exam Hours 03
8CREDITS – 02
9Course objectives:
10This laboratory course enable students to get practical experience in design, develop, implement,
11analyze and evaluation/testing of
12•Asymptotic performance of algorithms.
13•Linear data structures and their applications such as Stacks, Queues and Lists
14•Non-Linear Data Structures and their Applications such as Trees and Graphs
15•Sorting and Searching Algorithms
16Descriptions (if any)
17Implement all the experiments in C Language under Linux / Windows environment.
18Ex. No. Laboratory Experiments Description
19(RBT Levels: L3, L4, L5, L6) Page
20No.
21 Introduction to Data Structures
221 Design, Develop and Implement a menu driven Program in C for the following Array operations
23a. Creating an Array of N Integer Elements
24b. Display of Array Elements with Suitable Headings
25c. Inserting an Element (ELEM) at a given valid Position (POS)
26d. Deleting an Element at a given valid Position(POS)
27e. Exit.
28Support the program with functions for each of the above operations. 3
292 Design, Develop and Implement a Program in C for the following operations on Strings
30a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
31b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR with REP if PAT exists in STR. Report suitable messages in case PAT does not exist in STR
32Support the program with functions for each of the above operations. Don't use Built-in functions. 6
333 Design, Develop and Implement a menu driven Program in C for the following operations on STACK of Integers (Array Implementation of Stack with maximum size MAX)
34a. Push an Element on to Stack
35b. Pop an Element from Stack
36c. Demonstrate how Stack can be used to check Palindrome
37d. Demonstrate Overflow and Underflow situations on Stack
38e. Display the status of Stack
39f. Exit
40Support the program with appropriate functions for each of the above operations 7
414 Design, Develop and Implement a Program in C for converting an Infix Expression to Postfix Expression. Program should support for both parenthesized and free parenthesized expressions with the operators: +, -, *, /, %( Remainder), ^ (Power) and alphanumeric operands. 9
425 Design, Develop and Implement a Program in C for the following Stack Applications a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^ b. Solving Tower of Hanoi problem with n disks 10
436 Design, Develop and Implement a menu driven Program in C for the following operations on Circular QUEUE of Characters (Array Implementation of Queue with maximum size MAX)
44a. Insert an Element on to Circular QUEUE
45b. Delete an Element from Circular QUEUE
46c. Demonstrate Overflow and Underflow situations on Circular QUEUE
47d. Display the status of Circular QUEUE
48e. Exit
49Support the program with appropriate functions for each of the above operations 12
507 Design, Develop and Implement a menu driven Program in C for the following operations on Singly Linked List (SLL) of Student Data with the fields: USN, Name, Branch, Sem, PhNo
51a. Create a SLL of N Students Data by using front insertion.
52b. Display the status of SLL and count the number of nodes in it
53c. Perform Insertion and Deletion at End of SLL
54d. Perform Insertion and Deletion at Front of SLL
55e. Demonstrate how this SLL can be used as STACK and QUEUE
56f. Exit 14
578 Design, Develop and Implement a menu driven Program in C for the following operations on Doubly Linked List (DLL) of Employee Data with the fields: SSN, Name, Dept, Designation, Sal, PhNo
58a. Create a DLL of N Employees Data by using end insertion.
59b. Display the status of DLL and count the number of nodes in it
60c. Perform Insertion and Deletion at End of DLL
61d. Perform Insertion and Deletion at Front of DLL
62e. Demonstrate how this DLL can be used as Double Ended Queue
63f. Exit 17
649 Design, Develop and Implement a Program in C for the following operations on Singly Circular
65Linked List (SCLL) with header nodes
66a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
67b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store the result in
68POLYSUM(x,y,z)
69Support the program with appropriate functions for each of the above operations 20
7010 Design, Develop and Implement a menu driven Program in C for the following operations on Binary Search Tree (BST) of Integers
71a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
72b. Traverse the BST in Inorder, Preorder and Post Order
73c. Search the BST for a given element (KEY) and report the appropriate message
74d. Exit 24
7511 Design, Develop and Implement a Program in C for the following operations on Graph(G) of Cities
76a. Create a Graph of N cities using Adjacency Matrix.
77b. Print all the nodes reachable from a given starting node in a digraph using BFS method
78c. Check whether a given graph is connected or not using DFS method. 28
7912 Given a File of N employee records with a set K of Keys(4-digit) which uniquely determine the records in file F. Assume that file F is maintained in memory by a Hash Table(HT) of mmemory locations with L as the set of memory addresses (2-digit) of locations in HT. Let the keys in K and addresses in L are Integers. Design and develop a Program in C that uses Hash function H: K ®L as H(K)=K mod m (remainder method), and implement hashing technique to map a given key K to the address space L. Resolve the collision (if any) using linear probing. 30
80 Viva Questions 38
81Course outcomes: On the completion of this laboratory course, the students will be able to:
82• Analyze and Compare various linear and non-linear data structures
83• Code, debug and demonstrate the working nature of different types of data
84• structures and their applications
85• Implement, analyze and evaluate the searching and sorting algorithms
86• Choose the appropriate data structure for solving real world problems
87Graduate Attributes (as per NBA)
881. Engineering Knowledge
892. Problem Analysis
903. Design/Development of Solutions
914. 4. Modern Tool Usage
92Conduction of Practical Examination:
931. All laboratory experiments (TWELVE nos ) are to be included for practical examination.
942. Students are allowed to pick one experiment from the lot.
953. Strictly follow the instructions as printed on the cover page of answer script
964. Marks distribution: Procedure + Execution + Viva-Voce: 15+70+15 = 100 Marks d
975. Change of experiment is allowed only once and marks allotted to the procedure part to be made zero.
98
99Program1:
100Design, Develop and Implement a menu driven Program in C for the following Array operations
101a. Creating an Array of N Integer Elements
102b. Display of Array Elements with Suitable Headings
103c. Inserting an Element (ELEM) at a given valid Position (POS)
104d. Deleting an Element at a given valid Position(POS)
105e. Exit.
106Support the program with functions for each of the above operations.
107
108Theory:
109Array is a collection of elements of the same type. In this program we need to use functions for various operations
110Create(): Create an array for the size given by the user
111Display(): Display the elements of the array
112Insert(): Insert an element at the position given by the user
113Delete(): Delete an element from the position specified by the user
114Exit(): Terminate
115
116
117
118Algorithm:
119Step 1: Start.
120Step 2: Read N value.
121Step 3: Read Array of N integer elements
122Step 4: Print array of N integer elements.
123Step 5: Insert an element at given valid position in an array.
124Step 6: Delete an element at given valid position from an array.
125Step 7: Stop.
126
127#include<stdio.h>
128#include<stdlib.h>
129int a[20]; // Array declaration
130int n,val,i,pos;
131void create();
132
133int display();
134void insert();
135int delete();
136void main()
137{
138int choice;
139printf("\n\n--------MENU-----------\n");
140printf("1.CREATE\n");
141printf("2.display\n");
142printf("3.INSERT\n");
143printf("4.DELETE\n");
144printf("5.EXIT\n");
145printf("-----------------------");
146while(1)
147{
148printf("\nENTER YOUR CHOICE:\t");
149scanf("%d",&choice);
150switch(choice)
151{
152case 1: create();
153break;
154case 2: display();
155break;
156case 3: insert();
157
158break;
159case 4: delete();
160break;
161case 5: exit(0);
162default: printf("\nInvalid choice:\n");
163break;
164}
165}
166}
167void create()
168{
169printf("\nEnter the size of the array elements:\t");
170scanf("%d",&n);
171printf("\nEnter the elements for the array:\n");
172for(i=0;i<n;i++)
173{
174scanf("%d",&a[i]);
175}
176}
177int display()
178{
179if(n==0)
180
181{
182printf("\t Array is empty; no elements to display\n");
183return 0;
184}
185printf("\nThe array elements are:\n");
186for(i=0;i<n;i++)
187{
188printf("%d\t",a[i]);
189}
190}
191void insert()
192{
193printf("\nEnter the position for the new element:\t");
194scanf("%d",&pos);
195if(pos<=n)
196{
197printf("\nEnter the element to be inserted :\t");
198scanf("%d",&val);
199for(i=n-1;i>=pos;i--)
200{
201a[i+1]=a[i];
202}
203a[pos]=val;
204n=n+1;
205
206display();
207}
208else
209{
210printf(" Invalid Position");
211}
212}
213
214int delete()
215{
216if(n==0)
217{
218printf("\t Array is empty; no elements to delete \n");
219return 0;
220}
221printf("\nEnter the position of the element to be deleted:\t");
222scanf("%d",&pos);
223if(pos<=n-1)
224{
225val=a[pos];
226printf("\n Deleted element is =%d",val);
227for(i=pos;i<n-1;i++)
228
229{
230a[i]=a[i+1];
231}
232n=n-1;
233display();
234}
235else
236{
237printf(" Invalid Position");
238}
239}
240output
241
242--------MENU-----------
2431.CREATE
2442.DISPLAY
2453.INSERT
2464.DELETE
2475.EXIT
248-----------------------
249ENTER YOUR CHOICE: 1
250Enter the size of the array elements: 3
251Enter the elements for the array:
25210 25 30
253ENTER YOUR CHOICE: 2
254The array elements are:
25510 25 30
256ENTER YOUR CHOICE: 3
257Enter the position for the new element: 1
258Enter the element to be inserted : 20
259ENTER YOUR CHOICE: 2
260The array elements are:
26110 20 25 30
262ENTER YOUR CHOICE: 4
263Enter the position of the element to be deleted: 3
264The deleted element is =30
265enter your choice: 5
266
267Program2:
268Design, Develop and Implement a Program in C for the following operations on Strings
269a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
270b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR
271withREP if PAT exists in STR. Report suitable messages in case PAT does not exist in
272STR
273Support the program with functions for each of the above operations. Don't use Built-infunctions.
274Theory:
275Strings are actually one-dimensional array of characters terminated by a null character '\0'. Thus a null-terminated string contains the characters that comprise the string followed by a null
276C language supports a wide range of built-in functions that manipulate null-terminated strings as follows:
277strcpy(s1, s2): Copies string s2 into string s1.
278strcat(s1, s2): Concatenates string s2 onto the end of string s1.
279strlen(s1): Returns the length of string s1.
280strcmp(s1, s2): Returns 0 if s1 and s2 are the same; less than 0 if s1<s2; greater than 0 if s1>s2.
281strchr(s1, ch): Returns a pointer to the first occurrence of character ch in string s1.
282strstr(s1, s2): Returns a pointer to the first occurrence of string s2 in string s1
283
284
285Algorithm:
286Step 1: Start.
287Step 2: Read main string STR, pattern string PAT and replace string REP.
288Step 3: Search / find the pattern string PAT in the main string STR.
289Step 4: if PAT is found then replace all occurrences of PAT in main string STR with REP string.
290Step 5: if PAT is not found give a suitable error message.
291Step 6: Stop.
292
293#include<stdio.h>
294
295void main()
296{
297char STR[100],PAT[100],REP[100],ans[100];
298int i,j,c,m,k,flag=0;
299printf("\nEnter the MAIN string: \n");
300gets(STR);
301printf("\nEnter a PATTERN string: \n");
302gets(PAT);
303printf("\nEnter a REPLACE string: \n");
304
305gets(REP);
306i = m = c = j = 0;
307while ( STR[c] != '\0')
308{
309// Checking for Match
310if ( STR[m] == PAT[i] )
311{
312i++;
313m++;
314flag=1;
315if ( PAT[i] == '\0')
316{
317//copy replace string in ans string
318
319for(k=0; REP[k] != '\0';k++,j++)
320ans[j] = REP[k];
321i=0;
322
323c=m;
324}
325}
326else //mismatch
327{
328ans[j] = STR[c];
329j++;
330c++;
331m = c;
332
333i=0;
334}
335}
336if(flag==0)
337{
338
339printf("Pattern doesn't found!!!");
340
341}
342else
343{
344ans[j] = '\0';
345printf("\nThe RESULTANT string is:%s\n" ,ans);
346}
347}
348Output
349Enter the MAIN string:
350good morning
351Enter a PATTERN string:
352morning
353Enter a REPLACE string:
354evening
355The RESULTANT string is: good evening
356
357Program 3:
358Design, Develop and Implement a menu driven Program in C for the following operations on
359STACK of Integers (Array Implementation of Stack with maximum size MAX)
360a. Push an Element on to Stack
361b. Pop an Element from Stack
362c. Demonstrate how Stack can be used to check Palindrome
363d. Demonstrate Overflow and Underflow situations on Stack
364e. Display the status of Stack
365f. Exit
366Support the program with appropriate functions for each of the above operations
367
368Theory:
369Stack is a collection of elements of the similar types. It is also called as last in, first out.
370The element inserted first is the last one to be deleted. It is used for various applications like infix to postfix expression, postfix evaluation and for maintaining stack frames for function calling
371• push() - pushing (storing) an element on the stack.
372• pop() - removing (accessing) an element from the stack.
373To use a stack efficiently we need to check status of stack as well. For the same purpose, the following functionality is added to stacks;
374• peek() − get the top data element of the stack, without removing it.
375• isFull() − check if stack is full.
376• isEmpty() − check if stack is empty.
377Algorithm:
378Step 1: Start.
379Step 2: Initialize stack size MAX and top of stack -1.
380Step 3: Push integer element on to stack and display the contents of the stack.
381if stack is full give a message as ‘Stack is Overflow’.
382Step 3: Pop element from stack along with display the stack contents.
383if stack is empty give a message as ‘Stack is Underflow’.
384Step 4: Check whether the stack contents are Palindrome or not.
385Step 5: Stop
386
387#include <stdio.h>
388#include <stdlib.h>
389int stack[6],rev[6];
390int top=-1,k=0;
391int size;
392void push();
393void pop();
394void display();
395int pali();
396void main()
397{
398int choice,f;
399printf("Enter the size for stack\n");
400scanf("%d",&size);
401printf("1.Push\n2.Pop\n3.Display\n4.Check for Palindrome\n5.Exit\n");
402while(1)
403{
404printf("Enter the choice\n");
405scanf("%d",&choice);
406switch(choice)
407{
408case 1:push();
409break;
410case 2:pop();
411break;
412case 3:display();
413break;
414case 4:f=pali();
415if(f==1)
416printf("It's Palindrome\n");
417else
418printf("It's not a Palindrome\n");
419break;
420case 5:exit(0);
421default:printf("Wrong choice...\n");
422}
423}
424}
425void push()
426{
427int num;
428if(top==(size-1))
429{
430printf("Stack Overflow\n");
431}
432else
433{
434printf("Enter the number to be pushed\n");
435scanf("%d",&num);
436top++;
437stack[top]=num;
438}
439}
440void pop()
441{
442int num;
443if(top==-1)
444{
445printf("Stack Underflow\n");
446}
447else
448{
449num=stack[top];
450printf("Popped element is %d\n",num);
451top--;
452}
453}
454void display()
455{
456int i;
457if(top==-1)
458{
459printf("Stack Underflow\n");
460}
461else
462{
463printf("Stack Contents....\n");
464for(i=top;i>=0;i--)
465{
466printf("%d\n",stack[i]);
467rev[k++]=stack[i];
468}
469}
470}
471int pali()
472{
473int i,flag=1;
474for(i=top;i>=0;i--)
475{
476if(stack[i]!=rev[--k])
477{
478
479flag=0;
480}
481}
482return flag;
483}
484
485Output
486--------STACK OPERATIONS-----------
4871.Push
4882.Pop
4893.Check for Palindrome
4904.Display
4915.Exit
492-----------------------
493Enter your choice: 1
494Enter the element to be inserted: 1
495Enter your choice: 1
496Enter the element to be inserted: 2
497Enter your choice: 1
498Enter the element to be inserted: 1
499Enter your choice: 1
500Enter the element to be inserted: 5
501Enter your choice: 2
502The poped element: 5
503Enter your choice: 4
504The stack elements are:
5051
5062
5071
508Enter your choice: 3
509It’s a Palindrome
510Enter your choice: 5
511
512Program 4:
513Design, Develop and Implement a Program in C for converting an Infix Expression to Postfix
514Expression. Program should support for both parenthesized and free parenthesized expressions with
515the operators: +, -, *, /, %(Remainder), ^(Power) and alphanumeric operands.
516
517Theory:
518Infix: Operators are written in-between their operands. Ex: X + Y
519Prefix: Operators are written before their operands. Ex: +X Y
520postfix: Operators are written after their operands. Ex: XY+
521Algorithm:
522Step 1: Read the infix expression as a string.
523Step 2: Scan the expression character by character till the end. Repeat the following operations
524 1. If it is an operand add it to the postfix expression.
525 2. If it is a left parentheses push it onto the stack.
526 3. If it is a right parentheses pop out elements from the stack and assign it to the
527postfix string. Pop out the left parentheses but don’t assign to postfix.
528Step 3: If it is an operator compare its precedence with that of the element at the top of
529stack.
5301.If it is greater push it onto the stack.
5312.Else pop and assign elements in the stack to the postfix expression until
532you find one such element.
533Step 4: If you have reached the end of the expression, pop out any leftover elements in the stack till it becomes empty.
534Step 5: Append a null terminator at the end display the result
535
536#define size 50 /* size of stack */
537#include <ctype.h>
538#include <stdio.h>
539char s[size];
540int top = -1; /* global declarations */
541push(char elem) /* function for push operation */
542{
543s[++top] = elem;
544}
545char pop() /* function for pop operation */
546{
547return (s[top--]);
548}
549int pr(char elem) /* function for precedence */
550{
551switch (elem)
552{
553
554case '#':
555return 0;
556case '(':
557return 1 ;
558case '+':
559case '-':
560return 2;
561case '*':
562case '/':
563case '%':
564return 3;
565case '^':
566return 4;
567}
568 }
569void main() /* main program */
570{
571char infx[50], pofx[50], ch, elem;
572int i = 0, k = 0;
573printf("\n\nEnter the infix expression ");
574scanf("%s", infx);
575push('#');
576while ((ch = infx[i++]) != '\0')
577{
578if (ch == '(')
579push(ch);
580else if (isalnum(ch))
581pofx[k++] = ch;
582else if (ch == ')')
583{
584while (s[top] != '(')
585{
586pofx[k++] = pop();
587}
588elem = pop(); /* remove ( */
589}
590else /* operator */
591{
592while (pr(s[top]) >= pr(ch))
593{
594pofx[k++] = pop();
595}
596push(ch);
597}
598 }
599while (s[top] != '#') /* pop from stack till empty */
600{
601pofx[k++] = pop();
602}
603
604pofx[k] = '\0'; /* make pofx as valid string */
605printf("\n\n Given infix expression: %s\n postfix expression is: %s\n", infx, pofx);
606}
607Output
608Enter the infix expression (a+b)*c/d^5%1
609Given Infix Expn: (a+b)*c/d^5%1
610Postfix Expn: ab+c*d5^/1%
611
612
613Program 5:
614Design, Develop and Implement a Program in C for the following Stack Applications
615a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^
616b. Solving Tower of Hanoi problem with n disks
617
618Algorithm
619Step 1: Read the infix expression as a string.
620Step 2: Scan the expression character by character till the end. Repeat the following operations
621 a. If it is an operand push it onto the stack.
622 b. If it is an operator
6231.Pop out two operands from stack
6242.Apply the operator onto the popped operands.
6253.Store the result back on to the stack
626Step 3: On reaching the end of expression pop out the contents of the stack and display as the result.
627b. TOWER OF HANOI
628The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
629The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
630• Only one disk can be moved at a time.
631• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
632• No disk may be placed on top of a smaller disk.
633With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n - 1, where n is the number of disks
634Algorithm:
635Step 1:Move a tower of height-1 to an intermediate pole, using the final pole.
636Step 2:Move the remaining disk to the final pole.
637Step 3:Move the tower of height-1 from the intermediate pole to the final pole using the original pole.
638
639Program 5a:
640#include<stdio.h>
641#include<ctype.h>
642float stack[20];
643
644int top=-1;
645float eval_postfix(char[]); // function to evalute an given expression
646void push(float); // function to push elements to stack
647float pop(); // function to pop the elements from the stack
648main()
649{
650char postfix[20];
651float result;
652printf("enter postfix expr\n");
653scanf("%s", postfix);
654result=eval_postfix(postfix);
655printf("The result = %f\n",result);
656}
657float eval_postfix(char postfix[])
658{
659int i=0,k;
660char ch,op1,op2;
661float res;
662while(postfix[i]!='\0') //check till the end of string
663{
664ch=postfix[i];
665if(isdigit(ch)) //check for digitschecks whether a character is numeric (0-9) or not.
666{
667k=ch-'0';
668push(k);
669}
670else
671{
672op2=pop();
673op1=pop();
674switch(ch)
675{
676case '+':push(op1+op2);
677break;
678case '-':push(op1-op2);
679break;
680case '*':push(op1*op2);
681break;
682case '/':push(op1/op2);
683break;
684case '^':push(pow(op1,op2));
685break;
686default :printf("illegal\n");
687exit(0);
688}
689}
690i++;
691}
692res=pop();
693
694if(top!=-1)
695{
696printf("not a valid expression");
697exit(1);
698}
699return(res);
700}
701void push(float num)
702{
703top++;
704stack[top]=num;
705return;
706}
707float pop()
708{
709float num;
710if(top == -1)
711{
712printf("not a valid");
713exit(0);
714}
715else
716{
717num=stack[top];
718top--;
719return(num);
720}
721}
722OUTPUT
723
724Insert a postfix notation :: 22^32*+
725Result :: 10
726
727
728Program 5b:
729
730#include <stdio.h>
731void towers(int, char, char, char);
732int main()
733{
734int num;
735printf("Enter the number of disks : ");
736scanf("%d", &num);
737printf("The sequence of moves involved in the Tower of Hanoi are :\n");
738towers(num, 'A', 'C', 'B');
739return 0;
740}
741void towers(int num, char frompeg, char topeg, char auxpeg)
742{
743if (num == 1)
744{
745printf("\n Move disk 1 from peg %c to peg %c", frompeg, topeg);
746return;
747}
748
749towers(num - 1, frompeg, auxpeg, topeg);
750printf("\n Move disk %d from peg %c to peg %c", num, frompeg, topeg); towers(num - 1, auxpeg, topeg, frompeg); }
751
752OUTPUT
753Enter the number of disks : 3
754The sequence of moves involved in the Tower of Hanoi are :
755Move disk 1 from peg A to peg C
756Move disk 2 from peg A to peg B
757Move disk 1 from peg C to peg B
758Move disk 3 from peg A to peg C
759Move disk 1 from peg B to peg A
760Move disk 2 from peg B to peg C
761Move disk 1 from peg A to peg C
762Program6:
763Design, Develop and Implement a menu driven Program in C for the following operations onCircular QUEUE of Characters (Array Implementation of Queue with maximum size MAX)
764a. Insert an Element on to Circular QUEUE
765b. Delete an Element from Circular QUEUE
766c. Demonstrate Overflow and Underflow situations on Circular QUEUE
767d. Display the status of Circular QUEUE
768e. Exit
769Support the program with appropriate functions for each of the above operations
770
771Theory:
772Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node is connected back to the first node to make a circle.It is also called FIFO structure. Elements are added at the rear end and the elements are deleted at front end of the queue. The queue is considered as a circular queue when the positions 0 and MAX-1 are adjacent.
773ALGORITHM:
774Step 1: Start.
775Step 2: Initialize queue size to MAX.
776Step 3: Insert the elements into circular queue. If queue is full give a message as ‘queue is overflow”
777Step 4: Delete an element from the circular queue. If queue is empty give a message as ‘queue is underflow’.
778Step 5: Display the contents of the queue.
779Step 6: Stop.
780
781#include <stdio.h>
782#include <conio.h>
783#include <string.h>
784#define SIZE 5
785char CQ[SIZE];
786int front=-1, rear=-1;
787int ch;
788void CQ_Insert();
789void CQ_Delet();
790void CQ_Display();
791void main()
792{
793printf("1.Insert\n2.Delete\n3.Display\n4.Exit\n");
794while(1)
795{
796printf("Enter your choice\n");
797scanf("%d",&ch);
798switch(ch)
799{
800case 1: CQ_Insert();
801break;
802case 2:CQ_Delet();
803break;
804case 3:CQ_Display();
805break;
806case 4: exit(0);
807}
808}
809}
810void CQ_Insert()
811{
812char ele;
813if(front==(rear+1)%SIZE)
814{
815printf("Circular Queue Full\n");
816return;
817}
818if(front==-1)
819front++;
820printf("Enter the element to be inserted\n");
821scanf("\n%c",&ele);
822rear = (rear+1)%SIZE;
823CQ[rear] =ele;
824}
825void CQ_Delet()
826{
827char item;
828if(front == -1)
829{
830printf("Circular Queue Empty\n");
831return;
832}
833else if(front == rear)
834{
835item=CQ[front];
836printf("Deleted element is: %c\n",item);
837front=-1;
838rear=-1;
839}
840else
841{
842item =CQ[front];
843printf("Deleted element is: %c\n",item);
844front = (front+1)%SIZE;
845}
846}
847void CQ_Display()
848{
849int i;
850if(front==-1)
851printf("Circular Queue is Empty\n");
852else
853{
854printf("Elements of the circular queue are..\n");
855for(i=front;i!=rear;i=(i+1)%SIZE)
856{
857printf("%c\t",CQ[i]);
858}
859printf("%c\n",CQ[i]);
860}
861}
862Output
863Circular Queue operations
8641.insert
8652.delete
8663.display
8674.exit
868Enter your choice:1
869Enter element to be insert: a
870Enter your choice:1
871Enter element to be insert: b
872Enter your choice:1
873Enter element to be insert: c
874Enter your choice:3
875a b c
876Enter your choice:2
877Deleted element is: a
878Enter your choice:3
879b c
880Enter your choice:4
881
882
883
884Program 7:
885Design, Develop and Implement a menu driven Program in C for the following operations onSingly Linked List (SLL) of Student Data with the fields: USN, Name, Branch, Sem, PhNo
886a. Create a SLL of N Students Data by using front insertion.
887b. Display the status of SLL and count the number of nodes in it
888c. Perform Insertion and Deletion at End of SLL
889d. Perform Insertion and Deletion at Front of SLL
890e. Demonstrate how this SLL can be used as STACK and QUEUE
891f. Exit
892A linked-list is a sequence of data structures which are connected together via links.
893Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list the second most used data structure after array. Following are important terms to understand the concepts of Linked List.
894 Link − Each Link of a linked list can store a data called an element.
895 Next − Each Link of a linked list contain a link to next link called Next.
896 LinkedList − A LinkedList contains the connection link to the first Link called First.
897Basic Operations
898Following are the basic operations supported by a list.
899 Insertion − add an element at the beginning of the list.
900 Deletion − delete an element at the beginning of the list.
901 Display − displaying complete list.
902 Search − search an element using given key.
903 Delete − delete an element using given key.
904
905#include<stdio.h>
906int MAX=4, count;
907struct student
908{
909char usn[10];
910char name[30];
911char branch[5];
912int sem;
913char phno[10];
914struct student *next; //Self referential pointer.
915};
916typedef struct student NODE;
917int countnodes(NODE *head)
918{
919NODE *p;
920count=0;
921p=head;
922while(p!=NULL)
923{
924p=p->next;
925count++;
926}
927return count;
928}
929NODE* getnode(NODE *head)
930{
931NODE *newnode;
932newnode=(NODE*)malloc(sizeof(NODE)); //Create first NODE
933printf("\nEnter USN, Name, Branch, Sem, Ph.No\n");
934flushall();
935gets(newnode->usn);
936flushall();
937gets(newnode->name);
938flushall();
939gets(newnode->branch);
940scanf("%d",&(newnode->sem));
941flushall();
942gets(newnode->phno);
943newnode->next=NULL; //Set next to NULL...
944head=newnode;
945return head;
946}
947NODE* display(NODE *head)
948{
949NODE *p;
950if(head == NULL)
951printf("\nNo student data\n");
952else
953{
954p=head;
955printf("\n----STUDENT DATA----\n");
956printf("\nUSN\tNAME\t\tBRANCH\tSEM\tPh.NO.");
957while(p!=NULL)
958{
959printf("\n%s\t%s\t\t%s\t%d\t%s", p->usn, p->name, p->branch, p->sem, p->phno);
960p = p->next; //Go to next node...
961}
962printf("\nThe no. of nodes in list is: %d",countnodes(head));
963}
964return head;
965}
966NODE* create(NODE *head)
967{
968NODE *newnode;
969if(head==NULL)
970{
971newnode=getnode(head);
972head=newnode;
973}
974else
975{
976newnode=getnode(head);
977newnode->next=head;
978head=newnode;
979}
980return head;
981}
982NODE* insert_front(NODE *head)
983{
984if(countnodes(head)==MAX)
985printf("\nList is Full / Overflow!!");
986else
987head=create(head); //create()insert nodes at front.
988return head;
989}
990NODE* insert_rear(NODE *head)
991{
992NODE *p, *newnode;
993p=head;
994if(countnodes(head) == MAX)
995printf("\nList is Full(QUEUE)!!");
996else
997{
998if(head == NULL)
999{
1000newnode=getnode(head);
1001head=newnode; //set first node to be head
1002}
1003else
1004{
1005newnode=getnode(head);
1006while(p->next!=NULL)
1007{
1008p=p->next;
1009}
1010p->next=newnode;
1011}
1012}
1013return head;
1014}
1015NODE* insert(NODE *head)
1016{
1017int ch;
1018do
1019{
1020printf("\n1.Insert at Front(First)\t2.Insert at End(Rear/Last)\t3.Exit");
1021printf("\nEnter your choice: ");
1022scanf("%d", &ch);
1023switch(ch)
1024{
1025case 1: head=insert_front(head); break;
1026case 2: head=insert_rear(head); break;
1027case 3: break;
1028}
1029head=display(head);
1030}while(ch!=3);
1031return head;
1032}
1033NODE* delete_front(NODE *head)
1034{
1035NODE *p;
1036if(head==NULL)
1037printf("\nList is Empty/Underflow (STACK/QUEUE)");
1038else
1039{
1040p=head;
1041head=head->next; //Set 2nd NODE as head
1042free(p);
1043printf("\nFront(first)node is deleted");
1044}
1045return head;
1046}
1047NODE* delete_rear(NODE *head)
1048{
1049NODE *p, *q;
1050p=head;
1051while(p->next!=NULL)
1052{
1053p=p->next; //Go upto -1 NODE which you want to delete
1054}
1055q=p->next;
1056free(q);//Delete last NODE...
1057p->next=NULL;
1058printf("\nLast(end) entry is deleted");
1059return head;
1060}
1061NODE* del(NODE *head)
1062{
1063int ch;
1064do{
1065printf("\n1.Delete from Front(First)\t2. Delete from End(Rear/Last))\t3.Exit");
1066printf("\nEnter your choice: ");
1067scanf("%d",&ch);
1068switch(ch)
1069{
1070case 1: head=delete_front(head);
1071break;
1072case 2: head=delete_rear(head);
1073break;
1074case 3: break;
1075}
1076head=display(head);
1077}while(ch!=3);
1078return head;
1079}
1080NODE* stack(NODE *head)
1081{
1082int ch;
1083do
1084{
1085printf("\nSSL used as Stack...");
1086printf("\n 1.Insert at Front(PUSH) \t 2.Delete from Front(POP))\t3.Exit");
1087printf("\nEnter your choice: ");
1088scanf("%d", &ch);
1089switch(ch)
1090{
1091case 1: head=insert_front(head); break;
1092case 2: head=delete_front(head); break;
1093case 3: break;
1094}
1095head=display(head);
1096}while(ch!=3);
1097return head;
1098}
1099NODE* queue(NODE *head)
1100{
1101int ch;
1102do
1103{
1104printf("\nSSL used as Queue...");
1105printf("\n 1.Insert at Rear(INSERT) \t 2.Delete from Front(DELETE))\t3.Exit");
1106printf("\nEnter your choice: ");
1107scanf("%d", &ch);
1108switch(ch)
1109{
1110case 1: head=insert_rear(head); break;
1111case 2: head=delete_front(head); break;
1112case 3: break;
1113}
1114head=display(head);
1115}while(ch!=3);
1116return head;
1117}
1118void main()
1119{
1120int ch, i, n;
1121NODE *head;
1122head=NULL;
1123clrscr();
1124printf("\n*----------Studednt Database-----------*");
1125do
1126{
1127printf("\n 1.Create\t 2.Display\t 3.Insert\t 4.Delete\t 5.Stack\t 6.Queue\t 7.Exit");
1128printf("\nEnter your choice: ");
1129scanf("%d", &ch);
1130switch(ch)
1131{
1132case 1: printf("\nHow many student data you want to create: ");
1133scanf("%d", &n);
1134for(i=0;i<n;i++)
1135head=create(head);//Call to Create NODE...
1136break;
1137case 2: head=display(head); //Call to Display...
1138break;
1139case 3: head=insert(head); //Call to Insert...
1140break;
1141case 4: head=del(head); //Call to delete
1142break;
1143case 5: head=stack(head);
1144break;
1145case 6: head=queue(head);
1146break;
1147case 7: exit(); //Exit...
1148}
1149}while(ch!=7);
1150}
1151
1152OUTPUT:
11531. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
1154Enter your choice: 1
1155How many student data you want to create: 2
1156Enter USN, Name, Branch, Sem, Ph.No
11571ox18cs001 kumar cs 3 9900099000
1158Enter USN, Name, Branch, Sem, Ph.No
11591ox18is002 ravi is 3 9900099111
1160
11611. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
1162Enter your choice: 2
1163
1164----STUDENT DATA----
1165USN NAME BRANCH SEM Ph.NO.
11661ox18is002 ravi is 3 9900099111
11671ox18cs001 kumar cs 3 9900099000
1168The no. of nodes in list is: 2
11691. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
1170Enter your choice: 3
1171
11721.Insert at Front(First) 2.Insert at End(Rear/Last) 3.Exit
1173Enter your choice: 1
1174
1175Enter USN, Name, Branch, Sem, Ph.No
11761ox18cs003 suresh cs 3 99000992222
1177----STUDENT DATA----
1178USN NAME BRANCH SEM Ph.NO.
11791ox18cs003 suresh cs 3 99000992222
11801ox18is002 ravi is 3 9900099111
11811ox18cs001 kumar cs 3 9900099000
1182The no. of nodes in list is: 3
1183
11841.Insert at Front(First) 2.Insert at End(Rear/Last) 3.Exit
1185Enter your choice: 2
1186
1187Enter USN, Name, Branch, Sem, Ph.No
11881ox18is004 naresh is 3 99000993333
1189----STUDENT DATA----
1190USN NAME BRANCH SEM Ph.NO.
11911ox18cs003 suresh cs 3 99000992222
11921ox18is002 ravi is 3 9900099111
11931ox18cs001 kumar cs 3 9900099000
11941ox18is004 naresh is 3 99000993333
1195The no. of nodes in list is: 4
1196
11971.Insert at Front(First) 2.Insert at End(Rear/Last) 3.Exit
1198Enter your choice: 3
11991. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
1200Enter your choice: 4
12011. Delete from Front (First) 2. Delete from End (Rear/Last) 3.Exit
1202Enter your choice: 1
1203Front (first) node is deleted
1204----STUDENT DATA----
1205USN NAME BRANCH SEM Ph.NO.
12061ox18is002 ravi is 3 9900099111
12071ox18cs001 kumar cs 3 9900099000
12081ox18is004 naresh is 3 99000993333
1209The no. of nodes in list is: 3
1210
12111. Delete from Front (First) 2. Delete from End (Rear/Last) 3.Exit
1212Enter your choice: 2
1213
1214Last (end) node is deleted
1215----STUDENT DATA----
1216USN NAME BRANCH SEM Ph.NO.
12171ox18is002 ravi is 3 9900099111
12181ox18cs001 kumar cs 3 9900099000
1219The no. of nodes in list is: 2
12201. Delete from Front (First) 2. Delete from End (Rear/Last) 3.Exit
1221Enter your choice: 3
12221. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
1223Enter your choice: 5
1224SSL used as Stack...
12251.Insert at Front(PUSH) 2.Delete from Front(POP)) 3.Exit
1226Enter your choice: 1
1227Enter USN, Name, Branch, Sem, Ph.No
12281ox18is010 vikky is 3 9900011111
1229----STUDENT DATA----
1230USN NAME BRANCH SEM Ph.NO.
12311ox18is010 vikky is 3 9900011111
12321ox18is002 ravi is 3 9900099111
12331ox18cs001 kumar cs 3 9900099000
12341. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
1235Enter your choice: 7
1236Program 8:
1237Design, Develop and Implement a menu driven Program in C for the following operations onDoubly Linked List (DLL) of Employee Data with the fields: SSN, Name, Dept, Designation,Sal, PhNo
1238a. Create a DLL of N Employees Data by using end insertion.
1239b. Display the status of DLL and count the number of nodes in it
1240c. Perform Insertion and Deletion at End of DLL
1241d. Perform Insertion and Deletion at Front of DLL
1242e. Demonstrate how this DLL can be used as Double Ended Queue
1243f. Exit
1244Doubly Linked List is a variation of Linked list in which navigation is possible in both ways either forward and backward easily as compared to Single Linked List. Following are important terms to understand the concepts of doubly Linked List
1245 Link − Each Link of a linked list can store a data called an element.
1246 Next − Each Link of a linked list contain a link to next link called Next.
1247 Prev − Each Link of a linked list contain a link to previous link called Prev.
1248 LinkedList − A LinkedList contains the connection link to the first Link called First and to the last link called Last.
1249
1250#include<stdio.h>
1251#include<conio.h>
1252int MAX=4, count;
1253struct emp
1254{
1255int ssn;
1256char name[20];
1257char dept[10];
1258char desig[15];
1259int sal;
1260char phno[10];
1261struct emp *left;
1262struct emp *right;
1263};
1264typedef struct emp NODE;
1265int countnodes(NODE *head)
1266{
1267NODE *p;
1268count=0;
1269p=head;
1270while(p!=NULL)
1271{
1272p=p->right;
1273count++;
1274}
1275return count;
1276}
1277NODE* getnode(NODE *head)
1278{
1279NODE *newnode;
1280newnode=(NODE*)malloc(sizeof(NODE));
1281newnode->right=newnode->left=NULL;
1282printf("\nEnter SSN, Name, Dept, Designation, Sal, Ph.No\n");
1283scanf("%d",&newnode->ssn);
1284flushall();
1285gets(newnode->name);
1286flushall();
1287gets(newnode->dept);
1288flushall();
1289gets(newnode->desig);
1290scanf("%d",&newnode->sal);
1291flushall();
1292 gets(newnode->phno);
1293head=newnode;
1294return head;
1295}
1296NODE* display(NODE *head)
1297{
1298NODE *p;
1299if(head==NULL)
1300printf("\nNo Employee data\n");
1301else
1302{
1303p=head;
1304printf("\n----EMPLOYEE DATA----\n");
1305printf("\nSSN\tNAME\tDEPT\tDESINGATION\tSAL\t\tPh.NO.");
1306while(p!=NULL)
1307{
1308printf("\n%d\t%s\t%s\t%s\t\t%d\t\t%s", p->ssn, p->name, p->dept, p->desig,
1309p->sal, p->phno);
1310p = p->right; //Go to next node...
1311}
1312printf("\nThe no. of nodes in list is: %d",countnodes(head));
1313}
1314return head;
1315}
1316NODE* create(NODE *head)// creating & inserting at end.
1317{
1318NODE *p, *newnode;
1319p=head;
1320if(head==NULL)
1321{
1322newnode=getnode(head);
1323head=newnode;
1324}
1325else
1326{
1327newnode=getnode(head);
1328while(p->right!=NULL)
1329{
1330p=p->right;
1331}
1332p->right=newnode;
1333newnode->left=p;
1334}
1335return head;
1336}
1337NODE* insert_end(NODE *head)
1338{
1339if(countnodes(head)==MAX)
1340printf("\nList is Full!!");
1341else
1342head=create(head);
1343return head;
1344}
1345NODE* insert_front(NODE *head)
1346{
1347NODE *p, *newnode;
1348if(countnodes(head)==MAX)
1349printf("\nList is Full!!");
1350else
1351{
1352if(head==NULL)
1353{
1354newnode=getnode(head);
1355head=newnode; //set first node to be head
1356}
1357else
1358{
1359newnode=getnode(head);
1360newnode->right=head;
1361head->left=newnode;
1362head=newnode;
1363}
1364}
1365return head;
1366}
1367newnode=getnode(head);
1368newnode->right=head;
1369head->left=newnode;
1370head=newnode;
1371NODE* insert(NODE *head)
1372{
1373int ch;
1374do
1375{
1376printf("\n 1.Insert at Front(First) \t 2.Insert at End(Rear/Last)\t3.Exit");
1377printf("\nEnter your choice: ");
1378scanf("%d", &ch);
1379switch(ch)
1380{
1381case 1: head=insert_front(head); break;
1382case 2: head=insert_end(head); break;
1383case 3: break;
1384}
1385head=display(head);
1386}while(ch!=3);
1387return head;
1388}
1389NODE* delete_front(NODE *head)
1390{
1391NODE *p;
1392if(head==NULL)
1393printf("\nList is Empty (QUEUE)");
1394else
1395{
1396p=head;
1397head=head->right;
1398head->right->left=NULL;
1399free(p);
1400printf("\nFront(first)node is deleted");
1401}
1402return head;
1403}
1404NODE* delete_end(NODE *head)
1405{
1406NODE *p, *q;
1407p=head;
1408while(p->right!=NULL)
1409{
1410p=p->right; //Go upto -1 node which you want to delete
1411}
1412q=p->left;
1413q->right=NULL;
1414p->left=NULL;
1415free(p);//Delete last node...
1416printf("\nLast(end) entry is deleted");
1417return head;
1418}
1419NODE *del(NODE *head)
1420{
1421int ch;
1422do {
1423printf("\n1.Delete from Front(First)\t2. Delete from End(Rear/Last))\t3.Exit");
1424printf("\nEnter your choice: ");
1425scanf("%d", &ch);
1426switch(ch)
1427{
1428case 1: head=delete_front(head);
1429break;
1430case 2: head=delete_end(head);
1431break;
1432case 3: break;
1433}
1434head=display(head);
1435}while(ch!=3);
1436return head;
1437}
1438NODE* queue(NODE *head)
1439{
1440int ch, ch1, ch2;
1441do
1442{
1443printf("\nDLL used as Double Ended Queue");
1444printf("\n1.QUEUE- Insert at Rear & Delete from Front");
1445printf("\n2.QUEUE- Insert at Front & Delete from Rear");
1446printf("\n3.Exit");
1447printf("\nEnter your choice: ");
1448scanf("%d", &ch);
1449switch(ch)
1450{
1451case 1: do{
1452printf("\n1.Insert at Rear\t2.Delete from From Front\t3.Exit");
1453printf("\nEnter your choice: ");
1454scanf("%d", &ch1);
1455switch(ch1)
1456{
1457case 1: head=insert_end(head); break;
1458case 2: head=delete_front(head); break;
1459case 3: break;
1460}
1461}while(ch1!=3);
1462break;
1463case 2: do{
1464printf("\n1.Insert at Front\t2.Delete from Rear\t3.Exit");
1465printf("\nEnter your choice: ");
1466scanf("%d", &ch2);
1467switch(ch2)
1468{
1469case 1: head=insert_front(head); break;
1470case 2: head=delete_end(head); break;
1471case 3: break;
1472}
1473}while(ch2!=3);
1474break;
1475case 3: break;
1476}
1477}while(ch!=3);
1478head=display(head);
1479return head;
1480}
1481void main()
1482{
1483int ch, i, n;
1484NODE *head;
1485head=NULL;
1486clrscr();
1487printf("\n----------Employee Database-----------");
1488do
1489{
1490printf("\n1.Create\t2.Display\t3.Insert\t4.Delete\t5.Queue\t6.Exit");
1491printf("\nEnter your choice: ");
1492scanf("%d", &ch);
1493switch(ch)
1494{
1495case 1: printf("\nHow many employees data you want to create: ");
1496scanf("%d", &n);
1497for(i=0;i<n;i++)
1498head=create(head);//Call to Create node...
1499break;
1500case 2: head=display(head); //Call to Display...
1501break;
1502case 3: head=insert(head); //Call to Insert...
1503break;
1504case 4: head=del(head); //Call to delete
1505break;
1506case 5: head=queue(head);
1507break;
1508case 6: exit(0); //Exit...
1509break;
1510}
1511}while(ch!=6);
1512}
1513OUTPUT:
1514----------Employee Database-----------
15151. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit Enter your choice: 1
1516
1517How many employees data you want to create: 2
1518 Enter SSN, Name, Dept, Designation, Sal, Ph.No
15191 harish ISE Tech Assistant 8000 900099000
1520Enter SSN, Name, Dept, Designation, Sal, Ph.No
15212 manu ISE assistant 9000 9870676456
1522
1523
15241. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit Enter your choice: 2
1525
1526----EMPLOYEE DATA---
1527SSN NAME DEPT DESINGATION SAL Ph.NO
1528 1 Harish ISE Tech Assistant 8000 900099000
1529 2 manu ISE assistant 9000 9870676456
1530
1531
1532
1533The no. of nodes in list is: 2
1534
15351. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit Enter your choice: 3
1536
15371. Insert at Front (First) 2.Insert at End (Rear/Last) 3.Exit Enter your choice: 1
1538
1539Enter SSN, Name, Dept, Designation, Sal, Ph.No
15403 George Library Librarian 6000 900099333
1541----EMPLOYEE DATA----
1542
1543SSN NAME DEPT DESINGATION SAL Ph.NO.
15443 George Library Librarian 6000 900099333
15451 Harish ISE Tech Assistant 8000 900099000
15462 manu ISE assistant 9000 9870676456
1547
1548
1549The no. of nodes in list is: 3
1550
15511. Insert at Front (First) 2.Insert at End (Rear/Last) 3.Exit
1552Enter your choice: 3
1553
15541. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit Enter your choice: 5
1555
1556 DLL used as Double Ended Queue
1557 1.QUEUE- Insert at Rear & Delete from Front
1558 2.QUEUE- Insert at Front & Delete from Rear
1559 3.Exit Enter your choice: 3
1560
15611. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit Enter your choice: 7
1562
1563Program 9:
1564Design, Develop and Implement a Program in C for the following operations on Singly Circular
1565Linked List (SCLL) with header nodes
1566a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
1567b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store the result in
1568POLYSUM(x,y,z)
1569Support the program with appropriate functions for each of the above operations.
1570
1571Circular Linked List is a variation of Linked list in which first element points to last element and last element points to first element. Both Singly Linked List and Doubly Linked List can be made into as circular linked list.
1572Adding two polynomials are represented using linked lists
1573Representation of a Polynomial: A polynomial is an expression that contains more than two terms. A term is made up of coefficient and exponent.
1574An example of polynomial is
1575P(x) = 4x3+6x2+7x+9
1576A polynomial thus may be represented using arrays or linked lists. Array representation assumes that the exponents of the given expression are arranged from 0 to the highest value (degree), which is represented by the subscript of the array beginning with 0. The coefficients of the respective exponent are placed at an appropriate index in the array. The array representation for the above polynomial expression is given below:
1577
1578A polynomial may also be represented using a linked list. A structure may be defined such that it contains two parts- one is the coefficient and second is the corresponding exponent. The structure definition may be given as shown below:
1579struct polynomial
1580{
1581 int coefficient;
1582 int exponent;
1583 struct polynomial *next;
1584};
1585Thus the above polynomial may be represented using linked list as shown below:
1586
1587Addition of two Polynomials:
1588For adding two polynomials using arrays is straightforward method, since both the arrays may be added up element wise beginning from 0 to n-1, resulting in addition of two polynomials. Addition of two polynomials using linked list requires comparing the exponents, and wherever the exponents are found to be same, the coefficients are added up. For terms with different exponents, the complete term is simply added to the result thereby making it a part of addition result. The complete program to add two polynomials is given in subsequent section.
1589
1590#include<stdio.h>
1591#include<alloc.h>
1592#include<math.h>
1593struct node
1594{
1595int cf, px, py, pz;
1596int flag;
1597struct node *link;
1598};
1599typedef struct node NODE;
1600NODE* getnode()
1601{
1602NODE *x;
1603x=(NODE*)malloc(sizeof(NODE));
1604if(x==NULL)
1605{
1606printf("Insufficient memory\n");
1607exit(0);
1608}
1609return x;
1610}
1611void display(NODE *head)
1612{
1613NODE *temp;
1614if(head->link==head)
1615{
1616printf("Polynomial does not exist\n");
1617return;
1618}
1619temp=head->link;
1620printf("\n");
1621while(temp!=head)
1622{
1623printf("%d x^%d y^%d z^%d",temp->cf,temp->px,temp->py,temp-
1624>pz);
1625if(temp->link != head)
1626printf(" + ");
1627temp=temp->link;
1628}
1629printf("\n");
1630}
1631NODE* insert_rear(int cf,int x,int y,int z,NODE *head)
1632{
1633NODE *temp,*cur;
1634temp=getnode();
1635temp->cf=cf;
1636temp->px=x;
1637temp->py=y;
1638temp->pz=z;
1639cur=head->link;
1640while(cur->link!=head)
1641{
1642cur=cur->link;
1643}
1644cur->link=temp;
1645temp->link=head;
1646return head;
1647}
1648NODE* read_poly(NODE *head)
1649{
1650int px, py, pz, cf, ch;
1651printf("\nEnter coeff: ");
1652scanf("%d",&cf);
1653printf("\nEnter x, y, z powers(0-indiacate NO term): ");
1654scanf("%d%d%d", &px, &py, &pz);
1655head=insert_rear(cf,px,py,pz,head);
1656printf("\nIf you wish to continue press 1 otherwise 0: ");
1657scanf("%d", &ch);
1658while(ch != 0)
1659{
1660printf("\nEnter coeff: ");
1661scanf("%d",&cf);
1662printf("\nEnter x, y, z powers(0-indiacate NO term): ");
1663scanf("%d%d%d", &px, &py, &pz);
1664head=insert_rear(cf,px,py,pz,head);
1665printf("\nIf you wish to continue press 1 otherwise 0: ");
1666scanf("%d", &ch);
1667}
1668return head;
1669}
1670NODE* add_poly(NODE *h1,NODE *h2,NODE *h3)
1671{
1672NODE *p1,*p2;
1673int x1,x2,y1,y2,z1,z2,cf1,cf2,cf;
1674p1=h1->link;
1675while(p1!=h1)
1676{
1677x1=p1->px;
1678y1=p1->py;
1679z1=p1->pz;
1680cf1=p1->cf;
1681p2=h2->link;
1682while(p2!=h2)
1683{
1684x2=p2->px;
1685y2=p2->py;
1686z2=p2->pz;
1687cf2=p2->cf;
1688if(x1==x2 && y1==y2 && z1==z2)break;
1689p2=p2->link;
1690}
1691if(p2!=h2)
1692{
1693cf=cf1+cf2;
1694p2->flag=1;
1695if(cf!=0)
1696h3=insert_rear(cf,x1,y1,z1,h3);
1697}
1698else
1699h3=insert_rear(cf1,x1,y1,z1,h3);
1700p1=p1->link;
1701}
1702p2=h2->link;
1703while(p2!=h2)
1704{
1705if(p2->flag==0)
1706h3=insert_rear(p2->cf,p2->px,p2->py,p2->pz,h3);
1707p2=p2->link;
1708}
1709return h3;
1710}
1711void evaluate(NODE *h1)
1712{
1713NODE *head;
1714int x, y, z;
1715float result=0.0;
1716head=h1;
1717printf("\nEnter x, y, z, terms to evaluate:\n");
1718scanf("%d%d%d", &x, &y, &z);
1719while(h1->link != head)
1720{
1721result = result + (h1->cf * pow(x,h1->px) * pow(y,h1->py) *
1722pow(z,h1->pz));
1723h1=h1->link;
1724}
1725result = result + (h1->cf * pow(x,h1->px) * pow(y,h1->py) *
1726pow(z,h1->pz));
1727printf("\nPolynomial result is: %f", result);
1728}
1729void main()
1730{
1731NODE *h1,*h2,*h3;
1732int ch;
1733clrscr();
1734h1=getnode();
1735h2=getnode();
1736h3=getnode();
1737h1->link=h1;
1738h2->link=h2;
1739h3->link=h3;
1740while(1)
1741{
1742printf("\n\n1.Evaluate polynomial\n2.Add two
1743polynomials\n3.Exit\n");
1744printf("Enter your choice: ");
1745scanf("%d", &ch);
1746switch(ch)
1747{
1748case 1:
1749printf("\nEnter polynomial to evaluate:\n");
1750h1=read_poly(h1);
1751display(h1);
1752evaluate(h1);
1753break;
1754case 2:
1755printf("\nEnter the first polynomial:");
1756h1=read_poly(h1);
1757printf("\nEnter the second polynomial:");
1758h2=read_poly(h2);
1759h3=add_poly(h1,h2,h3);
1760printf("\nFirst polynomial is: ");
1761display(h1);
1762printf("\nSecond polynomial is: ");
1763display(h2);
1764printf("\nThe sum of 2 polynomials is: ");
1765display(h3);
1766break;
1767case 3:
1768exit(0); break;
1769default:
1770printf("\nInvalid entry");
1771break;
1772}
1773getch();
1774}
1775}
1776Output:
1777 1. Evaluate polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
1778 2. Add two polynomials
1779 3. Exit
1780Enter your choice: 1
1781Enter polynomial to evaluate:
1782Enter coeff: 6 Enter x, y, z powers (0-indiacate NO term: 2 2 1
1783If you wish to continue press 1 otherwise 0: 1
1784 Enter coeff: -4 Enter x, y, z powers (0-indiacate NO term: 0 1 5
1785If you wish to continue press 1 otherwise 0: 1
1786Enter coeff: 3
1787Enter x, y, z powers (0-indiacate NO term: 3 1 1
1788 If you wish to continue press 1 otherwise 0: 1
1789 Enter coeff: 2
1790x, y, z powers (0-indiacate NO term: 1 5 1
1791If you wish to continue press 1 otherwise 0: 1
1792Enter coeff: -2
1793Enter x, y, z powers (0-indiacate NO term: 1 1 3
1794 If you wish to continue press 1 otherwise 0: 0
1795Polynomial is: 6 x^2 y^2 z^1 + -4 x^0 y^1 z^5 + 3 x^3 y^1 z^1 + 2 x^1 y^5 z^1 + -2 x^1 y^1 z^3
1796 Enter x, y, z, terms to evaluate: 1 1 1
1797Polynomial result is: 5.000000
1798 1. Evaluate polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
17992. Add two polynomials
1800 3. Exit Enter your choice: 2
1801 Enter 1st polynomial: Enter coeff: 4
1802Enter x, y, z powers (0-indiacate NO term: 2 2 2
1803If you wish to continue press 1 otherwise 0: 1
1804Enter coeff: 3 Enter x, y, z powers (0-indiacate NO term: 1 1 2
1805 If you wish to continue press 1 otherwise 0: 0
1806Enter 2nd polynomial: Enter coeff: 6
1807Enter x, y, z powers (0-indiacate NO term: 2 2 2
1808 If you wish to continue press 1 otherwise 0: 0
1809 Polynomial is: 1st Polynomial is: 4 x^2 y^2 z^2 + 3 x^1 y^1 z^2
1810 2nd Polynomial is: 6 x^2 y^2 z^2 Added polynomial: 10 x^2 y^2 z^2 + 3 x^1 y^1 z^2 1.
1811 Evaluate polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
18122. Add two polynomials 3. Exit Enter your choice: 3
1813Program 10:
1814Design, Develop and Implement a menu driven Program in C for the following operations on
1815Binary Search Tree (BST) of Integers
1816a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
1817b. Traverse the BST in Inorder, Preorder and Post Order
1818c. Search the BST for a given element (KEY) and report the appropriate message
1819d. Delete an element(ELEM) from BST
1820e. Exit
1821A binary search tree (BST) is a tree in which all nodes follows the below mentioned properties −
1822 The left sub-tree of a node has key less than or equal to its parent node's key.
1823 The right sub-tree of a node has key greater than or equal to its parent node's key.
1824Thus, a binary search tree (BST) divides all its sub-trees into two segments; left sub-tree and right sub-tree and can be defined as −
1825left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
1826Basic Operations
1827Following are basic primary operations of a tree which are following.
1828 Search − search an element in a tree.
1829 Insert − insert an element in a tree.
1830 Preorder Traversal − traverse a tree in a preorder manner.
1831 Inorder Traversal − traverse a tree in an inorder manner.
1832 Postorder Traversal − traverse a tree in a postorder manner.
1833
1834#include <stdio.h>
1835#include <stdlib.h>
1836struct BST
1837{
1838int data;
1839struct BST *left;
1840struct BST *right;
1841};
1842typedef struct BST NODE;
1843NODE *node;
1844NODE* createtree(NODE *node, int data)
1845{
1846if (node == NULL)
1847{
1848NODE *temp;
1849temp= (NODE*)malloc(sizeof(NODE));
1850temp->data = data;
1851temp->left = temp->right = NULL;
1852return temp;
1853}
1854if (data < (node->data))
1855{
1856node->left = createtree(node->left, data);
1857}
1858else if (data > node->data)
1859{
1860node -> right = createtree(node->right, data);
1861}
1862return node;
1863}
1864NODE* search(NODE *node, int data)
1865{
1866if(node == NULL)
1867printf("\nElement not found");
1868else if(data < node->data)
1869{
1870node->left=search(node->left, data);
1871}
1872else if(data > node->data)
1873{
1874node->right=search(node->right, data);
1875}
1876else
1877printf("\nElement found is: %d", node->data);
1878return node;
1879}
1880void inorder(NODE *node)
1881{
1882if(node != NULL)
1883{
1884inorder(node->left);
1885printf("%d\t", node->data);
1886inorder(node->right);
1887}
1888}
1889void preorder(NODE *node)
1890{
1891if(node != NULL)
1892{
1893printf("%d\t", node->data);
1894preorder(node->left);
1895preorder(node->right);
1896}
1897}
1898void postorder(NODE *node)
1899{
1900if(node != NULL)
1901{
1902postorder(node->left);
1903postorder(node->right);
1904printf("%d\t", node->data);
1905}
1906}
1907NODE* findMin(NODE *node)
1908{
1909if(node==NULL)
1910{
1911return NULL;
1912}
1913if(node->left)
1914return findMin(node->left);
1915else
1916return node;
1917}
1918void main()
1919{
1920int data, ch, i, n;
1921NODE *root=NULL;
1922clrscr();
1923while (1)
1924{
1925printf("\n1.Insertion in Binary Search Tree");
1926printf("\n2.Search Element in Binary Search Tree");
1927printf("\n3.Inorder\n4.Preorder\n5.Postorder\n6.Exit");
1928printf("\nEnter your choice: ");
1929scanf("%d", &ch);
1930switch (ch)
1931{
1932case 1: printf("\nEnter N value: " );
1933scanf("%d", &n);
1934printf("\nEnter the values to create BST like(6,9,5,2,8,15,24,14,7,8,5,2)\n");
1935for(i=0; i<n; i++)
1936{
1937scanf("%d", &data);
1938root=createtree(root, data);
1939}
1940break;
1941case 2: printf("\nEnter the element to search: ");
1942scanf("%d", &data);
1943root=search(root, data);
1944break;
1945case 3: printf("\nInorder Traversal: \n");
1946inorder(root);
1947break;
1948case 4: printf("\nPreorder Traversal: \n");
1949preorder(root);
1950break;
1951case 5: printf("\nPostorder Traversal: \n");
1952postorder(root);
1953break;
1954case 6: exit(0);
1955default: printf("\nWrong option");
1956break;
1957}
1958}
1959}
1960Output:
19611. Insertion in Binary Search Tree
1962 2. Search Element in Binary Search Tree
19633. Inorder
19644. Preorder
19655. Postorder
19666. Exit
1967Enter your choice: 1
1968Enter N value: 12 Enter the values to create BST like(6,9,5,2,8,15,24,14,7,8,5,2)
19696 9 5 2 8 15 24 14 7 8 5 2
19701. Insertion in Binary Search Tree
19712. Search Element in Binary Search Tree
19723. Inorder
19734. Preorder
1974 5. Postorder
19756. Exit
1976Enter your choice: 3
1977Inorder Traversal: 2 5 6 7 8 9 14 15 24
1978 1. Insertion in Binary Search Tree
1979 2. Search Element in Binary Search Tree
1980 3. Inorder
1981 4. Preorder
1982 5. Postorder
1983 6. Exit
1984Enter your choice: 4
1985Preorder Traversal: 6 5 2 9 8 7 15 14 24
19861. Insertion in Binary Search Tree
19872. Search Element in Binary Search Tree
19883. Inorder
1989 4. Preorder
1990 5. Postorder
19916. Exit
1992Enter your choice: 5
1993Postorder Traversal: 2 5 7 8 14 24 15 9 6
19941. Insertion in Binary Search Tree
1995 2. Search Element in Binary Search Tree
19963. Inorder
19974. Preorder
19985. Postorder
19996. Exit
2000Enter your choice: 2 Enter the element to search: 24
2001 Element found is: 24
20021. Insertion in Binary Search Tree
2003 2. Search Element in Binary Search Tree
20043. Inorder
20054. Preorder
2006 5. Postorder
20076. Exit
2008Enter your choice: 2
2009 Enter the element to search: 50
2010 Element not found
20111. Insertion in Binary Search Tree
2012 2. Search Element in Binary Search Tree
20133. Inorder
20144. Preorder
20155. Postorder
2016 6. Exit Enter your choice: 6
2017
2018Program 11:
2019Design, Develop and Implement a Program in C for the following operations on Graph(G) of
2020Cities
2021a. Create a Graph of N cities using Adjacency Matrix.
2022b. Print all the nodes reachable from a given starting node in a digraph using BFS method
2023c. Check whether a given graph is connected or not using DFS method.
2024Depth-first search (DFS)
2025There are various ways to traverse (visit all the nodes) of a graph systematically. A couple of these ways (depth-first and breadth-first) give us some information about graph structure (e.g. connectedness).
2026In depth-first search the idea is to travel as deep as possible from neighbour to neighbour before backtracking. What determines how deep is possible is that you must follow edges, and you don't visit any vertex twice.
2027To do this properly we need to keep track of which vertices have already been visited, plus how we got to (the path to...) where we currently are, so that we can backtrack. We could keep track of which nodes were visited in a boolean array, and a stack to push nodes onto that we mean to visit (the course Readings have a recursive algorithm for DFS which takes a slightly different approach).
2028#include<stdio.h>
2029#include<conio.h>
2030int a[10][10], n, m, i, j, source, s[10], b[10];
2031int visited[10];
2032void create()
2033{
2034printf("\nEnter the number of vertices of the digraph: ");
2035scanf("%d", &n);
2036printf("\nEnter the adjacency matrix of the graph:\n");
2037for(i=1; i<=n; i++)
2038for(j=1; j<=n; j++)
2039scanf("%d", &a[i][j]);
2040}
2041void bfs()
2042{
2043int q[10], u, front=0, rear=-1;
2044printf("\nEnter the source vertex to find other nodes reachable or not: ");
2045scanf("%d", &source);
2046q[++rear] = source;
2047visited[source] = 1;
2048printf("\nThe reachable vertices are: ");
2049while(front<=rear)
2050{
2051u = q[front++];
2052for(i=1; i<=n; i++)
2053{
2054if(a[u][i] == 1 && visited[i] == 0)
2055{
2056q[++rear] = i;
2057visited[i] = 1;
2058printf("\n%d", i);
2059}
2060}
2061}
2062}
2063void dfs(int source)
2064{
2065int v, top = -1;
2066s[++top] = 1;
2067b[source] = 1;
2068for(v=1; v<=n; v++)
2069{
2070if(a[source][v] == 1 && b[v] == 0)
2071{
2072printf("\n%d -> %d", source, v);
2073dfs(v);
2074}
2075}
2076}
2077void main()
2078{
2079int ch;
2080clrscr();
2081while(1)
2082{
2083printf("\n1.Create Graph\n2.BFS\n3.Check graph connected or not(DFS)\n4.Exit");
2084printf("\nEnter your choice: ");
2085scanf("%d", &ch);
2086switch(ch)
2087{
2088case 1: create();
2089 break;
2090case 2: bfs();
2091for(i=1;i<=n;i++)
2092if(visited[i]==0)
2093printf("\nThe vertex that is not rechable %d" ,i);
2094break;
2095case 3: printf("\nEnter the source vertex to find the connectivity: ");
2096scanf("%d",&source);
2097m=1;
2098dfs(source);
2099for(i=1;i<=n;i++) {
2100if(b[i]==0)
2101m=0;
2102}
2103if(m==1)
2104printf("\nGraph is Connected");
2105else
2106printf("\nGraph is not Connected");
2107break;
2108default: exit(0);
2109}
2110}
2111}
2112OUTPUT:
21131. Create Graph
2114 2.BFS
21153.Check graph connected or not (DFS)
2116 4.Exit
2117Enter your choice: 1
2118Enter the number of vertices of the digraph: 5
2119Enter the adjacency matrix of the graph:
21200 1 1 1 0
21211 0 0 1 1
21221 0 0 1 0
21231 1 1 0 1
21240 1 0 1 0
2125
21261. Create Graph
21272.BFS
2128 3.Check graph connected or not (DFS)
2129 4.Exit
2130Enter your choice: 2
2131Enter the source vertex to find other nodes reachable or not: 1
21322 3 4 5
21331. Create Graph
2134 2.BFS
2135 3.Check graph connected or not (DFS)
21364.Exit
2137Enter your choice: 3
2138 Enter the source vertex to find the connectivity: 1
2139 1 -> 2
2140 2 -> 4
2141 4 -> 3
2142 4->5
2143Graph is Connected
21441. Create Graph 2.BFS 3.Check graph connected or not (DFS) 4.Exit Enter your choice:
21454
2146Program 12:
2147Given a File of N employee records with a set K of Keys(4-digit) which uniquely determine the records in file F. Assume that file F is maintained in memory by a Hash Table(HT) of mmemory locations with L as the set of memory addresses (2-digit) of locations in HT. Let the keys in K and addresses in L are Integers. Design and develop a Program in C that uses Hash function H: K L as H(K)=K mod m (remainder method), and implement hashing technique to map a given key K to the address space L. Resolve the collision (if any) using linear probing.
2148
2149Direct-address table
2150If the keys are drawn from the reasoning small universe U = {0, 1, . . . , m-1} of keys, a solution is to use a Table T[0, . m-1], indexed by keys. To represent the dynamic set, we use an array, or direct-address table, denoted by T[0 . . m-1], in which each slot corresponds to a key in the universe.
2151Following figure illustrates the approach.
2152
2153
2154Each key in the universe U i.e., Collection, corresponds to an index in the table T[0 . . m-1]. Using this approach, all three basic operations (dictionary operations) take θ(1) in the worst case.
2155Hash Tables
2156When the size of the universe is much larger the same approach (direct address table) could still work in principle, but the size of the table would make it impractical. A solution is to map the keys onto a small range, using a function called a hash function. The resulting data structure is called hash table.
2157With direct addressing, an element with key k is stored in slot k. With hashing =, this same element is stored in slot h(k); that is we use a hash function h to compute the slot from the key. Hash function maps the universe U of keys into the slot of a hash table T[0 . . .m-1].
2158h: U → {0, 1, . . ., m-1}
2159More formally, suppose we want to store a set of size n in a table of size m. The ratio α = n/m is called a load factor, that is, the average number of elements stored in a Table. Assume we have a hash function h that maps each key k U to an integer name h(k) [0 . . m-1]. The basic idea is to store key k in location T[h(k)].
2160Typical, hash functions generate "random looking" valves. For example, the following function usually works well
2161h(k) = k mod m where m is a prime number.
2162Is there any point of the hash function? Yes, the point of the hash function is to reduce the range of array indices that need to be handled.
2163Collision
2164As keys are inserted in the table, it is possible that two keys may hash to the same table slot. If the hash function distributes the elements uniformly over the table, the number of conclusions cannot be too large on the average, but the birthday paradox makes it very likely that there will be at least one collision, even for a lightly loaded table
2165
2166
2167A hash function h map the keys k and j to the same slot, so they collide.
2168There are two basic methods for handling collisions in a hash table: Chaining and Open addressing.
2169
2170#include <stdio.h>
2171#include <stdlib.h>
2172#define MAX 100
2173int create(int);
2174void linear_prob(int[], int, int);
2175void display (int[]);
2176void main()
2177{
2178int a[MAX],num,key,i;
2179int ans=1;
2180printf(" collision handling by linear probing : \n");
2181for (i=0;i<MAX;i++)
2182{
2183a[i] = -1;
2184}
2185do
2186{
2187printf("\n Enter the data");
2188scanf("%4d", &num);
2189key=create(num);
2190linear_prob(a,key,num);
2191printf("\n Do you wish to continue ? (1/0) ");
2192scanf("%d",&ans);
2193}while(ans);
2194display(a);
2195}
2196int create(int num)
2197{
2198int key;
2199key=num%100;
2200return key;
2201}
2202void linear_prob(int a[MAX], int key, int num)
2203{
2204int flag, i, count=0;
2205flag=0;
2206if(a[key]== -1)
2207{
2208a[key] = num;
2209}
2210else
2211{
2212printf("\nCollision Detected...!!!\n");
2213i=0;
2214while(i<MAX)
2215{
2216if (a[i]!=-1)
2217count++;
2218i++;
2219}
2220printf("Collision avoided successfully using LINEAR PROBING\n");
2221if(count == MAX)
2222{
2223printf("\n Hash table is full");
2224display(a);
2225exit(1);
2226}
2227for(i=key+1; i<MAX; i++)
2228if(a[i] == -1)
2229{
2230a[i] = num;
2231flag =1;
2232break;
2233}
2234//for(i=0;i<key;i++)
2235i=0;
2236while((i<key) && (flag==0))
2237{
2238if(a[i] == -1)
2239{
2240a[i] = num;
2241flag=1;
2242break;
2243}
2244i++;
2245}
2246}
2247}
2248void display(int a[MAX])
2249{
2250int i,choice;
2251printf("1.Display ALL\n 2.Filtered Display\n");
2252scanf("%d",&choice);
2253if(choice==1)
2254{
2255printf("\n the hash table is\n");
2256for(i=0; i<MAX; i++)
2257printf("\n %d %d ", i, a[i]);
2258}
2259else
2260{
2261printf("\n the hash table is\n");
2262for(i=0; i<MAX; i++)
2263if(a[i]!=-1)
2264{
2265printf("\n %d %d ", i, a[i]);
2266continue;
2267}
2268}
2269}
2270
2271Output:
2272collision handling by linear probing :
2273 Enter the data
2274 1234
2275Do you wish to continue ? (1/0) 1
2276 Enter the data2548
2277Do you wish to continue ? (1/0) 1
2278Enter the data3256
2279Do you wish to continue ? (1/0) 1
2280Enter the data1299
2281Do you wish to continue ? (1/0) 1
2282 Enter the data1298
2283Do you wish to continue ? (1/0) 1
2284Enter the data1398
2285Collision Detected...!!! Collision avoided successfully using LINEAR PROBING
2286Do you wish to continue ? (1/0) 0
22871.Display ALL
22882.Filtered Display
22892
2290the hash table is
22910 1398
229234 1234
2293 48 2548
229456 3256
2295 98 1298
229699 1299
2297
2298Extra Lab Programs
22991. Design, develop, and execute a program in C to simulate the working of a queue of integers using an array. Provide the following operations:
23001.Insert
23012.Delete
23023.Display
2303
2304#include<stdio.h> #include<stdlib.h> #define size 5 int q[size],f=0,r=-1,del,i; int insert() { if(r==(size-1)) printf("Queue is full\n"); else { r++; printf("Item to be inserted\n");
2305scanf("%d",&q[r]); }} int delete() { if(f>r) printf("Queue is Empty\n"); else { printf("deleted element is %d\n",q[f]); del=q[f]; f++; }} int display() { if(f>r) printf("Queue is Empty\n"); else { for(i=f;i<=r;i++) printf("%d\t",q[i]); printf("\n"); }} int main() { for(;;) { intitem,option,i,del; printf("\n1.Insert \n2.Delete \n3.Display \n4.EXIT\n"); printf("Enter the option\n"); scanf("%d",&option); switch(option) {case 1:insert(); break; case 2:delete(); break; case 3:display(); break; default :exit(0); }}}
23062. Design, develop, and execute a program in C to read a sparse matrix of integer values and to search the sparse matrix for an element specified by the user. Print the result of the search appropriately. Use the triple to represent an element in the sparse matrix.
2307
2308#include<stdio.h> #define MAX 100 structspnode { introw,col,val; }
2309spmat[MAX]; void search(int key); main() { intnrow, ncol, n,i,key; printf("enter the maximum row value\t"); scanf("%d",&nrow); printf("\n enter the maximum column value\t"); scanf("%d",&ncol); printf("\n enter the no of nonzero element\t"); scanf("%d",&n); spmat[0].row=nrow; spmat[0].col=ncol; spmat[0].val=n; printf("\n enter the row , col, value of non zero element\n \n"); for(i=1;i<=n;i++) { printf("\n %d th element", i); scanf("%d",&spmat[i].row); scanf("%d",&spmat[i].col); scanf("%d",&spmat[i].val); } printf("\n enter the element to be searched\t"); scanf("%d",&key); search(key); } void search(int key) { int i=1; while(i<=spmat[0].val) { if(spmat[i].val==key) {printf("\n the value found at <%d, %d>", spmat[i].row,spmat[i].col); return; } else i++; } printf("\n the element not found"); }
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323Viva Questions
23241. What is data structure?
23252. What are the different types of queues available?
23263. What is the main difference between a stack and a queue
23274. What are the applications of Queue
23285. What is the difference between a Stack and an Array?
23296. What do you mean by recursive definition?
23307. What is a linked list?
23318. What are the advantages of linked list over array (static data structure)?
23329. Can we apply binary search algorithm to a sorted linked list, why?
233310. What do you mean by overflow and underflow?
233411. What are the disadvantages array implementations of linked list?
233512. What is a priority queue?
233613. What are the disadvantages of representing a stack or queue by a linked list?
233714. Define circular list? What are the disadvantages of circular list?
233815. Define double linked list?
233916. What is the data structures used to perform recursion?
234017. What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
234118. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.
234219. List out few of the Application of tree data-structure?
234320. List out few of the applications that make use of Multilinked Structures?
234421. In tree construction which is the suitable efficient data structure?
234522. What are binary trees?
234623. Explain Binary Search Tree
234724. What are multidimensiotnal arrays?
234825. Are linked lists considered linear or non-linear data structures?
234926. How does dynamic memory allocation help in managing data?
235027. How do you insert a new item in a binary search tree?
235128. What is a graph? What are the applications of graph.
235229. Differentiate linear from non linear data structure.
235330. What is hashing?What are the types of Collision Resolution Techniques and the methods used in each of the type?
235431. What are the differentgraph traversal methods?
2355
2356
2357