ic2 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150
  1. .NH 2
  2. Representation of complex data structures in a sequential file
  3. .PP
  4. Most programmers are quite used to deal with
  5. complex data structures, such as
  6. arrays, graphs and trees.
  7. There are some particular problems that occur
  8. when storing such a data structure
  9. in a sequential file.
  10. We call data that is kept in
  11. main memory
  12. .UL internal
  13. ,as opposed to
  14. .UL external
  15. data
  16. that is kept in a file outside the program.
  17. .sp
  18. We assume a simple data structure of a
  19. scalar type (integer, floating point number)
  20. has some known external representation.
  21. An
  22. .UL array
  23. having elements of a scalar type can be represented
  24. externally easily, by successively
  25. representing its elements.
  26. The external representation may be preceded by a
  27. number, giving the length of the array.
  28. Now, consider a linear, singly linked list,
  29. the elements of which look like:
  30. .DS
  31. record
  32. data: scalar_type;
  33. next: pointer_type;
  34. end;
  35. .DE
  36. It is significant to note that the "next"
  37. fields of the elements only have a meaning within
  38. main memory.
  39. The field contains the address of some location in
  40. main memory.
  41. If a list element is written to a file in
  42. some program,
  43. and read by another program,
  44. the element will be allocated at a different
  45. address in main memory.
  46. Hence this address value is completely
  47. useless outside the program.
  48. .sp
  49. One may represent the list by ignoring these "next" fields
  50. and storing the data items in the order they are linked.
  51. The "next" fields are represented \fIimplicitly\fR.
  52. When the file is read again,
  53. the same list can be reconstructed.
  54. In order to know where the external representation of the
  55. list ends,
  56. it may be useful to put the length of
  57. the list in front of it.
  58. .sp
  59. Note that arrays and linear lists have the
  60. same external representation.
  61. .PP
  62. A doubly linked, linear list,
  63. with elements of the type:
  64. .DS
  65. record
  66. data: scalar_type;
  67. next,
  68. previous: pointer_type;
  69. end
  70. .DE
  71. can be represented in precisely the same way.
  72. Both the "next" and the "previous" fields are represented
  73. implicitly.
  74. .PP
  75. Next, consider a binary tree,
  76. the nodes of which have type:
  77. .DS
  78. record
  79. data: scalar_type;
  80. left,
  81. right: pointer_type;
  82. end
  83. .DE
  84. Such a tree can be represented sequentially,
  85. by storing its nodes in some fixed order, e.g. prefix order.
  86. A special null data item may be used to
  87. denote a missing left or right son.
  88. For example, let the scalar type be integer,
  89. and let the null item be 0.
  90. Then the tree of fig. 3.1(a)
  91. can be represented as in fig. 3.1(b).
  92. .DS
  93. .ft 5
  94. 4
  95. / \e
  96. 9 12
  97. / \e / \e
  98. 12 3 4 6
  99. / \e \e /
  100. 8 1 5 1
  101. .ft R
  102. Fig. 3.1(a) A binary tree
  103. .ft 5
  104. 4 9 12 0 0 3 8 0 0 1 0 0 12 4 0 5 0 0 6 1 0 0 0
  105. .ft R
  106. Fig. 3.1(b) Its sequential representation
  107. .DE
  108. We are still able to represent the pointer fields ("left"
  109. and "right") implicitly.
  110. .PP
  111. Finally, consider a general
  112. .UL graph
  113. , where each node has a "data" field and
  114. pointer fields,
  115. with no restriction on where they may point to.
  116. Now we're at the end of our tale.
  117. There is no way to represent the pointers implicitly,
  118. like we did with lists and trees.
  119. In order to represent them explicitly,
  120. we use the following scheme.
  121. Every node gets an extra field,
  122. containing some unique number that identifies the node.
  123. We call this number its
  124. .UL id.
  125. A pointer is represented externally as the id of the node
  126. it points to.
  127. When reading the file we use a table that maps
  128. an id to the address of its node.
  129. In general this table will not be completely filled in
  130. until we have read the entire external representation of
  131. the graph and allocated internal memory locations for
  132. every node.
  133. Hence we cannot reconstruct the graph in one scan.
  134. That is, there may be some pointers from node A to B,
  135. where B is placed after A in the sequential file than A.
  136. When we read the node of A we cannot map the id of B
  137. to the address of node B,
  138. as we have not yet allocated node B.
  139. We can overcome this problem if the size
  140. of every node is known in advance.
  141. In this case we can allocate memory for a node
  142. on first reference.
  143. Else, the mapping from id to pointer
  144. cannot be done while reading nodes.
  145. The mapping can be done either in an extra scan
  146. or at every reference to the node.