数据结构数组和广义表幻灯片.ppt

数据结构数组和广义表1第1页，共33页，编辑于2022年，星期六数组描述设二维数组设二维数组:其中其中:m、n为行列数为行列数,aij为第为第i行、第行、第j列的元素列的元素,0im-1,0jn-1;元素个数为元素个数为mn。二维数组可用形式化语言描述，即：二维数组可用形式化语言描述，即：A(2)=(D,R)其中：其中：D=aij|aijdatatype,0im-1,0jn-1;R=Row,Col行关系：行关系：Row=|aij,aij+1D,0im-1,0jn-2列关系：列关系：Col=|aij,ai+1jD,0im-2,0jn-1a00 a01 a0j a0n-1.ai0 ai1 aij.ain-1.am-10 am-11 am-1j am-1n-1A(2)=Amn=2第2页，共33页，编辑于2022年，星期六数组描述关关系系集集Row和和Col表表明明：除除数数组组A(2)周周边边元元素素外外的的其其它它任任一一个个元元素素aij，有有两两个个直直接接前前驱驱ai-1j，aij-1,和和两两个个直直接接后后继继ai+1j，aij+1(周周边边元元素素的的前前驱驱或或后后继继可可不不足足两两个个)。n维数组也可按上述方法类似定义。维数组也可按上述方法类似定义。二维数组可如下描述二维数组可如下描述:多维数组是线性表的推广，而线性表是多维数组的特例。A0 Ai Am-1=(A0Ai.Am-1)-线性表形式线性表形式a00 a01 a0j a0n-1.ai0 ai1 aij.ain-1.am-10 am-11 am-1j am-1n-1A(2)=Amn=3第3页，共33页，编辑于2022年，星期六5.1.1数组的抽象数据类型 在算法语言中，数组一旦生成，其元素的存储空间就固定下来，故数组的运算一般不包括插入和删除这样的操作。ADT Array D=aj1j2jn|aj1j2jndatatype，ji=0,bi-1其中i=1,2,n n(n0)为数组维数，bi是第i维长度，ji是数组元素第i维下标。R=R1,R2,Rn其中：Ri=|0jkbk-1，1kn且ki，0jibi-2，aj1jijn,aj1ji+1jnD，i=1,2,n P ArrayInit(&A,n,d1，d2,.dn)操作结果：若维数n和各维长度合法，则生成一个n维数组Ad1d2.dn（C语言中，1n8）。ArrayDestroy(&A)初始条件：数组A存在。操作结果：撤销数组A。ArrayGet(A,i1,.,in,&e)初始条件：数组A存在，edatatype。操作结果：若各下标合法，则将元素Ai1i2,.,in的值传给变量 e。4第4页，共33页，编辑于2022年，星期六数组的抽象数据类型ArrayAssign(&A,i1,.,in,e)初始条件：数组A存在，edatatype。操作结果：若各下标合法，则将变量 e的值传给数组元素Ai1i2,.,in。ADT Array；5.2数组的存储结构数组的存储结构 由于计算机的存储空间是一维的（或线性的），所以存储数组时，要将多维数组中的元素按某种次序映象到一维存储空间，即解决“降维”问题。5.2.1数组的静态存储方式数组的静态存储方式1数组的静态存储映像数组的静态存储映像 在PASCAL和C等语言中，是按低维下标优先变化（或按行优先）的方式，存储数组中的元素。如在C语言中，二维数组的映像如图5.1所示。但在FORTRAN语言中，数组元素是按高维下标优先变化或按列优先方式，存储数组中的元素。5第5页，共33页，编辑于2022年，星期六数组的存储映像 a00a0,n-1ai0ai,n-1am-1,n-1映像映像 （存储器）存储器）a00 a01 a0j a0n-1.ai0 ai1 aij.ain-1.am-10 am-11 am-1j am-1n-1 Amn=图图5.1思考：思考：1.三维以上数组如何映像三维以上数组如何映像?2.“按列优先按列优先”如何映像如何映像?6第6页，共33页，编辑于2022年，星期六2.静态数组元素的地址计算v以C语言为例。设数组元素的起始地址为b,每个元素占用L个单元（元素所占单元量由元素的类型而定），元素a的地址用Loc(a)表示。1）一维数组：）一维数组：即即:Loc(a0)=b;Loc(a1)=b+L;Loc(ai)=b+iL;规律：任一元素规律：任一元素ai的地址的地址:a0a1ai-1aian-1An=(a0,a1,ai,an-1)起始地址起始地址b+(ai前的元素个数前的元素个数i)L 起址起址 b:b+L:b+iL:L图图5.27第7页，共33页，编辑于2022年，星期六数组元素的地址计算2）二维数组：）二维数组：a00a0,n-1ai0aijam-1,n-1由图由图5.3知：知：Loc(a00)=b Loc(ai0)=b+(ai0前元素个数前元素个数)L=b+(in)L Loc(aij)=b+(aij前元素个数前元素个数)L=b+in+jL例例5-1 设设二二维维数数组组A78，起起始始地地址址b=1000，每每个个元元素素所所占占单单元元量量L=3，则则Loc(a5,6)=1000+(58+6)3=1138。inj映像映像 起址起址 b:b+L:b+inL:b+in+jL:图图5.3a00 a01 a0j a0n-1.ai0 ai1 aij.ain-1.am-10 am-11 am-1j am-1n-1 Amn=8第8页，共33页，编辑于2022年，星期六数组元素的地址计算3）三维数组）三维数组：由图5.5可知：Loc(a000)=b 图图5.5 Loc(ai00)=b+(inp)L Loc(aij0)=b+(inp+jp)L Loc(aijk)=b+(inp+jp+k)L aijk前的元素个数。a000ai00aij0aijk9第9页，共33页，编辑于2022年，星期六数组元素的地址计算4）n维数组维数组 从以上的地址公式推导中得出这样一条规律：数组中任一元素的地址数组中任一元素的地址=起址起址b+该元素前的个数该元素前的个数元素单元量元素单元量L。故n维数组Au1u2.un中任一元素ai1.in的地址为：Loc(ai1i2in)=b+(i1u2u3 un+i2u3u4 un+in-1un+in)L =b+()L元素按“列优先”方式存储时，地址计算方法类似，不再赘述。有了数组元素的地址计算公式，给出相应参数后，能够很快求出任一元素的地址，然后按地址存取相应元素，故对数组的存取是随机存取（或按公式存取）。5.2.2数组的动态存储方式（略）数组的动态存储方式（略）10第10页，共33页，编辑于2022年，星期六5.2 矩阵的压缩存储信息的压缩存储是一项专业技术，在当今的多媒体应用中显得尤为重要。但本节只是讨论矩阵（或二维数组）中元素的压缩存储。在矩阵中，往往会出现许多值相同的元素或元素，为节省存储空间，可以采用某些技术对这类矩阵进行压缩存储。压缩存储的原则是：对多个值相同的元素只存储其中之一，对元素甚至不分配存储空间。5.3.1特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵：值相同的元素或元素在矩阵中的分布遵循一定规律。1.对称矩阵对称矩阵：满足aij=aji，(1i,jn)a11 a22 aii ann Ann=aijaji11第11页，共33页，编辑于2022年，星期六特殊矩阵的压缩aij与aji对称相等，二者只需分配一个存储单元，即只存储包括主对角线的下三角(或上三角)元素。于是Ann所需单元数为n(n+1)/2，而不压缩存储需要n2个单元。当n很大时，几乎能压缩原存储空间的一半。具体做法：设置数组Sn(n+1)/2+1作为An.n的存储空间，且按行的次序存放Ann中包括主对角线的下三角元素，如图5.5所示。a11a21a22aijann Sn(n+1)/2+1:1 2 3 .k.n(n+1)/2图图5.5其中其中aij存入存入Sk单元，下标（单元，下标（i,j）与）与k的关系为：的关系为：i(i-1)/2+j 当当ij 时；时；Si(i-1)/2+j 当当ij 时；时；k=即：即：aij=j(j-1)/2+i 当当ij时。时。Sj(j-1)/2+i 当当ij)(ij)时，时，K=0.K=0.对于下三角矩阵，类似于对称矩阵，即只存储包括主对角对于下三角矩阵，类似于对称矩阵，即只存储包括主对角线的下三角元素。而当线的下三角元素。而当ijidata1 A-datatu 图图5.816第16页，共33页，编辑于2022年，星期六三元组表的转置然而，稀疏矩阵的压缩存储会给矩阵运算带来一些不便，算法要复杂些。这里的运算指求矩阵的转置，两矩阵相加和相乘等。我们只讨论矩阵的转置的算法。未压缩前，求矩阵A的转置矩阵B，算法很简单：for(col=1;col=nu;col+)for(row=1;rowdata3.j=1,故将A-data3转置：(1，2，6)=B-data1，又A-data6.j=1，所以A-data6转置：(1，4，3)=B-data2，完成第一列的转换，依此类推。算法描述算法描述：void Transm(Tsmtype A,Tsmtype B)int p,q,col;B-mu=A-nu;B-nu=A-mu;B-tu=A-tu;if(A-tu!=0)q=1;/目标表的序号 for(col=1;colnu;col+)for(p=1;ptn;p+)if(A-datap.j=col)B-dataq.i=A-datap.j;/行列互换 B-dataq.j=A-datap.i;B-dataq.v=A-datap.v;q+;18第18页，共33页，编辑于2022年，星期六三元组表的转置 ijv122154216238329413 p 123456 0 2 0 0 4 6 0 8 0 0 0 9 0 0 0 3 0 0 0 0 A45=1 2 3 4 5 colijv126 q 1234561432122393285140 6 0 3 2 0 9 0 0 8 0 0 0 0 0 0 4 0 0 0 B54=（矩阵（矩阵A 的三元组表）的三元组表）图图5.10（转置后的三元组表）（转置后的三元组表）算法的时间复杂度：算法的时间复杂度：O(tn)n=列数列数,t=非非0元个数。元个数。改进算法的复杂度：改进算法的复杂度：O(t+n)（略）（略）19第19页，共33页，编辑于2022年，星期六2.十字链表十字链表是以链表结构形式存储一个稀疏矩阵。矩阵中非0元设置成如下形式的节点：其中i、j分别存放非0元的行列号，head/data或作为一非0元的值域（data）或作为头节点的链指针(head)；down为指向相同列下一个非0元节点的指针，right为指向相同行下一非0元节点的指针。节点类型描述：typedef struct node int i,j;union struct node*head;datatype data;vdata;struct node*down,*right;nodetype,*tlink;ijhead/datadownright20第20页，共33页，编辑于2022年，星期六十字链表1 111 442 223 134 450 04 40 00 00 00 00 00 00 0L例例5-4 5-4 设稀疏矩阵设稀疏矩阵 ：1 0 0 40 2 0 03 0 0 00 0 0 5 A44=A的十字链表如图的十字链表如图5.11：21第21页，共33页，编辑于2022年，星期六建立十字链表算算法法思思路路：先构造空表，其中S取矩阵行列数的最大值，即S=max(m,n)。依次读入每个非0元(i,j,v)，生成一个非0元的节点，对该节点赋读入的值后，将其插入第i行链表和第j列链表的正确位置。算法描述算法描述：void Creattenlink(tlink L,int m,int n,int t)/L为头指针，m,n,t分别为行列号和非0元个数 tlink p,q,Hmaxsize;int i,j,k,s;datatype v;if(mn)s=m;else s=n;/确定头节点的个数 L=(tlink)malloc(sizeof(nodetype);/申请总的头节点 L-i=m;L-j=n;/置行列数 H0=L;for(i=1;ii=p-j=0;p-down=p-right=p;Hi=p;Hi-1-vdata.head=p;Hs-vdata.head=L;/构成循环 22第22页，共33页，编辑于2022年，星期六建立十字链表 for(k=1;ki=i;p-j=j;p-vdata.data=v;/赋值 q=Hi；/取第i行链表头节点指针 while(q-right!=Hi)&(q-right-jright;/找当前非0元节点在行链表中的位置 p-right=q-right;q-right=p;/当前非0元节点插入q节点之后 q=Hj；/取第j列链表头节点指针 while(q-down!=Hj)&(q-down-idown;/找当前非0元节点在列链表中的位置 p-down=q-down;q-down=p;/非0元节点节点插入q节点之后 23第23页，共33页，编辑于2022年，星期六5.4广义表的定义及其操作5.4.1广义表的定义广义表的定义 广义表又称列表(lists),是线型表的推广。在线型表L=(a0aian-1)中，ai是单元素或原子，即 ai本身不再是一个 DS，而广义表记为：LS=(d0d1didn1)其中di（0in-1）既可以是一个原子，又可以是另一个表（称为子表），即表中还可以套表。广义表LS的形式化描述为：LS=(D,R)其中：D=di|didatatype or diLS(递归定义)，i=0,1,.n-1,n0 R=|di,di+1D,0in-2式中n为表长（n=0 时为空表），若di为原子，则称di为LS的单元素，否则di称为LS的子表（满足递归定义)。对非空广义表定义两个函数：Gethead(LS)=d0；Gettail(LS)=(d1.dn-1)。即Gethead(LS)是LS的第一元素d0（当然d0可以为子表），而Gettail(LS)是LS中d1.dn-1的一个子表。对广义表的其它运算（如查找，插入和删除等）类似于线性表的运算（见5.4.2）。24第24页，共33页，编辑于2022年，星期六例5-5 广义表的例子约定：大写字母AZ为表名，小写字母 az为单元素。A=()或A()空表，表长=0，无表头，表尾；B=(a,b)或B(a,b)线性表特例,表长=2,Gethead(B)=a,Gettail(B)=(b)；C=(e,B)或C(e,B)表长=2，Gethead(C)=e,Gettail(C)=(B)=(a,b),表C可以表示为：C(e,(a,b)；D=(A,B,C)或D(A,B,C)表长=3，Gethead(D)=A=(),Gettail(D)=(B,C)=(a,b),(e,(a,b)；E=(a,E)表长=2，Gethead(E)=a,Gettail(E)=(E),整个表E为(a,(a,(a,.)，它为一个特殊的广义表，称为递归表，或无限表。从例5-5可以看出，广义表有如下特点：（1）表可以嵌套）表可以嵌套表中元素可以是一个表，称为子表，而子表还可以有子表。如例5-5中表B和表C的结构如图5.13所示。图图5.13CeBababB25第25页，共33页，编辑于2022年，星期六广义表的例子（2）表可以共享）表可以共享表可以是其它表的子表,或表中的元素可取自其他表。如例5-5中表D包含表A、B、C，或A、B、C为D的子表,如图5.16所示。（3）表可以递归）表可以递归表中元素可以是表本身。如例5-5中表E。EaDABCabe图图5.16另另外外，表表中中任任一一单单元元素素可可由由Gethead(Ls)和和Gettail(Ls)函函数数导导出出，如如取取表表A=(a,(b,d,e)中中单单元素元素d的运算为：的运算为：Gethead(Gettail(Gethead(Gettail(A)26第26页，共33页，编辑于2022年，星期六5.5广义表的存储结构对于广义表LS=(d0 didn-1)，由于di可以是单元素或子表，故用顺序存储结构表示LS较为困难，一般采用链表存储，称为广义链表。5.5.1广义表的链式存储广义表的链式存储1单链表示法单链表示法 元素di的节点形式：其中：0 当di为单元素时；data 当atom=0时；atom=data/link=1 当di为子表时。link 当atom=1时。next意义同线性链表，指向di+1所在节点。节点描述：typedef struct node int atom;union datatype data;struct node*link;dtype;struct node*next;Lsnode;atomdata/linknext27第27页，共33页，编辑于2022年，星期六广义表的存储为操作方便，对每一广义表引入头节点，其形式同一般的表节点：例例5-5中广义表A、B、C、D、E的单链表如图5.15所示。11AA=()图图5.150a0b1BB=(a，b)0e11CC=(e，B)1111DD=(A，B，C)0a11EE=(a，E)28第28页，共33页，编辑于2022年，星期六广义表的存储2双链表示法双链表示法元素元素di的节点形式：的节点形式：其中：其中：指向子表的指针指向子表的指针当当di为子表时；为子表时；link1=当当di为原子时。为原子时。表名表名当当di为子表时；为子表时；data=link2：指向：指向di+1所在的节点。所在的节点。原子值原子值当当di为原子时。为原子时。例例5-5中几个广义表的双链表结构如图中几个广义表的双链表结构如图5.16：datalink1link2BACDEaEBeCbaA=B29第29页，共33页，编辑于2022年，星期六广义表的存储例例5-7设职工工资的表头设职工工资的表头H：即即H=(A,B,x)，A=(a1，a2，a3)，B=(b1，b2，b3)。H的双链结构如图的双链结构如图5.18：工资收入工资收入A 扣除扣除B基本工资基本工资 岗位津贴岗位津贴 福利福利 房租房租 水电水电 其他其他 实发实发X a1 a2 a3 b1 b2 b3BAHx5.5.2 广义表基本操作的递归算法（略）广义表基本操作的递归算法（略）a1a2a3b1b2b330第30页，共33页，编辑于2022年，星期六第五章小结 多维数组定义、运算、多维数组定义、运算、存储映像存储映像数组元素地址计算数组元素地址计算:1、2、3、n 维维广义表广义表定义、特点定义、特点存储：单链、双链存储：单链、双链数组数组广义表广义表矩阵压缩存储矩阵压缩存储特殊矩阵：对称、三角、对角线特殊矩阵：对称、三角、对角线稀疏矩阵：三元组表、十字链表稀疏矩阵：三元组表、十字链表31第31页，共33页，编辑于2022年，星期六第五章习题第五章习题第五章习题 1.FORTRAN语言中，数组元素按列优先存放。设每个元素占语言中，数组元素按列优先存放。设每个元素占L个单元，首元素地址个单元，首元素地址=b，试确定：，试确定：一维一维 An=(A1 A2 An);二维二维 Am,n(m行、行、n列列);三维三维 Am,n,p 数组的元素地址计算公式。即数组的元素地址计算公式。即：Loc(Ai)=?Loc(Ai,j)=?Loc(Ai,j,k)=?2.设矩阵设矩阵:若若将将A视视为为一一个个上上三三角角矩矩阵阵时时，请请画画出出A的的“按按行行优优先先存存储储”的的压压缩缩存存储储表表S，并并写写出出A中元素之下标中元素之下标i,j与与S中元素之下标中元素之下标k之间的关系；之间的关系；若将若将A视为一个稀疏矩阵时，请画出视为一个稀疏矩阵时，请画出A的三元组表和十字链表结构。的三元组表和十字链表结构。A55=1 0 0 0 20 3 0 0 40 0 0 5 0 (行列下标i、j满足：1i，j5)0 0 0 6 00 0 0 0 732第32页，共33页，编辑于2022年，星期六第五章习题第五章习题 3.设设 银行一天营业业务表头银行一天营业业务表头H：试用广义表形式表示试用广义表形式表示H，并用，并用Gethead(H)和和Gettail(H)函数提取函数提取d2;画出画出H 的单链及双链结构。的单链及双链结构。存款存款A 取款取款B 活期活期 定期定期D 总存款总存款 支取支取 利息利息 总支付总支付 进款进款X a1 a3 b1 b2 b3 1年年 2年年 3年年 d1 d2 d333第33页，共33页，编辑于2022年，星期六