Lecture Notes for SE 598, Data Structures and Algorithms

24 May 2000, Introduction to C++

1. programming languages are useful because they, among other things, provide some handy, pre-defined data structures

   1. but how can you have data structures without knowing what the data structures are modeling

   2. most worlds are sufficiently similar in their basic characteristics that it makes sense to pre-define some proven data structures

   3. it's a bit like off-the-rack clothing - everybody's different in detail but generally the same in structure

   4. generic programming is an extension of this idea

      1. try to develop sophisticated, pre-defined data structures

      2. the standard template library supports generic programming

2. c++ data structures

   1. what are types

      1. a type is the way characteristics determine values

      2. data type is another name for data structure

      3. "what is this value's type" rather than "what is this value's structure" - equivalent questions

   2. simple data structures

      1. the basic (or elemental) data types - bits, bytes, words

      2. the atomic data types - ints, floats, doubles, chars, and bools

   3. arrays - a non-atomic, or composite, or structured data structure

      1. a homogeneous collection of data - all of the same type

         1. each datum is called an element, or a member, or an item

      2. any element in the array can be accessed with the same amount of work

         1. all elements in an array are accessible

         2. any element is equally easy to access as any other

      3. indices identify one element from another

   4. structures

      1. a heterogeneous collection of data - different types

      2. accessed via the dot operator

      3. unions - the structure's evil sibling

3. how does programming get done

   1. data structures and algorithms - which comes first

   2. procedural programming - concentrate on algorithms and the data structures follow

      1. identify the important transformations required

      2. implement each transformation as a procedure

      3. derive the data structures based on the given data and the procedures

   3. object-oriented programming - concentrate on data structures and the algorithms follow

      1. identify the important entities in the world

      2. implement each entity as an object

      3. derive the interactions among objects

This page last modified on 24 May 2000.