CIS 400 LECTURE 16

 

Variable sized elements: (heap elements)

·        Re-use without compacting

v     First-fit, (first block in heap storage that fits), makes large pieces smaller

v     Best fit, (traverse entire list to find closest fit)

·        Compaction

v     Partial compaction: (active storage can't be shifted)

v     Full compaction: (all storage shifted, similar to de-fragmentation)

 

 

 

Structured data types: issues

·        Type specification

·        Type incrementation

·        Declaration

·        Type checking

 

QUESTIONS TO CONSIDER:

·        How do you indicate component relationships in such a way that selection is easy?

·        Storage management issues

 

Specification issues:

·        Number of components, (fixed or variable), array vs. linked-list

·        Types of each component, (homogeneous or heterogeneous), array vs. structure

·        Name used for select, (sub-script or fieldname), A[I] or x.name

·        Maximum number of components

·        Organization of components, (linear organization-array or linked-lists, trees, etc.)

 

Operations:

·        Component selection, (random or sequential)

·        Whole data structure operations, (array multiplication, etc.)

·        Insertion and deletion components

·        Creation and destruction of entire data structure

 

Hardware support:

Base address offset, (for pointer), all else, (array, structure, etc.) is software implemented

 

Type checking

·        Existence of selected component

·        Type of selected component

 

A[i][j].link®item            //what type is this?

 

Vectors: (one dimensional arrays)

Attributes:

·        Number of components

·        Component types

·        Computed sub-script

 

Operations:

·        Selection

·        Creation and destruction, (only upon block entry and exit)

·        MAYBE some vector arithmetic

 

Implementation, (homogeneous)

 

Base address a ®

                                      

                                  

 

Location: A[i] = a + D + (i - lb) * E, where the quantity (i - lb) cannot precede lb or exceed ub

 

Multiple dimension array:

·        Row major, (1st row, 2nd row, etc.)

·        Column major, (FORTRAN IV…just TRY passing a FORTRAN IV array to C!!)

 

Location: A[i][j] = a + D + (i - lb1) * S + (j - lb2) * E

Where S = "width" * E

 

Base address a ®

                              

 

 

Records, (structs)

Aka Cartesian product

 

Specification:

·        Heterogeneous components

·        Symbolic names for components

 

Attributes:

·        Number of fields

·        Data type of components

·        Literal-compile time subscript

 

Operations:

·        Record assignment

·        Component selection

 

® x = y;  will this be by structural equivalence or by name

 

® move corresponding data for parts that match, regardless of order of  fields. This is dangerous because of …

 

®linear sequential storage

 

 

start location known at run time only

to use "move corresponding", locations must be kept track of at all time during execution

 

variant record:

   Union types

 

 

Using the "tag":

 

if x.tag = 2 then

   w.weight

 

Character strings, (sequence)

·        Fixed length, (length known at compile time)

·        Variable length, (length also known at compile time)

·        Unbounded length

 

Operations

·        Concatenation

·        relational operations, usually lexigraphical order

·        sub-script selection

·        I/O formatting

·        Sub-string selection vi pattern matching

Fixed length string = 1 dimensional array of characters

 

 

 

 

Variable length

 

 

Unbounded, (linked lists)