Please enable JavaScript.

Coggle requires JavaScript to display documents.

Data types - Coggle Diagram

- - - - set of values and a set of operations
      - In Data types
        
        data is sorted into sets
        
        operations are modelled by functions
        
        tests are modelled on relations or functions on the sets
      - mathematical model (algebra of data types)
      - Differences among languages
        
        types allowed
        
        operations allowed
        
        control sequences
        
        data structures
      - History
        
        abstraction
        
        process abstraction
        
        data abstraction
    - - Built in primitive data types
      - users can define new data types and operators
    - - Who provide the data
        
        Provided by hardware
        
        integer
        
        provided by language
        
        standard libraries
        
        constructed by programmer
        
        functions and libraries
        
        line code sequence
      - how they are manipulated in a program
        
        Elementary data objects
        
        Integer: Short, int, long
        
        Data Structures
        
        Built out of other types
    - - Aggregation of data object
      - require variable memory space
  - - - Boolean (Logical)
        
        true or false
        
        used for control programming structurs (choices)
        
        simplest data type
        
        Introduced in ALGOL 60
        
        Increases readability
        
        common operations
        
        and
        
        or
        
        not
        
        stored as a byte
      - Character
        
        single character as its value
        
        stored as numeric codes
        
        most commonly used codinf
        
        8-bit ASCII (128 chars)
        
        ISO 8859-1 (256 chars)
        
        Unicode
        
        16 bit character set
        
        first 128 chars are identical to ASCII
        
        commonly used in Java, JS, Python, Perl, C#
        
        character set
        
        aggregate characters
        
        code point
        
        numerical value that the char is mapped to
        
        code page
        
        collection of code points
        
        collating sequence
        
        order of the character set
      - Numerical
        
        Integers
        
        Representation
        
        Real World
        
        Why not take all numeric data as floating point numbers
        
        Computer
        
        Supported by hardware
        
        Not surpported by hardware
        
        Differences between integer data types in different languages
        
        size variation in different machines
        
        size varitaion among languages
        
        May/May not allow negative integers
        
        Storage representation
        
        Unsigned
        
        Signed
        
        Sign magnitude
        
        One's complement
        
        Two's complement
        
        Operations on integer data
        
        Arithmetic operations
        
        Binary operations
        
        Unary operations
        
        Relation Operations
        
        Assignment
        
        Bit operations
        
        Floating point
        
        Representation
        
        Real world
        
        real numbers
        
        Computer world
        
        mantissa and exponents
        
        IEE Floating-Point Standard 754 format
        
        Domain
        
        Precision
        
        accuracy of the fractional part of a value
        
        Range
        
        combination of the range of fractions
        
        Types
        
        float
        
        usually stored in 4 bytes of memory
        
        double
        
        usually stored in 8 bytes of memory
        
        Storage representation
        
        Floating point representation
        
        IEEE Floating-point standard 754 format
        
        Single precision (32 bits)
        
        double precision (64 bits)
        
        Issues
        
        only approximations for many real values
        
        stored in binary
        
        loss of accuracy
        
        Operations
        
        Arithmetic operations
        
        Binary operations
        
        Unary operations
        
        Relation Operations
        
        Assignment
        
        Bit operations
        
        trigonometric operations
        
        Fixed point (Decimal type)
        
        Storage representation
        
        Character strings
        
        Binary coded decimal (BCD)
        
        Integers
        
        Decimal point
        
        Advantages
        
        precisely to store decimal values
        
        Disadvantages
        
        range of values are restricted
        
        takes a wasteful amount of space
        
        Complex
        
        Descriptors
        
        collection of the attributes of a variable
        
        static
        
        required at compile time
        
        dynamic attribute
        
        required at run-time
        
        Symbol table
    - - Design choices
        
        static length string
        
        only required during compile time
        
        limited dynamic length strings
        
        run-time descriptor
        
        dynamic length strings
        
        simpler run-time descriptor
      - Implementation
        
        static length string
        
        name of the type
        
        type's length
        
        address of the first character
        
        limited dynamic length strings
        
        name of the type
        
        fixed maximum length
        
        current length
        
        Address
        
        dynamic length strings
        
        name of the type
        
        current length
        
        linked list
        
        (-)Extra storage occupied by the links
        
        (-)complexity of string operations due to pointer chasing
        
        (+)allocation and deallocation is simple
        
        arrays if pointers to individual characters
        
        (-)uses extra memory
        
        (+)faster than linked-list approach
        
        Complete strings in adjacent storage cells
        
        (+)Less storage
        
        (+)Faster string operations
        
        Address
      - Operations
        
        Assignment
        
        Comparison
        
        Concatenation
        
        Substring selection
        
        Pattern matching
      - Evaluation
        
        strcat
        
        strcmp
        
        strlen
        
        strcpy
        
        Regular Expressions
        
        basic elements
        
        position indicators
        
        Character sets
        
        Quantifiers
        
        Anchors
        
        ^ - start of the string
        
        $ - end of the
        
        \Z - End of string
        
        \b - Word boundary
        
        \B - Not word boundary
        
        \< - Start of word
        
        > - End of word
        
        Character sets
        
        Character classes
        
        [xy] - x or y
        
        [a-z] - a or b or ……z
        
        [1-9a-zA-Z] - a or b or ……z or A or B or ……Z or 1 or 2 or ……9
        
        [^1-9] - Any character other than a digit (negation)
        
        . - Any character.
        
        Character class abbreviations
        
        \d - Match any character in the range 0 – 9
        
        \D - Match any character NOT in the range 0 - 9
        
        \s - Match any whitespace characters (space, tab etc.)
        
        \S - Match any character NOT whitespace (space, tab)
        
        \w - Match any character in the range 0 - 9, A - Z and a – z
        
        \W - Match any character NOT the range 0 - 9, A - Z and a - z
        
        Recursive definitiion
        
        a | b choice
        
        ab sequence
        
        (a) grouping
        
        a* zero or more repetitions
        
        a+ One or more repetitions
        
        Quantifiers
        
        - 0 or more
        
        - 1 or more
        
        ? - 0 or 1
        
        {3} - Exactly 3
        
        {3,} - 3 or more
        
        {3,5} - 3,4,or 5
    - - Enumeration
        
        Design Issues
        
        Is a literal constant allowed to appear in more than one type definition.
        
        Are enumeration values coerced to integer
        
        Basic operations
        
        Relational operations
        
        Assignment
        
        Operations such as successor and predecessor
        
        Advantages
        
        Readability
        
        Reliability
      - Subrange
        
        Types
        
        Contiguous subsequence
        
        Define new names
        
        All the operations defined for the parent
      - Implementation
        
        associating a non-negative integer value with each symbolic constant in the type
    - - Forms
        
        One-dimensional arrays - Vector
        
        Array
        
        Element type
        
        Index type
        
        index lower bound
        
        index upper bound
        
        Address
        
        Two-dimensional arrays - Matrix
        
        row major order
        
        column major order
        
        Multi-dimensional arrays
        
        Multidimensional array
        
        Element type
        
        Index type
        
        No. of dimensions
        
        Index range 0
        
        ....
        
        Index range n-1
        
        Address
        
        Rectangular and Jagged arrays
      - Design issues
        
        When does array allocation take place
        
        Can arrays be initialized when they have their storage allocated
        
        What types are legal for subscripts
        
        Often a subrange of integers
        
        What is the lower bound of the subscript range and is it implicit
        
        Number of array subscripts (one, two, three,..)
        
        Are subscripting expressions in element references range checked
      - Types
        
        Static
        
        (+)Efficiency
        
        (-)Size must be known at compile time
        
        The subscript type (integers)
        
        bound at the language design time
        
        The subscript ranges
        
        statically bound
        
        Storage
        
        statically allocated
        
        Fixed Stack
        
        (+) Space efficiency
        
        (-) Size must be known at compile time.
        
        (-) The required allocation and deallocation time
        
        Subscript ranges are statically bound
        
        Storage allocation is done at declaration elaboration time during execution
        
        Fixed Heap Dynamic
        
        (+) flexibility
        
        (-) allocation time from the heap, which is longer than allocation time from the stack.
        
        Subscript ranges and the storage binding are both fixed after storage is allocated
        
        Storage bindings are done when the user program requests
        
        Storage is allocated from the heap
        
        Heap dynamic
        
        (+) flexibility
        
        (-) allocation and deallocation may take longer
        
        subscript ranges and storage allocation is dynamic in heap
      - Initialization
        
        at declaration
        
        to string constants
        
        with string literals
      - Operations
        
        assignment
        
        catenation
        
        comparison
        
        slices
    - - Unordered collection of data elements that are indexed by an equal number of values called keys
      - The user- defined keys must be stored in the structure
      - Implemented
        
        hash table
        
        LinkedHashMap
        
        Map interface (Java)
        
        Dictionaries (Python)
    - - Difference between arrays and records
        
        Arrays are used when all the data values have the same type or process.
        
        Records are used when the collection of data values is heterogeneous
        
        Array elements are accessed using Subscripts while Record elements are accessed using Field Names.
      - Design issues
        
        syntactic form of references to fields
        
        Are elliptical references (indirect references) allowed
      - Definition
        
        COBOL
        
        Pascal - recursive definition
        
        C,C++,C# - Linked list (structs)
      - Reference of fields
        
        Elliptical reference
      - Operations
        
        Assignment
        
        Record comparison
        
        Record initialization
      - Implementation
        
        record
        
        Name
        
        Type
        
        offset
        
        ... (Compile-time descriptor for a record)
        
        Name
        
        Type
        
        Offset
        
        Address