CSC 1061 Week 04 Data Structures Static Array PDF

CSC 1061 DATA STRUCTURE: BAG STATIC ARRAY  OBJECTIVES AGENDA: WEEK 04 Design and implement collection 1. Arrays classes that use partially filled 2. Data Structures / Collections arrays to store a collection of...

CSC 1061 DATA STRUCTURE: BAG STATIC ARRAY  OBJECTIVES AGENDA: WEEK 04 Design and implement collection 1. Arrays classes that use partially filled 2. Data Structures / Collections arrays to store a collection of elements 3. Big-O Analysis Write and maintain an accurate 4. Bag Data Structure invariant for each class that you 5. Bag Algorithm Efficiency implement 6. Invariant of the data members To understand why algorithm analysis is important to t 7. Bag ADT Develop understanding of Big O notation and other important techniques of algorithm analysis. STATIC ARRAYS Static arrays are defined as compiler memory managed array. The static is NOT referring to a value shared within a class and is NOT being used as the C++ keyword! Static arrays are stored on the stack part of memory. Arrays have 4 rules: 1. All elements stored within are of the same data type 2. The array is a fixed-size at compile time and cannot grow or shrink during run-time. 3. When declaring an array, the fixed-size of the array is a counting number NOT 0 based. 4. When referencing the elements of an array the indexes are 0 based. ARRAY CHALLENGE Test your knowledge and complete questions 1 and 2 SKIP 3 NOT C++ DATA STRUCTURES Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently. We'll be covering the following data structures this semester: 1. Static Array 2. Dynamic Array 3. Linked List 4. Stack & Queue 5. Graph 6. Binary Tree 7. Heap 8. B-Tree COLLECTIONS Read the tutorial and complete all the activities: 1.10. Collections 1.10.1. Arrays STOP when you get to 1.10.2 Vectors – this will be covered when we do dynamic array collections ALGORITHM ANALYSIS? Read the tutorial and complete all the activities: 2.2 What is algorithm analysis? STOP when you get to 2.2.1 Some Needed Math Notation BIG-O ANALYSIS Order of magnitude is often called Big-O notation (for “order”). It provides a useful approximation to the actual number of steps in the computation. Big-O characterizes an algorithm’s efficiency in terms of execution time, independent of any particular program or computer. https://runestone.academy/ns/books/published/cppds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html?mode=browsing BIG-O NOTATION Read the tutorial and complete all the activities for: 2.3 Big-O Notation Complete the Self-Check from the tutorial in BigO Finding Minimum Search BAG DATA STRUCTURE DEFINED A Bag Data Structure is an unordered collection of values that may have duplicates. Bag data structure (containers) do NOT care about order and are described like a Bag of groceries. A container is a holder object that stores a collection of other objects (elements). The container manages the storage space for its elements and provides member functions to access and modify the collection. BAG ADT DATA STRUCTURE A Bag is a limited (fixed size), unordered data structure. All data structures start out empty zero elements Bags must keep track of number of elements in the Bag data member: size Watch the YouTube Video: https://youtu.be/gU7qTGttlKw?si= xr2eDUwFIgYNc0_k ▪ Note: Video outlines the MAX_SIZE as capacity and the number of elements as used instead of size​ ALGORITHM EFFICIENCY Using the draw or text tool, determine 1. Create empty Bag the overall BigO efficiency of each task by writing 1-11 in the table below 2. Add Item to the unordered Bag Constant Logarithmic Linear Quadratic 3. Find Item in the Bag BigO(1) BigO(log(n)) BigO(n) BigO(n2) 4. Get an Item at a specified index 5. Count How Many elements 6. Determine MAX_SIZE 7. Remove Item from unordered Bag 8. Clear All Items 9. Check if Bag isEmpty 10. Remove Item By Index (unordered) 11. Remove All Duplicates (unordered) INVARIANT: RULES OF DATA MEMBERS Read the tutorial and complete the multiple-choice question activities: 14.8 Invariants INVARIANT: RULES OF DATA MEMBERS Fixed size array: dataType data[MAX_SIZE]; MAX_SIZE must be set at compile time using constant All items are of the same specified data type Array indexes must always be checked to safe guard against index- out-of-bounds errors Compare size against MAX_SIZE to determine room in data structure Data member size tracks number of elements in data structure: int size; size is initialized to 0 to indicate empty data structure size must be incremented with each element added size must be decremented with each element removed EXAMPLE BAG OF DATE OBJECTS #ifndef DATES_H #define DATES_H #include "date.h" class ImportantDates { Date data[MAX]; int size; public: static const int MAX = 3; ImportantDates() { size = 0; } // default constructor bool append(const Date& item); }; #endif Watch the YouTube Video: https://youtu.be/N5Y_Ye0LZsc?si=tSjVfZMLM_bcv4B6 BAG ADT: MODIFIER MEMBER FUNCTIONS bool append(const DataType& item); bool removeByIndex(int index); bool removeItem(const DataType& item); void clearAll(); BAG ADT: CAPACITY MEMBER FUNCTIONS int getSize() const; int getMaxSize() const; bool isEmpty() const; BAG ADT: ACCESS MEMBER FUNCTIONS int contains(const DataType& item) const; const DataType& at(int index) const; const DataType& operator[](int index) const;  OPERATOR[ ] The Subscript or Array Index Operator is denoted by []. This operator is generally used with arrays to retrieve and manipulate the array elements as both a getter and setter. The subscript operator is overloaded as a member function for data structure classes that use arrays to store the data. Bags and Lists have the same implementation Review the std::string subscript operator[] Notice there are 2 prototypes listed. Identify which is the getter and which is the setter Complete the replit demo: Bag with operators  AT MEMBER FUNCTION The at member function is generally used with arrays to retrieve and manipulate the array elements as both a getter and setter. Bags and Lists have the same implementation Review the std::string::at member function Notice there are 2 prototypes listed. Identify which is the getter and which is the setter and give examples of using each To alleviate redundancy between operator[] and at member function, have one defined and the other calls the defined function. Complete the replit demo: Bag with operators BAG ADT: OTHER MEMBER FUNCTIONS bool readFile(const std::string& fileName); bool writeFile(const std::string& fileName);