readme

data structures, algorithms and Application书的源代码

LIST OF ALL C++ PROGRAMS

All programs have been tested using Borland C++ version 5.01 for Windows 95.

For programs that require input to be provided, sample input is given in the
corresponding .dat file.  This sample input is NOT intended to constitute
an adequate test set.  For information on designing test data, see
Section 1.5 of the text.

The output generated by each program is given in the corresponding .out file.

CHAPTER 1

Program 1.1 Compute an integer expression
file: abc1.cpp

Program 1.2 Compute a floating point expression
file: abc2.cpp

Program 1.3 Compute an expression using a template function
file: abc3.cpp

Program 1.4 Compute an expression using reference parameters
file: abc4.cpp

Program 1.5 Compute an expression using const reference parameters
file: abc5.cpp

Program 1.6 A more general version of Program 1.5
file: abc6.cpp

Program 1.7 Recursive function to compute n!
file: fact.cpp

Program 1.8 Add a[0:n-1]
file: sum.cpp

Program 1.9 Recursive code to add a[0:n-1]
file: rsum.cpp

Program 1.10 Recursive function for permutations
file: perm.cpp

Program 1.11 Swap two values
file: swap.h, swap.cpp

Program 1.12 Allocate memory for a two-dimensional array
file: make2da,h, make2da.cpp

Program 1.13 Make a two-dimensional array but do not catch exceptions
file: make2db,h, make2db.cpp

Program 1.14 Free the memory allocated by Make2DArray
file: del2d.h, del2d.cpp

Program 1.15  Declaration of the class Currency
file: curr1.h, curr1.cpp

Program 1.16  Constructor for Currency
file: curr1.h, curr1.cpp

Program 1.17  Setting the private data members
file: curr1.h, curr1.cpp

Program 1.18  Adding two currency values
file: curr1.h, curr1.cpp

Program 1.19  Increment and Output
file: curr1.h, curr1.cpp

