• Unit 1: Abstract Data Types and Arrays in C++

    This unit will introduce you to Abstract Data Types and will make the important distinction between an Abstract Data Type and a Data Structure. You will also learn about arrays (a specific type of Data Structure) and the abstracted form of the array data type in C++.

    Completing this unit should take approximately 7 hours.

    • Upon successful completion of this unit, you will be able to:

      • solve program implementation requirements using multidimensional arrays.
        • build multi-dimensional arrays using native C/C++ definitions.
        • build multi-dimensional arrays using a combination of vectors.
        • demonstrate multi-dimensional arrays having varying length rows or columns.
        • define contiguous memory.
        • discuss why arrays of all kinds do not necessarily occupy contiguous memory.
      • relate C/C++ structures and classes to ADTs.
        • explain how structures (C language) and classes (C++ language) can be treated as ADTs.
        • illustrate the difference between an ADT definition and an ADT instance.
        • relate ADTs to the Standard Template Library (STL), a formal part of the C++ language.
      • apply the general concept of ADTs to lists and arrays accessed via pointers.
        • demonstrate how lists and arrays are specific forms of ADTs.
        • define pointer.
        • relate pointers to specific cells (data locations) in a list or array.
        • apply pointers to elementary data access requirements.

    • 1.1: Abstract Data Types

      • An abstract data type allows us to group native built-in data types into a compound type whose instances can be individually referenced. Far from just containing the data itself, an abstract data type also contains functions that operate on its data. There can be many instances of (specific uses of) an individual abstract data type. The data contained in each instance and the operations on that data are independent of all other instances. It is also possible for an abstract data type to be composed of other abstract data types. Within object-oriented programming, abstract data types are referred to as classes. An instance of a class is called an object. If we do not embed functions (methods) within an abstract data type then we are left with a data structure that is common in modular programming. Abstract data types are the foundation for understanding and applying specific data types, native or user-defined. They also form the foundation for structured and object-oriented programming. Ultimately, these lead to parallel and distributed processing.

      • Data Abstraction Page

        Read this section, which expands the discussion and illustrates with native built-in types. The discussion in 2.2.1 is true of all native built-in types, and the tiny bit of Python code at the end of 2.2.1 should be easily understandable. Each of the built-in types have their own methods, which apply to them and which operate appropriately according to their type. Also, their internal representation is hidden at the code-level perspective.

      • Sort Template with Callback Page

        While all languages include abstract data types in the form of native data types and their operations, there is also the matter of user-defined compound types. These abstract data types are introduced this video, which you should watch starting at 44:30. This begins a language-agnostic discussion that is very valuable.

      • Abstract Data Types Page

        The discussion from the previous video continues in this lecture. Watch from the beginning until 7:00.

      • Abstract Data Types in C++ Page

        Read these sections, which discuss the foundation of ADTs and the way they are implemented in C (as structures) and C++ (as classes). The Standard Template Library (STL) is now officially part of C++. The STL continues a natural progression from structures (data only) to classes (data plus operations on that data) to a library of trusted classes that implement often-needed data/method containers. Since the STL is largely data-type agnostic, templates begin to be very useful.

      • Standard Template Library Page

        This lecture introduces the C++ Standard Template Library (STL) from 21:08 to 29:25. STL is a formal part of the C++ language, and is a set of class templates for many important and commonly-used program components. It is very much worth your while to be familiar and practiced with this library.

    • 1.2: Contiguous Implementation

      • Arrays Page

        Read this introduction to the contiguous data structure type, which arrays are an example of. "Contiguous" refers to the memory occupied by the data structure being grouped serially by address. For instance, if an integer occupies four bytes, those four bytes are guaranteed to begin at the memory address of the first byte and end at the memory address of the fourth byte, so that those four bytes occupy memory addresses M, M+1, M+2, and M+3. One only has to reference address M to get the entire value of the integer. The same is true of contiguous arrays of any dimension. The cells of the array are guaranteed to occupy serially-grouped (contiguous) memory. Otherwise, the array can not be allocated.

    • 1.3: Non-Contiguous Implementation

      • Memory Allocation in C++ Page

        Arrays can be implemented so that they do not occupy contiguous memory. The addressing is the same. For instance, A[r][c] still addresses the c'th column of the r'th row of array A. However, as we will see later in the course, one can not use the address of A[0][0] as the starting point for calculating the address of A[r][c]. The reason we use this type of array allocation is to delay allocating memory until it is needed. We can also easily get rid of array rows that contain data no longer needed. This is not possible with arrays allocated using native declaration syntax <type> A[numRow][numCol] since that approach allocates an entire block of memory for the array at one time. Read the linked page. Pay special attention to the "Matrix" section. You will notice that individual rows do occupy contiguous memory, but the array itself does not.

    • 1.4: Introduction to Memory Pointers

      • Pointers in C++ URL

        A pointer variable is a variable whose value is a memory address. Memory pointers can be very complex and few programmers really understand them, even though they are involved in many uses, from simple to complex. Pointers are an essential topic in C/C++, since they offer many opportunities for run-time improvement and ease of access to linked data structures. However, using pointers can also produce obscure code that is hard to understand. Misuse of pointers can also seriously corrupt memory during program execution, and these kinds of errors are very hard to track down. Even so, direct memory access is central to C/C++. As your compound data types become more multifaceted and are used within increasingly involved operations, a good understanding of pointers becomes even more important. Watch this video to get an excellent introduction to pointer variables.

    • 1.5: Linked Lists

    • 1.6: Arrays

      • An array is a series of elements of the same serial abstract data type placed in contiguous memory. Their memory locations can be individually referenced by adding an index to a unique identifier. The number of elements in the array leads to the concept of the dimension of an array. Each object is stored in its own array cell, its own element. The following resources discuss how to access the elements of an array within the bounds of the array's dimensions.

      • Arrays in C Page

        Read this introduction to arrays in C/C++.

      • Additional Features of Arrays Page

        Read this page, which covers additional features of arrays and gives some example code.

      • Representations of Arrays Page

        Read this page, which includes graphical representations of arrays that illustrate their arrangement in contiguous memory.

      • Array Programming Exercises URL

        Attempt these exercises to gauge your understanding of arrays.

    • Unit 1 Assessment

      • Unit 1 Assessment Quiz
        View Receive a grade

        Take this assessment to see how well you understood this unit.

        • This assessment does not count towards your grade. It is just for practice!
        • You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
        • You can take this assessment as many times as you want, whenever you want.