Topic outline
-
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.
-
-
Students mustMark as done
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.
-
Students mustMark as done
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.
-
Students mustMark as done
The discussion from the previous video continues in this lecture. Watch from the beginning until 7:00.
-
Students mustMark as done
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.
-
Students mustMark as done
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.
-
-
Students mustMark as done
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.
-
-
-
Students mustMark as done
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.
-
-
-
Students mustMark as done
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.
-
-
-
Students mustMark as done
Read this page to learn about singly and doubly linked lists and their implementation.
-
Students mustMark as done
Study the code examples on this page to see the how linked lists are implemented in C/C++.
-
Students mustMark as done
Try some of these exercises to get hands-on practice with linked lists.
-
-
-
Students mustMark as done
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.
-
-
Students mustMark as done
Read this page, which covers additional features of arrays and gives some example code.
-
Students mustMark as done
Read this page, which includes graphical representations of arrays that illustrate their arrangement in contiguous memory.
-
Students mustMark as done
Attempt these exercises to gauge your understanding of arrays.
-
-
-
Students mustViewReceive 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.
-