Organizing information

“Organizing information” Contents 1. Introduction 2. The database a) How is a database constructed? 3. Data structures a) Pointers b) Strings c) Arrays d) Static and Dynamic Data Structures e) Stacks 4. Lists 5. Trees 1. Information worked by the computer can organized in a variety of ways.

Two important ways are that of a database and a spreadsheet. On a database, work is arranged in fields and we will discuss these presently. A spreadsheet will allow the user to keep accounts, make calculations and change information as necessary. 2. The database A database is a sort of store where information is kept in an organized way. Access is gained through a keyboard or a special keypad which is a small hand-held unit containing

keys which are pressed to work the set. The information can be of many different kinds. It is not always possible to gain access to a database and sometimes private pass-words are required in order that only certain people gain access. Some databases can be accessed through a specially adapted TV set using a modem. A modem is a small box that is specially made to change data into digital signals which can be sent through the telephone network. A database that can be accessed in this way is the

Prestel system, consisting of thousands of pages of information and sometimes offered by libraries. Information given on Prestel is of a general nature, concerning such topics as entertainment, books for sale, airline journeys and so on. Information on a company database may, however, be of a very different kind. Such information might include names and addresses of employees, their salaries and general state of health. It might include goods manufactures by the company and suggested price lists.

Much of the information a company might keep will probably be quite harmless, but other, more personal information about the company itself might be of a highly confidential nature requiring close security. a) How is a database constructed? A database can be organized in a variety of different ways depending upon the type of data that is to be stored. Take for instance a large collection of names and addresses, along with telephone numbers. This information will need to be broken down into fields, that is, in

this case, the first name, surname, address and so on. Each category is known as a field. The field is either string (letters), or numeric (numbers). The database program usually asks you for your choice. These fields will be organized as: Fields 1: surname (string) Fields 2: fist name (string) Fields 3: age (numeric)

Once the database has been set up, the computer will ask for the categories and they will be filled in as records. By using special commands the computer as able to search for names, addresses, telephone numbers or other fields and change, replace, add to, or even delete them altogether. Keeping information by this method saves much time and energy. Banks and building societies keep a lot of information about customers in this way.

Record № 8 Surname: Jones First name: Michael Address1: 33 Torr road Address2: Liverpool Telephone: 221-668973 Age: 3. Data structures 1. Most of the information we encounter in everyday life is structured in some way the commonest example is the words of our language, which are linked together in phrases, sentences and other more complex structures. The rules for constructing these structures are extremely complicated,

yet we apply them by intuition. 2. Other examples of structured information include dictionaries, telephone directories and encyclopedias. These are all stores of information which would be useless if the information were not strictly arranged according to ma few simple rules. The structure of a collection of information makes it easy to locate individual items of information, and to insert new items, or delete items. The same reasoning applies to structured information stored

in computers. a) Pointers 3. A pointer is a data item which indicates the location of another data item. It may be thought of as an arrow, as show in Figure 4. Pointers are used to build data structures. They provide the links which join elements of the structure. Of particular significance are pointers to the front and back of a data structure. Occasionally it is required that a pointer does not point to anything; in this situation, the pointer

is said to have a null value. See Figure 2. Figure 1. Figure 2. b) Strings 5. A string is a sequence of characters regarded as a single data item. Strings may be of fixed or variable length. The length of a string is indicated either by the number of characters in the string placed at the front of the string, or by a special character called an end-of-string marker at the end. The following example shows these two methods of representing the same

sting: 10CAPITAL194 CAPITAL194# Operations on sting are of two types: operations which join two or more strings to produce two or more sub-string. c) Arrays 6. An array is a set of data items of identical types, stored together. The numbers of elements in the array is fixed when the array is created. Each element is accessed by an index, which indicates the position of the element in the array.

7. For example, if the array BEATLES has elements as follows: BEATLES: JONH PAUL GEORGE RINGO then the element with index value 3, BEATLES(3) is the name GEORGE. 8. Arrays can have more than one dimension. A two-dimensional array may be thought of as having rows and columns like a matrix. Two indices are required to locate an item in the array, corresponding to row and column indices in

a matrix. For example, the state of a game of noughts and crosses may be represented by a two-dimensional array, GAME with three rows and three columns: GAME: O X O X X O O X If the top left element is GAME (1, 1), then the O in the third column of the second row is GAME (2, 3) and the blank element is GAME (3, 1). d) Static and Dynamic Data Structures 9.

An array is a static data structure, that is to say, is stays the same size once it has been created. Data structures which change in size once they have been created are called dynamic data structures. A string can be a static or a dynamic data structure. The structures introduced in the remainder of this shapter are dynamic data structures. They generally require pointers for their implementation. e)

