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

《第3章集合、稀疏矩阵和广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章集合、稀疏矩阵和广义表2021/9/20主要内容集合的定义和抽象数据类型1集合的顺序存储结构和操作实现2集合的链接存储结构和操作实现3稀疏矩阵4广义表52021/9/20DS3.1集合的定义和抽象数据类型集合定义集合的抽象数据类型2021/9/20DS3.1.1集合定义集合(set)：又称集合结构，由具有相同属性的数据元素组合而成，数据之间没有任何前驱与后继关系。集合的长度：数据元素的个数称为集合的长度(n>=0),n=0表示空集({})表示：{a1,a2,…,ai,ai+1,…,an}下标为该元素的编号，主要是为了区别而任意标注的，不代表任何次序集合中的元素可以按任何次序排列

2、也可以按元素前后位置编号的次序排列2021/9/20DS3.1.2集合的抽象数据类型数据部分：一个集合，用标识符S表示操作部分：包括对集合进行的各种常用运算集合的抽象数据类型定义：ADTSETisData:一个集合S，假定用标识符SetT表示抽象存储类型Operation:voidInitSet(SetT&S);voidClearSet(SetT&S);2021/9/20DS3.1.2集合的抽象数据类型intLenthSet(SetT&S);boolEmptySet(SetT&S);boolInSet(SetT&S,ElemTypeitem);voidOutputSet(SetT&S

3、);boolFindSet(SetT&S,ElemType&item);boolModifySet(SetT&S,constElemType&item);boolInsertSet(SetT&S,ElemTypeitem);boolDeleteSet(SetT&S,ElemType&item);2021/9/20DS3.1.2集合的抽象数据类型voidUnionSet(SetT&S1,SetT&S2,SetT&S)voidInterseSet(SetT&S1,SetT&S2,SetT&S)voidDifferenceSet(SetT&S1,SetT&S2,SetT&S)endSET

4、2021/9/20DS3.2集合的顺序存储结构和操作实现集合的顺序存储就是定义一个数组类型的对象来存储集合元素，同时要定义一个整数变量来存储当前集合长度和定义一个整型常量或变量来存储数组类型的长度。如下所示：constintMaxSize=20;//存储集合元素的数组的长度ElemTypeset[MaxSize];//存储集合所有元素的数组intlen;//集合当前长度变量，取值在0~MaxSize之间2021/9/20DS3.2集合的顺序存储结构和操作实现为了集合操作方便，可以把set数组和len变量封装在一个结构类型中，结构类型名用Set表示，定义如下：structSet{Ele

5、mTypeset[MaxSize];intlen;};2021/9/20DS3.2集合的顺序存储结构和操作实现若对存储集合的数组空间采用动态分配，并且其数组长度能够随之改变，则可以定义出如下的Set类型：structSet{ElemType*set;intlen;intMaxSize;}len下标01…n-1n↓n+1↓MaxSize-1seta1a2an2021/9/20DS3.2集合的顺序存储结构和操作实现集合运算的算法实现初始化集合并置为空voidInitSet(Set&S){S.MaxSize=10;//初始定义数组长度为10，以后可增减S.set=newElemType[1

6、0];//动态存储空间分配if(!S.set){cout<<"动态可分配的存储空间用完，退出运行！"<

7、boolEmptySet(Set&S){returnS.len==0;}2021/9/20DS3.2集合的顺序存储结构和操作实现判断一个元素是否属于集合boolInSet(Set&S,ElemTypeitem){for(inti=0;i