readme

data structures, algorithms and Application书的源代码

Program 6.12  The classes Task and Job
file: job.h

Program 6.13  The class Machine
file: machine.h

Program 6.14  The class EventList
file: eventl.h

Program 6.15  Global variables used by the simulator
file: machine.cpp

Program 6.16  Code to input shop data
file: machine.cpp

Program 6.17  Initial loading of machines
file: machine.cpp

Program 6.18  Code to change the active job at a machine
file: machine.cpp

Program 6.19  Run all jobs through their machines
file: machine.cpp

Program 6.20  Move a job to the machine for its next task
file: machine.cpp

Program 6.21  Output the wait times at each machine
file: machine.cpp
_________________________________________________________________

CHAPTER 7

Program 7.1 The class SortedChain
file: sonode.h, sochain.h, sochain.cpp

Program 7.2 Search and delete members of SortedChain
file: sonode.h, sochain.h, sochain.cpp

Program 7.3 Insertion into a sorted chain
file: sonode.h, sochain.h, sochain.cpp

Program 7.4 The class SkipNode
file: skipnode.h

Program 7.5 The class SkipList
file: skip.h, skip.cpp

Program 7.6 Constructor and destructor
file: skip.h, skip.cpp

Program 7.7 Operator overloading for skip lists
file: skip.h, skip.cpp

Program 7.8 Skip list search functions
file: skip.h, skip.cpp

Program 7.9 Skip list insertion
file: skip.h, skip.cpp

Program 7.10 Deletion from a skip list
file: skip.h, skip.cpp

Program 7.11 C++ class definition for hash tables
file: hash.h, hash.cpp

Program 7.12 Constructor for HashTable
file: hash.h, hash.cpp

Program 7.13 Search functions
file: hash.h, hash.cpp

Program 7.14 Insertion into a hash table
file: hash.h, hash.cpp

Program 7.15 Chained hash table
file: chash.h, chash.cpp

Program 7.16 Establish I/O streams
file: compress.cpp

Program 7.17 Code output
file: compress.cpp, cdat (input), cdat.zzz (output)

Program 7.18 LZW compressor
file: compress.cpp, cdat (input), cdat.zzz (output)

Program 7.19 Function main for compression
file: compress.cpp, cdat (input), cdat.zzz (output)

Program 7.20 Establish I/O streams
file: decomp.cpp, cdat.zzz (input), cdat (output)

Program 7.21 Compute text(code)
file: decomp.cpp, cdat.zzz (input), cdat (output)

Program 7.22 Extracting codes from a compressed file
file: decomp.cpp, cdat.zzz (input), cdat (output)

Program 7.23 LZW decompressor
file: decomp.cpp, cdat.zzz (input), cdat (output)

Program 7.24 Main function for decompression
file: decomp.cpp, cdat.zzz (input), cdat (output)
_________________________________________________________________

CHAPTER 8

Program 8.1 Node class for linked binary trees
file: btnode1.h

Program 8.2 Preorder traversal
file: btraver.cpp

Program 8.3 Inorder traversal
file: btraver.cpp

Program 8.4 Postorder traversal
file: btraver.cpp

Program 8.5 Output fully parenthesized infix form
file: infix.h, infix.cpp

Program 8.6 Level-order traversal
file: btraver.cpp

Program 8.7 Binary tree class
file: btnode2.h, binary.h, binary.cpp

Program 8.8 Implementation of public members
file: binary.h, binary.cpp

Program 8.9 Pre-, In-, and Postorder
file: binary.h, binary.cpp

Program 8.10 Level-order traversal
file: binary.h, binary.cpp

Program 8.11 Application of the class BinaryTree
file: binary.cpp

Program 8.12 Height of a binary tree
file: binary.h, binary.cpp

Program 8.13 The class Booster
file: booster.h

Program 8.14 Place boosters and determine D for binary distribution trees
file: booster.cpp

Program 8.15 Simple tree solution to union-find problem
file: union3.cpp

Program 8.16 Unioning with the weight rule
file: wtunion.cpp

Program 8.17 Path compaction
file: compact.cpp
_________________________________________________________________

CHAPTER 9

Program 9.1 The class MaxHeap
file: maxheap.h, maxheap.cpp
(minheap.h, minheap.cpp ... min heap)

Program 9.2 Constructor for MaxHeap
file: maxheap.h, maxheap.cpp

Program 9.3 Insertion into a max heap
file: maxheap.h, maxheap.cpp

Program 9.4 Deletion from a max heap
file: maxheap.h, maxheap.cpp

Program 9.5 Initialize a non-empty max heap
file: maxheap.h

Program 9.6  Node class for height biased leftist tees
file: hbltnode.h

Program 9.7  The class MaxHBLT
file: maxhblt.h, maxhblt.cpp

