第3章1集合稀疏矩阵和广义表

1、3.1集合的定义和抽象数据类型 3.2集合的顺序存储结构和操作实现 3.3集合的链接存储结构和操作实现3.1集合的定义和抽象数据类型2集合的抽象数据类型 集合的抽象数据类型同样包括数据和操作两个部分。 数据部分为一个集合，假定用标识符S表示。操作部分包括 对集合进行的各种常用运算，如初始化集合为空，向集合中插入指定元素，从集合中删除一个元素等。具体定义如下： ADT SET is Data: 一个集合S，用标识符SetT表示抽象存储类型 Operation: void InitSet(SetT&S);/初始化集合为空bool InsertSet(SetT&S,ElemType

2、item);/向集合中插入一个元素bool DeleteSet(SetT&S,ElemType &item);/从集合删除一个元素bool FindSet(SetT&S,ElemType &item);/从集合中查找一个元素bool ModifySet(SetT&S,const ElemType &item);/修改集合元素bool InSet(SetT&S,ElemType item);/判断一个元素是否属于集合bool EmptySet(SetT&S);/判断集合是否为空int LenthSet(SetT&S);/求出

3、集合的长度void OutputSet(SetT&S);/输出集合中的所有元素void UnionSet(SetT&S1, SetT&S2, SetT&S);/求两个集合的并集void InterseSet(SetT&S1, SetT&S2, SetT&S);/求两个集合的交集void DifferenceSet(SetT&S1, SetT&S2, SetT&S);/求两个集合的差集void ClearSet(SetT&S);/清除集合中的所有元素end SET 集合的顺序存储就是定义一个数组类型的对象来存

4、储集合元素，同时要定义一个整数变量来存储当前集合长度和定义一个整型常量或变量来存储数组类型的长度。这三个对象的定义假定如下： const int MaxSize=20; ElemType setMaxSize; int len; 为了对集合操作方便，通常把set数组和len变量封装在一个结构类型中，结构类型名用Set表示，即Struct Set ElemType setMaxSize; int len;3.2集合的顺序存储结构和操作实现 若要对存储集合的数组空间采用动态分配，并且其数组长度能够随之改变，则可以定义出如下的结构类型：Struct Set ElemType *set;int len

5、;int MaxSize; a1a2a3an0下面以set为集合的顺序存储类型，给出部分集合运算的算法。图3-1集合的顺序存储结构12n-1nMaxSize-1下标set/*1.初始化集合为空*/void InitSet(Set&S,int ms) S.MaxSize=10; S.set=new ElemType10; if(!S.set) cerr“存储空间用完”endl; exit(1); S.len=0;/*2.向集合中插入一个元素*/算法描述如下：（1）查找集合中是否存在待插入的元素，若存在，则不能插入；（2）检查集合空间是否用完，若是则动态增加存储空间；（3）把item插到最

6、后一个元素后面的空位置上；（4）集合长度加1；（5）返回真表示插入成功。具体实现过程如下：bool InsertSet(Set&S,ElemType item) for(int i=0;iS.len;i+) if(S.seti= =item)return false/元素存在于集合中，不用插入 /对空间用完进行处理 if(S.len= =S.MaxSize) int k=sizeof(ElemType); S.set=(ElemType*)realloc(S.set,2*S.MaxSize*k); if(S.set=NULL) cout“存储空间用完”endl; exit(1);S.M

7、axSize=2* S.MaxSize; S.setS.len=item; S.len+; return true;/*3.从集合中删除一个元素算法描述如下：（1）查找集合中是否存在待删除的元素，若存在，则删除；（2）把空出的位置用最后一个元素填补;（3）集合长度减1；（4）返回真表示删除成功；算法实现如下：bool DeleteSet(Set&S,ElemType& item) for(int i=0;iS.len;i+) if(S.seti= =item)break; if(iS.len) item=S.seti; S.seti=S.setS.len-1; S.len-;

8、if(float(S.len)/S.MaxSize10) int k=sizeof(ElemType); S.set=(ElemType*)realloc(S.set,S.MaxSize*k/2); S.MaxSize= S.MaxSize/2; return ture; /*4.输出集合中的元素*/void OutputSet(Set&S) for(int i=0;iS.len;i+) coutS.seti ; coutendl;简单选择排序算法描述如下：（1）把顺序存储的集合（数组）a看作一个有序表(空表)和一个无序表a0an-1，从无序表中顺序查找一个最小值，把它与表中第一个元素

9、a0交换；else return false;(2)从当前无序表中顺序查找一个最小值元素，把它与此表中第一个元素a1交换。(3)进行n-1次处理时，有序表中包含n-2个元素a0an-3，无序表an-2an-1，从这两个元素中查找最小值把它交换到an-2位置后,整个数组就成了一个有序表。具体算法实现如下：void OutputSet1(Set&S) int i,j,k; ElemType *a=new ElemTypeS.len;/定义临时数组a for(i=0;iS.len;i+)/把集合元素赋给数组a ai=S.seti; for(i=0;iS.len-1;i+) k=i; for(

10、j=i+1;jS.len;j+) if(ajak) k=j; ElemType x=ai;ai=ak;ak=x; coutai ; coutaS.len-1endl; delete a; 3.3集合的链接存储结构和操作实现 单链表中的节点是靠动态分配产生的，存储一个单链表只需要存储它的表头指针即可。由表头指针来访问单链表，因此，表头指针HT可定义为 sNode*HT 集合的链接存储结构如P103页图3-2。 按照集合的抽象数据类型的定义，假定集合存储采用单链表结构，下面给出部分运算的实现过程 。 /*1.初始化集合为空*/void InitSet(sNode*&HT) HT=NULL;

11、 /*2.向集合中插入一个元素*/bool InsertSet(sNode*&HT,ElemType item) sNode*tp=new sNode; if(!tp) cout“存储空间用完”data=item;/从单链表中顺序查找是否存在值为item的节点 sNode*p=HT; while(p!=NULL) if(p-data= =item) break; else p=p-next; /若不存在，则把新节点插入到表头 if(p= =NULL) tp-next=HT; HT=tp; return true; else return false;*3.从集合中删除一个元素*/bool DeleteSet(sNode*&Head,ElemType & item)/从单链表中查找是否存在值为item的元素 sNode*cp=HT,*ap=NULL; while(cp!=NULL) if(cp-da