Data Structures, Algorithms, and Software Principles in C

by Standish, Thomas A.

• ISBN13: 9780201591187
• ISBN10: 0201591189
• Edition: 1st
• Format: Paperback
• Copyright: 1994-09-30
• Publisher: Pearson

Summary

Using C, this book develops the concepts and theory of data structures and algorithm analysis in a gradual, step-by-step manner, proceeding from concrete examples to abstract principles. Standish covers a wide range of both traditional and contemporary software engineering topics. The text also includes an introduction to object-oriented programming using C++. By introducing recurring themes such as levels of abstraction, recursion, efficiency, representation and trade-offs, the author unifies the material throughout. Mathematical foundations can be incorporated at a variety of depths, allowing the appropriate amount of math for each user.

Author Biography

Thomas A. Standish is the chairman of computer science at the University of California, Irvine. In 1990-91, he became the fourth winner of University of California Irvine's Distinguished Faculty Lectureship for Teaching, the campus' highest distinction for teaching excellence. He has also been a co-winner of his department's best-teacher award, chosen by the popular vote of University of California Irvine undergraduate computer science students.

0201591189AB04062001

Table of Contents

Preparing for the Journey

Where Are We Going? Blending Mathematics, Science, and Engineering

The Search for Enduring Principles in Computer Science

Principles of Software System Structure

Efficiency and Tradeoffs

Software Engineering Principles

Our Approach to Mathematics

Some Notes on Programming Notation

Preview of Coming Attractions

Linked Data Representations

What are Pointers?

The Basic Intuition

Pointers in C—The Rudiments

Pointer Diagramming Notation

Linear Linked Lists

Other Linked Data Structures

Introduction to Recursion

Thinking Recursively

Common Pitfall—Infinite Regresses

Quantitative Aspects of Recursive Algorithms

Modularity and Data Abstraction

Modularity and Information Hiding in Program Design

Introduction to Software Engineering Concepts

Top-Down Programming By Stepwise Refinement

Proving Programs Correct

Transforming and Optimizing Programs

Testing Programs

The Philosophy of Measurement and Tuning

Software Reuse and Bottom-up Programming

Program Structuring and Documentation

Introduction to Analysis of Algorithms

What Do We Use for a Yardstick?

The Intuition Behind O-Notation

O-Notation—Definition and Manipulation

Analyzing Simple Algorithms

What O-Notation Doesn't Tell You

Linear Data Structures—Stacks and Queues

Some Background on Stacks

ADTs for Stacks and Queues

Using the Stack ADT to Check for Balanced Parentheses

Using the Stack ADT to Evaluate Postfix Expressions

Implementing the Stack ADT

How C Implements Recursive Function Calls Using Stacks

Implementations of the Queue ADT

More Queue Applications

Lists, Strings, and Dynamic Memory Allocation

Lists

Generalized Lists

Applications of Generalized Lists

Strings

Dynamic Memory Allocation

Trees

Basic Concepts and Terminology

Binary Trees

A Sequential Binary Tree Representation

An Application—Heaps and Priority Queues

Traversing Binary Trees

Binary Search Trees

AVL Trees and Their Performance

Two-Three Trees

Tries

An Application—Huffman Codes

Graphs

Basic Concepts and Terminology

Graph Representations

Graph Searching

Topological Ordering

Shortest Paths

Task Networks

Useful Background on Graphs

Hashing and the Table ADT

The Table ADT

Introduction to Hashing by Simple Examples

Collisions, Load Factors, and Clusters

Algorithms for Hashing by Open Addressing

Choosing a Hash function

Comparison of Searching Methods Using the Table ADT

External Collections of Data

Characteristics of External Storage Devices

Techniques That Don't Work Well

Techniques That Work Well

Information Retrieval and Databases

Sorting

Laying Some Groundwork

Priority Queue Sorting Methods

Divide-and-Conquer Methods

Methods That Insert Keys and Keep Them Sorted

Table of Contents provided by Publisher. All Rights Reserved.