数据结构数组和广义表市公开课一等奖百校联赛获奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第5章 数组和广义表（,Arrays&Lists,）,元素的值并非原子类型，可以再分解，表中元素也是壹种线性表（即广义的线性表）。,所有数据元素仍属同壹数据类型。,5.1 数组的定义,5.2 数组的次序表达和实現,5.3 矩阵的压缩存储,5.4 广义表的定义,5.5 广义表的存储构造,数组和广义表的特點：壹种特殊的线性表,1,5.1,数组的定义,数组：由壹组名字相似、下標不壹样的变量构成,注意：本章所讨论的数组与高级語言中的数组有所区别：高级語言中的数组是次序构造；而本章的数组既可以是次序的，也可以是链式构造，顾客可根据需要选择。,答：對的。由于：,数组中各元素具有统壹的类型；,数组元素的下標壹般具有固定的上界和下界，即数组壹旦被定义，它的维数和维界就不再变化。,数组的基本操作比较简朴，除了构造的初始化和销毁之外，只有存取元素和修改元素值的操作。,讨论：“数组的处理比其他复杂的构造要简朴”，對吗？,2,二维数组的特點：,壹维数组的特點：,1個下標，ai 是ai+1的直接前驱,2個下標，每個元素ai,j受到两個关系（行关系和列关系）的约束：,壹种mn的二维数组可以當作是m行的壹维数组，或者n列的壹维数组。,N维数组的特點：,n個下標，每個元素受到n個关系约束,壹种n维数组可以當作是由若干個n1维数组构成的线性表。,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,A,mn,=,3,N,维数组的数据类型定义,n_ARRAY=(,D,R,),其中：,Ri,=|,a,j1,j2,jijn,a,j1,j2,ji+1jn,D,i=2,n,数据关系：,R=,R1,R2，.Rn,数据對象：D=aj1,j2jn|ji為数组元素的第i 维下標，aj1,j2jn Elemset,数组的抽象数据类型定义略，参見教材P90,构造数组、销毁数组、讀数组元素、写数组元素,基本操作：,4,5.2 数组的次序存储表达和实現,問題：计算机的存储构造是壹维的，而数组壹般是多维的，怎样寄存？,处理措施：事先约定按某种次序将数组元素排成壹列序列，然後将這個线性序列存入存储器中。,例如：在二维数组中，我們既可以规定按行存储，也可以规定按列存储。,注意：,若规定好了次序，则数组中任意壹种元素的寄存地址便有规律可寻，可形成地址计算公式；,约定的次序不壹样，则计算元素地址的公式也有所不壹样；,C和PASCAL中壹般采用行优先次序；FORTRAN采用列优先。,5,补充：计算二维数组元素地址的通式设壹般的二维数组是Ac1.d1,c2.d2，這裏c1,c2不壹定是0。,無论规定行优先或列优先，只要懂得如下三要素便可随時求出任壹元素的地址（這样数组中的任壹元素便可以随机存取！）：,二维数组列优先存储的通式為：,LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L,a,c1,c2,a,c1,d2,a,ij,a,d1,c2,a,d1,d2,A,mn,=,單個元素長度,a,ij,之前的行数,数组基址,總列数，即第2维長度,aij本行前面的元素個数,開始結點的寄存地址（即基地址）,维数和每维的上、下界；,每個数组元素所占用的單元数,则行优先存储時的地址公式為：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L,6,例2：,已知二维数组,A,m,m,按行存储的元素地址公式是：Loc(a,ij,)=Loc(a,11,)+(i-1)*m+(j-1)*K,按列存储的公式是？,Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不壹样）,例1软考題：壹种二维数组A，行下標的范围是1到6，列下標的范围是0到7，每個数组元素用相邻的6個字节存储，存储器按字节编址。那么，這個数组的体积是 個字节。,288,例3：计算机系考研題设数组a160,170的基地址為2048，每個元素占2個存储單元，若以列序為主序次序存储，则元素a32,58的存储地址為 。,8950,LOC(,a,ij,)=LOC(a,c,1，,c,2,)+(,j-c,2,)*(,d,1,-c,1,+1)+,i-c,1,)*L,得：LOC(,a,32,58,)=2048+(58-1)*(60-1+1)+32-1)*28950,答：請注意审題！,运用列优先通式：,答：,Volume=m*n*L=(6-1,+1,)*(7-0,+1,)*6=48*6=288,7,Loc(j,1,j,2,j,n,)=LOC(0,0,0),若是N维数组，其中任壹元素的地址该怎样计算？,其中C,n,=L,C,i-1,=b,i,C,i，,1in,壹种元素長度,数组基址,前面若干元素占用的地址字节總数,第i维長度,与所存元素個数有关的系数，可用递推法求出,教材已給出低维优先的地址计算公式，見P93（5-2）式,该式称為n维数组的映像函数：,8,#define MAX_ARRAY_DIM 8 /假设最大维数為8,typedef struct,ELemType*base;/数组元素基址,int dim;/数组维数,int *bound;/数组各维長度信息保留区基址,int *constants;/数组映像函数常量的基址,Array;,即Ci信息保留区,数组的基本操作函数阐明（有5個）,（請阅讀教材P93-95）,N维数组的次序存储表达（見教材P93）,以销毁数组函数為例,9,Status InitArray(Array&A,int dim,),/若维数dim和各维長度合法，则构造對应的数组A并返回OK,if(dimMAX_ARRAY_DIM)return ERROR;,A.dim=dim;,A.bounds=(int*)malloc(dim*sizeof(int);,if(!a.bounds)exit(OVERFLOW);,/若各维長度合法，则存入A.bounds,并求出A的元素總数elemtotal,elemtotal=1;,va_start(ap.dim);/ap為va_list类型，是寄存变長参数表信息的类型,数组的基本操作函数阐明（5個）（見教材P93-95）,10,for(i=0;idim;+i),A.boundsi=va_arg(ap,int);,if(A.boundsi=0;-i),A.constantsi=A.boundsi+1*A.constantsi+1;,return OK;,11,数组基址指针,各维長度保留区指针,映像函数Ci保留区指针,Status,DestroyArray,(Array&A),/销毁数组A,if(!A.base )return ERROR;,free,(A.base );,A .base =NULL;,if(!A.bounds)return ERROR;,free,(A.bounds);,A.bounds=NULL;,if(!A.constants)return ERROR;,free,(A.constants);,A.constants=NULL;,return OK;,12,Status Locate(Array A,va_list ap,int&off),/若ap指示的各下標值合法，则求出该元素在A中，相對地址off,off=0;,for(i=0;iA.dim;+i),ind=va_arg(ap,int);,if(indA.boundsi)return OVERFLOW;,off+=A.constantsi*ind;,return OK;,13,Status Value(Array A,ElemType&e,),/A是n维数组，e為元素变量，随即是n個下標值，若各下標不超界，则e赋值為所指定的A的元素值，即将指定元素值讀到e变量中。,va_start(ap,e);,if(result=Locate(A,ap,off)=0)return result;,e=*(A.base+off);,return OK;,14,Status Assign(Array&A,ElemType e,),/A是n维数组，e為元素变量，随即是n個下標值，若各下標不超界，则e的值赋為所指定的A的元素值，即：将e值写入指定数组單元。,va_start(ap,e);,if(result=Locate(A,ap,off)=0)return result;,*(A.base+off)=e;,return OK;,15,次序存储方式：按低地址优先（或高地址优先）次序存入壹维数组。,行指针向量,a,11,a,12,a,1n,a,m1,a,m2,a,mn,补充：链式存储方式：用带行指针向量的單链表来表达。,注：数组的运算参見下壹节实例（稀疏矩阵的转置）,（难點是多维数组与壹维数组的地址映射关系）,16,5.3,矩阵的压缩存储,讨论：,1.什么是压缩存储？,若多种数据元素的值都相似，则只分派壹种元素值的存储空间，且零元素不占存储空间。,2.所有二维数组（矩阵）都能压缩吗？,未必，要看矩阵与否具有以上压缩条件。,3.什么样的矩阵具有以上压缩条件？,某些特殊矩阵，如：對称矩阵，對角矩阵，三角矩阵，稀疏矩阵等。,4.什么叫稀疏矩阵？,矩阵中非零元素的個数较少（壹般不不小于5%）,重點简介稀疏矩阵的压缩和對应的操作。,17,壹、稀疏矩阵的压缩存储,問題：,假如只存储稀疏矩阵中的非零元素，那這些元素的位置信息该怎样表达？,处理思绪：,對每個非零元素增開若干存储單元，例如寄存其所在的行号和列号，便可精确反应當元素所在位置。,实現措施：,将每個非零元素用壹种三元组（i，j，aij）来表达，则每個稀疏矩阵可用壹种三元组表来表达。,二、,稀疏矩阵的操作,18,例1：,三元素组表中的每個結點對应于稀疏矩阵的壹种非零元素，它包具有三個数据项，分别表达该元素的 、和 。,行下標,列下標,元素值,例2：,写出右图所示稀疏矩阵的压缩存储形式。,0,12 9 0 0 0,0,0 0 0 0 0,-3 0 0 0 14 0,0,0 24 0 0 0,0,18 0 0 0 0,15,0 0 -7 0 0,(,(1,2,12),，(1,3,9)，(3,1,-3)，(3,5,14)，,(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7),),法1：用线性表表达：,0,12 9,0 0 0,0,0 0 0 0 0,-3,0 0 0,14,0,0,0,24,0 0 0,0,18,0 0 0 0,15,0 0,-7,0 0,19,法2：用三元组矩阵表达：,0,12 9,0 0 0,0,0 0 0 0 0,-3,0 0 0,14,0,0,0,24,0 0 0,0,18,0 0 0 0,15,0 0,-7,0 0,1,2,12,1,3,9,3,1,-3,3,5,14,4,3,24,5,2,18,6,1,15,6,4,-7,注意：為更可靠描述，壹般再加壹行“總体”信息：即總行数、總列数、非零元素總個数,6,6,8,i,j,value,稀疏矩阵压缩存储的缺陷：将失去随机存取功能 :-(,0,1,2,3,4,5,6,7,8,20,法三：用带辅助向量的三元组表达。,措施：增長2個辅助向量：,记录每行非0元素個数，用NUM（i）表达；,记录稀疏矩阵中每行第壹种非0元素在三元组中的行号，用POS（i）表达。,7,6,5,3,1,2,1,1,2,0,2,NUM(,i,),6,5,4,3,POS(,i,),2,1,i,0,12,9,0 0 0,0,0 0 0 0 0,-3,0 0 0,14,0,0,0,24,0 0 0,0,18,0 0 0 0,15,0 0,-7,0 0,-7,4,6,15,1,6,18,2,5,24,3,4,14,5,3,-3,1,3,9,3,1,12,2,1,8,6,6,v,j,i,0,1,2,3,4,5,6,7,8,3,用途：通過三元组高效访問稀疏矩阵中任壹非零元素。,规律：,POS(1),1,POS(i)POS(i-1)+NUM(i-1),21,法四：用拾字链表表达,用途：以便稀疏矩阵的加減运算；,措施：每個非0元素占用5個域。,right,down,v,j,i,同壹列中下壹非零元素的指针,同壹行中下壹非零元素的指针,拾字链表的特點：,每行非零元素链接成带表頭結點的循环链表；,每列非零元素也链接成带表頭結點的循环链表。,则每個非零元素既是行循环链表中的壹种結點；又是列循环链表中的壹种結點，即呈拾字链状。,以刚刚的稀疏矩阵為例：,12,2,1,0,0,H1,9,3,1,18,2,5,22,#define MAXSIZE 125000 /设非零元素最大個数125000,typedef struct,int i;/元素行号,int j;/元素列号,ElemType e;/元素值,Triple;,typedef struct,Triple dataMAXSIZE+1;/三元组表，以行為主序存入壹维向量 data 中,int mu;/矩阵總行数,int nu;/矩阵總列数,int tu;/矩阵中非零元素總個数,TsMatrix;,三元组表的次序存储表达（見教材P98）：,/壹种結點的构造定义,/整個三元组表的定义,23,二、,稀疏矩阵的操作,0,12,9,0 0 0,0,0 0 0 0 0,-3,0 0 0,14,0,0,0,24,0 0 0,0,18,0 0 0 0,15,0 0,-7,0 0,0,0,3,0 0,15,12,0 0 0,18,0,9,0 0,24,0 0,0,0 0 0 0,-7,0,0,14,0 0 0,0,0 0 0 0 0,(,1,2,12,),(,1,3,9,),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7),(1,3,-3),(1,6,15),(,2,1,12,),(2,5,18),(,3,1,9,),(3,4,24),(4,6,-7),(5,3,14),三,元,组,表,a.data,三,元,组,表,b.data,转置后,M,T,（以转置运算為例）,目的：,24,答：肯定不對的！,除了：（1）每個元素的行下標和列下標互换（即三元组中的i和j互换）；,還应當：（2）T的總行数mu和總列数nu与M值不壹样（互换）；,（3）重排三元组内元素次序，使转置後的三元组也按行（或列）為主序有规律的排列。,上述（1）和（2）轻易实現，难點在（3）。,若采用三元组压缩技术存储稀疏矩阵，只要把每個元素的行下標和列下標互换，就完毕了對该矩阵的转置运算，這种說法對的吗？,有两种实現措施,压缩转置,(压缩)迅速转置,提問：,25,措施1：压缩转置,思绪：反复扫描a.data中的列序，從小到大依次進行转置。,三,元,组,表,a.data,三,元,组,表,b.data,(,1,3,-3),(,1,6,15),(,2,1,12),(,2,5,18),(3,1,9),(3,4,24),(4,6,-7),(5,3,14),(1,2,12),(1,3,9),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7),1,1,2,2,col,q,1,2,3,4,p,1,2,3,4,26,Status,TransPoseSMatrix,(TSMatrix,M,TSMatrix,&T,),T.mu,=M.nu;,T.nu,=M.mu;,T.tu,=M.tu;,if(T.tu),q=1,;,for(,col=1,;col=,M.nu,;col+),for(,p=1,;p=,M.tu,;p+),if(M.datap.j=,col,),T.data,q,.i,=M.datap.j;T.data,q,.j,=M.datap.i;,T.data,q,.value,=M.datap.value;,q+,;,return OK;,/TranposeSMatrix;,压缩转置算法描述：（見教材P99）,/用三元组表寄存稀疏矩阵M，求M的转置矩阵T,/q是转置矩阵T的結點编号,/,col,是扫描M三元表列序的变量,/p是M三元表中結點编号,27,1、重要時间消耗在查找M.datap.j=col的元素，由两重循环完毕:for(col=1;col=M.nu;col+)循环次数nu,for(p=1;p=M.tu;p+)循环次数tu,因此该算法的時间复杂度為O(nu*tu),-即M的列数与M中非零元素的個数之积,最惡劣状况：M中全是非零元素，此時tu=mu*nu，,時间复杂度為 O(nu2*mu),注：若M中基本上是非零元素時，虽然用非压缩老式转置算法的時间复杂度也不過是O(nu*mu)（程序見教材P99）,結论：压缩转置算法不能滥用。,前提：仅合用于非零元素個数很少（即tumu*nu）的状况。,压缩转置算法的效率分析,：,28,措施2 迅速转置,三,元,组,表,a.data,三,元,组,表,b.data,(1,3,-3),(,2,1,12,),(2,5,18),(,3,1,9,),(4,6,-7),(5,3,14),(1,6,15),(3,4,24),(,1,2,12,),(,1,3,9,),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7),思绪：依次把a.data中的元素直接送入b.data的恰當位置上（即M三元组的p指针不回溯）。,关键：怎样寻找b.data的“恰當”位置？,p,1,2,3,4,q,3,5,29,假如能预知M矩阵每壹列(即T的每壹行)的非零元素個数，又能预知第壹种非零元素在b.data中的位置,则扫描a.data時便可以将每個元素精确定位（由于已知若干参照點）。,技巧：运用带辅助向量的三元组表，它恰好携带每行（或列）的非零元素個数 NUM(i)以及每行（或列）的第壹种非零元素在三元组表中的位置POS(i)等信息。,设计思绪：,i,1,2,3,4,5,6,NUM(,i,),2,0,2,1,1,2,POS(,i,),1,3,3,5,6,7,不過我們需要的是按列生成的M矩阵的辅助向量。,规律：,POS(1),1,POS(i)POS(i-1)+NUM(i-1),請回忆：,請注意a.data特性：每列首個非零元素必然先被扫描到。,30,令：M中的列变量用col表达；num col：寄存M中第col 列中非0元素個数，cpot col：寄存M中第col列的第壹种非0元素的位置，（即b.data中待计算的“恰當”位置所需参照點）,讨论：按列优先的辅助向量求出後，下壹步该怎样操作？,由a.data中每個元素的列信息，即可直接查出b.data中的重要参照點之位置，進而可确定目前元素之位置！,col,1,2,3,4,5,6,numcol,2,2,2,1,1,0,cpotcol,1,规律：,cpot,(1),1,cpotcol,cpotcol-1,+,numcol-1,0,12,9,0 0 0,0,0 0 0 0 0,-3,0 0 0,14,0,0,0,24,0 0 0,0,18,0 0 0 0,15,0 0,-7,0 0,M,3 5 7 8 8,col 1 2 3 4 5 6,31,Status,FastTransposeSMatrix,（TSMatirx M,TSMatirx,&T,）,T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;,if(T.tu),for(col=1;col=M.nu;col+)numcol=0;,for(i=1;i=M.tu;i+)col=M.data i .j;+num col;,cpos 1 =1;,for(col=2;col=M.nu;col+)cposcol=cposcol-1+num col-1 ;,for(,p,=1;,p,=M.tu;,p,+),col,=M.data,p,.,j,;,q,=cpos,col,;,T.dataq.i=M.datap.j;,T.dataq.j=M.datap.i;,T.dataq.value=M.datap.value;,+cposcol;,/for,/if,return OK;,/FastTranposeSMatrix,;,迅速转置算法描述：,/M用次序存储表达，求M的转置矩阵T,/先记录每列非零元素個数,/再生成每列首元位置辅助向量表,/p指向a.data，循环次数為非0元素總個数tu,/查辅助向量表得,q,，即T中位置,/重要語句！修改向量表中列坐標值，供同壹列下壹非零元素定位之用！,32,1.与常规算法相比，附加了生成辅助向量表的工作。增開了2個長度為列長的数组(num 和cpos）。,老式转置：O(mu*nu)压缩转置：O(mu*tu),压缩迅速转置：O(nu+tu)牺牲空间效率换時间效率。,迅速转置算法的效率分析：,2.從時间上，此算法用了4個并列的單循环，并且其中前3個單循环都是用来产生辅助向量表的。,for(col=1;col=M.nu;col+)循环次数nu;,for(i=1;i=M.tu;i+)循环次数tu;,for(col=2;col=M.nu;col+)循环次数nu;,for(p=1;p=M.tu;p+)循环次数tu;,该算法的時间复杂度(nu*2)+(tu*2)=O(nu+tu）,讨论：最惡劣状况是tu=nu*mu(即矩阵中所有是非零元素），,而此時的時间复杂度也只是O(mu*nu)，并未超過老式转置算法的時间复杂度。,小結：,稀疏矩阵相乘的算法見教材P101-103,33,三、拾字链表,3 0 0 5,0-1 0 0,2 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,34,5.4 广义表的定义,广义表是线性表的推广，也称為列表（lists）,记為：LS =(a1,a2,，an),广义表名 表頭(Head）表尾(Tail),1、定义：,第壹种元素是表頭，而其他元素构成的表称為表尾；,用小写字母表达原子类型，用大写字母表达列表。,n是表長,在广义表中约定：,讨论：广义表与线性表的区别和联络？,广义表中元素既可以是原子类型，也可以是列表；,當每個元素都為原子且类型相似時，就是线性表。,35,广义表是递归定义的线性构造，,LS=(1,2,n),其中：i 或為原子 或為广义表,例如:,A=(),F=(d,(e),D=(a,(b,c),F),C=(A,D,F),B=(a,B)=(a,(a,(a,),36,广义表 LS=(1,2,n)的构造特點:,1)广义表中的数据元素有相對次序;,2)广义表的長度定义為最外层包括元素個数;,3)广义表的深度定义為所含括弧的重数;,注意:“原子”的深度為 0;,“空表”的深度為 1。,4)广义表可以,共享,;,5)广义表可以是壹种递归的表;,递归表的深度是無穷值，長度是有限值。,37,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),)=,(),38,E=(a,E)=(a,(a,E)=(a,(a,(a,.)，E為递归表,1）A=(),2）B=(e),3）C=(a,(b,c,d),4）D=(A,B,C),5）E=(a,E),例1：求下列广义表的長度。,n=0，由于A是空表,n=1，表中元素e是原子,n=2，a 為原子，(b,c,d)為子表,n=3，3個元素都是子表,n=2，a 為原子，E為子表,D=(A,B,C)=(),(e),(a,(b,c,d)，,共享表,39,A,B,D,C,e,a,b,c,d,A=(a,(b,A),例2：试用图形表达下列广义表.,（设 代表原子，代表子表）,e,D=(A,B,C)=(),(e),(a,(b,c,d),A,a,b,的長度為3，深度為3,的長度為2，深度為,深度括号的重数 结点的层数,40,广义表是壹种多层次的线性构造,例如：,D=(,E,F,),其中:,E=(,a,(,b,c,),),F=(,d,(,e,),),D,E,F,a,(),d,(),b,c,e,41,5.4,广义表的类型定义,ADT Glist,数据對象：Dei|i=1,2,.,n;n0;,eiAtomSet 或 eiGList,AtomSet為某個数据對象 ,数据关系：,LR|ei-1,eiD,2in,ADT Glist,基本操作:,42,构造的创立和销毁,InitGList(,CreateGList(,基本操作,状态函数,GListLength(L);GListDepth(L);,GListEmpty(L);GetHead(L);GetTail(L);,插入和删除操作,InsertFirst_GL(,&,L,e);,DeleteFirst_GL(,&,L,&,e);,遍历,Traverse_GL(L,Visit();,43,简介两种特殊的基本操作：,GetHead(L)取表頭(也許是原子或列表);,GetTail(L)取表尾(壹定是列表)。,广义表的抽象数据类型定义見教材P107-108,44,1.GetTail【(b,k,p,h)】,;,2.GetHead【(a,b),(c,d)】,;,3.GetTail【(a,b),(c,d)】,;,4.GetTail【GetHead【(a,b),(c,d)】,;,例：求下列广义表操作的成果（严題集5.10）,(k,p,h),（b）,(a,b),5.GetTail【（e）】,;,6.GetHead【()】,.,7.GetTail【()】,.,(),(c,d),(),(),(c,d),45,5.5 广义表的存储构造,由于广义表的元素可以是不壹样构造（原子或列表），难以用次序存储构造表达，壹般用链式构造，每個元素用壹种結點表达。,1.原子結點：表达原子，可设2個域或3個域，依习惯而选。,value,tag=0,标志域 数值域,注意：列表的“元素”還可以是列表，因此結點也許有两种形式,tp,atom,tag=,标志域 值域表尾指针,法2：標志域、值域、表尾指针,指向下壹結點,法1：標志域，数值域,46,tp,hp,tag=1,标志域 表头指针 表尾指针,2.表結點：表达列表，若表不空，则可分解為表頭和表尾，用3個域表达：標志域，表頭指针，表尾指针。,A=(),1,0,e,C=(a,(b,c,d),1,1,1,0,a,0,b,0,d,0,c,1,1,例：,B=(e),A=NULL,指向子表,指向下壹結點,1,47,E=(a,E),D=(A,B,C),(),(e),(a,(b,c,d),0,a,1,1,1,0,e,1,1,1,1,1,0,a,0,b,0,d,0,c,1,1,1,（参見教材P109图）,48,1)表頭、表尾分析法:,构造存储构造的两种分析措施:,若表頭為原子，则為,空表,ls=NIL,非空表,ls,tag=1,指向表頭的指针,指向表尾的指针,tag=0 data,否则，依次类推。,49,广义表的表达措施,壹般采用頭、尾指针的链表构造,表結點:,原子結點：,tag=0 data,tag=1,hp,tp,50,51,L=(a,(x,y),(x),a,(x,y),(,),1,L,L=(),0 a,1,1,1,1,1,0 x,(),x,52,1,1,1,ls,2)子表分析法:,若子表為原子，则為,空表,ls=NIL,非空表,指向子表1,的指针,tag=0 data,否则，依次类推。,指向子表2,的指针,指向子表n,的指针,53,例如:,ls,(x),LS=(a,(x,y),(x),a,(x,y),54,广义表從构造上可以分解成,广义表=表頭+表尾,或者,广义表=子表,1+子表2+子表n,因此常运用分治法求解之。,算法设计中的关键問題是，怎样将 l 個子問題的解组合成原問題的解。,55,广义表的頭尾链表存储表达：,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,表結點,56,理解数组的两种存储表达措施，并掌握数组在以行為主的存储构造中的地址计算措施。,掌握對特殊矩阵進行压缩存储時的下標变换公式。,理解稀疏矩阵的两类压缩存储措施的特點和合用范围，领會以三元组表达稀疏矩阵時進行矩阵运算采用的处理措施。,掌握广义表的构造特點及其存储表达措施，讀者可根据自已的习惯纯熟掌握任意壹种构造的链表，學會對非空广义表進行分解的两种分析措施：即可将壹种非空广义表分解為表頭和表尾两部分或者分解為n個子表。,57,