f rw .. . 1~.,,,,,s,.e~
`
`T ~
`
`e
`
`.a
`
`TA
`345
`~— _ ~, ~. .
`1993
`.'
`
`,,
`
`I
`
`1
`
`~,~.~/
`~1~ata Structures
`~ for
`r~~ ~
`~~ En in
`.,~
`q eerinQ So
`ftware
`~/~~~~~
`~~ ~~~
`. ~
`„r-~
`
`~~~'~~ eter P. Silvester
`~~`
`~:
`-
`,~~ ~'
`/ ~~.
`.~
`~ ~~
`
`~~~
`
`""~"~~
`~ ~'
`
`G
`
`~~~
`. -~~~-~'
`
`~- ~
`
`_—
`
`~~
`
`Computational Mechanics Publications
`
`~~
`
`__~_
`
`_~
`
`Facebook's Exhibit No. 1016
`Page 1
`
`

`

`Data Structures
`for
`Engineering Software
`
`Peter P. Silvester
`
`McGill University
`
`Computational Mechanics Publications
`Southampton Boston
`
`!~~R~ ,
`.,,~,~
`~' ~~I ~~~
`
`.r-
`
`~ ~_
`
`Facebook's Exhibit No. 1016
`Page 2
`
`

`

`Peter P. Silvester
`Department of Electrical Engineering
`McGill University
`3480 University Street
`Montreal, PQ
`Canada H3A 2A7
`
`Computational Mechanics Publications
`Ashurst Lodge, Southampton, SO4 2AA, UK
`Telephone: 44 (0) 703 293223 Fax: 44 (0) 703 292853
`E-mail: cmi@ib.rl.ac.uk
`
`For USA, Canada and Mexico:
`Computational Mechanics Inc
`25 Bridge Street, Billerica, MA 01821, USA
`Telephone: (508) 667-5841 Fax: (508) 667-7582
`
`British Library Cataloguing-in-Publication Data
`A Catalogue record for this book is available
`from the British Library
`
`ISBN 1-85312-233-5 Computational Mechanics Publications, Southampton
`ISBN 1-56252-157-8 Computational Mechanics Publications, Boston
`
`Library of Congress Catalog Card Number 93-71429
`
`This work is subject to copyright. All rights are reserved, whether the whole or part
`of the material is concerned, specifically those of translation, reprinting, re-use of
`illustrations, broadcasting, reproduction by photocopying machine or similar means,
`and storage in data banks.
`
`m Computational Mechanics Publications 1993
`
`Printed in Great Britain by Bookcraft Ltd.
`
`The use of registered names, trademarks, etc., in this publication does not imply,
`even in the absence of a specific statement, that such names are exempt from the
`relevant protective laws and regulations and therefore free for general use.
`
`C c
`
`ref`
`1. In
`
`2. Bi~~
`
`3. Ar
`
`'
`
`4. Mu
`
`5. Lin•
`
`Facebook's Exhibit No. 1016
`Page 3
`
`

`

`Contents
`
`Preface
`
`1. Introduction to data structures
`What are data structures?
`Engineering software
`Programs in this book
`Problems
`
`2. Bits, bytes and numbers
`Data storage in binary machines
`Integer notations
`Real numbers
`Character encoding
`Problems
`
`3. Arrays and vectors
`Elementary operations on arrays
`Linear arrays
`Vector operations
`Sparse vector storage
`Hashed storage
`Searching
`Sorting
`Problems
`
`4. Multidimensional arrays
`Array storage
`Matrix arithmetic
`Special storage forms
`Sparse matrices
`Problems
`
`5. Linear dynamic structures
`Stacks
`Queues
`Path-tracing problems
`
`hampton
`~n
`
`le whole or part
`rating, re-use of
`r similar means,
`
`does not imply,
`:xempt from the
`;ral use.
`
`vii
`
`1
`1
`7
`11
`12
`
`13
`13
`17
`21
`24
`26
`
`28
`28
`29
`34
`39
`44
`53
`58
`62
`
`64
`64
`70
`78
`86
`92
`
`94
`94
`98
`102
`
`Facebook's Exhibit No. 1016
`Page 4
`
`

