数组和广义表教学.ppt

第五章 数组和广义表,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表,第五章 数组和广义表,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,数据对象：,数据关系：,数组的定义,数组的定义,二维数组的定义:,数据对象: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*,数组的定义,有两种顺序映象的方式:以行序为主序(低下标优先)以列序为主序(高下标优先),数组的顺序表示和实现,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 0i,jn-1则称A为对称矩阵。,矩阵的压缩存储,元素总数为:,n(n+1)/2,将这些元素存放在一个向量sa0.n(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)/2,矩阵的压缩存储,2、三角矩阵,以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。,矩阵的压缩存储,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中，,矩阵的压缩存储,3、3.对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。,矩阵的压缩存储,一个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)和矩阵维数（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 struct 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),矩阵的压缩存储,解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的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,矩阵的压缩存储,方法二：快速转置 即按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.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;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,矩阵的压缩存储,三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。,行逻辑联接的顺序表,链式存储结构带行指针向量的单链表表示每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空表头结点与单链表结点类型定义,矩阵的压缩存储,#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,矩阵的压缩存储,矩阵乘法的精典算法:for(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）的过程可大致描述如下：,矩阵的压缩存储,Status 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.rposarow;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=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时，相乘算法的时间复杂度就相当于(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=sc、若c=p-col，则修改p-vald、若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=31,1,32,2,52,3,44,1,82,1,7,矩阵的压缩存储,5.4 广义表的定义,广义表（Lists，又称列表）是线性表的推广。,广义表是n(n=0)个元素a1,a2,a3,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作:,广义表的定义,LS=（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);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,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),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,LIST 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,指向子表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,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 个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。,分治法的设计思想为:,广义表的递归函数,在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。,广义表的递归函数,例如:,梵塔问题: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),广义表的递归函数,广义表从结构上可以分解成,广义表=表头+表尾,或者,广义表=子表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,tag=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=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,广义表的递归函数,例二 复制广义表,新的广义表由新的表头和表尾构成。,可以直接求解的两种简单情况为：空表复制求得的新表自然也是空表;原子结点可以直接复制求得。,将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，,广义表的递归函数,若 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-ptr.hp的一个副本L-ptr.hpCopyGList(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 个子问题，即分别由这 n个子串(递归)建立 n 个子表，再组合成一个广义表。,可以直接求解的两种简单情况为：由串()建立的广义表是空表；由单字符建立的子表只是一个原子结点。,广义表的递归函数,如何由子表组合成一个广义表？,首先分析广义表和子表在存储结构中的关系。,先看第一个子表和广义表的关系:,1,L,指向广义表的头指针,指向第一个子表的头指针,广义表的递归函数,再看相邻两个子表之间的关系:,1,1,指向第i+1个子表的头指针,指向第i个子表的头指针,可见，两者之间通过表结点相链接。,广义表的递归函数,若 S=()则 L=NIL；否则，构造第一个表结点*L，并从串S中分解出第一个子串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=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.学习利用分治法的算法设计思想编制递归算法的方法。,第五章 数组和广义表,