《第五章 数组和广义表》由会员分享，可在线阅读，更多相关《第五章 数组和广义表（42页珍藏版）》请在金锄头文库上搜索。
1、第5章 数组和广义表,wangzs,数组的类型定义 数组的存储表示方法 特殊矩阵的压缩存储表示方法 稀疏矩阵的压缩存储表示方法 广义表的定义 广义表的存储结构,学习要点,一组“连续的存储区域”，指根据此区域的起点，通过名称及偏移的方式，可以很容易地取到该区域的数据.,数组的回顾,在程序设计语言中，数组被定义为连续的、有限的，有序的同种元素的集合。,操作举例：读入数据 for (i=0;i=9;i+) scanf(“%d”,C语言中一维数组的定义及使用： 类型说明符 数组名常量表达式； 例如： int a10,数组的回顾,C语言中二维数组的定义及使用： 类型说明符 数组名常量表达式常量表达式；
2、例如： int a34,操作举例：读入数据 for (i=0;i=2;i+) for (j=0;j=3;j+) scanf(“%d”,数组的回顾,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。,5.1 数组的定义,A（01ip）(p=m-1,p=n-1) 其中每个数据元素i 是个行向量形式的线性表 i （i0i1iiin ） 或是一个列向量形式的线性表 i （0i1ijimi ）,0 a00 a01 a0n-1,1 a10 a11 a1n-1,m-1 am-10 am-11 am-1n-1,.,数组特点 数组结构固定（维数、上下界、元素关系） 数据元素同构 数组的基本操
3、作 数组初始化 数组结构销毁 存数组元素 取数组元素,数组的逻辑定义,5.2 数组的顺序表示和实现,数组只需要顺序存储结构 数组不需要插入和删除（移动元素）操作 顺序存储结构可实现随机存取 数组是多维结构，存储器是一维结构，所以存在两种从多维到一维的映象方法。 以行序为主序（低下标优先） 以列序为主序（高下标优先） 以第一行第一列元素的地址作为基地址，其他元素根据基地址和下标计算出存储地址。,a00 a01 a0n-1,a10 a11 a1n-1,am-10 am-11 am-1n-1,.,Loc( aij)=Loc(a00)+n*i+j*l,按行序为主序存放,0,1,n-1,n,(m-1)*
4、(n-1),数组的顺序表示和实现,按列序为主序存放,0,1,m-1,m,Loc(aij)=Loc(a00)+m*j+i*l,(m-1)*(n-1),数组的顺序表示和实现,这个矩阵中有一半的元素重复的，将浪费一半存储空间,5.3 矩阵的压缩存储,矩阵的压缩存储：对于多个值相同的元素只分配一个存储空间，对零元不分配存储空间。 特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定的规律。 稀疏矩阵：矩阵中存在大量的零元素。,矩阵的压缩存储,对称矩阵,若 n阶矩阵中的元满足a a,矩阵的压缩存储,三角矩阵,矩阵的上（下）三角（不包括对角线）中的元素均 为常数或为的阶矩阵,对角矩阵,Loc(aij)=L
5、oc(a11)+2(i-1)+(j-1) *L,假设在m*n的矩阵中，有个元素不为，则有 /（），认为 0.05时为稀疏矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值（三元组）,用三元组表示： (1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15), (6,4,-7) 再加上行列值(6,7)就可以唯一确定一个稀疏矩阵,稀疏矩阵,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,需存储: 行数=6;列数=7;非零元个数=8 每个非零元信息,稀疏矩阵的
6、压缩存储方法-顺序存储结构,稀疏矩阵的压缩存储方法-顺序存储结构,define MAXSIZE 12500 typedef struct int i,j; ElemType e; Triple; typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; TSMatrix,三元组顺序表,TSMatrix M; M.mu=6;M.nu=7;M.tu=8,三元组表所需存储单元个数为3(tu+1) 其中tu为非零元个数,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,M.datap.i,M.dat
7、ap.j,M.datap.e分别存放非零元行列数和非零元值,问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表,一般矩阵转置算法： for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=mrowcol; 时间复杂度：T(n)=O(mn),三元组存放的稀疏矩阵转置操作,解题思路：只要做到 将矩阵行、列值互换 将每个三元组中的i和j相互调换 重排三元组次序，使T中元素以T的行(M的列)为主序,方法一：按M的列序转置 即按T中三元组次序依次在M中找到相应的三元组进行 转置。为找到M中每一列所有非零元素，需对其三元组表 M从第一行起扫描一遍。
8、由于M中以行序为主序,所以 由此得到的恰是T中应有的顺序,三元组存放的稀疏矩阵转置操作,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,col=1,col=2,三元组存放的稀疏矩阵转置操作,算法描述： int TransposeSmatrix(TSMatrix M,TSMatrix ,时间复杂度：O(nu tu)若tu和mu nu 同数量级则：时间复杂度为O(mu nu2),方法二：快速转置 即按M中三元组次序转置，转置结果放入T中恰当位置,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -
9、7,6 3 14,此方法关键是要预先确定M中每一列(T的每一行)第一个非零元在T中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数。,实现：设两个数组 numcol：表示矩阵M中第col列中非零元个数 cpotcol：指示M中第col列第一个非零元在T中位置 显然有：,cpot1=1; cpotcol=cpotcol-1+numcol-1; (2col Ma.nu),1,3,5,7,8,8,9,三元组存放的稀疏矩阵转置操作,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,4,6,2,9,7,5,3,本列下一位置,int f
10、astTransposeSMatrix(TSMatrix M,TSMatrix ,时间复杂度：T(n)=O(nu+tu) 若 t 与mn同数量级，则T(n)=O(mn),稀疏矩阵的压缩存储方法-链式存储结构,typedef struct OLNode int i,j; ElemType e; struct OLNode *right,*down; OLNode; *Olink; typedef struct Olink *rhead,*chead; int mu,nu,tu; CrossList;,十字链表,稀疏矩阵的压缩存储方法-链式存储结构,从键盘接收信息建立十字链表算法,1、初始化rhe
11、ad与chead指针 2、接收信息生成结点 3、将新生成的结点插入到十字链表中 修改同一行的前一个元素的right指针，修改同一列元素的down指针,m=4,n=3,t=5 1,1,3 2,2,5 2,3,4 4,1,8 2,1,7,矩阵相加,矩阵A+矩阵B可能出现的情况： 1、aij+bij : aij与bij均为非零元若值非零，修改相应的 aij的值；若为零元，则删除aij结点 2、 aij + bij = aij :表示bij为零，则不作任何操作 3、 aij + bij =bij：表示aij为零，则插入bij元素,设pa,pb分别指向矩阵A和矩阵B中行值相等的两个结点 若pa= =Nu
12、ll表示A中无非零元 则： (1)pa= = Null 或者pa-j pb-j 则在A中插入结点bij (2)pa-j j 则pa=pa-right (3)pa-j= =pb-j且pa-e+pb-e !=0 则pa-e= pa-e+pb-e 若pa-e+pb-e =0 则删除pb结点并修改pa同行、同列 的前一个结点的right与down域 此外：需要设定辅助指针：pre 指示pa同一行的前驱结 点；A的每一列的链表上设一个指针hlj，初值和列链 表的头指针相同，即hlj=cheadj,广义是线性表的推广。广泛地用于人工智能等领域的表处理语言LISP。,广义表也一种线性表,又称为列表。一般记作
13、： LS=(1,i,n) LS：表名； n： 表长；空表：n = 0 i ：元素，若是单个元素，称为广义表LS的原子， 若是广义表则称为广义表LS的子表。 表头：第一个元素；其余元素组成的表为表尾。,5.4 广义表的定义,广义表的定义,例：以下为广义表 A=() F=(b,(c,d,e) E=(b,(c),(d,e) D=(E,A,F) C=(A,D,F) B=(a,B)=(a,(a,(a,v.) 基本操作举例： 求长度GListLength(L);由最外层括弧中的“逗号“来定 求深度GListDepth(L);括弧嵌套的最深层次 求表头GetHead(L);表中第一个数据元素(单原子或表)
14、求表尾GetTail(L); “必定”是个广义表(可能为空）,广义表的定义,结论：广义表是一种多层次结构，兼有线性结构的特性： 1. 广义表中的数据元素有固定的相对次序； 2. 广义表的长度定义为最外层括弧中包含的数据元素个数； 3. 广义表的深度定义为广义表中括弧的最大重数。 4. 广义表可被其它广义表所共享。 D=(E,A,F) 5. 广义表可以是一个“自递归”的表。B=(a,B) 自递归的广义表的长度是个有限值，而深 度为无限值。,5.4 广义表的存储结构,采用链式存储结构： typedef enumATOM,LISTElemTag;/ATOM=0;LIST=1 typedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode *hp,*tp; ptr; ; *GList,表结点,原子结点,小结,本章学习了线性表的扩展：即数据元素本身也是一个数据结构（线性表）。 要求掌握数组的类型定义、数组的存储表示方法、 特殊矩阵的压缩存储表示方法及其与线性存储结构的对应、稀疏矩阵的压缩存储表示方法及其运算。 另外，要求掌握广义表的定义和广义表的存储结构。,作业及思考题,实现二维数组到一维数组的映射的算法。 上机实现三元组存放的稀疏矩阵转置算法。,