Program 1.20  Application of the class \f(CWCurrency\fR
file: curr1.h, curr1.cpp

Program 1.21  New declaration of the class Currency
file: curr2.h, curr2.cpp

Program 1.22  New constructor and set codes
file: curr2.h, curr2.cpp

Program 1.23  New code for \f(CWAdd\fR and \f(CWlOutput\fR
file: curr2.h, curr2.cpp

Program 1.24  Class declaration using operator overloading
file: curr3.h, curr3.cpp

orPgram 1.25 Codes for \f(CW+\fR, \f(CWOutput\fR, and \f(CW<<\fR
file: curr3.h, curr3.cpp

Program 1.26  Using overloaded operators
file: curr3.h, curr3.cpp

Program 1.27  Exception class BadInitializers
file: xcept.h

Program 1.28  Throwing an exception
file: curr4.h, curr4.cpp

Program 1.29  Overloading the friend `<<'
file: curr5.h, curr5.cpp

Program 1.30  Compute and output the roots of a quadratic
file: roots.cpp

Program 1.31  Finding the largest element
file: max.cpp
_________________________________________________________________

CHAPTER 2

Program 2.1 Sequential search
file: ssearch1.cpp

Program 2.2 Recursive sequential search function
file: ssearch2.cpp

Program 2.3 A function to evaluate a polynomial
file: poly.cpp

Program 2.4 Horner's rule for polynomial evaluation
file: horner.cpp

Program 2.5 Computing ranks
file: rank.cpp

Program 2.6 Rearranging elements using an additional array
file: rsort1.cpp

Program 2.7 Selection sort
file: selsort1.cpp

Program 2.8 A bubbling pass
file: bubble1.cpp

Program 2.9 Bubble sort
file: bubble1.cpp

Program 2.10 Inserting into a sorted array
file: insert.cpp

Program 2.11 In-place rearrangement of elements
file: rsort2.cpp

Program 2.12 Early terminating version of selection sort
file: selsort2.cpp

Program 2.13 Early terminating bubble sort
file: bubble2.cpp

Program 2.14 Insertion sort
file: insort1.cpp

Program 2.15 Another version of insertion sort
file: insort.h, insort2.cpp

Program 2.16 Counting steps in Program 1.8
file: sumct1.cpp

Program 2.17 Simplified version of Program 2.16
file: sumct2.cpp

Program 2.18 Counting steps in Program 1.9
file: rsumct.cpp

Program 2.19 Matrix addition
file: madd.cpp

Program 2.20 Counting steps in Program 2.19
file: maddct1.cpp

Program 2.21 Simplified version of Program 2.20
file: maddct2.cpp

Program 2.22 Matrix transpose
file: trans.cpp

Program 2.23 Inefficient prefix sums
file: inef.cpp

Program 2.24 Multiply two n x n matrices
file: mmult1.cpp

Program 2.25 Multiply an m x n and an n x p matrix
file: mmult2.cpp

Program 2.26 Finding the minimum and maximum
file: minmax1.cpp

Program 2.27 Another function to find the minimum and maximum
file: minmax2.cpp

Program 2.28 Another sequential search function
file: ssearch3.cpp

Program 2.29 Function for Exercise
file: d.cpp

Program 2.30 Binary search
file: bsearch.cpp

Program 2.31 Program to obtain worst case run times for insertion sort
file: time1.cpp

Program 2.32 Program to obtain times with an accuracy of 10%
file: time2.cpp

Program 2.33 Inaccurate way to time InsertionSort
file: time4.cpp
_________________________________________________________________

CHAPTER 3

Program 3.1 Formula-based class LinearList
file: llist.h, llist.cpp

Program 3.2  Cause new to throw NoMem exceptions instead of xalloc exceptions
file: xcept.h

Program 3.3 Elementary list operations
file: llist.h, llist.cpp

Program 3.4 Deletion from a linear list
file: llist.h, llist.cpp

Program 3.5 Insertion into a linear list
file: llist.h, llist.cpp

Program 3.6 Inserting a list into the output stream
file: llist.h, llist.cpp

Program 3.7 Example using the class LinearList
file: llist.cpp, llist.cpp

Program 3.8 Class definitions for a chain
file: cnode.h, chain.h, chain.cpp

Program 3.9 Delete all nodes in a chain
file: chain.h, chain.cpp

Program 3.10 Determine the length of a chain
file: chain.h, chain.cpp

Program 3.11 Find the kth element of a chain
file: chain.h, chain.cpp

Program 3.12 Search a chain
file: chain.h, chain.cpp

Program 3.13 Output a chain
file: chain.h, chain.cpp

Program 3.14 Deletion from a chain
file: chain.h, chain.cpp

Program 3.15 Insert into a chain
file: chain.h, chain.cpp

Program 3.16 Deleting the nodes in a chain
file: echain.h, echain.cpp

Program 3.17 Add an element to the right end
file: echain.h, echain.cpp

Program 3.18 Chain iterator class
file: citer.h, citer.cpp

Program 3.19 Outputting the integer chain X using a chain iterator
file: chainout.cpp

Program 3.20 Searching a circular linked list with a head node
file: clist.h

Program 3.21 Class definition for doubly linked lists
file: dnode.h, double.h

Program 3.22 Class definition for an indirectly addressed list
file: indlist.h, indlist.cpp

Program 3.23 Constructor and destructor for indirect addressing
file: indlist.h, indlist.cpp

Program 3.24 Find operation for indirect lists
file: indlist.h, indlist.cpp

Program 3.25 Deletion from an indirect list
file: indlist.h, indlist.cpp

Program 3.26 Insertion into an indirectly addressed list
file: indlist.h, indlist.cpp

Program 3.27 Class definition for simulated pointers
file: snode.h, simul.h, simul.cpp

Program 3.28 Initialize available space list
file: simul.h, simul.cpp

Program 3.29 Allocate a node using simulated pointers
file: simul.h, simul.cpp

Program 3.30 Deallocate a node with simulated pointers
file: simul.h, simul.cpp

Program 3.31 Initialization of dual available space list
file: dsimul.h, dsimul.cpp

Program 3.32 Dual available space list version of Allocate
file: dsimul.h, dsimul.cpp

Program 3.33 Deallocate a circular list
file: dsimul.h, dsimul.cpp

Program 3.34 Class definition for simulated chains
file: schain.h, schain.cpp

Program 3.35 Destructor and length using simulated pointers
file: schain.h, schain.cpp

Program 3.36 Find using simulated pointers
file: schain.h, schain.cpp

Program 3.37 Delete using simulated pointers
file: schain.h, schain.cpp

Program 3.38 Insert using simulated pointers
file: schain.h, schain.cpp

Program 3.39 Using a simulated chain
file: schain.cpp

Program 3.40 Possible node class for bin sort
file binnode1.h

Program 3.41 An alternative way to handle operator overloading
file binnode2.h

Program 3.42 Another way to handle operator overloading
file binnode3.h

Program 3.43 Bin sort using class definitions
file: binsort1.cpp

Program 3.44 Bin sort as a class member of Chain
file: nchain.h, binsort2.cpp

Program 3.45 Sorting on different fields
file: binnode4.h, mchain.h, binsort3.cpp

Program 3.46 Online equivalence class functions using arrays
file: union1.cpp

Program 3.47 Online equivalence class functions using chains
file: union2.cpp
_________________________________________________________________

CHAPTER 4

Program 4.1  A one-dimensional array class
file: array1d.h, array1d.cpp

Program 4.2  Constructors for a one-dimensional array
file: array1d.h, array1d.cpp

Program 4.3  Overloading the array indexing operator
file: array1d.h, array1d.cpp

Program 4.4  Overloading the assignment operator
file: array1d.h, array1d.cpp

Program 4.5  Overloading binary minus, unary minus, and increment
file: array2d.h, array2d.cpp

Program 4.6  A class for two-dimensional arrays
file: array2d.h, array2d.cpp

Program 4.7  Constructor for a two-dimensional array
file: array2d.h, array2d.cpp

Program 4.8  Copy constructor for two-dimensional arrays
file: array2d.h, array2d.cpp

Program 4.9  Overloading [] for a two-dimensional array
file: array2d.h, array2d.cpp

Program 4.10  Subtraction
file: array2d.h, array2d.cpp

Program 4.11  Matrix multiplication
file: array2d.h, array2d.cpp

Program 4.12  The class Matrix
file: matrix.h, matrix.cpp

Program 4.13  Matrix constructor
file: matrix.h, matrix.cpp

Program 4.14  Indexing a matrix
file: matrix.h, matrix.cpp

Program 4.15  Matrix subtraction
file: matrix.h, matrix.cpp

Program 4.16  Matrix multiplication
file: matrix.h, matrix.cpp

Program 4.17 The class DiagonalMatrix
file: diag.h, diag.cpp

Program 4.18 The class TridiagonalMatrix
file: tridiag.h, tridiag.cpp

Program 4.19 The class LowerMatrix
file: lower.h, lower.cpp

Program 4.20 The class SparseMatrix
file: smatrix.h, smatrix.cpp, smatrix.dat

Program 4.21 SparseMatrix constructor
file: smatrix.h, smatrix.cpp, smatrix.dat

Program 4.22 SparseMatrix input and output codes
file: smatrix.h, smatrix.cpp, smatrix.dat

Program 4.23 Transposing a sparse matrix
file: smatrix.h, smatrix.cpp, smatrix.dat

Program 4.24 Appending a non-zero term
file: smatrix.h, smatrix.cpp, smatrix.dat

Program 4.25 Adding two sparse matrices
file: smatrix.h, smatrix.cpp, smatrix.dat

Program 4.26 Chain nodes used in sparse matrix representation
file: matnodes.h, lsmatrix.h, lsmatrix.cpp, lsmatrix.dat

Program 4.27 Class definition for a linked sparse matrix
file: lsmatrix.h, lsmatrix.cpp, lsmatrix.dat

Program 4.28 Input a sparse matrix
file: lsmatrix.h, lsmatrix.cpp, lsmatrix.dat

Program 4.29 Output a sparse matrix
file: lsmatrix.h, lsmatrix.cpp, lsmatrix.dat

Program 4.30 Transpose a sparse matrix
file: lsmatrix.h, lsmatrix.cpp, lsmatrix.dat
_________________________________________________________________

CHAPTER 5

Program 5.1 Formula-based class Stack
file: llista.h, dstack.h, dstack.cpp

Program 5.2 Customized version of Stack
file: stack.h, stack.cpp

Program 5.3 Linked stack derived from Chain
file: dlstack.h, dlstack.cpp

Program 5.4 Customized linked stack
file: node.h, lstack.h, lstack.cpp

Program 5.5 Program to output matched parentheses
file: paren.cpp, paren.dat

Program 5.6 Recursive function for Towers of Hanoi
file: hanoi1.cpp

Program 5.7 Towers of Hanoi using stacks
file: hanoi2.cpp

Program 5.8 Railroad car rearrangement program
file: rail1.cpp

Program 5.9 Output function used in Program 5.8
file: rail1.cpp

Program 5.10 Hold function used by Program 5.8
file: rail1.cpp

Program 5.11 Switch box routing
file: switch.cpp, switch.dat

Program 5.12 Offline equivalence class program
file: equiv.cpp, equiv.dat

Program 5.13 Code to find a path in a maze
file: position.h, maze.cpp, maze.dat
_________________________________________________________________

CHAPTER 6

Program 6.1 Formula-based class Queue
file: queue.h, queue.cpp

Program 6.2 Queue functions using formula-based representation
file: queue.h, queue.cpp

Program 6.3 Queue functions using formula-based representation
file: queue.h, queue.cpp

Program 6.4 Class definition for a linked queue
file: node.h, lqueue.h, lqueue.cpp

Program 6.5 Linked queue function implementations
file: lqueue.h, lqueue.cpp

Program 6.6 Linked queue function implementations
file: lqueue.h, lqueue.cpp

Program 6.7 Rearranging cars using queues
file: rail2.cpp

Program 6.8 Rearranging cars without the use of a queue
file: rail3.cpp

Program 6.9 Find a wire route
file: wire.cpp, wire.dat

Program 6.10 Component labeling
file: image.cpp, image.dat

Program 6.11  Main function for machine shop simulation
file: machine.cpp, machine.dat