Concepts
Similar pages
| Similarity |
Page |
Snapshot |
| 80 |
is given in Figure 4
...img src Fig
...A modification of the implementation of a list structure like this which makes it resemble a set of ring structures is to make the right hand pointer of the last element of a sublist point back to the head of the sublist
...One disadvantage associated with the use of list and ring structures for representing classifications is that they can only be entered at the top
...Another modification of the simple list representation has been studied extensively by Stanfel [21,22]and Patt A HREF REF
... |
| 77 |
is no K 3 list,the field reserved for its pointer could well have been omitted
...The multi list is designed to overcome the difficulties of updating an inverted file
...Cellular multi lists A further modification of the multi list is inspired by the fact that many storage media are divided into pages,which can be retrieved one at a time
...At this point the full power of the notation introduced before comes into play
...Ki,ni,hi,ai 1,...where the hi have beenpicked to ensure that a Ki list does not cross a page boundary
...Ring structures A ring is simply a linear list that closes upon itself
... |
| 71 |
To unify the discussion of file structures we need some further concepts
...1 the K pointers are distinct;2 each non null K pointer in L gives the address of a record within L;3 there is a unique record in L not pointed to by any record containing K;it is called the beginning of the list;and 4 there is a unique record in L containing the null K pointer;it is the end of the list
...Hsiao and Harary state condition 2 slightly differently so that no two K lists have a record in common;this only appears to complicate things
...From our previous example:K 1 list:R 1,R 2,R 5 K 2 list:R 2,R 4 K 4 list:R 1,R 2,R 3 Finally,we need the definition of a directory of a file
...Ki,ni,hi,ai 1,ai 2,...We are now in a position to give a unified treatment of sequential files,inverted files,index sequential files and multi list files
...Sequential files A sequential file is the most primitive of all file structures
...The implementation of this file structure requires the use of asorting routine
... |
| 70 |
The fields are not necessarily constant in length
...In the same picture I have also shown some fields labelled Pi
...To indicate that a record is the last record pointed to in a list of records we use the null pointer [[logicaland]]... |
| 82 |
access to the records is given in Figure 4
...1 when the key is exhausted,that is,no more key symbols are left to match;or 2 when no matching symbol is found at the current level
...For case 1 we have:a the key is present if the P 1 pointer in the same cell as the last matching symbol now points to a record;b P 1 points to a further symbol,that is,the key falls short and is therefore not in the structure
...For case 2,we also have that the key is not in the structure,but now there is a mismatch
...Stanfel and Patt have concentrated on generating search trees with minimum expected search time,and preserving this property despite updating
... |
|
|
