第五部分数组和广义表教学课件.ppt

《第五部分数组和广义表教学课件.ppt》由会员分享，可在线阅读，更多相关《第五部分数组和广义表教学课件.ppt（83页珍藏版）》请在三一文库上搜索。

1、第五章 数组和广义表,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表,第五章 数组和广义表,5.1 数组的定义,5.3 矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的定义,5.5 广义表的存储结构,5.6 m元多项式的表示,5.7 广义表的递归算法,第五章 数组和广义表,5.1 数组的定义,数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值,aj = (a0j,a1j, , am-1j),ai = (ai0,ai1, , ain-1),数组的定义,抽象数据类型数组的定义如下：,ADT List

2、,数据对象：,数据关系：,数组的定义,数组的定义,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,InitArray(&A, n, bound1, ., boundn),DestroyArray(&A),Value(A, &e, index1, ., indexn),Assign(&A, e, index1, ., indexn),基本操作：,数组的定义,=,m*,数组的定义,有两种顺序映象的方式: 以行序为主序(低下标优先) 以

3、列序为主序(高下标优先),数组的顺序表示和实现,5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。,Loc( aij)=Loc(a00)+i*n+j*l,按行序为主序存放,数组的顺序表示和实现,按列序为主序存放,Loc(aij)=Loc(a00)+j*m+i*l,数组的顺序表示和实现,4.3 矩阵的压缩存储,特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。,1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji

4、0i,jn-1 则称A为对称矩阵。,矩阵的压缩存储,元素总数为:,n(n+1)/2,将这些元素存放在一个向量sa0n(n+1)/2-1中,矩阵的压缩存储,aij和sak之间对应关系,ij 则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2,矩阵的压缩存储,ij 则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)

5、/2,矩阵的压缩存储,2、三角矩阵,以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。,矩阵的压缩存储,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0n(n+1)/2中，其中c存放在向量的最后一个分量中，,矩阵的压缩存储,3、3.对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。,矩阵

6、的压缩存储,一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,Loc(aij)=Loc(a11)+2(i-1)+(j-1),矩阵的压缩存储,假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,稀疏矩阵,矩阵的压缩存储,M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维

7、数（6,7）唯一确定,定义：非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,矩阵的压缩存储,稀疏矩阵的压缩存储方法:,一、三元组顺序表,二、行逻辑联接的顺序表,三、 十字链表,矩阵的压缩存储,三元组表所需存储单元个数为3(t+1) 其中t为非零元个数,6 7 8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,ma0.i,ma0.j,ma0.v分别存放 矩阵行列维数和非零元个数,三元组顺序表,矩阵的压缩存储,#define MAXSIZE 12500 typedef struc

8、t int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型,矩阵的压缩存储,求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 一般矩阵转置算法：,for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=mrowcol; T(n)=O(mn),矩阵的压缩存储,其时间复杂度为: O(munu),矩阵的压缩存储

9、,解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使mb中元素以N的行(M的列)为主序,方法一：按M的列序转置 即按mb中三元组次序依次在ma中找到相应的三元组进行转置。 为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序,矩阵的压缩存储,算法分析：T(n)=O(M的列数n非零元个数t) 若 t 与mn同数量级，则,矩阵的压缩存储,7 6 8,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,

10、矩阵的压缩存储,方法二：快速转置 即按ma中三元组次序转置，转置结果放入b中恰当位置 此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数,实现：设两个数组 numcol：表示矩阵M中第col列中非零元个数 cpotcol：指示M中第col列第一个非零元在mb中位置 显然有：,矩阵的压缩存储,1,3,5,7,8,8,9,Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) / FastTransposeSMatrix,矩阵的压缩存储,T.mu = M.nu; T.nu = M.mu; T

11、.tu = M.tu; if (T.tu) / if return OK;,for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) ,分析算法FastTransposeSMatrix的时间复杂度：,时间复杂度为: O(M.nu+M.tu),for (col=1; col=M.nu; +col) for (t=1;

12、t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) ,矩阵的压缩存储,7 6 8,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,矩阵的压缩存储,三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。,行逻辑联接的顺序表,链式存储结构 带行指针向量的单链表表示 每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个

13、非零元结点；若本行无非零元，则指针为空 表头结点与单链表结点类型定义,矩阵的压缩存储,#define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型,需存储单元个数为3t+m,矩阵的压缩存储,例如：给定一组下标，求矩阵的元素值,ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while (M.datap.i=r / value,矩阵的压缩存储,矩阵乘法的精典算法: f

14、or (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; ,其时间复杂度为: O(m1n2n1),矩阵的压缩存储,Q初始化； if Q是非零矩阵 / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if,两个稀疏矩阵相乘（QMN） 的过程可大致描述如下：,矩阵的压缩存储,Statu

15、s MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) / MultSMatrix,矩阵的压缩存储,if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 / for arow / if return OK;,ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rpo

16、sarow; pM.rposarow+1;+p) /对当前行中每一个非零元 / 求得Q中第crow( =arow)行的非零元,处理 的每一行,M,矩阵的压缩存储,brow=M.datap.j; if (brow N.nu ) t = N.rposbrow+1; else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q,for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu

