Data structure lec 1,2 .pdf

New Mansoura University Faculty of Computer Science and Engineering CSE-111 Data Structure Module 01: Lecture 01 Objectives Learn Abstract Data Type (ADT), and Data Structure. List Types of Data Structure, Definition, and Operations. Learn create and manipulate Arrays. Learn Algorithm...

New Mansoura University Faculty of Computer Science and Engineering CSE-111 Data Structure Module 01: Lecture 01 Objectives Learn Abstract Data Type (ADT), and Data Structure. List Types of Data Structure, Definition, and Operations. Learn create and manipulate Arrays. Learn Algorithm Basics, and Trace. 2 References Main Textbook Data Structure and Algorithms Extra Resources Using C++: A Practical 1. Moodle by NMU online Platform, Implementation. Online 2. Classroom by Microsoft Teams, Alternative Book 3. Lecture Notes, 4. YouTube, Data Structure Programming With 5. Online Courses. the Standard Template Library in C++. Online 3 Introduction to Data Structure Data structure is a Specific way to store and organize data in a computer's memory so that these data can be used efficiently later. Data may be arranged in different ways such as the logical or mathematical model for a particular organization of data. 4 Introduction to Data Structure The variety of a particular data model depends on the two factors: 1. It must be loaded enough in structure to reflect the actual relationships of the data with the real-world object. 2. The formation should be simple enough so that anyone can efficiently process the data each time it is necessary. The data structure type can be Linear or Non-linear Data Structure. 5 Linear Data Structure A data structure is said to be linear if its elements combine to form any specific order. There are basically two techniques of representing within memory: 1. Provide the linear relationships among all the elements represented by means of linear memory location; e.g. Arrays. 2. Provide the linear relationship among all the elements represented by using the concept of pointers or links; e.g. Linked List common examples: Arrays, Queues, Stacks, Linked Lists 6 Non-Linear Data Structure A data structure is mostly used for representing data that contains a hierarchical relationship among various elements. Common examples: Graphs, Trees, Table of contents 7 Common Data Structure Tree: In this case, data often contain a hierarchical relationship among various elements. The data structure that reflects this relationship is termed as rooted tree graph or a tree. Graph: In this case, data sometimes hold a relationship between the pairs of elements which is not necessarily following the hierarchical structure. Such data structure is termed as a Graph. 8 Common Data Structure Array is a container which can hold a fix number of items and 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. 9 Common Data Structure Following are the basic operations supported by an array: Traverse : print 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. 10 Sparse Matrix A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix. 11 Representation of Sparse Matrix Representing a sparse matrix by a 2D array leads to wastage of lots of memory. So, instead of storing zeroes with non-zero elements, we only store non- zero elements; with triples- (Row, Column, value). Sparse Matrix Representations can be done by: 1. Array representation 2. Linked list representation 12 Representation of Sparse Matrix Why to use Sparse Matrix instead of simple matrix ? Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements. Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements. 13 Abstract Data Type (ADT) The choice of the data structure begins from the choice of an abstract data type (ADT). ADT, is a logical description of how we view the data and the operations that are allowed without regard to how they will be implemented. We are concerned only with what data is representing and not with how it will eventually be constructed. 14 Algorithm for ADT operation(s) A well-designed data structure allows a variety of critical operations (implementing Algorithm) to be performed, using as few resources, both execution time and memory space, as possible. Algorithm has input step, assignment step, decision step, repetitive step, and output step in its structure. Different Approaches to Design an Algorithm: To save time (Time Complexity): A program that runs faster is a better program. To save space (Space Complexity): A program that saves space over a competing program is considerable desirable. 15 Algorithm for ADT operation(s) An algorithm is endowed with the following properties: 1. Finiteness: An algorithm must terminate after a finite number of steps. 2. Definiteness: The steps of the algorithm must be precisely defined or unambiguously specified. 3. Generality: An algorithm must be generic enough to solve all problems of a particular class. 4. Effectiveness: the operations of the algorithm must be basic enough to be put down on pencil and paper. 5. Input-Output: The algorithm must have certain initial and precise inputs, and outputs that may be generated both at its intermediate and final steps. 16 Insertion Operation Insert operation is to insert one ITEM is inserted into the Kth position or more data elements into an array. of LA A new element can be added at the beginning, end, or any given index of the array. Let LA be a Linear Array (unordered) with N elements and K is a positive integer such that K