Intermediate C - Data Structures
Mario Giannini

 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
 Tests: A midterm and Final exam, given on the 6th and 12th classes
respectivly. If missed, exams must be made up within 1 week.

Grading is broken down as follows:
Midterm/Final 70%
Homework 20%
Participation 10%

Final grades will be assigned on a pass/fail/honors basis. Note that a
mark of below 65 is failing, and only 98 and above are honors.

No 'upgrades' will be permitted for homeworks, 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.

 Goals: The goal of this class is to demonstrate analytical problem solving and
real-world programming situations using C. Code re-usability, design
principles and creative algorithms will be stressed throughout the

 Class Descrption
 1  Programming
Identifying the tasks at hand
Importance of design
Top-down programming
C Review
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
Advanced pointers
Pointers to functions
Menuing and Screen painting structures
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 Sorting
Brute force, Bubble, Quick
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
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
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)
Header-node definition
Homework: Create a simple one-way linked-list program with the
following functions: CreateList(), AddToList(), DestroyList(),
Reading: 170-184, 219-220
 7 Linked Lists - Two Way
Definition and differences
Using existing code as basis for new linked list
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
Homework: To be assigned
 9 Binary Trees
Usage and definition
Recursive traits
Balance principles
Homework: Write a word-counting program using a binary tree
Reading: 276-285, 289-302
10 Binary Trees
Tree searching
Ordered retrieval
Homework: Complete Generic B-Tree functions for tree management
 11 Binary trees continued
Alternative uses
Common non-database applications
Homework: Examine the maze-solving program, be prepared to discuss in class
 12 BTrees
Differences and applications
Application development tools
Make files
Libraries and Librarians
Final Exam