17、 = arow, ccol, ctempccol; / if,矩阵的压缩存储,分析上述算法的时间复杂度,累加器ctemp初始化的时间复杂度为 (M.muN.nu) 求Q的所有非零元的时间复杂度为 (M.tuN.tu/N.mu) 进行压缩存储的时间复杂度为 (M.muN.nu) 总的时间复杂度就是 (M.muN.nu+M.tuN.tu/N.mu)。,矩阵的压缩存储,若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu = Mmn N中非零元的个数 N.tu = Nnp 相乘算法的时间复杂度就是 (mp(1+nMN) 当M0.05 和N0.05及 n 1000时， 相乘算

18、法的时间复杂度就相当于 (mp)。,矩阵的压缩存储,十字链表 设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义,tpedef struct node int row,col,val; struct node *down, *right; JD;,矩阵的压缩存储,算法分析： T(n)=o(ts) 其中：t非零元个数 s= max(m,n),令q=NULL,p=rhr-1, （1）寻找插入位置：当p!=NULL且cp-col时，p和q右移 （2）插入： a、若p=NULL且q=NULL，即本行空，则rhr-1=s; b、若p=NULL,q!=NULL，即走到行末，则q-right=

19、s c、若c=p-col，则修改p-val d、若ccol且q=NULL，则在p之前插入s，即s是行链表中 第一个结点，令rhr-1=s; s-right=p; e、若ccol且q!=NULL，则在p之前插入s， 即 s-right=p; q-right=s;,从键盘接收信息建立十字链表算法,矩阵的压缩存储,m=4,n=3 1,1,3 2,2,5 2,3,4 4,1,8 2,1,7,矩阵的压缩存储,5.4 广义表的定义,广义表（Lists，又称列表）是线性表的推广。,广义表是n(n=0)个元素a1,a2,a3,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作:,广义表的定义,L

20、S=（a1,a2,a3,an),LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。 若广义表LS（n=1)非空，则a1是LS的表头，其余元素组成的表(a1,a2,an)称为LS的表尾。表尾,ADT Glist 数据对象：Dei | i=1,2,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系： LR| ei-1 ,eiD, 2in,广义表的定义, ADT Glist, 结构的创建和销毁 InitGList(, 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L

21、); GetTail(L);, 插入和删除操作 InsertFirst_GL(, 遍历 Traverse_GL(L, Visit();,基本操作：,广义表的定义,广义表是递归定义的线性结构，,LS = ( 1, 2, , n ) 其中：i 或为原子 或为广义表,例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ),广义表的定义,广义表是一个多层次的线性结构,例如：,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b

22、,c,e,广义表的定义,广义表 LS = ( 1, 2, , n )的结构特点:,1) 广义表中的数据元素有相对次序；,2) 广义表的长度定义为最外层包含元素个数；,3) 广义表的深度定义为所含括弧的重数； 注意：“原子”的深度为 0 “空表”的深度为 1,4) 广义表可以共享；,5) 广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。,6) 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 两部分。,广义表的定义,例如: D = ( E, F ) = (a, (b, c)，F

23、),Head( D ) = E Tail( D ) = ( F ),Head( E ) = a Tail( E ) = ( ( b, c) ),Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( ),Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ),Head( ( c ) ) = c Tail( ( c ) ) = ( ),广义表的定义,5.5 广义表的存储结构,通常采用头、尾指针的链表结构,表结点: 原子结点：,tag=1 hp tp,tag=0 atom,广义表的存储结构,typedef enum ATOM,LI

24、ST ElemTag; / ATOM = 0:原子，LIST=1：子表,广义表的存储结构,typedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode *hp,*top ptr; ; *Glist;,1) 表头、表尾分析法：,构造存储结构的两种分析方法:,若表头为原子，则为,空表 ls=NIL,非空表 ls,tag=1,指向表头的指针,指向表尾的指针,tag=0 atom,否则，依次类推。,广义表的存储结构,广义表的存储结构,2) 子表分析法：,若子表为原子，则为,空表 ls=NIL,非空表,1,指向子

25、表1 的指针,tag=0 data,否则，依次类推。,1,指向子表2 的指针,1,指向子表n 的指针,ls,广义表的存储结构,例如:,a (x, y) (x),LS=( a, (x,y), (x) ),ls,广义表的存储结构,5.7 广义表的递归函数,递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：,1)在每一次调用自己时，必须是(在某 种意义上)更接近于解;,2)必须有一个终止处理或计算的准则。,广义表的递归函数,例如: 梵塔的递归函数,void hanoi (int n, char x, char y, char z) if (n=1) move(x

26、, 1, z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); ,广义表的递归函数,如何设计递归函数？,二、后置递归法(Postponing the work),三、回溯法(Backtracking),一、分治法 (Divide and Conquer) (又称分割求解法),广义表的递归函数,对于一个输入规模为 n 的函数或问题， 用某种方法把输入分割成 k(1kn)个子集， 从而产生 l 个子问题，分别求解这 l 个问题， 得出 l 个问题的子解，再用某种方法把它们 组合成原来问题的解。若子问题还相当大， 则可以反

