Programming Abstractions in C : A Second Course in Computer Science

by Roberts, Eric S.

• ISBN13: 9780201545418
• ISBN10: 0201545411
• Edition: 1st
• Format: Paperback
• Copyright: 1997-08-08
• Publisher: Addison-Wesley

Summary

This exciting new data structures book provides students with powerful procedural programming skills that will serve as a solid foundation for later object-oriented programming. Throughout the book, Eric Roberts takes a library-based approach to the concepts, which allows readers to see more advanced programs early on. This innovative use of libraries will motivate students as they begin tackling more advanced data structures topics. In the first section of the book, Roberts brings readers up-to-speed on libraries and also provides a nice review of C. Eric Roberts is famous for his wonderful writing style, his use of real-world examples, and his special "bug features."

Author Biography

Eric S. Roberts is a Professor of Computer Science at Stanford University and the department's Associate Chair for Educational Affairs.

Table of Contents

Preliminaries

An Overview of Ansi C.

What is C?

The Structure of a C Program

Variables, Values, and Types

Expressions

Statements

Functions

Data Types in C

Enumeration Types

Data and Memory

Pointers

Arrays

Pointers and Arrays

Records

Dynamic Allocation

Libraries and Interfaces

The Concept of an Interface

Random Numbers

Strings

The Standard I/O Library

Other ANSI Libraries

Recursion and Algorithmic Analysis

Introduction to Recursion

A Simple Example of Recursion

The Factorial Function

The Fibonacci Function

Other Examples of Recursion

Thinking Recursively

Recursive Procedures

The Towers of Hanoi

Generating Permutations

Graphical Applications of Recursion

Backtracing Algorithms

Solving a Maze by Recursive Backtracking

Backtracking and Games

Analysis of Algorithms

The Sorting Problem

Computational Complexity and Big-O Notation

Recursion to the Rescue

Standard Complexity Classes

The Quicksort Algorithm

Mathematical Induction

Data Abstraction

Abstract Data Types

Stacks

Defining a Stack ADT

Using Stacks in an Application

Implementing the Stack Abstraction

Defining a Scanner ADT. Efficiency and ADTs

The Concept of an Editor Buffer

Defining the Buffer Abstraction

Implementing the Editor Using Arrays

Implementing the Editor Using Stacks

Implementing the Editor Using Linked Lists

Linear Structures: Stacks and Queues

Stacks Revisited

Queues

Simulations Involving Queues

Symbol Tables

Designing the Symbol Table Interface

Hash Tables

Using Functions as Data

Mapping Functions

Iterators

Command Dispatch Tables

Recursive Data

Recursive Lists

The Recursive Formulation of a List

Defining a List Abstraction

Generalized List Structure

Trees

Family Trees

Binary Search Trees

Balanced Trees

Defining a General Interface for Binary Search Trees

Expression Trees

Overview of the Interpreter

Understanding the Abstract Structure of Expressions

Representing Expressions as a Concrete Type

Parsing an Expression

Evaluating an Expression

Sets

Sets as a Mathematical Abstraction

Designing a Set Interface

Implementing the Set Package

Designing a Polymorphic Iterator

Enhancing the Efficiency of Integer Sets

Graphs

The Structure of a Graph

A Standalone Interface for Graphs

Implementation Strategies for Graphs

A Set-Based Interface for Graphs

Graph Traversals

Finding Minimum Paths

Looking Ahead

The Concept of Object-Oriented Programming

A Brief Tour of the Java Programming Language

Interactive Programming. 0201545411T04062001

Table of Contents provided by Publisher. All Rights Reserved.