Received assignment which is to cover element 3. 1 all PCs. My initial task is to Gather all relevant information on the basic data structures for storage and retrieval. I will research through lecture notes and the books BTEC Information Technology, BTEC in Computing, File structures theory and practice, as well as to search through the CD ROM Groliers Encyclopaedia. Take notes on any relevant Information 9/5/95 – 11/5/95 Research information on the way that Basic data structures are analysed for different applications. Research through above books and CD ROM’s and take relevant notes.
11/5/95 13/5/95 Find out about logical and physical file organisation, with regards to PC3 Element 6. 1 of the log book. Take notes on relevant Information. 13/5/95 – 15/5/95 16/5/95 18/5/95 Research information using methods as above with regards to how the physical file organisation is analysed in relation to different media, PC4. Make notes Research information to cover PC 5, which needs me to explain location and access methods. Use literature as above 19/5/95 Word process first draft, and take to tutor for first review After outcome of first review take tutors advice accordingly.
20/5/95 Check work to see if any important facts have been omitted, ask Tutor for a second review. After outcome of second review finalise any missing facts. Word process final draft, check the work for mistakes and hand in finished report for 1/6/95 Nicky Wilson GNVQ Advanced IT Investigate data Structure for storage and Retrieval Element 6. 1 Introduction The report will analyse basic data structures for different applications and physical file organisation in relation to different media.
The report will also explain basic data structure for storage and retrieval, logical and physical file organisation and location and access methods. A data structure is essentially a number of data items, also called elements or nodes with some relationship linking them together. Each item consists of one or more named parts called fields occupying one or more memory locations in the computer. For instance a list of numbers occupying consecutive memory locations in a computer is a simple data structure. Array: This is an ordering of the data elements so that the data is able to be extracted in a logical fashion, shown below is a diagram showing an example of this 1 6 9 3 Dim x (3) Index value 7 4 4 1 Dim y (3) Index value.
Dim x (3,3) Index value 9 2 6 7 Dim y (3,3,3) Index value Stack: The stack is a data structure chacterized by the expression LIFO = Last in first out this means that most recent item added to the stack is the first one which can be removed from the stack. A stack pointer is used to keep track of the last item added to the stack, which is the current top of the stack. Stacks are frequently used for data temporary storage. One common application of stacks is for storing return addresses (link values) for closed routines. TOP SP BOTTOM A stack only has two operations PUSH: Add an item POP: Remove the top item.
FULL ; EMPTY: Stack pointer It can define maximum values only one end used. Queue: The data structure known as a queue has the same characteristics as the queues that we encounter in everyday life. A queue in a data structure in which elements are added only at the rear of the list and removed only from the front of the list. A queue structure is often given the name FIFO which stands for first In first out. Data in what we call a queue is not moved along like people in a cinema queue, instead each datum stays in its storage location until its turn comes, thereby reducing time spent in data movement.
The use of pointers makes this possible. FRONT BACK JOIN HERE Take items from the front, add items to the end. List: Lists provide a flexible way of handling data items in order. Changes to the order can be achieved with minimal data movement and little loss of storage space These can be ordered can contain N ; 0 items, each data is an element, 3, 4, 41, 62, 79, 8, 11 or FRED, JIM, ANDY, CHRIS, SID. Tree: The tree structure is an Hierarchical structure, the term tree refers to a non linear data structure in which nodes have two or more pointers to other nodes forming an hierarchical structure.
The top node is called the root node The bottom node are called leaf (Terminal nodes) and the nodes are connected by branches. Shown below is an example of a tree structure showing how a record in a employee file may have the structure shown below. Works Number Name County Sex Post Holidays Status Nation`ty phone Street Town Age Service Dept Years Salary Entitmnt Storage ; Retrieval For example in a banking organisation, the information that must be recorded could be information on a customers checking or savings account, on loan applications, about employees of banking institutions etc. Due
to the four parts of information, each part is related to as a file, so the banking organisation must record the information in four separate file shown below. Checking Savings Loan Employee Accounts Accounts Applications File File File File Records: Are a collection of related fields, an example to show this could be a record of an accounts file, which contains four fields. Illustrated below is a diagram showing this. ACCOUNT NAME ADDRESS BALANCE 9783 – 59 -812 JOE BLOGGS BLOGGS AVENUE 1000. 89 Files: Logical is referred to as the external view of the file a logical file is nothing more than a collection of all logical data.
Media Access: File storage media is of two main types, Serial access and direct access, below is a short explanation of the two. Serial Access media: This means that in order to access a particular record, it is necessary to read all records which precede it in the relevant file. An example of this storage medium is in normal cassette tape. A difficulty with this storage media is that there are no readily identifiable physical access areas on the medium which can be addressed, it is non addressable. Thus to look for an individual record the software needs to examine each record key field, in sequence from the start of the file until the required record is found.
Direct access media: This allows direct access to a particular record, for example floppy or Hard drives. They have physical divisions which can be identified by computer software, as well as hardware, and can be addressable so that particular locations can be referred to by name or code, to retrieve a record which is shared at the location. Basic data structures are analysed for different applications Input / output Queuing and spooling Computer and printer everytime you print work out in room 107 YCC you go into a queue, it stores the information and prints it out in the order it went in. Queuing information uses first in first out. If it was more advanced, for example you needed to have certain priorities for printing ( small files first) to make the system more efficient you would need to use a list structure.
Spooling is the other way round, putting things together ready to go out. It would be possible to use a queue data structure. Storage (tables, declarations, files, databases) Table for example containing storage devices. TABLE 0 1 2 3 4 0 1 2 3 Two dimensional, one column specifies, and one column specifies the row.
Stored in a two dimensional array structure. Files are made up by a number of logical records. 1 Dimensional array Dimensional array Field Record Record Record Record Record Problem must contain the same type of information Each box of array can only store the same type of Information Retrieval: All structure storage and retrieval vary from structure to structure. It may use a tree, to extract information from a tree the name given is traversing the tree or tree walking, for simplicity we will use binary trees. The reason for this is that each node can only have two branches. Left Subtree Node Right Subtree A B C D E F G.
Inorder Traversal: Traverse the left subtree, visit the node. Traverse the right subtree. = DBEEAFCG Preorder Traversal Start at Node A Traverse the left Subtree. = ABDECFG Post Order Traversal Traverse the left Traverse the right Return to the Root. (Node) = DEBFGCA. Searching For searching list and array structures. Compilation: is the process of translating a High level language into machine code (Basic, Pascal, FORTRAN) There are 3 main steps Lexical Syntax Analysis Data structures is what we are interested in Code generation Lexical analysis: This involves breaking the input to the compiler into chunks, also known as tokens.
Syntax Analysis: This involves checking whether the input tokens form valid sentences when put together. This process is known as parsing. The second process of syntax analysis involves determining the values of arithmetic expressions. Code Generation: The final stage of the compilation process, where the machine code is generated. Methods of Syntax Analysis Parse trees can be used to evaluate whether a statement has the correct syntax.
; CAR REGISTRATION ; LETTER ; ; DIGIT ; ; DIGIT ; ; DIGIT ; ; LETTER ; ; LETTER ; ; LETTER ; ; B 3 8 4 P H X Evaluate Arithmetical expressions Operands Operator e.g. ( 3 + 5 ) ( 9 – 7 ) It is far easier for the compiler to evaluate arithmetic expressions if they are presented in reverse (Polish fix) notation. Post fix notation is also known as Prefix notation because the operators precede the operands. e. g. + 35 – 97 * Polish notation ( 3 + 5 ) ( 9 – 7 ) + 3 5 9 7 Left hand side Polish Notation (Prefix Notation) Reverse Polish Notation (Post fix notation) Right hand side 35 + 97 – * Next data structure used is a Stack 35 + 97 – A stack is used to evaluate the reverse polish expression using the following rules 1. Operands are placed on the stack.
2. Operators are applied to the top two items on the stack and the result is placed on top of the stack. look at each item in turn 3 3 Place on the stack 5 5 Place on the stack 3 + 8 9 8 Operand goes on the stack 9 7 7 Operand goes on the stack 9 8 – 2 Operator applied to top item on stack 8 * 16 Apply to top two items on stack 8 * 2 Originally had ( 3 + 5 ) * ( 9 – 7 ) = 16 Logical file organisation is explained. Logical file structure Serial file: This is where the records are stored one after another with no regard to the order of the records. Shown below is an example.
Customer 27 Customer 6 Customer 33 Customer 49 Sequential access files These are the files where the records are stored one after another in a predetermined order. This is usually around the key field, when files of data are created you need a means of access to a particular record within those files. This is done by giving each record a key field by which the record can be recognised or identified. Examples of key fields could be Customer number in a customer ledger record Stock code number in a stock record * Employee clock number in a payroll record Customer 10 Customer 26 Customer 34 Customer 47
Indexed sequential file: Records are stored in a sequence like sequential, the important difference is that an index is provided to enable individual records to be located. Strictly speaking the records may not always be stored in sequence but the index will always enable the sequence to be determined. Illustrated below is an example of an indexed sequential file. 1 INDEX 2 3 1 . . 10 . 10 11 20 12 . . . 20 21 22 Random access file structure This allows the ability to retrieve a record without having to read all the records that appear before it in the file. it allows fast access to records it is ideally suited for Interactive systems.
Physical file organisation is analysed to different media Magnetic tape. Because of the physical characteristics of magnetic tape it is necessary when processing a file that the tape unit starts to read the tape unit at the beginning of the tape. Magnetic tape is a low cost high storage capacity device, its advantages are that it is very cheap. Files can be organised two ways serial and sequentially. Shown below is a diagram showing how a file is arranged on tape both logically and physically. Block or physical record File I I header R1 R2 R3 R4 B R5 R6 R7 B R9 R10 R11 R12 … label G G Logical Records Inter Block Gap.
Magnetic Disk: Magnetic disk provides storage facilities far more flexible than magnetic tape. The surface of the disk is divided into physical locations. It is a direct access medium. Magnetic disk supports the following file organisation methods Serial, Sequential. CD ROM Uses tracks to store the data on, the tracks are very close together . They have a mass storage capacity, they can hold about 600Mb of information and are direct access medium. Latest CDs now allow you to put information on and keep adding to it. RAM Random access memory is Electrical memory, it is a temporary store for holding programs and data that has either been put into the computer from either disk, typed at the keyboard or input from some other device.
This type of memory is called volatile memory that means that the contents of main memory can be destroyed, either by been overwritten or when the machine is switched off. It is direct access and very fast access, it has a limited capacity and is relatively expensive. Location and access methods are explained serial sequential order: The lowest value is at the top, and the highest at the bottom. You would start at the beginning and work your way, the advantage of using this way is if for instance if you wanted to find number 29,if by the time it gets to number 34 th value is not found, the search will be terminated immediately.
If it wasn’t sequential you would have to go through the entire list. 4 13 26 34 If number 29 is not found by here, search will be stopped 97 102 Serial search: Using a serial search you would go through the files in each order, look through data items one at a time, from the start of the data structure to the end. This can be a very inefficient type of search because all of the data items must be examined unless the data is ordered. This is the only type of search that can be used with unordered information.
Serial record search: This means that in order to identify and retrieve a particular record it is necessary to read all the records which precede it in the relevant file, until the file you require is found RECORD 1 RECORD 2 RECORD 3 RECORD 4 Evaluation I am happy with the outcome of the assignment, I feel that I have covered the criteria and the range that was required. The way I approached the assignment was as such, first of all I researched Information from the books Information Technology by Roger Carter, BTEC Computer Studies, Information Processing BTEC, A level BTEC and first degree computing.
The next process was to decide which way, was the best way to try and cover the PCs and ranges for the unit were covered. Eventually I reached the conclusion that it would be easier for me to work through the PCs in the order that they appear in the log book. Thus starting with PC1. The other way I thought of approaching the assignment was to start by doing PC1 first but to try and bring in other elements of the ranges in accordingly. The reason why I opted out of doing it this way was because I thought that it would make it more difficult.
The way that I tried to checked the validity of the Information was by, trying to compare the information that I had it with the different books and CD ROM’s to see if it was correct. This way proved hard. In my opinion it is hard to judge the validity of the information for this assignment, because certain areas relating to this subject is hard to find a wide range of Information on. I have not done the work as instructed on my action plan, I have had reviews by tutor earlier than stated in my action plan, the reason for this is because I have other assignments that need completing. If any criticism is to be applied to my work, I feel that I have not gone into depth with certain parts of the assignment, but elaborated too much on other areas.
Bibliography Books and CD ROM’s Used Computer Studies for BTEC (3rd Edition) Geoffrey Knott, Nick Waites, Paul Callaghan, John Ellison. Business Education Publisher ltd. 1993 Information Processing for BTEC 2nd Edition Geoffrey Knott, Nick Waites, Paul Callaghan, John Ellison. Business Education Publisher ltd. 1990. A level, BTEC & first degree Computing by Nick Waites, Geoffrey Knott. Business Education Publishers Limited 1992 Information Technology by Roger Carter, first published 1991, reprinted 1992. Encarta encyclopaedia, Times, Guardian, Groliers Encyclopaedia (CD ROMS).