Source Code for Data Structures and Problem Solving Using Java (Second Edition)
Author: Mark A. Weiss

# Source Code for Data Structures and Problem Solving Using Java, Second Edition

LAST UPDATE: September 1, 2001
BUG REPORTS ARE APPRECIATED!!

Here is the source code for Data Structures and Algorithm Analysis in Java (Second Edition), by Mark Allen Weiss. The materials here are copyrighted. I have successfully compiled and tested the programs under JDK 1.3.

## Organization of Files

1. Most of the general, standalone, code is in the root directory.
2. There is an implementation of a large subset of java.util in package `weiss.util`. Its purpose is to illustrate how the concepts are used in an actual library implementation. This can be found in the `weiss\util` folder. Some of the sample code imports classes in `weiss.util`, but you can freely replace all occurrences of `weiss.util` with `java.util`. Needless to say, everything in `weiss.util` has a name clash with `java.util`, so you should not use wild-card import directives. These files are displayed in BOLDFACE font.
3. The package weiss.nonstandard, in the weiss\nonstandard folder, contains nonstandard implementations of various data structures. The code is generally simpler that the code in the Java 1.2 Collections API, and there are occasional name clashes (e.g. `LinkedList` and `Stack`). This package also contains priority queue implementations, since that is not part of the Java 1.2 Collections API. These files are display in ITALICS font.

### CLASSPATH Info

The code in the root directory should automatically compile if there is no `CLASSPATH`. Other code will be trickier to compile/run unless you use full names relative to the root directory. Otherwise, the easiest fix is to make sure that the root directory (i.e. the directory in which the `weiss` folder is found) is on your `CLASSPATH`, along with`.`. Let us assume you have extracted everything into the `bookcode` folder.

- For MS-DOS: `set CLASSPATH=C:\bookcode;.`
- For Unix: `setenv CLASSPATH bookcode:.`

Note that case-sensitivity may matter, and there is a difference between colons and semicolons.
If you are using an IDE, you will need to update the `CLASSPATH` using the IDE's own mechanism.

#### Jar files

An alternative is to install these two jar files (wutil.jar and wnonstandard.jar) in the Java extensions directory. A typical location would be `C:\jdk1.3.0\jre\lib\ext`. Once this is done, you can run any of the programs that require `weiss.util` or `weiss.nonstandard` from pretty much any location. (This is every program in the main distribution directory, except `MyContainerTest.java`).

### Complete Bundle

code.zip (not available, but winzip reads tar files)
code.tar
code.tar.Z

### Package Documentation

docs
docs.tar
docs.tar.Z

### Chapter 1: Basic Java

FirstProgram.java
MinTest.java
OperatorTest.java

### Chapter 2: References

RandomNumbers.java
ReadStrings.java
ReadStringsWithArrayList.java
MatrixDemo.java
Echo.java
DivideByTwo.java
MaxTest.java
ListFiles.java
DoubleSpace.java

### Chapter 3: Classes

IntCell.java TestIntCell.java
Date.java
Exiting.java
Ticket.java
Squares.java
StringArrayList.java ReadStringsWithStringArrayList.java

### Chapter 4: Inheritance

ConcurrentModificationException.java EmptyStackException.java NoSuchElementException.java
DecoratorDemo.java
PersonDemo.java
Shape.java Circle.java Rectangle.java Square.java ShapeDemo.java
MemoryCell.java TestMemoryCell.java
SimpleArrayList.java ReadStringsWithSimpleArrayList.java
WrapperDemo.java
StorageCellDemo.java
FindMaxDemo.java
Comparator.java SimpleRectangle.java CompareTest.java CompareTestInner1.java CompareTestInner2.java CompareTestInner3.java
StaticParamsDemo.java
BadEqualsDemo.java

### Chapter 5: Running Times

MaxSumTest.java
BinarySearch.java

### Chapter 6: The Collections API

Stack.java
UndeflowException.java
Queue.java
Collection.java
Iterator.java
Collections.java
Arrays.java
List.java
ListIterator.java
TestArrayList.java
Set.java
SortedSet.java
TreeSetDemo.java
IteratorTest.java
EqualsWithInheritance.java
Map.java MapDemo.java
PriorityQueue.java
PriorityQueueDemo.java

### Chapter 7: Recursion

RecSum.java
PrintInt.java
Factorial.java
BinarySearchRecursive.java
Ruler.java
FractalStar.java
Numerical.java RSA.java
MaxSumTest.java
MakeChange.java
Best.java TicTacToeSlow.java TicTacMainSlow.java

### Chapter 8: Sorting

DuplicateTest.java
Sort.java TestSort.java

### Chapter 9: Randomization

Random.java
Numerical.java RSA.java

### Chapter 10: Fun and Games

WordSearch.java puz.txt
Best.java TicTacToe.java TicTacMain.java

### Chapter 11: Applications of Stacks -- Compilers and Parsing

Tokenizer.java Balance.java
Evaluator.java

### Chapter 12: Utilities

Hzip.java HZIPInputStream.java HZIPOutputStream.java
Tokenizer.java Xref.java

### Chapter 13: Simulation

Josephus.java
ModemSim.java

### Chapter 14: Shortest Path Algorithms

Graph.java graph1.txt graph2.txt graph3.txt

### Chapter 15: Inner Classes and ArrayList Implementation

MyContainerTest.java Iterator.java MyContainer.java
AbstractCollection.java
ArrayList.java

### Chapter 16: Stacks

UnderflowException.java
ArrayStack.java
ListNode.java
ListStack.java
ArrayQueue.java
ListQueue.java
EmptyStackException Stack.java

### Chapter 17: Linked Lists

ListNode.java LinkedList.java
LinkedListIterator.java
SortedLinkedList.java
LinkedList.java

### Chapter 18: Trees

BinaryNode.java BinaryTree.java
TestTreeIterators.java

### Chapter 19: Search Trees

DuplicateItemException.java BinaryNode.java BinarySearchTree.java
BinarySearchTreeWithRank.java
Rotations.java
RedBlackTree.java
AATree.java
Set.java TreeSet.java
MapImpl.java TreeMap.java

### Chapter 20: Hash Tables

HashSet.java
MapImpl.java HashMap.java

### Chapter 21: Heaps

BinaryHeap.java

### Chapter 22: Splay Trees

SplayTree.java

### Chapter 23: Pairing Heaps

IllegalValueException.java PairingHeap.java

### Chapter 24: Disjoint Sets

DisjointSetsSlow.java
DisjointSets.java

### Appendix D: Swing

BasicGUI.java
BorderTest.java