Program 9.8  Merging two leftist trees
file: maxhblt.h, maxhblt.cpp

Program 9.9  Inserting into a max HBLT
file: maxhblt.h, maxhblt.cpp

Program 9.10  Deleting the max element from a max HBLT
file: maxhblt.h, maxhblt.cpp

Program 9.11  Initializing a max HBLT
file: maxhblt.h, maxhblt.cpp

Program 9.12 Heap sort
file: hsort.h, hsort.cpp

Program 9.13 The data types JobNode and MachineNode
file: lptnodes.h, lpt.cpp

Program 9.14 LPT schedule construction
file: lpt.cpp

Program 9.15 Construct a Huffman tree
file: huffman.cpp

Program 9.16 The class Huffman
file: huffman.h
_________________________________________________________________

CHAPTER 10

Program 10.1 Class definition for a winner tree
file: winner.h, winnode.h, winner.cpp, winner.dat

Program 10.2 Creating a winner tree
file: winner.h, winnode.h, winner.cpp, winner.dat

Program 10.3 Initializing a winner tree
file: winner.h, winnode.h, winner.cpp, winner.dat

Program 10.4 Playing matches to initialize the tree
file: winner.h, winnode.h, winner.cpp, winner.dat

Program 10.5 Replaying matches when element i changes
file: winner.h, winnode.h, winner.cpp, winner.dat

Program 10.6 First-fit bin packing
file: firstfit.cpp, firstfit.dat

Program 10.7 The function FirstFitPack
file: firstfit.cpp, firstfit.dat
_________________________________________________________________

CHAPTER 11

Program 11.1 Class definition for binary search trees
file: bst.h, datatype.h, bst.cpp

Program 11.2 Search a binary search tree
file: bst.h, datatype.h, bst.cpp

Program 11.3 Inserting into a binary search tree
file: bst.h, datatype.h, bst.cpp

Program 11.4 Deleting from a binary search tree
file: bst.h, datatype.h, bst.cpp

Program 11.5 New while loop for Program 11.3 to permit duplicates
file: dbst.h, datatype.h, dbst.cpp

Program 11.6 Simple histogramming program
file: histo.cpp, histo.dat

Program 11.7 Histogramming using a search tree
file: treehist.cpp, treehist.dat

Program 11.8 Finding the smallest key >= k
file: dbst.h, dbst.cpp

Program 11.9 Bin packing using best fit
file: bestfit.cpp, bestfit.dat

Program 11.10 Crossing distribution using a linear list
file: lcross.cpp
_________________________________________________________________

CHAPTER 12

Program 12.1 Cost-adjacency matrix for weighted directed graphs
file: awdgraph.h, awdgraph.cpp

Program 12.2 Cost-adjacency matrix for weighted graphs
file: awgraph.h, awgraph.cpp

Program 12.3 Adjacency-matrix representation of a digraph
file: adigraph.h, adigraph.cpp

Program 12.4 Adjacency-matrix representation of a graph
file: agraph.h, agraph.cpp

Program 12.5 Deleting from a chain by key
file: fchain.h

Program 12.6 Base class for linked-adjacency representations
file: lbase.h

Program 12.7 Linked-adjacency-list representation of a digraph
file: ldigraph.h, ldigraph.cpp

Program 12.8 The class LinkedGraph
file: lgraph.h, lgraph.cpp

Program 12.9 Linked-adjacency lists for weighted digraphs
file: lwdgraph.h, lwdgraph.cpp
(lwgraph.h, lwgraph.cpp ... linked weighted undirected graphs)

Program 12.10 The class GraphNode
file: gnode.h

Program 12.11 Iterators for adjacency-matrix representations
file: awd.h

Program 12.12 Additions to LinkedBase
file: lnbase.h

Program 12.13 Linked-adjacency-list iterators
file: ldg.h

Program 12.14 Linked-weighted-digraph iterators
file: lwdg.h

Program 12.15 The abstract class Network
file: network.h

Program 12.16 The abstract class AbstractList
file: abslist.h, absllist.h, abschain.h, absllist.cpp. abschain.cpp

Program 12.16 Breadth-first search
file: network.h, abfs.cpp, abfs.dat, dwbfs.cpp, dwbfs.dat

Program 12.17 Direct implementation of breadth-first search for
adjacency-matrix representations
file: awdbfs.h

Program 12.18 Direct BFS implementations for linked graphs and digraphs
file: ldgbfs.h

Program 12.19 Depth-first search
file: network.h, ldfs.cpp, ldfs.dat, adfs.cpp, adfs.dat

Program 12.20 Find a path in a graph
file: network.h, gpath.cpp, gpath.dat

Program 12.21 Determine whether an undirected graph is connected
file: undirect.h, connect.cpp, connect.dat

Program 12.22 Component labeling
file: undirect.h, glabel.cpp, glabel.dat
_________________________________________________________________

CHAPTER 13

Program 13.1  Loading containers
file: load.cpp

Program 13.2 Topological sorting
file: network.h, topo.cpp, topo.dat

Program 13.3 Definition of bin functions
file: undirect.h, cover.cpp, cover.dat

Program 13.4 Greedy cover construction
file: undirect.h, cover.cpp, cover.dat

Program 13.5 Shortest-path program
file: awd.h, short.cpp, short.dat

Program 13.6 The class WNetwork
file: wnetwork.h

Program 13.7 Data type for Kruskal's algorithm
file: edgenode.h

Program 13.8 C++ code for Kruskal's algorithm
file: unetwork.h, kruskal.cpp, kruskal.dat
_________________________________________________________________

CHAPTER 14

Program 14.1 Nonrecursive program to find the min and max
file: minmax3.cpp

Program 14.2 Tiling a defective chess board
file: chess.cpp, chess.dat

Program 14.3 Iterative merge sort
file: msort.h, msort.cpp

Program 14.4 Merge pass
file: msort.h, msort.cpp

Program 14.5 Merge
file: msort.h, msort.cpp

Program 14.6 Quick sort
file: qsort.h, qsort.cpp

Program 14.7 Find the kth element 
file: select.h, select.cpp

Program 14.8 Point classes
file: point.h

Program 14.9 Computing the distance between two points
file: closest.cpp, closest.dat

Program 14.10 Preprocess and invoke close
file: closest.cpp, closest.dat

Program 14.11 Computation of closest pair of points
file: closest.cpp, closest.dat
_________________________________________________________________

CHAPTER 15

Program 15.1 Recursive function for knapsack problem
file: rknap.cpp

Program 15.2 Computation of f and x
file: dknap.cpp

Program 15.3 Recursive computation of s, kay, and an optimal combining
file: rvbits.cpp

Program 15.4 Recursive computation avoiding recomputations
file: rcvbits.cpp

Program 15.5 Iterative computation of s and kay.
file: dvbits.cpp

Program 15.6 Recursive computation of c(i,j) and kay(i,j)
file: rmult.cpp

Program 15.7 Computing c(i,j) without recomputations
file: rcmult.cpp

Program 15.8 Iterative computation of c and kay
file: dmult.cpp

Program 15.9 Computation of c and kay
file: awd.h, allpairs.cpp, allpairs.dat

Program 15.10 Output a shortest path
file: awd.h, allpairs.cpp, allpairs.dat

Program 15.11 Finding a maximum non-crossing subset of nets
file: mns.cpp
_________________________________________________________________

CHAPTER 16

Program 16.1 First backtracking code for the loading problem
file: bloada.cpp

Program 16.2 Refinement of Program 16.1
file: bloadb.cpp

Program 16.3 Code to report best loading
file: bloadc.cpp

Program 16.4 Iterative loading code
file: bloadd.cpp

Program 16.5 The class Knap
file: bknap.cpp

Program 16.6 Knapsack bounding function
file: bknap.cpp

Program 16.7 Recursive function for 0/1 Knapsack problem
file: bknap.cpp

Program 16.8 The class Object
file: object.h

Program 16.9 Preprocessor for Program 16.7
file: bknap.cpp

Program 16.10 Max clique
file: ag.h, bclique.cpp, bclique.dat

Program 16.11 Preprocessor for traveling-salesperson backtracking
file: awd.h, btsp.cpp, btsp.dat

Program 16.12 Recursive backtracking for traveling salesperson
file: awd.h, btsp.cpp, btsp.dat

Program 16.13 Class definition of Board
file: bboard.cpp

Program 16.14 Search the permutation tree
file: bboard.cpp, bboard.dat

Program 16.15 Preprocessor for BestOrder (Program 16.14)
file: bboard.cpp, bboard.dat
_________________________________________________________________

CHAPTER 17

Program 17.1 FIFO branch-and-bound search for container loading
file: bbloada.cpp

Program 17.2 Improved version of Program 17.1
file: bbloadb.cpp

Program 17.3 The class QNode
file: qnode.h

Program 17.4 Branch-and-bound code that also computes the best subset
file: bbloadc.cpp

Program 17.5 bbnode and HeapNode class
file: bbnode.h

Program 17.6 Max profit branch and bound
file: bbloadd.cpp

Program 17.7 Max profit branch and bound for the 0/1 knapsack problem
file: bbnode2.h, bbknap.cpp

Program 17.8 Branch-and-bound max-clique code
file: ag.h, bbclique.cpp, bbclique.dat

Program 17.9 Least-cost branch and bound for traveling salesperson
file: awd.h, bbtsp.cpp, bbtsp.dat

Program 17.10 Least-cost branch and bound for the board-permutation problem
file: bbboard.cpp, bbboard.dat