第六章集合与字典 ·集合及其表示 ·并查集与等价类 字典 ·散列
第六章 集合与字典 • 集合及其表示 • 并查集与等价类 • 字典 • 散列 1
集合及其表示 集合基本概念 集合是成员（元素）的一个群集。集合中的成 员可以是原子（单元素），也可以是集合。 集合的成员必须互不相同。 在算法与数据结构中所遇到的集合，其单元 素通常是整数、字符、字符串或指针，且同 一集合中所有成员具有相同的数据类型。 . 例：colour={red,orange,yellow,green,, black,blue,purple,white 2
集合及其表示 • 集合是成员(元素)的一个群集。集合中的成 员可以是原子(单元素)，也可以是集合。 • 集合的成员必须互不相同。 • 在算法与数据结构中所遇到的集合，其单元 素通常是整数、字符、字符串或指针，且同 一集合中所有成员具有相同的数据类型。 • 例：colour = { red, orange, yellow, green, black, blue, purple, white } 2 集合基本概念
.集合中的成员一般是无序的，但在表示 它时，常写在一个序列里。 常设定集合中的单元素具有线性有序关 系，此关系可记作“<”，表示“优先 于” 整数、字符和字符串都有一个自然线性 顺序。指针也可依据其在序列中安排的 位置给予一个线性顺序。 3
• 集合中的成员一般是无序的，但在表示 它时，常写在一个序列里。 • 常设定集合中的单元素具有线性有序关 系，此关系可记作“<”，表示“优先 于”。 • 整数、字符和字符串都有一个自然线性 顺序。指针也可依据其在序列中安排的 位置给予一个线性顺序。 3
AUB或A+BA⌒B或AXB A-B 集合(Set)的抽象数据类型 template class Set public: virtual Set(=0; /构造函数 virtual makeEmpty()=0; 川置空集合 virtual bool addMember (const Tx)=0; 4
集合（Set）的抽象数据类型 template class Set { public: virtual Set() = 0; //构造函数 virtual makeEmpty() = 0; //置空集合 virtual bool addMember (const T x) = 0; 4 AB 或 A+B AB 或 AB A-B A B A B A B
virtual bool delMember (const Tx)=0; virtual SetintersectWith(Set&R)=0; 川集合的交运算 yirtual SetunionWith(Set&R)=0; 川集合的并运算 virtual SetdifferenceFrom (Set&R)=0; 川集合的差运算 yirtual bool Contains(Tx)=0; virtual bool subSet (Set&R)=0; virtual bool operator ==(Set&R)=0; /判集合是否相等 }; 5
virtual bool delMember (const T x) = 0; virtual Set intersectWith (Set& R) = 0; //集合的交运算 virtual Set unionWith (Set& R) = 0; //集合的并运算 virtual Set differenceFrom (Set& R) = 0; //集合的差运算 virtual bool Contains (T x) = 0; virtual bool subSet (Set& R) = 0; virtual bool operator == (Set& R) = 0; //判集合是否相等 }; 5
用位向量实现集合抽象数据类型 当集合是全集合{0,1,2，，n}的一个子集 且n是不大的整数时，可用位(0,1)向量来实 现集合。 当全集合是由有限个可枚举的成员组成时，可 建立全集合成员与整数0,1,2，..的一一对应 关系，用位向量来表示该集合的子集。 一个二进位有两个取值1或0，分别表示在集合 与不在集合。如果采用16位无符号短整数数组 bit Vector[作为集合的存储，就要考虑如何求 出元素i在bit Vector数组中的相应位置。 6
用位向量实现集合抽象数据类型 • 当集合是全集合 { 0, 1, 2, …, n } 的一个子集， 且 n 是不大的整数时，可用位(0, 1)向量来实 现集合。 • 当全集合是由有限个可枚举的成员组成时，可 建立全集合成员与整数 0, 1, 2, …的一一对应 关系，用位向量来表示该集合的子集。 • 一个二进位有两个取值1或0，分别表示在集合 与不在集合。如果采用16位无符号短整数数组 bitVector[ ]作为集合的存储，就要考虑如何求 出元素 i 在bitVector数组中的相应位置。 6
集合的位向量(bit Vector)类的定义 #include #include const int DefaultSize 50; template class bitSet 川用位向量来存储集合元素，集合元素的范围在0到 /setSize-1之间。数组采用16位无符号短整数实现 public: bitSet (int sz DefaultSize); /构造函数 bitSet (const bitSet&R); /复制构造函数 bitSet ()delete ]bit Vector; /析构丞数 unsigned short getMember(const Tx);/读取集合 元素X 7
集合的位向量(bit Vector)类的定义 #include #include const int DefaultSize = 50; template class bitSet { //用位向量来存储集合元素, 集合元素的范围在0到 //setSize-1之间。数组采用16位无符号短整数实现 public: bitSet (int sz = DefaultSize); //构造函数 bitSet (const bitSet& R); //复制构造函数 ～bitSet () { delete [ ]bitVector; } //析构函数 unsigned short getMember (const T x); //读取集合 元素x 7
void putMember (const Tx,unsigned short v);/ 将值V送入集合元素X void makeEmpty () 川置空集合 for (int i=0;i&operator =(const bitSet&R); bitSet&operator +(const bitSet&R); bitSet&operator (const bitSet&R); bitSet&operator -(const bitSet&R); bool Contains (const Tx); /判x是否集合this的成员
void putMember (const T x, unsigned short v); // 将值v送入集合元素x void makeEmpty () { //置空集合 for (int i = 0; i & operator = (const bitSet& R); bitSet& operator + (const bitSet& R); bitSet& operator * (const bitSet& R); bitSet& operator - (const bitSet& R); bool Contains (const T x); //判x是否集合this的成员 8
bool subSet(bitSet&R);/判this是否R的子集 bool operator ==(bitSet&R); /判集合this与R相等 friend istream&operator >>(istream&in, bitSet&R); 川输入 friend ostream&operator &R); /输出 private: int setSize; /集合大小N int vectorSize; /位数组大小 unsigned short *bit Vector; /存储集合元素的位数组 9
bool subSet (bitSet& R); //判this是否R的子集 bool operator == (bitSet& R); //判集合this与R相等 friend istream& operator >> (istream& in, bitSet& R); //输入 friend ostream& operator & R); //输出 private: int setSize; //集合大小 int vectorSize; //位数组大小 unsigned short *bitVector; //存储集合元素的位数组 }; 9
使用示例 bitSets1,s2,s3,s4,s5;bool index,equal; for (int k=0;k<10;k++ /集合赋值 s1.addMember (k); s2.addMember(k+7); /s1:{0,1,2,,9}, s2:{7,8,9,,16} s3=S1+s2; 1/求s1与s2的并{0,1，，16} s4=S1*s2; 1/求s1与s2的交{7,8,9} s5=s1-s2; /求s1与s2的差{0,1，，6 10
使用示例 bitSet s1, s2, s3, s4, s5; bool index, equal; for (int k = 0; k < 10; k++) { //集合赋值 s1.addMember (k); s2.addMember(k+7); } //s1: {0, 1, 2, …, 9}, s2: {7, 8, 9, …, 16} s3 = s1+s2; //求s1与s2的并 {0, 1, …, 16} s4 = s1*s2; //求s1与s2的交 {7, 8, 9} s5 = s1-s2; //求s1与s2的差 {0, 1, …, 6} 10