123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150 |
- .NH 2
- Representation of complex data structures in a sequential file
- .PP
- Most programmers are quite used to deal with
- complex data structures, such as
- arrays, graphs and trees.
- There are some particular problems that occur
- when storing such a data structure
- in a sequential file.
- We call data that is kept in
- main memory
- .UL internal
- ,as opposed to
- .UL external
- data
- that is kept in a file outside the program.
- .sp
- We assume a simple data structure of a
- scalar type (integer, floating point number)
- has some known external representation.
- An
- .UL array
- having elements of a scalar type can be represented
- externally easily, by successively
- representing its elements.
- The external representation may be preceded by a
- number, giving the length of the array.
- Now, consider a linear, singly linked list,
- the elements of which look like:
- .DS
- record
- data: scalar_type;
- next: pointer_type;
- end;
- .DE
- It is significant to note that the "next"
- fields of the elements only have a meaning within
- main memory.
- The field contains the address of some location in
- main memory.
- If a list element is written to a file in
- some program,
- and read by another program,
- the element will be allocated at a different
- address in main memory.
- Hence this address value is completely
- useless outside the program.
- .sp
- One may represent the list by ignoring these "next" fields
- and storing the data items in the order they are linked.
- The "next" fields are represented \fIimplicitly\fR.
- When the file is read again,
- the same list can be reconstructed.
- In order to know where the external representation of the
- list ends,
- it may be useful to put the length of
- the list in front of it.
- .sp
- Note that arrays and linear lists have the
- same external representation.
- .PP
- A doubly linked, linear list,
- with elements of the type:
- .DS
- record
- data: scalar_type;
- next,
- previous: pointer_type;
- end
- .DE
- can be represented in precisely the same way.
- Both the "next" and the "previous" fields are represented
- implicitly.
- .PP
- Next, consider a binary tree,
- the nodes of which have type:
- .DS
- record
- data: scalar_type;
- left,
- right: pointer_type;
- end
- .DE
- Such a tree can be represented sequentially,
- by storing its nodes in some fixed order, e.g. prefix order.
- A special null data item may be used to
- denote a missing left or right son.
- For example, let the scalar type be integer,
- and let the null item be 0.
- Then the tree of fig. 3.1(a)
- can be represented as in fig. 3.1(b).
- .DS
- .ft 5
- 4
- / \e
- 9 12
- / \e / \e
- 12 3 4 6
- / \e \e /
- 8 1 5 1
- .ft R
- Fig. 3.1(a) A binary tree
- .ft 5
- 4 9 12 0 0 3 8 0 0 1 0 0 12 4 0 5 0 0 6 1 0 0 0
- .ft R
- Fig. 3.1(b) Its sequential representation
- .DE
- We are still able to represent the pointer fields ("left"
- and "right") implicitly.
- .PP
- Finally, consider a general
- .UL graph
- , where each node has a "data" field and
- pointer fields,
- with no restriction on where they may point to.
- Now we're at the end of our tale.
- There is no way to represent the pointers implicitly,
- like we did with lists and trees.
- In order to represent them explicitly,
- we use the following scheme.
- Every node gets an extra field,
- containing some unique number that identifies the node.
- We call this number its
- .UL id.
- A pointer is represented externally as the id of the node
- it points to.
- When reading the file we use a table that maps
- an id to the address of its node.
- In general this table will not be completely filled in
- until we have read the entire external representation of
- the graph and allocated internal memory locations for
- every node.
- Hence we cannot reconstruct the graph in one scan.
- That is, there may be some pointers from node A to B,
- where B is placed after A in the sequential file than A.
- When we read the node of A we cannot map the id of B
- to the address of node B,
- as we have not yet allocated node B.
- We can overcome this problem if the size
- of every node is known in advance.
- In this case we can allocate memory for a node
- on first reference.
- Else, the mapping from id to pointer
- cannot be done while reading nodes.
- The mapping can be done either in an extra scan
- or at every reference to the node.
|