Untitled Document

Intermediate C/C++ - Data Structures

Mario Giannini

mario@openroad.org

Text Data Structures Using C
by Tenenbaum, Langsam, and Augenstein, Prentice Hall
ISBN 0-13-199746-7

Recommended The C Programming Language by Kernighan and Ritchie
The C++ Programming Language by Stroustrup

Project The final project for this class is a name and addressbook program. This program will utilize topics covered throughout the semester and will stress application design, code reusability, and data structure implementation. The final project is due on the day of the final exam.

Tests 1 take-home midterm assign at the seventh class, and 1 final exam during the fifteenth class (final exam only). Tests must be made up within 1 week.

Grading Grading is broken down as follows:
Project 35%
Midterm 25%
Final 20%
Homework 15%
Participation 5%

No 'upgrades' will be permitted for homework, or assignments unless previously agreed upon with instructor. No more than two homework assignments will be accepted from a student on the final day of class.

A grade of 'incomplete' must be requested by students two weeks prior to the final exam. A grade of incomplete is granted at the instructors discretion, taking into account the students grade average and ability to complete class assignments.

Goals The goal of this class is to demonstrate analytical problem solving and real-world programming situations using C/C++. Code re-usability, design principles and creative algorithms will be stressed throughout the semester. Common-place data structures and algorithms will be examined and explained, providing the foundation for future development projects.

Object oriented topics are discussed in the second part of the class, demonstrating the syntactical and logical advantages of C++ over C. Real world design examples, object classes, and "Do's and Don'ts" of object oriented programming are discussed.

1) Programming

Identifying the tasks at hand
Importance of design
Top-down programming
C Review
Pointers
Structures
Memory allocation
File access
Homework: Write a program to open a text file and display it's contents
to the screen, line-by-line. Use fopen, fgets, malloc, and free.
Challenge: Store the entire file in memory, and sort it.

2) C Review Continued

Structures
Unions
Advanced pointers
Pointers to functions
Screen painting and Menuing structures
int86(), Win32 Consoles, and screen I/O
Homework: Create a structure that may have a variable size, and
contains in itself it's own size.
Challenge: Create a set of routines to create, remove, copy, and
compare these structures

3) Recursion

Tower of hanoi
Recursive addition
Recursion and the Stack
Field editing structures
Homework: Write a recursive function to reverse the characters of a
string
Reading: p 100-103, 109-115

4) Stack

Usage and definition
Implementation
Creation, Push, Pop, and Destruction functions
Database structures and techniques
Records and fields
Homework: Write the Push() and Pop() functions
Challenge: Create a dynamic stack (Create() and Destroy())
Reading: 64-83

5) Queues

Usage and definition
Implementation
Creation, Add, Remove, and Destruction functions
I/O buffering
Homework: Write the Add() and Remove() functions
Challenge: Create a dynamic queue (Create() and Destroy())
Reading: 158-165

6) Linked Lists - One-way

Usage and definition (Database)
Implementation
Header-node definition
Homework: Create a simple one-way linked-list program with the
following functions: CreateList(), AddToList(), DestroyList(),
PrintList().
Reading: 170-184, 219-220

7) Linked Lists - Two Way

Definition and differences
Using existing code as basis for new linked list
Midterm (take-home)
Homework: Modify previous homework and make two-way functions
Reading: 222-224

8) Linked Lists - Summation

Applicable uses, when not to use
Generic linked-list management
Linked-list traits of other structures
Object Oriented programming
Objects, Instances, and classes
Homework: To be assigned

9) Binary Trees

Usage and definition
Recursive traits
Balance principles
Object Oriented programming
Method functions, and object communications
Polymorphism
Homework: 1)Write a word-counting program using a binary tree
2) Demonstrate a Clear method for a variable class, and derived string class.
Reading: 276-285, 289-302

10) Binary Trees

Tree searching
Ordered retrieval
Object Oriented Programming
Inheritance
Object identification
Homework: Complete Generic B-Tree functions for tree management

11) Binary trees continued

Rotations
Alternative uses
Common non-database applications
Object Oriented Programming
"is a" vs. "has a"
Overloaded functions
Homework: Examine the maze-solving program

12) BTrees

Differences and applications
Object Oriented Programming
Case study: Black Jack Game
Case Study: Player classes and derived classes. Human vs. Computer

13) Application development tools

Make files
Libraries and Librarians
Object Oriented Programming
Case Study: Microsoft Foundation class

14) Final exam

Text	Data Structures Using C by Tenenbaum, Langsam, and Augenstein, Prentice Hall ISBN 0-13-199746-7
Recommended	The C Programming Language by Kernighan and Ritchie The C++ Programming Language by Stroustrup
Project	The final project for this class is a name and addressbook program. This program will utilize topics covered throughout the semester and will stress application design, code reusability, and data structure implementation. The final project is due on the day of the final exam.
Tests	1 take-home midterm assign at the seventh class, and 1 final exam during the fifteenth class (final exam only). Tests must be made up within 1 week.
Grading	Grading is broken down as follows: Project 35% Midterm 25% Final 20% Homework 15% Participation 5% No 'upgrades' will be permitted for homework, or assignments unless previously agreed upon with instructor. No more than two homework assignments will be accepted from a student on the final day of class. A grade of 'incomplete' must be requested by students two weeks prior to the final exam. A grade of incomplete is granted at the instructors discretion, taking into account the students grade average and ability to complete class assignments.
Goals	The goal of this class is to demonstrate analytical problem solving and real-world programming situations using C/C++. Code re-usability, design principles and creative algorithms will be stressed throughout the semester. Common-place data structures and algorithms will be examined and explained, providing the foundation for future development projects. Object oriented topics are discussed in the second part of the class, demonstrating the syntactical and logical advantages of C++ over C. Real world design examples, object classes, and "Do's and Don'ts" of object oriented programming are discussed.