数据结构数组广义表精.ppt

《数据结构数组广义表精.ppt》由会员分享，可在线阅读，更多相关《数据结构数组广义表精.ppt（31页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构数组广义表数据结构数组广义表第1页，本讲稿共31页数组描述数组描述二维数组可用形式化语言描述，即：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-1关系集Row和Col表明：除数组A(2)周边元素外的其它任一个元素aij，有两个直接前驱ai-1j，aij-1,和两个直接后继ai+1j，aij+1(周边元素的前驱或后继可不足两个)。n维数组也可按上述方法类似定义。二维数组还可以用如下形式描述:A0 Ai Am-1

2、=(A0AiAm-1)-线性表形线性表形式式a00a01a0ja0n-1.ai0ai1 aij.ain-1.am-10am-11am-1jam-1n-1A(2)=Amn=第2页，本讲稿共31页2.数组的基本运算数组的基本运算多维数组是线性表的推广，而线性表是多维数组的特例。在算法语言中，数组一旦生成，其元素的存储空间就固定下来，故数组的运算一般不包括插入和删除这样的操作。对数组运算有：(1)构造一个n维数组：Setarray(A,n,d1d2,.dn)，即生成：Ad1d2.dn（C语言中，1n8）。(2)撤消一个数组：Dearray(A)，释放数组A的存储空间。(3)取值：Aget(A,i1,

3、.,in,x)，将Ai1i2,.,in的值传给变量x。(4)赋值：Assign(A,i1,.,in,x)，将变量x的值传给Ai1i2.in。5.2 数组的存储映像数组的存储映像由于计算机的存储空间是一维的（或线性的），所以存储数组时，要将多维数组中的元素按某种次序映象到一维存储空间，即解决“降维”问题。在PASCAL和C等语言中，是按低维下标优先变化（或按行优先）的方式，存储数组中的元素。如在C语言中，二维数组的映像如图5.1所示。但在FORTRAN语言中，数组元素是按高维下标优先变化或按列优先方式，存储数组中的元素。第3页，本讲稿共31页数组的存储映像数组的存储映像a00a0,n-1ai0a

4、i,n-1am-1,n-1映像映像 （存储器）存储器）a00a01a0ja0n-1.ai0ai1 aij.ain-1.am-10am-11am-1jam-1n-1 Amn=图图5.1思考：思考：1.三维以上数组如何映像三维以上数组如何映像?2.“按列优先按列优先”如何映像如何映像?第4页，本讲稿共31页5.2.1数组元素的地址计算数组元素的地址计算v以C语言为例。设数组元素的起始地址为b,每个元素占用L个单元（元素所占单元量由元素的类型而定），元素a的地址用Loc(a)表示。1.一维数组：一维数组：即即:Loc(a0)=b;Loc(a1)=b+L;Loc(ai)=b+iL;规律：任一元素规律：

5、任一元素ai的地址的地址:a0a1 ai-1aian-1An=(a0,a1,ai,an-1)起始地址起始地址b+(ai前的元素个数前的元素个数i)L 起址起址 b:b+L:b+iL:L图图5.3第5页，本讲稿共31页数组元素的地址计算数组元素的地址计算2.二维数组：二维数组：a00a0,n-1ai0aijam-1,n-1映像映像 （存储器）存储器）起址起址 b:b+L:b+inL:b+in+jL:由图由图5.4知：知：Loc(a00)=b Loc(ai0)=b+(ai0前元素个数前元素个数)L=b+(in)L Loc(aij)=b+(aij前元素个数前元素个数)L=b+in+jL例例5-1 设

6、设二二维维数数组组A78，起起始始地地址址b=1000，每每个个元元素素所所占占单单元元量量L=3，则则Loc(a5,6)=1000+(58+6)3=1138。inj图图5.4a00a01a0ja0n-1.ai0ai1 aij.ain-1.am-10am-11am-1jam-1n-1 Amn=第6页，本讲稿共31页数组元素的地址计算数组元素的地址计算3三维数组三维数组：由图5.5可知：Loc(a000)=b 图图5.5Loc(ai00)=b+(inp)LLoc(aij0)=b+(inp+jp)LLoc(aijk)=b+(inp+jp+k)L可以看出，inp，inp+jp，inp+jp+k分别为

