Granville Barnett

Pingback from  Dew Drop - December 22, 2008 | Alvin Ashcraft's Morning Dew

Chapter 5: Sets; Intersection

While traversing the smallerset, there is no need to check if the smallerset contains the item.  That is already known, or it would not have been found during the traversal.  Syntax adjusted to use what this form allows.

1) algorithm Intersection(set1, set2)

2) Pre: set1, and set2 not 1 emptySet

3) intersection, smallerSet and largerSet are sets

3) Post: An intersection of set1, and set2 has been created

4) if set1.Count < set2.Count

5) smallerSet is set1

6) largerSet is set2

7) else

8) smallerSet is set2

9) largerSet is set1

10) end if

11) foreach item in smallerSet

12) if largerSet.Contains(item)

13) intersection.Add(item)

14) end if

15) end foreach

16) return intersection

17) end Intersection

Alternative,

1) algorithm Intersection(set1, set2)

2) Pre: set1, and set2 not 1 emptySet

3) intersection is a set

3) Post: An intersection of set1, and set2 has been created

4) if set1.Count < set2.Count

5) foreach item in set1

6) if set2.Contains(item)

7) intersection.Add(item)

8) end if

9) end foreach

10) else

11) foreach item in set2

12) if set1.Contains(item)

13) intersection.Add(item)

14) end if

15) end foreach

16) end if

17) return intersection

18) end Intersection

I had a peek through Jon Skeet’s blog this morning at a free eBook called Data Structures and Algorithms by Granville Barnett and Luca Del Tongo. The book is clear and presents the usual linked lists, trees, sets structures in a concise yet precise

Hi,

Where can you download the source code for the book?

Thanks