Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Lec-23,24 Sets - Copy

    Uploaded by

    akyadav123

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Lec-23,24 Sets - Copy

    Uploaded by

    akyadav123
    2 views8 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    2 views8 pages

    Lec-23,24 Sets - Copy

    Uploaded by

    akyadav123

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 8

    Linked-List Implementation of Sets

     The Items of the linked-list are the


    members of the set.

     Linked-list uses space proportional to the


    size of the set represented, not the
    universal set.

     Linked-List can represent the sets where


    the universal set is infinite.
    Intersection in Unsorted List
     An element is in the intersection of lists L1
    and L2 if and only if it is on both lists.

     In unsorted lists, we must match each


    element of L1 with each element on L2.

     The process will take O(n2) steps on lists


    of length n.
    Intersection in Sorted List
    To Match an element e on one list L1 with
    the elements of another list L2, look down
    L2 until;

     Either find e, that is the match has been


    found.
     Or, find an element greater than e, which
    indicates the match does not exist.
    Intersection in Sorted List

     If d is the element on L1 that immediately precedes


    e.

     And the first element found on L2 is f, such that d


    <= f, then to search L2 for an occurrence of e we
    can begin with f.
     Thus, we can find matches for all the elements of
    L1, if they exist, by scanning L1 and L2 once.
    Assign in Sorted List
     A=B
     Copy all elements in B to A.

     Cannot be implemented by pointing the


    header cell of A to the header cell of B.

     Subsequent, changes in B will result in


    unexpected changes in A.
    Union in Sorted List
     C=AB
     Attach all the elements from either A or B list to the C
    list, in their proper, sorted order.
     Compare the elements of A with B.
     If the elements are equal add once to C.
     If the elements are unequal, add the elements from
    the smaller element’s list until a larger element is
    found.
     If one list exhausts, append the elements of the other
    list as it is.
    Difference in Sorted List
     C=A–B

     Do not add an element to the C list when equal


    elements are found.

     Add the current A list element to the C list when it is


    smaller than the current B list element; since the
    former cannot be found on the B list.
     If B exhausts then append all the remaining
    elements of A.
    Other Operations
     MIN: Return the first element on the list.

     FIND: Search through the list and return when the


    target element is found.
     DELETE: Same as FIND but dispose of the target
    element.
     INSERTION: Find out the position of the element to
    be inserted in order, and then change the pointers
    appropriately.

    You might also like