Data Structures in Java: A Laboratory Course

Sandra Andersen9780763718169, 0-7637-1816-5

A lab manual that walks computer science students through the implementation of data structures and the application of algorithms. It assumes students have a background in C, C++, or Java. The text introduces the use of classes to implement a simple ADT and also covers more complex Java language features (e.g., abstract window toolkit, cloning, inheritance). The author teaches at Concordia College-Moorehead, MN.

---

Table of contents :
Cover……Page 1
Preface……Page 6
Contents……Page 12
Logbook ADT……Page 17
Logbook ADT……Page 18
LABORATORY 1: Cover Sheet……Page 21
LABORATORY 1: Prelab Exercise……Page 23
Test Plan for Test1……Page 29
Test Plan for Test2……Page 30
LABORATORY 1: In-lab Exercise 1……Page 31
Test Plan for Test3……Page 32
LABORATORY 1: In-lab Exercise 2……Page 33
Test Plan for Test4……Page 34
LABORATORY 1: In-lab Exercise 3……Page 35
Test Plan for Test5……Page 36
LABORATORY 1: Postlab Exercise 1……Page 37
LABORATORY 1: Postlab Exercise 2……Page 38
Point List ADT……Page 39
Point List ADT……Page 40
LABORATORY 2: Cover Sheet……Page 43
LABORATORY 2: Prelab Exercise……Page 45
LABORATORY 2: Bridge Exercise……Page 50
Test Plan for the Operations in the Point List ADT……Page 52
LABORATORY 2: In-lab Exercise 1……Page 53
Test Plan for the Curve Drawing Program……Page 54
LABORATORY 2: In-lab Exercise 2……Page 55
Test Plan for the Curve Drawing Program……Page 58
LABORATORY 2: In-lab Exercise 3……Page 59
Test Plan for the insertBeginning Operation……Page 60
LABORATORY 2: Postlab Exercise 1……Page 61
LABORATORY 2: Postlab Exercise 2……Page 62
String ADT……Page 63
STRING ADT (a built-in class)……Page 65
LABORATORY 3: Cover Sheet……Page 69
LABORATORY 3: Prelab Exercise……Page 71
Test Plan for Test1……Page 73
Test Plan for Test2……Page 74
Test Plan for Test4……Page 75
Test Plan for Test5……Page 76
LABORATORY 3: In-lab Exercise 1……Page 77
Test Plan for the Lexical Analysis Program……Page 80
LABORATORY 3: In-lab Exercise 2……Page 81
Test Plan for the Hangman Program……Page 85
LABORATORY 3: In-lab Exercise 3……Page 86
LABORATORY 3: Postlab Exercise 1……Page 89
LABORATORY 3: Postlab Exercise 2……Page 90
Array Implementation of the List ADT……Page 93
List ADT……Page 95
LABORATORY 4: Cover Sheet……Page 99
LABORATORY 4: Prelab Exercise……Page 101
LABORATORY 4: Bridge Exercise……Page 104
Test Plan for the Operations in the List ADT……Page 106
LABORATORY 4: In-lab Exercise 1……Page 108
Test Plan for the countBases() Method……Page 109
LABORATORY 4: In-lab Exercise 2……Page 110
Test Plan for the moveToNth Operation……Page 111
LABORATORY 4: In-lab Exercise 3……Page 112
Test Plan for the Þnd Operation……Page 113
LABORATORY 4: Postlab Exercise 1……Page 115
LABORATORY 4: Postlab Exercise 2……Page 117
Stack ADT……Page 119
Stack ADT……Page 120
LABORATORY 5: Cover Sheet……Page 123
LABORATORY 5: Prelab Exercise……Page 125
LABORATORY 5: Bridge Exercise……Page 130
Test Plan for the Operations in the Stack ADT……Page 131
LABORATORY 5: In-lab Exercise 1……Page 132
LABORATORY 5: In-lab Exercise 2……Page 133
Test Plan for the Copy Constructor and clone Operation……Page 135
LABORATORY 5: In-lab Exercise 3……Page 136
Evaluation Program……Page 139
LABORATORY 5: Postlab Exercise 1……Page 141
LABORATORY 5: Postlab Exercise 2……Page 144
Queue ADT……Page 145
Queue ADT……Page 146
LABORATORY 6: Cover Sheet……Page 149
LABORATORY 6: Prelab Exercise……Page 151
LABORATORY 6: Bridge Exercise……Page 154
Test Plan for the Operations in the Queue ADT……Page 155
LABORATORY 6: In-lab Exercise 1……Page 156
Test Plan for the putFront and getRear Operations……Page 157
LABORATORY 6: In-lab Exercise 2……Page 158
Test Plan for the Length Operation……Page 159
LABORATORY 6: In-lab Exercise 3……Page 160
LABORATORY 6: Postlab Exercise 1……Page 163
LABORATORY 6: Postlab Exercise 2……Page 164
List ADT……Page 165
LABORATORY 7: Cover Sheet……Page 169
LABORATORY 7: Prelab Exercise……Page 171
LABORATORY 7: Bridge Exercise……Page 173
Test Plan for the Operations in the List ADT……Page 174
LABORATORY 7: In-lab Exercise 1……Page 176
Test Plan for the moveToBeginning Operation……Page 177
LABORATORY 7: In-lab Exercise 2……Page 178
Test Plan for the insertBefore Operation……Page 179
LABORATORY 7: In-lab Exercise 3……Page 180
Test Plan for the Slide Show Program……Page 181
LABORATORY 7: Postlab Exercise 1……Page 183
LABORATORY 7: Postlab Exercise 2……Page 185
LIST ADT……Page 187
LABORATORY 8: Cover Sheet……Page 191
LABORATORY 8: Prelab Exercise……Page 193
LABORATORY 8: Bridge Exercise……Page 195
Test Plan for the Operations in the List ADT……Page 196
LABORATORY 8: In-lab Exercise 1……Page 197
Test Plan for the reverse Operation……Page 198
LABORATORY 8: In-lab Exercise 2……Page 199
Test Plan for the length and position Operations……Page 201
Anagram Puzzle ADT……Page 202
Test Plan for the Anagram Puzzle Program……Page 204
LABORATORY 8: Postlab Exercise 1……Page 205
LABORATORY 8: Postlab Exercise 2……Page 207
Ordered List ADT……Page 209
LABORATORY 9: Cover Sheet……Page 213
LABORATORY 9: Prelab Exercise……Page 215
LABORATORY 9: Bridge Exercise……Page 219
Test Plan for the Operations in the Ordered List ADT……Page 220
Laboratory 9: In-lab Exercise 1……Page 221
Test Plan for the merge Operation……Page 222
LABORATORY 9: In-lab Exercise 2……Page 223
Test Plan for the subset Operation……Page 224
LABORATORY 9: In-lab Exercise 3……Page 225
Test Plan for the Message Processing Program……Page 226
Array Implementation of the insert Operation……Page 227
Linked List Implementation of the insert Operation……Page 228
LABORATORY 9: Postlab Exercise 2……Page 229
Recursion with Linked Lists……Page 231
LABORATORY 10: Cover Sheet……Page 237
LABORATORY 10: Prelab Exercise……Page 239
LABORATORY 10: Bridge Exercise……Page 250
LABORATORY 10: In-lab Exercise 1……Page 254
Test Plan for the iterReverse() Method……Page 255
Test Plan for the stackWriteMirror() Method……Page 257
LABORATORY 10: In-lab Exercise 2……Page 258
Test Plan for the aBeforeb() Method……Page 259
LABORATORY 10: In-lab Exercise 3……Page 260
Test Plan for the cRemove() Method……Page 261
LABORATORY 10: Postlab Exercise 1……Page 263
LABORATORY 10: Postlab Exercise 2……Page 264
Expression Tree ADT……Page 265
Expression Tree ADT……Page 266
LABORATORY 11: Cover Sheet……Page 271
LABORATORY 11: Prelab Exercise……Page 273
LABORATORY 11: Bridge Exercise……Page 275
Test Plan for the Operations in the Expression Tree ADT……Page 276
LABORATORY 11: In-lab Exercise 1……Page 277
Test Plan for the Copy Constructor and clone Operation……Page 279
LABORATORY 11: In-lab Exercise 2……Page 280
Test Plan for the commute Operation……Page 281
LABORATORY 11: In-lab Exercise 3……Page 282
Tree ADT……Page 284
LABORATORY 11: Postlab Exercise 1……Page 287
LABORATORY 11: Postlab Exercise 2……Page 289
Binary Search Tree ADT……Page 291
Binary Search Tree ADT……Page 292
LABORATORY 12: Cover Sheet……Page 295
Laboratory 12: Prelab Exercise……Page 297
Laboratory 12: Bridge Exercise……Page 299
ADT……Page 300
Laboratory 12: In-lab Exercise 1……Page 301
Test Plan for the height Operation……Page 302
Laboratory 12: In-lab Exercise 2……Page 303
Test Plan for the writeLessThan Operation……Page 304
Laboratory 12: In-lab Exercise 3……Page 305
Test Plan for the Indexed Accounts Database Program……Page 309
Laboratory 12: Postlab Exercise 1……Page 311
Laboratory 12: Postlab Exercise 2……Page 312
Heap ADT……Page 315
Heap ADT……Page 317
LABORATORY 13: Cover Sheet……Page 321
LABORATORY 13: Prelab Exercise……Page 323
LABORATORY 13: Bridge Exercise……Page 325
Test Plan for the Operations in the Heap ADT……Page 326
LABORATORY 13: In-lab Exercise 1……Page 327
Test Plan for the writeLevels Operation……Page 328
LABORATORY 13: In-lab Exercise 2……Page 329
Test Plan for the heapSort() Method……Page 333
Priority Queue ADT……Page 334
LABORATORY 13: Postlab Exercise 1……Page 339
LABORATORY 13: Postlab Exercise 2……Page 340
Weighted Graph ADT……Page 341
Weighted Graph ADT……Page 342
LABORATORY 14: Cover Sheet……Page 345
LABORATORY 14: Prelab Exercise……Page 347
LABORATORY 14: Bridge Exercise……Page 350
Test Plan for the Operations in the Weighted Graph ADT……Page 351
LABORATORY 14: In-lab Exercise 1……Page 352
Test Plan for the allEven Operation……Page 354
LABORATORY 14: In-lab Exercise 2……Page 355
Test Plan for the properColoring Operation……Page 357
LABORATORY 14: In-lab Exercise 3……Page 358
Test Plan for the computePaths Operation……Page 361
LABORATORY 14: Postlab Exercise 1……Page 363
LABORATORY 14: Postlab Exercise 2……Page 365
Performance Evaluation……Page 367
Timer ADT……Page 368
LABORATORY 15: Cover Sheet……Page 371
LABORATORY 15: Prelab Exercise……Page 373
LABORATORY 15: Bridge Exercise……Page 374
Test Plan for the Operations in the Timer ADT……Page 375
Execution Times of a Set of Searching Routines……Page 376
Execution Times of a Set of Sorting Routines……Page 379
LABORATORY 15: In-lab Exercise 3……Page 382
Time to Fill and Empty a 10,000-Element Stack……Page 383
LABORATORY 15: Postlab Exercise 1……Page 385
Execution Times of a Set of Sorting Routines……Page 386
Execution Times of a Set of Sorting Routines……Page 387
Team Software Development Project……Page 389
LABORATORY 16 Ñ Week 1: Prelab Exercise 1……Page 391
LABORATORY 16 Ñ Week 1: Prelab Exercise 2……Page 398
LABORATORY 16 Ñ Week 1: Bridge Exercise……Page 406
LABORATORY 16 Ñ Week 1: Project Cover Sheet……Page 409
Test Plan for the class……Page 411
Project……Page 412
LABORATORY 16 Ñ Week 1: In-lab Exercise……Page 413
LABORATORY 16 Ñ Week 2: Project Cover Sheet……Page 419
LABORATORY 16 Ñ Week 2: In-lab Exercise……Page 420
LABORATORY 16 Ñ Postlab Exercise……Page 423