DSA # 2 Array.pdf

9/28/2017 Data Structure & Algorithms Muzammil Khan Department of Computer & Software Technology University of Swat 1 Chapter 2...

9/28/2017 Data Structure & Algorithms Muzammil Khan Department of Computer & Software Technology University of Swat 1 Chapter 2 Data Structure “Array” Data Structure & Algorithms 2 1  9/28/2017 Array  Array is A container which can hold a fix number of items These items should be of the same type Most of the data structures make use of arrays to implement their algorithms  Following are the important terms to understand the concept of Array.  Element Each item stored in an array is called an element.  Index Each location of an element in an array has a numerical index, which is used to identify the element. Data Structure & Algorithms 3 Array Representation  Arrays can be declared in various ways in different languages  For illustration, let's take C array declaration. Memory representation Each element can be accessed via its index i.e. array Each element has it binary memory address Data Structure & Algorithms 4 2  9/28/2017 Basic Operations on Array  Following are the basic operations supported by an array  Traverse Prints all the array elements one by one  Insertion Adds an element at the given index  Deletion Deletes an element at the given index  Search Searches an element using the given index or by the value  Update Updates an element at the given index Data Structure & Algorithms 5 Traverse a “Linear Array”  Algorithm’s Description Here LA is a Linear array with lower boundary LB and upper boundary UB. This algorithm traverses LA applying an operation Process to each element of LA.  Algorithm’s Statements Step 1. [Initialize counter.] Set K=LB. Repeat Steps 2 and 4 Step 2. while K≤UB. then Step 3. [Visit element.] Apply PROCESS to LA[K]. Step 4. [Increase counter.] Set k=K+1. [End of Step 2 loop.] Step 5. Exit Data Structure & Algorithms 6 3  9/28/2017 Traverse a “Linear Array” (Cont…)  An alternative algorithm of the previous one  Algorithm’s Description Here LA is a Linear array with lower boundary LB and upper boundary UB. This algorithm traverses LA applying an operation Process to each element of LA.  Algorithm’s Statements Step 1. Repeat for K=LB to UB. Apply PROCESS to LA[K] [End of loop]. Step 2. Exit Data Structure & Algorithms 7 Search in Array  Algorithm’s Description Here LA is a Linear Array with N elements and KEY is a given item of information to search. This algorithm finds the location of KEY in LA if successful, otherwise it returns unsuccessful  Algorithm’s Statements LINEAR_SEARCH (LA, KEY) Step 1. Repeat for i = 0 to N-1 Step 2. if( LA[i] = KEY) return i [Successful Search] Exit Step 3. Return [Un-Successful search] Exit Data Structure & Algorithms 8 4  9/28/2017 Insertion in Array  Based on the requirement A new element can be added at the beginning, end, or any given index of array  Algorithm’s Description Here LA is a Linear Array (unordered) with N elements and K is a counter variable such that K= K Step 4. Set LA[J+1] = LA[J] Step 5. Set J = J-1 Step 6. Set LA[K] = ITEM Exit  Class Task Design algorithms for the following  Insertion of item at the beginning of the Linear Array  Insertion of item at the end of Linear Array Data Structure & Algorithms 10 5  9/28/2017 End of Chapter  You can design many algorithms with Array For example,  Sorting algorithms etc.  Simple algorithms with different requirements or conditions  Etc...  You may have quiz next week Data Structure & Algorithms 11 6