數據結構

內容簡介

本書從面向對象的視角介紹數據結構。內容從數據結構的基本原

理到面向對象程序設計的方法。書內使用適應面極廣的C++語言。全

書14章分別為：1緒論；2基本數據類型；3抽象數據類型與類；4.

集合類；5棧與隊列；6.抽象運算符；7.類屬數據類型；8.類與動態

存儲；9鏈表；10遞歸；11樹；12繼承與抽象類；13先進的非線

性結構；14構建集合。書後附有練習答案。

Preface xvll

CHAPTER 1 INTRODUCTION

1.1 Abstract Data Types

ADT Format

1.2 C++ Classes and Abstract Types

Encapsulatlon and Information Hidlng

Message Passing

1.3 Objecls in C++ Appllcatlons

Applicatlon: The Circle Class

1.4 Oblect Design

Objects and Composltion

C++ Geometric Classes

Objects and Inherltance

Inheritance In Frogrammlng

Ordered Llsts and Inheritance

Software Reusability

SeqLlst and OrderedLlsl Class Speclfications

1.5 Applicatlons with Class Inherltance

1.6 Object-Oriented Program Design

Problem Analysis/Program Definition

Deslgn

Coding

Tesllng

Program Deslgn Illustratlon: A Dlce Graph

1.7 Program Testlng and Malnlenance

Object Testlng

Contrul Module Testing

Program Malntenance and Documentation

1.8 The C++ Programming Language

1.9 Abstract Base Classes and Polymorphism

Polymorphlsm and Dynamic Binding

Written Exerclses

CHAPTER2 BASIC DATA TYMS

2.1 IntegerTypes

Computer Storage of Integers

Data In Memory

C++ Representatlon of Integers

2.2 Character Types

ASCIl Characlers

2.3 Real Data Types

Real Number Representatlons

2.4 Enumerated Types

Implementing C++ Enumerated Types

2.5 Pointers

Pointer ADT

l'olnter Values

2.6 The Array Type

the Buill-In C++ Array Type

Sloragc of One-Dimcnslonal Arrays

Array Bounds

Two-Dlmensional Arrays

Storage of Two-Dimenslonal Arrays

2.7 String Literals and Variables

C++ Strings

Appllcallon: Reverslng Names

2.8 Records

C++ Structures

2.9 Files

C++ Stream Hlerarchy

2.10 Array and Record Appllcations

Sequentlal Seareh

Exchange Sort

Counting C++ Reserved Words

Wrltten Exercises

ProgrammlIlg Exerclses

CHAPTER 3 ABSTRACT DATA TYPES AND CLASSES

3.1 The User Type CLASS

Class Declaration

Constructor

Object Declarallon

Class Implementatlon

Implementing a Constructor

Bulldlng Objects

3.2 Sample Classes

The Temperature Class

The Random Number Class

3.3 Oblects and Information Passlng

An Object as a Return Value

An Object as a Function Parameter

3.4 Arrays of Objects

The Default Conslructor

3.5 Multlple Constructors

3.6 Case Study: Triangular Matrices

llpper Triangular Matrlx Properties

Written Exerclses

Programming Exereises

CHAPTER 4 COLLECTION CLASSES

4.1 Describing Llnear Collectlons

Dlrecl Access Collections

Sequentlal Access Collectlons

Generalized Indexing

4.2 Describing Nonlinear Collectlons

Group Collectlons

4.3 Analysls of Algorllhms

Performance Crlteria

Common Orders of Magnltude

4.4 The Sequential and Blnary Search

Blnary Search

4.5 The Baslc Sequentlal List Class

List Modincatlon Melhods

Wrlllen Exerclses

Programming Exerclses

CHAPTER 5 STACKS AND QUEUES

5.1 Stacks

5.2 The Stack Class

5.3 Expression Evaluation

Postfix Evaluation

Appllcatlon: A Posttlx Calculator

5.4 Queues

5.5 The Oueue Class

5.6 Prlorlty Queues

A Prlorlty Queue Class

5.7 Case Study: Event-Drlven Slmulalion

