ELEMENTARY DATA STRUCTURES

50 %
50 %
Information about ELEMENTARY DATA STRUCTURES
Education

Published on March 6, 2009

Author: ankush85

Source: authorstream.com

ELEMENTARY DATA STRUCTURES : 1 ELEMENTARY DATA STRUCTURES Data structures improve the performance of algorithms. STACKS AND QUEUES. A stack is an ordered list in which all insertion and deletions are made at one end,called the top. A queue is an ordered list in which all insertions take place at one end called the rear while all deletions take place at the other end, the front. ELEMENTARY DATA STRUCTURES (Contd..) : 2 ELEMENTARY DATA STRUCTURES (Contd..) Stacks are Last In First Out lists. Queues are First In First Out lists. E Top D Front Rear C B A B C D E A Stack is represented in memory as a one-dimensional array Stack (1:n), n is the maximum number of elements Stack (1) = A, Stack (2) = B, etc. If stack index is top, stack (top) = E STACKEMPTY is true if top = 0. ELEMENTARY DATA STRUCTURES (Contd..) : 3 ELEMENTARY DATA STRUCTURES (Contd..) Operations on stacks Inserting element into stack, deleting element from stack| Procedure ADD (item, stack, n, top) // inserts item into stack of size n // // with index top // if top ? n then call STACKFULL endif top ? top +1 Stack ( top ) ? item end ADD ELEMENTARY DATA STRUCTURES (Contd..) : 4 ELEMENTARY DATA STRUCTURES (Contd..) //Deleting element from stack// Procedure DELETE (item, stack, n, top) // remove the top element // // and store in item // if top ? 0 then call STACKFULL endif item ? stack (top) top ? top -1 end DELETE ELEMENTARY DATA STRUCTURES (Contd..) : 5 ELEMENTARY DATA STRUCTURES (Contd..) Linked or pointer representation of stacks DATA Link NODE Node contains data and link; data field contains an item of stack; link points to the node with next item. top Stack E D E D C B A O C B A Linked Representation of stack ELEMENTARY DATA STRUCTURES (Contd..) : 6 Stack is a pointer variable pointing to node with top most item. Insertion and deletion in linked stack contain the following operations. Insertion operations Call GETNODE(T) Data(T) ? item Link (T) ? stack // Link (T) is pointing to whatever // // Stack is pointing to // Stack ? T// stack is pointing to T // ELEMENTARY DATA STRUCTURES (Contd..) ELEMENTARY DATA STRUCTURES (Contd..) : 7 ELEMENTARY DATA STRUCTURES (Contd..) Deletion operations If stack = 0 then call stackempty endif // stack is not pointing to any node// item ? Data (Stack ) T ? stack // A pointer to the first node is saved // Stack ?Link (stack ) // Stack is now pointing to the next node // call Retnode (T) Linked Representation requires more storage than sequential one. Representation of Queues : 8 Representation of Queues An efficient representation is using circular array. If Q ( 0:n-1) is a circular queue with n positions When rear = n-1, the next element is entered at Q (0)=Q ((rear+1) mod n) in case it is free. Representation of Queues (Contd..) : 9 Representation of Queues (Contd..) To distinguish between the cases queue full and queue empty, we keep the first position i.e.Q (0) free. Front will always point to one position anticlockwise from the first element, rear will point to the last element. Representation of Queues (Contd..) : 10 Representation of Queues (Contd..) The following are two circular queues with 4 elements : (0) (n-1) (n-2) (1) (2) (3) (3) (4) J1 J2 J3 J4 J1 J2 J3 J4 0 2 n-1 n-2 n-3 1 Representation of Queues (Contd..) : 11 Representation of Queues (Contd..) Inserting one element moves rear one position clockwise. Deleting an element moves front one position clockwise. Procedure ADDQ (item, Q, n, front, rear) // insert item in circular queue Q (0:n-1) // rear = (rear+1 ) mod n if front = rear then call QUEUEFULL endif Q (rear ) ? item end ADDQ Representation of Queues (Contd..) : 12 Representation of Queues (Contd..) Procedure delete (item, Q, n, front, rear) // removes the front element and stores it in item // if front=rear then call QUEUEEMPTY end if front=(front +1) mod n item? Q (front) end DELETEQ To use all n positions, a variable tag can be used. Tag= 0 if and only if the queue is empty. Linked Representation for Queues : 13 Linked Representation for Queues A B C D O Front rear // delete q // //Add q // Item ? data (front) call Getnode(T) T ? front (q) data(T) ? item; Link(T) ? 0) Front ? Link (front) if front = 0 then front ?T Retnode(T) else link(rear) ?T endif TREES : 14 TREES Definition: A tree is a finite set of one or more nodes such that (i) there is a specially designated node called the root (ii) the remaining node are partitioned into n ? 0 disjoint sets T1 … Tn where each Ti i=1…n is a tree Ti i=1..n are called subtrees of the root. TREES (Contd..) : 15 TREES (Contd..) Level A ……………… 1 B C D ……………….2 E F G H I J …….3 K L M ……………….. 4 TREES (Contd..) : 16 TREES (Contd..) Degree : The number of subtrees of a node is called degree A-root, degree of A is 3, B is 2, C is 1, F is 0. Nodes with degree 0 are terminals or leaf nodes (K, L, M) Nodes excluding leaves are called non terminals. The degree of a tree is the maximum degree of the nodes in the tree. TREES (Contd..) : 17 TREES (Contd..) The root is at level one. If a node is at level p , then its children are at level p+1. The height or depth of a tree is defined to be the maximum level of any node in the tree. A forest is a set of n ? 0 disjoint trees. If we remove the root of a tree, we get a forest. Representing Trees in Computers Memory : 18 Representing Trees in Computers Memory (Fig. – 1) D F C E B G A Linked representation for fig.-1 is as follows : 19 Linked representation for fig.-1 is as follows A 1 1 1 1 O O O B O C O G O O D O 1 O F O O E O Representing Trees in Computers Memory (Contd..) : 20 Representing Trees in Computers Memory (Contd..) Each node in the tree has three fields. TAG DATA LINK: TAG = 0 means DATA contains item. TAG = 1 means Data contains pointer. BINARY TREE : 21 BINARY TREE Definition : A binary tree is a finite set of nodes which is either * empty or consists of a root and two disjoint binary trees called the left and right sub trees. ( *To enable the left or right subtree empty, the definition says either empty). BINARY TREE (Contd..) : 22 BINARY TREE (Contd..) Binary trees Skewed to right A A B A B C A D C BINARY TREES (Contd..) : 23 BINARY TREES (Contd..) Result – 1 : The maximum number of nodes on level i of a binary tree is 2 i-1 Figure-2 Result – 2 : The maximum number of nodes in a binary tree of depth k is 2 k-1 A B D E C G F Full and Complete binary trees : 24 Full and Complete binary trees FULL BINARY TREE The binary tree of depth k which has exactly 2 k-1 nodes is called a full binary tree of depth k. Figure-2 is a full binary tree of depth 3. Definition : Complete Binary Tree : A binary tree with n nodes and of depth k is complete iff its nodes correspond to the nodes which are numbered 1 to n in the full binary tree of depth k. Nodes on any level are numbered from left to right. COMPLETE BINARY TREE (Contd..) : 25 COMPLETE BINARY TREE (Contd..) Not a complete is a complete Complete binary tree binary tree binary tree. A B E C G F D A B A B FULL BINARY TREE (Contd..) : 26 FULL BINARY TREE (Contd..) Lemma : If a complete binary tree with n nodes is represented sequentially,then for any node with index i, 1 ? i ? n. Parent (i) is at ?i/2? if i<>1 if i=1 it is the root Lchild (i) is at 2i if 2i ?n, if 2i?n then i has no left child. Rchild(i) is at 2i+1 if 2i+1?n,if 2i+1?n, i has no right child. Notation : ?d? Ceil (d) returns a value rounded up-to a next higher Integer. ?d? floor (d) rounded down to the lower integer Representation of Binary Trees In Memory : 27 Representation of Binary Trees In Memory A B C D E A B - C - - - D - --- E A B E D H I C F G A B C D E F G H I Figure - 3 Figure - 4 Representation of Binary Trees In Memory (Contd..) : 28 Representation of Binary Trees In Memory (Contd..) Sequential representation is good for complete binary trees while it is wasteful for many other binary trees. Insertion or deletion require movement of many nodes. Representation of Binary Trees In Memory (Contd..) : 29 Representation of Binary Trees In Memory (Contd..) Linked representation for figures 3 and 4 are as below. Each node contains - LCHILD … pointer - DATA …. item - RCHILD Pointer. Representation of Binary Trees In Memory (Contd..) : 30 Representation of Binary Trees In Memory (Contd..) T T A O A B O C O D O O E O B D O E O C O F O O H O O I O O G O Application of Binary Trees : 31 Binary Search Tree (BST) BST is constructed as follows: The data associated with any node P is both - (i) alphabetically greater than the data in the nodes contained in the left sub-tree of P and - (ii) alphabetically less than or equal to the data in the nodes contained in the right sub-tree of P. if Else repeat BST Application of Binary Trees Application of Binary Trees (Contd..) : 32 Application of Binary Trees (Contd..) With n elements n! BSTs can be formed by making any element as root. With {1,2,3 } we can have 3! = 6 BSTs as follows B(1,2,3) B(2,1,3) B(1,3,2) B(3,1,2) B(2,3,1) B(3,2,1) 1 2 3 2 1 3 1 3 2 3 1 2 2 1 3 3 2 1 Application of Binary Trees (Contd..) : 33 Application of Binary Trees (Contd..) The in-order traversal of the binary search tree gives the numbers in ascending order. consider the following reserved words of SPARKS. - case, do , else, end, endcase, endif ,if loop, procedure, repeat, return, then, while. Application of Binary Trees (Contd..) : 34 Application of Binary Trees (Contd..) A BST formed from the above words is as follows : The in order traversal : i) LChild ii) Root iii) RChild procedure repeat loop then return while if else End case End if end case do Figure 29-1 Application of Binary Trees (Contd..) : 35 Application of Binary Trees (Contd..) The in-order traversal of BST gives case, do, else, end, endcase, endif, if, loop, procedure, repeat, return, then, while. To check whether than is a reserved word, first than is compared with root if. since if, is less than ‘than’ right tree is searched. Proceeding like this we can conclude that than is not a reserved word. Application of Binary Trees (Contd..) : 36 Application of Binary Trees (Contd..) The linked representation of fig 29-1 is as follows array of reserved word. Address Lchild Data Rchild Address Lchild Data Rchild Application of Binary Trees (Contd..) : 37 Application of Binary Trees (Contd..) If else repeat case endcase The data field contains the index into the array of reserved words. Lchild and Rchild contain node addresses Consider the first node. 7 is the index of the data if 2 is the address of else whose index is 3 3 is the address of repeat whose index is 10 Application of Binary Trees (Contd..) : 38 Application of Binary Trees (Contd..) Array of reserved words Name (1) case 2 do 3 else 7 if 10 repeat 11 return 12 then 13 while K-ary Trees A node in a K-ary tree may have at most K-children and these are ordered. Conversion of tree into binary tree : 39 Conversion of tree into binary tree Any tree can be transformed into a binary tree converting a tree T with root T1 and sub-trees T11, T12,.. T1k. Make T1 the root of a binary tree. T11 the left child of T1 and T1i becomes right child of T1 i -1 for 2 ? i ? k. Conversion of tree into binary tree : 40 Conversion of tree into binary tree T11 T12 T11 T12 TIK T13 Tree T1K Binary Tree T1 T1 Conversion of tree into binary tree : 41 Conversion of tree into binary tree Tree Binary Tree A C B E F G D H I J A B E F C G D H I J

