❧

Subject Index

359

A

ALGOL 60, 3, 11

ASCII, 9, 42

AVL-tree. 215, 264

Abstraction, 1

Address, 29

Adelson-Velskii, G.M., 215

alfa (type), 31

Ancestor, 191

Array selector, 12

B

B-tree, 246

BB-tree, 257

Backtracking, 142, 183

Backus-Naur-Form (BNF), 28

Balance (of tree), 215

Balance factor, 218

Balanced merging, 88, 99

Base type, 11, 23

Bayer, R., 245, 257, 258

Binary B-tree, 257

Binary insertion sort, 61

Binary search, 14, 54

Binary tree, 193

Boolean, 8

Branch and bound, 159

Bubblesort, 66

C

Cardinality, 5, 7, 13, 16, 24

Cartesian product, 16

Cascade merge sort, 123

Case statement, 22

Centroid, 231

char, 9

Characteristic function, 33

chr (x), 10, 15

Cluster, 267

Collision, 265

Concatenation, 35

Concordance, 174

Constructor, 6, 12, 17

Context dependence, 313

Context free, 282

Context sensitive, 282

Control character, 42, 350

Coroutine, 119

Cross reference index, 206

Dependence diagram, 313

Descendant, 191

Dijkstra, E. W., x

Direct access file, 40

Direct chaining, 266

Distribution of runs, 93, 109, 116

360

div, 8

Don’t panic rule, 321

Dummy run, 108

Dynamic allocation, 166

Dynamic link, 332

Enumeration, 5

eof (f), 38

eoln (f), 43

Euler, L., xv, 65, 214, 272

Exchange sort, 65

Expression, 163, 194

Extensible language, 303

External path length, 192

External sorting, 57

F

FORTRAN, 11, 128

Factorial, 126, 128

Fibonacci number, 107, 129,

Fibonacci tree, 127, 216

File editing, 49

File operator, 37

File structure, 39

first (x), 35

Fixup, 335

Floyd, R.W., 73

Follow-symbol, 286

For statement, 14

G

Gauss, C.F., 143

get (f), 38

Gilstad, R.L., 105

Goal-oriented parsing, 288

Gotlieb, C.C., 231

H

Harmonic number, 64, 214, 2

Hash function, 266

Hashing, 266

Heap, 117

Heapsort, 68

Hedge tree, 261

Hilbert curve, 131

Hilbert, D., 131

Hoare, C.A.R., x, 76, 82, 83

Homogeneous structure, 11

Hu, T.C., 231

I

ISO, 9, 42

Index type, 11

Indexed file, 40

Infix notation, 199

Inorder traversal, 199

input, 42

Insertion sort, 60

integer, 8

Internal path length, 191

Internal sorting, 57

Interpreter, 331

K

Key transformation, 265

Keyword rule, 320

Knuth, D.E., 59, 64, 68, 70, 109, 229, 257

L

Landis, E.M., 215

Language, 282

Latency time, 41

Leaf, 191

Lexicographic tree, 206

Linear probing, 267, 273

List, 171

deletion, 172

generation, 171

insertion, 172, 175

search, 174, 175

traversal, 173

361

Load factor, 273

Locality, 307

Lookahead, 283

Loop invariant, 14

M

Matrix, 14

McCreight, E., 257

MceVitie, D.G., 153

Median, 82

Mergesort, 87

Meta-language, 299

Meta-symbol, 281

mod, 8

Multiway tree, 242

N

Natural merging, 92

new ( p), 167

nil, 168

Nonterminal symbol, 281

Null string problem, 286

Offset, 32

Open addressing, 267

Optimal tree, 228

ord (x), 10, 15

Ordered list, 176

output, 42

Overflow area, 267

P

PASCAL, xi, xiv, 3, 4, 5, 44, 85

PL/0 language, 307

PL/0 machine, 331

pack, 32

Packing, 31

Padding, 30

Page balancing, 251

Page merging, 251

Page splitting, 247

Partial order, 182, 183

Partition, 77, 82

Pass, 88, 93

Perfect balance, 195

Phase, 88, 93

Pointer (type), 166

Polyphasesort, 104

Postfix notation, 199

Postorder traversal, 199

Powerset, 23

Prefix notation, 199