7、ai00，aij0，aijk前的元素个数。a000ai00aij0aijk第7页，本讲稿共31页数组元素的地址计算数组元素的地址计算4n 维数组维数组从以上的地址公式推导中得出这样一条规律：任意维数组中任一元素的地址任意维数组中任一元素的地址=起址起址b+该元素前的个数该元素前的个数元素单元量元素单元量L。故n维数组Au1u2.un，其中任一元素ai1.in的地址为：Loc(ai1i2in)=b+(i1u2u3un+i2u3u4un+in-1un+in)L=b+()L元素按“列优先”方式存储时，地址计算方法类似，不再赘述。有了数组元素的地址计算公式，给出相应参数后，能够很快求出任一元素的地址，

8、然后按地址存取相应元素，故对数组的存取是随机存取（或按公式存取）。5.2.2数组空间的动态生成（略）数组空间的动态生成（略）第8页，本讲稿共31页5.3矩阵的压缩存储矩阵的压缩存储信息的压缩存储是一项专业技术，在当今的多媒体应用中显得尤为重要。但本节只是讨论矩阵（或二维数组）中元素的压缩存储。在矩阵中，往往会出现许多值相同的元素或元素，为节省存储空间，可以采用某些技术对这类矩阵进行压缩存储。压缩存储的原则是：对多个值相同的元素只存储其中之一，对元素甚至不分配存储空间。5.3.1特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵，指的是值相同的元素或元素在矩阵中的分布遵循一定规律的矩阵。1.对称矩阵对

9、称矩阵：满足aij=aji，(1i,jn)a11 a22 aii ann Ann=aijaji第9页，本讲稿共31页特殊矩阵的压缩特殊矩阵的压缩显然，aij与aji对称相等，二者只需分配一个存储单元，即只存储矩阵中包括主对角线的下三角(或上三角)元素。于是Ann所需的存储单元数为n(n+1)/2，而不压缩存储需要n2个存储单元。当n很大时，几乎能压缩原存储空间的一半。具体做法是：设置一个一维数组Sn(n+1)/2+1作为An.n的存储空间，且按行的次序存放Ann中包括主对角线的下三角元素，如图5.7所示。a11a21a22aijann Sn(n+1)/2+1:1 2 3 .k.n(n+1)/2

10、图图5.7a11 a22 aii ann Ann=aij其中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时。第10页，本讲稿共31页特殊矩阵的压缩特殊矩阵的压缩三角矩阵：三角矩阵：（下三角矩阵）(上三角矩阵）显然，对于下三角矩阵，类似于对称矩阵的压缩存储，即只存储包括主对角线的下三角元素。而当ij)时，K=0.图图5.8第11页，本讲稿共31页特殊矩阵的压缩特殊矩阵的压缩3对角线矩阵（对角线矩阵（三对角线）：按行顺序压缩于S中，如图5.9所示。

11、Ca11a12aijann S3n-1:0 1 2 .k .3n-2a11 a12 a21 a22 a23 .aii-1 aii aii+1 .ann-1 ann Ann=CC图图5.93(i-1)当i=j+1时；3i-2当i=j时；归纳为：k=2i+j-2当i=j+1,i=j,i+1=j时。3i-1当i+1=j时；如将i=1,j=2代入,k=20其他。k=第12页，本讲稿共31页5.3.2稀疏矩阵的压缩存储稀疏矩阵的压缩存储特殊矩阵中同值元素的分布有一定的规律可循，而有的矩阵，元素很多（如同一个画面上有几个亮点，其余全是空白），但分布无规律，称这类矩阵为稀疏矩阵。例例5-2 设一个67的矩阵

12、如下：则A67可以视为一个稀疏矩阵。对于矩阵Amn，设非0元素个数为t，若=t/(mn)0.2，则可以将其视为稀疏矩阵。显然，为节省存储空间，须对这类矩阵压缩存储空间，原则是只存储非0元素。一般有“三元组表三元组表”和“十字链表十字链表”的压缩存储方法。0 1 0 2 0 0 00 0 0 0 0 0 0 3 0 0 0 0 4 00 0 5 0 0 0 0 0 6 0 0 0 0 0 7 0 0 8 0 0 0A67=第13页，本讲稿共31页 1三元组表三元组表三元组：（i,j,v），其中i,j分别为非0元素的行、列号，v存放非0元的数值。以行优先的顺序将稀疏矩阵中非0元以三元组形式存入一数

13、组，即所谓的三元组表。三元组表的存储结构的描述：#definemaxsize64/最大非0元个数/typedefStruct/三元组类型/inti,j;datatypev;tritype;/三元组说明符/typedefStructtritypedatamaxsize+1;/三元组表/intmu,nu,tu;/原矩阵的行、列、非0元个数/Tsmtype,*Tsmlink;/三元组表说明符/若说明：TsmlinkA;A=(Tsmlink)malloc(sizeof(Tsmtype);则指针变量A指向一个如图5.10所示的三元组表。对例5-3中A67，设每个元素占16个字节，若不压缩存储，需6716

