INSTITUTE OF MANAGEMENT, BUSINESS AND LOW
Donetsk branch
COURSE PAPER
IN ENGLISH
On the topic
“Organizing information”
Made by Perkov Aleksey,
1st year student of IT department
Checked by Dronova Valentina,
Teacher of English
Donetsk
2009
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. Introduction
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: 41
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 1.
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.