数据结构与算法这集讲的内容继续第十章检索的学习。 We continue to take up chapter 10th retrieval to study data structure and algorithms.
今天来学习对集合的检索。 Today we introduce the retrieval of set.
集合，是数学里面一个重要的概念。 Set is an important mathematical concepts.
它是由若干确定的、相异的对象组成了一个整体。 It is a whole formed by several certain and dissimilar objects.
对集合的检索，其实就是确定某一个值是不是某个集合里面的元素。 In fact, the retrieval of set is to certain whether a value is an element of a set.
当然在数学的这个基因里面，集合它是更复杂的这样的一个结构。 In the mathematical gene, set is a more complicated structure.
它可以本身也含有这个子集。但是在计算机里面出现可以不考虑么复杂的情况，可以把这一些集合里面的元素看都是简单的一些数据类型，然后就是他们没有这种子集的这种情况，这样处理起来更方便一些。 It can also contain this subset itself. However, it can be considered less complex when it appears on the computer, you can regard some elements of the set as some simple data types, then consider the case that they have no subset, it is more convenient to handle.
看数学里面，集合的这些运算主要是有两大类，一类就是逻辑运算。 Operations of a set in mathematics are mainly two categories, one is logical operations.
最主要的就是判断某一个元素它属不属于某一个集合。 Which is uppermost is to judge whether an element belongs to a set.
另外就是两个集合它们的包含的关系是什么样的。 The other is the inclusion relation between the two sets.
还有一类运算， 就是算术运算。 Another type of operation is arithmetic.
算术运算就是由判断两个集合是不是相等或者是不等，以及并、交、差等这些运算来看在计算机里面第一集合的抽象数据类型，么除了这些基础的这个构造函数以外，就是可以 对这个集合我设置某一个元素属于它或者是说不属于它，我这个都是通过这个set，这个函数，通过这个X等于true或者是false来进行。 The arithmetic is to judge the two sets are equal or unequal, and to cognize abstract data type of computer’s first set by union, intersection and hardsubtract. In addition to these basic constructed function, we can set an element belong to or not belong to this set, these all perform through this set, this function, and this X equal true or false.
还有个判断某一个元素它是不是属于这个集合。 And to judge whether an element belongs to this set.
另外就是判断集合里面元素个数以及判断这个集合是不是空集。 Another is to judge the number of elements inside of the set and to judge whether the set is empty.
然后还有一些集合的一些相关的运算：有这个等于不等于，还有并、交、差，这些算数运算以及包含、包含于等这样的逻辑运算。 And then there are a number of operations related to set: some arithmetic include being equal or unequal, union, intersection, hardsubtract, and such logical operations like containing and being contained.
在计算机里面用这种位向量的方法来表示集合是非常便捷的。 It is very convenient to represent the set by bit vector on the computer.
首先，就是要对集合的元素来认为的第一个序的关系。 First, the relationship of the first sequence between the elements of the set should to be considered.
其实在数学的概念里面，集合的这一些元素，并不在乎它们之间的序的这个关系。 In fact, in the conception of mathematics, it won’t care about the sequence relationship between the elements of set.
但是为了在计算机存储里面的实现方便，我可以根据比如说这个集合如果它的集类是自然数，我就可以按照他的这个在自然数的第一名里面的大小的这个序的关系。 But in order to realize it conveniently in the computer storage, if the class of this set is natural number, I can follow the sequence relationship of its natural numbers.
或者是说集合元素，如果一些名词就可以根据它的这个字典序来定义序的关系。 If the elements of the set are some nouns, I can define its sequence relationship according to lexicographical.
如果它实在没有序了，我就给它规定硬性的一个序的关系。 If there is no order indeed, I’ll provide a rigid sequence relationship for it.
只要自己能够知道我是一个什么样的规定，然后我能够找到这个序就行。 As long as I’m able to know what kind of regulations are, and I can find the sequence.
然后，我规定一个序以后，就可以相应的在这个位向量里面来给它指定说这一个位就是代表的哪一个集合元素。 Then after I provided a sequence, I can specify that this bit represents which element in this bit vector.
如果这个就是说里面有这个元素，在相应的位就是一如果没有就是零。 If there is this element, the corresponding bit is one; or it is zero.
这种表示方法对于数据方面比较小，以及这里面的有效元素比较多的情况，它是一个非常有效的一个表示方法。 When the data is relatively small, and the effecive elements is relatively much, this representation is very effective.
来看一下怎么来表示这个奇数集合、素数集合，另外再来看一下怎么样对这个位向量的来进行相应的运算。 How to represent this odds set, prime numbers set and how to carry on the corresponding operations of this bit vector?
这个奇数集合，我就可以是在比如说假定是在零到十五的这样的范围之内的这个奇数， 它的相应的这个奇数位就定为一。 The odds set can be assumed to be odds in the range of zero to fifteen, then its corresponding odd bit is set to one.
对于这个素数集合，就是相应的这个素数位置，它的位置就是一。 For the prime numbers set, the position of this corresponding prime number is one.
然后再来看，我有一个运算，就是要计算从零到十五之间所有的这个奇素数，我就把这个奇数集合所代表的这个向量和素数集合所代表的这个向量，把这两个向量进行按位与的一个操作。 Now let’s apply these conclusion. There is a calculation is to calculate all the odd prime number from zero to fifteen. I perform a bitwise AND on the vectors of odds set and of prime numbers set.
得到的这个结果就是奇素数的这么一个集合。 The result is an odd prime numbers set.
再来看在计算机里面的存储实现。 How about the implementation of computer storage?
首先采用的这样的一个数据类型是无符号的整型。 First , the data type what it uses is unsigned integer.
对于一个三十二位集，如果是说我这个全集的元素有四十个的话，需要用两个ulong来表示。 For a thirty-two bits set, if there are forty elements in the whole set, it needs to be represented by two ulong.
在这个从第一位到高位顺序的这个表示的也是集合里面这个序从低到高这么一个排列。 The order from the first bit to higher bit also representes the order of the set is arranged from low to high.
可以看到对这一个集合，相应的这样的一些这个位置就是这个第零位、第一位、第二、第三、第四、第五、第六、第七、第八、第九，可以看到一、三、五、七、九这个位置都是表示为一，这就是这几元素。 You can see a set, whose conrresponding position is the zero position, the first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, while the first, third, fifth, seventh, ninth position is expressed as one, so the result is these elements.
三十五这个元素，它已经是需要在第二个这个ulong里面来表示了，可以知道第二个ulong里面它这一个位是表示三十二，三三、三四、三五，就在这个位置。 As for this element, thirty-five, it is already pushed into the second ulong. The second ulong contains thirty-two, thirty-three, thirty-four, thirty-five, and thirty-five is here.
补够一个ulong的时候是在左边给它补齐的。 When a ulong is not full, it would be make enough on the left.
来看它的一个常数？的表示。 It’s a point of view represents of ?the constant number?.
首先，计算出这样一个ulong它能够表示多少位。 First, it calculates how many bits such a ulong can represent.
在三十二位制里面一个ulong是四个字节，每一个字节是八位，所以是可以表示三十二位这样的，也就是说可以表示三十二个成员member。 In thirty-two bits system, a ulong is four bytes, while each byte is eight bits, so it can represent thirty-two bits, that is it can represent thirty-two members.
然后，这个集合它总的元素个数果是N的话，我就需要计算出我需要几个这个ulong来表示这个集合的元素。 Then if the total number of elements in the set is N, it need to figure out how many ulongs needed to represent the elements of the set.
计算出来了以后，我就能够存齐一个相应的这一个位向量数组。 After calculated, it is able to keep a corresponding array of th vector together.
然后来看我怎么样设置某一个位，它所代表的这个成员，它是个属于这样的一个集合。 And how should we set the member that one bit represents while it belongs to such a set?
也就是说其实就是把某一个元素加入到这个集合里面。 In fact, it’s just adding one element into this set.
当然这个算法其实它同时也可以删除，来看它的算法实现。 Of course this algorithm can delete elements at the same time, now let’s learn about the implementation of its algorithm.
如果我在这个P位要插入这个元素，这时候我给它传的就是这个X这个变量是真。 If it will insert this element at the P bit, which is passed to the algorithm is X, and this variable is true.
首先我是这个P位除以这个NB，这前面算出来是三十二,对于这个三十二为奇的话，我P除以NB，我首先就是找到这个ulong数组里面它第几个这个数组元素。 First, this P bit divide by NB, the result of the calculation is thirty-two. If this result is an odd, we divide P by NB, and we’ll find out which position of the element occupies in this ulong array.
然后，找到这个元素以后，相应的对这个P所代表的这样的一个位置，我给它设为一，其它位置设为零。 After we found the element, I set the position that P represents to one, the others are set to zero.
是首先把这个P，就是对这个NB取模，就是说我得到的是这个数组位里面它是从这个右边，这个最低段开始，它往左边来看是第几位。 Firstly, we mod p，thus NB， and get a bit starting from the right side of the array, the lowest segment, work out which position it represents from left.
然后是对这个一来左移动进行操作，就是它的结果，就是把这个相应的这一位设为一，其它的都设为零。 Then set the first bit on the left, namely its result to one, and others are set to zero.
然后把它跟这个对应的ulong的样一个段， 进行一个按位的或操作，就是把这个P位所对应的这个元素，就加入到了这个数组里面。 Next I perform a bitwise OR on the corresponding segment of ulong and the first bit on the left, by this we can add the element that P bit represents to the array.
如果我这个X传到是假，这个时候前面这个找到具体的这个位是一样的，这边计算出来的一个用于操作的这个位向量，是对它取反。 If the passed X is false, the specific bit we have found is the same. This time, we’ll keep the calculated bit bector’s negation.
也就是说P位的值是零，其它位的都是一。 That means that the value of the P bit is zero, while the others are all one.
跟原来的一个ulong的这样的一个位向量的值量进行一个按位与的操作，其实达到的效果就是把这个向量里面的相应的值设为零了，也就是说如果它原来在这个集合里面，我现在是给它删除了，然后把结果返回。还有一个是集合的交运算。 Performing a bitwise AND on the value of the original bit vector in ulong , the effect is equal to set the value of vector to zero, which means that if it was in this set, now I delete it from the set,and return the results. Another is intersection operation of set.
这个交运算的话是对这个一个ulong的数组，然后从第一位向高位然后对应的这两个集合，进行按位的一个与的运算，然后把结果返回就行了。 The intersection operation is a bitwise AND on two corresponding sets from the first position to higher position on a ulong array, then return the results.
这个非常的简单。 That’s very simple.
最后留两个思考：首先就是考虑一下集合它还可以用些技术来实现。 Finally, I question two problems for you to think. First consider what techniques can be used to realize set.
例如是不是可以用数组、链表还有BST的变种，例如红黑树还有散列的方法等等。 For example, if we can use arrays, linked lists as well as variants of BST, such as red-black tree and hashing methods and so on?
另外，是来分析一下这个STL里面集合的各种实现的版本。 In addition, analyze the variety implementations of set inside of STL.
其实刚才所看到的这一些ADT，还有集合运算的实现都是从STL里面抄出来的。 In fact, these ADT that we’ve just seen, as well as the realization of set operations are copied from STL.
谢谢大家。 Thank you!