`

`Vi
`
`DATA STRUCTURES FOR ENGINEERING SOFTWARE
`
`107
`112
`
`113
`113
`117
`121
`129
`134
`141
`
`Lists
`Problems
`
`6. Lists and pointers
`Linked lists
`Pointers in high-level languages
`List operations
`Multiple linking
`Threaded lists
`Problems
`
`'~. Tree structures
`Trees and tree-oriented processes
`Binary trees
`Balanced trees
`Complete trees and heaps
`Heap management
`Problems
`
`Apgendiac
`Readings
`The ASCII character set
`
`Index
`
`_ ---
`
`Facebook's Exhibit No. 1016
`Page 5
`
`

`

`rrays and vectors
`
`3A
`
`~
`
`~
`
`Widely used in engineering analysis and therefore ubiquitous in engineering
`software, the array is probably the simplest structure for organizing mathematical
`data. An array is a list of elements, items all be of a similar nature —real numbers,
`unsigned integers, characters, Boolean values, dates. In ordinary writing, array
`elements are normally identified by lower-case italic letters, with their indices given
`as subscripts: ak, bl~. Arrays are addressable data structures; any element of an array
`may be accessed independently of the others, for the indices of every element are
`unique. The elements can have just one index, or several, but every element of an
`array must have the same number of indices. An array whose elements are identified
`by n indices is said to be n-dimensional, and those with only a single index are often
`called linear arrays, or vectors.
`Arrays occur naturally in various physical and geometric problems as well as
`in numerical mathematics. It is usual to store matrices, which commonly arise in
`engineering analysis, as arrays — so usual that array indices are often called
`subscripts and even the words matrix and arrcry are occasionally regarded as
`synonyms. However, not all arrays represent matrices and not all matrices are best
`stored as arrays, so the words are not really equivalent. These subtleties will be
`taken up in due course; for most purposes of numerical computation, arrays and
`matrices are at least intimately related, and often amount to the same thing.
`Elementary operations on arrays
`Arrays may be composed of any kind of data, but with one proviso: all the elements
`of a given array must be of a similaz type. This rule is necessary, because the
`elementary operation of comparison must be defined on the elements of an array. In
`other words, it must be possible to decide whether a specified array element aZ is
`identical to another, say a~; the test if at=a~ then ... must make sense.
`You cannot compare apples and oranges, goes the saying; comparisons are
`only meaningful between like things. For comparison to be possible, an array must
`be made up of just one type of element. An array may consist entirely of apples —
`small apples, red apples, sour apples — or it may consist of oranges, but not both.
`
`,
`
`~
`
`Facebook's Exhibit No. 1016
`Page 6
`
`

`

`ARRAYS AND VECTORS
`
`29
`
`Arrays of real numbers, complex numbers, integers, or complicated structures
`including several elementary data types, are commonly encountered.
`The comparison operation does not imply that there is any particular ranking
`order for the elements, though natural orderings do exist for many kinds of data
`items (e.g., integers, alphabetic characters, days of the week). Comparisons to.
`determine similarity are entirely reasonable even where no ordering exists. Por
`example, the assertion Granny Smith ~ Red Delicious is perfectly sound, it merely
`says two apples are not alike. It is true no matter whether a Granny Smith apple
`ranks ahead of a Red Delicious, or whether any ranking system exists at all. In a
`similar way, the description of a computer display screen may include an array of
`screen colors. Like fruit, colors have no inherent order. Consequently, it may not
`make sense to ask "is color A greater than Red?", but "is A the same coloi as Red?"
`is always a meaningful question.
`Aside from comparisons, arrays must permit the two truly elementary
`operations that must be defined on any data structure and its elements. The first is
`assignment, which makes a specified array element at be identical to some given
`item z,
`
`al : = z;
`
`This is a specific form of the generic store operation., without which no data.
`structure can make sense. The second essential operation is retrieval, which makes
`some data object have the same value as a given-array element ai,
`
`z : = a~;
`
`This is a specific farm of the retrieve operation. As defined on arrays, retrieval is
`nondestructive, it makes a copy of ai without in any way affecting the original. It
`is perhaps worth pointing out that an array element always has a value; it is not
`possible for it to be empty. There is no destroy operation, so array elements can only
`be altered by a new assignment. Until they are altered this way, they retain whatever
`values they may have contained in the .past.
`
`Linear arrays
`The linear array, also known as a vector, is a list of N elements or components all
`of the same type and identified by a single index. They are simple structures, but so
`common as to merit close examination in this section.
`
`~gineering
`thematical
`numbers,
`ng, array
`ices given
`~f an array
`ement are
`vent of an
`identified
`c are often
`
`as well as
`ly arise in
`'ten called
`;garded as
`es are best
`es will be
`arrays and
`
`ng
`
`e elements
`ecause the
`n array. In
`;ment a; is
`
`prisons are
`array must
`f apples —
`it not both.
`
`y
`
`'
`
`~
`
`r
`
`~
`
`Facebook's Exhibit No. 1016
`Page 7
`
`

