Aait SYLABUS Shee ears) BE 2106 DATA STRUCTURE SYLLABUS (3-0-0) THEORY PAPER (B.TECH ,SECOND SEMESTER) Module-1! [12 hours] Introduction to data structures: storage structure for arrays, sparse matrices, Stacks and Queues: representation and application. Linked lists: Single linked lists, linked list representation of stacks and Queues. Operations on polynomials, Double linked list, circular list. . Module -1l_ [12 Hours} Dynamic storage management-garbage collection and compaction, infix to post fix conversion, postfix expression evaluation. Trees: Tree terminology, Binary tree, Binary search tree, General tree, B+ tree, AVL Tree, Complete Binary Tree representation, Tree traversals, operation on Binary tree- expression Manipulation. Module -IIl [12 Hours] Graphs: Graph terminology, Representation of graphs, path matrix, BFS (breadth first search), DFS (depth first search), topological sorting, Warshall’s algorithm (shortest path algorithm.) Sorting and Searching techniques ~ Bubble sort, selection sort, Insertion sort, Quick sort, merge sort, Heap sort, Radix sort. Linear and binary search methods, Hashing techniques and hash functions.ey INTRODUCTION TO DATA STRUCTURE Definition: The logical or mathematical model of a particular organization of data is called q data structure. Or The organized collection of data is called data structure, Classificatio Data structure | jug ee: RR Primitive Data structure Non-Primitive Data structure Int Float Char Pointer Array Uist Files i ar ea Stack Queue Graph i Primitive data structure:- These are basic structures and are directly operated upon by the machine instruction. These in general have different representations on different computers. Integers, floating point numbers, character, string and pointers. Non-Primitive data structure:-These are more sophisticated data structures. These are derived from the primitive data structures. The non-primitive data structure emphasize on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items. 3 Example: Array, List and files Linear data structure: A data structure is said to be linear if its elements form a linear sequence. In the linear data structures processing of the data item is possible in linear fashion, 'e. data can be processed one by one sequentially. There are two ways to represent a linear (data structure) information in memory. i) By contiguous memory location. ii) By pointers and links. Linear data structure contains following types of data structures. ‘Array, Stack, Queue, Link list Non-Linear data structure: A data structure in which insertion and deletion is not possible called non-linear data structure. Non linear data structure contains in linear fashion following type of data structure. Tree, graph. Data structure operation: The possible operations on the linear/non-linear data structure a 1. Traversing: Accessing or visiting each record exactly once so that certain items in the record may be processed. N.B:- A record is a collection of fields, a information a file is a collection records. 2, Searching: Finding the location of the record with a given key value. 3. Inserting: Adding a new record to the structure. fields is a single elementary unit of4. Deleting: Removing a record from the strus ture. 5. Sorting: Arranging the 1 al order. 6. Merging: Combining the records in two different sorted files into a single sorted file. Definition of Algorithm An algorithm is a finite set of instructions that are Particular task. Each instruction tells what task has to be performed, Or It is a clearly specified set of instructions to be followed to solve a Characteristic of an Algorithn Input: it should have zero or more output. Output: the algorithm should return at least one output, Definiteness: each instruction is clear and unambiguous, Finiteness: if we trace out the instruction of an algorithm, then for all cases the algorithm terminates after a finite number of steps, Effectiveness: Each instruction must be sufficiently bi pen can carry it out ina finite time. ‘Time Complexity: The time complexity of ai completion as a function o! Space Complexity: The space complexity of an algorithm is the amount of memory it needs to run for completion mn of its to be carried out in order to solve a problem so that person using paper and algorithm is the amount $f computer time it needs to run for input size. of a funct put size, Example: Without loop Intsum,Lj.Kb.....t3 0 Sum=itj+.....44; 1 Tim Space=11*2=22 bytes. Loop For(i=1 to 10) " Sum=sum+I; 10 Time=21 Space=2*2=4bytes Therefore we conclude that from above example 1 Time Complexity ¢ ———_— Spacecomplexity Array: An ee is a collection of similar data items it is also known as linear data structure. There exists a linear relationship between array elements. The array elements lie in the computer memory in linier fashion. If we chose the name A for the array then the elements of A are denoted as bracket notation A[0},A[1]....A[n] The syntax to define an array i Data type Array_name[SIZE]; Example: int A[20]; Memory Representation of a Matrix: , Like one dimensional array, matrices are also stored in contiguous memory locations. There are two conversion of storing any matrix in memory. i, Row major order. ii, Column major order. ;sments of @ matrix are stor major order el then in 2 -olumn ulation of Matrix elements In Row of I" row column by © ed in a row by row basis, ie. all the elemeny, n major order elements are storeq row and so on. Similarly in columt eet jajor Onder: i Bowox starts from O fi Hinde SALI address+(i no, of columns +j)*w Adgresjaress-location of the 1” element in matrix se : : Bae ade eet ofthe elements{ example: iit then w=2) from 1 address of A[2][3]=b+(2*10+3)*2=b+46 Column-Major-Order: If index starts from 0 Ifindex starts from 1 of (A[iJ[))=base address'((i-1) *no, of columns +(j-1))*¥ -xample: tn oe Consider a matrix of 1010 ie, no, of column is 10 and no, of. Row is 10. To find out Address of (A[i][j])=base address+(j *no. of Rows +i)*w Address of (A[i][])=base address +((j+1) *no, of Rows +i+1))*w Example: i - Consider a matrix of 1010 i.e. no. of column is 10 and no, of. Row is 10. To find out the address of A[2][3]=b+(3*1042)*2=b+46 Insertion: This operation is used to insert an element into an array provided that the array is not full. Algorithm: Step 1 Set ismaxsize Step 2. Repeat step 3 and step 4 until i>pos-1 Step AliI=AGi-1] Step 4: for(i=n; Ali-Ali-1]; A[pos-1]=item; Where n: The no. of element inserted into the array, Pos: position where data to be inserted, Item: element to be inserted, Progran void main() f int arr[20].n, clrscr(); printf("\nEnter the array size: "): scant("%d", en); printf("\nEnter the array elements"); for(i=0;i Hdefine size 10 int top=-1; int stack[size]; void push); jetions are mae d del and deletion are n whit » opposite order. emoved in the OPP’ be eres stack is at the top of ation in a tack. 5 set, tower of ‘TOP which contains the stack and assign into variableExample: +ab, *xy Infix expression to prefix polish notation using bracket { J to indicate a partial translation, Example: 1) (A+B)te = [FAB] "c= *+ABC 2) A+(B*C) = A+ [*BC] = +A°BC -ABJ/[-CD]=/+AB-CD [-AB]*[/DE] = *-AB/DE }+G= (A+ BD))/-EF}+G 3) (AtBY(C-D) 4) (A-B)(DE) 5) (A+BED VIE: tra BD|/-EF}G AP BD-EF]}+G = +/+at BD-EFG When the operator symbol is placed after ix expression or reverse polish expression. Postfix expression (Reverse Polish Notation ‘two operands then the expression is called pos Example: AB+, CD-, EF*, GH/ ‘One never needs parenthesis to determine the order of operation in any arithmetic expression written in reverse polish notation. This notation is frequently called postfix or suffix notation. Note:- The computer usually evaluated an arithmetic expression written in infix notation in two steps. 1. It converts the notation to postfix notation. 2. Then it evaluate the postfix expression, Translate Infix to postfix by inspection: 1, (A-B)*(D/E)=[AB-]*[DE/]=AB-DE/* 2. (A¥BtD)/(E-F)}+G=(A+[BDt ])/[EF-]+G=[ABD #)/[EF-}+G= [ABD 4EF-/}+G = ABDI +EF-/G+ A‘(B+DY/E- F*(G+H/K)=A*[BD+]/E-F*(G+[HK/])= A*[BD+)/E-P*[GHK/+] [ABD+*}/ E-F*[GHK/- [ABD+*E/]-[ FGHK/+*] -ABD+*E/FGHK/+*- ‘Translate Postfix into its equivalent infix expression: P:12,7,3,-,251,5,585¢ PH12(7-2)/,2,1,5,495¢ = (12/(7-3)), 2,154, (12/(7-3)), 2,145], + = (12(7-3)),2*(145)).+ =(12/(7-3))+ (2*(145)) ‘Transferring Infix expression to Postfix expression using stack /* Algorithm for reverse polish(Q,P)*! Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression P. Step I: PUSH “( “into the TOP of the stack and add *)” to the end of the Q. Step 2: Scan © from left o right and repeat step 3 10 step 6 foreach element of Q until the stack is empty. Step 3: Ifan operand is encountered, add it to P Step 4: Ifa “(is encountered push it onto stack, Step 5: If an operator® is encountered then: a) Repeatedly POP from the stack and add to P each operator ( on the top of the stack) which has the same precedence or higher than the operator® b)_ Add the operator to the stack. Step 6:Empty [ABEDFEF- Program: WAP to translate an infix expression 10 postfix: #include #include char stack{30}; int top=-1; int precedance(char c) inta; switeh(©) case"): a=0: break; case '(: a=15 break: case “!: a=2; break; case 20>) return a; void main() char in{50},p{50}: int HO; clrser(); print{("enter an in fix notaion: "); in); sca top++ stack{top]=(; I=strlen(in); in{!])' j-0: while(top!=1) iffisalphaCin[i})) top; plil=inlil ins else iflin{iJ-"0) { topt+s j stack{top}=inli}; else iftin[i] 9) , 4[ Symbol scanned iia Bs] K 2 6 si 2 4 + 3" 6 12 x 4 8 L 9 Ie 37 10D) aa Program: WAP to evaluate a postfix expression #include #include #include void main() int stack{20],top=-1,num,i=0,4,B; char s[20];, clrser(); printf("Enter the postfix expression \n"): scanf ("%s",s); while(sfi]!=\0") iffisalpha(sfi))) th printf("enter the value of %e: ",sli]): seanf{"%d" &num); top++; stack{top]=num; iH; } else i switch(sfi))a) Repeatedly pop from stack and a p Re a and add 10 P each operator which has the higher b) Then add® to stack Step 6: Ifa “(* encountered then a) Repeatedly POP from stack and add to “P “ peers add to“P” until a)” is encountered, Step 7: Exit Example: Convert the following infix expression to prefix expr Oe RE a prefix expression using stack __[ Symbol scanned xpression(P) | 1 H iz [a + (Si wee G ae [a ~ jed[os a ama | T mo) {7 + ye 8 P yee HGTP 9 ¥ Dat HGTP al 10. N yet in * De 4 | (12) M ye [HGTPNtM. | 13 ( ye HGTPN* Me Be 7 $ yee HGTPNY Ms | 15 Ce ye HGTPNT M*+C 16 | * yet HGTPNS MC eat = 0 HGTPN® M74CB [sy Fe yet HGTPN* M*+CB** | 197 a =a HGTPN*MECBA | Lol CT epry 7 THGTeNEMs+cBe*At | The required prefix notation result: Pop all the symbols of expression P and print the result P: +-+A**BC+*Mt NPTGH Evaluation of prefix expression: Algorithm: This algorithm finds the value of an arithmetic expression written in prefix notation Step 1: Add a “(“ at the beginning of P Step 2: Scan P from right to left and repeat step 3 and step 4 for each element of P until “¢* is encountered. Step 3: Ifan operand is encountered, put it on the stack. Step 4: If.an operator is encountered then: h Bech a) Remove the top two elements of the stack where A is the top element and B is the next top element. b) Evaluate A® B ¢) Place the result back on the stack.Print"\n1. Insert"); Printf("\n2. Delete");2. An output restricted Dequeu It is a Dequeue which allows insertion at only one end of the list but allows deletion at Of) Bike eet front ae, Algorithm for Insertion in Dequene: Step I [Check overflows condition] Ifrear=n-1 and front=0 then Print “OVERFLOW” AND Return Step 2: [Check front pointer value] If front>0 Front=front-1 Else Return Step 3: [Insert element at the front end] Qffront]=value Step 4: [Check rear pointer value] Tf rear<(n-1) rear=rear+1 else Return Step 5: [Insert element at the rear end) Qfrear=value Step 6: Exit Algorithm for Deletion in Dequewe: Step | [Check underflows condition] Ifrear=-1 and front= -1 then Print “UNDERFLOW” AND Return: Step 2: [Delete element at front end] If front>-1 value=Qffront] Return value Step 3: [Check Queue for empty] If{front—=rear) front=rear=-1 else front=front+1 Step 4: [Delete element at rear end]ifrear-l value-Qfreat] Return value ae Queue for emPts] front Tea) Front=rear— Else Rear-rear-l step 6: Exit Program: elements such as each element has been : ich elements are deleted and processed co jority Queues: re Queues is a collection of priority and such that the order in whi rules: i ined Rae of higher priority is processed before any element of lower prio 2 Two element of same priority are processed according to the order in r added to the queue. : Example: Timesharing system in which the processes of higher priority is executed of lower priority. There are two type of priority queue 1. Ascending priority queue: an ascending priority queue is a collectio which items can be inserted arbitrarily and from which only the small. removed. 2. Descending priority queue: A descending priority queue is similar but < of only the largest item. ae Program: WAP to implement Queue in Priority #include #inelude #include #define SIZE 5 int front=-1,rear=- struct que { int info,pr; }x{SIZE]; Void main() { void ins(void), Void del(void): Void view(voidy; int choice; char ¢; clrser(); do ; { Print("\nt Insert Prin nd Delete Print{"\n3. ViewLINKED LIST. A linked list or one way list is a linear collection of inear collection of data elements, called nodes where linear order is given by means of pointer Ina linked lisreachvode hactwerpaee ee 1, Information oa 2. Pointer to next node The last node of the list contains NULL in the pointer field. The pointer contains the address of the location where next information is stored. A linked list also contains a list pointer called START which contains the address of 1" node in the linked list, if there is no node in the list the list is called NULL list or empty list caer Node Patol. chon Nodes T[ a0 [2000] [0 |] 3000] sf 50 | 4000} ofa0_| MULE] Y Information part M Pointer to next node Single linked list Double linked list Circular list header linked list Operation: -—— Insert at beginning |___» insert at end | _+ insert after a given node {___+ insert at a specific location Insert [—— Insert at beginning |» Insert at end [insert after a given node |__+ insert at a specific location Deletion ‘Traversing: (Displaying) Insert at beginning: Sa a [a0 [et feo [so [eet] 20 P aaa 20 Algorithm: Step 1: START holds the address of the 1" node. Step 2: . Create a new node and allocate space to it. Struct node *P; P=getnode( ); /*P=(struct node*)malloc(sieof(struct node)); If P==NULL i Then print “Out of memory space” and exit Step info(P) = value; /*P->info=value;*/ Step 4: Link(P)-STARTStep 8: Temp>>next=P; Step 9: it Insert after a given node: ran ; Et fe To} fae ge liaany ou a Step 1: START points to the 1" node Step 2 [Declare a temporary pointer] Struct node *temp; intitem, value; Step 3: Temp=START temp points to 1" node Step 4 While(tempinfo!=item) temp=temp>next step 5 [Create a new node] Struct node *P; P=(struct node*)malloc (sizeofistruct node)); If P==NULL Then print “OUT OF MEMORY” and exit Step 6: P>info=value Exit Insertion at a specific location: Pah Step 1: ‘ START points to the 1" node Step 2: pointer] [Declare a temporary Struct node *temp: int loc, value, Step 3: Temp=START Step 4: While(inext!=NULL) tempI=temp temp=temp next ) Step 7: templ->next=NULL step 8: free(temp) step 9: exit Deletion after a given node: [starry te wo Lo} fo [od fo ot alo 14) — fremp g” [remp .” Step 1: START points to the I** node. Step 2: If START =NULL ‘Then print UNDER FLOW “and exit Step 3: [Declare a temporary pointer] Struct node *temp,*temp|; Step 4 Jitemp points to 1" node While(temp>>info!=item) temp=temp->next Step 6: temp!=temp->next step 7: temp->next=temp! next step 8: free(temp!) step 8: Location 3 exit fi ‘a specifica Location 3 12123, Deletion of a node at a specific location fee ee Eats He 4 bas | [remp 5. / Tremp} / Step 1:TART Step 5 While(temp!=NULL), If{temp> info Print“The item ‘Count=count+1 temp=temp->neat tem) Present at position count” and exit Step Print step 7: llement is not in the list” Stack using linked list: 1. Push operation using linked list:- The algorithm is based on the assumption that TOS points to the head(START) of the linked list and TOP is equal to NULL if the list is empty. PUSH: Inserting item at the beginning of the linked list. Fa mete Te TOP. ere Algorithm: Step I: TOP points to 1* node. Step 2: [create a new node and allocate space to it] Struct node *P; P=(struct node*)malloc(sizeofistruct node)); ULL) OUT OF MEMORY” and exit Step 3: 2. POP operation using linked list: ‘ POP: Deletion from the beginning of the linked list.Step 7: P>info=value Step 8: P>next=NULL Step 9: REARnext=P Step 10: REAR=P Step 11; Exit Queue deletion using linked list:= Deletion is just to delete the 1" node, ie. the node pointed by the front pointer, ee al elf ao [Nutt] Algorithm: Step 1: FRONT points to I* node, Step 2: If FRONT==NULL | Then print “UNDER FLOW” and exit Step 3: [Declare a temporary pointer] Struct node *temp; Step 4: ‘Temp-FRONT Step 5: FRONT=FRONT> next Step 6: Free(temp) Step 7: ing of two linked li pal weme30 a ee ee am * 6 Teme | [TEMP Algorithm: Step 1: START points to first node of list Step 2: Struct node *temp,*temp]: int item; Step 3: d Read the item from which the list to split Step 4: ‘Temp=START Step 5:Ifjtemp-info!=item) temp=temp>next step 6: tempI=femp>next step 7: temp nex-NULL step 8: ing the node value in a single linked list: : See 10 Algorithm: Step I: START points to first node of list Step 2: [declare two pointer to structure] Struct node *temp,*ptr; Step 3: temp=START Step 4: While(temp->nex t Pirtemp->next While(ptr!=NULL) t mua info) NULL) Tp=temp-> info; Temp>info=ptr> info Ptr info=p } Ptr=ptr->next } Temp=temp->next step 5: exit Reversing a single linked list:~ : 20 7 se) = iyAlgorithm: Step 1 START points to first node of list Step 2: [Declare four pointer to structure} Struct node *temp,*curr,¥ Step 3 Temp=START Step 4: If(temp>next Then EXIT Step 5: curr=temp step 6 pre step 7: curr->next=NULL step 8: while(prev->next!=NULL) A Ptr=prev->next Prev->next=curr Cur=prev Prev=ptr 5 Step 9: Prev->next Step 10: START=prev Step II: Exit prev,*ptry surt->next