Types of Data Structure with examples

explain the different categories of data structure with example, types of data structures and their applications and types of data structure with examples pdf free download
ImogenCameron Profile Pic
ImogenCameron,France,Teacher
Published Date:14-07-2017
Your Website URL(Optional)
Comment
Computer College, Department of Computer Science, Kingdom of Saudi Arabia  INSTRUCTOR: Shahid Iqbal Lone e_mail: loneshahidyahoo.com  COURSE BOOK: 1. Tanenbaum Aaron M, Langsam Yedidyah, Augenstein J Moshe, Data Structures using C.  LIST OF REFERENCE MATERIAL: 1. Seymour Lipschutz, Theory and Problems of data Structures, Schaum’s Series, Tata McGraw Hill, 2004. 2. Tremblay J.P and Sorenson P.G, An introduction to data structures with nd applications, Tata McGraw Hill, 2 Edition. 3. Gilberg, F Richard & Forouzan, A Behrouz, Data Structures A Pseudocode approach with C, Thomson Brooks/Cole Publications,1998.  OBJECTIVES: With a dynamic learn-by-doing focus, this document encourages students to explore data structures by implementing them, a process through which students discover how data structures work and how they can be applied. Providing a framework that offers feedback and support, this text challenges students to exercise their creativity in both programming and analysis. Each laboratory work creates an excellent hands-on learning opportunity for students. Students will be expected to write C-language programs, ranging from very short programs to more elaborate systems. Since one of the goals of this course is to teach how to write large, reliable programs. We will be emphasizing the development of clear, modular programs that are easy to read, debug, verify, analyze, and modify.  PRE-REQUISITE: A good knowledge of c-language, use of Function and structures.D A T A S T R U C T U R E S ( CS C-214) Data: Data are simply collection of facts and figures. Data are values or set of values. A data item refers to a single unit of values. Data items that are divided into sub items are group items; those that are not are called elementary items. For example, a student’s name may be divided into three sub items – first name, middle name and last name but the ID of a student would normally be treated as a single item. Student ID Name Address Age Gender First Middle Last Street Area In the above example ( ID, Age, Gender, First, Middle, Last, Street, Area ) are elementary data items, whereas ( Name, Address ) are group data items. An entity is something that has certain attributes or properties which may be assigned values. The values themselves may be either numeric or non-numeric. Example: Attributes: Name Age Gender Social Society number Values: Hamza 20 M 134-24-5533 Ali Rizwan 23 M 234-9988775 Fatima 20 F 345-7766443 Entities with similar attributes ( e.g. all the employees in an organization) form an entity set. Each attribute of an entity set has a range of values, the set of all possible values that could be assigned to the particular attribute. The term “information” is sometimes used for data with given attributes, of, in other words meaningful or processed data. A field is a single elementary unit of information representing an attribute of an entity, a record is the collection of field values of a given entity and a file is the collection of records of the entities in a given entity set. Data Structure: In computer science, a data structure is a particular way of storing and organizing data in a computer’s memory so that it can be used efficiently. Data may be organized in many different ways; the logical or mathematical model of a particular organization of data is called a data structure. The choice of a particular data model depends on the two considerations first; it must be rich enough in structure to mirror the actual relationships of the data in the real world. On the other hand, the structure should be simple enough that one can effectively process the data whenever necessary. 2 Shahid Iqbal (L ecturer) C omputer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S (CS C-214) Categories of Data Structure: The data structure can be classified in to major types:  Linear Data Structure  Non-linear Data Structure 1. Linear Data Structure: A data structure is said to be linear if its elements form any sequence. There are basically two ways of representing such linear structure in memory. a) One way is to have the linear relationships between the elements represented by means of sequential memory location. These linear structures are called arrays. b) The other way is to have the linear relationship between the elements represented by means of pointers or links. These linear structures are called linked lists. The common examples of linear data structure are  Arrays  Queues  Stacks  Linked lists 2. Non-linear Data Structure: This structure is mainly used to represent data containing a hierarchical relationship between elements. e.g. graphs, family trees and table of contents. Arrays: The simplest type of data structure is a linear ( or one dimensional) array. A list of a finite number n of similar data referenced respectively by a set of n consecutive numbers, usually 1, 2, 3 . . . . . . . n. if we choose the name A for the array, then the elements of A are denoted by subscript notation A , A , A . . . . A 1 2 3 n or by the parenthesis notation A (1) , A ( 2), A ( 3) . . . . . . A ( n) or by the bracket notation A 1, A 2, A 3 . . . . . . A n Example: A linear array A8 consisting of numbers is pictured in following figure. Linked List: A linked list, or one way list is a linear collection of data elements, called nodes, where the linear order is given by means of pointers. Each node is divided into two parts:  The first part contains the information of the element/node  The second part contains the address of the next node ( link /next pointer field) in the list. 3 Shahid Iqbal (L ecturer) C omputer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) There is a special pointer Start/List contains the address of first node in the list. If this special pointer contains null, means that List is empty. Example: Tree: Data frequently contain a hierarchical relationship between various elements. The data structure which reflects this relationship is called a rooted tree graph or, simply, a tree. Student ID Name Address Age Gender First Middle Last Street Area Graph: Data sometimes contains a relationship between pairs of elements which is not necessarily hierarchical in nature, e.g. an airline flights only between the cities connected by lines. This data structure is called Graph. Queue: A queue, also called FIFO system, is a linear list in which deletions can take place only at one end of the list, the Font of the list and insertion can take place only at the other end Rear. Stack: It is an ordered group of homogeneous items of elements. Elements are added to and removed from the top of the stack ( the most recently added items are at the top of the stack). The last element to be added is the first to be removed (LIFO: Last In, First Out) . Data Structures Operations: The data appearing in our data structures are processed by means of certain operations. In fact, the particular data structure that one chooses for a given situation depends largely in the frequency with which specific operations are performed. The following four operations play a major role in this text: 4 Shahid Iqbal (L ecturer) C omputer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214)  Traversing: accessing each record/node exactly once so that certain items in the record may be processed. ( This accessing and processing is sometimes called “visiting” the record.)  Searching: Finding the location of the desired node with a given key value, or finding the locations of all such nodes which satisfy one or more conditions.  Inserting: Adding a new node/record to the structure.  Deleting: Removing a node/record from the structure. 5 Shahid Iqbal (L ecturer) C omputer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) 6 Shahid Iqbal (L ecturer) C omputer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S (CS C-214) Decleration of the Arrays: Any array declaration contains: the array name, the element type and the array size. Examples: int a20, b3,c7; float f5, c2; char m4, n20; Initialization of an array is the process of assigning initial values. Typically declaration and initialization are combined. Examples: float, b3=2.0, 5.5, 3.14; char name4= ‘E’,’m’,’r’,’e’; int c10=0; 7 Shahid Iqbal (L ecturer) C omputer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) 8 Shahid Iqbal (L ecturer) C omputer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) Dynamic Arrays Dynamic array allocation is actually a combination of pointers and dynamic memory allocation. Whereas static arrays are declared prior to runtime and are reserved in stack memory, dynamic arrays are created in the heap using the new and released from the heap using delete operators. Start by declaring a pointer to whatever data type you want the array to hold. In this case I've used int : int my_array; This C++ statement simply declares an integer pointer. Remember, a pointer is a variable that holds a memory address. Declaring a pointer doesn't reserve any memory for the array - that will be accomplished with new. The following C++ statement requests 10 integer-sized elements be reserved in the heap with the first element address being assigned to the pointer my_array: my_array = new int10; The new operator is requesting 10 integer elements from the heap. There is a possibility that there might not be enough memory left in the heap, in which case your program would have to properly 9 Shahid Iqbal (L ecturer) C omputer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S (CS C-214) handle such an error. Assuming everything went OK, you could then use the dynamically declared array just like the static array. Dynamic array allocation is nice because the size of the array can be determined at runtime and then used with the new operator to reserve the space in the heap. To illustrate I'll uses dynamic array allocation to set the size of its array at runtime. // array allocation to set the size of its array at runtime. include iostream.h int main () int i,n; int p; cout "How many numbers would you like to type? "; cin i; p= new inti; // it takes memory at run-time from Heap if (p == NULL) cout "Error: memory could not be allocated"; else for (n=0; ni; n++) cout "Enter number: "; cin pn; int k=p; // to hold the base address of dynamic array cout "You have entered: \ n"; for (n=0; ni; n++) cout k ", "; k++; cout"\ n"; delete p; // it release the memory to send it back to Heap return 0; 10 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) Operations on array 1- Traversing: means to visit all the elements of the array in an operation is called traversing. 2- Insertion: means to put values into an array 3- Deletion / Remove: to delete a value from an array. 4- Sorting: Re-arrangement of values in an array in a specific order (Ascending / Descending) is called sorting. 5- Searching: The process of finding the location of a particular element in an array is called searching. There are two popular searching techniques/mechanisms : Linear search and binary search and will be discussed later. a) Traversing in Linear Array: It means processing or visiting each element in the array exactly once; Let ‘A’ is an array stored in the computer’s memory. If we want to display the contents of ‘A’, it has to be traversed i.e. by accessing and processing each element of ‘A’ exactly once. Algorithm: ( Traverse a Linear Array) 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. 1. Initialize counter. Set K=LB. 2. Repeat Steps 3 and 4 while K≤UB. 3. Visit element. Apply PROCESS to LAK. 4. Increase counter. Set k=K+1. End of Step 2 loop. 5. Exit. The alternate algorithm for traversing (using for loop) is : Algorithm: (Traverse a Linear Array) This algorithm traverse a linear array LA with lower bound LB and upper bound UB. 1. Repeat for K=LB to UB Apply PROCESS to LAK. End of loop. 2. Exit. This program will traverse each element of the array to calculate the sum and then calculate & print the average of the following array of integers. ( 4, 3, 7, -1, 7, 2, 0, 4, 2, 13) include iostream.h define size 10 // another way int const size = 10 int main( ) int x10=4,3,7,-1,7,2,0,4,2,13, i, sum=0,LB=0, UB=size; float av; for( i=LB,iUB;i++) sum = sum + xi; av = (float) sum/size; cout “The average of the numbers= “avendl; return 0; 11 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) b) Sorting in Linear Array: Sorting an array is the ordering the array elements in ascending (increasing - from min to max) or descending (decreasing – from max to min) order. Example: 2 1 5 7 4 31, 2, 3, 4, 5,7 ascending order 2 1 5 7 4 37,5, 4, 3, 2, 1 descending order Bubble Sort: The technique we use is called “Bubble Sort” because the bigger value gradually bubbles their way up to the top of array like air bubble rising in water, while the small values sink to the bottom of array. This technique is to make several passes through the array. On each pass, successive pairs of elements are compared. If a pair is in increasing order (or the values are identical), we leave the values as they are. If a pair is in decreasing order, their values are swapped in the array. B u b b le S o r t P a s s = 1 P a s s = 2 P a s s = 3 P a s s = 4 2 1 5 7 4 3 1 2 5 4 3 7 1 2 4 3 5 7 1 2 3 4 5 7 1 2 5 7 4 3 1 2 5 4 3 7 1 2 4 3 5 7 1 2 3 4 5 7 1 2 5 7 4 3 1 2 5 4 3 7 1 2 4 3 5 7 1 2 3 4 5 7 1 2 5 7 4 3 1 2 4 5 3 7 1 2 3 4 5 7 1 2 5 4 7 3 1 2 4 3 5 7 1 2 5 4 3 7  U n d e rlin e d p a irs s h o w th e c o m p a ris o n s . F o r e a c h p a s s th e re a re s ize -1 c o m p a ris o n s. 2  To ta l n u m b e r o f c o m p a ris o n s= ( s ize -1 ) Algorithm: ( Bubble Sort) BUBBLE (DATA, N) Here DATA is an Array with N elements. This algorithm sorts the elements in DATA. 1. for pass=1 to N-1. 2. for ( i=0; i= N-Pass; i++) 3. If DATAiDATAi+1, then: Interchange DATAi and DATAi+1. End of If Structure. End of inner loop. End of Step 1 outer loop. 4. Exit. 12 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) / This program sorts the array elements in the ascending order using bubble sort method / include iostream.h int const SIZE = 6 void BubbleSort(int , int); int main( ) int aSIZE= 77,42,35,12,101,6; int i; cout “The elements of the array before sorting\ n”; for (i=0; i= SIZE-1; i++) cout ai”, “; BubbleSort(a, SIZE); cout “\ n\ nThe elements of the array after sorting\ n”; for (i=0; i= SIZE-1; i++) cout ai”, “; return 0; void BubbleSort( int A , int N) int i, pass, hold; for (pass=1; pass= N-1; pass++) for ( i=0; i= SIZE-pass; i++) if( Ai Ai+1) hold =Ai; Ai=Ai+1; Ai+1=hold; Home Work Write a program to determine the median of the array given below: (9 , 4, 5, 1, 7, 78, 22, 15, 96, 45,25) Note that the median of an array is the middle element of a sorted array. 13 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S (CS C-214) Searching in Linear Array: The process of finding a particular element of an array is called Searching”. If the item is not present in the array, then the search is unsuccessful. There are two types of search (Linear search and Binary Search) Linear Search: The linear search compares each element of the array with the search key until the search key is found. To determine that a value is not in the array, the program must compare the search key to every element in the array. It is also called “Sequential Search” because it traverses the data sequentially to locate the element. Algorithm: (Linear Search) LINEAR (A, SKEY) Here A is a Linear Array with N elements and SKEY is a given item of information to search. This algorithm finds the location of SKEY in A and if successful, it returns its location otherwise it returns -1 for unsuccessful. 1. Repeat for i = 0 to N-1 2. if( Ai = SKEY) return i Successful Search End of loop 3. return -1 Un-Successful 4. Exit. / This program use linear search in an array to find the LOCATION of the given Key value / / This program is an example of the Linear Search/ include iostream.h int const N=10; int LinearSearch(int , int) ; // Function Prototyping int main( ) int AN= 9, 4, 5, 1, 7, 78, 22, 15, 96, 45, Skey, LOC; cout“ Enter the Search Key\n”; cinSkey; LOC = LinearSearch( A, Skey) ; // call a function if( LOC == -1) cout” The search key is not in the array\n Un-Successful Search\ n”; else cout” The search key “Skey “ is at location ”LOCendl; return 0; int LinearSearch ( int b , int skey) // function definition int i; for ( i=0; i= N-1; i++) if( bi == skey) return i; return -1; 14 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S (CS C-214) Binary Search: It is useful for the large sorted arrays. The binary search algorithm can only be used with sorted array and eliminates one half of the elements in the array being searched after each comparison. The algorithm locates the middle element of the array and compares it to the search key. If they are equal, the search key is found and array subscript of that element is returned. Otherwise the problem is reduced to searching one half of the array. If the search key is less than the middle element of array, the first half of the array is searched. If the search key is not the middle element of in the specified sub array, the algorithm is repeated on one quarter of the original array. The search continues until the sub array consist of one element that is equal to the search key (search successful) . But if Search-key not found in the array then the value of END of new selected range will be less than the START of new selected range. This will be explained in the following example: Binary Search Search-Key = 22 Search-Key = 8 Start=0 Start=0 A0 3 End = 9 A0 3 End = 9 Mid=int(S tart+End) / 2 Mid=int(S tart+End) / 2 A1 5 Mid= int ( 0 +9)/ 2 A1 Mid= int ( 0 +9)/ 2 5 Mid=4 Mid=4 A2 _________________ 9 A2 _________________ 9 Start=4+1 = 5 A3 11 Start=0 A3 11 End = 9 End = 3 Mid=int(5 +9)/ 2 = 7 A4 Mid=int( 0 +3) / 2 = 1 15 A4 _________________ 15 _________________ A5 17 A5 Start = 5 17 Start = 1+1 = 2 End = 7 – 1 = 6 End = 3 A6 22 Mid = int( 5 +6)/ 2 =5 A6 22 Mid = int(2 +3)/ 2 =2 _________________ _________________ A7 25 A7 25 Start = 5+1 = 6 Start = 2 A8 End = 6 37 A8 End = 2 – 1 = 1 37 Mid = int(6 + 6) / 2 = 6 A9 68 End is Start A9 68 Found at location 6 Un-Successful Search Successful Search 15 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) Algorithm: ( Binary Search) Here A is a sorted Linear Array with N elements and SKEY is a given item of information to search. This algorithm finds the location of SKEY in A and if successful, it returns its location otherwise it returns -1 for unsuccessful. BinarySearch ( A, SKEY) 1. Initialize segment variables. Set START=0, END=N-1 and MID=INT(( START+END) /2) . 2. Repeat Steps 3 and 4 while START ≤ END and AMID≠SKEY. 3. If SKEY AMID. Then Set END=MID-1. Else Set START=MID+1. End of If Structure. 4. Set MID=INT( (START +END) /2) . End of Step 2 loop. 5. If AMID= SKEY then Set LOC= MID Else: Set LOC = -1 End of IF structure. 6. return LOC and Exit // C++ Code for Binary Search include iostream.h int const N=10; int BinarySearch( int , int) ; // Function Prototyping int main( ) int AN= 3, 5, 9, 11, 15, 17, 22, 25, 37, 68, SKEY, LOC; cout” Enter the Search Key\ n ”; cinSKEY) ; LOC = BinarySearch(A, SKEY) ; // Function call if( LOC == -1) cout” The search key is not in the array\n”; else cout” The search key “SKEY “ is at location “LOCendl; return 0; int BinarySearch (int A, int skey) int START=0, END= N-1, MID=int( (START+END)/2), LOC; while( START = END && AMID = skey) if(skey AMID) END = MID - 1; Else START = MID + 1; MID=int( (START+END)/2) If( AMID == skey) LOC=MID else LOC= -1; return LOC; 16 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S ( CS C-214) Computational Complexity of Binary Search The Computational Complexity of the Binary Search algorithm is measured by the maximum (worst case) number of Comparisons it performs for searching operations. The searched array is divided by 2 for each comparison/iteration. Therefore, the maximum number of comparisons is measured by: log2( n) where n is the size of the array Example: If a given sorted array 1024 elements, then the maximum number of comparisons required is: log2( 1024) = 10 ( only 10 comparisons are enough) Computational Complexity of Linear Search Note that the Computational Complexity of the Linear Search is the maximum number of comparisons you need to search the array. As you are visiting all the array elements in the worst case, then, the number of comparisons required is: n (n is the size of the array) Example: If a given an array of 1024 elements, then the maximum number of comparisons required is: n-1 = 1023 (As many as 1023 comparisons may be required) 17 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S (CS C-214) Structures A structure is a collection of logically related variables under a single unit/name. These variables can be of different types, and each has a name which is used to select it from the structure. A structure is a convenient way of grouping several pieces of related information together. They are most commonly used for record-oriented data. Example: How to declare a structure struct Rectangle // this is type/name for structure float Length; float width; float area; ; NOTE: declaration of structure does not occupy space in memory. One has to create the variables for the struct and variable will take spaces in memory. For example: Following instruction will Following instruction will just occupy space and also occupy space initialize members. Struct Rectangle Rect; Struct Rectangle Rect=10, 8, 0; Rect Rect Length Length 10 Width Width 8 Area Area 0 Here is an other example of structure declaration. struct Student char name20; char course30; int age; int year; ; struct Student S1; // Here s1 is a variable of Student type and has four members. A structure is usually declared before main( ) function. In such cases the structure assumes global status and all the functions can access the structure. The members themselves are not variables they should be linked to structure variables in order to make 18 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S (CS C-214) them meaningful members. The link between a member and a variable is established using the membership operator ‘.’ Which is also known as dot / membership operator. For example: strcpy(S 1.name, “Nazir Hussain”) ; strcpy(S 1.course, “CS-214 Data Structures”) ; S1.age = 21; S1.year = 1989; Note: following is the work to do in the Lab. 1- Run this program and examine its behavior. In the following program you will see the way to initialize the structure variables. include iostream.h include conio.h include iomanip.h struct student int ID; // 4 bytes char name10; // 10 bytes float grade; // 4 bytes int age; // 4 char phone10; // 10 char e_mail16; // 16 ; // Prototyping of the functions void display(struct student); void main() struct student s1=55,"Amir Ali",3.5f,23,"6535418","amiryahoo.com"; struct student s2=26,"Mujahid",2.9888f,25,"5362169", "mujhotmail.com"; struct student s3=39,"M Jamil",3.108f,30,"2345677","jamhotmail.com"; struct student s4=44,"Dilawar",2.7866f,31,"5432186","dilhotmail.com"; struct student s5=59,"S.Naveed",2.9f,27,"2345671","naveeyahoo.com"; cout" Students Records Sheet\ n"; cout" \ n\ n"; cout"ID NAME GRADE AGE PHONE E-MAIL\ n"; cout" \ n"; display(s1); // structure pass to function display(s2); // structure pass to function display(s3); display(s4); display(s5); void display(struct student s) coutsetw(3) s.ID setw(12) s.name setw(8) setiosflags ( ios::showpoint)setprecision(2) s.gradesetw(5) s.age setw(10) s.phone setw(18)s.e_mailendl; 19 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi ArabiaD A T A S T R U C T U R E S (CS C-214) 2- Run this program and examine its behavior. // In this program you will see the structures (members Manipulation), // Passing structures to functions: include iostream.h include iomanip.h struct STU_GRADES char name 30; int exam1; int exam2; int exam3; int final; float sem_ave; char letter_grade; ; //inputs the data items for a student, structure //is passed by reference struct STU_GRADES get_stu ( ) struct STU_GRADES student; cout "\n\n\n\ n Enter the information for a student\n"; cout " Name: "; cin.getline (student.name, 30, '\n'); cout " Exam1: "; cin student.exam1; cout " Exam2: "; cin student.exam2; cout "exam3: "; cin student.exam3; cout "final: "; cin student.final; return student; //displays a student's info. //structure is passed by value void print_stu (struct STU_GRADES stu) cout "\ n\n\ nGrade report for: " stu.nameendl; cout "\ nexam 1\texam 2\texam 3\tfinal\ n"; cout stu.exam1 "\t" stu.exam2 "\t" stu.exam3 "\ t" stu.final; cout "\n\ n\ nsemester average: " setiosflags (ios::fixed) setprecision (2) stu.sem_ave; cout "\nsemester grade: " stu.letter_grade; float calc_ave (int ex1, int ex2, int ex3, int final) float ave; ave = float (ex1 + ex2 + ex3 + final)/4.0f; return ave; 20 Shahid Iqbal (L ecturer) Computer College Qassim University Kingdom of Saudi Arabia