Index

Absolute value, 19 CHILD, 256

Ackcrmann function, 179 Circular array, 190
ADJ. 287 Circular list, 140, 143
Adjacency matrix, 280 Coding. 254
Adjacency structure. 286, Collision resolution. 335
Adjacent nodes, 277 Column, 3, 81,.84
Algebraic expression. 6, 215 Column-major order, 83, 84
Algorithm, 9. 17 Complete binary tree, 216
Algorithmic notation, 21 Complete graph, 277
Ancestor, 215 Complexity of algorithms. 5, 9, 27
Arithmetic expression, 168 Concatenation, 48
Array, 2. 67 Conditional flow, 24
circular, 19() Connected graph. 279
jagged. 87 strongly, 279, 282
multidimensional, 81, 84 Control, flow of, 23
parallel, 92 Copying, 133
pointer, 86 Cycle, 277
Assignment statement. 23
Atoms, 94) Data, I
Attributes, I Data base management, 2
AVAIL list, 123- D,,ta modification, 332
Average case, 28 Data Structure, 2
Decision tree. 319
BACK, 445 Degree of a node. 277
Base address, 69 Deleting. 8, 50
Base criteria, 176 I)c,ise list. 114
Base values, 176 Depth, 178, 216
Ittg () notation. 29 Depth-first search, 296
Binar y search. 9, 78 Dequc, 192
complexity of, 80 Descendent. 215
l3in:iry search tree, 233 DEST. 287
deict irg in, 238 p iagonat , 95
insetting iii, 234 Digraph, 279
scarcltuig in. 234 Directed graph. 279
Binary tree. 214 Divide-and-conquer, 179
umplctc, 216 Division method, 334
depth of, 216 Double hashing, 336
extended, 217
height of, 216 Edge, 215, 277
traversing. 221 Elementary item, I
Bit matrix, 280 Empty string, 41
hot lean ni a (dx, 280 Entity. I
Ittacich, 215 Exit, 22
Breadth-first search, 294 Exponents, 20
l3rcthcrs, 215 Extended binary (Icc, 217
Utihtilc sort. 73--75 External node, 217
.t 'niplexity of, 75 External path length, 249

(emhitig Itinctioui, 18 Factorial function, 19, 177

Chaining, 337 Father. 215
Character set • 41 Fibonacci sequence, 178
Character type. 31, 46 Field, 1, 90
('bud. 215 FIFO (first-in-first-out), 7, 164, 188
340
 INDEX 341

File, I, 90 lndcgrcc, 279

File management. 2 Index, 67, 82
File scarching, 333 Indexing, 91
File sorting, 320 Infix notation. 169
Finite graph, 278 INFO, 116, 217
FIRST, 145 Initial point, 279
Fixcd-length records. 2 Murder threading, 230
Fixed-length storage; 42 Inordcr traversal, 221, 226
Floor function, 18 Input-restricted dcquc, 192
Folding method, 334 Inserting, 8, 49
FORW, 145 Insertion sort, 322
Frec-storagc list, 123 complexity of, 323
Front, 7, 188 Integer value, 19
FRONT, 189 Internal node, 217
Function suhalgorithm, 30 Internal path length, 249
Isolated node, 277
Garbage collection, 127 Item, I
General tree, 255 Iteration logic, 26
representation of, 256
Generation, 216
Global variables, 32 Jagged array, 87
(.tph, 8, 277
complete, 277
deleting from, 291 Key, 1, 318
direcid, 279
inserting i n, 289
labeled, 277 Labeled graph, 277
LAST, 145
linked representation of, 286
searching in, 289 Leaf, 215
Left child, 215
sequential representation of, 280
simple, 280 Left subtree, 214
weighted, 277 Left successor, 214
LEFT, 217
Group item, I
Length:
Growth, rate of, 29
of path, 249
of string, 41, 49
Hanoi, Towers of, 180-183 Level, 216
Hash addressing, 333
LIFO (last-in-first-out), 7,
Hash function, 334 Linear array, 2, 67
Hashing, 333 deleting from, 71
double, 336 inserting in, 71
Header linked list, 140 traversing, 70
Header list,two-way, 146 Linear probing, 335
Header node, 140
Linear search, 9, 28, 76
Heap, 243
Complexity of, 77
deleting the root of, 246 LINK, 116
inserting into, 243
Link field, 115
reheaping, 246
Linked list, 4, 114
Hcapsort, 243 circular, 143
Complexity of, 248 copying, 133
Height of a tree, 216 deleting from, 134
Homer's method, 113 header. , 140, 146
Hufiman's algorithm, 249, 251 inserting into, 127
searching, 121
Identifiers, 96 traversing, 120
Identifying numbers. 22 two-way, 144, 153
Inccdcncc matrix. 310 Linked storage, 45
342 INDEX

List. 4, 114 Null string. 41

AVAIL, 123 Null tree, 214
free-storage, 123 Number, priority, 193
Load factor, 335
Local variables, 32 o notation, 29-30
Logarithms, 20 One-dimensional array, 3
Logic, 23 One-way list, 115
Logical type. 32 Open addressing, 335
Loop, 278 Operations, 8
Lower hound, 67, 82 on graphs, 289
For sorting. 319. string, 47
Outdcgrcc, 279
Matrix, 3, 81, 94 Output-restricted dcque, 192
adjacency. 280 Overflow, 127
bit, 280 stack, 167-168
Boolean, 280
inccdencc, 310
path, 281 Page, 84
rcachhility. 281 Parallel arrays. 92
sparse, 97 Parent node, 215
triangular, 97 Partial ordering. 298
tridiagonal, 97, 104 Pass (in an algorithm), 73
weight, 284 Path, 215, 277
Matrix multiplication, 96 simple, 277
complexity of. 96-97 Path length. 249, 271
Maxhcap, 243 external, 249
Mean, 31 internal, 249
Mcmory, 2 weighted, 250
Memory allocation, 123 Path matrix, 281-282
Merge-sort, 328 Pattern matching. 53, 55
complexity of, 330 complexity of, 57
Merging, 8, 325 Permutations, 20
algorithm, 327 Pointers, 4, 86
complexity of, 327 searching, 333
Midsquarc method, 334 sorting, 320
Minhcap, 243 Polish notation, 169
Modules, 17, 23 Polynomials, 143
Modulus arithmetic, 18 POP, 167
Multidimensional arrays, 81, 84 Pop operation. 165
Multigraph, 278 Poset, 297
Multiple edges. 278 Postfix notation, 169
Postorder traversal, 221, 228
Neighbor, 277, 286 Prefix notation, 169
NEXT, 287 Preordcr traversal, 221, 224
Ncxtpointer field. 115 Primary key, 1, 318
Node, 115, 214, 255, 277 Prime number, 37
external, 217 Priority number, 193
header, 140, 229 Priority queue. 193
internal. 217 Probe, 335
isolated, 277 Probing, 335
terminal, 214 linear, 335
trailer, 143 quadratic, 336
NODE, 287 Procedurc, 23, 30
Nonlocal variables, 33 PUSH, 167
NULL, 116, 219 Push operation, 165
Null pointer. 115 Push-down list, 164
 INDEX 343.

Quadratic probing, 336 Sequence logic, 23

Qualification, 92 Sequential sort, 76
Queue, 7, 164, 188 Shortest-path algorithm, 284
deleting from, 192 SIUL, 256
iflSCr(iflg 111(0, 192 Sibling, 216
priority, 193 Side effect, 33
Quicksort, 173, 175, 200 Sigma (), 19
co mplexity of, 176 Similar graphs, 303
Similar trees, 215
Radix sort, 330 Simple graph, 280
complexity of, 332 Simple path, 277
Reachable in agraph, 279 Son, 215-216
Reachability matrix, 281 Sorting, 8. 73, 318
Real type, 32 bubble, 73
Rear, 7, 188 heapsort, 243
REAR, 189 insertion, 322
Record, I, 90
lower bound complexity, 318-320
fixed-length, 2 merge-sort, 328
variable-length, 2 quicksort, 173
Record structure, 6 radix, 330
Recursion, 176 Selection, 324
Recursive procedure, 183 topological, 297
Recursively defined, 176 Sparse matrix, 97
Regular array, 02 Square matrix, 95
Rehcap, 246 Stack, 7, 164
Remainder function, 18 STACK, 166
Rcpcat-for loop, 26 START, 116
Repeat-while loop, 27 STATUS, 294
Repctitivc flow, 26 Status of a node, 294
Replacement, SI Strings, 41
RIGHT, 217
Strongly connected graph, 779
Right son, 216 Sublgoritbrn, 30
Right subtrce, 214 Subsript, 2, 68
Right Successor, 214 Substring, 41, 47
Root, 214, 279 Subtrec, 214
ROOT, 217 Successor, 214, 286
Rooted tree, 279 Summation symbol (), 19
Row, 3, 81, 84 SWITCH, 31
Row-major order, 83, 84 Symmetric matrix, 97

S(A), 335
Table, 3, 81
Scalor, 90
Terminal node, 214
Search:
Terminal point, 279
binary, 9, 78 Text, 49
linear, 9, 28, 76 Thread, 230
sequential, 76
Threaded tree, 230
Searching, 8, 76, 318, 332 Time-space tradeoff, 10, IS
binary search tree, 234 TOP, 166
files, 333
Top of a stack, 7, 165
graph, 289
Topological sorting, 297
linked list, 121 Towers of Hanoi, 180, 185
pointers, 333
Trailer node, 143
two-way list. 147 Transitive closure, 282
Selection logic, 24 Traversing, 8
Selection sort, 324
binary (icc, 221
Complexity of, 325
graph, 294
344•• INDEX

U(A), 335
Traversing (COnhihued)
Underfiow, 127
linear array, 70
Upper bound, 67, 82
linked list, 120
two-way list, 147 Variable, 31
Tree, 5, 214, 255 global, 32-33
binary, 214 local, 32
decision, 319 subscripted, 2
depth of, 216 Variable length, 2
general, 255 Variable-length records, 2
height of, 216 Variable-length storage, 44
null, 214 Vertex, 277
threaded, 230 Visiting, 70
Triangular matrix, 97
Warshall's algorithm, 282
Tridiagon'l matrix, 94, 104
Weight, 277
Two-dimensional array, 3
Weight matrix, 284
Two-way header list, 146
Weighted graph, 277
Two-way list, 144, 153
Weighted path length, 250
deleting from, 147
Word processing, 49
inserting into, 148
Worst case, 28
Type, 31