数据结构教程第6章集合与字典ppt课件.ppt

《数据结构教程第6章集合与字典ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、集合及其表示并查集与等价类字典跳表散列第六章集合与字典集合基本概念6.1.1集合及其表示集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。集合的成员必须互不相同。在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。colour={red,orange,yellow,green,black,blue,purple,white}name={An,Cao,Liu,Ma,Peng,Wang,zhang}集合中的成员一般是无序的，但在表示它时，常设定集合中的单元素具有线性有序关系，此关系

2、可记作“<”，表示“优先于”；整数、字符和字符串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。某些集合保存的是实际数值，某些集合保存的是表示元素是否在集合中的指示信息。要求每个元素在集合中只出现一次，但多种集合允许元素重复出现。集合(Set)的抽象数据类型templateclassSet{public:virtualSet()=0;virtualMakeEmpty()=0;virtualboolAddMember(constTx)=0;virtualboolDelMember(constTx)=0;AB或A+BAB或ABA

3、-BAAABBBvirtualSetunionWithconstSet&R)=0;virtualSetintersectWith(constSet&R)=0;virtualSetdifferenceFrom(constSet&R)=0;virtualboolContains(constTx)=0;virtualboolsubSet(constSet&R)=0;virtualbooloperator==(constSet&R)=0;}6.1.2用位向量实现集合抽象数据类型当集合是全集合{0,1,2,…,n}的一个子集，且n是

4、不大的整数时，可用位(0,1)向量来实现集合。当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数0,1,2,…的一一对应关系，用位向量来表示该集合的子集。集合的位向量(bitVector)类的定义#includeconstintDefaultSize=50;classbitSet{private:unsignedshort*bitVector;intsetSize,vectorSize;public:bitSet(intsz=DefaultSize);~bitSet(){delete[]bitVector;}voidmakeEmpty

5、(){for(inti=0;i&operator=(constbitSet&R);bitSetoperator+(constbitSet&R);bitSetoperator*(constbitSet&R);bitSetoperator-(constbitSet

6、&R);boolContains(constTx);boolsubSet(bitSet&R);//判this是否R的子集booloperator==(bitSet&R);friendistream&operator>>(istream&in,bitSet&R);friendistream&operator<<(istream&out,bitSet&R);};使用示例bitSets1,s2,s3,s4,s5;intindex,equal;for(intk=0;k<10;k++)//集合赋值{s1.AddMember(k);s2.AddMember(

7、k+7);}//s1:{0,1,2,…,9},s2:{7,8,9,…,16}6.1.3用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集合∨firstfirst081723354972∨用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。各结点所表示的成员e0,e1,…,en在链表中按升序排列，即e0structSetNode{Tdata;SetNode*link;SetNode(constT&x,Se