内容简介

本书从面向对象的视角介绍数据结构。内容从数据结构的基本原

理到面向对象程序设计的方法。书内使用适应面极广的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

SeqLlst CLASS SPECIFICATION

DECIARATION

class SeqList

{

private:

// list storage array and number of current list elements

DataType listitem[ARRAYSIZE];

int size;

public:

// constructor

SeqList(void);

// list access methods

int ListSize(void) const;

int ListEmpty(void) const;

int Find (DataType& item) const;

DataType GetData (int pos) const;

// list modification methods

void Insert (const DataType& item);

void Delete (const DataType& item);

DataType DeleteFront (void);

void ClearList (void);



DESCRIPTION

The LlstSlze. ListEmpty, Flnd. and GetData methods conclude wlth the word

"const" afler the function declaration. They are called constant functlons because

they do nol alter the state of the list. The functions Insert, Delete have the word

"const" as part of the parameter llst. Thls C++ syntax passes a reference to

the item bul specifies that the value of Ihe Item is not altered.

C++ uscs a slmple synlax for declaring a derived class. In the header, the base

class Is specified after the colon (:). The following Is a declaratlon forthe OrderedLlst

class. The specincs are discussed In Chapter 12. whlch provides a fornlal Introductlon

to inheritance.

OrderedList CLASS SPCCIFICATION

DECIARATION

class OrderedList: public SeqList // inherit the SeqList class

public:

OrderedList (void); // initialize base class to

// create an empty list

void Insert (const DataType& item); // insert item in order

};



DESCRIPTION

Insert overrldes the base class method of the same name. It traverses the

list inherlted from the base class and Inserls the Item at the posltlon that

malntalns ordering.



Applications with Class Inheritance 1.5

The concept of class Inherltance has Important appllcatlons In graphlcal user inter-

face (GUI) programmlng and data base systems. The graphlcal appllcatlons focus

on wlndows. menus, dlalog boxes, and so forth. A basic window Is a data structure

with data and operatlons that are common to all types of wlndows. The operatlons

Include openlng a window, creatlng or changlng a wlndow title, settlng up scroll

bars and drag reglons, and so forth. GUI appllcatlons conslst of dlalog classes. menu

classes. text wlndow classes, and so forth that inherlt the baslc structure and

operatlons from the wlndow base class. For Instance, the following class hlerarchy

includes a Dlalog class and a TextEdlt class that are derlved from the Wlndow class.

Window Class

Dialog Class TextEdit Class

Flgure 1.7 lllustrates a GUI appllc'atlon wlth a dlalog and text wlndow.

The example ofthe window class lllustrates slngle Inherltance In whlch a derived

class has exactly one base class. Wlth multlple Inherllancc, however, the class Is

derived from two or more base classes. Some GUI appllcatlons use thls feature. A

word processlng program comblnes an editor wlth a vlew manager to llst text in a

wlndow. An edltor reads a character stream and makes changes by insertlng and

deletlng strlngs and embeddlng format Informatlon. The vlew manager Is responslble

for copylng text to a screen uslng font and wlndow Intormatlon. A screen editor

can be deflned as a derived class that uses an edltor class and a vlew class as

base classes.