华东理工大学数据结构

《华东理工大学数据结构》由会员分享，可在线阅读，更多相关《华东理工大学数据结构（56页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构信息学院1第五章 数组和广义表n5.1 数组的定义n5.2 数组的顺序表示和实现n5.3 矩阵的压缩存储5.3.1 特殊矩阵5.3.2 稀疏矩阵5.4 广义表的定义5.5 广义表的存储结构25.1 数组的定义数组可以看作线性表的推广。 表中的数所元 素本身也是一种线性表。一维数组可以看作一 个线性表，二维数组可以看作“数据元素是一 维数组”的一维数组，三维数组可以看作“数 据元素是二维数组”的一维数组，例如， m行 n列二维数组：a11 a12 a1na21 a22 a2n am1 am2 amn Amn=3在C语言中，一个二维数组类型可以定义为其分量 类型为一维数组类型的一维数

2、组类型:typedef elemtype array2mn;等价于：typedef elemtype array1n;typedef array1 array2m;一个n维数组类型可以定义为其数据元素为n-1维数 组类型的一维数组类型。 4数组是一个具有固定格式和数量的数据有序 集，每一个数据元素有唯一的一组下标来标 识，通常在各种高级语言中数组一旦被定义 ，每一维的大小及上下界都不能改变。因此 ，在数组上不能做插入、删除数据元素的操 作。在数组中通常做下面两种操作：(1) 取值操作：给定一组下标，读其对 应的数据元素。 (2) 赋值操作：给定一组下标，存储或 修改与其相对应的数据元素。5n数

3、组的抽象数据类型的定义：nADT Array n数据对象：Daj 1 ,j2 ,., ,.jn | ji =0,.,bi -1, i=1,2,n,nn(0)称为数组的维数，nbi 是数组第i维的长度，nji是数组元素的第i维下标，naj 1 ,.,j nElemSet n数据关系：RR1, R2, ., RnnRi | n0 =m) printf (%d,%d,%dn, i ,k,min);n /* if */n /*for i*/ 17n设计一个可容纳40位数的求n!的程序 。n分析：应用数组来弥补整数数据类型有 限的使用范围。n先将Data数组中的数据设初始值为零 ，令第一位数据 值为1，

4、位数也为1， 再将次相乘积存回数组中。n步骤1：1!=1n 4321000118n步骤2：2!=1!*2n位数为1n数组1=数组1*2n步骤3：3!=2!*3n位数为1n数组1=数组1*34321 00024321 000619n步骤4：4!=3!*4n位数为1n数组1=数组1*4n进位：n数组2=数组2+数组1/10=0+2=2n数组1=数组1%10=4n位数为24321 000244321 002420n步骤5：5!=4!*5n位数为2n数组1=数组1*5n数组2=数组2*5n进位n(1) 数组1进位n数组2=数组2+数组1/10=10+2=12n数组1=数组1%10=0n(2) 数组2进

5、位n数组3=数组3+数组2/10=0+1=1n数组2=数组2%10=2n位数为24321002*5=104*5=2021nnMain()nn int Data40;n int Digit,I,j,k,r,n;nFor (I=1;I10) n for (r=1;r10) Digit+;n /*当数组中的值大于10时，则位数加1*/n Datar+1+=Datar/10;/*前一位数组值=前一位数组值+此位数组值除以10*/Datar= Datar%10；23nnPrintf(“%d!=”,i);nFor (k=Digit;ko;k-)n printf(“%d”,Datak);n printf(“

6、n”);n245.3 矩阵的压缩存储用二维数组来存储矩阵元。当矩阵中有许 多值相同的元素或零元素时，以常规方 法，即以二维数组表示矩阵时产生的问 题: 1) 占的空间很大; 2) 计算中进行了很多和零值的运算; 如何解决问题: 压缩存贮：为多个值相同的元素只分配 一个存储空间；对零元不分配空间。25n通常，以非零元素在矩阵中的分布情况 ，可将矩阵分为两类:n1) 特殊矩阵的压缩存储n 例如: 三角矩阵n 对角矩阵n2) 稀疏矩阵的压缩存储n随机矩阵中的非零元分布不规则265.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一 定规律的矩阵. 1、对称矩阵 在一个n阶方阵A中，若元素满足下