`

`3O
`
`DATA STRUCTURES FOR ENGINEERING SOFTWARE
`
`Sequential storage
`The elements of a linear array may be physically stored in sequential locations on
`some linear storage medium, for example a magnetic tape or the main computer
`memory. Storing in sequential locations is a convenience, not a necessary
`requirement. Formally, an array is a mapping of arrcry elements (numbers,
`characters, or some other kind of data items) onto array indices, and it is the indices
`that must form a sequence. When array elements are sequentially stored, as is
`common practice, then the indices i also imply storage locations: array element ai 1
`occupies the i`h location. For example, real numbers in the widely accepted IEEE
`notation usually occupy four bytes, so member ai of array [a~...aN] occupies
`locations 4(i —1) + 1 through 4i of the space allocated to the array.
`Sequential storage of linear arrays is particularly well suited to operations in
`which one or more arrays need to be traversed one step at a time. A simple
`example: in the addition of n-component vectors, each component cl of a vector c
`is calculated as the sum of the components a~ and b= of two other vectors a and b:
`
`To form the sum, this calculation is repeated for successive values i = 1,2, ..., n.
`Linear arrays are often encountered in numerical mathematics and for that
`reason many high-level programming languages make special provision for arrays.
`Fortran, traditionally the primary language for numerical analysis, is strongly
`oriented to arrays; Pascal and C provide most of the same facilities. The key to
`array handling in these languages is that they allow _indices (in Fortran they are
`called subscripts) to be attached to variables. The indices permit addressing array
`components, with relation to a starting address known to the computer operating
`system but hidden from the Pascal programmer. A program to add two vectors in
`Pascal reads as follows:
`
`program Addvectr(input, output);
`{Adds two N-long vectors}
`const N = 5;
`var
`
`array [1. .NJ of integer;
`A, B, C
`i integer;
`procedure readvec;
`......
`begin
`procedure writvec;
`..... .
`begin
`begin
`readvec;
`
`end;
`
`end;
`
`Facebook's Exhibit No. 1016
`Page 8
`
`

`

`ARRAYS AND VECTORS
`
`31
`
`f or i := 1 to N do begin
`
`end;
`writvec;
`end.
`
`It is assumed, without showing the details, that a procedure readvec fetches the
`strings of numerical values that constitute the vectors A and s, and that another
`procedure writvec writes out the results. The essence of the program really lies
`in just one line,
`
`The bracketed quantities are understood by the Pascal compiler to mean array
`indices. The array declaration at the top of the program instructs the compiler to
`establish memory addresses and set up counters at the start, and to maintain their
`values current as the program runs, without troubling the programmer with such
`details.
`Two practical questions are always of interest when methods of storing data
`are examined: how much; space is taken up, and how much time is required for the
`operations the programmer has in mind. Here the space requirement is obvious: each
`vector requires exactly N integer locations, so the three vectors need 3N integer
`locations. Carrying out the addition means visiting each stored number location
`exactly once, and performing one addition for each of N components. Hence the
`number of instructions ,executed is proportional to the number N of vector
`components. The program is said to run in D(N) time (pronounced "order of 1V" or
`simply "oh of N"), and to require O(N) space. It is quite usual not to worry about
`the coefficient 3, but to concentrate on the exponent of N (in this case the exponent
`is just 1) because the coefficient can often be affected by clever programming while
`the exponent usually cannot. For example, the space requirement in the addition
`program can be reduced to 2N by having A overwrite B; but it remains proportional
`` to N.
`
`Storage in memory
`To examine how arrays are handled at the machine level, suppose two vectors of 5
`components each need to be added. Taking the vector components to be 2-byte
`integers, the original vectors A and B are stored in sequential memory locations
`beginning at Q05416 and (}06416 respectively; the result c is to be placed in
`
`Facebook's Exhibit No. 1016
`Page 9
`
`