S1: Data Abstraction in C++: Class
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S2: 1.1 Data Abstraction, ADTs, Encapsulation
  • Problem: Complexity of program design
  • Procedural Design (focus: algorithms)
    • encapsulate algorithms via procedure
    • Flaw: scope of data definition was very large
      • side-effects affected many units
    • Useful but not adequate
  • Alternative: Focus first on data rather than algorithm
    • Focus on key data types (structure and operations)
    • Data Abstraction: process of identifying key data types
      • (domain/structure, operations and properties)
    • Ex. Managing grades for CS3321
    • Student: < name, id, hw[5] > : update-HW-score, compute-total
    • ClassList : < cardinality, students > : add, sort by total, ...
  • Abstract Data Type(ADT): creates a user defined data type
    • Specifies (i) list of attributes and
    • (ii) operations to manipulate attributes
    • Usually properties are not explicit
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S3: Abstract Data Types
  • Encapsulation of ADT: View ADT as a program unit
    • Information Hiding: Need to know principle
      • Show interface (what), not implementation (how)
    • Implementation in C++
    • class: encapsulate ADT as a program unit
    • definition vs. implementation
  • ADT Format (pp. 4)
    • Header - specifies ADT-name
    • Data - describes the structure of data
    • List of operations with description of
      • Input, Output
      • Precondition : Assumption about data input
      • Postcondition: Guarantee about data after operation
      • Process: action performed with data
    • Constructor: a special operation for initialization
  • Ex. ADT Circle (pp 6)
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S4: Ch#2: Basic Data Types
  • Lists Basic data types common to most languages
    • with examples from C++
    • Uses ADT Format defined in Ch#1.1
      • to list data structure and operations
    • Additional details of C++ in Chapter 1 from
    • C++ notes from superconducting super collider lab.
    • Integers
    • Data: signed whole number N
    • Operations: =, +, -, *, /, %, ==, !=, < , < =, ...
    • Realization in C++: int, short int, long int
  • Character
    • Data: ASCII character set
    • Operations: assignment, relational (==, !=, < , < =, ...)
    • Realization in C++: char
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S5: Ch#2.3-5: Real, Enum & Pointers as ADTs
  • Real
    • Data: numbers in fixed-point or floating point
    • Operations: assignment, arithmetic, relational
    • Realization in C++: float, double, log double
  • Enumerated (pp 48)
    • Data: user defined list of N distinct items
    • Operations: assignment, relational
      C++: enum Boolean {False, True}; Boolean done = False;
  • Pointer (pp 49): More details in Chapter 8
    • Data: memory address of base type T (unsigned integer)
    • Operations: address (&), dereference (*), assignment,
      • memory allocation (new), deallocation (delete),
      • arithmetic and relational.
    • C++: What will the following print?
      char str[] = "ABCDEFG"; char *PC = str, *PC2 = PC++;
      short X = 33; short *PX = &X; PX points to X
      cout << *PC << endl ; //
      PC += 4; cout << *PC << endl ; // pointer + number - > pointer
      PC--; cout << *PC << endl ;
      cout << (PC2 - PC) << endl ; // pointer - pointer - > number
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S6: Ch#2.6-8: Arrays, records, strings as ADTs
  • Array (pp 52)
    • Data: homogeneous collection, integer indices
    • Operations: indexing ([ ])
      double X[50]; const int SZ = 10; long A[SZ];
  • Record (pp 65) :: Data: heterogeneous collection
    • Operations: access operator
      struct Student { int id; char name[30]; }
      Student S = { 555, "Davis, S." }; cout << s.id << s.name << endl;
  • String (pp 58) : details in ch#8.
    • Data: sequence of characters (null terminated)
    • Operations: length, copy, cat, compare, read, write,
    • index of given character in string, right-index
      char s1[20] = "dir/bin/app1", s2[20] = "file.asm",s3[20];
      char *p; int result;
      cout << strlen(s1) << endl; // A
      strcpy(s3, s1); strcat(s3, "/");
      strcat(s3, s2); cout << s3 << endl; // B
      cout << strcmp("hi", "Hi") << strcmp("12", "12"); // C
      p = strchr(s2, "."); strcpy(p, ".cpp"); cout << s2 << p; // D
      //(A) 12 (B) dir/bin/app1/file.asm (C) > 0, 0, (D) file.cpp, cpp
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S7: Ch#2.9: Files as ADTs
  • File (pp 68) : Details in Ch# 14.6
    • Data: external file and direction of data flow
    • Operations: open, close, read, write, seek
  • C++: stream hierarchy (Fig. 2.7); root = ios
    • input: istream, output: ostream
      • istream-withassign - understands data-types (eg cin)
      • istrstream - buffered in an array
      • ifstream - binary/ascii files
    • Ex. for 3 types of streams and operations (pp 70-71.)
      ifstream fin; /* input file */ char name[30], buffer[256];
      ostrstream outs(buffer, sizeof(buffer)); // buffered stream
      fin.open("names.dat", ios::in | ios::nocreate);
      fin >> name >> value; // say input is: Id 11111
      cout << name " = " << value; // prints Id = 11111
      outs << name " = " << value; outs << ends; // put in buffer
      cout << buffer << endl; // prints Id = 11111
  • SUMMARY of Chapter 2:
    • Language defined data-types can be viewed as ADTs
    • Now we ready to look at user-defined ADTs (C++ class)
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)