Wrltten Exerclses

Programmlng Exerclses

CHAPTER 6 ABSTRACT OPERATORS

6.1 Describlng Operator Overloading

Client-Defined External Functlons

Class Members

Frlend Functlons

6.2 Rational Number System

Representlng Ratlonal Numbers

Ratlonal Number Arithtnetlc

Ralional Number Converslon

6.3 The Ratlonal Class

6.4 Ratlonal Operators as Member Funclions

Implemenllng the Ratlonal Operators

6.5 The Ratlonal Stream Operators as Friends

Implementlng Ratlonal Stream Operators

6.6 Converting Rational Numbers

Conversion to Object Type

Converslon from Object Type

6.7 Using Ratlonal Numbers

Wrltten Exerclses

Programmlng Exerclses

CHAPTER 7 OENERIC DATA TYPES

7.1 Template Functlons

Template-Based Sort

7.2 Template Classes

Deflning a Template Class

Declaring Template Class Oblects

Defining Tcmplate Class Methods

7.3 Template Llst Classes

7.4 Infix Expression Evaluatlon

Wrltten Exerclses

Programming Exercises

CHAPTER 8 CLASSES AND DYNAMIC MEMORY

8.1 Pointers and Dynamic Data Structures

The Memory Allocation Operator New

Dynamlc Array Allocatlon

The Memory Deallocatlon Operator Delete

8.2 Dynamlcally Allocated Oblecte

Deallocatlng Object Data: The Destructor

8.3 Asslgnment and Inltlaltzatlon

Asslgnment Issues

Overloadlng the Assignment Operator

The Thls Polnter

Inltlallzatlon Issues

Creating a Copy Constructor

8.4 Safe Arrays

The Array Class

Memory Allocatlon for the Array Class

Array Bounds Checklng and the Overloaded 1] Operator

Convertlng an Object to a Polnter

Using the Array Class

8.5 A Strlng Class

String Class Implemenlation

8.6 Pattern Matehlng

The Flnd Process

Pattern Matchlng Algorlthm

Analysls of the Pattern Matchlng Algorlthm

8.7 Integral Sets

Sets of Integral Types

C++ Blt Handllng Operators

Representlng Set Elements

The Sleve of Eratosthenes

Set Class Implementatlon

Wrltten Exereises

Programmlng Exerclses

CHAPTER9 LINKIDLISTS

Descrlbing a Llnked Llst

Chapter 9 Overvlew

9.1 The Node Class

Declarlng a Node Type

Implementlng the Node Class

9.2 Bulldlng Llnked Llsts

Creating a Node

Insertlng a Node: InsertFront

Traversing a Llnked Llst

Insertlng a Node: InsertRear

Appllcatlon: Student Graduatlon Llst

Creatlng an Ordered Llst

Appllcation: Sortlng wlth Llnked Llsts

9.3 Deslgnlng a Llnked List Class

Llnked Llst Data Members

Llnked List Operatlons

9.4 The LlnkedLlst Class

9.5 Implementlng the LinkedList Class

9.6 Implementlng Collectlons wlth Llnked Lists

Llnked Queues

Implementlng Queue Methods

Llnked SeqLlst Class

Implementlng SeqLlst Data Access Methods

Appllcation: Comparlng SeqLlst Implementations

9.7 Case Study: A Prlnt Spooler

Implementing the Spooler Update Method

Spooler Evaluation Methods

9.8 Clreular Llsts

Clrcular Node Class Implementation

Appllcatlon: Solvlng the Josephus Problem

9.9 Doubly Llnked Lista

Appllcation: Doubly Linked List Sort

DNode Class Implementation

9.10 Case Study: Wlndow Management

The Wlndow Llst

WindowList Class Implementatlon

Writlen Exerclses

Programmlng Exercises

CHAPTCR 10 RECURSION

10.1 The Concept of Recurslon

Recurslve Deflnltions

Recursive Problems

10.2 Deslgnlng Recurslve Functlons

10.3 Recursive Code and the Runtlme Stack

