DSA-Module-2-Intro-to-Data-Structures.pdf
Transcript
Unit 2: Introduction to Data Structures Unit 2 INTRODUCTION TO DATA STRUCTURES Introduction Data structures and algorithms as used in computer programming are ways in which data is arranged in your computer's...
Unit 2: Introduction to Data Structures Unit 2 INTRODUCTION TO DATA STRUCTURES Introduction Data structures and algorithms as used in computer programming are ways in which data is arranged in your computer's memory (or stored on disk). Algorithms are the procedures a software program uses to manipulate the data in these structures. This unit is designed to discuss the basic concepts and terminologies in data structure as well as its hierarchy, structures and uses. In this way, you come to understand better the importance of studying data structures as well as its importance in structured programming. Unit Learning Outcomes At the end of the unit, you will be able to: a. define what a data structure is; b. cite the importance of studying data structures; c. cite the importance of data structures in structured programming; d. enumerate the different types and sub-types of data structures; and e. demonstrate appreciation on the significance of data structure in programming. Topic 1: Data Structures: An Introduction Time Allotment: 3 Hours Learning Objectives At the end of the session, you will be able to: a. define and understand data structures; b. differentiate primitive data type and non-primitive data type; c. differentiate Linear and Non Linear Data Structure; 1 Unit 2: Introduction to Data Structures d. enumerate Data Structure Operations; and e. appreciate the uses and importance of Data Structure in programming. Activating Prior Knowledge What is DATA STRUCTURE? K W L (What You Know) (What You want to (What You Learned and Learn) still Want to Learn) Presentation of Contents What is Data Structure? In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. It is a way in which data are stored for efficient search and retrieval. Efficiency in this context refers to the ability to find and manipulate data quickly and with the minimum consumption of computer and network resources. 2 Unit 2: Introduction to Data Structures A primitive data type is one that fits the base architecture of the underlying computer such as int, float, and pointer, and all of the variations, thereof such as char, short, long, unsigned, float, double, are primitive data type. Primitive data are only single values, they have no special capabilities. Primitive data type are predefined data type. A non-primitive data type is something else such as an array structure or class. Non primitive data type are based on class. it is also called reference data type The non-primitive data types are used to store a group of values. Two Types of Non-Primitive Data Structures Linear Data Structure A data structure is said to be linear if its elements form a sequence or a linear list. 3 Unit 2: Introduction to Data Structures A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. Non-Linear Data Structures Every data item is attached to several other data items in a way that is specific for reflecting relationships. The data items are not arranged in a sequential structure. Difference Between Linear and Non Linear Data Structure Linear Data Structure Non-Linear Data Structure Every item is related to its previous Every item is attached with and next item. many other items. Data is arranged in linear Data is not arranged in sequence. sequence. Data items can be traversed in a Data cannot be traversed in a single run. single run. Implementation is Easy. Implementation is Difficult. Operations on Data Structures Traversal: travel through the data structure Search: traversal through the data structure for a given element Insertion: adding new elements to the data structure Deletion: Removing an element from the data structure Sorting: arranging the elements in some type of order Merging: Combining two similar data structures into one Uses of data structures In general, data structures are used to implement the physical forms of abstract data types(ADT) In computer science, an abstract data type is a mathematical model for data types, where a data type is defined by its behavior from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. 4 Unit 2: Introduction to Data Structures Importance of data structures Data structures are essential for managing large amounts of data, such as information kept in databases or indexing services, efficiently. Proper maintenance of data systems requires the identification of memory allocation, data interrelationships and data processes, all of which data structures help with. Application I. Based on your own understanding, explain briefly what Data Structure is. You can include some examples or situations to support your answer. Write your answer on the space provided. _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ _______________________________________________________________ 5 Unit 2: Introduction to Data Structures II. Using the Venn diagram below, write down the similarities and differences of the Primitive and Non-primitive data types. In the outer part of the circle, write things about them that are different. At the intersection of the circle, write things that are alike. PRIMITIVE DATA TYPE NON-PRIMITIVE DATA TYPE Feedback Instructions: Determine whether the statement is TRUE or FALSE. Write FALSE if the statement is correct, otherwise write TRUE and underline the word that makes the statement false. Write your answer on the space provided. 1. Data structures are used to implement the physical forms of abstract data. ___________ 2. Char, short, long, unsigned, tree and double are examples of primitive data type. ___________ 3. A primitive data type is a mathematical model for data types, where a data type is defined by its behavior from the point of view of a user of the data. ___________ 4. Data structure is a way in which data are stored for efficient search and retrieval. ___________ 5. Traversal: traversal through the data structure for a given element. ___________ 6 Unit 2: Introduction to Data Structures 6. The non-primitive data types are used to store a group of values. ___________ 7. Data structures are essential for managing large amounts of data, such as information kept in databases or indexing services, efficiently. ___________ 8. Primitive data types are predefined data type. ___________ 9. Linear data structure is when data items are not arranged in a sequential structure. ___________ 10. Data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. ___________ REFLECTION Answer briefly the given questions based on your own understanding. Write your answer on the space provided. After knowing the importance and uses of Data Structure, what do you think is the essence of studying Data Structure as an Information Technology/Computer Science Student? What benefit can you derive from it especially in computer programming? 7 Unit 2: Introduction to Data Structures Summary of the Unit Data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. A primitive data type is one that fits the base architecture of the underlying computer such as int, float, and pointer, and all of the variations, thereof such as char, short, long, unsigned, float, double, are primitive data type. A non-primitive data type is something else such as an array structure or class. Linear Data Structure is a data structure that is said to be linear if its elements form a sequence or a linear list. The data elements sequentially, in which only one data element can directly be reached. Non-Linear Data Structures is when every data item is attached to several other data items in a way that is specific for reflecting relationships. The data items are not arranged in a sequential structure. In general, data structures are used to implement the physical forms of abstract data and are essential for managing large amounts of data, such as information kept in databases or indexing services, efficiently. References Data Structures and Algorithms in Java Michael T. Goodrich Department of Computer Science University of California, Irvine 1 Roberto Tamassia Department of Computer Science Brown University 0-471-73884-0 Fourth Edition Retrieved from https://www.geeksforgeeks.org/introduction- to-data-structures-10-most-commonly-used-data-structures/ Retrieved from https://www.w3schools.in/data-structures- tutorial/intro/ 8 Unit 2: Introduction to Data Structures 1. Linear Data Structures 1.1 Arrays In Python, arrays can be implemented using lists: ```python Array (List in Python) array = [10, 20, 30, 40, 50] Accessing elements print("First element:", array) print("Second element:", array) Adding an element to the array array.append(60) print("Array after adding 60:", array) Removing an element from the array array.remove(30) print("Array after removing 30:", array) ``` 1.2 Linked List A simple implementation of a singly linked list: ```python Node class for linked list class Node: def __init__(self, data): self.data = data self.next = None Linked List class class LinkedList: def __init__(self): self.head = None Add node to the end def append(self, data): new_node = Node(data) if not self.head: self.head = new_node return 9 Unit 2: Introduction to Data Structures last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node Print the linked list def print_list(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") Example usage linked_list = LinkedList() linked_list.append(10) linked_list.append(20) linked_list.append(30) linked_list.print_list() ``` 1.3 Stack (LIFO) Stack implemented using a Python list: ```python Stack implementation using list stack = [] Pushing elements into the stack stack.append(10) stack.append(20) stack.append(30) print("Stack after pushing:", stack) Popping elements from the stack stack.pop() print("Stack after popping an element:", stack) ``` 1.4 Queue (FIFO) Queue implemented using Python's `collections.deque`: ```python 10 Unit 2: Introduction to Data Structures from collections import deque Queue implementation using deque queue = deque() Enqueue operation queue.append(10) queue.append(20) queue.append(30) print("Queue after enqueue:", queue) Dequeue operation queue.popleft() print("Queue after dequeue:", queue) ``` --- 2. Non-Linear Data Structures 2.1 Tree (Binary Search Tree) A simple binary search tree (BST) implementation: ```python Node class for Binary Search Tree class Node: def __init__(self, key): self.left = None self.right = None self.val = key Insert function for Binary Search Tree def insert(root, key): if root is None: return Node(key) if key < root.val: root.left = insert(root.left, key) else: root.right = insert(root.right, key) return root Inorder traversal of the Binary Search Tree def inorder(root): 11 Unit 2: Introduction to Data Structures if root: inorder(root.left) print(root.val, end=" ") inorder(root.right) Example usage root = Node(50) root = insert(root, 30) root = insert(root, 20) root = insert(root, 40) root = insert(root, 70) root = insert(root, 60) root = insert(root, 80) print("Inorder traversal of the BST:") inorder(root) ``` 2.2 Graph A simple undirected graph implementation using an adjacency list: ```python Graph implementation using an adjacency list class Graph: def __init__(self): self.graph = {} Add an edge to the graph def add_edge(self, u, v): if u not in self.graph: self.graph[u] = [] if v not in self.graph: self.graph[v] = [] self.graph[u].append(v) self.graph[v].append(u) since this is an undirected graph Print the graph def print_graph(self): for node in self.graph: print(f"{node} -> {self.graph[node]}") Example usage g = Graph() 12 Unit 2: Introduction to Data Structures g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 3) g.print_graph() ``` --- Summary: - Linear data structures: Arrays, Linked Lists, Stacks, and Queues maintain a sequential relationship among elements. - Non-linear data structures: Trees and Graphs provide more complex relationships between elements, enabling hierarchical and networked representations. 13
