A laboratory course in C++ data structures

James Roberge9780763719760, 0-7637-1976-5

A Laboratory Course in C++ Data Structures, Second Edition exemplifies the active learning experience. With a dynamic learn-by-doing focus, this laboratory manual encourages students to explore data structures by implementing them, a process through which students discover how data structures work and how they can be applied. Providing a framework that offers feedback and support, this text challenges students to exercise their creativity in both programming and analysis. Each laboratory unit consists of four parts: the Prelab, the Bridge, the In-lab, and the Postlab, which create an excellent hands-on learning opportunity for students in supervised labs and students engaged in independent study.

---

Table of contents :
TeamLiB……Page 1
Cover……Page 2
Contents……Page 17
Preface to the Second Edition……Page 7
To the Instructor……Page 11
1 Logbook ADT……Page 21
Overview……Page 22
Logbook ADT……Page 23
Laboratory 1: Cover Sheet……Page 25
Laboratory 1: Prelab Exercise……Page 27
Laboratory 1: Bridge Exercise……Page 31
Laboratory 1: In- lab Exercise 1……Page 33
Laboratory 1: In- lab Exercise 2……Page 35
Laboratory 1: In- lab Exercise 3……Page 37
Laboratory 1: Postlab Exercise 1……Page 39
Laboratory 1: Postlab Exercise 2……Page 41
2 Point List ADT……Page 43
Overview……Page 44
Point List ADT……Page 45
Laboratory 2: Cover Sheet……Page 49
Laboratory 2: Prelab Exercise……Page 51
Laboratory 2: Bridge Exercise……Page 53
Laboratory 2: In- lab Exercise 1……Page 55
Laboratory 2: In- lab Exercise 2……Page 57
Laboratory 2: In- lab Exercise 3……Page 59
Laboratory 2: Postlab Exercise 1……Page 61
Laboratory 2: Postlab Exercise 2……Page 63
3 Array Implementation of the List ADT……Page 65
Overview……Page 66
List ADT……Page 68
Laboratory 3: Cover Sheet……Page 71
Laboratory 3: Prelab Exercise……Page 73
Laboratory 3: Bridge Exercise……Page 76
Laboratory 3: In- lab Exercise 1……Page 79
Laboratory 3: In- lab Exercise 2……Page 80
Laboratory 3: In- lab Exercise 3……Page 81
Laboratory 3: Postlab Exercise 1……Page 83
Laboratory 3: Postlab Exercise 2……Page 85
4 Ordered List ADT……Page 87
Overview……Page 88
Ordered List ADT……Page 89
Laboratory 4: Cover Sheet……Page 93
Laboratory 4: Prelab Exercise……Page 95
Laboratory 4: Bridge Exercise……Page 100
Laboratory 4: In- lab Exercise 1……Page 102
Laboratory 4: In- lab Exercise 2……Page 104
Laboratory 4: In- lab Exercise 3……Page 106
Laboratory 4: Postlab Exercise 1……Page 109
Laboratory 4: Postlab Exercise 2……Page 111
5 Stack ADT……Page 113
Overview……Page 114
Stack ADT……Page 117
Laboratory 5: Cover Sheet……Page 119
Laboratory 5: Prelab Exercise……Page 121
Laboratory 5: Bridge Exercise……Page 125
Laboratory 5: In- lab Exercise 1……Page 127
Laboratory 5: In- lab Exercise 2……Page 130
Laboratory 5: In- lab Exercise 3……Page 131
Laboratory 5: Postlab Exercise 1……Page 133
Laboratory 5: Postlab Exercise 2……Page 135
6 Queue ADT……Page 137
Overview……Page 138
Queue ADT……Page 139
Laboratory 6: Cover Sheet……Page 141
Laboratory 6: Prelab Exercise……Page 143
Laboratory 6: Bridge Exercise……Page 146
Laboratory 6: In- lab Exercise 1……Page 148
Laboratory 6: In- lab Exercise 2……Page 150
Laboratory 6: In- lab Exercise 3……Page 152
Laboratory 6: Postlab Exercise 1……Page 153
Laboratory 6: Postlab Exercise 2……Page 155
7 Singly Linked List Implementation of the List ADT……Page 157
Overview……Page 158
List ADT……Page 159
Laboratory 7: Cover Sheet……Page 163
Laboratory 7: Prelab Exercise……Page 165
Laboratory 7: Bridge Exercise……Page 167
Laboratory 7: In- lab Exercise 1……Page 169
Laboratory 7: In- lab Exercise 2……Page 171
Laboratory 7: In- lab Exercise 3……Page 173
Laboratory 7: Postlab Exercise 1……Page 175
Laboratory 7: Postlab Exercise 2……Page 177
8 Copying and Comparing ADTs……Page 179
Overview……Page 180
Enhanced List ADT……Page 183
Laboratory 8: Cover Sheet……Page 185
Laboratory 8: Prelab Exercise……Page 187
Laboratory 8: Bridge Exercise……Page 189
Laboratory 8: In- lab Exercise 1……Page 191
Laboratory 8: In- lab Exercise 2……Page 193
Laboratory 8: In- lab Exercise 3……Page 195
Laboratory 8: Postlab Exercise 1……Page 197
Laboratory 8: Postlab Exercise 2……Page 199
9 Doubly Linked List Implementation of the List ADT……Page 201
Overview……Page 202
List ADT……Page 203
Laboratory 9: Cover Sheet……Page 207
Laboratory 9: Prelab Exercise……Page 209
Laboratory 9: Bridge Exercise……Page 210
Anagram Puzzle ADT……Page 212
Laboratory 9: In- lab Exercise 2……Page 215
Laboratory 9: In- lab Exercise 3……Page 216
Laboratory 9: Postlab Exercise 1……Page 219
Laboratory 9: Postlab Exercise 2……Page 221
10 Recursion with Linked Lists……Page 223
Overview……Page 224
Laboratory 10: Cover Sheet……Page 229
Laboratory 10: Prelab Exercise……Page 231
Laboratory 10: Bridge Exercise……Page 240
Laboratory 10: In- lab Exercise 1……Page 243
Laboratory 10: In- lab Exercise 2……Page 247
Laboratory 10: In- lab Exercise 3……Page 249
Laboratory 10: Postlab Exercise 1……Page 251
Laboratory 10: Postlab Exercise 2……Page 253
11 Binary Search Tree ADT……Page 255
Overview……Page 256
Binary Search Tree ADT……Page 257
Laboratory 11: Cover Sheet……Page 259
Laboratory 11: Prelab Exercise……Page 261
Laboratory 11: Bridge Exercise……Page 263
Laboratory 11: In- lab Exercise 1……Page 264
Laboratory 11: In- lab Exercise 1……Page 268
Laboratory 11: In- lab Exercise 1……Page 270
Laboratory 11: Postlab Exercise 1……Page 273
Laboratory 11: Postlab Exercise 2……Page 275
12 Expression Tree ADT……Page 277
Expression Tree ADT……Page 278
Laboratory 12: Cover Sheet……Page 283
Laboratory 12: Prelab Exercise……Page 285
Laboratory 12: Bridge Exercise……Page 287
Laboratory 12: In- lab Exercise 1……Page 288
Laboratory 12: In- lab Exercise 2……Page 291
Laboratory 12: In- lab Exercise 1……Page 293
Laboratory 12: Postlab Exercise 1……Page 295
Laboratory 12: Postlab Exercise 2……Page 297
13 Weighted Graph ADT……Page 299
Weighted Graph ADT……Page 300
Laboratory 13: Cover Sheet……Page 305
Laboratory 13: Prelab Exercise……Page 307
Laboratory 13: Bridge Exercise……Page 310
Laboratory 13: In- lab Exercise 1……Page 312
Laboratory 13: In- lab Exercise 2……Page 316
Laboratory 13: In- lab Exercise 3……Page 319
Laboratory 13: Postlab Exercise 1……Page 323
Laboratory 13: Postlab Exercise 2……Page 325
14 Hash Table ADT……Page 327
Overview……Page 328
Hash Table ADT……Page 329
Laboratory 14: Cover Sheet……Page 333
Laboratory 14: Prelab Exercise……Page 335
Laboratory 14: Bridge Exercise……Page 337
Laboratory 14: In- lab Exercise 1……Page 339
Laboratory 14: In- lab Exercise 2……Page 341
Laboratory 14: In- lab Exercise 3……Page 343
Laboratory 14: Postlab Exercise 1……Page 347
Laboratory 14: Postlab Exercise 2……Page 349
A String ADT……Page 351
Overview……Page 352
String ADT……Page 353
Laboratory A: Cover Sheet……Page 355
Laboratory A: Prelab Exercise……Page 357
Laboratory A: Bridge Exercise……Page 359
Laboratory A: In- lab Exercise 1……Page 361
Laboratory A: In- lab Exercise 2……Page 363
Laboratory A: In- lab Exercise 3……Page 365
Laboratory A: Postlab Exercise 1……Page 367
Laboratory A: Postlab Exercise 2……Page 369
B Heap ADT……Page 371
Overview……Page 372
Heap ADT……Page 373
Laboratory B: Cover Sheet……Page 377
Laboratory B: Prelab Exercise……Page 379
Laboratory B: Bridge Exercise……Page 381
Priority Queue ADT……Page 383
Laboratory B: In- lab Exercise 2……Page 387
Laboratory B: In- lab Exercise 3……Page 391
Laboratory B: Postlab Exercise 1……Page 393
Laboratory B: Postlab Exercise 2……Page 395
C Performance Evaluation……Page 397
Overview……Page 398
Timer ADT……Page 399
Laboratory C: Cover Sheet……Page 401
Laboratory C: Prelab Exercise……Page 403
Laboratory C: Bridge Exercise……Page 404
Laboratory C: In- lab Exercise 1……Page 406
Laboratory C: In- lab Exercise 2……Page 408
Laboratory C: In- lab Exercise 3……Page 410
Laboratory C: Postlab Exercise 1……Page 411
Laboratory C: Postlab Exercise 2……Page 413
Appendix 1 Program Validation in C++……Page 415
Appendix 2 A Summary of C++ I/ O……Page 421
Appendix 3 Pointers……Page 429