Preorder traversal, 199

Production, 282

Program schema, 39, 43, 127, 142

Programming language, xiv, 2, 307

Programs:

Array search, 13

B-tree search, insertion, and deletion, 252-57

Balanced mergesort, 102-4

Balanced tree deletion, 223-25

Balanced tree search and insertion, 220-21

Binary insertion sort, 62

Binary search, 14, 54

Bubblesort, 66

Cross reference generator, 206-8

Cross reference generator (hash table), 269-71

Distribution of runs, 119-120

Eight queens, 145-47

File editor, 50-52

Find (median), 84

Find and display optimal search tree, 238-42

Heapsort, 75

Hilbert curves, 132-33

Knight’s tour, 140

List generation, 171

List traversal, 173

Natural mergesort, 97-98

362

Optimal selection, 157-58

PL/0 compiler, 337-47

PL/0 parser, 314-19

PL/0 parser with error recovery, 326-29

PL/0 sample programs, 310-11

Parser, 294

Parser of language, 301

Partition, 77

Perfectly balanced tree, 196

Polyphase sort, 113-16

Powers of 2, 15

Quickshort (non-rec.), 80

Quicksort (recursive), 79

Read file, 39

Read text, 43

Readreal, 45-47

Scanner, 26

School time table, 27-29

Shakersort, 67

Shellsort, 70

Sierpinski curves, 136-37

Sift, 73

Stable marriages, 152-53

Straight insertion sort, 61

Straight list search and insertion, 175-81

Straight mergesort, 91

Straight selection sort, 64

Symmetric binary B-tree search and insertion, 263-64

Table-driven parser, 298

Topological sort, 188-89

Translator of language, 304-7

Tree deletion, 211

Tree search, 200-201

Tree search and insertion, 203-4

Tree search and insertion (non-rec.), 205

Tree traversal, 199

Write file, 39

Write text, 43

put (ff), 37

Q

Quadratic probing, 268

Queue, 171

Quicksort, 76

Random-access, 11

Re-organizing list, 180

read, 38

readlIn, 43

real, 8

Record discriminator, 20

Record selector, 17

Record variant, 20, 21

Recursion, 125

Recursion scheme, 131

Recursive data type, 163

Rehashing, 278

Replacement rule, 281

Representation of data, 2

reset (f'), 37

rest (x), 35

Restrictive Rules, 285, 286

rewrite ( f'), 37

Run, 92

S

SBB-tree, 260

Scalar type, 5, 7

Scanner, 24, 300

Search tree, 200

Segmented file, 40

Selection sort, 63

Selective updating, 13, 169

Selector, 6, 12, 17

Semantics, 281

Sentinel, 13, 61, 175, 200

Sequence, 35

Set difference, 23

Set intersection, 23

Ann

363

Set operation, 23

Set structure, 23

Set union, 23

Shakersort, 66

Shared data, 166

Shell, D.L., 68

Shellsort, 68

Sierpinski curve, 134

Single phase merging, 88

Singleton sequence, 35

Singleton set, 24

Stable sorting, 58

Stage, 88

Standard types, 5

Start symbols, 281

Static link, 333

Stepwise enrichment, 303

Stepwise refinement, 49, 303

Stopping symbol, 321

Straight merging, 87

String, 92

Structuring method, 5

Symmetric binary B-tree, 260

Syntax, 281

Syntax analysis, 283

Syntaxgraph, 288

T

2-3 tree, 257

Table-driven parsing, 288, 295

Tag field, 20

Terminal symbol, 281

Termination, 127

Top-down parsing, 283

Topological sort, 182

Tree, 189

deletion, 210, 222, 250

depth, 191

degree, 191

height, 191

insertion, 202, 216, 248, 258, 260

level, 191

search, 202, 216, 248, 258, 260

traversal, 198

Tree page, 245

Tree-hashing, 278

Tucker, A.C., 231

Type (of data), 4

Type declaration, 4, 7, 10, 11, 16, 21 36, 167

U

unpack, 32

V

Variant record structure, 20

Vocabulary, 280

W

Walker, W.A., 231

Weighted path length, 226

Williams, J., 72

Wilson, L.B., 153

Word, 29, 30

Wordsize, 29

write, 38

writeln, 43

364