14、=672（字节），而压缩成三元组表存储时，i,j为整型，故共需：216+816=160（字节）。ijv121142313364435526617648A-data1A-datatu图图5.10第14页，本讲稿共31页三元组表的转置三元组表的转置然而，稀疏矩阵的压缩存储会给矩阵运算带来一些不便，算法要复杂些。这里的运算指求矩阵的转置，两矩阵相加和相乘等。我们只讨论矩阵的转置的算法。未压缩前，求矩阵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

15、，所以A-data6的转置：(1，4，3)=B-data2，完成第一列的转换，依此类推。算法描述算法描述：voidTransm(TsmtypeA,TsmtypeB)intp,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+)/扫描A的所有列/for(p=1;ptn;p+)/扫描所有非0元/if(A-datap.j=col)B-dataq.i=A-datap.j;/行列互换/B-dataq.j=A-datap.i;B-dataq.v=A-datap.v;q+;第16页，本讲稿共31页三元

16、组表的转置三元组表的转置ijv122154216238329413 p123456 0 2 0 0 4 6 0 8 0 0 0 9 0 0 0 3 0 0 0 0A45=1 2 3 4 5 colijv126 q1234561432122393285140 6 0 3 2 0 9 0 0 8 0 0 0 0 0 0 4 0 0 0B54=（矩阵（矩阵A 的三元组表）的三元组表）图图5.12（转置后的三元组表）（转置后的三元组表）算法的时间复杂度：算法的时间复杂度：O(tn)n=列数列数,t=非非0元个数。元个数。改进算法的复杂度：改进算法的复杂度：O(t+n)（略）（略）第17页，本讲稿共31

17、页2.十字链表十字链表十字链表是以链表结构形式存储一个稀疏矩阵。矩阵中非0元设置成如下形式的结点：其中i、j分别存放非0元的行列号，head/data或作为一非0元的值域（data）或作为头结点的链指针(head)；down为指向相同列下一个非0元结点的指针，right为指向相同行下一非0元结点的指针。结点类型描述：typedefstructnodeinti,j;unionstructnode*head;datatypedata;vdata;structnode*down,*right;nodetype,*tlink;ijhead/datadownright第18页，本讲稿共31页十字链表十字

18、链表例例5-4 设稀疏矩阵：1 0 0 40 2 0 03 0 0 00 0 0 5A44=1 111 442 223 134 450 04 40 00 00 00 00 00 00 0LA的十字链表如图的十字链表如图5.13：第19页，本讲稿共31页十字链表十字链表算算法法思思路路：先构造空表，其中S取矩阵行列数的最大值，即S=max(m,n)。依次读入每个非0元(i,j,v)，生成一个非0元的结点，对该结点赋读入的值后，将其插入第i行链表和第j列链表的正确位置。算法描述算法描述：voidCreattenlink(tlinkL,intm,n,t)/L为头指针，m,n,t分别为行列号和非0元个

