数据结构组广义表.ppt

第五章数组和广义表数组和广义表可以看成是线性表在以下含义上的扩展：5.1数组一.多维数组的概念2．二维数组3．多维数组二.多维数组在计算机内的存放（数组）提要5.1.1数组的类型定义二维数组的定义:InitArray(A,n,bound1,...,boundn)Value(A,e,index1,...,indexn)Assign(A,e,index1,...,indexn)5.1.2数组的顺序表示和实现以“行序为主序”的存储映象同理，三维数组Al×m×n按行优先存放的地址计算公式为：行序为主序排列规律：推广到一般情况，可得到n维数组数据元素存储位置的映象关系:以“列序为主序”的存储映象列序为主序排列规律：5.1.3矩阵的压缩存储1.特殊矩阵以对称矩阵为例，n阶对称矩阵A满足：2.稀疏矩阵以常规方法，即以二维数组表示高阶的稀疏矩阵时会产生的问题:解决问题的原则:稀疏矩阵的压缩存储方法:一、三元组顺序表矩阵M可表示为：三元组顺序表表示的稀疏矩阵的转置运算。在三元组表表示的稀疏矩阵中，怎样求得它的转置呢?例如：voidtransposeSMatrix(TSMatrixM,TSMatrixT)用常规的二维数组表示时的算法：（2）按照A的行序进行转置(快速转置)例如：StatusFastTransposeSMatrix(TSMatrixM,TSMatrixT){分析算法FastTransposeSMatrix的时间复杂度：二、行逻辑链接的顺序表#defineMAXMN500

typedefstruct{

Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

intmu,nu,tu;

}RLSMatrix;//行逻辑链接顺序表类型例如：给定一组下标，求矩阵的元素值矩阵乘法的精典算法:两个稀疏矩阵相乘（Q?M?N）

的过程可大致描述如下：StatusMultSMatrix

(RLSMatrixM,RLSMatrixN,RLSMatrixQ){处理的每一行

分析上述算法的时间复杂度三、十字链表十字链表的类型定义例：5.2广义表1.广义表3.广义表的深度5.广义表举例广义表举例（广义表）提要5.2.1广义表的类型定义广义表LS=(?1,?2,…,?n)的结构特点:3)广义表是一个多层次的线性结构基本操作5.2.2广义表的表示方法有两种具体的表示方法：(1)广义表的头尾链表存储表示：例如:L=(a,(x,y),((x)))再看几个例子（1）A=(e)该存储结构的特点(2)广义表的扩展线性链表存储表示例如:再看几个例子（1）A=(e)该存储结构的特点本章学习要点本章作业：由于广义表中的数据元素可以是原子，也可以是列表，即其中的元素可以有不同的结构，难以用顺序存储结构表示，因此，通常采用链式存储结构。在用链式结构时，需要两种结构的结点：(1)表结点，用以表示列表；(2)原子结点，用以表示原子。(1)头尾链表存储表示(2)扩展线性链表存储表示typedefenum{ATOM,LIST}ElemTag;//枚举类型//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//公共部分，标志域union{//联合部分AtomTypeatom;//原子结点的数据域struct{structGLNode*hp,*tp;}ptr;//表结点的指针域};}*GList表结点:tag=1hptpptrtag=0atom原子结点：空表非空表tag=1指向表头的指针指向表尾的指针LSLS=NULLL10a110