Stacks 10. You have probably seen the way in which plates are sometimes stored in restaurants. A pile of plates is supported on a spring. As a new plate is put on top of the pile, it pushes the rest down. When a plate is taken from the pile, the next plate pops up. Such a structure is a stack in the computing sense of the word. A stack is a collection of data items which may only be accessed at one end, called the top of the

stack. 11. Only two operations may be carried out on a stack. Adding a new item, called pushing or stacking the item, involves placing in on top of the stack. Removing an item involves popping it from the stack. 12. If a number of items are pushed onto a stack, and then popped from the stack, the last item added well be the first one removed. For this reason a stack is called a last-in-first-out (LIFO) stack.

Other names for a stack are push-down stack and push-down list. 13. When a stack is stored in a computer memory, the elements do not move up and down as the stack is pushed and popped. Instead, the position of the top of the stack changes. A pointer called a stack pointer indicates the position of the top of the stack. Another pointer is used to indicate the base of the stack.

This pointer, called the stack base, keeps the same value as long as the stack is in existence. Figure 3 shows a stack pointer and stack base in use. If the sequence of operations pop, pop, push 5.9, is carried out n this stack, the result is shown in Figure 4. 3-5 Stack base 14. The stack is one the most important data structures in computing. Stacks are used in calculations, for translating from one computer language to another, and for transferring

control from one pert of a program to another. Most modern processors include a stack pointer as an architectural feature, and some regard their entire memory as a set of stacks. 15. In spite of the American origins of many ideas associated with computers, that great British institution, the queue, has found its way into the theory o computing. Everyone knows how a queue works: newcomers join at the rear, service is provided at the front, and

no pushing-in is allowed. Exactly the same rules apply to queues of data stored in a computer memory^ data items are added at the back and removed from the front. A queue is a first-in-first-out (FIFO) data structure. 16. Although queues are used slightly less frequently than stacks, they do have a variety of applications. These include queuing data items in transit between a processor and a peripheral device, or at intermediate

points in a data communications network. 4. Lists A list is a set of data items stored in some order. Data items may be inserted or deleted at any point in the list. In this respect, a list is less restrictive than a stack or queue. The simplest way of implementing a list makes use of a pointer from each item to the one following it in the list. There is also a pointer to the start of the list, while the last item it the list has

a null pointer. See Figure 5. A data structure of this type is also known as a linked link. A list element consists of a data item and its pointer. In many applications a list element contains a number of data items. Since elements can easily be added to the rear or removed from the front of the linked list, this structure my also be used to implement a queue. Inserting an element into a list is achieved by adjusting the

pointers to include the new element. See Figure 6. Removing an element is achieved in a similar way, as shown in Figure 7. Data items in a lust are in order, in the sense that one data item is behind another in the list. Lists are, however, frequently used in cases where the data items are in numerical or alphabetical order. Such lists are called ordered lists. Lists are very useful for storing ordered sets of data,

if insertions and deletions of data items are frequent. Data items may themselves be entire lists. Lists of this nature are widely used in artificial intelligence research, and form the basis of the programming language Lisp. 5. Trees We are all familiar with phrases “family tree” and “getting to the top of the tree”. In this sense, a tree is a structure implying a hierarchy, with each element of the tree being linked

to elements below it. For example, the tree in Figure 7 shows the descendants of Queen Elizabeth II. Each data item in a tree is at a node of the tree. The node at the top of the tree is called the root. Each node may be connected to one or more subtrees, which also have a tree structure. A node at the bottom the tree, which has no subtrees, is called a terminal node, or a leaf.

See Figure 9. A number of operations may be carried out on trees. Two binary trees may be joined to en additional node, which becomes the root a larger binary tree, with the original trees as subtrees. A tree may be traversed in several ways. Traversing a tree is accessing its elements in a systematic way. See Figure 10. Tress Have a number of applications in computing.

The modules of many programs are linked together in a tree structure. Trees are also used to represent arithmetic expressions, and for sorting and searching. Some computers regard their entire memory as if it were partitioned into a tree structure. The essential feature of a tree is that each node is connected to subtrees, which themselves have the structure of trees. In other words, wherever you are in a tree, the structure “below” you is a tree.

In this sense a tree is a recursive data structure, and can be manipulated by recursive programs. This is the property of tree which makes them so useful from a computing point of view. A number of program languages require that the type of each data item be declared before the data item is used in a program. A data item may be an integer, an array, or a list, to name just a few examples.