Data Structures: ADT and C++ Classes

Unit Objectives

• Getting to know why data structures are important
• Software development cycle
• Getting to know basics of Object Oriented Programming
• Learning Abstract Data Type

 

Reading List

• Chapter 1 from the main textbook and web links provided by the instructor

Problems

• Why data structures are important?
• What procedures must be taken to develop good software?
• What's the role of an ADT in Object Oriented Programming?
• What are the basic steps in testing and  debugging?

Why Data Structures?

Data structure is a way to store information in a program. To solve a problem using a computer, we need to have a correct and efficient way to solve the problem (algorithm) but we also need to carefully organize the information (data). An algorithm is systematic methods and procedures to solve a specific problem. Quite often, the way we organize the information directly affects the performance, ease of programming and debugging of a program. So a good program is a combination of a good algorithm and  good data structures. An algorithm is about how to solve a problem and the data structure is about the organization of information that the algorithm is dealing with.

Program = Algorithms + Data Structures

You may have used arrays and some other simple data structures for the CSCI141/CSCI1411 Fundamentals of Computing and CSCI2320 Intermediate Programming. This course will guide you through many widely used advanced data structures and their proper applications. In addition, you'll learn and reinforce important concepts of object oriented programming using C++, and basics of software engineering.  

Software Development Cycle

Program design strategy

1. specify the input and output
2. Design an appropriate algorithm to solve the problem
3. Choose appropriate data structures
4. Translate the algorithm into a programming language of your choice (C++)
5. Test and debug the program

There is no step like "write a program"

The software development cycle can be roughly illustrated as

1. Specification
2. Design
3. Implementation

Specification

 The specification step includes following tasks

1. Specifying precisely what the program is supposed to do
2. Specifying what's the input of the program
3. Specifying what's the output of the program

In this step, just ignore how the problem can be solved.

Design

The design step includes development of an algorithm and choosing the right data structures. The algorithm can be described in either a high level, programming language independent description for solving the problem. Since the detail is often omitted, the plain English is generally acceptable for this process, but sometimes the pseudo code is more desirable since it includes more detailed methods and is easier to translate into a programming languages.

Design step also outlines the data structures. All programs manipulate data in various form including text, number, picture, sound, etc. The data must be processed and stored. As mentioned above, data is the information manipulated by an algorithm.  So to make a program efficient, clear, correct and effective, data should be properly organized. Depending on the algorithm, usually there are matching or appropriate data structures beyond simple arrays, such as linked lists, stacks, queues, trees, and graphs. This process is especially important in object oriented programming since it considers algorithms and data structures are equally important and tightly related. Object oriented programming combines them in one package called Object.  The OOP will be detailed in the later units.

Implementation

Implementation is the actual source code written in a specific programming language that carries out the design. If you have a good specification and design, this final process is relatively straight forward to translate specification into pre- and post-conditions, and to translate algorithmic pseudo-code and data structures layout into actual source code.

What is a Good Program?

Programming Strategies

Before we start discussing the ADT and C++ Classes, let's think about the programming and effective strategies to solve problems as a whole. Take a look at this article. 

Object Oriented Software

Let's first discuss about what Object Oriented Software is. This article uses Smalltalk as an example of a true object oriented programming language but it's not widely used. Instead, C++ evolved substantially to incorporate OOP paradigm into widely used popular C language. Take a look at this article.

Object Oriented Software vs. Other Paradigm

This article is about the survey of programming techniques. It includes some advanced topics (linked list, and some basic software engineering concepts etc.) that we haven't discussed so far, but nonetheless it will give you a good idea about the main difference of the OOP and some historical perspective of the evolution of programming paradigm. Take a look at this article. 

Abstract Data Type

An abstract data type is a data structure and a collection of functions and procedures which operate on the data structure.

We'll call the functions and procedures methods (member functions in C++) and the data structure and its methods a class, i.e. we'll call our ADTs classes. An instance of the class is called an object . Objects represent objects in the real world and appear in programs as variables of a type defined by the class.

So what's the relationship between a class and an object?

A class is a template and an object is an instantiation from the class. You can think of an analogy to existing data types and variables. For example, if you want to declare a variable "mynumbers" in integer data type, you use "mynumbers" as a new variable name and create that variable using existing data type "integer". From OOP's point of view, "mynumbers" is an object and "integer" is a class. However, in this case, the class has only one data structure and no associated member function.  In addition, there's no mechanism for information hiding.

More formal definition of ADT can be found here.