CPP253 - Data Structures PDF

CPP253 Data Structures Introduction to Data Structures Öğr. Gör. İhsan Can İÇİUYAN  2 CPP253 – Data Structures Contents  Basic Terminology  Data Structure Organization  Classification of Data Structures ...

CPP253 Data Structures Introduction to Data Structures Öğr. Gör. İhsan Can İÇİUYAN  2 CPP253 – Data Structures Contents  Basic Terminology  Data Structure Organization  Classification of Data Structures  Arrays  Linked Lists  Stacks  Queues  Trees  Graphs  Operations on Data Structures  Abstract Data Type (ADT)  3 CPP253 – Data Structures Basic Terminology  A good program is defined as a program that  runs correctly  is easy to read and understand  is easy to debug  is easy to modify  Program → correct results + efficient run-time  In order to write efficient programs we need to apply certain data management concepts.  4 CPP253 – Data Structures Basic Terminology  The concept of data management is a complex task that includes activities like  data collection  organization of data into appropriate structures  developing and maintaining routines for quality assurance  A data structure is basically a group of data elements that are put together under one name, and which defines a particular way of storing and organizing data in a computer so that it can be used efficiently.  5 CPP253 – Data Structures Basic Terminology  Data structures are widely applied in the following areas:  Compiler design  Operating system  Statistical analysis package  DBMS  Numerical analysis  Simulation  Artificial intelligence  Graphics  The primary goal of a program or software is not to perform calculations or operations but to store and retrieve information as fast as possible.  6 CPP253 – Data Structures Basic Terminology  When selecting a data structure to solve a problem, the following steps must be performed: 1. Analysis of the problem to determine the basic operations that must be supported. For example, basic operation may include inserting/deleting/searching a data item from the data structure. 2. Quantify the resource constraints for each operation. 3. Select the data structure that best meets these requirements. Data-centred view of the design process  7 CPP253 – Data Structures Basic Terminology  3 step process 1. Data + Operations on them 2. Representation of the data 3. Implementation  Adding new data items → Only at the beginning? Any position?  Accessing data items → Sequentially? Randomly?  Selection of an appropriate data structure for the problem is a crucial decision and may have a major impact on the performance of the program.  8 CPP253 – Data Structures Data Structure Organization  Data → a value or set of values  value of a variable or constant  marks of students, name of an employee, address of a customer, value of pi, etc.  Record → collection of data items  name + address + course + marks  File → collection of related records  A file of all students in a class, employees in an organization, all the customers of a company, etc.  Primary key, K → unique data item for each record in a file  student number, employee id, etc.  9 CPP253 – Data Structures Classification of Data Structures  10 CPP253 – Data Structures Classification of Data Structures  Primitive data structures → fundamental data types supported by the programming language  integer, float, character, boolean  data type, basic data type, primitive data type  Non-primitive data structures → created using primitive data structures  arrays, linked lists, stacks, trees, graphs, etc.  two categories: linear and non-linear  11 CPP253 – Data Structures Classification of Data Structures  Linear data structure → elements are stored in a linear or sequential order  arrays, linked lists, stacks, queues  two different representation in memory:  sequential memory locations  links  Non-linear data structure → elements are not stored in a sequential order  trees, graphs  12 CPP253 – Data Structures Arrays  Array → collection of similar data elements  Elements  have the same data type.  are stored in consecutive memory locations.  are referenced by an index.  In C, arrays are declared using the following syntax: type name[size];  13 CPP253 – Data Structures Arrays  For example int marks;  An array named marks containing 10 elements.  The array index starts from zero.  In the memory, the array will be stored as below:  14 CPP253 – Data Structures Arrays  Arrays are generally used when we want to store large amount of similar type of data.  They have some limitations:  Arrays are of fixed size.  Data elements are stored in consecutive memory locations which may not be always available.  Insertion and deletion of elements can be problematic because of shifting of elements from their positions.  Possible solutions: dynamic arrays (using pointers), linked lists  15 CPP253 – Data Structures Linked Lists  Linked list → very flexible, dynamic data structure in which elements (called nodes) form a sequential list  No fixed size like arrays.  Each node is allocated space as it is added to the list.  Every node in the list points to the next node in the list.  Every node contains the following two types of data:  The value of the node  A pointer or link to the next node in the list  16 CPP253 – Data Structures Linked Lists  The last node in the list contains a NULL pointer (end or tail of the lists)  An example of linked list of seven nodes:  Advantage: Easier to insert or delete data elements.  Disadvantage: Slow search operation and requires more memory space  17 CPP253 – Data Structures Stacks  Stack → linear data structure in which insertion and deletion of elements are done at only one end (top of the stack)  Last-in, first-out (LIFO) structure  Can be implemented using arrays or linked lists  An array implementation of a stack (top = 4):  18 CPP253 – Data Structures Stacks  top → the address of the topmost element of the stack. Elements will be added at or deleted from this position.  MAX → the maximum number of elements that the stack can store.  top = NULL or -1 → Stack is empty  top = MAX – 1 → Stack is full  19 CPP253 – Data Structures Stacks  Supports three operations:  push → adds an element to the top of the stack  pop → removes the element from the top of the stack  peek → returns the value of the topmost element of the stack (without deleting it)  Before inserting an element → check for overflow (full stack)  Before deleting an element → check for underflow (empty stack)  20 CPP253 – Data Structures Queues  Queue → linear data structure in which the element that is inserted first is the first one to be taken out  First-in, first-out (FIFO) structure  Can be implemented using arrays or linked lists  An array implementation of a queue (front = 0, rear = 5):  21 CPP253 – Data Structures Queues  front → the position from where deletions can be done  rear → the position from where insertions can be done  MAX → the maximum number of elements in the queue  rear = MAX – 1 → Queue is full  front = NULL and rear = NULL → Queue is empty  22 CPP253 – Data Structures Queues  Adding an element to the queue (front = 0, rear = 6):  Deleting an element from the queue (front = 1, rear = 6):  Before inserting an element → check for overflow (full queue)  Before deleting an element → check for underflow (empty queue)  23 CPP253 – Data Structures Trees  Tree → non-linear data structure which consists of a collection of nodes arranged in a hierarchical order  One of the nodes is designated as the root node.  The remaining nodes can be partitioned into disjoint sets such that each set is a sub-tree of the root.  24 CPP253 – Data Structures Trees  The simplest form of a tree → binary tree  A binary tree consists of a root node and left and right sub-trees, where both sub-trees are also binary trees.  Each node contains:  a data element  a left pointer which points to the left sub-tree  a right pointer which points to the right sub-tree  root element → topmost node which is pointed by a root pointer  root = NULL → Tree is empty  25 CPP253 – Data Structures Trees  An example of a binary tree:  R → root, T1 → left sub-tree, T2 → right sub-tree  Node 2 → left child of root, node 3 → right child of root  Advantage: Provides quick search, insert, and delete operations  Disadvantage: Complicated deletion algorithm  26 CPP253 – Data Structures Graphs  Graph → non-linear data structure which is a collection of vertices (also called nodes) and edges that connect these vertices  Graph → generalization of the tree structure  Tree → parent-child relationship  Graph → complex relationships  An example of a graph with five nodes:  27 CPP253 – Data Structures Graphs  Examples:  Cities as nodes, roads as edges  Workstations as nodes, network connections as edges  No root node!  Two nodes connected via an edge → neighbours  Advantage: Best models real-world situations  Disadvantage: Some algorithms are slow and very complex  28 CPP253 – Data Structures Data Structures  29 CPP253 – Data Structures Operations on Data Structures  Traversing → to access each data item exactly once so that it can be processed  printing the names of all the students in a class  Searching → to find the location of one or more data items that satisfy the given constraint  finding the names of all the students who secured 100 marks in mathematics  Inserting → to add new data items to the given list of data items  adding the details of a new student who has recently joined the course  Deleting → to remove (delete) a particular data item from the given collection of data items  deleting the name of a student who has left the course  30 CPP253 – Data Structures Operations on Data Structures  Sorting → to arrange in some order like ascending order or descending order  arranging the names of students in a class in an alphabetical order  Merging → to combine lists of two sorted data to form a single list of sorted data items  31 CPP253 – Data Structures Abstract Data Type  Abstract Data Type (ADT) → the way we look at a data structure  focusing on what it does  ignoring how it does its job  Mathematical description of an object with set of operations on the object  The end-user is not concerned about the details of how the methods carry out their tasks.  They are only aware of the methods that are available to them.  Stack → push() and pop() functions, but can be implemented using arrays or linked lists  32 CPP253 – Data Structures Data Structures  33 CPP253 – Data Structures References  https://en.wikipedia.org/wiki/Data_structure  https://www.geeksforgeeks.org/data-structures/  https://www.tutorialspoint.com/data_structures_algorithms/index.ht m  https://www.programiz.com/dsa/data-structure-types  https://levelup.gitconnected.com/data-structures-overview- 13ac8a02a880  https://youtu.be/DuDz6B4cqVc  34 CPP253 – Data Structures That’s all for today!