C++: Classes and Data Structures

Description

Most books on data structures are filled with so many technical details (and lack thorough explanations) that the reading becomes difficult. This accessible, conversational presentation explores data structures concepts in clear language. KEY TOPICS: Assumes a basic knowledge of C++. Focuses on the client for all programs, classes, and data structures. Offers meaningful, relevant examples and worked examples throughout. Includes thoroughly tested code. Provides code for all examples. MARKET: A useful reference for anyone interested in learning more about programming.

 

Table of Contents

Preface IX

Chapter 1 Structs and Classes 1

1.1 Structs

1.2 Basic Class Concepts

1.3 Class Implementation

1.4 Testing a Class

1.5 Placing Function Definitions in the Class Definition (and Why We Shouldn’t Do It)

1.6 Commenting a Class

1.7 The Differences Between a Struct and a Class

Summary

Exercises

Chapter 2 Overloaded Operators, Class Templates, and Abstraction

2.1 Overloaded Operators

2.2 Using a Check Struct in the Checkbook Class

2.3 Class Templates

2.4 Classes and Abstraction

Summary

Exercises

Chapter 3 More about Classes

3.1 The const Specifier

3.2 Constructors

3.3 Class Modification

3.4 Modifying the Checkbook Class to Keep a History of Checks

Summary

Exercises

Chapter 4 Pointers and Dynamic Arrays

4.1 Pointers

4.2 The [ ] Operator

v

vi Contents

4.3 Dynamically Allocated Memory

4.4 Dynamic Arrays

4.5 The Delete Operator

4.6 Pointers to Objects

4.7 Running out of Heap Memory

4.8 Adjustable Arrays

Summary

Exercises

Chapter 5 An Array Class

5.1 Array Class Template

5.2 Using the Array Class

5.3 Destructors

5.4 The Copy Constructor 107

5.5 The Overloaded Assignment Operator Function

5.6 An Example 117

5.7 Advantages and Disadvantages of an Array Class

5.8 The Standard Template Library

Summary

Exercises

Chapter 6 Introduction to Object-Oriented Programming

6.1 Composition

*6.2 Inheritance

*6.3 Polymorphism

Summary

Exercises

Chapter 7 Methods for Making Data Structures

7.1 Using Arrays in Data Structures

7.2 Introduction to Linked Structures

7.3 Writing Code for Linked Lists

7.4 Arrays vs. Linked Lists

Summary

Exercises

Chapter 8 Stacks and Queues

8.1 The Stack ADT

8.2 Array Implementation of a Stack

8.3 Linked-List Implementation of a Stack

8.4 The Queue ADT

8.5 The Linked-List Implementation of a Queue

8.6 Other Linked-List Implementations of Queues

*8.7 Array Implementation of a Queue

Summary

Exercises

Contents vii

Chapter 9 Introduction to Time Complexities

9.1 Time Complexity Basics

9.2 The Constant Time Complexity

9.3 Big-Oh Notation

9.4 The Logarithmic Time Complexity

9.5 The Binary Search Algorithm

9.6 Computer Speed: Where Does It Really Come From?

9.7 Time Complexities of Data Structure Functions

*9.8 Amortized Analysis of Array Expansion and Contraction

Summary

Exercises

Chapter 10 The Linked List as a Data Structure

10.1 The List ADT

10.2 Using Key Values in Records of Information

10.3 Linked-List Implementation

10.4 Other Implementations

Summary

Exercises

Chapter 11 Hash Tables

11.1 The Hash Table ADT

11.2 Hash Functions and Hash Table Design

11.3 Implementation Issues for a Hash Table

11.4 Pointers to Functions

11.5 A Hash Table Implementation

11.6 Using the Hash Table Implementation

11.7 A Hash Table Implementation of a Doubly Linked List

Summary

Exercises

Chapter 12 Priority Queues, Trees, and Heaps

12.1 Priority Queue ADT

12.2 Priority Queue Design

12.3 Trees

12.4 Heaps

12.5 Using a One-Assignment Swap

12.6 A Heap Implementation of a Priority Queue (Array-Based)

*12.7 The Design of a Linked (Embedded) Heap

*12.8 A Linked (Embedded) Heap Implementation of a Priority Queue

Summary

Exercises

Chapter 13 Recursion

13.1 A Recursive Factorial Function

13.2 Guidelines for Writing Recursive Functions

ChilFMff.qxd 6/29/07 4:32 PM Page vii

viii Contents

13.3 Using Recursion on Linked Structures

13.4 Time Complexities of Recursive Functions

Summary

Exercises

Chapter 14 Introduction to Sorting Algorithms

14.1 Heapsort

14.2 Insertion Sort

14.3 Quicksort

14.4 Counting Sort

14.5 Sorting a Linked List

Summary

Exercises

Chapter 15 Other Data Structures

15.1 Binary Search Trees

15.2 Comparison of the BST with Other Data Structures

15.3 Graphs

15.4 Comparing Adjacency Matrices with Adjacency Lists

Summary

Exercises

Appendix A How to Compile and Work with Multiple-File Programs

Microsoft Visual Studio 2005 C++ Compiler

Compiling and Running Code Using Classes (Not Class Templates)

Compiling and Running Code Using Class Templates

Writing Code Using Microsoft Visual Studio 2005

Opening a Project in Microsoft Visual Studio 2005 That You Have Already Created

When Things Really Get Screwed Up

UNIX compilers

Index

描述

大多數關於資料結構的書籍都充滿了太多的技術細節（並且缺乏詳細的解釋），讓閱讀變得困難。這本易於理解、對話式的書籍以清晰的語言探索資料結構的概念。重點內容包括：假設讀者具備基本的 C++ 知識；專注於所有程式、類別和資料結構的客戶端；提供有意義且相關的例子和實例；包含經過全面測試的程式碼；為所有例子提供程式碼。適用於任何有興趣深入了解程式設計的人的參考書籍。

目錄

前言
第一章：結構和類別
1.1 結構
1.2 基本類別概念
1.3 類別實作
1.4 測試類別
1.5 在類別定義中放置函式定義（以及為什麼不應該這麼做）
1.6 為類別加上註解
1.7 結構和類別的差異
摘要
練習題

第二章：重載運算子、類別模板和抽象
2.1 重載運算子
2.2 在支票簿類別中使用檢查結構
2.3 類別模板
2.4 類別和抽象