27、复使用分治法，直至最后所分得 的子问题足够小，以至可以直接求解为止。,分治法的设计思想为:,广义表的递归函数,在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。,广义表的递归函数,例如:,梵塔问题: Hanoi(n, x, y, z),可递归求解 Hanoi(n-1, x, z, y),将 n 个盘分成两个子集(1至n-1 和 n )，从而产生下列三个子问题：,1) 将1至n-1号盘从 x 轴移动至 y 轴；,3) 将1至n-1号盘从y轴移动至z轴；,2) 将 n号盘从 x 轴移动至 z 轴；,可递归求解 Hanoi(n-1, x, z, y),广义表的递归函数,

28、广义表从结构上可以分解成,广义表 = 表头 + 表尾,或者,广义表 = 子表1 + 子表2 + + 子表n,因此常利用分治法求解之。 算法设计中的关键问题是，如何将 l 个子问题的解组合成原问题的解。,广义表的递归函数,广义表的头尾链表存储表示：,typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表 typedef struct GLNode ElemTag tag; / 标志域 union AtomType atom; / 原子结点的数据域 struct struct GLNode *hp, *tp; ptr; ; *GList,ta

29、g=1,hp tp,ptr,表结点,广义表的递归函数,例一 求广义表的深度,例二 复制广义表,例三 建立广义表的存储结构,广义表的递归函数,广义表的深度=Max 子表的深度 +1,例一 求广义表的深度,可以直接求解的两种简单情况为： 空表的深度 = 1 原子的深度 = 0,将广义表分解成 n 个子表，分别(递归)求得每个子表的深度，,广义表的递归函数,int GlistDepth(Glist L) / 返回指针L所指的广义表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max

30、= dep; return max + 1; / GlistDepth,if (!L) return 1; if (L-tag = ATOM) return 0;,广义表的递归函数,1,1,1,L,for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; ,例如:,pp,pp-ptr.hp,pp,pp,pp-ptr.hp,广义表的递归函数,例二 复制广义表,新的广义表由新的表头和表尾构成。,可以直接求解的两种简单情况为： 空表复制求得的新表自然也是空表; 原子结点可以直接复制

31、求得。,将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，,广义表的递归函数,若 ls= NIL 则 newls = NIL 否则 构造结点 newls, 由 表头ls-ptr.hp 复制得 newhp 由 表尾 ls-ptr.tp 复制得 newtp 并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp,复制求广义表的算法描述如下:,广义表的递归函数,Status CopyGList(Glist / CopyGList,分别复制表头和表尾,广义表的递归函数,CopyGList(T-ptr.hp, L-ptr.hp); / 复制求得表头T

32、-ptr.hp的一个副本L-ptr.hp CopyGList(T-ptr.tp, L-ptr.tp); / 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp,语句 CopyGList(T-ptr.hp, L-ptr.hp); 等价于 CopyGList(newhp, L-ptr.tp); T-ptr.hp = newhp;,广义表的递归函数,例三 创建广义表的存储结构,对应广义表的不同定义方法相应地有不同的创建存储结构的算法。,假设以字符串 S = (1, 2, , n ) 的形式定义广义表 L，建立相应的存储结构。,由于S中的每个子串i定义 L 的一个子表，从而产生 n 个子问题，即

33、分别由这 n个子串 (递归)建立 n 个子表，再组合成一个广义表。,可以直接求解的两种简单情况为： 由串( )建立的广义表是空表； 由单字符建立的子表只是一个原子结点。,广义表的递归函数,如何由子表组合成一个广义表？,首先分析广义表和子表在存储结构中的关系。,先看第一个子表和广义表的关系:,1,L,指向广义表 的头指针,指向第一个 子表的头指针,广义表的递归函数,再看相邻两个子表之间的关系:,1,1,指向第i+1个 子表的头指针,指向第i个 子表的头指针,可见，两者之间通过表结点相链接。,广义表的递归函数,若 S = ( ) 则 L = NIL； 否则，构造第一个表结点 *L， 并从串S中分解

34、出第一个子串1，对应创建第一个子广义表 L-ptr.hp； 若剩余串非空，则构造第二个表结点 L-ptr.tp，并从串S中分解出第二个子串 2，对应创建第二个子广义表 ； 依次类推，直至剩余串为空串止。,广义表的递归函数,void CreateGList(Glist /脱去串S的外层括弧 / else ,由sub中所含n个子串建立n个子表;,广义表的递归函数,do sever(sub, hsub); / 分离出子表串hsub=i if (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode); / 建下一个子表的表结点*(p-ptr.tp) p

35、=p-ptr.tp; while (!StrEmpty(sub); p-ptr.tp = NULL; / 表尾为空表,创建由串hsub定义的广义表p-ptr.hp;,广义表的递归函数,if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub; / 创建单原子结点 else CreateGList(p-ptr.hp, hsub); /递归建广义表,广义表的递归函数,本章小结,1. 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。,2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。,3. 了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。,4. 掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。,5. 学习利用分治法的算法设计思想编制递归算法的方法。,第五章 数组和广义表,