7、述性质：aij=aji 0i,jn-1 则称A为对称矩阵。271 5 1 3 7 a005 0 8 0 0 a10 a 111 8 9 2 6 a20 a21 a233 0 2 5 1 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1k=0 1 2 3 n(n-1)/2 n(n+1)/2-1元素总数为：n(n+1)/2将这些元素存放在sa0n(n+1)/2-1中。a00a10a11a20an-1 0 an-1,n-128在aij和sak 之间找一个对应关系 若ij，则ai j在下三角形中。 ai j之前的i行（从 第0行到第i-1行）一共有1+2+i=i(i

8、+1)/2个元 素，在第i行上， ai j之前恰有j个元素 k=i*(i+1)/2+j 0kj 上三角矩阵中，主对角线之上的第i行(0ijk=k=313、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的 带状区域中，即除了主对角线和主对角线相邻两侧的若干条 对角线上的元素之外，其余元素皆为零。a00 a01a10 a11 a12a21 a22 a23. . an-2 n-3 an-2 n-2 an-2 n-1an-1 n-2 an-1 n-1按某个原则(或以行为主，或以对角线的顺序)将其压缩 存储到一维数组中 325.3 稀疏矩阵假设m行n列的矩阵含t个非零元素，则称d =t/(m

9、 * n)为稀疏因子 通常认为 d 0) /*有非零元素则转换*/n q=1; n for (col=1; coltu); p+)/*扫描整个三元组 表*/n if (T. datap.j=col ) n M. dataq.i= T. datap.j ;n M. dataq.j= T. datap.i ;nM. dataq.e= T. datap.e;nq+; n return ok; 时间复杂性为O(nu * tu) 38n(2) 快迅转置算法思路：n若能直接确定A中每一三元组在B中的位置，则对A的三元 组表扫描一次即可。n需引入两个向量来实现 ：numcol和cpotcol， numcol

10、表示矩阵A中第col列的非零元素的个数;ncpotcol初始值表示矩阵A中的第col列的第一个非零 元素在B.data中的位置。于是cpot的初始值为： cpot1=1； cpotcol=cpotcol-1+numcol-1； 2coln n依次扫描A.data，当扫描到一个col列元素时，直接将其 存放在B.data的cpotcol位置上，cpotcol加， cpotcol中始终是下一个col列元素在B.data中的位置 。 39nStatus FastTransposeSMatrix(TSMatrix M, TSMatrix T.nu = M.mu; T.tu = M.tu;nif (T.

11、tu) nfor (col=1; col| ei-1 ,ei D, 2in 46n基本操作： n结构的创建和销毁nInitGList( DestroyGList(nCreateGList( CopyGList(n状态函数nGListLength(L); GListDepth(L);nGListEmpty(L); GetHead(L); GetTail(L);n插入和删除操作nInsertFirst_GL(nDeleteFirst_GL(n遍历Traverse_GL(L, Visitn();n ADT GList47n例如：nD = (E, F) nE = (a, (b, c) nF = (d,

12、 (e) n n其它如：nA = ( )nB = (a, B) = (a, (a, (a, . , ) ) )nC = (A, D, F)n 48n例如：LS = ( A, D ) = ( ), ( E, F ) = ( ), (a, (b, c)，F )nHead(LS) = A Tail(LS) = ( D )nHead( D ) = E Tail( D ) = ( F )nHead( E ) = a Tail( E ) = ( ( b, c) )nHead( ( b, c) ) = ( b, c) nTail( ( b, c) ) = ( )nHead( ( b, c) ) = b nT

13、ail( ( b, c) ) = ( c )nHead( ( c ) ) = c nTail( ( c ) ) = ( ) 49n5.5 广义表的存储n通常都采用链式的存储结构来存储广义表。在这种 表示方式下，每个数据元素可用一个结点表示。n头尾链式存贮表示法n若广义表不空，则可分解成表头和表尾；则一对确 定的表头和表尾可惟一地确定一个广义表。n结点的结构形式有两种：一种是表结点，用以表示 列表；另一种是原子结点，用以表示单元素。n在表结点中应该包括指向表头的指针、指向表尾的 指针和标志域；而在元素结点中应该包括所表示单 元素的元素值和标志域。n如果标志为1，则表示该结点为表结点；如果标志为

14、0，则表示该结点为元素结点 50tag=1 hp tp tag=0 data（a）表结点 （b）元素结点头尾表示法的结点形式注：除空表的表头指针为空外，对任何非空列 表，其表头指针指向一个表结点 。该结点的hp 域指示列表表头(原子结点或表结点)，tp域指 示列表表尾(表尾为空，tp为空，否则为指示表 结点)51n其形式定义说明如下：ntypedef enum ATOM, LIST Elemtag; /*ATOM=0：单元素；LIST=1：子表*/ntypedef struct GLNode nElemtag tag; /*标志域，用于区分元素结点和表结点*/n union /*元素结点和表结点的联合部分*/n datatype data; /*data是元素结点的值域*/n struct n struct GLNode *hp, *tpn ptr; /*ptr是表结点的指针域，ptr.hp和n ptr.tp分别指向表头和表尾*/n ;n