📄 http:^^www.cs.wisc.edu^~cs354-2^cs354^lec.notes^data.structures.html
字号:
Date: Tue, 05 Nov 1996 20:50:10 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Wed, 30 Aug 1995 21:21:35 GMTContent-length: 12971<html><head><title> Lecture notes - Chapter 7 - Data Structures</title></head><BODY><h1> Chapter 7 -- data structures</h1><pre>DATA STRUCTURES---------------common theme in programming: SPACE vs. TIME tradeoff space is memory space time is time to execute program it is often possible to write a program such that it 1. executes very fast, but wastes/utilizes more memory or 2. utilizes little memory, but executes quite slow data structures can make memory useage efficient or inefficientdata structures we will discuss: arrays, stacks, and queues (in that order)ARRAYS------array implementation is important 1. most assembly languages have no concept of arrays 2. from an array, any other data structure we might want can be builtProperties of arrays: 1. each element is the same size (char = 1 byte, integer = 1 word) 2. elements are stored contiguously, with the first element stored at the smallest memory addressso, the whole trick in assembly language is 1. allocate correct amount of space for an array 2. an ADDRESS tells the location of an elementmemory can be thought of as an array it is a giant array of bits or bytes or words (picture needed here!) the element numbering starts at 0 the element number is an address if each byte has a unique address, we have BYTE ADDRESSING. (the MIPS has this, as do many machines) SAL access of the memory array we can access any element (byte) of memory m[address] refers to the element (contents) at address m[20] is the byte numbered address 20, the 21st byte of memory. important: 20 is the address m[20] is the contents of the byte at address 20 M[address] refers to the element (contents) at address M[20] is the word at byte address 20, the 21st-24th byte of memory. it is common to have byte addressibility, and address words. A word address is defined to be the byte address of the smallest byte. There are also machines designed such that they only have word addressibility. (Then the words are numbered with unique addresses.) SAL declarations of arrays within memory to allocate a portion of memory (more than a single variable's worth) (allocating an array within memory) variablename: type initvalue:numelements type is just like before -- .byte, .word or .float numelements is just that, numbering ALWAYS starts at 0 initvalue is a value given to each element of the arraynew directive: name: .space numberofbytes .space is a way of allocating space (bytes) within memory, but not give them an initial value. Note: the type of the data within this space cannot be inferred. example: arrayname: .byte 0:8 8 character elements, numbered 0 - 7, initialized to 0 name: .space 18 18 bytes of memoryan example of how to calculate the address of an element: byte (character) elements -- array1: array[6..12] of char; /* PASCAL */ 6 7 8 9 10 11 12 <---- element index ----------------------------- | | | | |XXX| | | | | | | |XXX| | | ----------------------------- 25 26 27 28 29 30 31 <---- address byte address of array1[10] = 25 + (10 - 6) = 29 this same example (or close) only in SAL: array1: .byte 0:7 0 1 2 3 4 5 6 ----------------------------- | | | | |XXX| | | | | | | |XXX| | | ----------------------------- 25 26 27 28 29 30 31 <---- address want the 5th element, array1[4] is at address array1 + 4 If element[0] is at address 25, byte address of array1[4] = 25 + 4how do you get the address array1? SAL la (load address) instruction la addr, array1 takes the address array1 (25 in the example) and puts it into the variable called addr. this is where it is extremely important to understand and keep clear the difference between an address and the contents of an address. to reference array1[4] in SAL, write the code, la baseaddr, array1 add elem4, baseaddr, 4 # then if we wanted to decrement element number 4 sub m[elem4], m[elem4], 1 remember, elem4 is an address (declared as .word) m[elem4] is the byte at the address elem4 word (integer) elements -- array2: array[0..5] of integer; in SAL, array2: .word 0:6 (or array2: .space 24) 0 1 2 3 4 5 <-- index ------------------------- | | | |XXX| | | | | | |XXX| | | ------------------------- 80 84 88 92 96 100 <-- memory address byte address of array2[3] = 80 + 4(3 - 0) = 92 SO, we need to know 1. where the array starts (called base address) 2. size of an element in bytes (to get a byte address) 3. what the first element is numbered byte address of element[x] = base + size(x - first index)2 DIMENSIONAL ARRAYS--------------------There are more issues here, than for 1 dimensional arrays.First, how to map a 2 dimensional array onto a 1 dimensional memory? TERMINOLOGY: r x c array -- r rows c columns element[y, x] -- y is row number x is column number example: 4 x 2 array mapping this 4 x 2 array into memory.2 possiblilities: row major order: rows are all together | | ------- | 0,0 | ------- | 0,1 | ------- | 1,0 | ------- | 1,1 | ------- | 2,0 | ------- | 2,1 | ------- | 3,0 | ------- | 3,1 | ------- | |column major order: columns are all together | | ------- | 0,0 | ------- | 1,0 | ------- | 2,0 | ------- | 3,0 | ------- | 0,1 | ------- | 1,1 | ------- | 2,1 | ------- | 3,1 | ------- | | 2-D Arrays----------The goal: come up with a formula for calculating the address of an element of a 2-D array.Row Major: addr. of [y, x] = base + offset to + offset within correct row row (size)(y - first_row) (# columns) (size) (x - first_col)Column Major: addr. of [y, x] = base + offset to + offset within correct column column (size)(x - first_col) (# rows) (size) (y - first_row)Need to know: 1. row/column major (storage order) 2. base address 3. size of elements 4. dimensions of the arrayHINTS toward getting this correct: Draw pictures. Don't forget to account for size. BOUNDS CHECKING---------------Many HLL's offer some form of bounds checking. Your program crashes,or you get an error message if an array index is out of bounds example: x: array[1..6] of integer; code. . . y := x[8];Assembly languages offer no implied bounds checking.After all, if your program calculates an address of an element,and then loads that element (by the use of the address), there isno checking to see that the address calculated was actually withinthe array!example (to motivate some thought as to how to do bounds checking): given -- a 5 x 3 array byte size elements row major order first_row = 1 first_col = 1 what is the address of element[2, 5] a program probably just plugs the numbers into the formula: addr of [2, 5] = base + 1(2 - 1)(3) + 1(5) = base + 8 this actually gives the address of element [3, 3], still a valid element of the array, but not what was really required. . . STACKS------We often need a data structure that stores data in the reverseorder that it is used. Along with this is the concept that thedata is not known until the program is executed (RUN TIME).A STACK allows both properties.Abstractly, here is a stack. Analogy to stack of dishes.Also dubbed Last In First Out, LIFO. | | |-------| | | |-------| | | |-------| | | |-------| | | |-------|Data put into the stack is said to be PUSHED onto the stack.Data taken out of the stack is said to be POPPED off the stack.Example: printing out a positive integer, character by character (integer to character string conversion) integer = 1024 if integer == 0 then push '0' else while integer <> 0 digit <- integer mod base char <- digit + 48 push char onto stack integer <- integer div base while stack is not empty pop char put char IMPLEMENTATION OF A STACK-------------------------One implementation of a stack out of an array.Need to know: index of TOP OF STACK (tos), often called a stack pointer (sp). (initial state) sp | \ / ----------------------------- | | | | | | | | ----------------------------- sp is a variable that contains the address of the empty location at the top of the stack.for an array declared (in SAL) as stack: .word 0:50 sp: .word stack OR stack: .space 0:200 sp: .word stack New use of a directive for initial contents of sp. The address (label) stack gets put into the variable sp. Identical to use of la sp, stack # initialization of stack pointera PUSH operation: move M[sp], data add sp, sp, 4 a POP operation: sub sp, sp, 4 move data, M[sp] A stack could instead be implemented such that the stack pointerpoints to a FULL location at the top of the stack. (initial state) sp | \ / ----------------------------- | | | | | | | | -----------------------------a PUSH operation: add sp, sp, 4 move M[sp], data a POP operation: move data, M[sp] sub sp, sp, 4ANOTHER ALTERNATIVE: The stack could "grow" from the end of the array towards the beginning. (Note that which end of the array the stack grows toward is independent of what sp points to.)For the student to figure out: How do you know when there are no more items in the stack? How do you know when the stack is full? QUEUES-------whereas a stack is LIFO, a queue is FIFO (First In, First Out).a real life analogy is a line (called a queue in British English). Person gets on the end of the line (the TAIL), waits, and gets off at the front of the line (the HEAD).getting into the queue is an operation called ENQUEUE.taking something off the queue is an operation called DEQUEUE.it takes 2 pointers to keep track of the data structure, the head and the tail. initial state: -------------------------------------------- | | | | | | -------------------------------------------- ^ | head, and tail after 1 enqueue operation: -------------------------------------------- | | x | | | | -------------------------------------------- ^ ^ | | | tail head after another enqueue operation: -------------------------------------------- | | x | y | | | -------------------------------------------- ^ ^ | | | tail head after a dequeue operation: -------------------------------------------- | | x | y | | | -------------------------------------------- ^ ^ | | | tail head Note that (like stacks) when an item is removed fromthe data structure, it is physically still present,but correct use of the structure cannot access it.If enough items are enqueued (and possibly dequeued) fromthe queue, the points will eventually run off the end of thearray! This leads to implementations that "wrap" thebeginning of the array to the end, and forms a CIRCULAR QUEUE.The implementation of the circular queue is a bit more complex. The conditions to test for an empty queue and full queue are more difficult. They can be eased by implementing a queue with one element that is a DUMMY. It is never used for data storage. This is an example of the space vs. time trade-off. An extra piece of memory is used in an inefficient manner, in order to make the test for full/empty queues more efficient.</pre>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -