Homework 4:
Sub-Group 1: Natalie Alleman, Brock Boyd, and Pattie G. Dickerson
QUESTION:
Homework
#4 - Individual or Group -
Due Date: March 3rd
Points: 50
For
each of the following data structures based on the class readings (both text
and notes), determine the attributes and operations necessary from a
programming language specification approach for each of the following
application areas. Then assess feasibility of including each of those
data structures based on the implementation issues for storage
representation and storage management.
Arrays
Multidimensional arrays
Slices (substructure of an array)
Records
Lists
Character strings
Pointers
Sets
Files (pick one type of file)
Variant records
1.Real-time system for controlling life-support
systems.
2.Event driven system for data
mining.
ANSWER:
Attributes
| Single data type. |
| Set number of data (indexed) defined by
programmer. |
| Individual elements are accessed relative to the
position from the first element. |
| Linear data structure. |
Operations
| Random or sequential access of datum through
index. |
| Operations on the array are treated as a unit. |
| Data can be accessed in the array, but new
elements cannot be inserted at runtime. |
| The creation of the array occurs at compile
time. |
| Destruction of the array occurs at termination
of program. |
Storage
| Allocation of memory is linearly sequential. |
| Storage is statically or dynamically bound to
memory. |
| Management addressed
as a whole unit |
Attributes
| Homogeneous data type |
| Fixed number of components, defined by user |
| Subscripts (index) reference individual
components |
| User defines of components |
| Multi-dimensional organization of components
(Elements can be stored in row major order or column major order) |
Operations
| Random access of data through subscripts (index)
|
| Whole data structure operations, treated as a
unit |
| Insertion/deletion of data is not supported |
| Creation is done at compile time |
| Destruction is done at program termination |
Storage
| Storage of components must be mapped into single
dimensional memory (column major order or row major order) |
| Statically or dynamically bound to memory |
| Management addressed
as a whole unit |
Attributes
| Homogeneous data type |
| Fixed number of components |
| Subscripts (index) reference individual
components |
| Programmer defines number of data |
| Linear organization |
| Mechanism for referencing part of an existing
array as a unit |
Operations
| Random access of data through sub-scripts
(index) |
| Whole data structure operations, treat as a unit
|
| Insertion/deletion of datum is not supported |
| Creation is done at compile time |
| Destruction is done at program termination |
Storage
| Storage of data is sequential in memory |
| Statically or dynamically bound to memory |
| Managed as a whole
unit |
Attributes
| Possibly heterogeneous component type aggregate
data type |
| Number of data types is fixed |
| Fixed number of fields |
| Number of datum is directly proportional to
amount of memory available |
| Datum names defined by programmer |
| Linear organization |
| Sometimes allowed to include unions |
Operations
| Fields are not processed in sequential order |
| Whole data structure operations, treated as a
unit |
| Insertion/deletion of data is not supported |
| Creation is done at compile time |
| Destruction is done at program termination |
Storage
| Storage of fields is sequential in memory |
| Fields vary in size |
| Access to each field relative to the beginning
of each record |
| Uses compile time
descriptor |
Attributes
| Data objects of the same type are stored in
linked memory locations |
| All data types are supported |
| Variable number of data |
| Linear organization for data |
| Number of datum is directly proportional to
amount of memory available |
| Data types use ordering for datum naming |
Operations
| Selecting datum is sequential |
| Datum can't be accessed randomly |
| Dynamic list allow insertion and deletion of
data |
| Static list do not allow for insertion and
deletion of data |
| Whole data structure |
| Dynamic lists are created and destroyed during
run time |
Storage
| Sequential storage for static list |
| Random storage for dynamic list |
| Storage management on a static list is the same
as an array |
| Special attention to dynamic lists is needed to
handle dangling pointers and mishandled memory |
| Memory binding occurs during run time and is
generally dynamic |
| When a list id
destructed, reclaiming of allocated memory varies between static and
dynamic lists |
Attributes
| A pointer type is one in which the variables
have a range of values that consist of memory addresses and a special null value |
| Pointers are not structured types |
| Pointers are used to reference some other
variable and are not used to store data |
| Pointers provide the ability to perform dynamic
storage access and management and provide the use of indirect addressing |
| The value of a pointer is the address of a data
object used in the program |
Operations
| Pointers can be organized into arrays or linked
links. |
| There are two fundamental pointer operations:
Reference and dereferencing |
| When a dereferencing operator is called, it
accesses the actual value of the object |
| Reference operator sets a pointer to the
address of an object and stores the address of the object |
| If pointers are used for indirect addressing to
variable that is not dynamically allocated, then there must be an explicit operator or built-in subprogram for fetching the address of a variable, which can then be assigned to the pointer variable |
| If pointer variables are used only to manage
dynamic storage, the allocation mechanism, whether by operator or built-in subprogram, serves to initialize the pointer variable |
Storage
| In general, larger computers use single values
to store pointers in either two byte or four byte memory cells, depending on the size of the address space of the machine |
| In microcomputers, pointers are implemented as
pairs of 16 bit words |
| Pointers are single values stored in 2 or 4 byte
memory cells in larger computers. |
| One of the problems
of using pointers is the dangling pointer, which is a pointer that holds the address of a storage that has been deallocated |
Attributes
| The number of components is usually variable. |
| The types of components within a set are homogeneous. |
| Components are referred to by names, which are instinctive
descriptions of the set |
| The maximum number of components is determined by the
implementation of the set – many implementations restrict the number of components. |
| Components organized in a linear fashion. |
Operations
| Components may have operations performed on them
randomly or sequentially. |
| An entire set may be copied, or individual components may have
operations performed on them, depending on the implementation used. |
| Insertions and deletions are possible during runtime. |
| Creation and destruction of sets is done most often before runtime. |
| Whole-data-structure operation includes union, comparison and equality |
Storage
| Usually stored as bit
strings in memory |
| In languages that do not support sets, arrays
are used to store set elements |
Attributes
|
Data types can be integer values, character strings, etc.,
and can be of fixed size |
|
An output file is oftentimes variably sized, this occurs
during runtime |
|
Data types area often heterogeneous and homogeneous
depending on the |
|
The organization of data is linear |
|
The maximum number of data is limited by the space available
and is defined by computer system |
|
Components in a data file are stored linearly and can be
read only in order of occurrence |
Operations
|
Sequential selection/search is mandatory in an input file |
|
The data file may be copied; individual components may be
read, or compared with other individual |
|
Creation of a data file, if it is an output file, can occur
either as a result of the or by the program |
|
An input file can be created by a program, or by the user
|
Attributes
|
Variably
sized. |
|
Heterogeneous data |
|
Data names are used to refer to individual records. |
|
Maximum amount of data is based on available memory
resources |
|
Organization
of data is linear |
Operations
|
Data may be randomly selected |
|
Individual data items may have operations performed on the |
|
Insertion and deletion of data may occur during runtime. |
|
Creating and destroying variant records occurs during
runtime. |
Storage
|
Memory allocation is sequential with the variant record
stored in one contiguous block. |
|
Records
are implemented using a compile time descriptor |
Arrays:
o
Not feasible
Reason:
1. Allocation/deallocation of data is
unavailable
2. Random access to data is not
supported
3. Whole blocks of data must be moved
in order to sort data
Multidimensional
arrays:
o
Not feasible
Reason:
1. Same as above, although a multidimensional
array would allow for grouping of similar data
2.
Insertion and deletion
of multidimensional array elements is tedious, since in a fixed-size array,
no
insertion or deletion may take place during runtime
3.
Even if the array is
dynamic, once it is created, no inserting or deleting of elements may occur
4. Creating new elements, whether in fixed-size or
dynamic arrays, is still not a possibility since the size array is
determined
when the array is created
5. Once the array is created, elements may be changed,
as in copying, or initialized,
but no creating or destruction can take place
Slices:
o
Not feasible
Reason:
1. Insertion/deletion of data is
unavailable
2. Whole blocks of data must be moved
in order to sort data
3.
The size of the slice
is determined once – either before runtime (fixed-size) or during, but cannot
be changed
once it is determined
4.
Elements can be overwritten or
amended, but individual components cannot be destroyed or created,
since the
slice, whether dynamically allocated or fixed, has its size determined once
Records:
o
Not feasible
Reason:
1.
Insertion and deletion
during runtime not possible – the records are created once and may not be
changed unless they are recreated
2. Creation and destruction does not occur during runtime.
Components are created at the same time, but initialized and/or changed
separately
Lists:
o
Feasible for payroll systems
Reason:
1. Lists,
used along with records and pointers, would be efficient because sequential
searching is supported
2. The
sorting of data records is available with the use of pointers
3. Records
can be inserted and deleted easily
Pointers:
o
Feasible for payroll systems
Reason:
(see above)
1. The
sorting of data records is available with pointers
2. Pointers
can be used to retrieve data from the object being pointed to by dereferencing
that object.
3.
Individual pointers can
be referenced either randomly, as in an array, or sequentially, as in a list of
some sort
4. An entire array of pointers may have an operation
performed on itself as a whole, whereas a list of pointers, or a similar
organization, cannot have an operation performed on itself in entirety.
5. New pointers may be inserted depending on their
organization – in an array, this is not usually possible, whereas in a list, it
would be possible to add or subtract individual pointers
Sets:
o
Not feasible
Reason:
1. Fixed number of components
2.
Homogeneous component
type
3.
Uses programmer defined
names for component naming
4.
The maximum number of
components is determined by what the programmer specifies
5. Linear organization of components
6. Insertion or deletion of components is not allowed
Files
(data):
o
Feasible for payroll systems
Reason:
1.
Sequential selection is
mandatory in an input file – it may be searched for an individual element, but
the search, or any other function on the file, must start its traversal at the
beginning of the file
2. The data file, as a whole, may be copied; individual
components, as well, may be read in, or compared, etc., with other components,
whether in the same file, or from another source
3. Insertion and deletion of components is usually done
by filestream statements, where outstream commands can write to a file. Also
using outstream statements, or the equivalent, the user may overwrite the data
file with a new one
4. Creation of a data file, if it is an output file, can occur either because of a user-originated operation (i.e., a text editor), or by commands in the program. An input file can be created by a program, or again, by the user with a text editor.
5.
Components in a data
file can be integer values, character strings, etc., and can be of fixed size,
such as in an input data file – an output file’s components are often variably
sized during runtime
6.
Component types are
often heterogeneous, but can be homogeneous, depending on the needs of the
program referring to the file
7.
Individual components
can be referenced in a number of ways, depending primarily on how the program
needs them. A component may be an integer value, wherein the program may call
it with an infile statement (as in C++) copying it to a pre-defined integer
variable.
Variant
records:
o
Feasible for payroll systems
Reason:
1.
Can be variably-sized
2.
Use of heterogeneous
components is allowed
3.
Names of components are
used to refer to individual records
4. Individual components may have operations performed
on them
5. Components may be selected at random
6. Inserting and deleting elements may occur during
runtime
7. Creating and destroying variant records occurs also
during runtime