数据结构第三章1.ppt

集合(set)由具有相同属性的数据元素组合而成,数据之间没有任何前驱和后继关系. void InitSet(SetT S); void ClearSet(SetT S); int LenthSet(SetT S); bool EmptySet(SetT S); bool InSet(SetT S, ElemType item); void OutputSet(SetT S); bool FindSet(SetT S, ElemType item); bool ModifySet(SetT S, const ElemType item); bool InsertSet(SetT S, ElemType item); bool DeleteSet(SetT S, ElemType item); void UnionSet(SetT S1, SetT S2, SetT S); void InterseSet(SetT S1, SetT S2, SetT S); void DifferenceSet(SetT S1, SetT S2, SetT S); 静态分配的数组存放: struct Set { ElemType set[MaxSize]; int len; }; * * 3.2 集合的顺序存储 结构和操作实现 3.5 广义表 第三章 集合 稀疏矩阵 和广义表 3.4 稀疏矩阵 3.3 集合的链接存储 结构和操作实现 3.1 集合的定义和 抽象数据类型 3.1 集合的定义和抽象数据类型 {a 1, a 2, …, a i, a i+1,…, a n} 下标为编号,不代表任何次序 元素类型用ElemType表示, 可以通过typedef语句在使用前将其定义为任一具体类型。如，整数 typedef int ElemType ; 抽象数据类型集合的定义如下： ADT SET is Data： 一个集合S,假定用标识符SetT表示 抽象存储类型 end SET Operation： 操作描述请见后续页 3.2 集合的顺序存储结构和操作实现 new ElemType[MaxSize] or (ElemType*)malloc(sizeof(Elemtype)*MaxSize)) 动态分配的数组存放: struct Set { ElemType *set; int len; int MaxSize; }; void InitSet(Set S )； 操作结果： 构造一个空的集合。 1 初始化操作 p96 void ClearSet(Set S )； 操作结果： 由于集合数组空间是动态分配的, 清除集合就是释放动态存储空间。 2 清除集合中所有元素 p96 int LenthSet(Set S )； 操作结果： 返回集合S中的len域的值。 3 求出集合长度 p97 bool EmptySet(Set S )； 操作结果： 集合长度为0则返回真,否则返回假。 4 判断集合是否为空 p97 bool InSet(Set S , ElemType item) { for(int i=0;iS.len; i++) if(S.set[i] == item) retrun true; retrun false; } 5 判断一个元素是否属于集合 p97 void OutputSet(Set S) { for(int i=0;iS.len; i++) couts.set[i]‘ ‘; coutendl; } 6 输出集合中所有元素 p97 void OutputSet(Set S) { int I,j,k; ElemType *a=new ElemType[S.len]; for(i=0; iS.len; i++) a[i]=S.set[i]; for(i=0; is.len-1; i++) { k=i; 6 输出集合中所有元素 -简单选择排序 for(j=i+1; jS.len; j++) if(a[j]a[k]) k=j; ElemType x=a[i]; a[i]=a[k]; a[k]=x; couta[i]‘ ‘; } coutendl; delete []a; } 其时间复杂度为: O(n2) bool FindSet(Set S, ElemTyp