Add a comment

Related presentations

Related pages

Course: CS201: Elementary Data Structures - Saylor

When we use programming for problem-solving purposes, data must be stored in certain forms, or Data Structures, so that operations on that data will yield ...
Read more

Elementary Data Structures 2 - Algorithm Design

Elementary Data Structures Stacks, Queues, & Lists Amortized analysis Trees Elementary Data Structures 2 The Stack ADT (§2.1.1) The Stack ADT stores
Read more

Elementary Data Structures - UW Courses Web Server

4 Elementary Data Structures v1.4 10 Applications of Vectors Direct applications Sorted collection of objects (elementary database) Indirect applications
Read more

Elementary Data Structures | Engineer_Ankit - Sellfy.com

In this assignment, you will apply data structures in an OOPprogram. Write the following programs: Elementary Data Structures Suppose youcreated a video ...
Read more

CHAPTER 11: ELEMENTARY DATA STRUCTURES - USTC

CHAPTER 11: ELEMENTARY DATA STRUCTURES. In this chapter, we examine the representation of dynamic sets by simple data structures that use pointers.
Read more

Elementary Data Structures download | SourceForge.net

Elementary Data Structures download. Elementary Data Structures 2013-03-11 19:16:32 free download. Elementary Data Structures I've created c++ library ...
Read more

Elementary Data Structures - Utah State University

Elementary Data Structures Stacks, Queues, & Lists Amortized analysis Trees The Stack ADT (§2.1.1) The Stack ADT (Abstract Data Type) stores arbitrary ...
Read more

Course: CS201: Elementary Data Structures, Topic: Course ...

When we use programming for problem-solving purposes, data must be stored in certain forms, or Data Structures, so that operations on that data will yield ...
Read more

Elementary Data Types (Visual Basic) - msdn.microsoft.com

Note ; Every elementary data type in Visual Basic is supported by a structure or a class that is in the System namespace. The compiler uses each data type ...
Read more

Course: CS201: Elementary Data Structures, Topic: Unit 1 ...

This unit will introduce students to Abstract Data Types and will make the important distinction between an Abstract Data Type and a Data Structure.
Read more