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

1、第3章 集合、稀疏矩阵和广义表,2020/7/31,DS,主要内容,2020/7/31,DS,3.1 集合的定义和抽象数据类型,集合定义 集合的抽象数据类型,2020/7/31,DS,3.1.1 集合定义,集合(set)：又称集合结构，由具有相同属性的数据元素组合而成，数据之间没有任何前驱与后继关系。 集合的长度：数据元素的个数称为集合的长度(n=0),n=0表示空集() 表示：a1,a2,ai,ai+1,an 下标为该元素的编号，主要是为了区别而任意标注的，不代表任何次序 集合中的元素可以按任何次序排列 也可以按元素前后位置编号的次序排列,2020/7/31,DS,3.1.2 集合的抽象数据

2、类型,数据部分：一个集合，用标识符S表示 操作部分：包括对集合进行的各种常用运算 集合的抽象数据类型定义： ADT SET is Data: 一个集合S，假定用标识符SetT表示抽象存储类型 Operation: void InitSet(SetT,2020/7/31,DS,3.1.2 集合的抽象数据类型,int LenthSet(SetT,2020/7/31,DS,3.1.2 集合的抽象数据类型,void UnionSet( SetT /存储集合元素的数组的长度 ElemType setMaxSize; /存储集合所有元素的数组 int len; /集合当前长度变量，取值在0MaxSize之

3、间,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,为了集合操作方便，可以把set数组和len变量封装在一个结构类型中，结构类型名用Set表示，定义如下： struct Set ElemType setMaxSize; int len; ;,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,若对存储集合的数组空间采用动态分配，并且其数组长度能够随之改变，则可以定义出如下的Set类型： struct Set ElemType *set; int len; int MaxSize; ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,集合运算的算法实现

4、初始化集合并置为空 void InitSet(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,清除集合中的所有元素 void ClearSet(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,求出集合的长度，即所含元素的个数 int LenthSet(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,判断一个元素是否属于集合 bool InSet(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,输出集合中所有元素 void OutputSet(Set ,2020/7/31,DS,3.2 集合的

5、顺序存储结构和操作实现,采用简单选择排序实现有序输出集合元素的算法 void OutputSet1(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,从集合中查找一个元素 bool FindSet(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,修改集合中的一个指定元素 bool ModifySet(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,向集合插入一个元素 顺序查找集合中是否存在值为待插值item的元素，若存在则不能插入，返回假，因为集合中不允许存在重复的元素 检查集合空间是否用完，若是则动态重分配，增加存储

6、空间 把item值插入到表尾（即最后一个集合元素的后面空位置）上 集合长度增1 返回真表示插入成功,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,bool InsertSet(Set /返回真表示插入成功 ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,从集合删除一个元素 bool DeleteSet(Set /删除失败返回假 ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,求两个集合的并集 void UnionSet(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,求两个集合的交集 void InterseSet

7、(Set ,2020/7/31,DS,3.2 集合的顺序存储结构和操作实现,求两个集合的差集 void DifferenceSet(Set ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,通过存储结点之间的链接实现集合的链接存储结构，链接形成的结果称为链接表，通常采用单链表。 由于集合中的元素是无序的，所以在单链表中可以按任何次序链接。 插入操作：插入到表头，成为新的表头结点 删除操作：把该结点的指针域的值赋给其前一个结点的指针域 结点结构定义： struct SNode ElemType data; SNode* next; ;,2020/7/31,DS,3.3 集合的链接

8、存储结构和操作实现,表头指针： SNode* head; 集合单链表的示意图：,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,初始化集合为空 void InitSet(SNode* ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,清除集合中的所有元素并释放占有的动态存储空间 void ClearSet(SNode* ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,求出集合中元素个数 int LenthSet(SNode* HT) int n=0; while(HT!=NULL) n+; HT=HT-next; return n; ,2020

9、/7/31,DS,3.3 集合的链接存储结构和操作实现,判断集合是否为空 bool EmptySet(SNode* HT) return HT=NULL; ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,判断一个元素是否属于集合 bool InSet(SNode* HT,ElemType item) while(HT!=NULL) if(HT-data=item) return true; else HT=HT-next; return false; ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,/输出集合中所有元素 void OutputSet(SNod

10、e* HT) while(HT!=NULL) coutdatanext; coutendl; ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,从集合中查找一个元素 bool FindSet(SNode* HT,ElemType ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,修改集合中的一个指定元素 bool ModifySet(SNode* HT,const ElemType ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,向集合插入一个元素 bool InsertSet(SNode* ,2020/7/31,DS,3.3 集合的链接存储结

11、构和操作实现,从集合删除一个元素 bool DeleteSet(SNode* ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,求两个集合的并集 void UnionSet(SNode* HT1, SNode* HT2, SNode* ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,求两个集合的交集 void InterseSet(SNode* HT1, SNode* HT2, SNode* /使p指向下一个结点 ,2020/7/31,DS,3.3 集合的链接存储结构和操作实现,求两个集合的差集 void DifferenceSet(SNode* HT1, S

12、Node* HT2, SNode* /使p指向下一个结点 ,2020/7/31,DS,3.4 稀疏矩阵,3.4.1 稀疏矩阵的定义 3.4.2 稀疏矩阵的存储结构 3.4.3 稀疏矩阵的运算,2020/7/31,DS,3.4.1 稀疏矩阵的定义,稀疏矩阵的概念 矩阵：是一个具有m行n列的数表，共包含有m*n个数，每个元素处在确定的行和列的交点位置上，都与一对行号和列号唯一对应。 方阵：当一个矩阵中的行数和列数相同时。 稀疏矩阵：其非零元素的个数远远小于零元素的个数。,2020/7/31,DS,3.4.1 稀疏矩阵的定义,举例：,2020/7/31,DS,3.4.1 稀疏矩阵的定义,稀疏矩阵的三

13、元组线性表示 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,三元组线性表表示为： (1,1,3),(1,4,5),(2,3,-2), (3,1,1),(3,3,4),93,5,6), (5,3,-1),2020/7/31,DS,3.4.1 稀疏矩阵的定义,稀疏矩阵的抽象数据类型 数据部分为用三元组线性表表示的稀疏矩阵。 操作部分所包含的操作与对一般矩阵所做的操作相同，通常为求矩阵转置，计算两个矩阵的和，计算矩阵乘积等。,2020/7/31,DS,3.4.1 稀疏矩阵的定义,ADT SparseMatrix is Data: 采用顺序或链接方式存储的稀疏矩阵，假定其存储类型用SM

14、atrix标识符表示。 Operation: void InitMatrix(SMatrix end SparseMatrix,2020/7/31,DS,3.4.2 稀疏矩阵的存储结构,除了存储三元组线性表中的所有元素之外，通常还需要存储稀疏矩阵的行数，列数和非零元的个数这3个整型量。 顺序存储：顺序存储三元组线性表，先要定义三元组，再定义线性表。,定义三元组 Struct Triple int row,col; Elemtype val; ;,定义三元组线性表 Struct SMatrix int m,n,t; Triple smMaxTerms+1; ;,2020/7/31,DS,3.4.

15、2 稀疏矩阵的存储结构,(1,1,3),(1,4,5),(2,3,-2),(3,1,1), (3,3,4),93,5,6),(5,3,-1),2020/7/31,DS,3.4.2 稀疏矩阵的存储结构,链接存储 带行指针向量的链接存储 需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表。 使用一个行指针向量，向量中的第i个分量用来存储稀疏矩阵中第i行所对应的单链表的表头指针。,定义三元组结点 Struct TripleNode int row,col; Elemtype val; TripleNode* next; ;,带行指针向量的链接存储 Struct LMatrix in

16、t m,n,t; TripleNode * vectorMaxRows+1;,2020/7/31,DS,3.4.2 稀疏矩阵的存储结构,2020/7/31,DS,3.4.2 稀疏矩阵的存储结构,十字链接存储：既带行指针向量又带列指针向量，每个三元组结点既处于同一行的单链表中，又处于同一列的单链表中。,定义结点 Struct CrossNode int row,col; Elemtype val; CrossNode *down,*right; ;,十字链接存储 Struct CLMatrix int m,n,t; CrossNode *rvMaxRows+1; CrossNode *cvMax

17、columns+1; ;,2020/7/31,DS,3.4.2 稀疏矩阵的存储结构,2020/7/31,DS,3.5 广义表,3.5.1 广义表的定义 3.5.2 广义表的存储结构 3.5.3 广义表的运算 3.5.4 简单程序举例,2020/7/31,DS,3.5.1 广义表的定义,广义表的定义：简称表。n个表元素组成的线性表，其中表元素可以是单元素或子表。 组成 单元素：某一确定类型的对象。用小写字母表示 子表：由单元素构成的表，也称为表元素。用大写字母表示 一般表示：(a1，a2， ，ai，ai+1，an) 或LS=(a1，a2， ，ai，ai+1，an) 表头(head)：广义表的第一

18、个元素 表尾(tail)：广义表中其余元素组成的表 表长：表中元素的个数 n=0：空表 表的深度：指该表中括号嵌套的最大层数,2020/7/31,DS,3.5.1 广义表的定义,说明: 广义表是线性表的一种推广。 广义表的定义是递归的。因为在描述广义表的时候又用到了广义表的概念。 广义表是多层次结构。 一个广义表可以为其它广义表所共享。 广义表的图形表示 单元素： 表元素：,2020/7/31,DS,3.5.1 广义表的定义,例： (1)A=( ) (2) B=(e ) (3) C=(a,(b,c,d) (4) D=(A(),B(e),C(a,(b,c,d) (5) E=(a,(a,b),(a,b),c),2020/7/31,DS,3.5.2 广义表的存储结构,存储方法：动态链接存储 结点结构： 元素结点 表结点,2020/7/31,DS,3.5.2 广义表的存储结构,(1)A=( ),(2)B=(e),(3)C=(a,(b,c,d),A=NULL,2020/7/31,DS,3.5.2 广义表的存储结构（带表头附加结点）,(1)A=( ),(2)B=(e),(3)C=(a,(b,c,d),2020/7/31,DS,3.5.3 广义表的运算,求广义表的长度（递