第六章集合与字典 集合及其表示 并查集与等价类 字典 散列
第六章 集合与字典 • 集合及其表示 • 并查集与等价类 • 字典 • 散列 1
集合及其表示 集合基本概念 集合是成员(元素)的一个群集。集合中的成 员可以是原子单元素),也可以是集合 集合的成员必须互不相同。 在算法与数据结构中所遇到的集合,其单元 素通常是整数、字符、字符串或指针,且同 集合中所有成员具有相同的数据类型。 19: colour= red, orange, yellow, green, black, blue, purple, white j
集合及其表示 • 集合是成员(元素)的一个群集。集合中的成 员可以是原子(单元素)，也可以是集合。 • 集合的成员必须互不相同。 • 在算法与数据结构中所遇到的集合，其单元 素通常是整数、字符、字符串或指针，且同 一集合中所有成员具有相同的数据类型。 • 例：colour = { red, orange, yellow, green, black, blue, purple, white } 2 集合基本概念
集合中的成员一般是无序的,但在表示 它时,常写在一个序列里。 常设定集合中的单元素具有线性有序关 系,此关系可记作“<”,表示“优先 于 整数、字符和字符串都有一个自然线性 顺序。指针也可依据其在序列中安排的 位置给予一个线性顺序
• 集合中的成员一般是无序的，但在表示 它时，常写在一个序列里。 • 常设定集合中的单元素具有线性有序关 系，此关系可记作“<”，表示“优先 于”。 • 整数、字符和字符串都有一个自然线性 顺序。指针也可依据其在序列中安排的 位置给予一个线性顺序。 3
A B A B A B AUB或A+BA∩B或A×B A-B 集合(Set)的抽象教据类型 template lass set public virtual Set(=0 构造函数 virtual makeEmpty=0;∥置空集合 virtual bool addMember (const tx)=0;
集合（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 Set intersect With (set&r)=0; /(集合的交运算 virtual Set union With(Set<>&r)=0; 集合的并运算 virtual Set difference from (Set&r)=o ′集合的差运算 virtual bool Contains(Tx)=0; virtual bool subSet(Set&r)=0; virtual bool operator==(Set&r)=0; 判集合是否相等
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是不大的整数时,可用位(,1)向量来实 现集合。 当全集合是由有限个可枚举的成员组成时,可 建立全集合成员与整数0,1,2,的一一对应 关系,用位向量来表示该集合的子集。 一个二进位有两个取值0,分别表示在集合 与不在集合。如果采用16位无符号短整数数组 bit vector作为集合的存储,就要考虑如何求 出元素i在 bit vector数组中的相应位置
用位向量实现集合抽象数据类型 • 当集合是全集合 { 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 i 用位向量來存储集合元素.集合元素的范围在0到 setSize-1之间。数组采用16位无符号短整数实现 public bitSet(int Sz= DefaultSize) 构造函数 bitset( const bitset&R);∥复制构造函数 bitset0{ delete[ Bit vector;}∥析构函数 unsigned short getmember( const tx);∥读取集合 元素ⅹ
集合的位向量(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送入集合元素ⅹ void make Empty ( i /置空集合 for (int 1=0; 1& operator=(const bitSet& ri; bitset& operator +(const bitSet& r bitset>& operator *(const bitSet&R) bitset& operator-(const bitset& r) bool Contains(const Tx); /x是否集合this的成员8
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( bitsets&R);/判this是否R的子集 bool operator=(bitSet& r) /判集合this与R相等 friend istream& operator >>(istream& in, bitset& r) /入 friend ostream& operator &r) 出 private: int setsize /集合大小 int vector Size. ∥1位数组大小 unsigned short *bit vector /存储集合元素的位数组
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
使用示例 bitSetsl, S2, S3, S4, s5; bool index, equal for(intk=0;k<10;k++){/集合赋值 Sl. addMember(k) S2. addMember(k+7) s:④0,1,2,…,9},s2:{7,8,9,…,16} s3=sl+s2;/求s1与S2的并{0,1,…,16 s4=sls2;1求S1与S2的交{7,8,9} s5=s1-s2;/s1与S2的差{0,1,…,6}
使用示例 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