第七章、集合和有哪些信誉好的足球投注网站.ppt

集合与有哪些信誉好的足球投注网站 《数据结构》第七章 本章主要内容 集合及其表示 静态有哪些信誉好的足球投注网站表 二叉有哪些信誉好的足球投注网站树 AVL树 集合及其表示 集合基本概念： 集合： 通常将一些具有确定的、可以区分的若干事物的全体称为集合。集合是成员的一个群集，成员可以是单元素(原子),也可以是集合 集合的特性： 集合中的成员必须是互不相同的 集合中的成员是无序的，可以任意列出 算法和数据结构中的常见集合： 其单元素通常是整数、字符、字符串或指针 同一集合中的所有成员具有相同的数据类型 常设定集合中的单元素具有线性有序关系，此关系可记作“”，称“优先于”或“小于”，整数、字符、字符串都有自然的线性顺序 集合的基本运算: 并(union) 交(intersection) 差(difference) 判存在(contain) 集合的存储表示：集合是最基本的抽象数据类型，本章介绍了集合的二种常见的存储表示 位数组(位向量)存储表示 引入一维整型数组表示集合(全集) ，集合(全集)中的所有成员在数组中都有一个元素与之对应 问题涉及的是全集的子集,将与子集所含成员对应的数组元素的值设为1,其他数组元素值设为0 有序链表存储表示 引入链表表示集合(子集),集合中的所有成员在链表中都有一个结点与之对应 链表中结点按关键码的升序排列,可提高有哪些信誉好的足球投注网站效率 【例】 {1,2,3},{3,2,1}是同一个集合,但在算法和数据结构中常设定整数具有线性有序关系(小于),记作 {1,2,3},集合中元素呈现123 【例】 A={a,b,c},B={b,d}是两个集合,则有 集合并运算:A∪B={a,b,c,d} 集合交运算:A∩B={b} 集合差运算:A－B={a,c} 集合判存在运算: a∈A 用位向量实现集合的抽象数据类型 若讨论的集合是全集合{0,1,2, …,n}的子集,且n是一个不大的整数时,可用位(0,1)向量来实现集合 【例】 设全集合U={0,1,2,3,4,5,6,7,8,9},子集合SUB={1,3,5,7,9} 引入一维整型数组A表示全集U, 集合U的每个成员都对应数组A的一个元素(此处用数组下标值表示集合成员值) 子集SUB包含的成员,在数组A的对应元素值设为1, 子集SUB不包含的成员,在数组A的对应元素值设为0 用位向量实现的集合类定义 class Set { int * bitVector; int MaxSize; int sxd; public: static int tag; Set(int sz=DefaultSize); Set(Set x); ~Set() { cout destroy :sxdendl; tag--; delete []bitVector; } void MakeEmpty() { for(int i=0;iMaxSize;i++) bitVector[i]=0; } int GetMember(const int x) { return x=0 xMaxSize ? bitVector[x]:-1; } int AddMember(const int x); int DelMember(const int x); Set operator=(Set right); Set operator+(Set right); Set operator*(Set right); Set operator-(Set right); int Contains(const int x); int SubSet(Set right); int operator==(Set right); friend ostream operator(ostream out,Set x); }; 说明： 用位向量实现的集合类定义，实际是用一维整型数组表示全集合 问题涉及的总是全集合的子集 两个子集进行并、交、差运算，结果仍是子集，仍用一维整型数组表示 用有序链表实现集合的抽象数据类型 用有序链表可以表示无穷全集合的子集 沿有序链表有哪些信誉好的足球投注网站集合元素,不用遍历整个链表,可提高有哪些信誉好的足球投注网站效率 【例】 设集合为S={17,09,72,23,63,49,35} 引入带表头结点的单链表L表示集合S,集合S中的每个成员都对应链表L中的一个结点 链表中的结点是按对应的集合成员值的升序排列 用有序链表实现的集合类定义 templateclass Type class SetList; //define class SetNode templateclass Type class SetNode { friend class SetListType; Ty