The Runtlme Stack

10.4 Problem-Solvlng wlth Recurslon

Blnary Search

Combinatorics: The Commlttee Problem

Combinalorlcs: Permutations

Maze Handllng

Maze Class Implementatlon

10.5 Evaluatlng Recurslon

Wrlllen Exerclses

Programmlng Exerclses

CHAPTER 11 TREES

Tree Termlnology

Binary Trees

11.1 Binary Tree Structure

Deslgning a TreeNode Class

Bulldlng a Blnary Tree

11.2 Deslgnlng TreeNode Funclions

Recursive Tree Traversals

11.3 Uslng Tree Scan Algorlthms

Application: Vlsitlng Tree Nodes

Appllcation: Tree Prlnt

Appllcation: Copyfng and Delellng Trees

Applicatlon: Upright Tree Prlnting

11.4 Blnary Search Trees

The Key in a Blnary Search Tree Node

Operatlons on a Blnary Search Tree

Declaring a Blnary Search Tree ADT

11.5 LIsing Binary Search Trees

Duplicate Nodes

11.6 The BlnSTree Implementation

List Operations

11.7 Case Study: Concordance

Written Exercises

Programming Exercises

CHAPTER 12 INHERITANCE AND ABSTRACT CLASSES

12.1 A Vlew of Inheritance

Class Inherltance Termlnology

12.2 Inheritance In C++

Constructors and Derived Classes

What Cannot Be Inherited

12.3 Polymorphism and Vlrtual Functlons

Demonstratlng Polymorphlsm

Appllcation: Geometrlc Figures and Virtual Methods

Virtual Melhods and the Destructor

12.4 Abstract Base Classes

Abstract Base Class-List

Derlvlng SeqLlst from Abstract Base Class List

12.5 Iterators

The Iterator Abstract Base Class

Derlving Llst Iterators

Building the SeqLlst Iterator

Array Iterator

Applicatlon: Merglng Sorted Runs

Arraylterator Implementatlon

12.6 Ordered Llsts

OrderedLlst Class Implementatlon

12.7 Heterogeneous Llsts

Heterogeneous Arrays

Heterogeneous Linked Lists

Wrltten Exercises

Programmlng Exerelses

CHAPTER 13 ADVANCED NONLINEAR STRUCTURES

13.1 Array-Based Binary Trees

Appllcation: The Tournament Sort

13.2 Heaps

The Heap as a List

The Heap Class

13.3 Implementlng the Heap Class

Appllcatlon: Heap Sort

13.4 Priorlty Queues

Appllcation: Long Runs

13.5 AVLTrees

AVL Tree Nodes

13.6 The AVL Tree Class

Memory Allocation for the AVLTree

Evaluatlng AVL Trees

13.7 Trce Iterators

The Inorder Iterator

Inorderlteralor Class Implementatlon

Appllcation: TreeSort

13.8 Graphs

Connected Components

13.9 The Graph Class

Declaring a Graph ADT

Graph Class Implementatlon

Graph Traversals

Appllcatlons

Reachabillty and Warshall's Algorlthm

Writlen Exercises

Programmlng Exercises

CHAPTER 14 ORGANIZING COLLECTIONS

14.1 Baslc Array Sortlng Algorithms

The Selection Sort

The Bubble Sorl

The Insertion Sort

14.2 OuickSort

OulckSort Descrlption

OuickSort Algorithm

Comparison of Array Sort Algorithms

14.3 Hashing

Keys and a Hash Function

Hashing Functions

Other Hash Methods

Colllslon Resolutlon

14.4 Hash Table Class

Appllcation: Strlng Frequency

HashTable Class Implementation

HashTableIterator Class Implementation

14.5 The Performance of Searching Methods

14.6 Blnary Flles and External Data Operatlons

Binary Flles

The BlnFlle Class

External Flle Searching

External Flle Sort

Long Run MergeSort

14.7 Dictionarles

Writlen Exerclses

Programming Exercises

APPENDIX ANSWERS TO SELECTED EXERCISES

BIBLIOGRAPHY