CS201 Study Guide

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

1a. Solve program implementation requirements using multidimensional arrays

  1. Describe the difference between contiguous and non-contiguous memory for any object.
  2. Demonstrate various means of implementing arrays.
  3. Show the difference between variable addresses and pointers.
  4. What is a linked-list, and what are its components?
  5. How does one create a linked-list?

Understanding how to arrange data in a computer's active and persistent memory is an important component of your study of computer science. The choice of arrangement depends very much on the application at hand; even so, it should never be so inflexible that it can't evolve with that application's requirements. Many "standards" in software engineering and software project management assume, if only implicitly, that a project's requirements are static. In the real world, that is never the case.

In this subunit, we focus on the most common data structure, arrays. These are native to most languages. Since we are dealing with C/C++, be sure you understand the rudiments of native array implementation in that language. Additionally, be sure you know the difference between contiguous and non-contiguous implementation. Although we do not cover it in this course, it is worth noting that "non-contiguous" can also refer to components of an array (or any data structure) that do not exist on the same physical computer that the access/manipulation software is running on.

Access to non-contiguous arrays and other data structures is facilitated by memory pointers. Memory pointers use memory addressing to locate the various components of a data structure.

Linked-lists are also part of the discussion on arrays since arrays can be implemented using nodes that point to other nodes. Each node can be interpreted as an array cell. As we have seen in the course, linked-lists are the basis for many other useful data structures. There are many approaches to the implementation of linked-lists; you should be familiar with those.

 

1b. Relate C/C++ structures and classes to ADTs

  1. What is the Standard Template Library (STL), and why is it important?
  2. Define "Abstract Data Type" (ADT).
  3. How are classes and structures and arrays related to ADTs?
  4. What are the important attributes of ADTs?

Abstract data types (ADTs) are the general case of specific types, such as arrays and linked-lists. Be sure you are familiar with the general concept of ADTs (in this video from 44:30). You should also understand the relationship between the general concept and C/C++ classes and structures.

The Standard Template Library (STL) is now part of the C++ language. Review the STL (in this video from 21:08-29:25) since it is applied regularly in professional practice.

 

1c. Apply the general concept of ADTs to lists and arrays accessed via pointers

  1. Review author implementations of linked-lists. How could they be improved?
  2. Review author implementations of arrays. How could they be improved?
  3. Why is it important to release memory allocated at runtime after it is no longer needed?
  4. Explain how memory can be available but unusable.

Use your favorite IDE to practice with arrays and linked-lists. Practice is essential. You need experience to be successful in your professional work. Programs used by various authors are presented as illustrations throughout the course. It is well worth your while to load these into your IDE and get them to work. As you do this, study them to understand their logic and how it translates to C/C++ syntax.

 

Unit 1 Vocabulary

This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.

Try to think of the reason why each term is included. Understanding linked-lists, arrays, and how they relate to ADTs lays the foundation for much of what is done in the application of data structures. Here are some terms you should be familiar with:

  • Node
  • Cell
  • Array
  • Vector
  • Linked-list
  • Abstract data type
  • Contiguous
  • Non-contiguous
  • Standard Template Library
  • Pointer
  • Address