Previous Section
 < Free Open Study > 
Next Section


Index

S

Scenarios, 8, 170, 172, 189
in index building case study, 510
in real estate listings case study, 175
in simulation case study, 249
Scope resolution operator (::), 18, 87
and definition of member functions, 94
and implementation of derived class, 244
and namespaces, 98
Scope rules, 87
Searching, 619-637, 643
binary, 622
choosing good hash function, 633-637
and complexity of hashing, 637
hashing, 622-633
high-probability ordering, 620-621
key ordering, 621-622
linear, 620
technique, 619
Secondary keys, 617, 618
Seed value, 260
SEI Software Engineering Process Group Conference, 33
Selection sort algorithm
analyzing, 592-593
snapshot of, 590
SelectionSort function, 589, 594, 596, 600
number of comparisons required to sort arrays with, 593
Selector function, 71
Self, 90
explicit reference to, 391
Self-organizing (or self-adjusting) lists, 621
Semantics
of class type, 86
SEMICOLON EXPECTED error message, 23
Sending a message, 91
Sequential array-based list representation, 132
Sequential implementations
Big-O comparison of sorted list operations for, 326
Sequential lists
hashed list compared with, 625
in static and dynamic storage, 359
Sequential searches, 620,
efficiency with, 643
Serve operation, 227
ServerList ADT specification, 252-253
ServerList class, 259
Servers, 246, 247, 248, 249
ServerType class, 252
Set ADT, 530, 579
specification for, 572-573
Set notation
vertices listed in, 547
Sets, 117, 571-579
application level, 574
implementation level, 574-579
intersection of, 577
logical level, 571-573
special types of, 571
SetType class, 572
SetType constructor, 577
Shallow copies, 358
deep copies versus, 351, 352
Shallow copying, 334, 392
with assignment operator, 357
Shape property
in binary search tree, 456
of heaps, 533, 536, 537, 543, 610
ShortBubble, 600, 642
analysis of, 597
ShortestPath, 560
Shortest-path algorithm
code for, 561-562
Simula, 91
Simulation case study, 245-261
output from one run of program simulation, 261
Simulations
with queues, 245
Simulation variables
initializing, 256
Single-source shortest-path problem, 559-563
Singly linked linear list structure, 334
Singly linked list
inserting into, 347
Size factor
and Big-O notation, 164, 167
Size of problem
and order of magnitude, 159
in writing recursive functions, 408
Skewed binary search tree, 546
Slicing problem, 372, 373
Smaller-Caller Question, 407, 408
and iteration, 433
and RevPrint function, 415
and ValuelnList function, 411
Smalltalk, 91
Software
development, 3
process, 2-9
quality, 4-7
Software engineering, 3, 58
Software engineers, 9
Software errors
importance of early detection of, 23
Software life cycle, 58
activities in, 2-3
Software specification, 4
SomeType, 223
Sort algorithms
choosing, 642-643
SortDr.cpp file, 615
Sorted arrays
merging, 603-606
strategy for merging of, 603
Sorted halves
merging, 604
Sorted List ADT, 188, 252, 334, 373, 621
specification (partial) for, 146-147
Sorted List ADT algorithms
comparison of Unsorted List ADT algorithms, 164-167
Sorted List ADT as linked data structure
comparing sorted list implementations, 324-326
and DeleteItem function, 324
implementing, 318-326
and InsertItem function, 320-324
and RetrieveItem function, 318-319
Sorted list implementations
comparing, 324-326
Sorted list operations
Big-O comparison of, 326
Sorted list property, 146
Sorted lists, 124
in array of records, 361
deleting items in, 150
four insertion cases, 323
goal of, 588
inserting at end of, 320
inserting items in, 147, 148, 189
linear searching of, 621
retrieving in, 151
retrieving items that are not there, 319
SortedType class, 147, 348
Sorting/Sorts, 588-618, 642, 643
bubble sort, 593-597
in general, 617-618
with the heap, 612-614
heap sort, 609-615
insertion sort, 598-600
with keys, 617-618
O(N log2N) sorts, 600-608
other efficiency considerations, 615-617
with pointers, 618
and priority queues, 531
Quick Sort, 609
radix, 637-642
straight selection sort, 589-593
testing sorting algorithms, 615
Sorting algorithms, 438
comparison of, 643
SortNodes, 613
Sorts.in file, 615
SortsOut, 615
Sorts.screen, 615
Space considerations/requirements
for radix sorts, 642
and sorting algorithms, 608, 617
Specialized list ADT, 373-379
inserting at front and rear, 377
operation to be tested and description of action for, 379
SpecializedList class, 374, 380, 392, 461
Specifications, 7-8
for binary search tree, 461-462
for class, 85, 86-87
and design errors, 21-23
detailed, 8-9
for Graph ADT, 551-552
for program simulation, 248-249
for Queue ADT, 227, 229
for ServerList ADT, 252-253
for Set ADT, 572-573
Specifier, 591
Splitting algorithms, 444
Split value, 609
Stable sort, 617, 618
Stack ADT, 230
and C++ templates, 210
specification, 198-199
test plan for, 208-210
Stack ADT as linked data structure
implementing, 280-296
comparison of stack implementations, 295-296
and other stack functions, 293-295
and Pop function, 289-291
and Push function, 280-289
and Top function, 291-292
Stack class
definition of, 204-205
Stack elements
chaining, 282
Stack frame, 423
Stacking, 432, 434-436
Stack operations
definitions of, 205-208
Stacks, 117, 159, 196-210, 225, 327, 439, 547
airline routes stored in, 554
application level, 199-204
defined, 196
implementation level, 204-210
implementing as linked structure, 280-296
logical level, 196-197
operations on, 197-199
overflow of, 205
popping, 292
popping first element on, 293
real-life, 196
and recursion, 446
shallow copy versus deep copy of, 352
StackType class, 202, 204, 205, 213, 285-286, 351, 353, 356, 555
default constructor in, 225
dynamic storage allocation for, 280
StackType constructors
implementations of, 223
StackType object, 231
Stack underflow, 207
Standard Template Library, 17, 124
Statement coverage, 36
Static allocation, 217
Statically allocated arrays, 358
Static array implementation
Big-O comparison of queue operations for, 306
in terms of Big-O, 295, 296
Static arrays, 295
Static binding, 92, 368
static reserved word, 224
Static storage
array-based lists in, 359
linked lists in, 360
Static storage allocation, 420-423, 446
for program with three functions, 422
Status flag, 252
stdexcept
hierarchy of error classes in, 97
std namespace
rules for using, 99
Stepwise refinement, 11-12, 13
Storage
devices, 3
requirements for queue implementations, 305
Store operation, 577
Straight selection sort, 588, 589-593
example of, 589
Stream failure, 26-27
Stream input and output, 25-26
Stream insertion operator, 484
Stream operators
overloading, 358
String ADT specification, 102-103
string class, 100
string data type, 49
Strings, 100
StringType, 22, 23
string variable, 49
StrType class, 100, 101
expanded definition of, 168
Structs, 72, 116
application level, 75
differences between classes and, 90
as records, 73
Structured data types, 72, 82
Structured programming, 91
Stubs, 45, 49, 255, 256, 258
Subarrays, 604, 607, 608
Subclass, 94, 242
SubKey function, 640, 641
Sublists, 643
Subprograms, 172
Subset, 571
Subtraction, 65
in large ADT implementation case study, 381, 382-383
Subtrees, 457, 459, 465
and heap building, 610, 611
Summary function, 71, 72
Superclass, 94, 242
Swap function, 540, 591
Swapping/Swaps, 616
and bubble sorts, 593
and sorting algorithms, 591
and sorting efficiency, 588
and sorting with pointers, 618
switch statement, 2, 137, 169, 406, 432
Symbol table, 420, 421
SymbolType class, 202
Syntax, 72
of class, 18-19
of class type, 86
of component selector, 73
for copy constructor, 353
for declaring pointer pointing to integer value, 214
errors in, 23, 79, 136
and one-dimensional arrays, 78
for overloading a symbol, 168
for two-dimensional arrays, 82


Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)