19、数/tlinkp,q,Hmaxsize;inti,j,k,s;datatypev;if(mn)s=m;elses=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;/构成循环链表/第20页，本讲稿共31页十字链表十字链表for(k=1;ki=i;p-j=j;p-vdata.data=v;/赋值/q=Hi；/取第i行链表头结点指针/while(q-r

20、ight!=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结点之后/第21页，本讲稿共31页5.4广义表的定义广义表的定义广义表又称列表(lists),是线型表的推广。在线型表L=(a0aian-1)中，ai是单元素或称原子，即ai本身不再是一个数据结构，而广义表记为：LS=(d0

21、d1didn1)其中di（0in-1）既可以是一个原子，又可以是另一个表（称为子表），即表中还可以套表。广义表LS的形式化描述为：LS=(D,R)其中：D=di|didatatypeordiLS(递归定义)，i=0,1,.n-1,n0 R=|di,di+1D,0in-2式中n为表长（n=0时为空表），若di为原子，则称di为LS的单元素，否则di称为LS的子表（满足递归定义)。当广义表非空时，定义两个函数：head(LS)=d0；tail(LS)=(d1.dn-1)。即head(LS)是LS的第一元素d0（当然d0可以为子表），而tail(LS)是LS中d1.dn-1的一个子表。对广义表的其它

22、运算（如查找，插入和删除等）类似于线性表的运算。第22页，本讲稿共31页广义表广义表例例5-5 广义表的例子。约定：大写字母AZ为表名，小写字母az为单元素。A=()或A()空表，表长=0，无表头，表尾；B=(a,b)或B(a,b)线性表(广义表特例),表长=2,head(B)=a,tail(B)=(b)；C=(e,B)或C(e,B)表长=2，head(C)=e,tail(C)=(B)=(a,b),表C可以表示为：C(e,(a,b)；D=(A,B,C)或D(A,B,C)表长=3，head(D)=A=(),tail(D)=(B,C)=(a,b),(e,(a,b)；E=(a,E)表长=2，head

23、(E)=a,tail(E)=(E),整个表E为(a,(a,(a,.)，它为一个特殊的广义表，称为递归表，或无限表。从例5-5可以看出，广义表有如下特点：（1）表可以嵌套表中元素可以是一个表，称为子表，而子表还可以有子表。如例5-5中表B和表C的结构如图5.15所示。图图5.15CeBababB第23页，本讲稿共31页广义表广义表（2）表可以共享表可以是其它表的子表，或表中的元素可取自其他的表。如例5-5中表D包含表A、B、C，或A、B、C为D的子表,如图5.16所示。（3）表可以递归表中元素可以是表本身。如例5-5中表E。EaDABCabe图图5.16另外，表中任一单元素可由head(Ls)和

24、tail(Ls)函数导出，如取表A=(a,(b,d,e)中单元素d的运算为：head(tail(head(tail(A)第24页，本讲稿共31页5.5广义表的存储结构广义表的存储结构对于广义表LS=(d0didn-1)，由于di可以是单元素或子表，故用顺序存储结构表示一个广义表较为困难，一般采用链表存储结构，称为广义链表。5.5.1单链及双链结构单链及双链结构1单链表示法单链表示法元素di的结点形式：其中：0当di为单元素时；data当atom=0时；atom=data/link=1当di为子表时。link当atom=1时。next意义同线性链表，指向di+1所在结点。结点描述：typedef

25、structnodeintatom;uniondatatypedata;structnode*link;dtype;structnode*next;Lsnode;atomdata/linknext第25页，本讲稿共31页广义表的存储广义表的存储为了广义表的运算方便，对每一广义表引入头结点，其形式同一般的表结点：例例5-5中广义表A、B、C、D、E的单链表如图5.17所示。11AA=()图图5.170a0b1BB=(a，b)0e11CC=(e，B)1111DD=(A，B，C)0a11EE=(a，E)第26页，本讲稿共31页广义表的存储广义表的存储2双链表示法双链表示法元素di的结点形式：其中：指

26、向子表的指针当di为子表时；link1=当di为原子时。表名当di为子表时；data=link2：指向di+1所在的结点。原子值当di为原子时。例5-5中几个广义表的双链表结构如图图5.18：datalink1link2BACDEaEBeCbaA=B第27页，本讲稿共31页广义表的存储广义表的存储例例5-6设职工工资的表头H：即H=(A,B,x)，A=(a1，a2，a3)，B=(b1，b2，b3)。H的双链结构如图图5.20：工资收入工资收入A 扣除扣除B基本工资基本工资 岗位津贴岗位津贴 福利福利 房租房租 水电水电 其他其他 实发实发X a1 a2 a3 b1 b2 b3BAHx5.5.2

27、 广义表的生成算法、广义表的生成算法、5.5.3 求广义表深度的算法（略）求广义表深度的算法（略）a1a2a3b1b2b3第28页，本讲稿共31页第五章小结第五章小结多维数组定义、运算、多维数组定义、运算、存储映像存储映像数组元素地址计算数组元素地址计算:1、2、3、n 维维广义表广义表定义、特点定义、特点存储：单链、双链存储：单链、双链数组数组广义表广义表矩阵压缩存储矩阵压缩存储特殊矩阵：对称、三角、对角线特殊矩阵：对称、三角、对角线稀疏矩阵：三元组表、十字链表稀疏矩阵：三元组表、十字链表第29页，本讲稿共31页第五章习题第五章习题第五章习题第五章习题 1.FORTRAN语言中，数组元素按列

28、优先存放。设每个元素占语言中，数组元素按列优先存放。设每个元素占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之间的关系；之间的关系；若将若将

29、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 7第30页，本讲稿共31页第五章习题第五章习题 3.设设 银行一天营业业务表头银行一天营业业务表头H：试用广义表形式表示试用广义表形式表示H，并用，并用head(H)和和tail(H)函数提取函数提取d2;画出画出H 的单链及双链结构。的单链及双链结构。存款存款A 取款取款B 活期活期 定期定期D 总存款总存款 支取支取 利息利息 总支付总支付 进款进款X a1 a3 b1 b2 b3 1年年 2年年 3年年 d1 d2 d3第31页，本讲稿共31页