Check your mailbox for the verification email from Amazon Kindle. Related Booklists. Post a Review To post a review, please sign in or sign up. You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read.
Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them. PupilGarage provides you several tutorials and notes for different subjects that would help in better understanding.
Toggle navigation. Books feed your brains Algorithms And Data Structures. Author s : Niklaus Wirth. If you find our web-site helpful, please recommend us on Google. After all, integers form a subset of real numbers. However, the inverse direction is not permissible: Assignment of a real value to an integer variable requires an operation such as truncation or rounding.
The standard transfer function Entier x yields the integral part of x. The Boolean operators are the logical conjunction, disjunction, and negation whose values are defined in Table 1. Thus, the result of a comparison may be assigned to a variable, or it may be used as an operand of a logical operator in a Boolean expression.
This conditionality is an important and useful property. Unfortunately, there is no generally accepted standard character set used on all computer systems. Therefore, the use of the predicate "standard" may in this case be almost misleading; it is to be understood in the sense of "standard on the computer system on which a certain program is to be executed.
It consists of 95 printable graphic characters and 33 control characters, the latter mainly being used in data transmission and for the control of printing equipment. In order to be able to design algorithms involving characters i. The type CHAR contains the 26 capital Latin letters, the 26 lower-case letters, the 10 decimal digits, and a number of other graphic characters, such as punctuation marks.
The subsets of letters and digits are ordered and contiguous, i. The type CHAR contains a non-printing, blank character and a line-end character that may be used as separators. We will call them ORD ch , denoting the ordinal number of ch in the character set, and CHR i , denoting the character with ordinal number i.
Its value is defined as the capital letter corresponding to ch, provided ch is a letter. The Array Structure The array is probably the most widely used data structure; in some languages it is even the only one available. An array consists of components which are all of the same type, called its base type; it is therefore called a homogeneous structure.
The array is a random-access structure, because all components can be selected at random and are equally quickly accessible. In order to denote an individual component, the name of the entire structure is augmented by the index selecting the component. This index is to be an integer between 0 and n-1, where n is the number of elements, the size, of the array. Given an array variable x, we denote an array selector by the array name followed by the respective component's index i, and we write x i or x[i].
Because of the first, conventional notation, a component of an array component is therefore also called a subscripted variable. The common way of operating with arrays, particularly with large arrays, is to selectively update single components rather than to construct entirely new structured values.
Although selective updating causes only a single component value to change, from a conceptual point of view we must regard the entire composite value as having changed too.
The fact that array indices, i. A general index expression may be substituted in place of an index constant; this expression is to be evaluated, and the result identifies the selected component. This generality not only provides a most significant and powerful programming facility, but at the same time it also gives rise to one of the most frequently encountered programming mistakes: The resulting value may be outside the interval specified as the range of indices of the array.
We will assume that decent computing systems provide a warning in the case of such a mistaken access to a non-existent array component. The cardinality of a structured type, i. An array variable whose components are again arrays is called a matrix. Selectors may be concatenated accordingly, such that Mij and M[i][j] denote the j th component of row Mi, which is the i th component of M.
In a further example, assume that a fraction f is represented in its decimal form with k-1 digits, i. The repetition of halving to compute , 2 -2, Write W, ". Write W, "5" ; Texts. The Record Structure The most general method to obtain structured types is to join elements of arbitrary types, that are possibly themselves structured types, into a compound. Examples from mathematics are complex numbers, composed of two real numbers, and coordinates of points, composed of two or more numbers according to the dimensionality of the space spanned by the coordinate system.
An example from data processing is describing people by a few relevant characteristics, such as their first and last names, their date of birth, sex, and marital status. In mathematics such a compound type is the Cartesian product of its constituent types. This stems from the fact that the set of values defined by this compound type consists of all possible combinations of values, taken one from each set defined by each constituent type.
Thus, the number of such combinations, also called n-tuples, is the product of the number of elements in each constituent set, that is, the cardinality of the compound type is the product of the cardinalities of the constituent types.
In data processing, composite types, such as descriptions of persons or objects, usually occur in files or data banks and record the relevant characteristics of a person or object. The word record has therefore become widely accepted to describe a compound of data of this nature, and we adopt this nomenclature in preference to the term Cartesian product.
In general, a record type T with components of the types T1, T2, Records of type Complex, Date, and Person The identifiers s1, s2, As components of records are called fields, the names are field identifiers.
They are used in record selectors applied to record structured variables. Given a variable x: T, its i-th field is denoted by x. Selective updating of x is achieved by using the same selector denotation on the left side in an assignment statement: x. Given, for example, the record variables z, d, and p declared above, the following are selectors of components: z. Thus, selectors may be concatenated.
Naturally, different structuring types may also be used in a nested fashion. For example, the i-th component of an array a being a component of a record variable r is denoted by r. It is a characteristic of the Cartesian product that it contains all combinations of elements of the constituent types. But it must be noted that in practical applications not all of them may be meaningful.
For instance, the type Date as defined above includes the 31st April as well as the 29th February , which are both dates that never occurred. Thus, the definition of this type does not mirror the actual situation entirely correctly; but it is close enough for practical purposes, and it is the responsibility of the programmer to ensure that meaningless values never occur during the execution of a program. The following short excerpt from a program shows the use of record variables.
The record is more general in the sense that there is no requirement that all constituent types must be identical. In turn, the array offers greater flexibility by allowing its component selectors to be computable values expressions , whereas the selectors of record components are field identifiers declared in the record type definition.
Representation Of Arrays, Records, And Sets The essence of the use of abstractions in programming is that a program may be conceived, understood, and verified on the basis of the laws governing the abstractions, and that it is not necessary to have further insight and knowledge about the ways in which the abstractions are implemented and represented in a particular computer.
Nevertheless, it is essential for a professional programmer to have an understanding of widely used techniques for representing the basic concepts of programming abstractions, such as the fundamental data structures. It is helpful insofar as it might enable the programmer to make sensible decisions about program and data design in the light not only of the abstract properties of structures, but also of their realizations on actual computers, taking into account a computer's particular capabilities and limitations.
The problem of data representation is that of mapping the abstract structure onto a computer store. Computer stores are - in a first approximation - arrays of individual storage cells called bytes. They are understood to be groups of 8 bits.
The indices of the bytes are called addresses. The unit transferable concurrently is called a word. Representation of Arrays A representation of an array structure is a mapping of the abstract array with components of type T onto the store which is an array with components of type BYTE.
The array should be mapped in such a way that the computation of addresses of array components is as simple and therefore as efficient as possible. If s is not a whole number and this is the normal case , then s is usually rounded up to the next larger integer S. Each array component then occupies S words, whereby S-s words are left unused see Figs. Rounding up of the number of words needed to the next whole number is called padding.
Padded representation of a record Since an implementor has to aim for a storage utilization as close to 1 as possible, and since accessing parts of words is a cumbersome and relatively inefficient process, he or she must compromise.
The following considerations are relevant: 1. Padding decreases storage utilization. Omission of padding may necessitate inefficient partial word access. Partial word access may cause the code compiled program to expand and therefore to counteract the gain obtained by omission of padding. In fact, considerations 2 and 3 are usually so dominant that compilers always use padding automatically.
This technique is called packing. If n components are packed into a word, the utilization factor is see Fig. Packing 6 components into one word Access to the i-th component of a packed array involves the computation of the word address j in which the desired component is located, and it involves the computation of the respective component position k within the word.
However, it should be possible to indicate the desirability of packing at least in those cases in which more than one component would fit into a single word, i. Representation of Records Records are mapped onto a computer store by simply juxtaposing their components. The address of a component field r i relative to the origin address of the record r is called the field's offset k i. The generality of the record structure does unfortunately not allow such a simple, linear function for offset address computation, and it is therefore the very reason for the requirement that record components be selectable only by fixed identifiers.
This restriction has the desirable benefit that the respective offsets are known at compile time. The resulting greater efficiency of record field access is well-known. The technique of packing may be beneficial, if several record components can be fitted into a single storage word see Fig. Since offsets are computable by the compiler, the offset of a field packed within a word may also be determined by the compiler.
This means that on many computers packing of records causes a deterioration in access efficiency considerably smaller than that caused by the packing of arrays. Representation of a packed record 1. Representation of Sets A set s is conveniently represented in a computer store by its characteristic function C s.
It therefore appears that in order to be able to implement the basic set operations in an efficient manner, sets must be represented in a small, fixed number of words upon which not only the basic logical operations, but also those of shifting are available. Testing for membership is then implemented by a single shift and a subsequent sign bit test operation. The File or Sequence Another elementary structuring method is the sequence.
A sequence is typically a homogeneous structure like the array. That is, all its elements are of the same type, the base type of the sequence. This structure looks exactly like the array. The essential difference is that in the case of the array the number of elements is fixed by the array's declaration, whereas for the sequence it is left open.
This implies that it may vary during execution of the program. Although every sequence has at any time a specific, finite length, we must consider the cardinality of a sequence type as infinite, because there is no fixed limit to the potential length of sequence variables.
A direct consequence of the variable length of sequences is the impossibility to allocate a fixed amount of storage to sequence variables.
Instead, storage has to be allocated during program execution, namely whenever the sequence grows. Perhaps storage can be reclaimed when the sequence shrinks.
All structures with variable size share this property, which is so essential that we classify them as advanced structures in contrast to the fundamental structures discussed so far.
What, then, causes us to place the discussion of sequences in this chapter on fundamental structures? The primary reason is that the storage management strategy is sufficiently simple for sequences in contrast to other advanced structures , if we enforce a certain discipline in the use of sequences. In fact, under this proviso the handling of storage can safely be delegated to a machanism that can be guaranteed to be reasonably effective.
The secondary reason is that sequences are indeed ubiquitous in all computer applications. This structure is prevalent in all cases where different kinds of storage media are involved, i. The discipline mentioned is the restraint to use sequential access only.
By this we mean that a sequence is inspected by strictly proceeding from one element to its immediate successor, and that it is generated by repeatedly appending an element at its end.
The immediate consequence is that elements are not directly accessible, with the exception of the one element which currently is up for inspection. It is this accessing discipline which fundamentally distinguishes sequences from arrays. As we shall see in Chapter 2, the influence of an access discipline on programs is profound. The advantage of adhering to sequential access which, after all, is a serious restriction, is the relative simplicity of needed storage management.
But even more important is the possibility to use effective buffering techniques when moving data to or from secondary storage devices. Sequential access allows us to feed streams of data through pipes between the different media. Buffering implies the collection of sections of a stream in a buffer, and the subsequent shipment of the whole buffer content once the buffer is filled.
This results in very significantly more effective use of secondary storage. Given sequential access only, the buffering mechanism is reasonably straightforward for all sequences and all media. It can therefore safely be built into a system for general use, and the programmer need not be burdened by incorporating it in the program.
Such a system is usually called a file system, because the high-volume, sequential access devices are used for permanent storage of persistent data, and they retain them even when the computer is switched off. The unit of data on these media is commonly called sequential file.
Here we will use the term file as synonym to sequence. There exist certain storage media in which the sequential access is indeed the only possible one. Among them are evidently all kinds of tapes. But even on magnetic disks each recording track constitutes a storage facility allowing only sequential access. Strictly sequential access is the primary characteristic of every mechanically moving device and of some other ones as well. It follows that it is appropriate to distinguish between the data structure, the sequence, on one hand, and the mechanism to access elements on the other hand.
The former is declared as a data structure, the latter typically by the introduction of a record with associated operators, or, according to more modern terminology, by a rider object. The distinction between data and mechanism declarations is also useful in view of the fact that several access points may exist concurrently on one and the same sequence, each one representing a sequential access at a possibly different location.
We summarize the essence of the foregoing as follows: 1. Arrays and records are random access structures. They are used when located in primary, random-access store. Sequences are used to access data on secondary, sequential-access stores, such as disks and tapes. We distinguish between the declaration of a sequence variable, and that of an access mechanism located at a certain position within the seqence. Hence, although we may here refer to the i-th element of a sequence s by writing si, this shall not be possible in a program.
Such a device retains the data even if a program is terminated, or a computer is switched off. Therefore the introduction of a file variable is a complex operation connecting the data on the external device with the file variable in the program.
We therefore define the type File in a separate module, whose definition specifies the type together with its operators. Evidently, the set of operators must contain an operator for generating writing and one for inspecting reading a sequence.
We postulate that these operations apply not to a file directly, but to an object called a rider, which itself is connected with a file sequence , and which implements a certain access mechanism.
The sequential access discipline is guaranteed by a restrictive set of access operators procedures. A sequence is generated by appending elements at its end after having placed a rider on the file. It is denoted by r. Furthermore, we postulate that a rider contain a predicate flag r. We can now postulate and describe informally the following set of primitive operators: 1a. New f, name defines f to be the empty sequence. Old f, name defines f to be the sequence persistently stored with given name.
Set r, f, pos associate rider r with sequence f, and place it at position pos. Write r, x place element with value x in the sequence designated by rider r, and advance. Read r, x assign to x the value of the element designated by rider r, and advance.
Close f registers the written file f in the persistent store flush buffers. Note: Writing an element in a sequence is often a complex operation. However, mostly, files are created by appending elements at the end. In order to convey a more precise understanding of the sequencing operators, the following example of an implementation is provided. It shows how they might be expressed if sequences were represented by arrays.
This example of an implementation intentionally builds upon concepts introduced and discussed earlier, and it does not involve either buffering or sequential stores which, as mentioned above, make the sequence concept truly necessary and attractive. The operators are presented in terms of conventional procedures. This collection of definitions of types, variables, and procedure headings signatures is called a definition. We assume that we are to deal with sequences of characters, i.
The declarations of File and Rider are good examples of an application of record structures because, in addition to the field denoting the array which represents the data, further fields are required to denote the current length and position, i.
A definition represents an abstraction. Here we are given the two data types, File and Rider, together with their operations, but without further details revealing their actual representation in store.
Of the operators, declared as procedures, we see their headings only. This hiding of the details of implementation is intentional.
The concept is called information hiding. About riders we only learn that there is a property called eof. This flag is set, if a read operation reaches the end of the file. The invariant expresses the fact that the position always lies within the limits given by the associated sequence.
The invariant is established by procedure Set, and required and maintained by procedures Read and Write. The statements that implement the procedures and further, internal details of the data types, are sepecified in a construct called module. Many representations of data and implementations of procedures are possible. Note that in this example the maximum length that sequences may reach is an arbitrary constant.
Should a program cause a sequence to become longer, then this would not be a mistake of the program, but an inadequacy of this implementation. On the other hand, a read operation proceeding beyond the current end of the sequence would indeed be the program's mistake.
Here, the flag r. Buffering sequences When data are transferred to or from a secondary storage device, the individual bits are transferred as a stream. Usually, a device imposes strict timing constraints upon the transmission. For example, if data are written on a tape, the tape moves at a fixed speed and requires the data to be fed at a fixed rate. When the source ceases, the tape movement is switched off and speed decreases quickly, but not instantaneously.
Thus a gap is left between the data transmitted and the data to follow at a later time. In order to achieve a high density of data, the number of gaps ought to be kept small, and therefore data are transmitted in relatively large blocks once the tape is moving. Similar conditions hold for magnetic disks, where the data are allocated on tracks with a fixed number of blocks of fixed size, the so-called block size.
Our programs, however, do not observe any such timing constraints. In order to allow them to ignore the constraints, the data to be transferred are buffered. They are collected in a buffer variable in main store and transferred when a sufficient amount of data is accumulated to form a block of the required size.
Buffering has an additional advantage in allowing the process which generates receives data to proceed concurrently with the device that writes reads the data from to the buffer. In fact, it is convenient to regard the device as a process itself which merely copies data streams. The buffer's purpose is to provide a certain degree of decoupling between the two processes, which we shall call the producer and the consumer.
If, for example, the consumer is slow at a certain moment, it may catch up with the producer later on. The degree of decoupling grows with increasing buffer size.
We now turn to the question of how to represent a buffer, and shall for the time being assume that data elements are deposited and fetched individually instead of in blocks. A buffer essentially constitutes a first- in-first-out queue fifo. If it is declared as an array, two index variables, say in and out, mark the positions of the next location to be written into and to be read from. Ideally, such an array should have no index bounds.
A finite array is quite adequate, however, considering the fact that elements once fetched are no longer relevant. Their location may well be re-used. This leads to the idea of the circular buffer. The operations of depositing and fetching an element are expressed in the following module, which exports these operations as procedures, but hides the buffer and its index variables - and thereby effectively the buffering mechanism - from the client processes.
This mechanism also involves a variable n counting the number of elements currently in the buffer. Not meeting the former condition must be regarded as a programming error, a violation of the latter as a failure of the suggested implementation buffer too small. This simple implementation of a buffer is acceptable only, if the procedures deposit and fetch are activated by a single agent once acting as a producer, once as a consumer.
If, however, they are activated by individual, concurrent processes, this scheme is too simplistic. The reason is that the attempt to deposit into a full buffer, or the attempt to fetch from an empty buffer, are quite legitimate.
The execution of these actions will merely have to be delayed until the guarding conditions are established. Such delays essentially constitute the necessary synchronization among concurrent processes. Buffering between Concurrent Processes The presented solution is, however, not recommended, even if it is known that the two processes are driven by two individual engines.
The reason is that the two processors necessarily access the same variable n, and therefore the same store. The idling process, by constantly polling the value n, hinders its partner, because at no time can the store be accessed by more than one process. This kind of busy waiting must indeed be avoided, and we therefore postulate a facility that makes the details of synchronization less explicit, in fact hides them. We shall call this facility a signal, and assume that it is available from a utility module Signals together with a set of primitive operators on signals.
If a process needs to be delayed until Ps is established by some other process , it must, before proceeding, wait for the signal s. This is to be expressed by the statement Wait s. If, on the other hand, a process establishes Ps, it thereupon signals this fact by the statement Send s. If Ps is the established precondition to every statement Send s , then P s can be regarded as a postcondition of Wait s. Init nonfull ; Signals. Init nonempty END Buffer1. An additional caveat must be made, however.
The scheme fails miserably, if by coincidence both consumer and producer or two producers or two consumers fetch the counter value n simultaneously for updating.
It is indeed necessary to protect the processes from dangerous interference. In general, all operations that alter the values of shared variables constitute potential pitfalls. A sufficient but not always necessary condition is that all shared variables be declared local to a module whose procedures are guaranteed to be executed under mutual exclusion. Such a module is called a monitor [].
The mutual exclusion provision guarantees that at any time at most one process is actively engaged in executing a procedure of the monitor. Should another process be calling a procedure of the same monitor, it will automatically be delayed until the first process has terminated its procedure. Niklaus Wirth. Prentice Hall. David Watt , Deryck Brown.
Since Free ebooks since ZLibrary app.
0コメント