Топик: Organizing information
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 